LeetCode 1238. Circular Permutation in Binary Representation

思路

題目要求給出任意一種全排列數組。我們可以設計一種算法，每次改變一個比特位，進而生成一個新的數。

這個具體的生成算法就是，從最後一位嘗試改變，如果改變後的數之前周遊到了，則撤回改變，并嘗試下一個數。而其中判決生成的數之前是否已經周遊過了，需要一個 HashMap 記錄，這裡我們直接用 count 數組記錄就行。

public int next(int a, int[] count) {
        int xor = 1;
        while (true) {
            a ^= xor;
            if (count[a] == 0) {
                count[a]=1;
                return a;
            }
            a ^= xor;
            xor <<= 1;
        }

    }
           

這樣不斷生成新的數，可以保證新數和前面的數隻差一個比特位。也不難想到為什麼最後一個數必須和第一個數相隔一位（因為如果排除掉第一個數 start，再生成一個新數必然是 start， 不然就和前面的數重複了）。

于是，整個代碼如下：

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        int[] count = new int[(int) Math.pow(2, n)];
        List<Integer> res = new ArrayList<>(count.length);
        res.add(start);
        count[start] = 1;

        for (int i = 1; i < count.length; i++) {
            start = next(start, count);
            res.add(start);
        }
        return res;
    }

    public int next(int a, int[] count) {
        int xor = 1;
        while (true) {
            a ^= xor;
            if (count[a] == 0) {
                count[a]=1;
                return a;
            }
            a ^= xor;
            xor <<= 1;
        }

    }