Leetcode 1545. Find Kth Bit in Nth Binary String

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

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

1. Description

Find Kth Bit in Nth Binary String

2. Solution

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

  • Version 1

    class Solution:

    1. def findKthBit(self, n: int, k: int) -> str:
    2.     pre = '0'
    3.     for i in range(1, n):
    4.         current = pre + '1' + self.invert(pre)[::-1]
    5.         pre = current
    6.     return pre[k-1]
  1.     def invert(self, s):
  2.         result = ''
  3.         for ch in s:
  4.             if ch == '1':
  5.                 result += '0'
  6.             else:
  7.                 result += '1'
  8.         return result

  • Version 2

    class Solution:

    1. def findKthBit(self, n: int, k: int) -> str:
    2.     pre = '0'
    3.     for i in range(1, n):
    4.         if len(pre) < k:
    5.             current = pre + '1' + self.invert(pre)[::-1]
    6.             pre = current
    7.         else:
    8.             return pre[k-1]
    9.     return pre[k-1]
  1.     def invert(self, s):
  2.         result = ''
  3.         for ch in s:
  4.             if ch == '1':
  5.                 result += '0'
  6.             else:
  7.                 result += '1'
  8.         return result

Reference

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

发表评论

表情：
评论列表 （有 0 条评论，81人围观）

还没有评论，来说两句吧...

相关阅读