力扣知识点

滑动窗口思路构建滑动窗口只要窗口里面的字母和要求的字母每个数量一样就行public ListInteger findAnagrams(String s, String p) { int nrs.length(); int ncp.length(); if (nrnc){ return new ArrayList(); } ListInteger listnew ArrayList(); int[] s_intnew int[26]; int[] p_intnew int[26]; for (int i 0; i nc; i) { s_int[s.charAt(i)-a]; p_int[p.charAt(i)-a]; } if (Arrays.equals(s_int,p_int)){ list.add(0); } for (int i 0; i nr-nc; i) { s_int[s.charAt(i)-a]--; s_int[s.charAt(inc)-a]; if (Arrays.equals(s_int,p_int)){ list.add(i1); } } return list; }有点类似字符串的算法桶排序思路是用fre记录当前人物右边的所有人的身高然后再遍历fre从开始到当前人物的位置相加再当前人物入队就可以了。或者可以使用归并排序记录所有的逆序对数量。第三题我采取的思路是先用库自定义排序按照每个区间的左端点。之后进行合并代码如下public int[][] merge(int[][] intervals) { Arrays.sort(intervals, new Comparatorint[]() { Override public int compare(int[] o1, int[] o2) { return o1[0]-o2[0]; } }); Listint[] listnew ArrayList(); int nrintervals.length; for (int i 0; i nr; i) { int xintervals[i][0]; int yintervals[i][1]; int lasty; while (true){ i; if (i nr) { list.add(new int[]{x,last}); break; } int new_x intervals[i][0]; int new_y intervals[i][1]; if (last new_x) { last Math.max(last, new_y); }else { list.add(new int[]{x,last}); i--; break; } } } return list.toArray(new int[list.size()][]); }继续第四题有关这种题目既可以选择再开一个数组也可以选择就原地交换相应的数字要记住一点就是先把k处理一下k%len这里详细说明一点就是原地交换相应数字的方法public void rotate(int[] nums, int k) { int n nums.length; k k % n; int count gcd(k, n); for (int start 0; start count; start) { int current start; int prev nums[start]; do { int next (current k) % n; int temp nums[next]; nums[next] prev; prev temp; current next; } while (start ! current); } } public int gcd(int x, int y) { return y 0 ? gcd(y, x % y) : x; }这是力扣官方的做法笔者一开始的想法只是新开一个数组可以学习一下这种更快的方法。next是指当前的数字挪到哪个地方去然后用temp先存下来那个即将被覆盖的数字将那个数字填写为prevprev是提前存好的一开始的当前位置的数字。依次类推将所有的都改一下。第五题这个题有两种思路一种是借助额外的数组对于矩阵中第 i 行的第 j 个元素在旋转后它出现在倒数第 i 列的第 j 个位置。因此利用这个可以进行矩阵里面数字的转移力扣官方做法详见如下。class Solution { public void rotate(int[][] matrix) { int n matrix.length; int[][] matrix_new new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { matrix_new[j][n - i - 1] matrix[i][j]; } } for (int i 0; i n; i) { for (int j 0; j n; j) { matrix[i][j] matrix_new[i][j]; } } } }还有第二种做法是原地旋转不借助额外的数组。思路就是先上下对折再进行转置。class Solution { public void rotate(int[][] matrix) { int n matrix.length; // 水平翻转 for (int i 0; i n / 2; i) { for (int j 0; j n; j) { int temp matrix[i][j]; matrix[i][j] matrix[n - i - 1][j]; matrix[n - i - 1][j] temp; } } // 主对角线翻转 for (int i 0; i n; i) { for (int j 0; j i; j) { int temp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] temp; } } } }第六题回溯public class lc2 { ListListInteger ansnew ArrayList(); int[] c; int t; public ListListInteger combinationSum(int[] candidates, int target) { ccandidates; ttarget; ListInteger pathnew ArrayList(); dfs(0,path,0); return ans; } public void dfs(int num,ListInteger path,int pathSum){ if (pathSumt||numc.length){ return; } if (pathSumt){ ans.add(new ArrayList(path)); return; } path.add(c[num]); pathSumc[num]; dfs(num,path,pathSum); pathSumpathSum-path.getLast(); path.removeLast(); dfs(num1,path,pathSum); } }public void dfs(int num,ListInteger path,int pathSum){ if (pathSumt||numc.length){ return; } if (pathSumt){ ans.add(new ArrayList(path)); return; } path.add(c[num]); pathSumc[num]; dfs(num,path,pathSum); pathSumpathSum-path.getLast(); path.removeLast(); dfs(num1,path,pathSum); }这个肯定是重点这里面第一path是引用因此ans加入的时候需要拷贝一份。第二path.add(c[num]);pathSumc[num];dfs(num,path,pathSum);pathSumpathSum-path.getLast();path.removeLast();dfs(num1,path,pathSum);这个代码主体里面先选当前的再回溯再选num1这里不需要回溯是因为我们并没有修改path和pathsum。第七题机器人移动利用周长取模简化是一个力扣的每日一题class Robot { int width; int height; int[][] dir{{1,0},{0,1},{-1,0},{0,-1}}; int dir_num0; int x0; int y0; public Robot(int width, int height) { this.heightheight; this.widthwidth; } public void step(int num) { int perimeter 2 * (width height - 2); if (perimeter 0) { num num % perimeter; } for (int i 0; i num; i) { while (!check(x dir[dir_num][0], y dir[dir_num][1])) { dir_num (dir_num 1) % 4; } x dir[dir_num][0]; y dir[dir_num][1]; } } public boolean check(int nx,int ny){ if (nx0ny0nxwidthnyheight){ return true; }else { return false; } } public int[] getPos() { return new int[]{x,y}; } public String getDir() { if (x 0 y 0 dir_num 0) { return South; } return switch (dir_num) { case (0) - East; case (1) - North; case (2) - West; case (3) - South; default - ; }; } }对于这个题主要是如果走的步数一长的话那机器人就会绕着周长转圈因此可以用这个来简化运算第8题生成括号回溯核心主要是不能写成左括号数量小于n的时候加左括号右括号数量小于n的时候加右括号应该写成右括号的数量小于左括号的时候才加右括号第九题上下左右的遍历dfs(board,word,len,xdir[0][0],ydir[0][1]); dfs(board,word,len,xdir[1][0],ydir[1][1]); dfs(board,word,len,xdir[2][0],ydir[2][1]); dfs(board,word,len,xdir[3][0],ydir[3][1]);这种遍历需要用一个visited标记一下不重复走