leetcode 第 225 场算法比赛

零、背景

这次比赛终于有点难度，但是犯各种小错误，在一百名附近徘徊了。

下次可以再难点，我就有希望进去前百名了。

一、替换隐藏数字得到的最晚时间

题意：合法时间是00:00 到 23:59。
现在给一些合法时间，部分数字使用?代替了。
问可能的合法最大时间是多少？

思路：最简单的方法是枚举所有时间，看是否匹配。
复杂度：O(24*60)

常数复杂度的方法是分段讨论。

对于分钟，由于从00到59是连续的，可以无脑取最大值。
对于小时，超过 20 后，最大是23。所以需要特殊判断。
具体逻辑是优先判断是否可以取值 20+ 的小时，否则第一位不能取2，第二位可以取最大值。
复杂度：O(1)

PS：手残，字符1忘记加引号了，写成数字1了，WA 了一次。

二、满足三条件之一需改变的最少字符数

题意：给两个字符串，可以任意修改每个字符的值。
问是否可以让一个字符串的所有字符都小于另外一个字符串。
当然，如果两个字符串的字符完全相同也可以。
求最小修改次数。

思路：枚举。

优先枚举a-z，使得所有字符相同时，最优答案是什么。
然后枚举小于的情况，枚举边界a-z，左边的字符串小于等于边界，右边的大于边界，求最优答案。

PS：对于边界z是非法情况，因为不存在大于z的字符。
我本来枚举的边界是a-y，后来合并了两个循环，忘记处理z了，WA 一次。
而且这次 WA 时判题系统也没有给出反例，不过我知道存在这种边界情况，加了一个特殊判断就过了。

三、找出第 K 大的异或坐标值

题意：给一个矩阵，构造一个新的矩阵。
新的矩阵每个方格的值，是旧矩阵左上方子矩阵的异或结果。
求新矩阵中，所有值里面的第 K 大的值。

思路：算是动态规划题。
核心方程：

dp(i,j) = val(i,j) ^ dp(i-1, j) ^ dp(i,j-1) ^ dp(i-1,j-1)  

求新矩阵时，处理好第一行和第一列的边界即可。

求出新矩阵后，对所有值逆序排序即可。

四、放置盒子

题意：给 n 个正方体盒子，在房间里摆盒子。
盒子可以放在地面上，也可以对齐放在其他盒子上。
放在其他盒子之上时，这些盒子的底部四条边必须和其他盒子相连，即下面的那个盒子周围必须全部有其他盒子。
由于是在房间里，允许盒子挨着墙方，此时挨着墙的那一个底部边允许没有其他盒子相连，即下面的那个盒子的一面允许靠着墙。

可以看下图来理解题意。

思路：简单纸上画画，可以发现这是一个公式题。

先下个定义： num 完美组合。
代表使用盒子摆出了一个长宽高都是 num 的盒子组合，且不能再多了。

此时我们要做的是怎么摆出 num+1的完美组合。

如上图，显然，需要一侧需要新增一行，个数为 1 。
倒数第二行可以新增两个，先摆外面，再摆里面。
倒数第三行可以新增三个，也是先摆外面。
依次递推，最后一行可以新增 num+1 个。
从而组成了 num+1的完美组合。

新的完美组合新增了 1+2+...+num+1 个盒子。

自此，我们就可以得到相关公式了。

f(num) = f(num-1) + num*(num+1)/2;

注意事项：如果输入的 n 不是完美组合答案，则需要按照上面的模拟，从 1 加到 num+1，来看中间状态需要多少个盒子。

int minimumBoxes(int n) {
    ll sum = 1, num = 1, ans = 1;
    while(sum < n){
        num++;
        ll add = (1+num)*num/2;
        if(sum + add <= n){
            sum += add;
            ans += num;
            continue;
        }

        for(int i=1; i<=num;i++){
            ans++;
            sum += i;
            if(sum >= n){
                return ans;
            }
        }
    }
    return ans;
}

五、最后

这次比赛没啥说的了，以后再难点就好了。

加油，算法人。

《完》

-EOF-

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