原文链接: https://leetcode-cn.com/problems/find-kth-bit-in-nth-binary-string
英文原文
Given two positive integers n
and k
, the binary string Sn
is formed as follows:
S1 = "0"
Si = Si-1 + "1" + reverse(invert(Si-1))
fori > 1
Where +
denotes the concatenation operation, reverse(x)
returns the reversed string x, and invert(x)
inverts all the bits in x (0 changes to 1 and 1 changes to 0).
For example, the first 4 strings in the above sequence are:
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
Return the kth
bit in Sn
. It is guaranteed that k
is valid for the given n
.
Example 1:
Input: n = 3, k = 1 Output: "0" Explanation: S3 is "0111001". The first bit is "0".
Example 2:
Input: n = 4, k = 11 Output: "1" Explanation: S4 is "011100110110001". The 11th bit is "1".
Example 3:
Input: n = 1, k = 1 Output: "0"
Example 4:
Input: n = 2, k = 3 Output: "1"
Constraints:
1 <= n <= 20
1 <= k <= 2n - 1
中文题目
给你两个正整数 n
和 k
,二进制字符串 Sn
的形成规则如下:
S1 = "0"
- 当
i > 1
时,Si = Si-1 + "1" + reverse(invert(Si-1))
其中 +
表示串联操作,reverse(x)
返回反转 x
后得到的字符串,而 invert(x)
则会翻转 x 中的每一位(0 变为 1,而 1 变为 0)。
例如,符合上述描述的序列的前 4 个字符串依次是:
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
请你返回 Sn
的 第 k
位字符 ,题目数据保证 k
一定在 Sn
长度范围以内。
示例 1:
输入:n = 3, k = 1 输出:"0" 解释:S3 为 "0111001",其第 1 位为 "0" 。
示例 2:
输入:n = 4, k = 11 输出:"1" 解释:S4 为 "011100110110001",其第 11 位为 "1" 。
示例 3:
输入:n = 1, k = 1 输出:"0"
示例 4:
输入:n = 2, k = 3 输出:"1"
提示:
1 <= n <= 20
1 <= k <= 2n - 1
通过代码
高赞题解
解题思路
递归 将时间复杂度降到logn
代码
class Solution {
private:
char ch_not(char ch) {
if(ch == '0') { return '1'; }
else { return '0'; }
}
public:
char findKthBit(int n, int k) {
if(n == 1) { return '0'; }
int mid = (1<<(n-1));
if(k == mid) { return '1'; }
if(k < mid) { return findKthBit(n-1, k); }
return ch_not(findKthBit(n-1, (1<<n) - k));
}
};
统计信息
通过次数 | 提交次数 | AC比率 |
---|---|---|
7713 | 13893 | 55.5% |
提交历史
提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
---|