基本用法

基础篇：https://www.flandre.ltd/java/
数据结构篇幅： https://www.flandre.ltd/数据结构/

排序

• java数组排序Collections.sort()；
• 已经排序好的数组合并使用双指针比较最前端数字- https://leetcode.cn/problems/merge-sorted-array/

算法

栈

• 可以先向栈中存入"-1"，这样可以做到每次操作时先弹出并且判断一个元素。

快速幂

注意递归出口为n=0，因为幂可能为负数

• https://leetcode.cn/problems/powx-n/description/

二分法

• 可解决旋转排序数组问题，最后一个值很关键，比它大则在第一个递增区间，比它小则在第二个递增区间。
  1. 对于旋转数组，二分之后有一边必定有序，可进行分类讨论写题
  2. 索引为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

特别

字典排序

• 从右到左找到第一个右侧大于左侧的数
• 右侧的右侧找到最小大于原左侧的数，交换
• 将交换后右边排序