leetcode 第 265 场算法比赛

零、背景

这次比赛的题其实不难，没想到过的人才 45 个，真没想到。

最后一题我写到一半，不知从哪飞进来一只蜜蜂，我在屋里赶了一会蜜蜂，导致思路被打断。
再加上看错题了，代码最后重写，比赛过之后才通过最后一题。

看来我最大的问题是看错题，以后细心了。

一、值相等的最小索引

题意：问是否存在某个元素值模 10，值等于下标。
存在了输出第一个下标，不存在返回 -1。

思路：循环模 10 判断即可。

二、找出临界点之间的最小和最大距离

题意：给一个链表，问间距最大和最小的临界点间距。
临界点定义：值大于相邻两个点或小于相邻两个点。

思路：循环链表，求出所有临界点。
间距最大的临界点是第一个与最后一个的距离。
间距最小的临界点是所有相邻临界点距离里面的最小值。

三、转化数字的最小运算数

题意：给一个起始值、目标值、数组。

当前值数据范围在 [0, 1000] 时，可以进行三个操作。

1、数组里选一个元素，相加
2、数组里选一个元素，相减
3、数组里选一个元素，异或

问不断的进行操作，是否可以计算出目标值。

思路：队列记忆化搜索即可，简称动态规划。
复杂度：O(1000 * 1000)

四、同源字符串检测

题意：给一个编码规则，问两个编码后的字符串是否是由同一个字符串编码得到。

编码规则：

1、字符串分割为几个子串。
2、选择某些子串，子串的长度转化为对应的数字字符串。
3、子串合并为字符串。

思路：数据范围不大，直接枚举记忆化搜索即可，也可以称为动态规划。

状态定义：dp[pos1][num1]][pos2][num2]
状态解释：第一个编码分析到 pos1 且前面数字是 num1，第二个编码分析到 pos2 且前面数字是 num2 时是否有答案。
空间复杂度：40 * 1000 * 40 * 1000

由于状态是四维的，逻辑分析起来比较复杂，我画了一个思维导图。

当然，默认状态可能内存会爆，所以需要优化状态。

空间优化：num1 与 num2 不可能同时存在，所以使用标记位即可。
优化状态：dp[pos1][pos2][flag][num]
状态解释：flag 为 0 时 num 代表 pos1 前面的数字，flag 为 1 时 num 代表 pos2 前面的数字。

递归逻辑我们不需要改变，只需要做一下状态转化即可。

int Dfs(int p1, int ext1, int p2, int ext2){
    if(ext1 > 0 && ext2 > 0) { // 不使用状态储存
        int minExt = min(ext1, ext2);
        return Dfs(p1, ext1 - minExt, p2, ext2 - minExt);
    }
    
    int flag = 0;
    int ext = ext1;
    if(ext2 > 0) {
        flag = 1;
        ext = ext2;
    }
    
    int& ret = dp[p1][p2][flag][ext];
    // 判断逻辑只对 ret 进行赋值即可
    if(ret != -1) {
        return ret;
    }
    ...
}

五、最后

这次比赛题目还好吧，可惜我看错题了，把三位数字看成两位数字了。

比赛的全过程我都录屏下来了。
下午会处理视频并上传到 B 站。
感兴趣的可以去 B 站围观。

加油，算法人。

《完》

-EOF-

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