本文最后更新于244 天前,其中的信息可能已经过时,如有错误请发送邮件到3368129372@qq.com
基本用法
基础篇:https://www.flandre.ltd/java/
数据结构篇幅: https://www.flandre.ltd/数据结构/
排序
- java数组排序Collections.sort();
- 已经排序好的数组合并使用双指针比较最前端数字- https://leetcode.cn/problems/merge-sorted-array/
算法
栈
- 可以先向栈中存入"-1",这样可以做到每次操作时先弹出并且判断一个元素。
快速幂
注意递归出口为n=0,因为幂可能为负数
二分法
- 可解决旋转排序数组问题,最后一个值很关键,比它大则在第一个递增区间,比它小则在第二个递增区间。
- 对于旋转数组,二分之后有一边必定有序,可进行分类讨论写题
- 索引为n-1的位置一定为最小值或者在最小值的右边
- 取中点可使用
mid=left+(right-left)/2
防止数据溢出。 - 最好不要在中间return结果,在最后出循环之后再return,每次循环的时候可以对ans进行更新。
回溯法
- 个人建议定义为void,使用return;直接回到上一层。
- 可使用iter遍历,stringBuilder的deleteCharAt(sb.length()-1)可快速删除最后一个字符)
- 可在递归出口相同的地方进行枝剪
- 传入的list为地址,可直接被修改,建议传入StringBuilder来进行答案的增减
-
dfs时,可把回溯结果设为boolean,方便从点看起
如下所示private boolean dfs(TreeNode node, TreeNode target, List<TreeNode> path) { if (node == null) { return false; } path.add(node); if (node.val == target.val) { return true; } if (dfs(node.left, target, path) || dfs(node.right, target, path)) { return true; } path.remove(path.size() - 1); return false; }
动态规划
- 先定义好dp[]到底代表着什么,数组之间有什么关系,数组与答案有什么关系。
位运算
- 寻找最低位的1
s = 101100 ~s = 010011 (~s)+1 = 010100 // 根据补码的定义,这就是 -s 最低 1 左侧取反,右侧不变 s & -s = 000100 // lowbit
- 巧用异或解决成对含单的问题
技巧
- for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) 可以对i与j一起进行遍历
- 需要对值与下表同时排序时,可以定义一个二维数组A[n][2],然后自定义Arrays.sort(A,(a,b)->a[0]==b[0]?a[0]-b[0]:a[1]-b[1]),实现升序
- 遇到多个区间的问题,可以对首元素进行排序,用堆存储末元素,这样遍历两次只需要根据首尾的状态就能够运算,而不用遍历这个区间的所有元素
- dfs递归时,把dfs放在操作的上面可以先遍历到底再一步一步挽回,放操作的下面则相反
- 树形dp,可把边存储为
List<Integer>[] g = new ArrayList[n]; for(int i=0;i<n;i++){ g[i] = new ArrayList<>(); } g[0].add(-1); for(int[] edge : edges){ g[edge[0]].add(edge[1]); g[edge[1]].add(edge[0]); }
注意不能用Arrays.fill填充g!!!不然填充的是同一个对象!!!
但是可以用:Arrays.setAll(g, e -> new ArrayList<>()); - 递归时设置begin与end,初始值为1-n
特别
字典排序
- 从右到左找到第一个右侧大于左侧的数
- 右侧的右侧找到最小大于原左侧的数,交换
- 将交换后右边排序