leetcode 第 259 场算法比赛

零、背景

这次比赛的题目其实都很水，但是最后一题我没做出来。

以后还是需要加强复杂度的计算，以为会超时的，由于存在减值或优化，其实不会超时。

一、执行操作后的变量值

题意：给一个自制的编程语言，有一个变量和四个操作，问操作若干次后，变量的值。

思路：操作只有加法与减法，按照操作进行加减即可。

小技巧：加法与减法中间的字符不一样，只需要判断中间的字符即可。

二、数组美丽值求和

题意：给一个数组，每个位置可以根据数组的特征以及三个规则计算出一个美丽值。

规则1：如果某个位置的值大于前面的所有值，小于后面的所有值，则美丽值是 2 。
规则2：如果某个位置的值大于前面一个位置的值，小于后面一个位置的值，则美丽值是 1。
规则3：其他情况，美丽值是 0。

思路：扫描两边，预处理出每个位置前面的最大值与后面的最小值。

然后再次循环就可以计算出每个位置的魅力值了。

三、检测正方形

题意：这是一个坐标点集数据流题。

数据流有两个操作，一个是增加一个坐标点，一个是询问与坐标轴对齐的正方形的个数。
当然，询问的时候已经输入了一个坐标，我们只需要在点集里面找到三个坐标，来组成正方形即可。

思路：已经输入了一个点，只需要枚举一个点集，另外两个点的位置就几乎可以确定了。
通过 map 储存下所有点的位置，就可以快速判断另外两个点是否存在。

注意实现：由于存在重复点，找到三个点的数量后，需要相乘才能得到所有的正方形个数。

小优化：可以对点进行 hash 处理，然后使用 unordered_map 储存，就可以做到 O(n) 的查询。

四、重复 K 次的最长子序列

题意：给一个字符串，问是否存在一个子序列，重复 K 次后依旧是子序列。
如果存在求最长的答案，长度相等时，求字典序最大的那个。

数据范围：k 不大于 2000， n 不大于 8 * k。

思路：根据数据范围，可以发现答案长度最长是 8。

所以很容易想到可以枚举所有长度小于 8 的子序列，然后判断是否是答案。

但是以计算复杂度，枚举的子序列有 26^8 个，判断是否是答案又需要 O(n)，复杂度直接爆炸了。

赛后一看通过的人，果然是枚举子序列通过的。

不过枚举的时候做了一个小优化：如果一个子序列不是答案，那就没必要继续枚举这个子序列为前缀的序列了。

void Dfs(){
    if(pre.length() == maxLen) {
        return ; // 出口
    }
    
    // 剪枝，如果 pre 目前一个
    
    for(int i = 0; i < 26; i++) {
        pre.push_back('a' + i);
        if(Check()) {
            Dfs();
        }
        pre.pop_back();
    }
}

我们知道 26^8 会爆炸，但是输入的字符串长度只有 8k。
所以满足条件的子序列会快速收敛，这样时间就不会爆炸了。

当然，判断是否是答案的时候，也可以做一个预处理优化。

通过预处理每个位置每个字母下次出现的位置，就可以快读找到下个预期的位置，复杂度由O(n)减小到O(l * k)。

void Init() {
    for(int j=0;j<26;j++) dp[j][n] = -1;
    
    for(int i = n - 1; i >= 0; i--) {
        for(int j = 0; j < 26; j++) {
            dp[j][i] = dp[j][i + 1];
        }
        dp[s[i] - 'a'][i] = i;
    }
}

这时候， check 的函数有两个功能。
一个是判断是否是答案，一个是判断是否是最优答案。

bool Check(){ // 是一个答案就需要返回 true
    int j = 0, i = 0;
    int num = 0;
    
    while(pre.length() * (K - num) - j + i <= n) {
        i = dp[pre[j] - 'a'][i];
        if(i == -1) return false;
        
        j++, i++;
        if(j == pre.length()){
            num++;
            if(num == K) {
                break;
            }
            j = 0;
        }
    }
    
    if(num == K) {
        if(pre.length() < ans.length()) return true; // 长度不是最优答案
        if(pre.length() == ans.length() && pre < ans) return true; // 字典序不是最优答案
        ans = pre;
        return true;
    }
    return false;
}

可以看到，check 函数还通过剩余字符串的长度是否大于答案的长度，来快速剪枝。

五、最后

最近几次比赛都在考察复杂度优化了。
一个看起来会超时的算法，由于一个小的剪枝或者优化，就不再超时了。

不过这类题目不适合做面试题。
因为这些优化不可复制，想到了就过了，想不到就超时，不具备推导性。
一个合格的面试题，肯定是有多种方法，可以暴力做，然后慢慢引导出其他方法。

加油，算法人。

《完》

-EOF-

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