一、5952. 环和杆
1、题目简介
2、题目解析
- 签到题，我们使用
Map>来进行存储 - 遍历
map，判断value的size是否为3就可
3、题目代码
class Solution { public int countPoints(String rings) { Map<Character, Set<Character>> map = new HashMap<>(); for (int i = 0; i < rings.length(); i = i + 2) { char ch = rings.charAt(i); char index = rings.charAt(i + 1); if (map.containsKey(index)) { map.get(index).add(ch); } else { Set<Character> set = new HashSet<>(); set.add(ch); map.put(index, set); } } int num = 0; for (Set<Character> set : map.values()) { if (set.size() == 3) { num++; } } return num; } }
二、5953. 子数组范围和
1、题目简介
2、题目解析
- 这个题，W了三次才过，原因在于：我一开始使用
List>来进行存储，导致内存直接爆了，时间也超时了 - 后续想了想优化空间：
使用两个最优队列来存储当前的最大值和最小值，这样我们就可以用O(1)的时间复杂度获取当前max - min的值 - 最后第4次才过，呜呜呜
- 第二种做法：我们暴力的同时使用
max和min维护当前的最大值和最小值，见代码二
3、题目代码
代码一 时间复杂度相对 代码二 来说，主要增加了 最优队列 中 选举最大或最小 的时间
3.1 代码一
class Solution { public long subArrayRanges(int[] nums) { long sum = 0; for (int i = 0; i < nums.length; i++) { sum = sum + f(nums, i, 0); } return sum; } public long f(int[] nums, int index, long sum) { PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } }); List<Long> path = new ArrayList<>(); for (int i = index; i < nums.length; i++) { priorityQueue.add(nums[i]); priorityQueue2.add(nums[i]); sum = sum + (priorityQueue.peek() - priorityQueue2.peek()); } return sum; } }
3.2 代码二
class Solution { public long subArrayRanges(int[] nums) { long sum = 0; for (int i = 0; i < nums.length; i++) { int max = nums[i]; int min = nums[i]; for(int j = i + 1; j < nums.length; j++){ max = Math.max(max, nums[j]); min = Math.min(min, nums[j]); sum += max - min; } } return sum; } }
三、5954. 给植物浇水 II
1、题目简介
2、题目解析
- 模拟题，模拟每次倒水的流程
- 题主这里W一次是因为忘记
当前的水 = 可浇水，忘记相等也可以直接浇水了，笔误。。。。
3、题目代码
class Solution { public int minimumRefill(int[] plants, int capacityA, int capacityB) { int sum = 0; int capacityAMAX = capacityA; int capacityBMAX = capacityB; // A从开头浇水 // B从结尾浇水 int indexA = 0; int indexB = plants.length - 1; while (indexA < indexB) { // A 浇水 if (plants[indexA] <= capacityA) { capacityA = capacityA - plants[indexA]; } else { sum++; capacityA = capacityAMAX; capacityA = capacityA - plants[indexA]; } // B浇水 if (plants[indexB] <= capacityB) { capacityB = capacityB - plants[indexB]; } else { sum++; capacityB = capacityBMAX; capacityB = capacityB - plants[indexB]; } indexA++; indexB--; } if (indexA == indexB) { if (capacityA >= capacityB) { if (plants[indexA] <= capacityA) { capacityA = capacityA - plants[indexA]; } else { sum++; capacityA = capacityAMAX; capacityA = capacityA - plants[indexA]; } } else { // B浇水 if (plants[indexB] <= capacityB) { capacityB = capacityB - plants[indexB]; } else { sum++; capacityB = capacityBMAX; capacityB = capacityB - plants[indexB]; } } } return sum; } }
四、5955. 摘水果
1、题目简介
2、题目解析
- 题主一开始直接写了一个
dfs交上去了，不出所料，就这数据量，卡的死死的 - 我们将题目简化为：
在一段区间中，找到最大的水果总数[L,R] - 这个区间的范围：我们的总步数为
k
- 我们可以先往右走
i步，再往左走k - i，那么我们的区间为：[startPos + i - k + i ,startPos + i] - 我们也可以先往左走
i步，再往左走k - i，那么我们的区间为：[startPos - i, startPos - i + k - i]
- 我们可以用前缀和求出整个表上的水果数目，然后暴力求每个区间的获得水果的最大值
3、题目代码
3.1 DFS
public int maxTotalFruits(int[][] fruits, int startPos, int k) { Map<Integer, Integer> map = new HashMap<>(); int max = Integer.MIN_VALUE; for (int i = 0; i < fruits.length; i++) { int index = fruits[i][0]; if (max <= index) { max = index; } int value = fruits[i][1]; map.put(index, value); } return dfs(map, startPos, k, max, 0); } public int dfs(Map<Integer, Integer> map, int startPos, int k, int len, int sum) { // 判断越界 if (startPos < 0 || startPos >= len || k == 0) { return sum; } int value = map.getOrDefault(startPos, 0); // 判断一下有没有吃到水果 if (map.containsKey(startPos)) { sum = sum + map.get(startPos); // 需要将此后设置为0 map.put(startPos, 0); } // 然后去下一个状态 int num1 = dfs(map, startPos - 1, k - 1, len, sum); int num2 = dfs(map, startPos + 1, k - 1, len, sum); // 最后别忘记了回溯 map.put(startPos, value); return Math.max(num1, num2); }
3.2 贪心
class Solution { public int maxTotalFruits(int[][] fruits, int startPos, int k) { int MAX = 200001; int[] arr = new int[MAX]; int index = 0; int currSum = 0; for(int i = 0; i < MAX; i++){ if(index < fruits.length && fruits[index][0] == i){ currSum = currSum + fruits[index][1]; index++; } arr[i] = currSum; } // 计算K步最多能走的步数 int res = 0; //先往左走i步, 再往右走 k - i 步 for(int i = 0; i <= k; i++){ // 防止越界 int left = Math.max(0, startPos - i); int right = Math.min(MAX - 1, left + k - i); int curr = arr[right] - (left == 0 ? 0 : arr[left - 1]); res = Math.max(res, curr); } // 先往右走i步，再往左走k - i步 for(int i = 0; i <= k; i++){ int right = Math.min(startPos + i, MAX - 1); int left = Math.max(0, right - k + i); int curr = arr[right] - (left == 0 ? 0 : arr[left - 1]); res = Math.max(res, curr); } return res; } }
五、总结
本周又是三题，由于一些细心问题，导致罚时过多，过三题排名 626 ~ 2250
可以看出，程序员的算法能力逐渐开始上升
下周争取不迟到，争取AK！
