讨论/题目交流/🏆 第 167 场力扣周赛/
🏆 第 167 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 二进制链表转整数
5 分 - 顺次数
5 分 - 元素和小于等于阈值的正方形的最大边长
6 分 - 网格中的最短路径

展开讨论

第一题

条件: 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。

思路:直接遍历链表,转换为字符串

class Solution:

    def getDecimalValue(self, head: ListNode) -> int:
        """
        遍历链表,用str存储,转10进制
        :param head:
        :return:
        """
        p = head
        res = ''
        while p:
            res += str(p.val)
            p = p.next
        return int(res, 2)

第二题

条件:我们定义「顺次数」为:每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表(从小到大排序)。

范围: 10 <= low <= high <= 10^9

思路:直接枚举1~9,后面位数=当前位数+1,记录下就可以

class Solution:

    def __is_suitable_number(self, num):
        pre = num % 10
        num = num // 10
        while num:
            if num % 10 + 1 != pre:
                return False

            pre = num % 10
            num = num // 10
        return True

    def sequentialDigits(self, low: int, high: int) -> List[int]:
        high_counter = self.digit(high)
        res = []
        for j in range(1, 10):
            num = j
            flag = False
            pre = j
            for i in range(high_counter):
                pre += 1
                num = num * 10 + pre
                if low <= num <= high:
                    if self.__is_suitable_number(num):
                        res.append(num)
                    continue
                elif num > high:
                    flag = True
                    break
            if flag:
                continue

        res.sort()
        return res

    def digit(self, num):
        counter = 1
        while num // 10:
            counter += 1
            num = num // 10
        return counter

第三题

条件:给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长;如果没有这样的正方形区域,则返回 0 。

范围:

  • 1 <= m, n <= 300
  • m == mat.length
  • n == mat[i].length
  • 0 <= mat[i][j] <= 10000
  • 0 <= threshold <= 10^5

思路: 这道题,求的是最大边长,由此可以跳过很多比当前最大边长小的区域,直接遍历就过了,代码还能用前缀和优化下区域求和,比较懒就不写了,有兴趣的可以自己写下.

class Solution:
   
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        """
        暴力遍历,以当前位置找正方形最大区域
        :param mat:
        :param threshold:
        :return:
        """
        import numpy as np
        mat = np.array(mat)
        row = len(mat)
        col = len(mat[0])

        min_val = float('-inf')
        max_length = -1
        for i in range(row):
            for j in range(col):
                # 最大区域
                length = min(row - i, col - j)
                if length <= max_length:
                    break
                # 对正方形区域内的值进行求和
                # 区域范围2 ~ 最大区域
                for k in range(2, length + 1):
                    if k <= max_length:
                        continue
                    nums = mat[i:i + k, j:j + k]
                    sums = nums.sum()
                    if sums <= threshold and nums.shape == (k, k):
                        min_val = max(min_val, k)
                        max_length = max(max_length, k)
                    elif sums > threshold:
                        break

        return min_val if min_val != float('-inf') else 0

第四题

条件:给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。

范围:

  • grid.length == m
  • grid[0].length == n
  • 1 <= m, n <= 40
  • 1 <= k <= m*n
  • grid[i][j] == 0 or 1
  • grid[0][0] == grid[m-1][n-1] == 0

思路:这道题用bfs和dfs都能做,不过bfs相对简单些,第一个到达终点的就是最短路径,转移状态时,只需要判断当前是否为障碍,如果消除当前障碍,并且计数 > k,则跳过当前状态点.

class Solution:
    
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        """
        bfs,消除障碍
        :param grid:
        :param k:
        :return:
        """
        from collections import deque
        row = len(grid)
        col = len(grid[0])

        queue = deque()
        queue.appendleft((0, 0, 0, 0))

        seen = set()
        seen.add((0, 0, 0))

        while queue:
            i, j, counter, step = queue.pop()

            if i == row - 1 and j == col - 1:
                return step

            if grid[i][j] == 1:
                counter += 1
            if counter > k:
                continue

            for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                tmp_i, tmp_j = x + i, y + j
                if 0 <= tmp_i < row and 0 <= tmp_j < col and (tmp_i, tmp_j, counter) not in seen:
                    queue.appendleft((tmp_i, tmp_j, counter, step + 1))
                    seen.add((tmp_i, tmp_j, counter))

        return -1
2
展开全部 10 讨论