【Zilliz專場】力扣第 271 場周賽覆盤
你好，我是小黃，一名獨角獸企業的Java開發工程師。 感謝茫茫人海中我們能夠相遇， 俗話說：當你的才華和能力，不足以支撐你的夢想的時候，請靜下心來學習 希望優秀的你可以和我一起學習，一起努力，實現屬於自己的夢想。
這周沒起來，遲到了一會~
一、5952. 環和杆
1、題目簡介
2、題目解析
- 簽到題，我們使用
Map<Character, Set<Character>>來進行儲存 - 遍歷
map，判斷value的size是否為3就可
3、題目程式碼
```java
class Solution {
public int countPoints(String rings) {
Map
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 程式碼一
```java 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 程式碼二
java
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、題目程式碼
```java 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
```java
public int maxTotalFruits(int[][] fruits, int startPos, int k) {
Map
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 貪心
```java 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！