六月集训（10）位运算

文章目录

• 1.LeetCode:868. 二进制间距
• 2.LeetCode:1734. 解码异或后的排列
• 3.LeetCode:89. 格雷编码
• 4:LeetCode:1238. 循环码排列

1.LeetCode:868. 二进制间距

原题链接

        给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。

        如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，“1001” 中的两个 1 的距离为 3 。

        示例 1：

        输入：n = 22

        输出：2

        示例 2：

        输入：n = 8

        输出：0

        示例 3：

        输入：n = 5

        输出：2

        提示：

        1 <= n <= 1e9

        这道题最简单的做法就是枚举n的每一位，并不断更新距离。

class Solution {
public:
    int binaryGap(int n) {
        int prev=-1;
        int ans=0;
        for(int i=0;i<=31;++i){
            if((n>>i)&1){
                if(prev==-1){
                    prev=i;
                }
                else {
                    ans=max(ans,i-prev);
                    prev=i;
                }
            }
        }
        return ans;
    }
};

2.LeetCode:1734. 解码异或后的排列

原题链接

        给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。

        它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。

        给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。

        示例 1：

        输入：encoded = [3,1]

        输出：[1,2,3]

        示例 2：

        输入：encoded = [6,5,4,6]

        输出：[2,4,1,5,3]

        提示：

        3 <= n < 1e5

        n 是奇数。

        encoded.length == n - 1

        由于perm是n个正整数的排列，且有奇数个元素，把他们按题目的要两两异或得到的encoded数组一定有n-1个数字，由perm得到encoded很简单，但是由encoded得到perm就必须要知道perm中的头元素的具体位置。这也是我们想要得到的信息，那么该怎么得到perm的头元素呢？

        其实很简单，对于encoded[0]=perm[0] ^ perm[1] , encoded[1]=perm[1] ^ perm[2],encoded[2]=perm[2] ^ perm[3],encoded[3]^perm[4]假设n=5，那么我们会发现将encoded数组的奇数下标异或到一起的结果就是perm[1] ^ perm[2] ^ perm[3] ^ perm[4],而perm是1-n的某个排列，我们可以先把1-n异或到一起，再与encoded奇数下标异或在一起的结果异或，这样就得到了perm数组的第一个元素，又因为x ^ y=z一定有 x ^z=y,这也反向 *** 作即可得到perm数组。

class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n=encoded.size();
        int permx=0;
        for(int i=0;i<=n;++i){
            permx^=i+1;
            if(i&1){
                permx^=encoded[i];
            }
        }
        vector<int> ans;
        ans.push_back(permx);
        for(int i=0;i<n;++i){
            ans.push_back(ans.back()^encoded[i]);
        }
        return ans;
    }
};
/*
    0   1   2   3
    12  23  34  45 
    123
    12345
    1  2  3  4  5
*/

3.LeetCode:89. 格雷编码

原题链接

        n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

        每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）

        第一个整数是 0

        一个整数在序列中出现 不超过一次

        每对 相邻 整数的二进制表示 恰好一位不同 ，且

        第一个 和 最后一个 整数的二进制表示 恰好一位不同

        给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

        示例 1：

        输入：n = 2

        输出：[0,1,3,2]

        示例 2：

        输入：n = 1

        输出：[0,1]

        提示：

        1 <= n <= 16

        当n=1的时候，很显然的该阶格雷编码为0，1. 现在我们要得到n=2时候的格雷编码，观察0-3的二进制分别为00,01,10,11，从n-1过渡到n，新增添的数字就是n-1阶格雷编码中每个数字加上2^n-1后的数字，也就是第n-1位的二进制位变成1。

        这样我们会发现由上一阶的某数加2^n-1后，与他的二进制位只有这新增添的一位不同 ，比如00与10，01与11。再往后的有000 100（0，4），001 101（1，5），010 110（2，6）， 011 111（3，7）

        于是很自然的想到了将新增添的数字倒序插入到第n-1阶格雷编码的尾部，比如 0 1，先插入3 再插入1， 得到n=2时的格雷编码0 1 3 2。对于0 1 3 2 先插入2+4=6 然后是3+4= 7 然后是 1+4=5 然后是0+4=4。首先这样可以做到新插入相邻的数字二进制只有一位不同，因为相邻的数字都差1或2，新加入的数组和上一阶数组的接口处与头尾部第n-1位不同，保证了接口处和头尾符合条件。这样得到的编码序列一定是合法的。

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        ans.push_back(1);
        int base=2;
        while(n>1){
            n--;
            for(int i=ans.size()-1;i>=0;--i){
                ans.push_back(ans[i]+base);
            }
            base*=2;
        }
        return ans;
    }
};

4:LeetCode:1238. 循环码排列

原题链接

        给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,…,2^n-1) 的排列 p，并且满足：

        p[0] = start

        p[i] 和 p[i+1] 的二进制表示形式只有一位不同

        p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

        示例 1：

        输入：n = 2, start = 3

        输出：[3,2,0,1]

        示例 2：

        输出：n = 3, start = 2

        输出：[2,6,7,5,4,0,1,3]

        提示：

        1 <= n <= 16

        0 <= start < 2^n

        这道题观察示例我们可以看出，答案就是n阶格雷编码序列从start的位置反转数组的结果。

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> ans;
        ans.push_back(0);
        ans.push_back(1);
        int base=2;
        while(n>1){
            n--;
            for(int i=ans.size()-1;i>=0;--i){
                ans.push_back(ans[i]+base);
            }
            base*=2;
        }
        int idx=0;
        for(int i=0;i<ans.size();++i){
            if(ans[i]==start){
                idx=i;
                break;
            }
        }
        reverse(ans.begin(),ans.begin()+idx);
        reverse(ans.begin()+idx,ans.end());
        reverse(ans.begin(),ans.end());
        return ans;
    }
};