Gray Code(Leetcode 89)

2565 단어
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.
public class Solution {
    public List<Integer> grayCode(int n) {
		List list=new LinkedList<>();
        int length=1<<n;
        for(int i=0;i<length;i++)
        	list.add(i^(i>>1));
        return list;
    }
}

그레코드의 특징은 다음과 같다.
두 수에 인접한 그레코드는 단지 한 개의 이진법만 변화가 생겼다.
그리고 그 범위 내의 최소치와 최대치도 단지 한 개의 이진법만 변화한다.
세 자리를 예로 들면 다음과 같습니다.
000^000-->000
001^000-->001
010^001-->011
011^001-->010
100^010-->110
101^010-->111
110^011-->101
111^011-->100
두 개의 숫자가 한 조로 되어 있고 각 조 사이에는 한 개의 숫자만 떨어진다. 즉, 마지막 자리, 첫 번째는 0이고 두 번째는 1이다.그룹 내의 두 숫자와 다르거나 다른 숫자는 같기 때문에 그룹 내의 변환 후 두 숫자는 반드시 차이가 있을 뿐만 아니라 한 개의 차이만 있을 것이라고 보장한다.
그룹과 그룹 사이의 근접한 두 개의 숫자, 그 다음 하나는 앞의 숫자의 가장 오른쪽에 있는 연속된 1을 모두 0으로 설정한 다음에 연속된 1의 앞자리에서 1로 설정한다. 이들의 다른 형식과 유사하다.모두 그 자체에 비해 오른쪽으로 한 자리를 옮겼는데 결과는 두 가지가 다르거나 숫자가 같다(1과 1, 0과 0) 결과는 0이다. 원래 자신이 상대적으로 변화한 두 자리에서만 교체되고 뒤에 있는 숫자는 앞의 숫자보다 앞의 숫자가 하나 더 많다.
이렇게 하면 그룹 내, 그룹 간에 모두 앞의 숫자와 한 자리 차이가 난다.Gray Code의 간격이 모두 1이고 가장 큰 숫자와 가장 작은 숫자도 한 자리 차이이다. 다른 특성으로 인해 뒤의 부분은 모두 0이 된다.
반복 생성 코드 테이블
이런 방법은 그레코드가 반사코드라는 사실을 바탕으로 귀속되는 다음과 같은 규칙을 이용하여 구성한다.
1위 그레코드는 두 글자가 있어요.

(n+1)비트 그레코드의 앞2
n개의 코드는 n자리 그레코드의 코드와 같아서 순서대로 쓰고 접두사 0을 붙인다

(n+1)비트 그레코드의 뒷2
n개의 코드는 n자리 그레코드의 코드와 같고 역순으로 쓰고 접두사를 붙인다

2비트 그레코드
3비트 그레코드
4비트 그레코드
4비트 자연 바이너리
00
01
11
10
000
001
011
010
110
111
101
100
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

좋은 웹페이지 즐겨찾기