[已解决]Python：每日一题 366

zltzlt

今天的题目：

在第一行我们写上一个 0。接下来的每一行，将前一行中的 0 替换为 01，1 替换为 10。

给定行数 n 和序号 k，返回第 n 行中第 k 个字符。（k 从 1 开始）

示例 1：

输入：n = 1, k = 1
输出：0

示例 2：

输入：n = 2, K = 1
输出：0

示例 3：

输入：n = 2, k = 2
输出：1

示例 4：

输入：n = 4, k = 5
输出：1
解释：
第一行：0
第二行：01
第三行：0110
第四行：01101001

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

kinkon

2020-4-1 19:27:53

def f366(n, k):return bin(k - 1).count('1') % 2

跳转到最佳答案楼层

kinkon

def f366(n, k):return bin(k - 1).count('1') % 2

BngThea

def fun366(n,k):
    s='0'
    if k == 1:
        return '0'
    for i in range(n-1):        
        t = ""
        for l in s:
            add = '01' if l=='0' else '10'
            t+=add
        s = t[:]
    return t[k-1]

ouyunfu

def f366(n,k):
    def f(n):
        if n==1:
            return '0'
        elif n==2:
            return '01'
        else:
            return f(n-1)+f(n-1)[2**(n-3):]+f(n-1)[:2**(n-3)]
    return f(n)[k-1]

TJBEST

我询问了一下，输出可以是字符串或者是数字。我这里采用字符串的形式。
想法非常简单，没用递归，但是思想雷同，我手算递归后发现等价的性质。
楼主 我这里默认您的检验序列没有错误 即输入的（n,k）一定输出‘0’或'1'不会存在其他情况

def fun366(n,k):
   #假设 输入数据不包含错误，即输入(n,k)输出'0'或者'1'无其他情况。得到n实际无效
    def inner(num):
        for each in range(0,num):
            if 2**each < num and 2**(each+1) >= num:
                return each + 1
    count = 0
    while k > 1:
        pow_2 = inner(k)
        k = k - 2**(pow_2-1)
        count += 1
    if count % 2 == 0:
        return '0'
    else:
        return '1'

March2615

def daily366_0(n: int, k: int) -> int:
    # 后一半和前一半1、0互换
    if k > 2 ** (n-1):  # 输入有误
        return -1
    if n == 1:
        return 0
    if k <= 2 ** (n-2):  # 目标在该行的前半段
        return daily366_0(n-1, k)
    else:  # 目标在该行后半段，与前半段是1、0互换的关系
        return daily366_0(n-1, k-2**(n-2)) ^ 1  # n行前半段和n-1行相同

风魔孤行者

def f(n,k):
    x = 0
    while n>1:
        if k > 2**(n-1):
            return False
        else:
            if k <= 2**(n-2):
                k = k
            else:
                k -= 2**(n-2)
                x += 1
            n -= 1
    if x%2 :
        return 1
    else:
        return 0

l0stparadise

def f366(n,k):
    start="0"
    res=""
    while n-1:
        for i in range(len(start)):
            if start[i] == "0":
                res+="01"
            if  start[i] == "1":
                res += "10"
        start=res
        res=""
        n -= 1
    return start[k-1]

TJBEST

@zltzlt 输出是字符还是数？

zltzlt

TJBEST 发表于 2020-4-1 21:40
@zltzlt 输出是字符还是数？

都可以

塔利班

def f366(n,k):
    f=1
    while k>2:
        t=2**(n-2)
        if k>t:
            k-=t
            f=1-f
        n-=1
    return 1-(k-1)^f

永恒的蓝色梦想

占楼

sunrise085

def fun366(n,k):
    if 2**(n-1)<k or n<1 or k<1:
        return None
    code=[]
    k-=1
    if k==0:
        code.append(0)
    while k!=0:
        code.insert(0,k%2)
        k=k//2
    length=len(code)
    flag=True
    for i in code:
        if not i:
            flag=(not flag)
    if flag:
        r=length%2
    else:
        r=(length+1)%2
    return r
    
for i in range(1,33):
    print(fun366(8,i),end="")

旅途Z

def find_n_k(n, k):
    def get_n_k(x, y):
        if x == 1:
            get_num = -1
        elif y % 2 == 0:
            get_num = -get_n_k(x-1, y//2)
        else:
            get_num = get_n_k(x-1, (y+1)//2)
        return get_num
    return (get_n_k(n, k)+1)//2

sYMMetrY

方法一：
def q366(n,k):
    if k == 1 or k == 4:
        return 0
    if k == 2 or k == 3:
        return 1

    if k%2 == 0:
        if k%4 == 0:    
           return q366(n-2,(k//4))
        else:        
            return abs(q366(n-1,(k//2))-1)
        
    else:           
        if (k+1)%4 == 0:
           return abs(q366(n-2,((k+1)//4))-1)
          
        else:
           return q366(n-1,((k+1)//2))

方法二：直接构造数据的字符串

def q366(n,k):
    A = '01'
    a = '10'
    x = A
    i = 3
    while (3 <= i) and (i <= n):
        A = A+a
        a = a+x
        x = A
        i += 1

    return A[k-1]

死骑Reynolds

k = str(bin(int(input('>>>'))))
if k.count('1') % 2 == 0:
    print(0)
else:
    print(1)

这题牛在答案跟n就没关系

思路是对k地板除2得到上一行的第k//2项,以余数来判断是否改变数值
统计递归到0的改变次数然后反推出所求项

Joy187

n,k=map(int,input().split(","))
d="0"
if(n==1 and k==1):
     print("0")
else:
     while(pow(2,n-1)>len(d)):
          for i in d:
               if(i=="0"):
                    d = d.replace("0","01")
               if(i=="1"):
                    d = d.replace("1","10")     
print(d[k-1])

死骑Reynolds

死骑Reynolds 发表于 2020-4-2 02:38
这题牛在答案跟n就没关系

思路是对k地板除2得到上一行的第k//2项,以余数来判断是否改变数值

k = int(input('请输入K的值:'))
count = 0

while k > 1:
    if k % 2 == 1:
        k += 1
        k //= 2
    else:
        k //= 2
        count += 1
if count % 2 == 1:
    print(1)
else:
    print(0)

有点小错误

chen971130

def func(n,k):
    a = [0]
    while 1:
        b = a.copy()
        count = 1
        for i in range(len(a)):
            if a[i] == 0:
                b.insert(i+count,1)
            else:
                b.insert(i+count,0)
            count += 1
        if len(a) == 2**(n-1):
            print(a[k-1])
            break
        a = b.copy()
func(4,5)

easy

蒋博文

先占个楼