leetcode 第 258 场算法比赛

零、背景

昨天竟然是 leetcode 秋季变成大赛的个人赛，而我忘记了。

算了，这次周赛保持正常心态，好好打，没想到进入前百名了。

一、反转单词前缀

题意：给一个字符串和字符，找到字符串中字符第一次出现的位置。
然后将这个位置之前的字符串反转。

思路：按照题意，循环找到位置，前缀循环反转即可。

二、 可互换矩形的组数

题意：给一个数组，储存的是正整数二维下标。
求斜率相同的二元组个数。

思路：假设斜率相同的元素有 n 个，则二元组有 C(n, 2) 个。
所以需要先对斜率分组，然后依次求个数即可。

具体方法：直接按斜率排序，相同的斜率就是连续的。

注意事项1：考虑到精度，需要把除法转化为乘法。
注意实现2：而输入的范围是 10^5，相乘的时候需要转化为 int64，否则会越界。

三、两个回文子序列长度的最大乘积

题意：给一个字符串，找两个没有交集的回文子序列，使得两个子序列的长度乘积最大。

思路：一开始以为是状态压缩的动态规划。
但是推导状态方程时，发现状态太多储存不下。

然后先做第四题去了。
做完第四题一看榜单，第三题过了三百多个人，那显然不是状态压缩，毕竟会状态压缩的人没那么多。

既然可以过那么多人，显然可以暴力枚举了。
于是可以写两层循环，暴力枚举所有子序列，判断是否有交集，是否是回文串，都满足情况了，取最大值即可。

int n = s.length();
int N = 1<<n;
int ans = 0;
for(int i=1;i<N;i++){
    if(!CheckHuiwen(i, s)) continue;
    for(int j=1;j<N;j++){
        if(i & j) continue;
        if(!CheckHuiwen(j, s)) continue;
        int tmpans = int(__builtin_popcount(i)) * __builtin_popcount(j);
        if(tmpans > ans){
            ans = tmpans;
        }
    }
}
return ans;

四、每棵子树内缺失的最小基因值

题意：给一个有根树，每个节点有一个唯一的权重值。
问每个节点为根的子树里，最小的未出现的权重值是多少。

思路：一开始想使用树套树或者 LCA 来做，但是一计算复杂度，每个节点需要维护一个权重集合，内存和复杂度爆炸了。

然后就想着怎么去优化。

很快发现，对于子树节点没 1 的子树根，答案肯定都是 1.
所以权重为 1 的节点到根节点的值不确定外，其他节点的答案肯定都是 1。

这样本来是一道树的题，转化为了一个链的问题。

对于链，从下到上只需要维护一个权重集合即可，复杂度O(n)。

int x = -1;
for(int i=0;i<n;i++) {
    if(nums[i] == 1) {
        x = i;
        break;
    }
}

while(x != -1) {
    Dfs(x);
    while(flag[minVal]) {
        minVal++;
    }
    ans[x] = minVal;
    x = parents[x];
}
return ans;

五、最后

这次比赛最后一题很奇妙，想到转化为链了，就是大水题，一个 DFS 就搞定了。
想不到转化为链，那就是超级复杂的数据结构题了。

同样，第三题暴力枚举的话，就是大水题，两层循环搞定，否则也是很复杂的动态规划题。

这两道题你都是怎么做的呢？

加油，算法人。

《完》

-EOF-

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