Leetcode - 139双周赛

目录
一，3285. 找到稳固山的下标
二，3286. 穿越网格图的安全路径
三，3287. 求出数组中最大序列值
四，3288. 最长上升路径的长度

---

一，3285. 找到稳固山的下标

本题就是找[0， n-2]中，height 小于 threshold 的全部下标，直接枚举，代码如下：

1. class Solution {
2.     public List<Integer> stableMountains(int[] height, int threshold) {
3.         List<Integer> ans = new ArrayList<>();
4.         for(int i=0; i<height.length-1; i++){
5.             if(height[i] > threshold)
6.                 ans.add(i+1);
7.         }
8.         return ans;
9.     }
10. }

复制代码

二，3286. 穿越网格图的安全路径

本题就是一道求从起点到尽头的最短边权，是一道经典的djstra题目，只不外这里是利用（x，y）这样的坐标来表现当前位置，代码如下：

1. class Solution {
2.     int[][] dirct = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
3.     public boolean findSafeWalk(List<List<Integer>> grid, int health) {
4.         int m = grid.size(), n = grid.get(0).size();
5.         int[][] dis = new int[m][n];//(0,0)->(i,j)的安全路线
6.         for(int i=0; i<m; i++) Arrays.fill(dis[i], Integer.MAX_VALUE/2);
7.         PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->x[0]-y[0]);
8.         que.add(new int[]{grid.get(0).get(0), 0, 0});
9.         dis[0][0] = grid.get(0).get(0);
10.         while(!que.isEmpty()){
11.             int[] t = que.poll();
12.             if(t[0] != dis[t[1]][t[2]]) continue;
13.             for(int[] d : dirct){
14.                 int x = t[1] + d[0], y = t[2] + d[1];
15.                 if(x>=0 && x<m && y>=0 && y<n){
16.                     if(dis[t[1]][t[2]] + grid.get(x).get(y) < dis[x][y]){
17.                         dis[x][y] = dis[t[1]][t[2]] + grid.get(x).get(y);
18.                         que.add(new int[]{dis[x][y], x, y});
19.                     }
20.                 }
21.             }
22.         }
23.         return dis[m-1][n-1] < health;
24.     }
25. }

复制代码

但是题目中说，边权仅为0 / 1，所以我们可以利用双端队列来模拟最小堆，可以节省一些时间，代码如下：

1. class Solution {
2.     int[][] dirct = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
3.     public boolean findSafeWalk(List<List<Integer>> grid, int health) {
4.         ArrayDeque<int[]> que = new ArrayDeque<>();
5.         que.add(new int[]{0, 0});
6.         int m = grid.size(), n = grid.get(0).size();
7.         int[][] dis = new int[m][n];//(0,0)->(i,j)的安全路线
8.         for(int i=0; i<m; i++) Arrays.fill(dis[i], Integer.MAX_VALUE/2);
9.         dis[0][0] = grid.get(0).get(0);
10.         while(!que.isEmpty()){
11.             int[] t = que.poll();
12.             for(int[] d : dirct){
13.                 int x = t[0] + d[0], y = t[1] + d[1];
14.                 if(x>=0 && x<m && y>=0 && y<n){
15.                     if(dis[t[0]][t[1]] + grid.get(x).get(y) < dis[x][y]){
16.                         dis[x][y] = dis[t[0]][t[1]] + grid.get(x).get(y);
17.                         if(grid.get(x).get(y) == 0)
18.                             que.addFirst(new int[]{x, y});
19.                         else
20.                             que.addLast(new int[]{x, y});
21.                     }
22.                 }
23.             }
24.         }
25.         return dis[m-1][n-1] < health;
26.     }
27. }

复制代码

三，3287. 求出数组中最大序列值

由于本题是数据范围较小，所以我们可以暴力图出左半边和右半边的全部子序枚举行或运算得到的值，再通过枚举中间位置来求出 x ^ y 的最大值。
这里的紧张题目就是如何计算出左半边和右半边能得到的全部或值，我们可以界说一个f[j][x]：表现能否从前 i 个数中选择 j 个数，且或值恰好为 x。

• 不选 v = nums，f[i+1][j][x] = f[j-1][x]
  
• 选 v = nums，f[i+1][j][x|v] = f[i+1][j][x|v] or f[j-1][x]
  

代码如下：

1. class Solution {
2.     public int maxValue(int[] nums, int k) {
3.         int n = nums.length;
4.         int MX = 1<<7;
5.         boolean[][][] pre = new boolean[n+1][k+1][1<<7];
6.         for(int i=0; i<=n; i++) pre[i][0][0] = true;
7.         for (int i=0; i<n; i++){
8.             int v = nums[i];
9.             for (int j=1; j<=k; j++){
10.                 for (int x=0; x<MX; x++){   
11.                     pre[i+1][j][x] |= pre[i][j][x];
12.                     pre[i+1][j][x|v] |= pre[i][j-1][x];
13.                 }
14.             }
15.         }
16.         boolean[][][] suf = new boolean[n+1][k+1][1<<7];
17.         for(int i=0; i<=n; i++) suf[i][0][0] = true;
18.         for (int i=n-1; i>=0; i--){
19.             int v = nums[i];
20.             for (int j=1; j<=k; j++){
21.                 for (int x=0; x<MX; x++){
22.                     suf[i][j][x] |= suf[i+1][j][x];
23.                     suf[i][j][x|v] |= suf[i+1][j-1][x];
24.                 }
25.             }
26.         }
27.         int ans = 0;
28.         for(int i = k - 1; i < n - k; i++){
29.             for(int x = 0; x < MX; x++){
30.                 if(pre[i + 1][k][x]){
31.                     for(int y = 0; y < MX; y++){
32.                         if(suf[i + 1][k][y]){
33.                             ans = Math.max(ans, x ^ y);
34.                         }
35.                     }
36.                 }
37.             }
38.         }
39.         return ans;
40.     }
41. }

复制代码

四，3288. 最长上升路径的长度

本题就是求最长上升子序列的题，只不外这里改成了坐标的形式，我们必要先给坐标按横坐标排序，在利用二分，但是必要注意的点是，可能存在有多个点，它们的横坐标相同，如果在横坐标相同时，纵坐标从小到大来排序，那么在计算的时候会重复计算，但是题目要求每个横纵坐标都要大于前一个点才算是上升序列，所以我们在横坐标相同时，纵坐标从大到小来排序，这样一来每个横坐标就只会计算一个纵坐标的点。
代码如下：

1. class Solution {
2.     public int maxPathLength(int[][] c, int k) {
3.         int n = c.length;
4.         int a = c[k][0], b = c[k][1];
5.         Arrays.sort(c, (x, y)->x[0]==y[0]?y[1]-x[1]:x[0]-y[0]);
6.         int[] f = new int[n+1];
7.         int ret = 0;
8.         for(int[] t : c){
9.             if(t[0] < a && t[1] < b || t[0] > a && t[1] > b){
10.                 if(ret == 0 || f[ret] < t[1]){
11.                     f[++ret] = t[1];
12.                 }else{
13.                     int l = 1, r = ret;
14.                     while(l <= r){
15.                         int mid = (l + r) / 2;
16.                         if(f[mid] < t[1]) l = mid + 1;
17.                         else r = mid - 1;
18.                     }
19.                     f[l] = t[1];
20.                 }
21.             }
22.         }
23.         return ret + 1;
24.     }
25. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。