Leetcode

Leetcode 1545. Find Kth Bit in N

2021-09-18  本文已影响0人  SnailTyan

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Find Kth Bit in Nth Binary String

2. Solution

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

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
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/
上一篇 下一篇

猜你喜欢

热点阅读