数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用Python查找第n个二进制字符串中的第k位
假设我们有两个正值n和k，现在我们可以使用以下规则创建一个二进制字符串S_n：
S_1 = "0"
S_i = S_(i-1) 连接 "1" 连接 reverse(invert(S_(i-1))) 对于 i > 1
这里reverse(x)返回反转后的字符串x，invert(x)翻转x中的所有位。
以下是四个这样的字符串示例
S_1 = "0"
S_2 = "011"
S_3 = "0111001"
S_4 = "011100110110001"
我们需要找到S_n中的第k位。
因此，如果输入像n = 4 k = 10，则输出将为1，因为S_4 = "011100110110001"，所以第10位是1（第一位在位置1）。
为了解决这个问题，我们将遵循以下步骤：
如果k等于1，则
返回"0"字符串
否则，
arr := 一个包含单个元素0的数组
arr2 := 一个包含单个元素1的数组
当k > arr的大小，执行以下操作：
templast := arr的副本
temp2last := arr2的副本
arr := templast 连接 "1" 连接 temp2last
arr2 := templast 连接 "0" 连接 temp2last
返回arr中第k-1个元素
让我们看下面的实现来更好地理解：
示例
def solve(n, k): if k == 1: return(str(0)) else: arr = [0] arr2 = [1] while k > len(arr): templast = arr.copy() temp2last = arr2.copy() arr = templast + [1] + temp2last arr2 = templast + [0] + temp2last return(str(arr[k-1])) n = 4 k = 10 print(solve(n, k))
输入
4, 10
输出
1
更新于：2021年5月29日
浏览量：306
广告