[leetcode] 1238. Circular Permutation in Binary Representation

[leetcode] 1238. Circular Permutation in Binary Representation

Description

Given 2 integers n and start. Your task is return any permutation p of (0,1,2…,2^n -1) such that :

p[0] = startp[i] and p[i+1] differ by only one bit in their binary representation.p[0] and p[2^n -1] must also differ by only one bit in their binary representation.Example 1:

Input: n = 2, start = 3Output: [3,2,0,1]Explanation: The binary representation of the permutation is (11,10,00,01). All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2Output: [2,6,7,5,4,0,1,3]Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Constraints:

1 <= n <= 160 <= start < 2 ^ n

分析

题目的意思是：求给定数的格雷码。格雷码的计算可以通过i^(i>>1)，其中i=range(1<

具体是怎么推出来的，其实我也不太清楚，哈哈哈。不过可以自己验证一下

代码

class Solution: def circularPermutation(self, n: int, start: int) -> List[int]: res=[] for i in range(1<>1) res.append(t) return res

代码二

class Solution: def circularPermutation(self, n: int, start: int): res=[] for i in range(1<>1) print(i) t=start^i^(i>>1) res.append(t) return resif __name__ == "__main__": solution=Solution() res=solution.circularPermutation(3,2) print(res) #[2, 3, 1, 0, 4, 5, 7, 6] 逆过来也行

参考文献

​​[Java/C++/Python] 4-line Gray Code​​​​Leetcode 1238 Circular Permutation in Binary Representation 格雷码 gray code​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。