Leetcode 1545. Find Kth Bit in N
2021-09-18 本文已影响0人
SnailTyan
文章作者:Tyan
博客:noahsnail.com | CSDN | 简书
1. Description

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