8-周赛334总结
终于过了三题，第二题卡了很久，最后才灵光一现。然后第四题就来不及做了，太着急了，卡在了反复移动计算时间点上。这周继续努力啦
左右元素和的差值【LC2574】
给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：
answer.length == nums.length
answer[i] = |leftSum[i] - rightSum[i]|
其中：
leftSum[i]是数组nums中下标i左侧元素之和。如果不存在对应的元素，leftSum[i] = 0。
rightSum[i]是数组nums中下标i右侧元素之和。如果不存在对应的元素，rightSum[i] = 0。
返回数组 answer 。
思路：简单模拟
按照要求求出leftSum[i]和rightSum[i]，然后计算出answer[i] = |leftSum[i] - rightSum[i]|
class Solution { public int[] leftRigthDifference(int[] nums) { int n = nums.length; int[] res = new int[n]; int[] left = new int[n]; int[] right = new int[n]; for (int i = 1; i < n; i++){ left[i] = left[i - 1] + nums[i - 1]; } for (int i = n - 2; i >= 0; i--){ right[i] = right[i + 1] + nums[i + 1]; } for (int i = 0; i < n; i ++){ res[i] = Math.abs(left[i] - right[i]); } return res; } }
复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
优化：一个循环计算left和right
class Solution { public int[] leftRigthDifference(int[] nums) { int n = nums.length; int[] res = new int[n]; int[] left = new int[n]; int[] right = new int[n]; for (int i = 1; i < n; i++){ left[i] = left[i - 1] + nums[i - 1]; right[n - i - 1] = right[n - i] + nums[n - i]; } for (int i = 0; i < n; i ++){ res[i] = Math.abs(left[i] - right[i]); } return res; } }
找出字符串的可整除数组【LC2575】
给你一个下标从 0 开始的字符串
word，长度为n，由从0到9的数字组成。另给你一个正整数m。
word的 可整除数组div是一个长度为n的整数数组，并满足：
- 如果
word[0,...,i]所表示的 数值 能被m整除，div[i] = 1- 否则，
div[i] = 0返回
word的可整除数组。
思路【重点在于如何处理越界 卡了贼久】
- 使用变量
cur记录word[0,i]的整数值，如果该值能被m整除，那么ans[i]=1
class Solution { public int[] divisibilityArray(String word, int m) { int n = word.length(); int[] res = new int[n]; long cur = 0L; for (int i = 0; i < n; i++){ cur = (cur * 10 + word.charAt(i) - '0') % m; if (cur == 0){ res[i] = 1; } } return res; } }
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O ( 1 )
求出最多标记下标【LC2576】
给你一个下标从 0 开始的整数数组
nums。一开始，所有下标都没有被标记。你可以执行以下操作任意次：
- 选择两个 互不相同且未标记 的下标
i和j，满足2 * nums[i] <= nums[j]，标记下标i和j。
请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。
贪心+双指针
- 思路：贪心+双指针
class Solution { public int maxNumOfMarkedIndices(int[] nums) { int res = 0, n = nums.length; Arrays.sort(nums); int l = 0; int r = n / 2 ; while (l < n / 2 && r < n){ if (nums[l] * 2 <= nums[r]){ // res += 2; l++; r++; }else{ r++; } } return 2 * l; } }
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
在网格图中访问一个格子的最少时间【LC2577】
给你一个
m x n的矩阵grid，每个元素都为 非负 整数，其中grid[row][col]表示可以访问格子(row, col)的 最早 时间。也就是说当你访问格子(row, col)时，最少已经经过的时间为grid[row][col]。你从 最左上角 出发，出发时刻为
0，你必须一直移动到上下左右相邻四个格子中的 任意 一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。请你返回 最早 到达右下角格子的时间，如果你无法到达右下角的格子，请你返回
-1。
思路：BFS+最短路径
- 由于需要求出访问到右下角的最早时间，每次只能移动一格，也就是最短路径，因此可以考虑使用最短路径Dijkstra 算法求最短路径。
class Solution { public int minimumTime(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; if (grid[1][0] > 1 && grid[0][1] > 1 ) return -1;// 无法达到右下角 PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]); pq.add(new int[]{0, 0, 0}); boolean[][] visited = new boolean[m][n];// 存储最短时间 visited[0][0] = true; while(!pq.isEmpty()){ int[] pos = pq.poll(); for (int j = 0; j < 4; j++){ int nextX = pos[0] + dir[j][0]; int nextY = pos[1] + dir[j][1]; if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY]){ int t = pos[2] + 1;// grid[nextX][nextY] <= pos[2] 直接走进 // 来回等待时间 if (grid[nextX][nextY] > pos[2] + 1){ t += (grid[nextX][nextY] - pos[2]) / 2 * 2;// 等待的时间 } if (nextX == m - 1 && nextY == n - 1) return t; pq.add(new int[]{nextX, nextY, t}); visited[nextX][nextY] = true; } } } return -1; } }
复杂度
- 时间复杂度：O(mnlogmn)，m 、 n 为矩阵的行和列数节点数。
- 空间复杂度：O ( m n )
