Leetcode 周赛 311
Nowherechan 学徒
  2023-02-10 10:55:22 2023-02-10 10:55   2023-03-19 11:03:07    1.5k Words  6 Mins  

近来显然有点急功近利了。想要快速把 Leetcode 刷到两千分。但是原先平均 3.5 道题，近两次周赛却分别只做对了一道和两道题。

做题时的代码的凌乱、思路的混乱，以及赛后惨不忍睹的结果，将近来浮躁的心态展现得淋漓尽致。

2560. House Robber IV

题目链接

首先贴出比赛时候 AC 了但是实际上并没有，赛后用新增样例 rejudge 出错误的代码。（说实话，我没想过周赛样例会这么不严谨的，客观上还是有一点影响了我的判断）

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
class Solution {
public:

    bool judge(vector<int>& a, int idx, int k) {
        int m = a[idx];
        // judge left
        int i = idx-2, tk = 1;
        while (i >= 0) {
            if (a[i] > m) {
                i--;
            } else {
                tk++;
                i -= 2;
            }
        }
        
        // judge right
        i = idx+2;
        while (i < a.size()) {
            if (a[i] > m) {
                i++;
            } else {
                tk++;
                i += 2;
            }
        }

        return tk >= k;
    }

    int minCapability(vector<int>& nums, int k) {
        map<int, vector<int>> m;
        for (int i = 0; i < nums.size(); i++) {
            int &x = nums[i];
            if (m.find(x) != m.end()) {
                m[x].emplace_back(i);
            } else {
                m[x] = {i};
            }
        }

        vector<int> search_arr;
        for (auto &x: m) {
            search_arr.emplace_back(x.first);
        }

        sort(search_arr.begin(), search_arr.end());
        
        // bin search
        int l = 0, r = search_arr.size()-1;
        while (l < r) {
            int mid = (l + r) / 2;
            bool valid = 0;
            for (auto &idx: m[search_arr[mid]]) {
                if (judge(nums, idx, k)) {
                    valid = 1;
                    break;
                }
            }

            if (valid) {
                r = mid;
            } else {
                l = mid+1;
            }
        }

        return search_arr[l];
    }
};

其实思路还是清晰的，读题首先肯定都会想到二分判断，然后问题就变成了“怎么二分”和“怎么判断”这两个子问题。但是显然，这段代码中这两个问题都处理得不好。

首先是整个思路，比赛的时候我盲目觉得“如果 a > b，那么如果 a 不是答案，那么 b 不是答案”，因为 b 选择数据的范围比 a 更小嘛。

但是实际上一个简单的样例 [1, 2, 1, 3, 3], 2 就把这个假结论否定了。所以可以看出我二分的方法和 judge 函数完全是错误的。不过这个问题可以通过修改 judge 函数解决，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool judge(vector<int>& a, int idx, int k) { 
    // 为方便主函数调用，不修改主函数结构，这里参数还用 idx
    int num = a[idx], i = 0, times = 0;
    while (i < a.size()) {
        if (a[i] <= num) {
            i += 2;
            times++;
        } else {
            i++;
        }
    }
    return times >= k;
}

其实改完这段就可以 AC 了。但是主函数还用诸多繁杂的地方，离优雅二字有如天堑。原先代码中，我将相同的数字整合到一起，并排序，然后用哈希表记录同一个数字的不同索引位置，实际上是担心不同位置的同样的数字有不一样的结果。但是实际上这是由不正确的 judge 的思路造成的。

在修改了 judge 函数之后，这些操作就没有太多意义了。首先是相同数字不必考虑其位置，因为 judge 函数是从数组开头开始判断的。其次罗列各个出现的数值也意义不大，因为 judge 函数并不要求该数值真的在数组中出现过（当然要把参数从 index 换成具体数值），而且最终二分停止的时候，得到的结果一定在数组中出现（因为二分判断有效总是依赖于原数组）。

因此只需要找到最大值即可开始二分。修改如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool judge(vector<int>& a, int num, int k); // 这里改了参数，具体内容略

int minCapability(vector<int>& nums, int k) {
    int l = 0, r = *max_element(nums.begin(), nums.end());
    // binary search
    while (l < r - 1) {
        int mid = (l + (long long)r) / 2; // 考虑 l, r 范围，避免溢出
        if (judge(nums, mid, k)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}

2561. Rearranging Fruits

题目链接

读完题，其实思路也很明显，就是利用好最小的元素，如果要交换的两个数 a, b 都大于最小元素 x 的两倍，那么比起这两个数交换，不如用第一堆的 x 交换第二堆的 b，再用第二堆的 x 交换第一堆的 a，代价 2x。麻烦的地方就在于怎么去用代码模拟这个过程。

原先 WA 的代码，思路极其混乱，无参考价值。

实际上勤快一点，老老实实用哈希表找出“差异”，然后将差异分为：小于 2x 并且 12，小于 2x 并且 21，不小于 2x 并且 12，不小于 2x 并且 21 总共四类，然后从小到大依次去匹配并消除，如果小于 2x 的还没消完但是大于 2x 的已经没有了，那么就得先用小的消掉大的。就是写代码需要细心亿点。

然后看这个思路，会发现实际上没有必要分别讨论“哪些大于 2x，哪些小于 2x”，只需要考虑移动的方向分成两类，两边分别排序，从左侧的小值和右侧的大值开始一一抵消。

甚至两类都不需要分，直接混作一团，从小到大排序后直接算前一半的数据。

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
class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        
        unordered_map<int, int> total, b1, b2;
        
        for (int x: basket1) {
            b1[x]++;
            total[x]++;
        }
        
        for (int x: basket2) {
            b2[x]++;
            total[x]++;
        }
        
        long long min_cost = 2 * min( *min_element(basket1.begin(), basket1.end()), 
                                      *min_element(basket2.begin(), basket2.end()) );
        
        typedef pair<int, int> p;
        vector<int> tobemoved;
        
        for (auto kv: total) {
            
            //special
            if (kv.second % 2) {
                return -1;
            }
            
            int key = kv.first;
            int num = abs((total[key])/2 - b1[key]);
            for (int i = 0; i < num; i++) {
                tobemoved.emplace_back(key);
            }
        }
        
        sort(tobemoved.begin(), tobemoved.end(), [] (int a, int b) {
            return a < b; 
        });
        
        long long ret = 0;
        
        for (int i = 0; i < tobemoved.size()/2; i++) {
            int key = tobemoved[i];
            if (key < min_cost) {
                ret += key;
            } else {
                ret += min_cost;
            }
        }
        
        return ret;
    }
};

总结

想来其实都是些不太难的题，最终写得很复杂的原因，大约在于心态浮躁，不能做到冷静思考。

可能需要多做做复杂的数据结构题，用来磨一磨自己的性子。

Leetcode 周赛 311
2023/02/10/Algorithm/lc-weekly-331/
Author
Nowherechan
Published
2023-02-10 10:55
License
 Comments
  1. 2560. House Robber IV
  2. 2561. Rearranging Fruits
  3. 总结