100264. Longest Strictly Increasing or Strictly Decreasing Subarray
给你一个整数数组 nums 。
返回数组 nums 中 严格递增 或 严格递减 的最长非空子数组的长度。
测试样例：
输入：nums = [1,4,3,3,2]
输出：2
解释：nums 中严格递增的子数组有[1]、[2]、[3]、[3]、[4] 以及 [1,4] 。nums 中严格递减的子数组有[1]、[2]、[3]、[3]、[4]、[3,2] 以及 [4,3] 。因此，返回 2 。
解答：按照题意计算，计算最大递增或者递减前缀。
class Solution {
public int longestMonotonicSubarray(int[] nums) {
int pre = 1, res = 1;
for (int i = 1; i < nums.length; ++i) {
if (nums[i] > nums[i - 1]) {
if (i == 1 || nums[i - 1] > nums[i - 2]) {
++pre;
} else {
pre = 2;
}
} else if (nums[i] < nums[i - 1]) {
if (i == 1 || nums[i - 1] < nums[i - 2]) {
++pre;
} else {
pre = 2;
}
} else {
pre = 1;
}
res = Math.max(res, pre);
}
return res;
}
}100242. Lexicographically Smallest String After Operations With Constraint
给你一个字符串 s 和一个整数 k 。
定义函数 distance(s1, s2) ，用于衡量两个长度为 n 的字符串 s1 和 s2 之间的距离，即：
- 字符 'a' 到 'z' 按 循环 顺序排列，对于区间 [0, n - 1] 中的 i ，计算所有「 s1[i] 和 s2[i] 之间 最小距离」的 和 。
例如，distance("ab", "cd") == 4 ，且 distance("a", "z") == 1 。
你可以对字符串 s 执行 任意次 操作。在每次操作中，可以将 s 中的一个字母 改变 为 任意 其他小写英文字母。
返回一个字符串，表示在执行一些操作后你可以得到的 字典序最小 的字符串 t ，且满足 distance(s, t) <= k 。
测试样例：
输入：s = "zbbz", k = 3
输出："aaaz"
解释：在这个例子中，可以执行以下操作：
- 将 s[0] 改为 'a' ，s 变为 "abbz" 。
- 将 s[1] 改为 'a' ，s 变为 "aabz" 。
- 将 s[2] 改为 'a' ，s 变为 "aaaz" 。
"zbbz" 和 "aaaz" 之间的距离等于 k = 3 。可以证明 "aaaz" 是在任意次操作后能够得到的字典序最小的字符串。因此，答案是 "aaaz" 。
解答：可以利用贪婪，越前面的字符串越能获取更过的操作次数，来尽量减少字符序列。
class Solution {
public String getSmallestString(String s, int k) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
char best = s.charAt(i);
for (char c = 'a'; c <= 'z'; ++c) {
int dis = Math.min(Math.abs(c - s.charAt(i)), 26 - Math.abs(c - s.charAt(i)));
if (dis <= k && c < best) {
best = c;
}
}
k -= Math.min(Math.abs(best - s.charAt(i)), 26 - Math.abs(best - s.charAt(i)));
sb.append(best);
}
return sb.toString();
}
}100277. Minimum Operations to Make Median of Array Equal to K
给你一个整数数组 nums 和一个 非负 整数 k 。
一次操作中，你可以选择任一下标 i ，然后将 nums[i] 加 1 或者减 1 。
请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。
一个数组的 中位数 指的是数组按 非递减 顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。
测试样例：
输入：nums = [2,5,6,8,5], k = 4
输出：2
解释：我们将 nums[1] 和 nums[4] 减 1 得到 [2, 4, 6, 8, 4] 。现在数组的中位数等于 k 。所以答案为 2 。
解答：首先记录数字在k这个分割数的情况下的统计情况，即小于，大于和等于k的出现次数。如果小于的数太多，就取最大的几个数变成k。如果大于的数字太多，就把最大的几个数下降成k。
class Solution {
public long minOperationsToMakeMedianK(int[] nums, int k) {
int less = 0, equ = 0, more = 0;
for (int n : nums) {
if (n < k) {
++less;
} else if (n == k) {
++equ;
} else {
++more;
}
}
if (less <= nums.length / 2 && equ > 0 && less + equ > nums.length / 2) {
return 0;
}
if (less > nums.length / 2) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
long remove = less - nums.length / 2;
for (int n : nums) {
if (n < k) {
queue.add(n);
}
if (queue.size() > remove) {
queue.poll();
}
}
long sum = 0;
for (int n : queue) {
sum += n;
}
return remove * k - sum;
} else {
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (b.compareTo(a)));
long remove = nums.length / 2 + 1 - less - equ;
for (int n : nums) {
if (n > k) {
queue.add(n);
}
if (queue.size() > remove) {
queue.poll();
}
}
long sum = 0;
for (int n : queue) {
sum += n;
}
return sum - remove * k;
}
}
}100244. Minimum Cost Walk in Weighted Graph
给你一个 n 个节点的带权无向图，节点编号为 0 到 n - 1 。
给你一个整数 n 和一个数组 edges ，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权值为 wi 的无向边。
在图中，一趟旅途包含一系列节点和边。旅途开始和结束点都是图中的节点，且图中存在连接旅途中相邻节点的边。注意，一趟旅途可能访问同一条边或者同一个节点多次。
如果旅途开始于节点 u ，结束于节点 v ，我们定义这一趟旅途的 代价 是经过的边权按位与 AND 的结果。换句话说，如果经过的边对应的边权为 w0, w1, w2, ..., wk ，那么代价为w0 & w1 & w2 & ... & wk ，其中 & 表示按位与 AND 操作。
给你一个二维数组 query ，其中 query[i] = [si, ti] 。对于每一个查询，你需要找出从节点开始 si ，在节点 ti 处结束的旅途的最小代价。如果不存在这样的旅途，答案为 -1 。
返回数组 answer ，其中 answer[i] 表示对于查询 i 的 最小 旅途代价。
测试样例：
输入：n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
输出：[1,-1]
解释：第一个查询想要得到代价为 1 的旅途，我们依次访问：0->1（边权为 7 ）1->2 （边权为 1 ）2->1（边权为 1 ）1->3 （边权为 7 ）。第二个查询中，无法从节点 3 到节点 4 ，所以答案为 -1 。
解答：因为同一个节点和边在旅途中可以重复经过，又因为是与计算，那么两点间能经过的边越多越好（除非source == target，这种情况下就是无脑0）。这样，我们利用并查集，查看那些点可以放在一个子图中。如果query的点在子图内，就是无脑遍历所有子图内的边。否则就是-1。
class Solution {
class DSU{
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
public int[] minimumCost(int n, int[][] edges, int[][] query) {
DSU uf = new DSU(n);
for (int[] e : edges) {
uf.union(e[0], e[1]);
}
int[] allAnd = new int[n];
Arrays.fill(allAnd, Integer.MAX_VALUE);
for (int[] e : edges) {
allAnd[uf.find(e[0])] &= e[2];
}
int[] res = new int[query.length];
for (int i = 0; i < query.length; ++i) {
if (query[i][0] == query[i][1]) {
res[i] = 0;
} else if (uf.find(query[i][0]) != uf.find(query[i][1])) {
res[i] = -1;
} else {
res[i] = allAnd[uf.find(query[i][0])];
}
}
return res;
}
}