欢迎大家加QQ群：623375442，可以方便群里面交流。
100435. Find Indices of Stable Mountains
有 n 座山排成一列，每座山都有一个高度。给你一个整数数组 height ，其中 height[i] 表示第 i 座山的高度，再给你一个整数 threshold 。
对于下标不为 0 的一座山，如果它左侧相邻的山的高度 严格大于 threshold ，那么我们称它是 稳定 的。我们定义下标为 0 的山 不是 稳定的。
请你返回一个数组，包含所有 稳定 山的下标，你可以以 任意 顺序返回下标数组。
测试样例：
输入：height = [1,2,3,4,5], threshold = 2
输出：[3,4]
解释：下标为 3 的山是稳定的，因为 height[2] == 3 大于 threshold == 2 。下标为 4 的山是稳定的，因为 height[3] == 4 大于 threshold == 2.
解答：按照题意暴力枚举一下位置。
class Solution {
public List<Integer> stableMountains(int[] height, int threshold) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i < height.length; ++i) {
if (height[i - 1] > threshold) {
res.add(i);
}
}
return res;
}
}100414. Find a Safe Walk Through a Grid
给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。
你开始于矩形的左上角 (0, 0) ，你的目标是矩形的右下角 (m - 1, n - 1) 。
你可以在矩形中往上下左右相邻格子移动，但前提是你的健康值始终是 正数 。
对于格子 (i, j) ，如果 grid[i][j] = 1 ，那么这个格子视为 不安全 的，会使你的健康值减少 1 。
如果你可以到达最终的格子，请你返回 true ，否则返回 false 。
注意 ，当你在最终格子的时候，你的健康值也必须为 正数 。
返回 result 。
测试样例：
输入：grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
输出：false
解释：
健康值最少为 4 才能安全到达最后的格子。
解答：利用BFS遍历一下格子，并判断一下是否可以到达当前格子。
class Solution {
private static final int[] moves = {1,0,-1,0,1};
public boolean findSafeWalk(List<List<Integer>> _grid, int health) {
int[][] grid = new int[_grid.size()][];
int offset = 0;
for (List<Integer> row : _grid) {
grid[offset] = new int[row.size()];
int rowOffset = 0;
for (int n : row) {
grid[offset][rowOffset++] = n;
}
++offset;
}
if (health == 1 && grid[0][0] == 1) {
return false;
}
int[][] dp = new int[grid.length][grid[0].length];
dp[0][0] = health - grid[0][0];
TreeSet<int[]> set = new TreeSet<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (dp[o1[0]][o1[1]] != dp[o2[0]][o2[1]]) {
return Integer.compare(dp[o2[0]][o2[1]], dp[o1[0]][o1[1]]);
}
for (int i = 0; i < 2; ++i) {
if (o1[i] != o2[i]) {
return Integer.compare(o1[i], o2[i]);
}
}
return 0;
}
});
set.add(new int[]{0, 0});
while (!set.isEmpty()) {
int[] tmp = set.pollFirst();
if (tmp[0] == grid.length - 1 && tmp[1] == grid[0].length - 1) {
return true;
}
int oldHealth = dp[tmp[0]][tmp[1]];
for (int i = 0; i < 4; ++i) {
int xt = tmp[0] + moves[i], yt = tmp[1] + moves[i + 1];
if (xt >= 0 && xt < grid.length && yt >= 0 && yt < grid[0].length) {
int nextHealth = oldHealth - grid[xt][yt];
if (nextHealth > dp[xt][yt]) {
int[] key = {xt, yt};
set.remove(key);
dp[xt][yt] = nextHealth;
set.add(key);
}
}
}
}
return false;
}
}100429. Find the Maximum Sequence Value of Array
给你一个整数数组 nums 和一个 正 整数 k 。
定义长度为 2 * x 的序列 seq 的 值 为：
- (seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1]).
请你求出 nums 中所有长度为 2 * k 的 子序列 的 最大值 。
测试样例：
输入：nums = [2,6,7], k = 1
输出：6
解释：子序列 [2, 7] 的值最大，为 2 XOR 7 = 5 。
解答：这题有2个非常重要的提示：2 <= nums.length <= 400，1 <= nums[i] < 2^7。数据范围很小，基本可以暴力。我们利用动态规划计算一下从当前位置到最后可以获取的所有k个数组的可能。然后再从头到尾遍历，计算所有XOR的可能性。
class Solution {
private static final int max = 128;
public int maxValue(int[] nums, int k) {
boolean[][] dp = new boolean[nums.length][max];
{
boolean[][] isMet = new boolean[max][k + 1];
List<int[]> valid = new ArrayList<>();
valid.add(new int[]{0, 0});
isMet[0][0] = true;
for (int i = nums.length - 1; i >= 0; --i) {
List<int[]> nextValid = new ArrayList<>();
for (int[] tmp : valid) {
nextValid.add(tmp);
// 利用动态规划，记录一下计算各个长度数组OR的结果
if (tmp[1] + 1 <= k && !isMet[tmp[0] | nums[i]][tmp[1] + 1]) {
isMet[tmp[0] | nums[i]][tmp[1] + 1] = true;
nextValid.add(new int[]{tmp[0] | nums[i], tmp[1] + 1});
}
// 记录当前位置，所有可能的k长度的OR结果
if (tmp[1] + 1 == k) {
dp[i][tmp[0] | nums[i]] = true;
}
if (tmp[1] == k) {
dp[i][tmp[0]] = true;
}
}
valid = nextValid;
}
}
int res = 0;
{
boolean[] isLeftMet = new boolean[max];
boolean[][] isMet = new boolean[max][k + 1];
List<int[]> valid = new ArrayList<>();
valid.add(new int[]{0, 0});
isMet[0][0] = true;
for (int i = 0; i < nums.length; ++i) {
List<int[]> nextValid = new ArrayList<>();
for (int[] tmp : valid) {
nextValid.add(tmp);
// 和上面类似的逻辑，计算各个长度数组OR的结果
if (tmp[1] + 1 <= k && !isMet[tmp[0] | nums[i]][tmp[1] + 1]) {
isMet[tmp[0] | nums[i]][tmp[1] + 1] = true;
nextValid.add(new int[]{tmp[0] | nums[i], tmp[1] + 1});
}
// 为k的时候，查看一下最大XOR结果
if (tmp[1] + 1 == k && !isLeftMet[tmp[0] | nums[i]] && i + 1 < nums.length) {
int orResult = tmp[0] | nums[i];
isLeftMet[orResult] = true;
for (int j = 1; j < max; ++j) {
if (dp[i + 1][j]) {
res = Math.max(res, orResult ^ j);
}
}
}
}
valid = nextValid;
}
}
return res;
}
}100426. Length of the Longest Increasing Path
给你一个长度为 n 的二维整数数组 coordinates 和一个整数 k ，其中 0 <= k < n 。
coordinates[i] = [xi, yi] 表示二维平面里一个点 (xi, yi) 。
如果一个点序列 (x1, y1), (x2, y2), (x3, y3), ..., (xm, ym) 满足以下条件，那么我们称它是一个长度为 m 的 上升序列 ：
- 对于所有满足 1 <= i < m 的 i 都有 xi < xi + 1 且 yi < yi + 1 。
- 对于所有 1 <= i <= m 的 i 对应的点 (xi, yi) 都在给定的坐标数组里。
请你返回包含坐标 coordinates[k] 的 最长上升路径 的长度。
测试样例：
输入：coordinates = [[3,1],[2,2],[4,1],[0,0],[5,3]], k = 1
输出：3
解释：
(0, 0) ，(2, 2) ，(5, 3) 是包含坐标 (2, 2) 的最长上升路径。
解答：这题和354. Russian Doll Envelopes做法类似，使用最长递增子序列的想法计算。唯一需要注意的是，k必须包含。所以当遍历到k的时候，有一些特殊截断操作。
class Solution {
public int maxPathLength(int[][] coordinates, int k) {
Integer[] sort = new Integer[coordinates.length];
for (int i = 0; i < coordinates.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (coordinates[a][0] == coordinates[b][0]
? Integer.compare(coordinates[b][1], coordinates[a][1]) : Integer.compare(coordinates[a][0], coordinates[b][0])));
int[] dp = new int[coordinates.length];
int initial = -1, p = 0;
for (int i : sort) {
if (i == k) {
// 当为k的时候，截断数组，并记录一下k出现的位置。
initial = binarySearchPos(dp, p, coordinates[i][1]);
dp = new int[coordinates.length];
dp[0] = coordinates[i][1];
p = 1;
} else {
int tmp = binarySearchPos(dp, p, coordinates[i][1]);
if (initial != -1) {
if (tmp != 0) {
dp[tmp] = coordinates[i][1];
}
} else {
dp[tmp] = coordinates[i][1];
}
if (tmp == p) {
++p;
}
}
}
return initial + p;
}
private int binarySearchPos(int[] dp, int pos, int num) {
if (pos == 0 || dp[pos - 1] < num) {
return pos;
}
int st = 0, ed = pos;
while (st < ed) {
int mid = (st + ed) / 2;
if (dp[mid] < num) {
st = mid + 1;
} else {
ed = mid;
}
}
return st;
}
}