Skip to main content

1545. 找出第 N 个二进制字符串中的第 K 位 [medium]

1545. 找出第 N 个二进制字符串中的第 K 位 [medium]​

https://leetcode-cn.com/problems/find-kth-bit-in-nth-binary-string/

给你两个正整数 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

通过次数4,859 | 提交次数8,905

Thrid Try [golang]​

2020-08-17

处理这种很难直接计算的序列，还是用递归无脑解决比较方便，定义好规则就行，不用自己推导出归纳公式来。

比较麻烦的是当k在中间点右边位置，一是中间对称坐标的切换，middle - (k - middle) = 2 * middle - k , 非常清晰。其次需要invert，用map进行01映射即可。

容易出bug的是起始位置，n = 1, k = 1，如果不用特殊条件列出来，按规则定义会被识别为中间点，返回的反而是1而不是0。

// 计算出编码n字符的的长度，不计较是否要在k处提前截断
func slen(n int) int {
    if n == 1 {
        return 1 
    }
    return 2 * slen(n - 1) + 1
}

var moc map[byte]byte = map[byte]byte{'0': '1', '1': '0'}

func findKthBit(n int, k int) byte {
    if n == 1 && k == 1 {
        return '0'  // 不特殊处理也属于中间，但并不是中间
    }
    for {
        middle := slen(n) / 2 + 1
        if k == middle {
            return '1'
        } else if k > middle {
            return moc[findKthBit(n - 1, 2 * middle - k)]
        } else if k < middle {
            return findKthBit(n - 1, k)
        }
    }
}
  • 执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
  • 内存消耗：1.9 MB, 在所有 Go 提交中击败了80.22%的用户

Second Try​

2020-08-17

一看到k的大小为2^20就意识到这么长的字符串可能内存无法存储，于是在first try中一直在考虑进行存数学计算，后来看题解才发现模拟暴力解也能通过。 模拟暴力解能通过的话，这题应该是easy难度才对。 

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def reverse_invert(s):
            moc = {"0": "1", "1": "0"}
            return ''.join([moc[c] for c in reversed(s)])

        s = '0'
        i = 1 
        while i <= n:
            s = s + "1" + reverse_invert(s)
            if len(s) >= k:
                return s[k - 1]
            i += 1


  • 执行用时：320 ms, 在所有 Python3 提交中击败了57.63%的用户
  • 内存消耗：22.7 MB, 在所有 Python3 提交中击败了23.61%的用户

First Try​

2020-08-10

周赛时候的解法，虽然时间复杂度低，但是考虑的映射较多，太耗费时间了。


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        # 想不到规则啊。。。 只能上O(lgN)算法了，找对称映射规律
        
        slen = [0] * (n + 1)
        for i in range(1, n + 1):
            slen[i] = 2 * slen[i - 1] + 1
        
        reverse = 0 
        # print(slen)
        while n >= 1:
            mlen = slen[n] // 2  + 1 
            # print(n, k, reverse, mlen)

            if k != 1 and k == mlen:
                if reverse % 2 == 0:
                    return "1"
                else:
                    return "0"
            if k > mlen:  # 差点缺少判断
                k = mlen - (k - mlen)
                reverse += 1
            if k == 1:
                if reverse % 2 == 0:
                    return "0"
                else:
                    return "1"
            n -= 1
  • 执行用时：40 ms, 在所有 Python3 提交中击败了87.42%的用户
  • 内存消耗：13.7 MB, 在所有 Python3 提交中击败了83.33%的用户