題目:
格雷編碼是一個二進制數(shù)字系統(tǒng)灌危,在該系統(tǒng)中讽挟,兩個連續(xù)的數(shù)值僅有一個位數(shù)的差異。
給定一個代表編碼總位數(shù)的非負整數(shù) n悍赢,打印其格雷編碼序列决瞳。格雷編碼序列必須以 0 開頭。
示例 1:
輸入: 2
輸出: [0,1,3,2]
解釋:
00 - 0
01 - 1
11 - 3
10 - 2
對于給定的 n左权,其格雷編碼序列并不唯一皮胡。
例如,[0,2,3,1] 也是一個有效的格雷編碼序列赏迟。
00 - 0
10 - 2
11 - 3
01 - 1
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/gray-code
import java.util.TreeMap;
import java.util.ArrayList;
class Solution {
public List<Integer> grayCode(int n) {
TreeMap<String,Integer> map = new TreeMap<>();
List<Integer> res = new ArrayList<Integer>();
if(n==0) {
res.add(0);
return res;
}
StringBuffer str = new StringBuffer();
for(int i=0;i<n;i++) {
str.append('0');
}
fGrayCode(str,map,res);
return res;
}
private void fGrayCode(StringBuffer str, TreeMap<String, Integer> map, List<Integer> res) {
int num = getInt(str.toString());
map.put(str.toString(),num);
res.add(num);
StringBuffer strBuffer = getNext(str,map);
if(strBuffer!=null) {
fGrayCode(strBuffer,map,res);
}
}
private StringBuffer getNext(StringBuffer str, TreeMap<String, Integer> map) {
StringBuffer temp = new StringBuffer(str);
for(int i=0;i<str.length();i++) {
char c = temp.charAt(i)=='0' ? '1' : '0';
temp.setCharAt(i,c);
if(map.get(temp.toString())==null) {
return temp;
}
c = temp.charAt(i)=='0' ? '1' : '0';
temp.setCharAt(i,c);
}
return null;
}
private int getInt(String str) {
int res = 0;
for(int i=0;i<str.length();i++) {
int c = str.charAt(i)-'0';
res = res*2 + c;
}
return res;
}
}