LeetCode第167场周赛

Posted on | Post modified: | In
Words count in article: 1.6k

本文是leetcode contest 107的题解，包括：

1
2
3
4
1290.二进制链表转整数（简单）
1291. 顺次数 （中等）
1283.使结果不超过阈值的最小除数 （中等）
1284.转化为全零矩阵的最少反转次数（困难）

AC1290和1292两题。

1290. 二进制链表转整数

题目描述

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1：

1
2
3
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

示例 2：

1
2
输入：head = [0]
输出：0

示例 3：

1
2
输入：head = [1]
输出：1

示例 4：

1
2
输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880

示例 5：

1
2
输入：head = [0,0]
输出：0

提示：

1
2
3
链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

解题思路

复杂度：O(30)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {

        int res = 0;

        while (head != null){
            res = res * 2 + head.val;
            head = head.next;
        }
        return res;

    }
}

1291. 顺次数

题目描述

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

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

示例 1：

1
2
输出：low = 100, high = 300
输出：[123,234]

示例 2：

1
2
输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

提示：

1
10 <= low <= high <= 10^9

解题思路

枚举所有的顺次数，如果符合条件则加入结果列表中，最后排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {

        List<Integer> res = new ArrayList<>();

        for (int i = 1; i <= 9; i++){
            int val = 0;
            for (int j = i; j <= 9; j++){
                val = val *10 + j;
                if (low <=val && val <= high){
                    res.add(val);
                }
            }
        }
        Collections.sort(res);
        return res;
    }
}

1292. 元素和小于等于阈值的正方形的最大边长

题目描述

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

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

示例 1：

1
2
3
输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出：2
解释：总和小于 4 的正方形的最大边长为 2，如图所示。

示例 2：

1
2
输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出：0

示例 3：

1
2
输入：mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
输出：3

示例 4：

1
2
输入：mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
输出：2

提示：

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

解题思路

维护二维前缀和（304题），，然后枚举正方形子矩阵的起点和变长，然后用二维子矩阵的和与threshold比较，如果满足就更新答案。
复杂度：O(n*m*min(n,m))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {


        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m+1][n+1];

        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }


        int res = 0;

        for (int i = 0; i <= m; i++){
            for (int j = 0; j <= n; j++) {
                int index = 1;
                while (i+index <= m && j+index <= n){
                    int sum = dp[i+index][j+index] - dp[i+index][j] - dp[i][j+index] + dp[i][j];
                    if (sum <= threshold){
                        res = Math.max(res, index);
                    }
                    index ++;
                }
            }
        }
        return res;
    }

}

1293. 网格中的最短路径

题目描述

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入： 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

示例 2：

1
2
3
4
5
6
7
8
9
输入：
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
输出：-1
解释：
我们至少需要消除两个障碍才能找到这样的路径。

提示：

1
2
3
4
5
6
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暴力搜索。

搜索的过程中携带三个状态 (x, y, cost)，(x, y) 代表点的位置，cost 代表这个点已经花费的消除次数。

dp[x][y][cost]：记录到达 (x, y) 且花费消除次数为 cost 的情况是否存在。如果存在这个情况或者cost>k则忽略当前点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    class Node {
        private int x;
        private int y;
        private int cost;
        private int step;

        public Node(int x, int y, int cost, int step) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.step = step;
        }
    }

    public int shortestPath(int[][] grid, int k) {

        int m = grid.length, n = grid[0].length;
        boolean[][][] dp = new boolean[m][n][k + 1];
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Queue<Node> queue = new ArrayDeque<>();

        queue.offer(new Node(0, 0, 0, 0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.x == m - 1 && node.y == n - 1) {
                return node.step;
            }
            for (int[] dir : dirs) {
                int x = node.x + dir[0], y = node.y + dir[1];
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    int cost = node.cost + grid[x][y];
                    if (cost > k || dp[x][y][cost]) continue;
                    dp[x][y][cost] = true;
                    queue.offer(new Node(x, y, cost, node.step + 1));
                }
            }
        }
        return -1;
    }
}
Donate comment here
------------The End------------
0%