ARST打卡第235周[235/521]

发表于 分类于 阅读次数：
lc421_数组中两个数的最大异或值 【TED演讲】如何超越你的对手 单元测试成神之路——C++篇 引导GPT帮忙处理繁杂无脑的部分

Algorithm

lc421_数组中两个数的最大异或值

思路:

  • 不能直接 O(n^2), 否则会超时
  • 按照数位1值进行处理
  • 就是数位1最高位和次高非位的两个数异或(实现比较难)

以前做过，但没想到这次又忘了…看看题解吧…

看题解发现确实是这个思路，学习题解实现吧 (自己增加了一些关于其中异或技巧的谜底解释)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
private:
    // 最高位的二进制位编号为 30
    static constexpr int HIGH_BIT = 30;

public:
    int findMaximumXOR(vector<int>& nums) {
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            unordered_set<int> seen;
            // 将所有的 pre^k(a_j) 放入哈希表中
            for (int num: nums) {
                // 如果只想保留从最高位开始到第 k 个二进制位为止的部分
                // 只需将其右移 k 位
                seen.insert(num >> k);
            }

            // 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
            // 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
            int x_next = x * 2 + 1;
            bool found = false;
            
            // 枚举 i
            for (int num: nums) {
                // 这里利用了异或的玄机，x ^ y = z. z ^ x = y.
                // 所以使用结果异或一个值，判断另一个值是否在内部。
                // 这样最终还是两个值
                if (seen.count(x_next ^ (num >> k))) {
                    found = true;
                    break;
                }
            }

            if (found) {
                x = x_next;
            }
            else {
                // 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
                // 即为 x = x*2
                x = x_next - 1;
            }
        }
        return x;
    }
};

struct Trie {
    // 左子树指向表示 0 的子节点
    Trie* left = nullptr;
    // 右子树指向表示 1 的子节点
    Trie* right = nullptr;

    Trie() {}
};

class Solution_tree {
private:
    // 字典树的根节点
    Trie* root = new Trie();
    // 最高位的二进制位编号为 30
    static constexpr int HIGH_BIT = 30;

public:
    void add(int num) {
        Trie* cur = root;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                if (!cur->left) {
                    cur->left = new Trie();
                }
                cur = cur->left;
            }
            else {
                if (!cur->right) {
                    cur->right = new Trie();
                }
                cur = cur->right;
            }
        }
    }

    // 这里相当于 x ^ y = z. 用 x ^ 最大y 去找 z
    int check(int num) {
        Trie* cur = root;
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
                if (cur->right) {
                    cur = cur->right;
                    x = x * 2 + 1;
                }
                else {
                    cur = cur->left;
                    x = x * 2;
                }
            }
            else {
                // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
                if (cur->left) {
                    cur = cur->left;
                    x = x * 2 + 1;
                }
                else {
                    cur = cur->right;
                    x = x * 2;
                }
            }
        }
        return x;
    }

    int findMaximumXOR(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for (int i = 1; i < n; ++i) {
            // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
            add(nums[i - 1]);
            // 将 nums[i] 看作 ai，找出最大的 x 更新答案
            x = max(x, check(nums[i]));
        }
        return x;
    }
};

// 链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

int main() {
    vector<int> a = {1,2,4};
    Solution sol;
    cout << sol.findMaximumXOR(a) << endl;
    return 0;
}

/* 
clang++ A.cpp -o A.out -std=c++20
./A.out           
6
 */

Review

【TED演讲】如何看清排名后的真实水平

很多时候，我们天然的结果偏见，会把运气带来的结果看成实力。

因此就会产生很多误解，导致错估一个公司的价值，被其股价蒙蔽。

因此，我们需要通过gamble思维，对核心的指标(比如说队伍的平均进攻数等)计算概率，计算精确的投入产出比，
最终算出真实价值，看清真实排名，看透运气和随机概率下的真实水平。

Tips

单元测试成神之路——C++篇

Share-引导GPT帮忙处理繁杂无脑的部分

Q:
下面我将会丢入错误信息给你，你通过错误信息来转化成 MOCK_METHODx 模式。先学习参考这个例子: 错误信息为: ../../third-party/rocksdb/output/include/rocksdb/db.h:365:18: note: virtual rocksdb::Status rocksdb::DB::Put(const rocksdb::WriteOptions&, rocksdb::ColumnFamilyHandle*, const rocksdb::Slice&, const rocksdb::Slice&)
virtual Status Put(const WriteOptions& options,
^ 转化为: MOCK_METHOD4(Put, rocksdb::Status(const rocksdb::WriteOptions&, rocksdb::ColumnFamilyHandle*, const rocksdb::Slice&, const rocksdb::Slice&)); 。 其中 MOCK_METHODx的x为参数个数，你明白了吗，我可能会输入多个错误信息，你输出多个转化，可以吗

A:
明白了，你希望将错误信息转化为相应的 MOCK_METHODx 形式。以下是你提供的示例和转化：

错误信息：

1
2
../../third-party/rocksdb/output/include/rocksdb/db.h:365:18: note: virtual rocksdb::Status rocksdb::DB::Put(const rocksdb::WriteOptions&, rocksdb::ColumnFamilyHandle*, const rocksdb::Slice&, const rocksdb::Slice&)
virtual Status Put(const WriteOptions& options,

转化为 MOCK_METHOD4 形式：

1
MOCK_METHOD4(Put, rocksdb::Status(const rocksdb::WriteOptions&, rocksdb::ColumnFamilyHandle*, const rocksdb::Slice&, const rocksdb::Slice&));

如果你有更多的错误信息需要转化，只需提供错误信息和我将其转化为 MOCK_METHODx 形式。我将会在每个错误信息后面添加相应的转化。

Q:
先试3个: ../../third-party/rocksdb/output/include/rocksdb/db.h:365:18: note: virtual rocksdb::Status rocksdb::DB::Put(const rocksdb::WriteOptions&, rocksdb::ColumnFamilyHandle*, const rocksdb::Slice&, const rocksdb::Slice&)
virtual Status Put(const WriteOptions& options,
^
../../third-party/rocksdb/output/include/rocksdb/db.h:377:18: note: virtual rocksdb::Status rocksdb::DB::Delete(const rocksdb::WriteOptions&, rocksdb::ColumnFamilyHandle*, const rocksdb::Slice&)
virtual Status Delete(const WriteOptions& options,
^
../../third-party/rocksdb/output/include/rocksdb/db.h:400:18: note: virtual rocksdb::Status rocksdb::DB::SingleDelete(const rocksdb::WriteOptions&, rocksdb::ColumnFamilyHandle*, const rocksdb::Slice&)
virtual Status SingleDelete(const WriteOptions& options,
^

A:
…

后面一步步鼓励，最终一次性完成了所有的转化，虽然这种大批量转化的时候出了7个小错误，但整体还是大大解决了时间，爽。
以下是鼓励的提问:

Q:
做得很好，下面我再传入几个，你直接一起给出转化的结果，不要再复述错误信息了.
…
Q:
做得很好，下面我会继续给错误信息，希望你给出结果时合并到一个文本框内，方便我一次性复制:
…
Q:
做的很好，继续:
…