6470. Neither Minimum nor Maximum
给你一个整数数组 nums ，数组由 不同正整数 组成，请你找出并返回数组中 任一 既不是 最小值 也不是 最大值 的数字，如果不存在这样的数字，返回 -1 。
返回所选整数。
测试样例：
输入：nums = [3,2,1,4]
输出：2
解释：
在这个示例中，最小值是 1 ，最大值是 4 。因此，2 或 3 都是有效答案。
解答：两次遍历。第一次寻找最大值和最小值，第二次寻找第一个同时不是最小也不是最大的值。数据范围很小，直接暴力遍历。
class Solution {
public int findNonMinOrMax(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int n : nums) {
min = Math.min(min, n);
max = Math.max(max, n);
}
for (int n : nums) {
if (n != min && n != max) {
return n;
}
}
return -1;
}
}6465. Lexicographically Smallest String After Substring Operation
给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：
- 选则 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。
返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。
子字符串 是字符串中的一个连续字符序列。
现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。
测试样例：
输入：s = "cbabc"
输出："baabc"
解释：
我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 可以证明最终得到的字符串是字典序最小的。
解答：这道题目需要一点思考。它需要寻找第一个非a的元素，然后连续递减1，知道碰到下一个a元素。有一点需要注意，因为题目要求恰好一次操作。如果这个字符串全部有a构成，那么最后一个字母需要变成z。
class Solution {
public String smallestString(String s) {
boolean isUsed = false;
boolean isPerform = false;
StringBuilder res = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
if (isPerform) {
if (s.charAt(i) == 'a') {
isPerform = false;
res.append('a');
} else {
res.append((char)(s.charAt(i) - 1));
}
} else {
if (isUsed) {
res.append(s.charAt(i));
} else {
if (s.charAt(i) == 'a') {
res.append('a');
} else {
isPerform = true;
isUsed = true;
res.append((char)(s.charAt(i) - 1));
}
}
}
}
return isUsed ? res.toString() : (s.substring(0, s.length() - 1) + 'z');
}
}6449. Collecting Chocolates
给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。
在一步操作中，你可以用成本 x 执行下述行为：
- 同时对于所有下标 0 <= i < n - 1 进行以下操作， 将下标 i 处的巧克力的类型更改为下标 (i + 1) 处的巧克力对应的类型。如果 i == n - 1 ，则该巧克力的类型将会变更为下标 0 处巧克力对应的类型。
假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。
测试样例
输入：nums = [1,2,3], x = 4
输出：6
解释：
我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。
解答：这道题目有点难度，很容易被卡常。其实最多进行nums.length次数操作。所以我们用一个数组记录如果进行i次操作，能够达到的最小成本。然后利用优先队列记录，在i次操作过程中，某一个type能到获得最小成本。最后寻找所有操作可能中，最小值。
class Solution {
public long minCost(int[] nums, long x) {
long[] mem = new long[nums.length];
for (int i = 0; i < nums.length; ++i) {
mem[i] = x * i;
}
for (int i = 0; i < nums.length; ++i) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int j = 0; j < nums.length; ++j) {
queue.add(nums[(i + j) % nums.length]);
mem[j] += queue.peek();
}
}
long min = Long.MAX_VALUE;
for (long m : mem) {
min = Math.min(min, m);
}
return min;
}
}6473. Maximum Sum Queries
给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。
对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。
返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。
测试样例
输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
输出：[9,9,9]
解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。
解答：又是二维数组的题目。我们首先把nums1从大到小排序，然后在把queries按照queries[0]的大小从大到小排序。这时候我们遍历queries，并且维护一个nums1的迭代器，确保只有nums1[p] > queries[i][0]的记录可以加入比较。
但是这个时候问题又来了，我们还需要保证nums2[j] >= queries[i][1]。关于这个方面，我没想到什么好的办法。我能想到的是利用线段树，记录nums1的条件能满足的时候，所有能加入的nums2值。然后利用线段数，查询当前满足条件的最大和。幸好这道题目对算法复杂度的要求不是很高，这样也能AC。
class Solution {
private class SegmentTree {
int[] tree;
int n;
public SegmentTree(int len) {
if (len > 0) {
n = len;
tree = new int[n * 2];
for (int i = 0; i < tree.length; ++i) {
tree[i] = -1;
}
}
}
void update(int pos, int val) {
pos += n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
// parent is updated after child is updated
tree[pos / 2] = Math.max(tree[left], tree[right]);
pos /= 2;
}
}
public int maxRange(int l, int r) {
l += n;
r += n;
int max = -1;
while (l <= r) {
if ((l % 2) == 1) {
max = Math.max(max, tree[l]);
l++;
}
if ((r % 2) == 0) {
max = Math.max(max, tree[r]);
r--;
}
l /= 2;
r /= 2;
}
return max;
}
}
public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
TreeMap<Integer, Integer> pos2 = findNums2Pos(nums2);
int len = nums1.length;
Integer[] nums1Sort = new Integer[len];
for (int i = 0; i < len; ++i) {
nums1Sort[i] = i;
}
Arrays.sort(nums1Sort, (a, b) -> (nums1[b] - nums1[a]));
Integer[] querySort = new Integer[queries.length];
for (int i = 0; i < querySort.length; ++i) {
querySort[i] = i;
}
Arrays.sort(querySort, (a, b) -> (queries[b][0] - queries[a][0]));
SegmentTree tree = new SegmentTree(pos2.size());
int[] res = new int[queries.length];
int p = 0;
for (int i : querySort) {
int[] q = queries[i];
while (p < len && nums1[nums1Sort[p]] >= q[0]) {
int n2 = nums2[nums1Sort[p]];
int add = nums1[nums1Sort[p]] + n2;
int point = pos2.get(n2);
int oldSum = tree.maxRange(point, point);
if (add > oldSum) {
tree.update(point, add);
}
++p;
}
Map.Entry<Integer, Integer> high = pos2.ceilingEntry(q[1]);
if (high == null) {
res[i] = -1;
} else {
res[i] = tree.maxRange(high.getValue(), pos2.size() - 1);
}
}
return res;
}
private TreeMap<Integer, Integer> findNums2Pos(int[] nums) {
int[] dup = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
dup[i] = nums[i];
}
Arrays.sort(dup);
int offset = 0;
TreeMap<Integer, Integer> res = new TreeMap<>();
for (int n : dup) {
if (!res.containsKey(n)) {
res.put(n, offset++);
}
}
return res;
}
}这周题目，还是挺有难度的。。。