【Zilliz专场】力扣第 271 场周赛复盘

怼烎@ 2023-10-01 09:22 0阅读 0赞

> 你好，我是小黄，一名独角兽企业的Java开发工程师。 感谢茫茫人海中我们能够相遇，  
> 俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习  
> 希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

**这周没起来，迟到了一会~**

#### 文章目录 ####

*  一、5952. 环和杆
 *   *  1、题目简介
     *  2、题目解析
     *  3、题目代码
 *  二、5953. 子数组范围和
 *   *  1、题目简介
     *  2、题目解析
     *  3、题目代码
     *   *  3.1 代码一
         *  3.2 代码二
 *  三、5954. 给植物浇水 II
 *   *  1、题目简介
     *  2、题目解析
     *  3、题目代码
 *  四、5955. 摘水果
 *   *  1、题目简介
     *  2、题目解析
     *  3、题目代码
     *   *  3.1 DFS
         *  3.2 贪心
 *  五、总结

## 一、5952. 环和杆 ##

### 1、题目简介 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16]

### 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;
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 1]

## 二、5953. 子数组范围和 ##

### 1、题目简介 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 2]

### 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;
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 3]

#### 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;
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 4]

## 三、5954. 给植物浇水 II ##

### 1、题目简介 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 5]

### 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;
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 6]

## 四、5955. 摘水果 ##

### 1、题目简介 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 7]

### 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;
    
        }
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_14_color_FFFFFF_t_70_g_se_x_16]

## 五、总结 ##

本周又是三题，由于一些细心问题，导致罚时过多，过三题排名 `626 ~ 2250`

可以看出，程序员的算法能力逐渐开始上升

下周争取不迟到，争取AK！

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/499b7b1d0c4548789eecee52af49a124.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6dedb2b6d4444e468c2bc41b28aed503.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/274523fe3fc14420ba64f9cf8cff872b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/ee0d105408794193ae3b1e3c193d14f8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/f240e9c1e9fc4025a99fb3145fbec18f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/c439ebfb131d49618dee7732982d75c9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/14f7a3930a78487b8257797e45fc8308.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/59eeb901c1c04344961d676ad573d23d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_15_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/21cd557bb2814f3b85c69a54b2011bdd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE_size_14_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a4dea92e28ba48aa9f13d7a59ef9a770.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5bCP6buE,size_14,color_FFFFFF,t_70,g_se,x_16