佳宸学习和分享笔记的地方

0%

设计问题,数学 leetcode

随机数组

Shuffle an Array

打乱一个没有重复元素的数组。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* @param {number[]} nums
*/
var Solution = function(nums) {
this.nums = nums
};

/**
* Resets the array to its original configuration and return it.
* @return {number[]}
*/
Solution.prototype.reset = function() {
return this.nums
};

/**
* Returns a random shuffling of the array.
* @return {number[]}
*/
Solution.prototype.shuffle = function() {
// 并不是真正随机,sort小于10个是插入排序,大于是快速排序
// nums.sort(()=>Math.random() - 0.5)

// 扩展运算符 深拷贝 ,直接赋值是赋引用地址,会把原数组改变
let arr = [...this.nums]
let len = this.nums.length
let j ,x
// 取得随机位置,与当前位置交换
while(len) {
j = Math.floor(Math.random() * (len--))
// [arr[i], arr[random]] = [arr[random], arr[i]]
// 结构赋值leetcode用不了有点奇怪
t = arr[len]
arr[len] = arr[j]
arr[j] = t
}
return arr
};

/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(nums)
* var param_1 = obj.reset()
* var param_2 = obj.shuffle()
*/

Fizz Buzz

写一个程序,输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数,输出“Fizz”;

  2. 如果 n 是5的倍数,输出“Buzz”;

  3. 如果 n 同时是3和5的倍数,输出 “FizzBuzz”。

解:除余数,然后字符串拼接,如果不是就直接加数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number} n
* @return {string[]}
*/
var fizzBuzz = function(n) {
let str = []
for(let i = 1; i <= n; i++) {
let x = ''
x += i % 3 ? '' : 'Fizz'
x += i % 5 ? '' : 'Buzz'
if(!x) {
x += i
}
str.push(x)
}
return str
};

计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

1
2
3
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解:厄拉多塞筛法,把当前循环数的倍数全都标记,没有标记的就是质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
let count = 0,
arr = []
for(let i = 2; i < n; i++) {
if(!arr[i]) {
count++
// 从两倍开始
for(let j = i * 2; j < n; j += i) {
arr[j] = true
}
}
}
return count
};

3的幂

给定一个整数,写一个函数来判断它是否是 3 的幂次方。

示例 1:

1
2
输入: 27
输出: true

示例 2:

1
2
输入: 0
输出: false

示例 3:

1
2
输入: 9
输出: true

示例 4:

1
2
输入: 45
输出: false

进阶:
你能不使用循环或者递归来完成本题吗?

解:可以使用3进制转换

  • n = 1 时 ==> 转3进制数为 1
  • n = 3 时 ==> 转3进制数为 10
  • n = 9 时 ==> 转3进制数为 100
  • n = 27 时 ==> 转3进制数为 1000

得出结论,3的幂次方的3进制都是1开头的,后面都是0

进制转换:Number.prototype.toString()

1
2
3
4
5
6
7
8
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfThree = function(n) {
// 匹配1开头的 0有0个或以上
return /^10*$/.test(n.toString(3))
};

罗马数字转整数

罗马数字包含以下七种字符: IVXLCDM

1
2
3
4
5
6
7
8
字符          数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

1
2
输入: "III"
输出: 3

示例 2:

1
2
输入: "IV"
输出: 4

解:先把罗马对应的数值存map,然后与后一个比较,如果小于后一个就是减,大于就是加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
let romaMap = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
let sum = 0
for(let i = 0; i < s.length; i++) {
romaMap[s[i]] < romaMap[s[i+1]] ? sum -= romaMap[s[i]] : sum += romaMap[s[i]]
}
return sum
};