上次参加 leetcode 比赛还是去年四月份的时候了。回想的时候总觉得时间过得很快。只是一年，以前一起比赛的小伙伴们包括我自己都已经离开哥村了。

第一题Convert Binary Number in a Linked List to Integer

以单向链表给出一个二进制数，将其转成十进制。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        r = 0
        while head:
            r = r * 2 + head.val
            head = head.next
        return r

第二题Sequential Digits

找出两个数 low 和 high 之间所有“后面一位数字比前面一位大1”的数（比如 123、3456）。

我一开始觉得这题很麻烦，先做了第三题。再次读题的时候我发现我可以枚举所有“后面一位数字比前面一位大1”的数，然后保留low 和 high 之间的数就行。

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ret = []
        for s in range(1, 10):
            c = s
            i = s + 1
            while c < high and i < 10:
                c = c * 10 + i
                i += 1
                if low <= c <= high:
                    ret.append(c)
        ret.sort()
        return ret

第三题Maximum Side Length of a Square with Sum Less than or Equal to Threshold

给定一个二维数组和一个阈值，我们想找出所有数字之和小于阈值的正方形子数组的最大边长。

对正方形数组的边长做二分查找。

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        # 预处理，方便查询数组中矩形区域的和
        n = len(mat)
        m = len(mat[0])
        s = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n):
            for j in range(m):
                s[i][j] = s[i-1][j] + s[i][j-1] + mat[i][j] - s[i-1][j-1]

        # 判断是否存在边长为 c 的所有数字之和小于 threshold 的正方形区域
        def check(c):
            for i in range(n-c+1):
                for j in range(m-c+1):
                    if s[i+c-1][j+c-1] - s[i-1][j+c-1] - s[i+c-1][j-1] + s[i-1][j-1] <= threshold:
                        return True
            return False

        # 二分查找
        a = 0
        b = min(n, m)
        r = 0
        while a <= b:
            c = (a + b) // 2
            if check(c):
                r = c
                a = c + 1
            else:
                b = c - 1
        return r

第四题Shortest Path in a Grid with Obstacles Elimination

经典的迷宫问题的变种：找出从左上到右下的最短路径的长度。只是现在我们允许通过最多 k 个障碍。

一开始以为可以动态规划，但是没有想出来。于是直接就深度搜索+剪枝了。我一开始就做了一个剪枝：如果当前的搜索路径长度已经大于已有的路径的长度，那么就没有必要继续下去了。不幸的是，这个算法TLE了。然后我又想到了另一个明显的剪枝：如果现在找到的答案已经是最小的，那么就没有必要搜索下去了。没有想到加上这个剪枝就过了。

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        n = len(grid)
        m = len(grid[0])
        ans = [-1]
        visited = [[False] * m for _ in range(n)]
        def dfs(x, y, s, c):
            if ans[0] == (n+m-2) or ans[0] != -1 and ans[0] < s:
                return
            if x == n-1 and y == m-1:
                ans[0] = s
                return
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                cx = x + dx
                cy = y + dy
                if cx < 0 or cy < 0 or cx >= n or cy >= m or visited[cx][cy]:
                    continue
                visited[cx][cy] = True
                if (grid[cx][cy] == 0):
                    dfs(cx, cy, s+1, c)
                elif c > 0:
                    dfs(cx, cy, s+1, c-1)
                visited[cx][cy] = False

        visited[0][0] = True
        dfs(0, 0, 0, k)
        return ans[0]
leetcode contest