C++LeetCode 구현(89.그레이 코드)
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.
이 문 제 는 그레이 코드 에 관 한 것 이다.갑자기 보 니 그레이 코드 를 전혀 접 해 본 적 이 없 는 것 같 았 다.그러나 위 키 피 디 아 를 보고 은은 한 느낌 이 들 었 다.아,선생님 께 다 드 렸 다.이 문 제 는 그레이 코드 를 모 르 면 정말 잘 풀 리 지 않 는 다.다행히 위 키 피 디 아 를 보완 했다.위 에서 그레이 코드 는 순환 바 이 너 리 단위 의 거리 코드 라 고 말 했다.주요 특징 은 두 개의 인접 수의 코드 가 한 개의 바 이 너 리 만 다른 코드 라 는 것 이다.그레이 코드 의 처 리 는 주로 비트 조작 이다.LeetCode 에서 비트 조작 에 관 한 문제 도 흔히 볼 수 있다.예 를 들 어 Repeated DNA Sequences 중복 되 는 DNA 서열 구하 기 Single Number 단독 숫자 잠깐 만.세 분 의 그레이 코드 와 이 진 수 는 다음 과 같 습 니 다.
Int Grey Code Binary
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111
사실 이 문 제 는 여러 가지 해법 이 있다.먼저 가장 간단 한 것 은 그레이 코드 와 이 진수 간 의 상호 전환 을 사용 하 는 것 이다.전환 방법 을 알 게 된 후에 이 문 제 는 전혀 어렵 지 않다.코드 는 다음 과 같다.
해법 1:
// Binary to grey code
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res;
for (int i = 0; i < pow(2,n); ++i) {
res.push_back((i >> 1) ^ i);
}
return res;
}
};
그 다음 에 우 리 는 다른 해법 을 살 펴 보 겠 습 니 다.위 키 백과 에서 그레이 코드 의 성질 을 참고 하 세 요.하 나 는 거울 면 이 배열 되 어 있 고 n 비트 의 그레이 코드 는 n-1 비트 의 그레이 코드 이상 에서 거울 로 발사 한 후에 새로운 비트 를 더 하 는 방식 으로 신속하게 얻 을 수 있 습 니 다.이 성질 이 있 으 면 우 리 는 코드 를 다음 과 같이 쉽게 쓸 수 있다.
해법 2:
// Mirror arrangement
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res{0};
for (int i = 0; i < n; ++i) {
int size = res.size();
for (int j = size - 1; j >= 0; --j) {
res.push_back(res[j] | (1 << i));
}
}
return res;
}
};
위 키 백과 에 또 하나의 그레이 코드 의 성질 은 직접 배열 하 는 것 이다.이 진 을 0 값 으로 하 는 그레이 코드 는 0 번 째 항목 이 고 첫 번 째 항목 은 오른쪽 에 있 는 비트 원 을 바 꾸 고 두 번 째 항목 은 오른쪽 에서 첫 번 째 가 1 인 비트 원 의 왼쪽 비트 원 을 바 꾸 며 세 번 째,네 번 째 방법 은 첫 번 째,두 번 째 항목 과 같다.이렇게 반복 하면 n 개의 비트 원 의 그레이 코드 를 배열 할 수 있다.이 성질 에 따라 코드 를 쓸 수 있 지만 앞의 것 에 비해 약간 복잡 합 니 다.코드 는 다음 과 같 습 니 다.0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
해법 3:
// Direct arrangement
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res{0};
int len = pow(2, n);
for (int i = 1; i < len; ++i) {
int pre = res.back();
if (i % 2 == 1) {
pre = (pre & (len - 2)) | ((~pre) & 1);
} else {
int cnt = 1, t = pre;
while ((t & 1) != 1) {
++cnt;
t >>= 1;
}
if ((pre & (1 << cnt)) == 0) pre |= (1 << cnt);
else pre &= ~(1 << cnt);
}
res.push_back(pre);
}
return res;
}
};
위의 세 가지 해법 은 모두 그레이 코드 와 그 성질 을 미리 알 아야 한다.만약 에 우리 가 이전에 그레이 코드 를 접촉 한 적 이 없다 면 우 리 는 비교적 어 리 석 은 방법 으로 결 과 를 찾 을 수 있다.예 를 들 어 아래 의 이런 방법 은 하나의 set 로 이미 발생 한 결 과 를 보존 할 수 있다.우 리 는 0 부터 이 진 매 사람 을 옮 겨 다 니 며 그 에 대해 반대 한다.그 다음 에 set 에 나타 난 적 이 있 는 지 확인 합 니 다.없 으 면 set 와 결과 res 에 가입 한 다음 에 이 수의 모든 사람 을 옮 겨 다 니 면 모든 그레이 코드 를 찾 을 수 있 습 니 다.코드 는 다음 과 같 습 니 다.해법 4:
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res;
unordered_set<int> s;
helper(n, s, 0, res);
return res;
}
void helper(int n, unordered_set<int>& s, int out, vector<int>& res) {
if (!s.count(out)) {
s.insert(out);
res.push_back(out);
}
for (int i = 0; i < n; ++i) {
int t = out;
if ((t & (1 << i)) == 0) t |= (1 << i);
else t &= ~(1 << i);
if (s.count(t)) continue;
helper(n, s, t, res);
break;
}
}
};
재 귀 방법 이 실 현 될 수 있 는 이상 해당 하 는 교체 기법 이 있 습 니 다.당연히 stack 으로 보조 해 야 합 니 다.코드 는 다음 과 같 습 니 다.해법 5:
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res{0};
unordered_set<int> s;
stack<int> st;
st.push(0);
s.insert(0);
while (!st.empty()) {
int t = st.top(); st.pop();
for (int i = 0; i < n; ++i) {
int k = t;
if ((k & (1 << i)) == 0) k |= (1 << i);
else k &= ~(1 << i);
if (s.count(k)) continue;
s.insert(k);
st.push(k);
res.push_back(k);
break;
}
}
return res;
}
};
C++구현 LeetCode(89.그레이 코드)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 그레이 코드 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Visual Studio에서 파일 폴더 구분 (포함 경로 설정)Visual Studio에서 c, cpp, h, hpp 파일을 폴더로 나누고 싶었습니까? 어쩌면 대부분의 사람들이 있다고 생각합니다. 처음에 파일이 만들어지는 장소는 프로젝트 파일 등과 같은 장소에 있기 때문에 파일...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.