LeetCode89/60 Gray Code/Permutation Sequence--迭代

悠悠 2022-08-07 16:40 136阅读 0赞

一：Leetcode 89 [Gray Code][]

题目：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

分析：题目通过分析会发现这样的规律， 比如当有4位时，首先vector中放入一个0(只有0位的时候)；然后当位数为1时，vector中存放的是0和1；当位数为2时，vector中存放的是【0,1,3,2】实际上就是加入了3和2，而3==1+2， 2==0+2；；当位数为3的时候，vector中存放的是【0,1,3,2,6,7,5,4】也就是加入了后4位亦即：6==2+4， 7==3+4，5==1+4，4==0+4.也就是将原有的vector中元素逆序+上当前位所代表的数字(如第三位就是4，第4位就是8等)

代码：

class Solution {
    public:
        vector<int> grayCode(int n) {
            vector<int> result;
            result.push_back(0);
            for(int i = 0; i < n; i++){
                int k = 1 << i;
                int len = result.size()-1;
                while(len >= 0){
                    result.push_back(result[len] + k);    // 这道题的规律在于数据为从后往前+k放入result中
                    len--;
                }
            }
            return result;
            
        }
    };

二：leetcode 60 [Permutation Sequence][]

题目：

The set `[1,2,3,…,n]` contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,  
We get the following sequence (ie, for n = 3):

1.  `"123"`
2.  `"132"`
3.  `"213"`
4.  `"231"`
5.  `"312"`
6.  `"321"`

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

分析：设元素个数为n，那么排名为k，

第1位要放入的元素：j = ceil(k/(n-1)!) ；剩余元素的排名为：k = k- (j-1)\*t。。注意这里后续要放入元素并不是j，而是还未被放入的元素中的第j位

代码：

class Solution {
    public:
        int factorial(const int &n){
            int sum = 1;
            for(int i = 1; i <= n; i++)
                sum *= i;
            return sum;
            
        }
       
        string getPermutation(int n, int k) {
            string str(n, ' ');
            int x = k;
            vector<int> visited;
            visited.resize(n+1,0);
            for(int i = 0; i < n; i++){
                int t = factorial(n-i-1);
                int j = ceil((x+0.0)/t);     ///  未被访问的元素中排名第j个并不是j 放入str[i]  ceil是大于等于
    			x = x - (j-1)*t;   // 剩余元素所占排名
    			int count = 0;
    			for(int p = 0; p < n; p++){
    				if(!visited[p]) count++;
    				if(count == j){     // 未被访问元素中第j个
    					stringstream ss;
    					ss << p+1;
    					ss >> str[i];
    					visited[p] = 1;
    					break;
    				}
    			}
            }
            return str;
        }
        
    
    };

[Gray Code]: https://leetcode.com/problems/gray-code/
[Permutation Sequence]: https://leetcode.com/problems/permutation-sequence/