leetcode 第 257 场算法比赛

零、背景

一、统计特殊四元组

题意：给一个数组，问是否存在四元组，使得前三个数字之和是第四个数字。

思路：数据范围不大，最暴力的是四层循环。

一种优化：求前三个数组的和，判断第四个数字是否存在。

二、游戏中弱角色的数量

题意：给一个数组，每个元素有两个属性：攻击和防御。
如果一个元素的攻击和防御都小于另一个，则成为弱元素。
问若元素的个数。

思路：典型的拓扑排序问题。

先按一个属性降序排序，再按另一个属性升序排序，保存另一个属性的最大值即可。

原理：按照第一个属性进行分组，降序排序。
由于第二个属性是升序排序，如果最大值大于当前属性，说明这个最大值是上一个分组的。
上一个分组的第一个属性保证大于当前分组，第二个属性有大于当前属性，说明找到一个答案。

int numberOfWeakCharacters(vector<vector<int>>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end(), [](auto&a, auto&b){
        if(a[0] == b[0]) {
            return a[1] < b[1];
        }else {
            return a[0] > b[0];
        }
    });

    int max_val = -1;
    int ans = 0;
    for(auto& v: nums) {
        if(max_val > v[1]) {
            ans++;
        }
        max_val = max(max_val, v[1]);
    }

    return ans;

}

三、访问完所有房间的第一天

题意：给 n 个房间，每天按照规则访问一个房间。

规则1：如果此房间是奇数次访问，那么第二天必须访问房间nextVisit[i]。
规则2：如果此房间是偶数次访问，那么第二天必须访问房间(i + 1) mod n。

问第几天可以首次访问所有房间

思路：规则其实是有规律的。

第一个规则只会往回跳，第二个规则只会往后跳一步。

有了这两个规则，就可以很容易写出动态转移方程。

状态定义：dp[i][2]
dp[i][1] 代表第 i 个房间第一次奇数次访问需要的天数。
dp[i][0] 代表第 i 个房间第一次偶数次访问需要的天数。

状态转移方程:

dp[i][1] = dp[i-1][0] + 1
dp[i][0] = dp[i][1] + 1 + Dis({i, 1}, {next(i), ?})
Dis({a, 1}, {b, ?}) = dp[a][1] - dp[b][?]

写状态转移方程的时候，发现有个疑问：回跳的时候，不知道那个位置是偶数次访问还是奇数次访问。

数据样例观察一下，发现除了自身位置，其他位置肯定是奇数次访问。
这个结论使用反证法很容易证明，这里就不证明了。

确定了奇数位置，状态转移方程也就确定了，一层循环就可以做出这道题了。

ll dp[max5][2];
int firstDayBeenInAllRooms(vector<int>& nextVisit) {
    int n = nextVisit.size();
    memset(dp,0, sizeof(dp));

    dp[0][1] = 0; // 奇数天 dp[i][1] = dp[i-1][0] + 1
    dp[0][0] = 1; // 偶数天 dp[i][0] = dp[i][1] + 1 + Dis(next[i], i)
    for(int i = 1; i < n; i++){
        int v = nextVisit[i];
        dp[i][1] = (dp[i-1][0] + 1) % mod;
        dp[i][0] = (dp[i][1] + dp[i][1] - dp[v][1] + 1 + mod) % mod;
    }
    return dp[n-1][1];
}

思路题：规则1跳的位置如果是任意位置，即可以大于当前位置，这道题改如何做呢？

四、数组的最大公因数排序

题意：给一个数组，如果两个数字的最大公约数大于1，则可以交互两个数字。
问最后是否可以使整个数组有序？

思路：最大公约数大于1，代表非互质。
如果两个数字非互质，代表两个数字之间有边。
可以大胆猜测：连通图之间可以做到任意顺序。

于是这道题就需要先根据连通性进行分组，每组单独排序，然后判断最终是否有序。

求连通性可以先求不大于 sqrt(n)的素数表，共log(n)/2个。
然后通过并查集，把连通的节点标记起来。
最后对每组数字进行排序。

五、最后

思考题：第三题的规则变化一下，规则1跳的位置改成任意位置后，该如何做呢？

加油，算法人。

《完》

-EOF-

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