【Zilliz专场】力扣第 271 场周赛
你好，我是小黄，一名独角兽企业的Java开发工程师。 感谢茫茫人海中我们能够相遇，
俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习
希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。
这周没起来，迟到了一会~
一、5952. 环和杆
1、题目简介
2、题目解析
- 签到题，我们使用
Map<Character, Set<Character>>来进行存储 - 遍历
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<List<Integer>>来进行存储，导致内存直接爆了，时间也超时了 - 后续想了想优化空间：
使用两个最优队列来存储当前的最大值和最小值，这样我们就可以用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！
#Java##学习路径#
