【DP】格雷码

xiaoxiao2021-02-28  8

题目描述 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return[0,1,3,2]. Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 Note:  For a given n, a gray code sequence is not uniquely defined. For example,[0,2,3,1]is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

确实没有找到规律....思路参考的题解。

递推公式:n每增加一位,其格雷码为上一次的格雷码顺次添加0再逆向添加1,如:

00 01 11 10———>000 001 011 010 110 111 101 100....

T T真的强...

ps 吐槽一下判题系统,n=0返回0为的格雷码,0位不应该是空吗...竟然还需要返回个0

import java.util.ArrayList; public class Solution { public ArrayList<Integer> grayCode(int n) { ArrayList<Integer> res = new ArrayList<Integer> (); if(n == 0){ res.add(0); return res; } res.add(0);res.add(1); if(n == 1) return res; int base = 1; while(base != n){ for(int i = res.size() - 1; i >= 0; --i){ int temp = res.get(i); temp = temp | (1<<base); res.add(temp); } base++; } return res; } }

转载请注明原文地址: https://www.6miu.com/read-1150159.html

最新回复(0)