Leetcode_14 天算法入门_day14

Posted on | Edited on | In ,
| 2.7k | 22 mins.

最后一天的位运算了。

190. Reverse Bits

Analysis

这个题必须要用循环来做？

Code

method 1

这个题实际上是一个二进制数串逆置的问题，所以把每一位都提取出来就可以了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0;
        for(int i = 0; i < 32; i++) {
            if(n & 0x80000000) ret += pow(2, i);
            n <<= 1;
        }
        return ret;
    }
};

因为最后得到的结果是个整数，所以直接算就行了。不过实际上，是没有必要用 pow 函数的。而且，也没有必要一定非得执行 32 次。所以，优化一下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0;
        for(int i = 0; i < 32 && n > 0; i++) {
            ret |= (n & 1) << (31 - i); 
            n >>= 1;
        }
        return ret;
    }
};

method 2

看了题解才知道，这个题还可以用分治的思路来做。
分治思路的核心在于不断交换奇偶数位，先依次交换相邻的 2 个数位，然后每 4 个进行交换，依次执行，最后 16 个数位进行交换，就得到了结果，这个过程有点类似归并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    const uint32_t M1 = 0x55555555;
    const uint32_t M2 = 0x33333333;
    const uint32_t M3 = 0x0f0f0f0f;
    const uint32_t M4 = 0x00ff00ff;
public:

    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M3 | (n & M3) << 4;
        n = n >> 8 & M4 | (n & M4) << 8;
        return n >> 16 | n << 16;
    }
};

190. Reverse Bits

Analysis

这个题首先想到的是借助 hash 来完成。

Code

method 1

虽然题目限定了线性时间复杂度与常数空间，但是先做了再说吧。用 hash 就会额外消耗 $O(n)$ 的空间，当然，这个题其实也可以用排序来做，这个就不写了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* method 1 */
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> ht;
        for(int i = 0; i < nums.size(); i++) {
            ht[nums[i]]++;
        }
        int ret = 0;
        for(auto it: ht) {
            if(it.second == 1) {
                ret = it.first;
                break;
            }
        }
        return ret;
    }
};

既然出现位运算这里，肯定还有更优的解法。

method 2

实际上这里要用到亦或（^）运算的性质，也即：

  • $a \oplus a = 0$
  • $a \oplus 0 = a$
  • $a \oplus b \oplus a = a \oplus a \oplus b = 0 \oplus b = b$

这样就可以直接遍历数组，全部元素异或运算，最后的结果就是那个只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
/* method 2 */
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(auto i: nums) {
            ret ^= i;
        }
        return ret;
    }
};

Summary

这两天碰到的位运算相关的题目都是比较简单的题目，只要掌握好运算的性质和一些特殊的使用技巧就行了。如果在不知道这些技巧和性质的情况下来做这些题，可能很难想到从位运算的角度去解决，多半会用其他方法来解决，所以还是要熟悉一点。

尽管这 14 天的题目都是一些简单的题目，但是也涵盖了大部分算法思想：二分、双指针、递归、分治、动态规划、回溯、DFS、BFS等等，需要做更多的相关练习来巩固...不过最好是结合一定的数据结构，这样效果应该会更好。是的，现在就赶紧开始强化一下数据结构吧 :p。

Buy me a coffee ? :)
0%