leetcode 第184算法比赛

零、背景

这次周末有事情没有参加 leetcode 的第 184 场比赛。

后来做了一下发现这次的题比较简单，其中有几道题可以使用一些高级算法来做。

下面题解以及高级算法分享给大家。

一、数组中的字符串匹配

题意：给一个字符串数组，找出所有的数组子串。
定义：如果一个字符串是数组中某个字符串的子串，则这个字符串称为数组子串。

思路：数组大小 100， 字符串长度 30，直接暴力做即可。

二、查询带键的排列

题意：给一个大小为 m 的数组 P，值分别为 1~m。
然后给一个 queries 数组，依次在数组 P 中查找值为 queries[i]的位置，并将这个值移动到第一个位置。
输出每次查询的位置下标（从0开始）。

思路：最简单的是暴力查找与移动，复杂度 O(n^2)。

面对这道题，可以发现，使用 map 维护好每个值的位置，就可以 O(1) 查找了。

唯一的问题是在最前面插入一个值后，前缀区间的位置都会后移一位。

那能不能先把所有元素后移呢？
这样依次在最前面的空位置插入数据时，其他元素的位置都不会变化。

不过这个时候，位置不能代表下标了。
我们需要一个算法快速确定当前位置的下标。

回头看下，下标的含义是什么？
下标代表前面有多少个元素。

所以我们如果能够使用一个算法快速确定某个值前面有多少个值，就可以计算出对应的下标了。

如果维护一个区间，有值代表1，没值代表0，我们求出区间和就可以全速计算区间有多少个值了。

这个问题其实是经典的线段树问题，即单点修改与区间查询。

考虑到问题比较简单，我们可以直接使用树状数组来做。

PS：至于什么是线段树和树状数组，这里不做介绍了。

三、HTML 实体解析器

题意：给一个 encode 后的 HTML 文本，求 decode 后的文本。

思路：按题意模拟即可。

四、给 N x 3 网格图涂色的方案数

题意：给一个 N*3 的网格，可以涂三种颜色。
要求上下左右相邻不能有相同的颜色。
问总共有多少中涂法。

思路：最简单的动态规划题。

表面上看 3 中颜色组合会有很多中情况，但是我们考虑等价等，实际上只有两种排列组合。

第一种是 abc 的形式，第二种是 aba 的形式。

假设当前层是 abc ， 下一个层可以推导出 2 种 abc 和 2 种 aba。
假设当前层是 aba ，下一个层可以推导出 2 种 abc 和 3 种 aba。

第一层有 6 个 abc 和 6 个 aba。
所以我们就可以递归求出答案了。

当然，由于状态转移方程太简单了，我直接递推循环来敲代码了。

另外，这种题型之前我已经分享无数遍了。

这种典型的状态转移，我们可以递归，也可以递推，还可以使用高大上的状态机幂乘。

这里就不多介绍了，感兴趣的可以看下面三篇文章。

1、《Leetcode 第 158 场比赛回顾》中的第三题。
2、《有限制的掷骰子（递推版）》
3、《有限制的随机数（矩阵状态机）》

五、最后

这次比赛的第二题和第四题可以当做面试题来考察大家。

第二题优化的方向是树状数组或者线段树，当然自己实现计数平衡树也可以。
而第四题则是经典的动态规划，应该难度不大吧。

《完》

-EOF-

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