100270. Score of a String
给你一个字符串 s 。一个字符串的 分数 定义为相邻字符 ASCII 码差值绝对值的和。
请你返回 s 的 分数 。
测试样例：
输入：s = "hello"
输出：13
解释：s 中字符的 ASCII 码分别为：'h' = 104 ，'e' = 101 ，'l' = 108 ，'o' = 111 。所以 s 的分数为 |104 - 101| + |101 - 108| + |108 - 108| + |108 - 111| = 3 + 7 + 0 + 3 = 13 。
解答：根据题意计算ASCII的diff，累和。
class Solution {
public int scoreOfString(String s) {
int res = 0;
for (int i = 1; i < s.length(); ++i) {
res += Math.abs(s.charAt(i) - s.charAt(i - 1));
}
return res;
}
}100280. Minimum Rectangles to Cover Points
给你一个二维整数数组 point ，其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。
每个矩形的左下角在某个点 (x1, 0) 处，且右上角在某个点 (x2, y2) 处，其中 x1 <= x2 且 y2 >= 0 ，同时对于每个矩形都 必须 满足 x2 - x1 <= w 。
如果一个点在矩形内或者在边上，我们说这个点被矩形覆盖了。
请你在确保每个点都 至少 被一个矩形覆盖的前提下，最少 需要多少个矩形。
注意：一个点可以被多个矩形覆盖。
测试样例：
输入：points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出：2
解释：一个矩形的左下角在 (1, 0) ，右上角在 (2, 8) 。一个矩形的左下角在 (3, 0) ，右上角在 (4, 8) 。
解答：排序之后，利用双指针+贪婪可以完成计算。
class Solution {
public int minRectanglesToCoverPoints(int[][] points, int w) {
Arrays.sort(points, (a, b) -> (Integer.compare(a[0], b[0])));
int res = 1, first = points[0][0];
for (int[] p : points) {
if (p[0] - first > w) {
++res;
first = p[0];
}
}
return res;
}
}100279. Minimum Time to Visit Disappearing Nodes
给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。
同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。
注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。
请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。
测试样例：
输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]
输出：[0,-1,4]
解释：我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。
- 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
- 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。但当我们到达的时候，它已经消失了，所以我们无法到达它。
- 对于节点 2 ，我们需要至少 4 单位时间，通过 edges[2] 到达。
解答：有一点点变形的BFS。区别只在于节点如果消失，那么就不能进入BFS计算。
class Solution {
public int[] minimumTime(int n, int[][] _edges, int[] disappear) {
List<int[]>[] edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(new int[]{e[1], e[2]});
edges[e[1]].add(new int[]{e[0], e[2]});
}
int[] res = new int[n];
Arrays.fill(res, Integer.MAX_VALUE);
TreeSet<Integer> set = new TreeSet<>((a, b) -> (res[a] != res[b] ? Integer.compare(res[a], res[b]) : Integer.compare(a, b)));
res[0] = 0;
set.add(0);
while (!set.isEmpty()) {
int f = set.pollFirst();
for (int[] e : edges[f]) {
if (res[f] + e[1] < res[e[0]] && res[f] + e[1] < disappear[e[0]]) {
set.remove(e[0]);
res[e[0]] = res[f] + e[1];
set.add(e[0]);
}
}
}
for (int i = 0; i < n; ++i) {
if (res[i] == Integer.MAX_VALUE) {
res[i] = -1;
}
}
return res;
}
}100273. Find the Number of Subarrays Where Boundary Elements Are Maximum
给你一个 正 整数数组 nums 。
请你求出 nums 中有多少个子数组，满足子数组中 第一个 和 最后一个 元素都是这个子数组中的 最大 值。
测试样例：
输入：nums = [1,4,3,3,2]
输出：6
解释：总共有 6 个子数组满足第一个元素和最后一个元素都是子数组中的最大值：
- 子数组 [1,4,3,3,2] ，最大元素为 1 ，第一个和最后一个元素都是 1 。
- 子数组 [1,4,3,3,2] ，最大元素为 4 ，第一个和最后一个元素都是 4 。
- 子数组 [1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
- 子数组 [1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
- 子数组 [1,4,3,3,2] ，最大元素为 2 ，第一个和最后一个元素都是 2 。
- 子数组 [1,4,3,3,2] ，最大元素为 3 ，第一个和最后一个元素都是 3 。
所以我们返回 6 。
解答：第一个 和 最后一个 元素都是这个子数组中的 最大 值。这个条件，我们可以将每个数字的出现位置利用TreeMap记录下来。然后通过栈可以发现第一个比当前数字大的数字。最后利用TreeMap的特性，就能寻找到可以匹配上的位置，累和。
class Solution {
public long numberOfSubarrays(int[] nums) {
int len = nums.length;
Stack<Integer> stack = new Stack<>();
int[] firstLarge = new int[len];
Arrays.fill(firstLarge, -1);
for (int i = len - 1; i >= 0; --i) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
firstLarge[stack.pop()] = i;
}
stack.push(i);
}
HashMap<Integer, TreeMap<Integer, Integer>> numPosMem = new HashMap<>();
long res = 0;
for (int i = 0; i < nums.length; ++i) {
if (!numPosMem.containsKey(nums[i])) {
numPosMem.put(nums[i], new TreeMap<>());
numPosMem.get(nums[i]).put(i, 0);
res += 1;
} else {
TreeMap<Integer, Integer> tmp = numPosMem.get(nums[i]);
tmp.put(i, tmp.size());
Map.Entry<Integer, Integer> higher = tmp.higherEntry(firstLarge[i]);
res += tmp.size() - higher.getValue();
}
}
return res;
}
}