LCOF-62圆圈中最后剩下的数字

description

开始采用暴力法,run time error

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var lastRemaining = function(n, m) {
let nums=[];
for(let i=0; i<n; ++i) nums.push(i);
let start = 0;
while(nums.length>1) {
let i=start;
for(let j=0; j<m-1;j++, i=(i+1)%nums.length) {
}
nums.splice(i,1);
if(i===nums.length) start=0;
else start = i;
}
return nums[0];
};
  1. n个人编号0, 1, …, n-1, 每数m次删掉一个人
  2. 假设有函数f(n)表示n个人最终剩下的人的编号
  3. n个人删掉一个人后,可以看作是n-1的状态,不过有自己的编号
  4. n个人删掉第一个人的编号是(m-1)%n, 那么在被删除这个人后面的编号m%n,对应的是n-1个人时,编号为0的那个人。所以n时编号为m%n的那个人,n-1个人时编号为i的人就是n个人时(m+i)%n
  5. 所以f(n)=(m+f(n-1))%n
  6. f(1) = 0

在JavaScript语言中会爆栈,因此改写为迭代

1
2
3
4
5
6
7
var lastRemaining = function (n, m) {
let ans = 0;
for (let i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
};

lCOF-60

​ # 剑指 Offer 60. n个骰子的点数

description

At first use recursion:

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
var twoSum = function(n) {
let m = new Map();
dfs(m, 0, n,0);
let sum = 0;
let ret= [];
for(let [k, v] of m.entries()) {
sum+=v;
ret.push(v);
}
for( let i = 0; i< ret.length; ++i) {
ret[i] = ret[i] / sum
}
return ret;
};

var dfs = function(m, start, n, sum) {
if(start===n) {
if(m.has(sum)) {
m.set(sum, m.get(sum)+1);
} else {
m.set(sum, 1);
}
return;
}
for(let i=1; i<=6; ++i) {
sum+=i;
dfs(m, start+1, n, sum);
sum-=i;
}
}

Unfortunetely, rum time error.

Refer to the official answer, we could use iterative method.

1
2
3
4
5
6
7
8
9
10
11
var twoSum = function(n) {
if(n<1) return []
const res = [0, 1, 1, 1, 1, 1, 1];
for(let i = 1; i<n; ++i) {//control times for simulation
for(let j = 6*n; j>0; j--) {//control simulation
res[j] = res.slice(Math.max(0, j-6), j)
.reduce((acc, cur)=>acc+cur, 0);
}
}
return res.slice(1).map(num=>num/Math.pow(6,n)).filter((i)=>i!=0);
};

The time complexity is O(n2), and space complexity is O(n).