会展网站的建设情况,洛阳app开发公司,上海前十名文化传媒公司,网站建设材料格雷编码格雷编码的定义格雷编码的码表LeetCode 89. 格雷编码实例思路与代码思路一#xff1a;找规律代码一代码二思路二#xff1a;与自然数之间的关系#xff08;你必须知道#xff0c;这个规律要去百度才知道#xff09;代码一LeetCode 1238. 循环码排列实例思路与代码…
格雷编码格雷编码的定义格雷编码的码表LeetCode 89. 格雷编码实例思路与代码思路一找规律代码一代码二思路二与自然数之间的关系你必须知道这个规律要去百度才知道代码一LeetCode 1238. 循环码排列实例思路与代码思路一找规律代码一思路二与自然数之间的关系代码一格雷编码的定义
格雷编码我们在大学时期已经了解过了在一组数的编码中若任意两个相邻的代码只有一位二进制数不同则称这种编码为格雷码Gray Code另外由于最大数与最小数之间也仅一位数不同即“首尾相连”因此又称循环码或反射码。 [2] 在数字系统中常要求代码按一定顺序变化。例如按自然数递增计数若采用8421码则数0111变到1000时四位均要变化而在实际电路中4位的变化不可能绝对同时发生则计数中可能出现短暂的其它代码1100、1111等。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。 格雷码Gray code曾用过Grey Code、葛莱码、葛兰码、格莱码、戈莱码、循环码、二进制反射码、最小差错码等名字它们有的是错误的有的易与其它名称混淆建议不再使用它们。
格雷编码的码表
自然数自然数的二进制一位格雷码二位格雷码三位格雷码四位格雷码0000000000000001000110100100012001011011001130011100100010401001100110501011110111601101010101701111000100810001100910011101101010111111101111101211001010131101101114111010011511111000
LeetCode 89. 格雷编码
LeetCode 89. 格雷编码 n 位格雷码序列 是一个由 2n 个整数组成的序列其中 每个整数都在范围 [0, 2n - 1] 内含 0 和 2n - 1 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表示 恰好一位不同 且 第一个 和 最后一个 整数的二进制表示 恰好一位不同 给你一个整数 n 返回任一有效的 n 位格雷码序列 。
实例
输入n 2
输出[0,1,3,2]
解释
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同思路与代码
思路一找规律
观察格雷码的规律具有一定的对称性高位是 1 或者 0并由此就行对称
代码一
//耗时 6ms
class Solution {public ListInteger grayCode(int n) {int count 1;ListInteger res new ArrayList();res.add(0);res.add(1);while (n-- 1) {count 1;for (int i count - 1; i 0; i--) {res.add(res.get(i) count);}}return res;}
}因为res.get(i)是循环方式去取值当n的位数确定后格雷数就已经知道多少了故可以这样写
代码二
class Solution {public ListInteger grayCode(int n) {Integer[] res new Integer[1 n];res[0] 0;res[1] 1;int count 1;while (n-- 1) {count 1;for (int i 0; i count; i) {res[i count] count res[count - i - 1];}}return Arrays.asList(res);}
}思路二与自然数之间的关系你必须知道这个规律要去百度才知道
格雷码→二进制码解码 从左边第二位起将每位与左边一位解码后的值异或作为该位解码后的值最左边一位依然不变。依次异或直到最低位。依次异或转换后的值二进制数就是格雷码转换后二进制码的值。
代码一
class Solution {public ListInteger grayCode(int n) {ListInteger res new ArrayList();int sum 1n;for(int i 0;i sum;i){res.add((i 1) ^ i);}return res;}
}LeetCode 1238. 循环码排列
LeetCode 1238. 循环码排列 给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,…,2^n-1) 的排列 p并且满足 p[0] start p[i] 和 p[i1] 的二进制表示形式只有一位不同 p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同 实例
实例
输入n 2, start 3
输出[3,2,0,1]
解释这个排列的二进制表示是 (11,10,00,01)所有的相邻元素都有一位是不同的另一个有效的排列是 [3,1,0,2]思路与代码
题目与上面的是一样的所有解决方法也是两种
思路一找规律
观察格雷码的规律具有一定的对称性高位是 1 或者 0并由此就行对称
代码一
class Solution {public ListInteger circularPermutation(int n, int start) {ListInteger ans new ArrayList();Integer[] res new Integer[1 n];res[0] 0;res[1] 1;int count 1;int index start; // 找到位置 存在start 为 01的问题故直接赋值过去while (n-- 1) {count 1;for (int i 0; i count; i) {res[i count] count res[count - i - 1];if (res[i count] start) {index i count;}}}for (int i 0; i res.length; i) {ans.add(res[(index i) % res.length]);}return ans;}
}思路二与自然数之间的关系
要通过观察格雷数的 ^ 关系格雷是从0开始的0^任意数都是本身然后格雷数每个与前一个变化相差为一故一直第一个数 ^ 结果就是你想要的
代码一
class Solution {public ListInteger circularPermutation(int n, int start) {ListInteger res new ArrayList();int sum 1n;for(int i 0;i sum;i){res.add((i 1) ^ i ^ start);}return res;}
}
