第 K个符号
-> 题目描述
K-th Symbol in Grammar
第一行给定一个初始数字 0。接下来的每一行都根据他的前一行产生： 把前一行字符中的数字 0替换成 01，数字 1替换成 10
需要输出 第 N行的第 K 个数字（行和列的索引均从 1开始）
Examples:
Input: N = 1, K = 1
Output: 0
Input: N = 2, K = 1
Output: 0
Input: N = 2, K = 2
Output: 1
Input: N = 4, K = 5
Output: 1
Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
另：
- N 为一个整数，范围为 [1, 30]
- K 也为一个整数，范围为 [1, 2^(N-1)]
/**
* @param {number} N
* @param {number} K
* @return {number}
*/
var kthGrammar = function(N, K) {
};
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
-> 解法
点击查看
/**
* @param {number} N
* @param {number} K
* @return {number}
*/
var kthGrammar = function (n, k) {
if (k === 1){
return 0
} else {
let j = Math.ceil(k/2)
if (kthGrammar(n-1, j) === 0) {
return k % 2 === 0? 1: 0
} else {
return k % 2
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-> 总结
- 一开始想法是输出第 N行的结果，返回第 K-1个元素，提交发现内存使用超出范围
- 转换方向，找规律。第 N行的第 K个元素由第 N-1行的
Math.ceil(k/2)个元素决定 - 如果
k%2为0，即能整除。则为第 N-1行的Math.ceil(k/2)个元素分裂的两个元素中的第二个，否则为第一个 - 如果第 N-1行的
Math.ceil(k/2)个元素为 0，则两个元素分别为[0, 1], 否则为[1, 0] - 递归出口为第一个元素
0
学习了下最快的解法
- 如果K 小于或等于该行总元素数量的一半，则它的值与前一行的第 K个数相等（新增行元素数为前一行两倍，且前面的值均相等）
- 如果 K 小于或大于该行总元素数量的一半，则第 N的数值为
1 - Val(k-mid)
点击查看
var kthGrammar = function(N, K) {
const Kth = (n,k) => {
if(n==1 || k==1) {
return 0;
}
let noOfBits = 2**(n-1);
let mid = noOfBits/2;
if(k<=mid) {
return Kth(n-1,k);
} else {
return !Kth(n-1,k-mid);
}
}
return Kth(N,K);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
不知道这个规律咋看出来的，感觉没有我发现的规律直观🐶
编辑此页 (opens new window)
更新于: 2019-08-27 15:21