Leetcode 1545. Find Kth Bit in Nth Binary String

一时失言乱红尘 2022-09-04 05:51 7阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 1. Description ##

![Find Kth Bit in Nth Binary String][]

## 2. Solution ##

\*\*解析：\*\*Version 1，依次求出`Si`，返回对应的第`k`位即可。Version 2进行了优化，当字符串的长度大于等于`k`时，第`k`位字符就已经可以确定并返回了，不需要执行到`Sn`。

*  Version 1

class Solution:
        def findKthBit(self, n: int, k: int) -> str:
            pre = '0'
            for i in range(1, n):
                current = pre + '1' + self.invert(pre)[::-1]
                pre = current
            return pre[k-1]
    
    
        def invert(self, s):
            result = ''
            for ch in s:
                if ch == '1':
                    result += '0'
                else:
                    result += '1'
            return result

*  Version 2

class Solution:
        def findKthBit(self, n: int, k: int) -> str:
            pre = '0'
            for i in range(1, n):
                if len(pre) < k:
                    current = pre + '1' + self.invert(pre)[::-1]
                    pre = current
                else:
                    return pre[k-1]
            return pre[k-1]
    
    
        def invert(self, s):
            result = ''
            for ch in s:
                if ch == '1':
                    result += '0'
                else:
                    result += '1'
            return result

## Reference ##

1.  [https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/][https_leetcode.com_problems_find-kth-bit-in-nth-binary-string]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Find Kth Bit in Nth Binary String]: /images/20220829/32337763dd0b41d8a2f29eb329900f46.png
[https_leetcode.com_problems_find-kth-bit-in-nth-binary-string]: https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/