【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）碎碎念
简单题，所以，多看了一种思路。完~