文章目录
- 415. 字符串相加（高精度计算、大数运算）
- 1851. 包含每个查询的最小区间⭐⭐⭐⭐⭐
- 解法1——按区间长度排序 + 离线询问 + 并查集
- 解法2——离线算法 + 优先队列
- 874. 模拟行走机器人（哈希表 + 方向数组）
- 918. 环形子数组的最大和⭐⭐⭐⭐⭐（升级版子数组的最大和）
- 分成两种情况计算，取两种情况的最大值
- 1499. 满足不等式的最大值（单调队列 | 优先队列）
- 解法1——单调队列维护窗口内的最大值
- 解法2——优先队列/堆
- 860. 柠檬水找零（简单无聊模拟题）
- 42. 接雨水（🐂好题）
- 解法1——单调栈
- 解法2——双指针
415. 字符串相加（高精度计算、大数运算）
https://leetcode.cn/problems/add-strings/description/
模拟即可。
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder ans = new StringBuilder();
for (int i = num1.length() - 1, j = num2.length() - 1, c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
if (i >= 0) c += num1.charAt(i) - '0';
if (j >= 0) c += num2.charAt(j) - '0';
ans.append(c % 10);
c /= 10;
}
return ans.reverse().toString();
}
}
更多大数计算可见：
【算法基础】1.4 高精度（模拟大数运算：整数加减乘除）
Java【大数类】整理
1851. 包含每个查询的最小区间⭐⭐⭐⭐⭐
https://leetcode.cn/problems/minimum-interval-to-include-each-query/
提示：
1 <= intervals.length <= 10^5
1 <= queries.length <= 10^5
queries[i].length == 2
1 <= lefti <= righti <= 10^7
1 <= queries[j] <= 10^7
解法1——按区间长度排序 + 离线询问 + 并查集
https://leetcode.cn/problems/minimum-interval-to-include-each-query/solutions/755131/an-qu-jian-chang-du-pai-xu-chi-xian-bing-6jzs/
换个角度，对每个区间，去回答包含这个区间的询问。
按照区间长度从小到大排序，遍历每个区间，我们可以直接回答在该区间内的尚未被回答的询问，这是因为区间是按长度从小到大排序的，这些未被回答的询问所需要找的最小区间就是当前区间。
由于一个区间内可能存在已经被回答过的询问，所以我们需要跳过这些询问，这可以用并查集来维护，当我们回答一个区间时，将区间所有元素指向其下一个元素，这样当我们用并查集查询到一个回答完毕的区间的左端点时，自然就跳到了区间的右端点的右侧。
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
// 按区间长度从小到大进行排序
Arrays.sort(intervals, (a, b) -> a[1] - a[0] - (b[1] - b[0]));
int m = queries.length;
int[][] qs = new int[m][2];
for (int i = 0; i < m; ++i) {
qs[i] = new int[]{queries[i], i};
}
Arrays.sort(qs, (a, b) -> a[0] - b[0]); // 按查询位置从小到大进行排序
// 初始化并查集
int[] p = new int[m + 1];
Arrays.setAll(p, e -> e);
int[] ans = new int[m];
Arrays.fill(ans, -1);
// 对每个区间，回答所有在 [l, r] 范围内的询问
// 由于每次回答询问之后，都将其指向了下一个询问
// 所以若 i = find(i) 符合 i < m && qs[i][0] <= r 的条件，则必然是一个在[l, r] 范围内还没有回答过的询问
for (int[] interval: intervals) {
int l = interval[0], r = interval[1]; // 取出当前区间
int len = r - l + 1;
int i = bs(qs, l); // 找到查询中第一个大于等于左端点的位置
// 回答所有询问位置在 [l, r] 范围内还没有被回答过的询问
for (i = find(i, p); i < m && qs[i][0] <= r; i = find(i + 1, p)) {
ans[qs[i][1]] = len;
p[i] = i + 1;
}
}
return ans;
}
public int bs(int[][] qs, int t) {
int l = 0, r = qs.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (qs[mid][0] < t) l = mid + 1;
else r = mid;
}
return l;
}
public int find(int x, int[] p) {
if (p[x] != x) p[x] = find(p[x], p);
return p[x];
}
}
解法2——离线算法 + 优先队列
https://leetcode.cn/problems/minimum-interval-to-include-each-query/solutions/755628/bao-han-mei-ge-cha-xun-de-zui-xiao-qu-ji-e21j/
874. 模拟行走机器人（哈希表 + 方向数组）
https://leetcode.cn/problems/walking-robot-simulation/description/
用哈希表存储障碍物位置，然后使用方向数组模拟即可。
class Solution {
public int robotSim(int[] commands, int[][] obstacles) {
int[] dx = new int[]{0, 1, 0, -1}, dy = new int[]{1, 0, -1, 0};
int ans = 0, t = 0, x = 0, y = 0;
Set<String> s = new HashSet<String>();
for (int[] obstacle: obstacles) s.add(obstacle[0] + " " + obstacle[1]);
for (int c: commands) {
if (c == -2) t = (t + 3) % 4;
else if (c == -1) t = (t + 1) % 4;
else {
for (int d = 1; d <= c; ++d) {
if (s.contains((x + dx[t]) + " " + (y + dy[t]))) break;
x += dx[t];
y += dy[t];
}
ans = Math.max(ans, x * x + y * y);
}
}
return ans;
}
}
918. 环形子数组的最大和⭐⭐⭐⭐⭐（升级版子数组的最大和）
https://leetcode.cn/problems/maximum-sum-circular-subarray/
提示：
n == nums.length
1 <= n <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
分成两种情况计算，取两种情况的最大值
第一种情况就是 普通 子数组的最大和。
第二种情况就是 前缀 + 后缀 的最大和。
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length, leftSum = nums[0], pre = nums[0], res = nums[0];
int[] leftMax = new int[n];
leftMax[0] = nums[0];
for (int i = 1; i < n; ++i) {
pre = Math.max(nums[i], pre + nums[i]);
res = Math.max(res, pre);
leftSum += nums[i]; // leftSum是前缀和
leftMax[i] = Math.max(leftMax[i - 1], leftSum);
}
int rightSum = 0; // rightSum是后缀和
for (int i = n - 1; i > 0; --i) {
rightSum += nums[i];
res = Math.max(res, rightSum + leftMax[i - 1]);
}
return res;
}
}
1499. 满足不等式的最大值（单调队列 | 优先队列）
https://leetcode.cn/problems/max-value-of-equation/
解法1——单调队列维护窗口内的最大值
从前往后枚举 j ，使用单调队列维护 yi - xi 的最大值。
class Solution {
public int findMaxValueOfEquation(int[][] points, int k) {
int n = points.length, ans = Integer.MIN_VALUE;
Deque<Integer> dq = new ArrayDeque<Integer>();
// 从前向后枚举 x 一定大于之前的 公式变成 yi + yj + xj - xi（这里 i < j）
// 所以单调队列里按 yi - xi 从大到小排序
for (int j = 0; j < n; ++j) {
// 移除 xj - xi < k 的 i
while (!dq.isEmpty() && points[j][0] - points[dq.peekFirst()][0] > k) dq.pollFirst();
// 更新答案
if (!dq.isEmpty()) {
int i = dq.peekFirst();
ans = Math.max(points[j][0] + points[j][1] - points[i][0] + points[i][1], ans);
}
// 更新单调队列
int v = points[j][1] - points[j][0];
while (!dq.isEmpty() && v >= points[dq.peekLast()][1] - points[dq.peekLast()][0]) dq.pollLast();
dq.offerLast(j);
}
return ans;
}
}
解法2——优先队列/堆
使用优先队列，队列中的元素是 int[] {x - y, x}
class Solution {
public int findMaxValueOfEquation(int[][] points, int k) {
int n = points.length, ans = Integer.MIN_VALUE;
// 堆中元素按 x - y 从小到大排序
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
for (int[] point: points) {
int x = point[0], y = point[1];
while (!pq.isEmpty() && pq.peek()[1] < x - k) pq.poll();
if (!pq.isEmpty()) ans = Math.max(ans, x + y - pq.peek()[0]);
pq.offer(new int[]{x - y, x});
}
return ans;
}
}
860. 柠檬水找零（简单无聊模拟题）
https://leetcode.cn/problems/lemonade-change/submissions/
提示：
1 <= bills.length <= 10^5
bills[i] 不是 5 就是 10 或是 20
class Solution {
public boolean lemonadeChange(int[] bills) {
int[] cnt = new int[21];
for (int bill: bills) {
cnt[bill]++;
if (bill == 10) cnt[5]--;
else if (bill == 20) {
if (cnt[10] > 0) {
cnt[10]--;
cnt[5]--;
} else cnt[5] -= 3;
}
if (cnt[5] < 0) return false;
}
return true;
}
}
42. 接雨水（🐂好题）
https://leetcode.cn/problems/trapping-rain-water/description/
解法1——单调栈
class Solution {
public int trap(int[] height) {
int n = height.length, ans = 0;
Deque<Integer> stk = new ArrayDeque();
for (int i = 0; i < n; ++i) {
// 单调递减的栈
while (!stk.isEmpty() && height[i] >= height[stk.peek()]) {
int last = stk.pop();
if (!stk.isEmpty()) {
int second = stk.pop();
ans += (Math.min(height[i], height[second]) - height[last]) * (i - second - 1);
stk.push(second);
}
}
stk.push(i);
}
return ans;
}
}
解法2——双指针
class Solution {
public int trap(int[] height) {
int n = height.length, l = 0, r = n - 1, ml = height[l], mr = height[r], ans = 0;
while (l <= r) {
if (ml < mr) {
ans += ml - height[l++];
if (l <= r) ml = Math.max(ml, height[l]);
} else {
ans += mr - height[r--];
if (r >= l) mr = Math.max(mr, height[r]);
}
}
return ans;
}
}
