2개의 정수 n이 있고 시작한다고 가정합니다. 우리의 작업은 다음과 같이 (0,1,2.....,2^n -1)의 순열 p를 반환하는 것입니다. -
- p[0] =시작
- p[i] 및 p[i+1]은 이진 표현에서 1비트만 다릅니다.
- p[0] 및 p[2^n -1]도 이진 표현에서 1비트만 달라야 합니다.
따라서 입력이 n =2 및 시작 =3과 같으면 반환된 배열은 [3,2,0,1]이고 이들은 [11,10,00,01]
입니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans는 배열입니다
- 0~2^n
- 범위의 i에 대해
- 시작 XOR i XOR i/2를 as에 삽입
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> circularPermutation(int n, int start) {
vector <int> ans;
for(int i = 0 ; i < 1<<n; i++){
ans.push_back(start ^ i ^(i>>1));
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.circularPermutation(5,3));
} 입력
5 3
출력
[3, 2, 0, 1, 5, 4, 6, 7, 15, 14, 12, 13, 9, 8, 10, 11, 27, 26, 24, 25, 29, 28, 30, 31, 23, 22, 20, 21, 17, 16, 18, 19, ]