Loading... 省流(重点题)：滑动窗口最大值，找出字符串中第一个匹配项的下标 ## 目标和  思路：动态规划或者递归。背包问题变式题。 ```java class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int num : nums) { sum += num; } int diff = sum - target; if (diff < 0 || diff % 2 != 0) { return 0; } int n = nums.length, neg = diff / 2; int[][] dp = new int[n + 1][neg + 1]; dp[0][0] = 1; for (int i = 1; i <= n; i++) { int num = nums[i - 1]; for (int j = 0; j <= neg; j++) { dp[i][j] = dp[i - 1][j]; if (j >= num) { dp[i][j] += dp[i - 1][j - num]; } } } return dp[n][neg]; } } ``` ## 数组中重复数字  思路：刚开始以为直接hashset，没想到题中条件存在数范围问题，这样可以优化set方式，降低空间复杂度。 ```java class Solution { public int findRepeatNumber(int[] nums) { int i = 0; while(i < nums.length){ if(nums[i] == i){ i++; continue; } if(nums[nums[i]] == nums[i]) return nums[i]; int t = nums[i]; nums[i] = nums[t]; nums[t] = t; } return nums[0]; } } ``` ## 最大网络秩  思路：写的太丑了，直接邻接矩阵能方便很多。 ```java class Solution { public int maximalNetworkRank(int n, int[][] roads) { var dic = new HashMap<Integer, ArrayList<Integer>>(); for(int i = 0; i < roads.length; i++){ int a = roads[i][0]; int b = roads[i][1]; if(dic.containsKey(a)){ var t = dic.get(a); t.add(b); dic.put(a, t); }else{ var t = new ArrayList<Integer>(); t.add(b); dic.put(a, t); } if(dic.containsKey(b)){ var t = dic.get(b); t.add(a); dic.put(b, t); }else{ var t = new ArrayList<Integer>(); t.add(a); dic.put(b, t); } } int res = 0; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(dic.containsKey(i) && dic.containsKey(j)){ int l1 = dic.get(i).size(); int l2 = dic.get(j).size(); if(dic.get(i).contains(j)) res = Math.max(res, l1 + l2 - 1); else res = Math.max(res, l1 + l2); } } } return res; } } ``` ## 滑动窗口最大值  思路：单调队列模板题，实际上就是在每个窗口内进行单调栈处理。 ```java class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] q = new int[n]; int hh = 0; int tt = -1; // int n = nums.length; int[] res = new int[n - k + 1]; for(int i = 0; i < n; i++){ if(hh <= tt && i - k + 1 > q[hh]) hh++; while(hh <= tt && nums[q[tt]] <= nums[i]) tt--; q[++tt] = i; if(i - k + 1 >= 0) res[i - k + 1] = nums[q[hh]]; } return res; } } ``` ## 长度最小子数组  思路：滑动窗口模板题。 ```java class Solution { public int minSubArrayLen(int target, int[] nums) { int res = Integer.MAX_VALUE; int l = 0; int n = nums.length; int s = 0; for(int i = 0; i < n; i++){ s += nums[i]; while(s >= target){ res = Math.min(i - l + 1, res); s -= nums[l]; l++; } } return res == Integer.MAX_VALUE ? 0 : res; } } ``` ## 找出字符串中第一个匹配项的下标  思路：KMP模板题。尝试记忆一下算法，其实本身算法并不复杂，主要边界问题、细节需要加深理解（如j+1），核心在于next数组生成。 ```java class Solution { public int strStr(String haystack, String needle) { // int res = -1; int n = haystack.length(); int m = needle.length(); char[] hay = new char[n + 1]; char[] need = new char[m + 1]; int[] next = new int[m + 1]; for(int i = 1; i <=n; i++){ hay[i] = haystack.charAt(i-1); } for(int i = 1; i <=m; i++){ need[i] = needle.charAt(i-1); } for(int i = 2, j = 0; i <= m; i++){ while(j != 0 && need[j + 1] != need[i]) j = next[j]; if(need[j + 1] == need[i]) j++; next[i] = j; } for(int i = 1, j = 0; i <= n; i++){ while(j != 0 && hay[i] != need[j + 1]) j = next[j]; if(need[j + 1] == hay[i]) j++; if(j == m) return i - m; } return -1; } } ``` 最后修改：2023 年 04 月 28 日 © 允许规范转载 赞 3 如果觉得我的文章对你有用，请随意赞赏
3 条评论
真的是很厉害哎，菜狗仰慕大佬
🉑
学会了🐂🍺