提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode刷题系列(2)

LeetCode 系列 刷题
2023-06-13 09:12:50 时间

1 颠倒二进制位

分析：c++的bitset中封装了对二进制的操作：构造函数可以直接将整型转为其二进制表示，to_string()可将其二进制转为字符串形式，to_ulong()转为整数形式。

代码：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        bitset<32> x(n);
        string s = x.to_string();
        reverse(s.begin(), s.end());
        bitset<32> y(s);
        uint32_t res = y.to_ulong();
        return res;
    }
};

2 只出现一次的数

分析：两个相同的数异或为0，任何数与0异或为本身，所以数组中所有数的异或即为只出现一次的数。

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;
        return ret;
    }
};

3 位1的个数

方法一：同样利用bitset，将其二进制表示转为字符串形式，然后统计其中1的个数。

代码：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        bitset<32> x(n);
        int res = 0;
        string s = x.to_string();
        for(int i = 0; i < 32; i++) {
            if(s[i] == '1') {
                res++;
            }
        }
        return res;
    }
};

方法二：n & (n - 1)其运算结果恰为把n的二进制位中的最低位的1变为0之后的结果，所以依次将n的最低位的1变为0，在这个过程中计数，直到n为0即可。

代码：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

4 2的幂

分析：n如果是2的幂，则n是正整数并且n的二进制表示中只有1个1。第一个方法采用了前面提到的n & (n - 1)，该式可以将n最低位的1变成0，如果最低位变成0后n为0，则n满足要求。第二个方法采用了n & -n，该式可以直接获取到最低位的1，实际上就是n的最高位，如果n & -n后n不变，则n满足要求。

代码：

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

5 组合

分析：典型的dfs例题，背模板。

代码：

class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;
    void dfs(int cur, int n, int k) {
        if(temp.size() + (n - cur + 1) < k) {
            return;
        }
        if(temp.size() == k) {
            ans.push_back(temp);
            return;
        }
        temp.push_back(cur);
        dfs(cur + 1, n, k);
        temp.pop_back();
        dfs(cur + 1, n, k);
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }
};

相关文章