leetcode 第 371 场算法比赛

零、背景

这次比赛最后一题是区间字典树，需要进行删除操作，我没模板，调试很久，比赛结束才通过。
赛后一想，直接数位二分就可以了，做复杂了。

比赛代码: https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、找出强数对的最大异或值 I

题意：给一个数组，求选择两个数字，满足|x - y| <= min(x, y),求满足要求数字的最大异或值。

思路：数据范围不大，暴力枚举即可。
复杂度：O(n^2)

二、异常员工

题意：给一个员工打卡列表，同一个员工一个小时内存在打开3次打卡算异常员工，求出异常员工列表。

思路：如果某个员工连续三次打卡在一个小时内，则该员工算异常员工。

先对数据按员工分组与排序，然后枚举每个打开时间，判断最近三个是否在一个小时内即可。

小技巧：时间转化为分钟级别数字，判断第三个与第一个的差值是否在 60 以内。

三、最大化数组末位元素的最少操作次数

题意：给两个数组，相同位置可以交换，问是否在若干次交换后，使得数组的最后一位是当前数组的最大值，求最小交换次数。

思路：最后一位分为交换与不交换最大值不一样，所以两种情况分别计算。

令第一个数组最后一位数字是 M1，第二个数组最后一位数字是 M2。

情况1: 若干次交换，使得第一个数组都小于等于 M1，第二个数组都小于等于 M2。
情况2: 若干次交换，使得第一个数组都小于等于 M2，第二个数组都小于等于 M1。

实现函数 Solver(P1, P2) 来标示第一个数组都小于等于 P1 且 第二个数组都小于等于 P2 的答案。
则答案是 min(Solver(M1, M2), Solver(M2, M1))

如何求 Solver(P1, P2) 呢？
这个是经典的动态规划。

定义状态: f(i) 代表前 i 位满足要求的最小交换次数，不存在使用特殊的最大值标记。
方程：f(i) = min(Check(i) && f(i-1), SwapCheck(i) && 1+ f(i-1), inf)

解释：
当前位满足最大值关系Check(i)，则答案是与上一个一致。
当前交换后满足最大值关系SwapCheck(i)，则答案是上一个答案加1。
交换与不交换都不满足，答案为无穷大，代表无答案。

复杂度：O(n)

四、找出强数对的最大异或值 II

题意：给一个数组，求选择两个数字，满足|x - y| <= min(x, y),求满足要求数字的最大异或值。

思路：与第一题一样，数据范围很大。

不妨设x>=y，则 |x - y| <= min(x, y) 展开后，如下

   x >= y && |x - y| <= min(x, y)
=> x >= y && x-y <= y
=> x >= y && x <= 2y
=> y <= x <= 2y

y <= x <= 2y 意味着 x 在 [y,2y]区间内时才满足情况。

如何找到[y,2y]内与 x 异或的最大值呢？

这个是典型的字典树问题。
唯一的区别是，这里的字典树存在删除节点操作，字典树上需要特殊标记才行。

另外，之前我曾提到过，有序数组其实就是字典树。
比如最高位，可以将数组分为两半，前面一半最高位都是 0，后面一半最高位都是 1。
每一半递归之后，依旧是这样的性质。

所以，这道题也可以不使用字典树，直接在数组上二分查找答案。
维护一个当前备选答案的区间，根据当前处理的位数，选择下一个最优答案区间。
选择的时候，优先选择位数相反的区间，这样异或后值会更大。

// [l, r)
for (int i = maxBit; i >= 0; i--) {
    // 区间内，查找第 i 位首次出现 1 的位置
    const int mid = BinarySearch(nums, l, r, i);
    const int bit = (y >> i) & 1;

    if (bit == 0) {
    if (mid < r) {  // 存在位1区间
        l = mid;
    } else {  // 不存在位1区间
        continue;
    }
    } else {
    if (l < mid) {  //存在位0区间
        r = mid;
    } else {  //存在位0区间
        continue;
    }
    }
}
return nums[l] ^ y;

五、最后

这个比赛算是只有 三道题。
第二题分组枚举。
第三题动态规划。
第四题区间字典树或者数位二分查找。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code