👨🎓作者简介：爱好技术和算法的研究生
🌌上期文章：力扣周赛：第421场周赛
📚订阅专栏：力扣周赛
希望文章对你们有所帮助
感觉这场比赛的前三题太简单了，除了签到题以外，那两个mid难度的题直接用bfs+记忆化就可以过了，第三题数据量大一点那就用优先队列优化一下距离优先，当然了也可以直接用dijkstra优先队列优化来做，都挺容易的。第四题大致看了一下，有一个Perm+记忆化搜索的思路，但是面试coding一般不会考这么难的，自己时间有限就直接略过了。
力扣周赛：第422场周赛
- 检查平衡字符串
- 到达最后一个房间的最少时间 I
- 到达最后一个房间的最少时间 II
检查平衡字符串
题目描述
给你一个仅由数字 0 - 9 组成的字符串 num。如果偶数下标处的数字之和等于奇数下标处的数字之和，则认为该数字字符串是一个 平衡字符串。
如果 num 是一个 平衡字符串，则返回 true；否则，返回 false。
示例1
输入：num = “1234”
输出：false
解释：
偶数下标处的数字之和为 1 + 3 = 4，奇数下标处的数字之和为 2 + 4 = 6。
由于 4 不等于 6，num 不是平衡字符串。
示例2
输入：num = “24123”
输出：true
解释：
偶数下标处的数字之和为 2 + 1 + 3 = 6，奇数下标处的数字之和为 4 + 2 = 6。
由于两者相等，num 是平衡字符串。
提示
- 2 <= num.length <= 100
- num 仅由数字 0 - 9 组成。
签到题，不必多说
class Solution {public boolean isBalanced(String num) {int l = 0, r = 0;for(int i = 0; i < num.length(); ++i){if((i & 1) == 1)l += num.charAt(i) - '0';else r += num.charAt(i) - '0';}return l == r ? true : false;}
}
到达最后一个房间的最少时间 I
题目描述
有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。
给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为 1 秒。
请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。
如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。
示例1
输入：moveTime = [[0,4],[4,4]]
输出：6
解释：
需要花费的最少时间为 6 秒。
在时刻 t = 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
在时刻 t = 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 1 秒。
示例2
输入：moveTime = [[0,0,0],[0,0,0]]
输出：3
解释：
需要花费的最少时间为 3 秒。
在时刻 t = 0 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
在时刻 t = 1 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 1 秒。
在时刻 t = 2 ，从房间 (1, 1) 移动到房间 (1, 2) ，花费 1 秒。
提示
- 2 <= n == moveTime.length <= 50
- 2 <= m == moveTime[i].length <= 50
- 0 <= moveTime[i][j] <= 109
解法一：直接bfs，然后记忆化一个count表示到达这个点的最短时间，之后如果有其他到达这个情况的时候就判断一下是不是大于这个count，是的话就没必要继续走了。类似dfs的剪枝。
解法二：dijkstra
解法一：
class Solution {public int res = (int)(1e9 + 150);public static final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int m, n;public class Node{int x, y, ans;public Node(int x, int y, int ans){this.x = x;this.y = y;this.ans = ans;}}public int minTimeToReach(int[][] moveTime) {m = moveTime.length; n = moveTime[0].length;int[][] count = new int[m][n];for(int i = 0; i < m; ++i)Arrays.fill(count[i], Integer.MAX_VALUE);count[0][0] = 0;Queue<Node> q = new LinkedList<>();q.add(new Node(0, 0, 0));while(q.size() > 0){Node u = q.peek(); q.poll();if(u.ans >= res)continue;if(u.x == m - 1 && u.y == n - 1){res = Math.min(res, u.ans);}for(int i = 0; i < 4; ++i){int newx = u.x + dir[i][0], newy = u.y + dir[i][1];if(check(newx, newy) && count[newx][newy] > u.ans){count[newx][newy] = Math.max(u.ans, moveTime[newx][newy]);q.add(new Node(newx, newy, count[newx][newy] + 1));}}}return res;}public boolean check(int x, int y){if(x >= 0 && x < m && y >= 0 && y < n)return true;return false;}
}
解法二：
class Solution {int[] move = new int[]{-1, 0, 1, 0, -1};public int minTimeToReach(int[][] moveTime) {int n = moveTime.length;int m = moveTime[0].length;return dijkstra(moveTime, 0, 0, n - 1, m - 1);}public int dijkstra(int[][] grid, int startX, int startY, int targetX, int targetY) { int n = grid.length;int m = grid[0].length;int[][] distance = new int[n][m];for (int i = 0; i < n; i++)Arrays.fill(distance[i], Integer.MAX_VALUE);distance[startX][startY] = 0;boolean[][] visited = new boolean[n][m];PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);heap.add(new int[]{startX, startY, 0});while (!heap.isEmpty()) {int[] cur = heap.poll();int x = cur[0];int y = cur[1];if (visited[x][y]) {continue;}visited[x][y] = true;if (x == targetX && y == targetY)return distance[x][y];for (int i = 0, nx, ny; i < 4; i++){nx = x + move[i];ny = y + move[i + 1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]&& (distance[x][y] < grid[nx][ny] ? grid[nx][ny] + 1 : distance[x][y] + 1) < distance[nx][ny]) {distance[nx][ny] = distance[x][y] < grid[nx][ny] ? grid[nx][ny] + 1 : distance[x][y] + 1;heap.add(new int[]{nx, ny, distance[nx][ny]});}}}return -1;}
}
到达最后一个房间的最少时间 II
题目描述
有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。
给你一个大小为 n x m 的二维数组 moveTime ，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为：第一次花费 1 秒，第二次花费 2 秒，第三次花费 1 秒，第四次花费 2 秒……如此 往复 。
请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。
如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。
示例1
输入：moveTime = [[0,4],[4,4]]
输出：7
解释：
需要花费的最少时间为 7 秒。
在时刻 t = 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
在时刻 t = 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 2 秒。
示例2
输入：moveTime = [[0,0,0,0],[0,0,0,0]]
输出：6
解释：
需要花费的最少时间为 6 秒。
在时刻 t = 0 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。
在时刻 t = 1 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 2 秒。
在时刻 t = 3 ，从房间 (1, 1) 移动到房间 (1, 2) ，花费 1 秒。
在时刻 t = 4 ，从房间 (1, 2) 移动到房间 (1, 3) ，花费 2 秒。
提示
- 2 <= n == moveTime.length <= 750
- 2 <= m == moveTime[i].length <= 750
- 0 <= moveTime[i][j] <= 109
其实主要还是数据量变大了，所以用优先队列优化一下，使用最小堆就好了，保证队头元素一直都是路程比较短的，之后如果遍历到路程太长的，直接和res判断一下就好了，如果比res小说明还有尝试的价值，否则不再尝试，这样就不会超时了。
class Solution {public int res = Integer.MAX_VALUE;public static final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int m, n;public class Node{int x, y, ans, step;public Node(int x, int y, int ans, int step){this.x = x;this.y = y;this.ans = ans;this.step = step;}}public int minTimeToReach(int[][] moveTime) {m = moveTime.length; n = moveTime[0].length;int[][] count = new int[m][n];for(int i = 0; i < m; ++i)Arrays.fill(count[i], Integer.MAX_VALUE);count[0][0] = 0;//Queue<Node> q = new LinkedList<>();PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.ans - o2.ans);q.add(new Node(0, 0, 0, 0));while(q.size() > 0){Node u = q.peek(); q.poll();if(u.ans >= res)continue;if(u.x == m - 1 && u.y == n - 1){res = Math.min(res, u.ans);}for(int i = 0; i < 4; ++i){int newx = u.x + dir[i][0], newy = u.y + dir[i][1];if(check(newx, newy) && count[newx][newy] > u.ans){count[newx][newy] = Math.max(u.ans, moveTime[newx][newy]);if((u.step & 1) == 0){q.add(new Node(newx, newy, count[newx][newy] + 1, u.step + 1));}else{q.add(new Node(newx, newy, count[newx][newy] + 2, u.step + 1));}}}}return res;}public boolean check(int x, int y){if(x >= 0 && x < m && y >= 0 && y < n)return true;return false;}
}