devbox
酷酷是懒虫
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

力扣刷题篇之每日一题（2023年11月完成）_力扣 集中刷题

作者：酷酷是懒虫 | 2024-07-07 15:17:19

赞

踩

力扣 集中刷题

前言

想着每天都要刷每日一题的，但每次刷过了也没啥留下的，之后也容易忘，不如记录下来，一些知识，解题技巧，有趣的，碎碎念的。。。工作日就每日都更新，周末的题可能会留到周一更新。

每日一题

1

2127. 参加会议的最多员工数 - 力扣（LeetCode）

第一天就难度升级

 

这题还是很好看懂的，这个i人啊必须有她喜欢的人favorite[i]坐到她的左右两边（一个圈子）她才会参加（返回数加一）。其实就是找到能满足条件的最大的圈子大小。

思路：

拓扑排序来构建邻接表，然后计算圈子的大小。下面是代码的一般流程：

  1. 统计每个人的入度，即有多少个人喜欢这个人。

  2. 将入度为0的人添加到一个队列中。

  3. 通过BFS（广度优先搜索）遍历队列，计算每个人所在的圈子深度。

  4. 统计两种类型的圈子：小圈子和大圈子。

  5. 对于小圈子，它的最大大小为2，然后加上与它相邀请的人的深度之和。

  6. 对于大圈子，计算最大的圈子大小。

  7. 最后返回小圈子和大圈子中的最大值。

通过拓扑排序和BFS来找到满足条件的最大的圈子大小。

这题很有意思，有点人际交往的东西在里面。

  1. class Solution {
  2.     public int maximumInvitations(int[] favorite) {
  3.         int n = favorite.length;
  4. 		int[] indegree = new int[n];
  5. 		for (int i = 0; i < n; i++) 
  6. 			indegree[favorite[i]]++;
  7. 		
  8. 		int[] que = new int[n];
  9. 		int read = 0, write = 0;
  10. 		for (int i = 0; i < n; i++) {
  11. 			if (indegree[i] == 0) 
  12. 				que[write++] = i;
  13. 			
  14. 		}
  15. 		
  16. 		int[] depth = new int[n];
  17. 		while (read < write) {
  18. 			int cur = que[read++];
  19. 			int next = favorite[cur];
  20. 			depth[next] = Math.max(depth[next], depth[cur] + 1);
  21. 			if (--indegree[next] == 0) 
  22. 				que[write++] = next;
  23. 			
  24. 		}
  25. 		int sumOfSmallRings = 0;
  26. 		int bigRings = 0;
  27. 		for (int i = 0; i < n; i++) {
  28. 			if (indegree[i] > 0) {
  29. 				int maxSize = 1;
  30. 				indegree[i] = 0;
  31.  
  32. 				for (int j = favorite[i]; j != i; j = favorite[j]) {
  33. 					maxSize++;
  34. 					indegree[j] = 0;
  35. 				}
  36.  
  37. 				if (maxSize == 2) 
  38. 					sumOfSmallRings += 2 + depth[i] + depth[favorite[i]];
  39. 				else 
  40. 					bigRings = Math.max(bigRings, maxSize);
  41. 				
  42. 			}
  43. 		}
  44. 		return Math.max(sumOfSmallRings, bigRings);
  45.     }
  46. }

2.

2103. 环和杆 - 力扣（LeetCode）

简单题了，舒服

容易，找出所有集齐 全部三种颜色 环的杆，并返回这种杆的数量。

数组g存储每根杆上套的所有环，时间空间复杂度均为O(n)，n为字符串长度/2即环的个数

  1. class Solution {
  2.     public int countPoints(String rings) {
  3.         // 数组g存储每根杆上套的所有环，时间空间复杂度均为O(n)，n为字符串长度/2即环的个数
  4.         int n = rings.length() / 2, ans = 0;
  5.         List[] g = new ArrayList[10];
  6.         for (int i = 0; i < 10; i++) g[i] = new ArrayList<Character>();
  7.         for (int i = 0; i < n; i++) g[rings.charAt(2 * i + 1) - '0'].add(rings.charAt(2 * i));
  8.         for (int i = 0; i < 10; i++) if (g[i].contains('R') && g[i].contains('G') && g[i].contains('B')) ans++;
  9.         return ans;
  10.     }
  11. }

3.

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

中等题，但还是很简单的

这题其实就是层序遍历，填充他的next指针。

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4.     public int val;
  5.     public Node left;
  6.     public Node right;
  7.     public Node next;
  9.     public Node() {}
  10.     
  11.     public Node(int _val) {
  12.         val = _val;
  13.     }
  15.     public Node(int _val, Node _left, Node _right, Node _next) {
  16.         val = _val;
  17.         left = _left;
  18.         right = _right;
  19.         next = _next;
  20.     }
  21. };
  22. */
  23.  
  24. class Solution {
  25.     public Node connect(Node root) {
  26.       if(root==null){
  27.           return root;
  28.       }  
  29.       Node cur=root;
  30.       while(cur!=null){//遍历完
  31.         //   dummy是每层的头，pre负责构建，cur是指代当前层
  32.           Node dummy=new Node(0);
  33.           Node pre = dummy;
  34.           while(cur!=null){//到了NULL就说明每层结束了
  35.               if(cur.left!=null){
  36.                   pre.next=cur.left;
  37.                   pre=pre.next;
  38.               }
  39.               if(cur.right!=null){
  40.                   pre.next=cur.right;
  41.                   pre=pre.next;
  42.  
  43.               }
  44.               cur=cur.next;
  45.           }
  46.           cur=dummy.next;//指向下一层的第一个元素
  47.       }
  48.       return root;
  49.     }
  50. }

4.

421. 数组中两个数的最大异或值 - 力扣（LeetCode）

这个题最容易想到的是O(n^2)的暴力解法。

为了更高效地找到数组中两个数的最大异或值，可以使用更优化的算法，例如基于前缀树（Trie）的方法。这种方法可以将时间复杂度优化到 O(n)，从而提高算法的效率。

基于前缀树的方法涉及构建一个 Trie 数据结构，其中存储了数组中的数字的二进制表示。通过遍历数组中的每个数字，并在 Trie 中查找与当前数字的异或结果最大的另一个数字，可以找到数组中两个数的最大异或值。

前缀树的学习资料：

【【数据结构 10】Trie｜前缀树｜字典树】https://www.bilibili.com/video/BV1Az4y1S7c7?vd_source=70cd9a7d58eaf79ee46e9bddc1d0d53e

  1. class TrieNode {
  2.     TrieNode[] children;
  3.  
  4.     TrieNode() {
  5.         children = new TrieNode[2];
  6.     }
  7. }
  8.  
  9. class Solution {
  10.     public int findMaximumXOR(int[] nums) {
  11.         TrieNode root = new TrieNode();
  12.         int maxXOR = 0;
  13.  
  14.         for (int num : nums) {
  15.             insertNumber(root, num);
  16.             int currXOR = findXOR(root, num);
  17.             maxXOR = Math.max(maxXOR, currXOR);
  18.         }
  19.  
  20.         return maxXOR;
  21.     }
  22.  
  23.     private void insertNumber(TrieNode root, int num) {
  24.         TrieNode curr = root;
  25.  
  26.         for (int i = 31; i >= 0; i--) {
  27.             int bit = (num >> i) & 1;
  28.  
  29.             if (curr.children[bit] == null) {
  30.                 curr.children[bit] = new TrieNode();
  31.             }
  32.  
  33.             curr = curr.children[bit];
  34.         }
  35.     }
  36.  
  37.     private int findXOR(TrieNode root, int num) {
  38.         TrieNode curr = root;
  39.         int xor = 0;
  40.  
  41.         for (int i = 31; i >= 0; i--) {
  42.             int bit = (num >> i) & 1;
  43.             int oppositeBit = bit == 1 ? 0 : 1;
  44.  
  45.             if (curr.children[oppositeBit] != null) {
  46.                 xor |= (1 << i);
  47.                 curr = curr.children[oppositeBit];
  48.             } else {
  49.                 curr = curr.children[bit];
  50.             }
  51.         }
  52.  
  53.         return xor;
  54.     }
  55. }

  1. class Solution {
  2.     public int findMaximumXOR(int[] nums) {
  3.  
  4.         int max = Integer.MIN_VALUE;
  5.  
  6.         for(int n:nums)
  7.         {
  8.             max = Math.max(max,n);
  9.         }
  10.  
  11.         
  12.         int highestBitPos = 31 - Integer.numberOfLeadingZeros(max);
  13.  
  14.         int res = 0;
  15.         int mask = 0;
  16.  
  17.         Set<Integer> set;
  18.  
  19.         for(int i=highestBitPos;i>=0;i--)
  20.         {
  21.             set = new HashSet<>();
  22.             mask = mask | (1 << i);
  23.             int candidateRes = res | (1 << i);
  24.             for(int n:nums)
  25.             {
  26.                 n = n & mask;
  27.                 if(set.contains(candidateRes ^ n))
  28.                 {
  29.                     res = candidateRes;
  30.                     break;
  31.                 }
  32.                 set.add(n);
  33.             }
  34.         }
  35.  
  36.         return res;
  37.  
  38.  
  39.  
  40.     }
  41. }

5.

187. 重复的DNA序列 - 力扣（LeetCode）

找长度为10，出现过两次及以上的子序列。

方法一，用哈希表

遍历字符串，把所有十个连续的子序列存进map里，每出现一次value加一，value等于2时就能加入ansl了。

  1. class Solution {
  2.     public List<String> findRepeatedDnaSequences(String s) {
  3.         int n = s.length();
  4.         List<String> ansL = new ArrayList<>();
  5.         if (n <= 10) return ansL;
  6.         Map<String, Integer> map = new HashMap<>();
  7.         for (int i = 0; i <= n - 10; i++) {
  8.             String ans = s.substring(i, i + 10);
  9.             map.put(ans, map.getOrDefault(ans, 0) + 1);
  10.             if (map.get(ans) == 2) ansL.add(ans);
  11.         }
  12.         return ansL;
  13.     }
  14. }

方法二、滑动窗口＋哈希表

  1. import java.util.AbstractList;
  2. class Solution {
  3.     public static List<String> findRepeatedDnaSequences(String s) {
  4.         int n = s.length();
  5.         Map<Character, Integer> cMap = new HashMap<>() {{
  6.             put('A', 0);
  7.             put('C', 1);
  8.             put('G', 2);
  9.             put('T', 3);
  10.         }};
  11.         return new AbstractList<String>() {
  12.             private final List<String> list = new ArrayList<>();
  13.  
  14.             private final Map<Integer, Integer> map = new HashMap<>();
  15.  
  16.             @Override
  17.             public String get(int index) {
  18.                 init();
  19.                 return list.get(index);
  20.             }
  21.  
  22.             @Override
  23.             public int size() {
  24.                 init();
  25.                 return list.size();
  26.             }
  27.  
  28.             void init() {
  29.                 if (list.isEmpty() && n > 10) {
  30.                     findRepeatedDnaSequences();
  31.                 }
  32.             }
  33.  
  34.             void findRepeatedDnaSequences() {
  35.                 int code = 0;
  36.                 for (int i = 0; i < 10; i++) {
  37.                     code = (code << 2) + cMap.get(s.charAt(i));
  38.                 }
  39.                 map.put(code, 1);
  40.                 for (int i = 10; i < n; i++) {
  41.                     code &= (1 << 18) - 1;
  42.                     code = (code << 2) + cMap.get(s.charAt(i));
  43.                     int count = map.getOrDefault(code, 0);
  44.                     if (count == 1) {
  45.                         list.add(s.substring(i - 9, i + 1));
  46.                     }
  47.                     map.put(code, count + 1);
  48.                 }
  49.             }
  50.         };
  51.     }
  52. }

6

318. 最大单词长度乘积 - 力扣（LeetCode）

 位运算+暴力枚举：

首先，创建一个整型数组 store，用于存储每个字符串的二进制表示。

然后，遍历字符串数组 words，对每个字符串进行处理。

对于每个字符串 s，遍历其中的每个字符，并计算字符相对于字符 'a' 的偏移量。根据偏移量，使用位运算来设置相应的二进制位。

在内层循环中，首先计算 tag，表示字符在当前字符串的二进制表示中对应位的值。如果 tag 等于 0，说明该字符在当前字符串中是第一次出现，将相应的二进制位设置为 1。

完成字符串的二进制表示后，接下来的嵌套循环用于比较每对字符串的二进制表示。

对于每对字符串的二进制表示，使用位运算的与操作 (store[i] & store[p])，如果结果为 0，说明两个字符串没有相同的字母。

如果两个字符串没有相同的字母，则计算它们的长度乘积 res，并更新最大乘积 ans。

最后，返回最大乘积 ans。

  1. class Solution {
  2.     public int maxProduct(String[] words) {
  3.         //思路：直接用位运算
  4.         int[] store=new int[words.length];
  5.         for(int i=0;i<words.length;i++){//转二进制存储
  6.             String s=words[i];
  7.             for(Character c : s.toCharArray()){
  8.                 int tag=(store[i]%(1<<(c-'a'+1)))/(1<<(c-'a'));
  9.                 if(tag==0){
  10.                     store[i]=store[i]+(1<<(c-'a'));
  11.                 }
  12.             }
  13.         }
  14.         int ans=0;
  15.         for(int i=0;i<store.length-1;i++){
  16.             for(int p=i+1;p<store.length;p++){
  17.                 if((store[i]&store[p])==0){//与运算，结果为0则说明两者没有相同字母
  18.                     int res=words[i].length()*words[p].length();
  19.                     ans=Math.max(res,ans);
  20.                 }
  21.             }
  22.         }
  23.         return ans;
  24.     }
  25. }

 

优化：

首先对每个字符串进行预处理，将其转换为一个包含字符出现情况的位向量（bitmask），出现的位在二进制上的偏移置为1，方便后续计算。然后，对于每一对字符串，如果它们的位向量按位与的结果为0，则它们没有相同的字母，可以计算它们的长度乘积并更新最大乘积。

  1. class Solution {
  2.     public int maxProduct(String[] words) {
  3.         int n = words.length;
  4.  
  5.         // 预处理，将每个字符串转换为位向量
  6.         int[] bitmasks = new int[n];
  7.         for (int i = 0; i < n; i++) {
  8.             String word = words[i];
  9.             int bitmask = 0;
  10.             for (char c : word.toCharArray()) {
  11.                 bitmask |= 1 << (c - 'a'); // 将对应的位设置为1
  12.             }
  13.             bitmasks[i] = bitmask;
  14.         }
  15.  
  16.         int maxProduct = 0;
  17.         for (int i = 0; i < n - 1; i++) {
  18.             for (int j = i + 1; j < n; j++) {
  19.                 // 如果两个字符串的位向量按位与的结果为0，则它们没有相同的字母
  20.                 if ((bitmasks[i] & bitmasks[j]) == 0) {
  21.                     int product = words[i].length() * words[j].length();
  22.                     maxProduct = Math.max(maxProduct, product);
  23.                 }
  24.             }
  25.         }
  26.  
  27.         return maxProduct;
  28.     }
  29. }

7.

2586. 统计范围内的元音字符串数 - 力扣（LeetCode）

简单题，我哭死

判断首尾是不是元音字符串就好了。 

  1. class Solution {
  2.     public int vowelStrings(String[] words, int left, int right) {
  3.         int res=0;
  4.         for(int i=left;i<=right;i++){
  5.             String s=words[i];
  6.             int n=s.length();
  7.             if((s.charAt(0)=='a'||s.charAt(0)=='e'||s.charAt(0)=='i'||s.charAt(0)=='o'||s.charAt(0)=='u') && (s.charAt(n-1)=='a'||s.charAt(n-1)=='e'||s.charAt(n-1)=='i'||s.charAt(n-1)=='o'||s.charAt(n-1)=='u')) res++;
  8.         }
  9.         return res;
  10.     }
  11. }

 

 8

2609. 最长平衡子字符串 - 力扣（LeetCode）

  • 在循环中，初始化变量 a 和 b 为 0，分别表示以 0 和 1 结尾的平衡子字符串的长度。
  • 在第一个 while 循环中，判断索引 idx 是否小于 n，并且字符串 s 在索引 idx 处的字符是否为 '0'，如果是则进入循环体。
    • 将 a 自增 1，并且判断 a 是否大于等于 0。
    • 将索引 idx 自增 1。
  • 在第二个 while 循环中，同样判断索引 idx 是否小于 n，并且字符串 s 在索引 idx 处的字符是否为 '1'，如果是则进入循环体。
    • 将 b 自增 1，并且判断 b 是否大于等于 0。
    • 将索引 idx 自增 1。
  • 计算当前平衡子字符串的长度，取 a 和 b 的较小值乘以 2，并将结果与 ans 进行比较，取较大值更新 ans。
  1. class Solution {
  2.     public int findTheLongestBalancedSubstring(String s) {
  3.         int n = s.length(), idx = 0, ans = 0;
  4.         while (idx < n) {
  5.             int a = 0, b = 0;
  6.             while (idx < n && s.charAt(idx) == '0' && ++a >= 0) idx++;
  7.             while (idx < n && s.charAt(idx) == '1' && ++b >= 0) idx++;
  8.             ans = Math.max(ans, Math.min(a, b) * 2);
  9.         }
  10.         return ans;
  11.     }
  12. }

9

2258. 逃离火灾 - 力扣（LeetCode）

bfs,我先CV 

  1. // class Solution {
  2. //     // 二分+bfs(预处理+验证路径)
  3. //     // 将矩阵可达点预处理为着火时间，后续bfs搜索路径时，到达时间小于着火时间的为可走路径。
  4. //     // 可暂停时间的最小值为0，最大值为无穷大，而无穷大状态即火焰扩张完所有可达位置后，
  5. //     // 矩阵中仍存在从左上到右下角的安全路径，所以可暂停时间time可设置为火焰完成扩张时间+2，
  6. //     // 即ans可能取[0,time]内任何值，在此区间内二分查找不存在可达路径的暂停时间最小值，
  7. //     // 判定合法的方式就是对每个时间t在预处理过后的矩阵内搜索是否存在左上到右下的安全路径，
  8. //     // 1、若t=0时不可到达目标点，则永远不可达成，返回-1，
  9. //     // 2、若t=time,而在time-1时存在安全路径，而火焰完成扩张的时间是time-2，所以火焰不在扩张后仍存在安全路径，是否可达与暂停时间无关，返回1e9，
  10. //     // 3、其余情况下则是火扩张至某时刻后目标点不在可达，那么二分求的是最小不可达时间r，r-1即为最大可达目标点的暂停时间。
  11. //     int[][] g;
  12. //     int m, n;
  13. //     int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
  14. //     public int maximumMinutes(int[][] g) {
  15. //         this.g = g;
  16. //         m = g.length;
  17. //         n = g[0].length;
  18. //         Deque<int[]> que = new ArrayDeque<>();
  19. //         boolean[][] vis = new boolean[m][n];
  20. //         // 预处理矩阵，将所有墙壁点标记为-1，这样就可以用0代表空地，以及大于0的数字代表每个位置开始着火的时间。
  21. //         // 将初始火源点存入队列，后续bfs按圈扩张，标记所有
  22. //         for(int i = 0; i < m; ++i){
  23. //             for(int j = 0; j < n; ++j){
  24. //                 if(g[i][j] == 2){
  25. //                     g[i][j] = -1;
  26. //                 }else if(g[i][j] == 1){
  27. //                     que.offer(new int[]{i, j});
  28. //                     vis[i][j] = true;
  29. //                 }
  30. //             }
  31. //         }                 
  32. //         int time = 1;
  33. //         // bfs分层模拟扩展随时间可被火焰蔓延的区域,在g矩阵标记着火时间点,time最终为火焰铺满所有可蔓延位置所需的时间。
  34. //         while(!que.isEmpty()){
  35. //             int len = que.size();
  36. //             while(--len >= 0){
  37. //                 int[] p = que.poll();
  38. //                 for(int k = 0; k < 4; ++k){
  39. //                     int i = p[0] + dir[k][0], j = p[1] + dir[k][1];
  40. //                     if(i >= 0 && j >= 0 && i < m && j < n && !vis[i][j] && g[i][j] == 0){
  41. //                         g[i][j] = time;
  42. //                         que.offer(new int[]{i, j});
  43. //                         vis[i][j] = true;
  44. //                     }
  45. //                 }
  46. //             }
  47. //             ++time;
  48. //         }
  49. //         // 二分找到无法到达的最小暂停时间r，则r-1即为最大可暂停时间。
  50. //         int l = 0, r = time;
  51. //         while(l < r){
  52. //             int mid = l + r >> 1;
  53. //             if(!bfs(mid))
  54. //                 r = mid;
  55. //             else
  56. //                 l = mid + 1;
  57. //         }
  58. //         // 若直接出发仍无法到达，则-1不可实现；若火焰完成扩张后+1秒仍可到达，因火焰不会在扩张，所以说明后续仍可到达。
  59. //         // 否则返回最小无法到达暂停时间r-1即可。
  60. //         if(r == 0)
  61. //             return -1;
  62. //         else if(r == time)
  63. //             return 1000000000;
  64. //         else
  65. //             return r-1;
  66. //     }
  67. //     // bfs验证在预留t时间的火势状态下，是否能够从左上角走到右下角。
  68. //     public boolean bfs(int t){
  69. //         ++t;
  70. //         boolean[][] vis = new boolean[m][n];
  71. //         Deque<int[]> que = new ArrayDeque<>();
  72. //         que.offer(new int[]{0,0});
  73. //         vis[0][0] = true;
  74. //         // 当
  75. //         while(!que.isEmpty()){
  76. //             int len = que.size();
  77. //             while(len-- > 0){
  78. //                 int[] p = que.poll();
  79. //                 for(int k = 0; k < 4; ++k){
  80. //                     int i = p[0] + dir[k][0], j = p[1] + dir[k][1];
  81. //                     if(i >= 0 && j >= 0 && i < m && j < n && !vis[i][j] && (g[i][j] >= t || g[i][j] == 0)){
  82. //                         // 到达终点(m-1,n-1)则true。
  83. //                         if(i == m - 1 && j == n - 1)
  84. //                             return true;
  85. //                         if(g[i][j] > t || g[i][j] == 0)
  86. //                             que.offer(new int[]{i, j});
  87. //                         vis[i][j] = true;
  88. //                     }
  89. //                 }
  90. //             }
  91. //             // 若中途终点被火蔓延,则后续也无法再到达,直接false。
  92. //             if(g[m-1][n-1] == t)
  93. //                 return false;
  94. //             ++t;
  95. //         }
  96. //         return false;
  97. //     }
  98. // }
  99.  
  100. class Solution {
  101.     static int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
  102.     public int maximumMinutes(int[][] grid) {
  103.         int m = grid.length, n = grid[0].length;
  104.         int[][] fire = new int[m][n];
  105.         int[][]people = new int[m][n];
  106.         for (int i = 0; i < m; i++) {
  107.             Arrays.fill(fire[i], -1);
  108.             Arrays.fill(people[i], -1);
  109.         }
  110.         Deque<int[]> que = new ArrayDeque<>();
  111.         for (int i = 0; i < m; i++) {
  112.             for (int j = 0; j < n; j++) {
  113.                 if (grid[i][j] == 1) {
  114.                     fire[i][j] = 0;
  115.                     que.offer(new int[]{i, j, 0});
  116.                 }
  117.             }
  118.         }
  119.         while (!que.isEmpty()) {
  120.             int[] cur = que.poll();
  121.             for (int[] d: directions) {
  122.                 int nx = cur[0] + d[0], ny = cur[1] + d[1];
  123.                 if (nx >= 0 && ny >= 0 && nx < m && ny < n && fire[nx][ny] == -1 && grid[nx][ny] == 0) {
  124.                     fire[nx][ny] = cur[2] + 1;
  125.                     que.offer(new int[]{nx, ny, cur[2] + 1});
  126.                 }
  127.             }
  128.         }
  129.  
  130.         people[0][0] = 0;
  131.         que = new ArrayDeque<>();
  132.         que.offer(new int[]{0, 0, 0});
  133.         while (!que.isEmpty()) {
  134.             int[] cur = que.poll();
  135.             for (int[] d:directions) {
  136.                 int nx = cur[0] + d[0], ny = cur[1] + d[1];
  137.                 if (nx >= 0 && ny >= 0 && nx < m && ny < n && people[nx][ny] == -1 && grid[nx][ny] == 0) {
  138.                     people[nx][ny] = cur[2] + 1;
  139.                     if (nx == m - 1 && ny == n - 1) return fire[m - 1][n - 1] == -1 ? (int)1e9 : fire[m - 1][n - 1] - people[m - 1][n - 1] - ((fire[m - 2][n - 1] != fire[m - 1][n - 1] - 1 && people[m - 2][n - 1] == people[m - 1][n - 1] - 1 || fire[m - 1][n - 2] != fire[m - 1][n - 1] - 1 && people[m - 1][n - 2] == people[m - 1][n - 1] - 1) ? 0 : 1);
  140.                     if (people[nx][ny] >= fire[nx][ny] && fire[nx][ny] != -1) continue;
  141.                     que.offer(new int[]{nx, ny, cur[2] + 1});
  142.                 }
  143.             }
  144.         }
  145.         return -1;
  146.     }
  147. }

10.

2300. 咒语和药水的成功对数 - 力扣（LeetCode）


 

  1. // // class Solution {
  2. // //     public int[] successfulPairs(int[] spells, int[] potions, long success) {
  3. // //         int n=spells.length;
  4. // //         int[] res=new int[n];
  5. // //         for(int i=0;i<n;i++){
  6. // //             int cnt=0;
  7. // //             for(int j=0;j<potions.length;j++){
  8. // //                 if(spells[i]*potions[j]>=success) cnt++;
  9. // //             }
  10. // //             res[i]=cnt;
  11. // //         }
  12. // //         return res;
  13. // //     }
  14. // // }
  15.  
  16. // class Solution {
  17.  
  18. //     public int[] successfulPairs(int[] spells, int[] potions, long success) {
  19. //         Arrays.sort(potions);
  20. //         int N = spells.length;
  21. //         int M = potions.length;
  22. //         int[] ans = new int[N];
  23. //         for (int i = 0; i < N; i++) {
  24. //             int l = 0;
  25. //             int r = M - 1;
  26. //             int min = -1;
  27. //             while (l <= r) {
  28. //                 int m = (l + r) >>> 1;
  29. //                 if ((long) potions[m] * spells[i] >= success) {
  30. //                     min = m;
  31. //                     r = m - 1;
  32. //                 } else {
  33. //                     l = m + 1;
  34. //                 }
  35. //             }
  36. //             if (min != -1) {
  37. //                 ans[i] = M - min;
  38. //             }
  39. //         }
  40. //         return ans;
  41. //     }
  42. // }
  43.  
  44. class Solution {
  45.     static int inf = (int)1e5;
  46.     public int[] successfulPairs(int[] spells, int[] potions, long success){
  47.         int max = 0;
  48.         for(int x : spells){
  49.             if(x > max) max = x;
  50.         }
  51.         int minPotion = (int)Math.min(inf, (success - 1) / max);
  52.         int[] count = new int[max + 1];
  53.         for(int potion:potions){
  54.             if(potion > minPotion){
  55.                 ++count[(int)((success + potion - 1)/potion)];
  56.             }
  57.         }
  58.         for(int i = 1; i <= max; i++){
  59.             count[i] += count[i-1];
  60.         }
  61.         int n = spells.length;
  62.         int[] result = new int[n];
  63.         for(int i = 0; i < n; i++){
  64.             result[i] = count[spells[i]];
  65.         }
  66.         return result;
  67.     }
  68. }

11

765. 情侣牵手 - 力扣（LeetCode）

使用了贪心算法的思想。从左到右遍历数组，对于每一对夫妻，如果他们不坐在一起（即i位置的配偶不是y），则在后面的位置中找到y的位置j，然后交换i位置的配偶和j位置的人。交换次数加1，继续遍历下一对夫妻。最终返回交换次数。

该方法的时间复杂度为O(n^2)，其中n是数组row的长度。

  1. class Solution {
  2.     public int minSwapsCouples(int[] row) {
  3.         int count = 0;  // 交换次数计数器
  4.         for (int i = 0; i < row.length; i += 2) {
  5.             int x = row[i];  // 当前位置i的夫妻编号
  6.             int y = x ^ 1;  // x的配偶编号
  7.             if (row[i + 1] != y) {  // 如果i位置的配偶不是y，则需要进行交换
  8.                 for (int j = i + 2; j < row.length; j++) {
  9.                     if (row[j] == y) {  // 在后面的位置找到y的位置j
  10.                         int temp = row[i + 1];  // 交换i位置的配偶和j位置的人
  11.                         row[i + 1] = row[j];
  12.                         row[j] = temp;
  13.                         count++;  // 交换次数加1
  14.                         break;
  15.                     }
  16.                 }
  17.             }
  18.         }
  19.         return count;  // 返回交换次数
  20.     }
  21. }

12

715. Range 模块 - 力扣（LeetCode）

讲实话，我看不懂一点，这个之后还要仔细看看

  1. // class RangeModule {
  2. //     TreeMap<Integer, Integer> intervals;
  3.  
  4. //     public RangeModule() {
  5. //         intervals = new TreeMap<Integer, Integer>();
  6. //     }
  7.  
  8. //     public void addRange(int left, int right) {
  9. //         Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
  10. //         if (entry != intervals.firstEntry()) {
  11. //             Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
  12. //             if (start != null && start.getValue() >= right) {
  13. //                 return;
  14. //             }
  15. //             if (start != null && start.getValue() >= left) {
  16. //                 left = start.getKey();
  17. //                 intervals.remove(start.getKey());
  18. //             }
  19. //         }
  20. //         while (entry != null && entry.getKey() <= right) {
  21. //             right = Math.max(right, entry.getValue());
  22. //             intervals.remove(entry.getKey());
  23. //             entry = intervals.higherEntry(entry.getKey());
  24. //         }
  25. //         intervals.put(left, right);
  26. //     }
  27.  
  28. //     public boolean queryRange(int left, int right) {
  29. //         Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
  30. //         if (entry == intervals.firstEntry()) {
  31. //             return false;
  32. //         }
  33. //         entry = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
  34. //         return entry != null && right <= entry.getValue();
  35. //     }
  36.  
  37. //     public void removeRange(int left, int right) {
  38. //         Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
  39. //         if (entry != intervals.firstEntry()) {
  40. //             Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
  41. //             if (start != null && start.getValue() >= right) {
  42. //                 int ri = start.getValue();
  43. //                 if (start.getKey() == left) {
  44. //                     intervals.remove(start.getKey());
  45. //                 } else {
  46. //                     intervals.put(start.getKey(), left);
  47. //                 }
  48. //                 if (right != ri) {
  49. //                     intervals.put(right, ri);
  50. //                 }
  51. //                 return;
  52. //             } else if (start != null && start.getValue() > left) {
  53. //                 if (start.getKey() == left) {
  54. //                     intervals.remove(start.getKey());
  55. //                 } else {
  56. //                     intervals.put(start.getKey(), left);
  57. //                 }
  58. //             }
  59. //         }
  60. //         while (entry != null && entry.getKey() < right) {
  61. //             if (entry.getValue() <= right) {
  62. //                 intervals.remove(entry.getKey());
  63. //                 entry = intervals.higherEntry(entry.getKey());
  64. //             } else {
  65. //                 intervals.put(right, entry.getValue());
  66. //                 intervals.remove(entry.getKey());
  67. //                 break;
  68. //             }
  69. //         }
  70. //     }
  71. // }
  72.  
  73. class RangeModule {
  74.  
  75.     public Range root;
  76.     public RangeModule() {
  77.         
  78.     }
  79.     
  80.     public void addRange(int left, int right) {
  81.         root = insert(root,left, right-1);
  82.     }
  83.     
  84.     public boolean queryRange(int left, int right) {
  85.         return query(root,left, right-1);
  86.     }
  87.     
  88.     public void removeRange(int left, int right) {
  89.         root = remove(root,left, right-1);
  90.     }
  91.     
  92.     static class  Range{
  93.         public int left, right;
  94.         public Range l, r;
  95.         
  96.         public Range(int left,int right){
  97.             this.left = left;
  98.             this.right = right;
  99.         }
  100.     }
  101.         
  102.     public Range remove(Range range,int left,int right){
  103.         
  104.         if(range == null) return null;
  105.         
  106.         if(right < range.left)
  107.             range.l = remove(range.l, left, right);
  108.         else if(left > range.right)
  109.         
  110.             range.r = remove(range.r, left, right);
  111.         else if(left <= range.left && right >= range.right){
  112.          
  113.             Range l = remove(range.l, left, right);
  114.             Range r = remove(range.r, left, right);
  115.             if(l == null)
  116.                 return r;
  117.             else if(r == null)
  118.                 return l;
  119.             else{
  120.                 if(l.r == null){
  121.                     l.r = r;
  122.                     return l;
  123.                 }else{
  124.                     Range temp = r;
  125.                     while(temp.l!=null)
  126.                         temp=temp.l;
  127.                     temp.l = l;
  128.                     return r;
  129.                 }
  130.             }
  131.  
  132.         }else if(left <= range.left){
  133.             range.left = right+1;
  134.             range.l = remove(range.l, left, right);
  135.  
  136.         }else if(right >= range.right){
  137.             range.right = left - 1;
  138.             range.r = remove(range.r, left, right);
  139.  
  140.         }else{
  141.            
  142.             Range newR = new Range(right+1, range.right);
  143.             Range r = range.r;
  144.             range.right = left - 1;
  145.             newR.r = r;
  146.             range.r = newR;
  147.         }
  148.  
  149.         return range;
  150.     }
  151.     public boolean query(Range range,int left,int right){
  152.         
  153.         if(range == null)
  154.             return false;
  155.  
  156.         if(right < range.left)
  157.             return query(range.l,left,right);
  158.         else if(left > range.right)
  159.             return query(range.r,left,right);
  160.         else if(left >= range.left && right <= range.right)
  161.             return true;
  162.         
  163.         return false;
  164.     }
  165.     
  166.     public Range insert(Range range,int left,int right){
  167.         
  168.         if(range == null)
  169.             return new Range(left, right);
  170.         
  171.         if(right < range.left -1)
  172.             range.l = insert(range.l, left, right);
  173.  
  174.          else if(left > range.right+1)
  175.             range.r = insert(range.r, left, right);
  176.  
  177.         else{ 
  178.             int[]info = new int[]{left, right};
  179.             range.l = add(range.l, info, true);
  180.             range.r = add(range.r, info, false);
  181.          range.left = Math.min(range.left, info[0]);       
  182.          range.right = Math.max(range.right, info[1]);
  183.         }
  184.         return range;
  185.     }
  186.     public Range add(Range range,int [] info,boolean isleft){
  187.         
  188.         if(range == null)
  189.             return null;
  190.             
  191.         if(isleft){ 
  192.             if(range.right >= info[0] - 1){ //重叠
  193.                 info[0] = Math.min(info[0], range.left);
  194.                 return add(range.l, info, isleft);
  195.             }else{
  196.                 range.r = add(range.r, info, isleft);
  197.                 return range;
  198.             }
  199.         }else if(!isleft){ 
  200.             if(range.left <= info[1]+1){ 
  201.                 info[1] = Math.max(info[1], range.right);
  202.                 return add(range.r, info, isleft);
  203.             }else{
  204.                 range.l = add (range.l, info, isleft);
  205.                 return range;
  206.             }
  207.         }
  208.         return range;
  209.     }
  210. }

13 

307. 区域和检索 - 数组可修改 - 力扣（LeetCode）

this.nums=nums;下面这个 通过了但是不好，遍历区间，效果不好

  1. class NumArray {
  2.     private int[] nums;
  3.  
  4.     public NumArray(int[] nums) {
  5.         this.nums = nums;
  6.     }
  7.     
  8.     public void update(int index, int val) {
  9.         nums[index] = val;
  10.     }
  11.     
  12.     public int sumRange(int left, int right) {
  13.         int sum = 0;
  14.         for (int i = left; i <= right; i++) {
  15.             sum += nums[i];
  16.         }
  17.         return sum; // Add this line to return the computed sum
  18.     }
  19. }
  20.  
  21. /**
  22.  * Your NumArray object will be instantiated and called as such:
  23.  * NumArray obj = new NumArray(nums);
  24.  * obj.update(index,val);
  25.  * int param_2 = obj.sumRange(left,right);
  26.  */

加上双指针，也不太好

  1. class NumArray {
  2.     private int[] nums;
  3.  
  4.     public NumArray(int[] nums) {
  5.         this.nums = nums;
  6.     }
  7.     
  8.     public void update(int index, int val) {
  9.         nums[index] = val;
  10.     }
  11.     
  12.     public int sumRange(int left, int right) {
  13.         int sum = 0;
  14.         if((left+right)%2==0){
  15.             sum=nums[(left+right)/2];
  16.         }
  17.         
  18.         while(left<right){
  19.             sum=sum+nums[left]+nums[right];
  20.             left++;
  21.             right--;
  22.         }
  23.         return sum; // Add this line to return the computed sum
  24.     }
  25. }
  26.  
  27. /**
  28.  * Your NumArray object will be instantiated and called as such:
  29.  * NumArray obj = new NumArray(nums);
  30.  * obj.update(index,val);
  31.  * int param_2 = obj.sumRange(left,right);
  32.  */

用上树状数组（Binary Indexed Tree，BIT）来实现动态数组的区间更新和区间查询，有所改进

  1. public class NumArray {
  2.     private int[] nums;   // 存储原始数组
  3.     private int[] tree;   // 树状数组，用于快速计算区间和
  4.  
  5.     public NumArray(int[] nums) {
  6.         int n = nums.length;
  7.         this.nums = nums;
  8.         tree = new int[n + 1];
  9.  
  10.         // 初始化树状数组
  11.         for (int i = 1; i <= n; i++) {
  12.             tree[i] += nums[i - 1];
  13.             int nxt = i + (i & -i); // 下一个关键区间的右端点
  14.             if (nxt <= n) {
  15.                 tree[nxt] += tree[i];
  16.             }
  17.         }
  18.     }
  19.  
  20.     public void update(int index, int val) {
  21.         int delta = val - nums[index];
  22.         nums[index] = val;
  23.  
  24.         // 更新树状数组
  25.         for (int i = index + 1; i < tree.length; i += i & -i) {
  26.             tree[i] += delta;
  27.         }
  28.     }
  29.  
  30.     // 计算从位置 1 到位置 i 的前缀和
  31.     private int prefixSum(int i) {
  32.         int s = 0;
  33.         for (; i > 0; i &= i - 1) { // i -= i & -i 的另一种写法
  34.             s += tree[i];
  35.         }
  36.         return s;
  37.     }
  38.  
  39.     public int sumRange(int left, int right) {
  40.         // 计算区间和
  41.         return prefixSum(right + 1) - prefixSum(left);
  42.     }
  43. }

 

 14

1334. 阈值距离内邻居最少的城市 - 力扣（LeetCode）

该算法通过 Floyd-Warshall 算法计算所有城市之间的最短路径，并统计每个城市到其他城市的距离是否满足条件。最后，返回满足条件的城市中，拥有最小邻居数量的城市。

这个算法的时间复杂度为 O(n^3)，其中 n 是城市的数量。这是因为它使用了 Floyd-Warshall 算法，该算法的时间复杂度为 O(n^3)。对于小规模的城市数量可能是可接受的，但对于大规模的城市网络，可能会变得很慢。

  1. class Solution {
  2.     public int findTheCity(int n, int[][] edges, int distanceThreshold) {
  3.         // 初始化城市之间的距离矩阵，使用较大的值表示无穷大距离
  4.         int[][] dis = new int[n][n];
  5.         for (int i = 0; i < n; i++) {
  6.             Arrays.fill(dis[i], Integer.MAX_VALUE / 2);
  7.         }
  8.  
  9.         // 根据边数组更新直接相连城市之间的距离
  10.         for (int[] e : edges) {
  11.             dis[e[0]][e[1]] = e[2];
  12.             dis[e[1]][e[0]] = e[2];
  13.         }
  14.  
  15.         // 使用 Floyd-Warshall 算法计算所有城市之间的最短路径
  16.         for (int k = 0; k < n; k++) {
  17.             dis[k][k] = 0;
  18.             for (int i = 0; i < n; i++) {
  19.                 for (int j = i + 1; j < n; j++) {
  20.                     // 更新城市 i 到城市 j 的最短路径
  21.                     dis[i][j] = dis[j][i] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
  22.                 }
  23.             }
  24.         }
  25.  
  26.         // 统计每个城市满足条件的邻居数量，并记录邻居数量最小的城市
  27.         int[] ans = new int[]{Integer.MAX_VALUE, -1};
  28.         for (int i = 0; i < n; i++) {
  29.             int cnt = 0;
  30.             for (int j = 0; j < n; j++) {
  31.                 // 统计满足条件的邻居数量
  32.                 if (dis[i][j] <= distanceThreshold) {
  33.                     cnt++;
  34.                 }
  35.             }
  36.             // 更新邻居数量最小的城市信息
  37.             if (cnt <= ans[0]) {
  38.                 ans[0] = cnt;
  39.                 ans[1] = i;
  40.             }
  41.         }
  42.  
  43.         // 返回邻居数量最小的城市
  44.         return ans[1];
  45.     }
  46. }

15

2656. K 个元素的最大和 - 力扣（LeetCode）

今天好简单，我好爱

  1. class Solution {
  2.     public int maximizeSum(int[] nums, int k) {
  3.         int max=0;
  4.         for(int n:nums){
  5.             max=n>max? n:max;
  6.         }
  7.         return k*max+(k-1)*k/2;
  8.     }
  9. }

16

2760. 最长奇偶子数组 - 力扣（LeetCode）

这个题要求从第一个偶数开始，偶奇偶奇偶奇这么往后排，找最长的 

使用一个迭代的方法，在遍历数组时，根据条件更新交替子数组的起始位置和最长长度。最后，处理最后一个交替子数组，返回最终的最长交替子数组的长度。 

  1. class Solution {
  2.     public int longestAlternatingSubarray(int[] nums, int threshold) {
  3.         int li = -1; // 记录当前交替子数组的起始位置
  4.         int max = 0; // 记录最长交替子数组的长度
  5.         int n = nums.length;
  6.  
  7.         for (int i = 0; i < n; i++) {
  8.             if (nums[i] > threshold) {
  9.                 // 当前元素大于阈值，结束当前交替子数组
  10.                 max = li == -1 ? max : Math.max(max, i - li);
  11.                 li = -1;
  12.             } else if (li == -1 && (nums[i] & 1) == 0) {
  13.                 // 第一个偶数，标记当前位置为交替子数组的起始位置
  14.                 li = i;
  15.             } else if (li != -1 && (nums[i] & 1) == (nums[i - 1] & 1)) {
  16.                 // 当前元素与前一个元素奇偶性相同，结束当前交替子数组
  17.                 max = Math.max(max, i - li);
  18.                 // 更新起始位置，如果当前元素是偶数，则更新为当前位置，否则为 -1
  19.                 li = (nums[i] & 1) == 0 ? i : -1;
  20.             }
  21.         }
  22.  
  23.         // 处理最后一个交替子数组
  24.         return li == -1 ? max : Math.max(max, n - li);
  25.     }
  26. }

17

2736. 最大和查询 - 力扣（LeetCode）

  1. public class Solution {
  2.  
  3.     // BinarySet 类表示二元组 (x, y)，实现 Comparable 接口用于排序
  4.     public static class BinarySet implements Comparable<BinarySet> {
  5.         int x;
  6.         int y;
  7.         BinarySet left;
  8.         BinarySet right;
  9.  
  10.         public BinarySet(int x, int y) {
  11.             this.x = x;
  12.             this.y = y;
  13.         }
  14.  
  15.         // 降序比较，用于排序
  16.         @Override
  17.         public int compareTo(BinarySet o) {
  18.             return -(x + y) + (o.x + o.y);
  19.         }
  20.     }
  21.  
  22.     // 主要方法，处理查询
  23.     public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
  24.         int[] result = new int[queries.length];
  25.         BinarySet[] binarySets = new BinarySet[nums1.length];
  26.  
  27.         // 创建 BinarySet 数组并按照 (x + y) 降序排序
  28.         for (int i = 0; i < nums1.length; i++) {
  29.             binarySets[i] = new BinarySet(nums1[i], nums2[i]);
  30.         }
  31.         Arrays.sort(binarySets);
  32.  
  33.         // 构建二叉搜索树
  34.         BinarySet root = binarySets[0];
  35.         for (int i = 1; i < binarySets.length; i++) {
  36.             buildTree(root, binarySets[i]);
  37.         }
  38.  
  39.         // 处理查询
  40.         for (int i = 0; i < queries.length; i++) {
  41.             result[i] = search(root, new BinarySet(queries[i][0], queries[i][1]));
  42.         }
  43.         return result;
  44.     }
  45.  
  46.     // 查询方法，返回满足条件的最大值，如果找不到则返回 -1
  47.     public int search(BinarySet root, BinarySet q) {
  48.         if (root.x < q.x && root.y < q.y) {
  49.             return -1;
  50.         } else if (root.x >= q.x && root.y >= q.y) {
  51.             return root.x + root.y;
  52.         } else if (root.x < q.x) {
  53.             if (root.left == null) {
  54.                 return -1;
  55.             }
  56.             return search(root.left, q);
  57.         } else {
  58.             if (root.right == null) {
  59.                 return -1;
  60.             }
  61.             return search(root.right, q);
  62.         }
  63.     }
  64.  
  65.     // 构建二叉搜索树的辅助方法
  66.     public void buildTree(BinarySet root, BinarySet added) {
  67.         if (added.x > root.x) {
  68.             if (root.left != null) {
  69.                 buildTree(root.left, added);
  70.             } else {
  71.                 root.left = added;
  72.             }
  73.         } else if (added.y > root.y) {
  74.             if (root.right != null) {
  75.                 buildTree(root.right, added);
  76.             } else {
  77.                 root.right = added;
  78.             }
  79.         }
  80.     }
  81. }

18

使用了一个二维数组 val 来记录每个数位和对应的最大两个值。在遍历数组时，对每个数字计算数位和，并更新 val 数组中的值。最后，遍历 val 数组，找到最大的两个值的和。

这个算法的时间复杂度是 O(n)，其中 n 是数组的长度。使用了数组来记录每个数位和对应的最大两个值，避免了排序的开销。

  1. class Solution {
  2.     public int maximumSum(int[] nums) {
  3.         int[][] val = new int[100][2];
  4.         for (int x : nums) {
  5.             int t = x, cur = 0;
  6.             while (t != 0) {
  7.                 cur += t % 10;
  8.                 t /= 10;
  9.             }
  10.             if (x >= val[cur][1]) { // 最大沦为次大, 更新最大
  11.                 val[cur][0] = val[cur][1];
  12.                 val[cur][1] = x;
  13.             } else if (x > val[cur][0]) { // 更新次大
  14.                 val[cur][0] = x;
  15.             }
  16.         }
  17.         int ans = -1;
  18.         for (int i = 0; i < 100; i++) {
  19.             if (val[i][0] != 0 && val[i][1] != 0) ans = Math.max(ans, val[i][0] + val[i][1]);
  20.         }
  21.         return ans;
  22.     }
  23. }

19

689. 三个无重叠子数组的最大和 - 力扣（LeetCode）

使用了动态规划的思想，首先计算以每个点为起始的长度为 k 的子数组的和，然后计算左右两侧的最大值下标，最后遍历中间子数组的起始位置，计算三个子数组的和，更新最大和及其对应的下标。

  1. class Solution {
  2.   public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
  3.     int n = nums.length;
  4.     int currentSum = 0;
  5.     for(int i = 0 ; i < k - 1; i ++ ) {
  6.       currentSum += nums[i];
  7.     }
  8.     int sz = n - k + 1;
  9.     int[] arr = new int[sz];
  10.     Arrays.fill(arr, 0);
  11.     for(int i = k - 1 ; i < n ; i ++ ) {
  12.       currentSum = currentSum + nums[i];
  13.       if(i >= k) {
  14.         currentSum -= nums[i-k];
  15.       }
  16.       arr[i-k+1] = currentSum;
  17.     }
  18.     /**
  19.      * 现在我们得到了从每个点起始的k个元素的和
  20.      * 需要知道如何选择起始点，a,b,c 使得他们的和最大
  21.      * 并且a + k <= b && b + k <= c
  22.      */
  23.  
  24.  
  25.     // prefix: 某个节点之前的最大值下标，suffix：之后
  26.     int[] suffix = new int[sz];
  27.     int[] prefix = new int[sz];
  28.     prefix[0] = 0;
  29.     suffix[sz-1] = sz-1;
  30.     for(int i = 1 ; i < sz ; i ++ ) {
  31.       int prevPrefix = prefix[i-1];
  32.       int nextSuffix = suffix[sz-i];
  33.       if(arr[i] > arr[prevPrefix]) {
  34.         prefix[i] = i;
  35.       } else {
  36.         prefix[i] = prevPrefix;
  37.       }
  38.  
  39.       if(arr[sz-i-1] >= arr[nextSuffix]) {
  40.         suffix[sz-i-1] = sz-i-1;
  41.       } else {
  42.         suffix[sz-i-1] = nextSuffix;
  43.       }
  44.     }
  45.     int ans = -1;
  46.     int l=0, m=0, r=0;
  47.     for(int mid = k ; mid + k < sz ; mid ++ ) {
  48.       int left = mid - k ;
  49.       int right = mid + k;
  50.       int sum = arr[prefix[left]] + arr[mid] + arr[suffix[right]];
  51.       if(sum > ans) {
  52.         ans = sum;
  53.         l = prefix[left] ;
  54.         r = suffix[right];
  55.         m = mid;
  56.       }
  57.     }
  58.     // System.out.println(ans);
  59.     return new int[]{l, m, r};
  60.   }
  61. }

20

53. 最大子数组和 - 力扣（LeetCode）

采用了动态规划的思想。在遍历数组的过程中，通过不断更新 count 变量，记录当前连续子数组的和，并将其与当前元素的值比较，选择较大的值。同时，使用 ans 变量记录遍历过程中的最大子数组和。最终返回 ans 即为数组的最大子数组和。

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int ans = Integer.MIN_VALUE;
  4.         int count = 0;
  5.         
  6.         // 遍历数组
  7.         for (int i = 0; i < nums.length; i++) {
  8.             // 更新当前连续子数组的和，如果之前的和为负数，则从当前元素开始重新计算
  9.             count = Math.max(count + nums[i], nums[i]);
  10.             
  11.             // 更新最大和
  12.             ans = Math.max(ans, count);
  13.         }
  14.         
  15.         return ans;
  16.     }
  17. }

21

2216. 美化数组的最少删除数 - 力扣（LeetCode）

 

通过维护 pos 变量记录当前操作的位置，curPos 指针遍历数组。当 pos 为偶数时，尝试删除相邻的相同元素，如果删除后的数组没有相邻的相同元素，pos 加 1；当 pos 为奇数时，直接移动到下一个位置。最终，根据剩余元素的奇偶性返回删除的元素个数。 

  1. class Solution {
  2.     public int minDeletion(int[] nums) {
  3.         int len = nums.length;
  4.         int pos = 0;      // 记录当前操作的位置
  5.         int curPos = 0;   // 遍历数组的指针
  6.  
  7.         // 遍历数组
  8.         while (curPos < len) {
  9.             if ((pos & 1) == 0) {
  10.                 // 当 pos 为偶数时，尝试删除相邻的相同元素
  11.                 if (curPos + 1 == len || nums[curPos] != nums[curPos + 1]) {
  12.                     pos++;
  13.                 }
  14.             } else {
  15.                 // 当 pos 为奇数时，直接移动到下一个位置
  16.                 pos++;
  17.             }
  18.             curPos++;
  19.         }
  20.  
  21.         int delCount = curPos - pos;  // 计算删除的元素个数
  22.         return ((len - delCount) & 1) == 0 ? delCount : delCount + 1;  // 判断最终剩余元素的奇偶性
  23.     }
  24. }

 22

 2304. 网格中的最小路径代价 - 力扣（LeetCode）

 

动态规划算法，用于计算从二维网格底部到顶部的最小路径代价。通过迭代从倒数第二行到第一行，计算每个位置的最小代价，最终得到从顶部到底部的最小路径代价。

  1. class Solution {
  2.     public int minPathCost(int[][] grid, int[][] moveCost) {
  3.         int m = grid.length, n = grid[0].length;
  4.  
  5.         // 从倒数第二行迭代到第一行
  6.         for (int i = m - 2; i >= 0; i--) {
  7.             for (int j = 0; j < n; j++) {
  8.                 int[] cost = moveCost[grid[i][j]];  // 获取当前单元格的移动成本
  9.                 int res = Integer.MAX_VALUE;
  10.  
  11.                 // 找到下一行的最小成本
  12.                 for (int k = 0; k < n; k++) {
  13.                     res = Math.min(res, grid[i + 1][k] + cost[k]);
  14.                 }
  15.  
  16.                 // 使用最小成本更新当前单元格
  17.                 grid[i][j] += res;
  18.             }
  19.         }
  20.  
  21.         // 从第一行找到最小成本
  22.         int ans = Integer.MAX_VALUE;
  23.         for (int res : grid[0]) {
  24.             ans = Math.min(ans, res);
  25.         }
  26.  
  27.         return ans;
  28.     }
  29. }

23

1410. HTML 实体解析器 - 力扣（LeetCode）

  1. class Solution {
  2.     
  3.     private static char[][] key = {{'q','u','o','t'}, {'a', 'p', 'o', 's'} , {'a', 'm', 'p'}, {'g', 't'}, {'l', 't'}, {'f', 'r', 'a', 's', 'l'}};
  4.     private static int[] len = {5, 5, 4, 3, 3, 6};
  5.     private static char[] value = {'\"', '\'', '&', '>', '<', '/'};
  6.     
  7.     static char[] result;
  8.     public String entityParser(String text) {
  9.         
  10.         char[] cs = text.toCharArray();
  11.         int n = cs.length;
  12.         result = new char[n];
  13.         int index = 0;
  14.         
  15.         for (int i = 0; i < n; i++) {
  16.             
  17.             if (cs[i] == '&' && i + 3 < n) { 
  18.                 boolean special = false;
  19.                 for (int j = 0; j < 6; j++) {
  20.                     if(i + len[j] + 1 > n || cs[i + len[j] ] != ';') continue;
  21.                     if (isSpecial(cs, i + 1, key[j])) { 
  22.                         result[index++]= value[j];
  23.                         i += len[j];
  24.                         special = true;
  25.                         break;
  26.                     }
  27.                 }
  28.                 if (!special)
  29.                    result[index++]= cs[i];
  30.             }else
  31.           
  32.                result[index++]= cs[i];
  33.          
  34.         }
  35.         return new String(result, 0, index);
  36.     }
  37.  
  38.     private boolean isSpecial(char[] cs, int i, char[] target) {
  39.         for (char c : target) 
  40.             if (cs[i++] != c) return false;
  41.         
  42.         return true;
  43.     }
  44. }

24

2824. 统计和小于目标的下标对数目 - 力扣（LeetCode）

双重循环n方 

  1. class Solution {
  2.     public int countPairs(List<Integer> nums, int target) {
  3.         int n = nums.size(), ans = 0;
  4.         for (int i = 0; i < n - 1; i++) 
  5.             for (int j = i + 1; j < n; j++)
  6.                 if (nums.get(i) + nums.get(j) < target)
  7.                     ans++;
  8.         return ans;
  9.     }
  10. }

先排好序 

  1. class Solution {
  2.     public int countPairs(List<Integer> nums, int target) {
  3.         int[] numsArray = new int[nums.size()];
  4.         for (int i = 0; i < nums.size(); i++) {
  5.             numsArray[i] = nums.get(i);
  6.         }
  7.  
  8.         Arrays.sort(numsArray);
  9.  
  10.         int cnt = 0;
  11.  
  12.         int start = 0;
  13.         while (start < numsArray.length) {
  14.             int end = start + 1;
  15.             while (end < numsArray.length && numsArray[start] + numsArray[end] < target) {
  16.                 cnt++;
  17.                 end++;
  18.             }
  19.             start++;
  20.         }
  21.  
  22.         return cnt;
  23.     }
  24. }

25

1457. 二叉树中的伪回文路径 - 力扣（LeetCode）

使用 status 变量来表示当前路径中每个数字的出现次数的奇偶性。通过异或运算 (^) 来更新状态。如果路径的某个数字出现次数为奇数，那么对应位上的状态就是1，否则是0。

在叶子节点处，通过判断 status 是否是 status & (-status)，如果是，则说明路径中最多只有一个数字出现次数为奇数，即可以构成伪回文路径。

递归过程中，将左右子树的状态相加，最终得到从根节点到叶子节点的伪回文路径数量。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     // 主函数，计算伪回文路径的数量
  18.     public int pseudoPalindromicPaths(TreeNode root) {
  19.         return dfs(root, 0);
  20.     }
  21.  
  22.     // 递归函数，计算以当前节点为起点的伪回文路径的数量
  23.     public int dfs(TreeNode cur, int status) {
  24.         if (cur == null) {
  25.             return 0;
  26.         }
  27.         // 使用异或运算更新当前节点的状态
  28.         status ^= 1 << cur.val;
  29.         // 如果当前节点是叶子节点，判断路径是否为伪回文路径
  30.         if (cur.left == null && cur.right == null) {
  31.             return status == (status & (-status)) ? 1 : 0;
  32.         }
  33.         // 递归遍历左右子树
  34.         return dfs(cur.left, status) + dfs(cur.right, status);
  35.     }
  36. }

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     int ans = 0;
  18.     public int pseudoPalindromicPaths (TreeNode root) {
  19.         dfs(root,0);
  20.         return ans;
  21.     }
  22.     public void dfs(TreeNode root, int status){
  23.         if(root == null){
  24.             return ;
  25.         }        
  26.         status ^= 1 << root.val;
  27.         if(root.left == null && root.right == null){
  28.             if(status == 0 || (status&(status-1))==0){
  29.                 ans++;
  30.             }
  31.         }
  32.         if(root.left!=null) dfs(root.left, status);
  33.         if(root.right!=null) dfs(root.right, status);
  34.     }
  35. }

26

828. 统计子串中的唯一字符 - 力扣（LeetCode）

  1. class Solution {
  2.     public int uniqueLetterString(String s) {
  3.         // 假设一个字母出现 2 次或者3 次，下标分别为 i，j，k，这里相当于记录 i 的下标
  4.         // 出现 2 次的时候 i 相当于 -1。
  5.         int[] prePreIndex = new int[128];
  6.         int[] preIndex = new int[128];// 这里相当于记录 j 的下标
  7.         Arrays.fill(prePreIndex, -1);
  8.         Arrays.fill(preIndex, -1);
  9.         char[] chars = s.toCharArray();
  10.         int res = 0;
  11.         for (int i = 0; i < chars.length; i++) {
  12.             int cur = chars[i];
  13.             // 这里只计算一个字母出现 2 次以及 2 次以上的（不包含最后一个字母构成的个数）。
  14.             if (preIndex[cur] > -1)
  15.                 res += (preIndex[cur] - prePreIndex[cur]) * (i - preIndex[cur]);
  16.             // 更新 prePreIndex 和 preIndex 。
  17.             prePreIndex[cur] = preIndex[cur];
  18.             preIndex[cur] = i;
  19.         }
  20.         // 这里再来计算字母只出现 1 次的情况以及重复的时候最后一个字母构成的个数。
  21.         for (int i = 0; i < 128; i++) {
  22.             if (preIndex[i] > -1)
  23.                 res += (preIndex[i] - prePreIndex[i]) * (s.length() - preIndex[i]);
  24.         }
  25.         return res;
  26.     }
  27. }

27 

907. 子数组的最小值之和 - 力扣（LeetCode）

  1. class Solution {
  2.     public int sumSubarrayMins(int[] arr) {
  3.         long result = 0;
  4.         int[] stack = new int[arr.length]; // 使用数组结构模拟堆栈，里面存储arr数组的下标，为了便于计算“管辖区域”的跨度
  5.         int head = 0, tail = head, mod = (int) (1e9 + 7); // 配合模拟堆栈的head指针和tail指针
  6.         for (int i = 0; i <= arr.length; i++) {
  7.             int num = (i == arr.length) ? 0 : arr[i]; // 如果arr数组遍历到最后一个元素，则还需要模拟结尾元素0，为了让stack中元素都出栈
  8.             while (head != tail && arr[stack[tail - 1]] > num) {
  9.                 int n = stack[--tail]; // 待计算数字arr[n]的【数组下标】
  10.                 int h = (head != tail) ? stack[tail - 1] : -1; // arr[n]的“辐射区域”head头的【数组下标】（开区间）
  11.                 int t = i; // arr[n]的“辐射区域”tail尾的【数组下标】（开区间）
  12.                 result = (result + (long) (n - h) * (t - n) * arr[n]) % mod;
  13.             }
  14.             stack[tail++] = i;
  15.         }
  16.         return (int) result;
  17.     }
  18. }

28

1670. 设计前中后队列 - 力扣（LeetCode）

  1. class FrontMiddleBackQueue {
  2.     LinkedList<Integer> preq;
  3.     LinkedList<Integer> proq;
  4.     int pren,pron;
  5.     public FrontMiddleBackQueue() {
  6.         pren=0;
  7.         pron=0;
  8.         preq=new LinkedList<Integer>();
  9.         proq=new LinkedList<Integer>();
  10.     }
  11.     
  12.     public void pushFront(int val) {
  13.         preq.offerFirst(val);
  14.         pren++;
  15.         if(pren>pron){
  16.             proq.offerFirst(preq.pollLast());
  17.             pren--;
  18.             pron++;
  19.         }
  20.     }
  21.     
  22.     public void pushMiddle(int val) {
  23.         preq.offerLast(val);
  24.         pren++;
  25.         if(pren>pron){
  26.             proq.offerFirst(preq.pollLast());
  27.             pren--;
  28.             pron++;
  29.         }
  30.     }
  31.     
  32.     public void pushBack(int val) {
  33.         proq.offerLast(val);
  34.         pron++;
  35.         if(pron>pren+1){
  36.             preq.offerLast(proq.pollFirst());
  37.             pren++;
  38.             pron--;
  39.         }
  40.     }
  41.     
  42.     public int popFront() {
  43.         int res=-1;
  44.         if(preq.isEmpty()&&!proq.isEmpty()){
  45.             res=proq.pollFirst();
  46.             pron--;
  47.         }else if(!preq.isEmpty()){
  48.             res=preq.pollFirst();
  49.             pren--;
  50.             if(pron>pren+1){
  51.                 preq.offerLast(proq.pollFirst());
  52.                 pren++;
  53.                 pron--;
  54.             }
  55.         }
  56.         // System.out.println(res);
  57.         return res;
  58.     }
  59.     
  60.     public int popMiddle() {
  61.         int res=-1;
  62.         if(pron>pren){
  63.             res=proq.pollFirst();
  64.             pron--;
  65.         }else if(pron==pren&&pron!=0){
  66.             res=preq.pollLast();
  67.             pren--;
  68.             if(pron>pren+1){
  69.                 preq.offerLast(proq.pollFirst());
  70.                 pren++;
  71.                 pron--;
  72.             }
  73.         }
  74.         // System.out.println(res);
  75.         return res;
  76.     }
  77.     
  78.     public int popBack() {
  79.         int res=-1;
  80.         if(!proq.isEmpty()){
  81.             res=proq.pollLast();
  82.             pron--;
  83.             if(pren>pron){
  84.                 proq.offerFirst(preq.pollLast());
  85.                 pren--;
  86.                 pron++;
  87.             }
  88.         }
  89.         // System.out.println(res);
  90.         return res;
  91.     }
  92. }
  93.  
  94. /**
  95.  * Your FrontMiddleBackQueue object will be instantiated and called as such:
  96.  * FrontMiddleBackQueue obj = new FrontMiddleBackQueue();
  97.  * obj.pushFront(val);
  98.  * obj.pushMiddle(val);
  99.  * obj.pushBack(val);
  100.  * int param_4 = obj.popFront();
  101.  * int param_5 = obj.popMiddle();
  102.  * int param_6 = obj.popBack();
  103.  */

29

2336. 无限集中的最小数字 - 力扣（LeetCode）

  1. class SmallestInfiniteSet {
  2.     boolean[] used;
  3.     int idx;
  4.     public SmallestInfiniteSet(){
  5.         used = new boolean[1001];
  6.         idx = 1;
  7.     }
  8.  
  9.     public int popSmallest(){
  10.         while(used[idx]) ++idx;
  11.         used[idx] = true;
  12.         return idx;
  13.     }
  14.  
  15.     public void addBack(int num){
  16.         if(used[num]) used[num] = false;
  17.         if(idx > num) idx = num;
  18.     }
  19. }
  20.  
  21. /**
  22.  * Your SmallestInfiniteSet object will be instantiated and called as such:
  23.  * SmallestInfiniteSet obj = new SmallestInfiniteSet();
  24.  * int param_1 = obj.popSmallest();
  25.  * obj.addBack(num);
  26.  */

30

1657. 确定两个字符串是否接近 - 力扣（LeetCode）

长度相等 字符集相等 频率数组相等

  1. class Solution {
  2.     public boolean closeStrings(String word1, String word2) {
  3.         int n = word1.length();
  4.         if (n != word2.length())  return false;    
  5.         if (word1.equals(word2))  return true;   
  6.  
  7.         int[] count1 = new int[128];     
  8.         int[] count2 = new int[128];    
  9.         byte[] bytes = new byte[n];
  10.         word1.getBytes(0, n, bytes, 0);     // Faster than String.toCharArray().
  11.         for (byte b : bytes)  count1[b]++;
  12.         
  13.         word2.getBytes(0, n, bytes, 0);
  14.         for (byte b : bytes) count2[b]++;
  15.         
  16.         int maxFreq = 0;
  17.         for (int i = 'a'; i <= 'z'; i++)
  18.             maxFreq = Math.max(maxFreq, Math.max(count1[i], count2[i]));
  19.  
  20.         byte[] freq = new byte[maxFreq + 1];    
  21.         int count = 0;
  22.         for (int i = 'a'; i <=  'z'; i++) {
  23.             int c1 = count1[i];
  24.             int c2 = count2[i];
  25.             if (c1 == 0 ^ c2 == 0)  return false;   
  26.             if (c1 == 0) continue;
  27.             int f1 = ++freq[c1];
  28.             int f2 = --freq[c2];
  29.             if (f1 == 1)  count++;  else  if (f1 == 0)  count--;
  30.             if (f2 == -1)  count++;  else  if (f2 ==  0)  count--;
  31.             
  32.         }
  33.       
  34.         return count == 0;     
  35.   
  36.     }
  37. }

总结

写完这一个月，老实说我觉得收获不大，每天都是不一样的题型，还是得系统性刷才有效果。然后我觉得我刷题还不太行，稍微难一点就是cv侠了，还要加油啊，下个月继续吧。当然这个我之后还要再都看一遍的。

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/796066
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号