leetcode 第 298 场算法比赛/未参赛

零、背景

这次比赛，由于我有事，所以就无法参加比赛了。

现在有时间了，做了下比赛，坑有不少。

一、兼具大小写的最好英文字母

题意：问哪个字母的大小写都出现了，求出现的字典树最大的那个字母。

方法1：边遍历边寻找。

维护一个集合，代表前面出现的字母。
边遍历，边判断大小写反转的字母是否存在集合，存在了就找到一个答案，再判断是否可以更新为最优值。
之后，再把当前字母加入到集合。

方法2：预处理集合，枚举答案。

遍历一遍字符串，将所有字符加入到集合里。
之后从后到前枚举每个字母，判断是否是答案。

二、个位数字为 K 的整数之和

题意：求最少的整数个数，要求这些整数各位都是 k，整数之和是 num。

方法1：动态规划

状态定义：f(n) 代表和为 n 的最少整数。

状态转移方程如下：

i % 10 == k;
f(n) = min(f(i) + 1)

复杂度：O(n^2)

方法2：贪心

分析9*9乘法表，只观察个位，可以发现，每个数字都有自己的循环节。

0 => 0
1 => 1,2,3,4,5,6,7,8,9,10
2 => 2,4,6,8,10
3 => 3,6,9,12,15,18,21,24,27,30
4 => 4,8,12,16,20
5 => 5,10
6 => 6,12,18,24,30
7 => 7,14,21,28,35,42,49,56,63,70
8 => 8,16,24,32,40
9 => 9,18,27,36,45,54,63,72,81,100

这意味着有两个推论。

瑞伦1：如果数字和在循环节之内，则可能有答案，否则没答案。

推论2：一个数字，是否存在答案，在循环节之内可以判断出来。

贪心思路：数字和不断的减去 k，循环节之内，剩余和个位可以等于 k，则答案是减去的次数加一。

例子：假设和为 182, k 为 4 第一次减法：182-4=178
第二次减法：178-4=174
故最小的整数集合为4,4,174。
答案为 3.

三、小于等于 K 的最长二进制子序列

题意：给一个二进制字符串，求最长的子序列，使得子序列的值不大于 K。

方法1：贪心

贪心之前需要想到两个推论。

推论1：选择 0 比选择 1 更优。
推论2：选择低位的 1 比选择高位的 1 更优。

有了这两个推论，我们就可以预处理计算出 0 的个数，然后从后到前求后缀的值 ，来看是否可以得到更优答案。
一旦无法得到更优答案，遍历就结束。

方法2：动态规划

假设：我们可以储存下字符串对应的十进制

状态定义：f(n, i) 前 n 个字符里面选 i 个字符可以得到最小十进制。

状态转移方程：

f(n, i) = min(f(n-1, i), f(n-1,j-1)*2 + v)  

解释：分为选择当前字符与不选择。
选择了就是之前的最优值左移加上当前的值。

问题：字符串长度上千位，必然会越界。

绝妙之处：状态转移方程修改为下面的样子

f(n, i) = min(f(n-1, i), f(n-1,j-1)*2 + v)  
f(n, i) = min(f(n, i), k+1)

解释：既然目标是求不大于 k 的数字，大于 K 的统一标记为 k+1 即可。

四、卖木头块

题目：给一个大矩阵，以及一些小矩阵的长、宽、价值。
大矩阵需要切割为与小矩阵匹配的大小才能得到对应的价值。
但是，切割的时候只能横着一刀切或者竖着一刀切。
小矩阵的个数都是无限的，问怎么切割才能得到最大价值。

思路：如果思考的顺序不对，这道题可能就做不出来了。

起初，我思考的是先选择小矩阵，然后决定横着切一刀或者竖着切一刀，结果发现复杂度很高。

后来，我逆向思考，枚举横竖的所有切割，再求出不切割的最优价值，取最大值即可

不切割的最优价值，其实就是求二维最优值，好像需要树套树，我也不会。

后来，我突然意识到，不切割的最优值，在枚举横竖切的时候，也会遇到。
所以，不切割只需要判断是否存在当前不切割大小矩阵的输入矩阵即可。

算法：

预处理输入，储存在二维表格中，代表一个矩阵是否存在，存在了价值是多少。

状态：f(n,m)大小为 n*m的矩阵可以得到的最大价值。

状态转移方程：

f(n, m) = input(n, m) // 不存在为0
f(n, m) = max(f(n, m), f(i, m) + f(n-i, m))
f(n, m) = max(f(n, m), f(n, i) + f(n, m-i))

复杂度：O(n*3)

五、最后

这次比赛除了最后一题，前三题都有三种方法，我都第一时间想到的是方法一。

其中第三题的方法二非常妙，是一个不错的思路，值得学习

而对于第四题，则不好评价。

如果从枚举小矩阵入手，可能就会陷入无底深渊。
如果从枚举切割入手，就会想二维线段树，进而发现预处理打标记即可。

总的来说，我认为这次比赛算比较难吧。

不过由于我没参加比赛，就知道我能排多少名了。

加油，算法人。

《完》

-EOF-

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