Leetcode 第 167 场比赛回顾

零、背景

趁着周三年会，做了上周的两次比赛。
这两次比赛的题都是基础里，单周赛的题解昨天已经写了，今天写写双周赛的题解。

一、二进制转整数

题意：给一个链表组成的二进制，求转化为十进制整数。

思路：循环计算即可。

二、有序数字

题意：给一个数字区间，找出这个区间内的所有有序数字。
定义：一个数字从高位到低位是连续递增，则称为有序数字。

例如：123就是有序数字，因为1+1=2，2+1=3

思路：因为最高位的数字只能是1~9，后面的位数又都是递增的。
那对于某一个长度位数的所有数字，有序数字不会超过9个。
而且位数越长，有序数字越少。

比如对于9位的数字，只有一个有序数字，那就是123456789。
而对于8位的数字，则有两个有序数字，那就是12345678和23456789。
依次递推，长度为2的有序数字有8个。
那么所有有序数字是1+2+...+8为36个。

我们枚举所有有序数字，看是否在输入的区间即可。

三、正方形和小于目标数

题意：给一个矩阵，问矩阵里是否存在一个正方形，其和小于目标数。
如果存在，找到最大的正方形，输出其边长。

思路：最简单的方法就是边长不断递增，然后判断这个边长是否有答案。
而判断是否有答案的方法则是枚举所有正方形，求和。

复杂度分析：边长递增 * 枚举所有正方形 * 正方形求和。
复杂度：O(n^5)
由于数据比较小，这个方法也可以通过。

这道题其实在之前的比赛中出现过。

在计算矩阵和的时候，完全可以预处理，然后O(1)算出来。
比如我们已经计算出每个定点到左上角的矩阵和了， 那一个顶点为右下角的正方形也可以通过矩阵和的加加减减计算出来。

而对于遍历边长，可以改成二分查找。
这样复杂度就是O(n^2 log(n))的了。

四、有障碍物的最短路

题意：给一个矩阵，起始位置在左上角，可以上下左右移动。
有些坐标有障碍物，最多可以跳过 K 个障碍物，问能否到达右下角。
如果可以，求最小步数。

思路：路径最小步数问题，典型的 BFS 问题。
到达一个坐标时，由于存在障碍物的跳数，所以坐标是有状态的。
有状态的坐标需要使用三元组<x, y, k>来标示，代表跳过k个障碍物后到达<x,y>

由此，我们就可以BFS找出答案了。
复杂度分析：坐标个数n^2，每个坐标状态个数k
复杂度：k n^2

优化：分析后，可以发现，有些状态是显然不会更优的。
比如那些回头的坐标，此时跳数更大。

所以，对于相同的坐标，如果再次遇到时，跳数更大了，显然不会最优。

而对于跳数更小的场景，则可能是答案。 应为之前跳数大的状态可能无法到达目标，而跳数小的可以走的更远，从而可能到达目标。

复杂度：均摊是 n^2

五、最后

这次比赛都比较简单，大部分也之前也都遇到。
比如矩阵里面最大的正方形，矩阵路径问题，都是做过的题。

-EOF-

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