[已解决]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

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

复制代码

跳转到最佳答案楼层

kinkon

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

复制代码

BngThea

1. def fun366(n,k):
   
2.     s='0'
   
3.     if k == 1:
   
4.         return '0'
   
5.     for i in range(n-1):        
   
6.         t = ""
   
7.         for l in s:
   
8.             add = '01' if l=='0' else '10'
   
9.             t+=add
   
10.         s = t[:]
    
11.     return t[k-1]

复制代码

ouyunfu

1. def f366(n,k):
   
2.     def f(n):
   
3.         if n==1:
   
4.             return '0'
   
5.         elif n==2:
   
6.             return '01'
   
7.         else:
   
8.             return f(n-1)+f(n-1)[2**(n-3):]+f(n-1)[:2**(n-3)]
   
9.     return f(n)[k-1]

复制代码

TJBEST

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

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

复制代码

March2615

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

复制代码

风魔孤行者

1. def f(n,k):
   
2.     x = 0
   
3.     while n>1:
   
4.         if k > 2**(n-1):
   
5.             return False
   
6.         else:
   
7.             if k <= 2**(n-2):
   
8.                 k = k
   
9.             else:
   
10.                 k -= 2**(n-2)
    
11.                 x += 1
    
12.             n -= 1
    
13.     if x%2 :
    
14.         return 1
    
15.     else:
    
16.         return 0

复制代码

l0stparadise

1. def f366(n,k):
   
2.     start="0"
   
3.     res=""
   
4.     while n-1:
   
5.         for i in range(len(start)):
   
6.             if start[i] == "0":
   
7.                 res+="01"
   
8.             if  start[i] == "1":
   
9.                 res += "10"
   
10.         start=res
    
11.         res=""
    
12.         n -= 1
    
13.     return start[k-1]

复制代码

TJBEST

@zltzlt 输出是字符还是数？

zltzlt

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

都可以

塔利班

1. def f366(n,k):
   
2.     f=1
   
3.     while k>2:
   
4.         t=2**(n-2)
   
5.         if k>t:
   
6.             k-=t
   
7.             f=1-f
   
8.         n-=1
   
9.     return 1-(k-1)^f

复制代码

永恒的蓝色梦想

占楼

sunrise085

1. def fun366(n,k):
   
2.     if 2**(n-1)<k or n<1 or k<1:
   
3.         return None
   
4.     code=[]
   
5.     k-=1
   
6.     if k==0:
   
7.         code.append(0)
   
8.     while k!=0:
   
9.         code.insert(0,k%2)
   
10.         k=k//2
    
11.     length=len(code)
    
12.     flag=True
    
13.     for i in code:
    
14.         if not i:
    
15.             flag=(not flag)
    
16.     if flag:
    
17.         r=length%2
    
18.     else:
    
19.         r=(length+1)%2
    
20.     return r
    
21.    
    
22. for i in range(1,33):
    
23.     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

1. 方法一：
   
2. def q366(n,k):
   
3.     if k == 1 or k == 4:
   
4.         return 0
   
5.     if k == 2 or k == 3:
   
6.         return 1
   
7. 
   
8.     if k%2 == 0:
   
9.         if k%4 == 0:   
   
10.            return q366(n-2,(k//4))
    
11.         else:        
    
12.             return abs(q366(n-1,(k//2))-1)
    
13.         
    
14.     else:           
    
15.         if (k+1)%4 == 0:
    
16.            return abs(q366(n-2,((k+1)//4))-1)
    
17.          
    
18.         else:
    
19.            return q366(n-1,((k+1)//2))

复制代码

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

1. def q366(n,k):
   
2.     A = '01'
   
3.     a = '10'
   
4.     x = A
   
5.     i = 3
   
6.     while (3 <= i) and (i <= n):
   
7.         A = A+a
   
8.         a = a+x
   
9.         x = A
   
10.         i += 1
    
11. 
    
12.     return A[k-1]

复制代码

死骑Reynolds

1. k = str(bin(int(input('>>>'))))
   
2. if k.count('1') % 2 == 0:
   
3.     print(0)
   
4. else:
   
5.     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项,以余数来判断是否改变数值

1. k = int(input('请输入K的值:'))
   
2. count = 0
   
3. 
   
4. while k > 1:
   
5.     if k % 2 == 1:
   
6.         k += 1
   
7.         k //= 2
   
8.     else:
   
9.         k //= 2
   
10.         count += 1
    
11. if count % 2 == 1:
    
12.     print(1)
    
13. else:
    
14.     print(0)

复制代码

有点小错误

chen971130

1. def func(n,k):
   
2.     a = [0]
   
3.     while 1:
   
4.         b = a.copy()
   
5.         count = 1
   
6.         for i in range(len(a)):
   
7.             if a[i] == 0:
   
8.                 b.insert(i+count,1)
   
9.             else:
   
10.                 b.insert(i+count,0)
    
11.             count += 1
    
12.         if len(a) == 2**(n-1):
    
13.             print(a[k-1])
    
14.             break
    
15.         a = b.copy()
    
16. func(4,5)

复制代码

easy

蒋博文

先占个楼