Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/21 00:01)推噓0(0推 0噓 3→)

留言3則, 2人參與討論串352/719 (看更多)

https://leetcode.com/problems/k-radius-subarray-averages/description/ 2090. K Radius Subarray Averages 給你一個整數陣列 nums 和一個數字 k 表示左右間距，返回一個陣列 res， res[i] = nums[i-k] + nums[i-k+1] + ... + nums[i+k], 若 i >= k 且 i < nums.len res[i] = -1, 若 i < k 或 i + k > nums.len Example 1: https://assets.leetcode.com/uploads/2021/11/07/eg1.png

Input: nums = [7,4,3,9,1,8,5,2,6], k = 3 Output: [-1,-1,-1,5,4,4,-1,-1,-1] Explanation: - avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index. - The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37. Using integer division, avg[3] = 37 / 7 = 5. - For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4. - For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4. - avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index. Example 2: Input: nums = [100000], k = 0 Output: [100000] Explanation: - The sum of the subarray centered at index 0 with radius 0 is: 100000. avg[0] = 100000 / 1 = 100000. Example 3: Input: nums = [8], k = 100000 Output: [-1] Explanation: - avg[0] is -1 because there are less than k elements before and after index 0. 思路： 1.因為題目要求出每個點的左右和平均，而多次求和可以使用prefixSum來快速求和。 2.先把 corner case 排掉，若 k = 0 的話每個點的平均都會是自己所以直接返回 nums ，如果 k * 2 + 1 比 n 大表示每個點求範圍和都會越界所以直接返回全為 -1 的解。 3.再來只要求出前綴和，然後找出 k ~ n -k 區間每一個點做為中心的和除以k即可，比較需要注意的是如果用int會爆掉，要用long才能AC。 Java Code： ------------------------------------------- class Solution { public int[] getAverages(int[] nums, int k) { int n = nums.length; int[] res = new int[n]; if (k == 0) { return nums; } if (k * 2 + 1 > n) { Arrays.fill(res, -1); return res; } for (int i = 0; i < k; i++) { res[i] = -1; res[n - i - 1] = -1; } long[] prefix = new long[n]; prefix[0] = nums[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + nums[i]; } for (int i = k; i < n - k; i++) { long sum = getSum(prefix, i - k, i + k); res[i] = (int)((sum)/(2 * k + 1)); } return res; } private long getSum(long[] nums, int i, int j) { if (i == 0) { return nums[j]; } else { return nums[j] - nums[i - 1]; } } } ------------------------------------------- -- https://i.imgur.com/tdaniED.jpg