【LeetCode每日一题】2024年9月第二周（下）

 2024.9.13  困难  难度评分1917

链接：2398. 预算内的最多机器人数目

（1）题目描述：

（2）示例

（3）分析

        翻译一下题目：要求我们在给定的 chargeTimes 和 runningCosts 数组以及发 budget的限制下，找到机器人运行的最长连续子数组，使得所有机器人的总运行成本不超过预算。

         那么思路还是比较明确的，我们用两个标识符left，right限定住既定的数据范围，然后依据：max(chargeTimes[l:r]) + (r - l + 1) * sum(runningCosts[l:r])<=budget，来进行取舍。下面是大致代码思路。

一开始的思路，可以过40%的测试用例，但很明显，节点选取和处理有错误

    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int sum=0; int max=0; int left=0; int temp=0; int len=chargeTimes.length;
        //定义标识符
        for (int right = 0; right < len; right++) {
            //从左向右遍历，判断是否符合
            if(chargeTimes[right]>max)  max=chargeTimes[right];//更新最大值
                    sum+=runningCosts[right];
            if(max+sum*(right-left+1)>budget){
                temp =Math.max(temp,right-left+1);//temp循环更新，确定最大值
            }
            else { left = right;max=0;sum=0; //对sum、max进行复原==》应当是回归到舍去值之后的状态}
        }
        return temp;
    }

（4）代码

方法一：滑动窗口？

为什么超预算的时候，必须舍弃掉left？因为题目要求他必须连续，断开时已经得到一个temp（结果），是前面考虑后得到的结果，接下来需要判断的就是：后面可能出现的连续情况

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        long sum=0;
        long max=0;
        int left=0;
        long temp=0;
        long len=chargeTimes.length;
        for (int right = 0; right < len; right++) {
            max=Math.max(max,chargeTimes[right]);
            sum+=runningCosts[right];
            //判断超预算了,此处必须断开，因为必须连续，所以去掉头部，判断接下来的可能的情况
            while(max+ sum *(right-left+1)>budget){
                sum-=runningCosts[left];
                left++;

                max = 0;
                for (int i = left; i <= right; i++) {
                    //此处必须重新计算，因为前面已经去掉头部了
                    max=Math.max(max,chargeTimes[i]);
                }
            }
            temp=Math.max(temp,right-left+1);
        }
        return (int) temp;
    }
}

方法二：使用队列。

维护最长连续子数组，入和出皆和一个队列的入队出队相似，于是就变为了队列的基本操作。代码如下：

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int ans = 0; // 用于存储符合条件的最长子数组长度
        int left = 0; // 滑动窗口的左边界
        long sum = 0; // 当前窗口内的 runningCosts 总和
        Deque<Integer> q = new ArrayDeque<>(); // 双端队列，用来维护当前窗口的最大 chargeTimes 值的索引

        // 遍历 chargeTimes 数组，right 表示滑动窗口的右边界
        for (int right = 0; right < chargeTimes.length; right++) {
            // 1. 处理入队操作，保持队列中的值递减，保证队头为当前窗口内的最大 chargeTimes
            while (!q.isEmpty() && chargeTimes[right] >= chargeTimes[q.peekLast()]) {
                q.pollLast(); // 弹出队尾元素，确保队列内维持递减顺序
            }
            q.addLast(right); // 将当前元素索引加入队列尾部
            
            // 更新窗口内 runningCosts 的总和
            sum += runningCosts[right];

            // 2. 如果当前窗口的总成本超出预算，则需要调整窗口左边界，缩小窗口
            while (!q.isEmpty() && chargeTimes[q.peekFirst()] + (right - left + 1) * sum > budget) {
                // 如果队头的元素索引已经超出窗口左边界，移除队头
                if (q.peekFirst() == left) {
                    q.pollFirst(); // 弹出队头，更新最大 chargeTimes
                }
                // 调整窗口，减少窗口的总 runningCosts，左边界右移
                sum -= runningCosts[left];
                left++;
            }

            // 3. 更新答案，当前窗口大小为 (right - left + 1)
            ans = Math.max(ans, right - left + 1);
        }

        // 返回符合条件的最大窗口大小，即最大机器人数量
        return ans;
    }
}

（5）碎碎念

方法一，一开始直接没看范围，直接给我超了！看到测试用例的那一刻，确实有点无语。

 2024.9.14 中等  难度评分1348

链接：2390. 从字符串中移除星号

（1）题目描述：

（2）示例

（3）分析

        emm，实际上感觉，类似简单题。

        题目要求我们对一个字符串进行变换，就是删除星号和它左边的字符。我们观察只要返回值即可，没顺序要求。所以我们直接把他转换为一个字符的集合或数组，然后从左往右直接替换即可。遇到*必然是最后一位，直接去除即可，其余添加进去。

（4）代码

class Solution {
    public String removeStars(String s) {
        StringBuilder st = new StringBuilder();
        //StringBuilder，方便调用函数进行操作
        for (char c : s.toCharArray()) {
        //把他转换为一个字符的集合或数组，从左往右直接替换。
            if (c == '*') {
        // 遇到*必然是最后一位，直接去除即可，其余添加进去
                st.deleteCharAt(st.length() - 1);
            } else {
                st.append(c);
            }
        }
        return st.toString();
    }
}

（5）碎碎念

还行，没有花太长时间。

 2024.9.15 简单  难度评分1230

链接：2848. 与车相交的点

（1）题目描述：

（2）示例

（3）分析

        这题目，一开始还没理解啥意思。结果就是：所有数组内，包含几个不同的数的问题。 有不同，那直接：hashset，自带去重属性，所以直接调用。或者每个独自计算，也可以。

（4）代码

方法一：hashset，遍历后直接输出。

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        HashSet j=new HashSet(); //hashset，自带去重属性，所以直接调用
        for(List<Integer> num:nums){
            for (int i=num.get(0);i<=num.get(1);i++){
                j.add(i);
            }
        }
        return j.size();
    }
}

方法二：差分

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        int maxEnd = 0; // 用于存储所有区间的最大结束位置

        // 遍历每个区间，找到最大结束位置
        for (List<Integer> p : nums) {
            maxEnd = Math.max(maxEnd, p.get(1)); // p.get(1) 是当前区间的结束位置
        }

        // 差分数组，长度为最大结束位置加 2。这样确保我们可以处理到 [end + 1] 的情况
        int[] diff = new int[maxEnd + 2];

        // 根据每个区间来构建差分数组
        for (List<Integer> interval : nums) {
            // interval.get(0) 是区间的起始位置，在起始位置处 +1
            diff[interval.get(0)]++;
            // interval.get(1) 是区间的结束位置，结束位置的下一位 -1
            diff[interval.get(1) + 1]--;
        }

        int ans = 0; // 用于存储覆盖的点数
        int s = 0;   // 维护当前累积的区间覆盖数

        // 遍历差分数组，通过前缀和计算每个点的覆盖情况
        for (int d : diff) {
            s += d; // 更新当前点的覆盖数量
            if (s > 0) { // 如果当前点被至少一个区间覆盖
                ans++; // 统计覆盖的点数
            }
        }

        return ans; // 返回被至少一个区间覆盖的点的总数
    }
}

（5）碎碎念

简单题，所以，多看了一种思路。完~