算法思想：

双指针：

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

应用场景：

满足单调性(指针在移动的过程中，待衡量的量总是朝一个方向变化)

同向双指针：

3. 无重复字符的最长子串

209. 长度最小的子数组

713. 乘积小于 K 的子数组

相向双指针：

167. 两数之和 II - 输入有序数组

15. 三数之和

11. 盛最多水的容器

42. 接雨水

前缀和技巧

// 二维前缀和模板（'A' 的 ASCII 码最低位为 1，'.' 的 ASCII 码最低位为 0）
class MatrixSum {
  private final int[][] sum;
  public MatrixSum(String[] matrix) {
      int m = matrix.length, n = matrix[0].length();
      sum = new int[m + 1][n + 1];
      for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
              sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (matrix[i].charAt(j) & 1);
          }
      }
  }

  // 返回左上角在 (r1,c1) 右下角在 (r2-1,c2-1) 的子矩阵元素和（类似前缀和的左闭右开）
  public int query(int r1, int c1, int r2, int c2) {
      return sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
  }
}

二分查找

有两种计算中值 m 的方式：

m = (l + h) / 2
m = l + (h - l) / 2

l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。

//如果while中是 l <= h 的话，那么下面也要对应的 l = m + 1; r = m - 1
//如：
while(l <= h){
    int mid = l + (h - l)/2;
    if(nums[mid] < target){
        l = mid + 1;
    }else if(nums[mid] >= target){
        if(nums[mid] == target){tag = true;}
        h = mid - 1;
    }
}

//如果是  l < h 的话，那么下面只需要出现一个 {l = m + 1  and  r = m}  或者  {l = m  and  r = m - 1}!

1011. 在 D 天内送达包裹的能力

//这题好妙，本菜鸟根本想不到这题还能二分，长见识了！

我们对运载能力进行讨论：对于某运载能力，

如果此运载能力下需要的天数大于系统所述的天数，那么需要提高运载能力；

如果运载能力下需要的天数小于系统所述的天数，那么需要降低运载能力；

public int shipWithinDays(int[] weights, int days) {
        // 确定二分查找左右边界
        int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
        while (left < right) {
            int mid = (left + right) / 2;
            // need 为需要运送的天数
            // cur 为当前这一天已经运送的包裹重量之和
            int need = 1, cur = 0;
            for (int weight : weights) {
                if (cur + weight > mid) {
                    ++need;
                    cur = 0;
                }
                cur += weight;
            }
			//因为要求最小的运载能力，所以我们在得到符合条件所述天数的运载能力时，要再往小的运载能力那边试试
            if (need <= days) {			
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

2616. 最小化数对的最大差值

与上一题思路相同：

🌟看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。

为什么？一般来说，二分的值越大，越能/不能满足要求；二分的值越小，越不能/能满足要求，有单调性，可以二分。

在这一题中，我们对 最大差值的最小值 进行二分(左边界为两数相等的差值：0；右边界为最大值与最小值的差值)对于某一最大差值的最小值 mid：如果满足差值小于mid 的数对数量大于p，则应当减小mid(满足的太多了，要让条件严格一些)，否则反之。

public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int n = nums.length, left = -1, right = nums[n - 1] - nums[0]; // 开区间
        while (left + 1 < right) { // 开区间
            int mid = (left + right) >>> 1, cnt = 0;
            for (int i = 0; i < n - 1; ++i)
                if (nums[i + 1] - nums[i] <= mid) { // 都选
                    ++cnt;
                    ++i;
                }
            if (cnt >= p) right = mid;
            else left = mid;
        }
        return right;
    }

作者：endlesscheng
链接：https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/solution/er-fen-da-an-tan-xin-by-endlesscheng-dlxv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

分治：

241. 为运算表达式设计优先级

public List<Integer> diffWaysToCompute(String input) {
    List<Integer> ways = new ArrayList<>();
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        if (c == '+' || c == '-' || c == '*') {
            List<Integer> left = diffWaysToCompute(input.substring(0, i));
            List<Integer> right = diffWaysToCompute(input.substring(i + 1));
            for (int l : left) {
                for (int r : right) {
                    switch (c) {
                        case '+':
                            ways.add(l + r);
                            break;
                        case '-':
                            ways.add(l - r);
                            break;
                        case '*':
                            ways.add(l * r);
                            break;
                    }
                }
            }
        }
    }
    if (ways.size() == 0) {
        ways.add(Integer.valueOf(input));
    }
    return ways;
}
//真的太优美了！

95. 不同的二叉搜索树 II

public List<TreeNode> generateTrees(int n) {
        if (n < 1) {
            return new LinkedList<TreeNode>();
        }
        return generate(1,n);
    }
    
    public List<TreeNode> generate(int start, int end){
        List<TreeNode> res = new ArrayList<TreeNode>();
        if(start > end){
            res.add(null);
            return res;
        }
        for(int i = start; i<=end; i++){
            List<TreeNode> left = generate(start, i - 1);
            List<TreeNode> right = generate(i + 1, end);
            for(TreeNode l: left){
                for(TreeNode r: right){
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }

做完这两道，感觉已经摸清了分治的底细！遍历特征点，左边和右边的不同情况排列组合得到多种结果

搜索：

BFS：

在程序实现 BFS 时需要考虑以下问题：

队列：用来存储每一轮遍历得到的节点；
标记：对于遍历过的节点，应该将它标记，防止重复遍历。

LinkedList<>() 的API：poll获取并删除队头元素；offer向队尾添加元素

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)){
            return 0;
        }
        if (beginWord.equals(endWord))return 1;
        int res = 1;
        //标记
        HashSet<String> hashset = new HashSet<>();
        //bfs
        LinkedList<String> queue = new LinkedList();
        queue.offer(beginWord);
        hashset.add(beginWord);
        while(queue.size() != 0){
            int sz = queue.size();
            res++;
            while(sz-- != 0){
                String word = queue.poll();
//                if(word.equals(endWord))return res;
//                res++;
//                if(hashset.contains(word))continue;
                for(String s:wordList){
                    if(judge(word,s) && !hashset.contains(s)){
                        queue.offer(s);
                        if(s.equals(endWord))return res;
                        // System.out.println(word + "->" +s);
                        hashset.add(s);
                    }
                }
            }
        }
        return 0;

    }
    //需要写一个方法，来判断两个字符串的差异是否为一个字符
    boolean judge (String s1, String s2){
        if(s1.length() != s2.length())return false;
        int count = 0;
        for(int i = 0; i < s1.length(); i++){
            if(s1.charAt(i) != s2.charAt(i))count++;
            if(count > 1)return false;
        }
        return count == 1;
    }

DFS:

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。

在程序实现 DFS 时需要考虑以下问题：

栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

//套路格式
class Solution {
    int [][] direction =  new int[][]{{0,1},{0,-1},{1,0},{-1,0}};	//方向，视题目而定
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                res = Math.max(res, dfs(grid, i, j));
            }
        }
        return res;
    }
    int dfs(int [][] grid, int i, int j){
      	//出界或者已经到达过
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0){
            return 0;
        }
        int addition = 1;
        grid[i][j] = 0;		//到达过的地点全部进行标记(不能再次到达)
        for(int k = 0; k < direction.length; k++){
            addition += dfs(grid, i + direction[k][0], j + direction[k][1]);
        }
        return addition;
    }
}

回溯：

回溯做题三问：

当前的操作是什么
当前操作对应的子问题是什么
下一个子问题是什么

子集形回溯：

对每个点进行选择：选 or 不选

或者从答案的角度：如果选这个会满足条件再依此继续

组合型回溯：

有顺序要求可以进行剪枝

排列型回溯：

Backtracking（回溯）属于 DFS。

普通 DFS 主要用在 可达性问题 ，这种问题只需要执行到特点的位置然后返回即可。
而 Backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,’b’,’c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

对于一定规则下的排列组合问题，我们使用回溯法进行求解
回溯法 = dfs+回溯操作
	一般而言void dfs的参数如下(int n, <T>存储当前步骤生成的中间结果的变量,用于存储最终各种情况的变量[一般为一个ArrayList], 待进行操作的元素)；
	如：dfs(0,new StringBuilder(),res,s);
	dfs中刚开始写上终止条件：n到达指定轮数或不满足其他限制条件，直接return
	接下来根据当前存储的中间结果，再·给中间结果添加这轮得到的产物 ··对其进行下一轮dfs ···将这轮的产物删去，并换成这一轮产物的下一种情况！

//回溯模版：
//在回溯时，如果使用ArrayList等引用对象存放你产生的结果，在将其添加至结果集中时需要重新创建一个与其相同的副本，将副本加入结果集，如果不这样做，回溯后删除了元素会导致结果集中元素的改变。。
public List<List<Integer>> permute(int[] nums) {
  			if(nums.length == 0){
            return res;
        }
        List<List<Integer>> res = new ArrayList<>();
 			  ArrayList<Integer> curNum = new ArrayList<Integer>();
        boolean[] tag = new boolean[nums.length];
        dfs(curNum, tag, res, nums);
        return res;
    }
    void dfs(ArrayList<Integer> curNum,boolean[] tag, List<List<Integer>> res, int[] nums){
        if(curNum.size() == nums.length){
            res.add(new ArrayList<>(curNum));//##############################就说的是这里！！！！
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(!tag[i]){
                curNum.add(nums[i]);
                tag[i] = true;
                dfs(curNum, tag, res, nums);
                curNum.remove(curNum.size() - 1);
                tag[i] = false;
            }
        }
    }

对于排列问题：我们只需要遍历并回溯所有的情况并记录即可，

组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。

我们需要按照某种顺序(比如大小顺序)进行搜索，也就是“剪枝”

笔记的回溯第11、12、13、14、15题未做！

贪心：

适用范围：

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

两种常见思路：

排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

动态规划！

写到0-1背包第三题

链表：

纯链表操作的题目有很多都可以使用递归解决！

如：

//要求两两交换链表中的节点
public ListNode swapPairs(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    return next;
}

除了递归很常见以外，快慢指针的方法也很常见

如判断链表是否回文，可以使用快慢指针找到链表的中间(具体奇偶位再考虑)，再将链表分割位两个子链表，反转其一，如果两个子链表相等则回文！

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast != null) slow = slow.next;  // 偶数节点，让 slow 指向下一个节点
    cut(head, slow);                     // 切成两个链表
    return isEqual(head, reverse(slow));
}

private void cut(ListNode head, ListNode cutNode) {
    while (head.next != cutNode) {
        head = head.next;
    }
    head.next = null;
}

private ListNode reverse(ListNode head) {
    ListNode newHead = null;
    while (head != null) {
        ListNode nextNode = head.next;
        head.next = newHead;
        newHead = head;
        head = nextNode;
    }
    return newHead;
}

private boolean isEqual(ListNode l1, ListNode l2) {
    while (l1 != null && l2 != null) {
        if (l1.val != l2.val) return false;
        l1 = l1.next;
        l2 = l2.next;
    }
    return true;
}

树：

递归：

一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。

对树的操作，一般可以用递归解决：
//通用格式：
functionname ( TreeNode root ){
	if(root  == null){
    return xx;
  }  
  root.left = functionname(xxx);
  root.right = functionname(xxx);
  return xxx;
}


//例1:
private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return max;
}

private int depth(TreeNode root) {
    if (root == null) return 0;
    int leftDepth = depth(root.left);
    int rightDepth = depth(root.right);
    max = Math.max(max, leftDepth + rightDepth);
    return Math.max(leftDepth, rightDepth) + 1;
}
//例2:
public TreeNode invertTree(TreeNode root) {
        if(root == null){return root;}
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
}  
//例3:
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null){
            return null;
        }
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        TreeNode res = new TreeNode(root1.val + root2.val);
        res.left = mergeTrees(root1.left, root2.left);
        res.right = mergeTrees(root1.right, root2.right);
        return res;
    }

//例4:一种有点妙的格式：
public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
    if (t == null && s == null) return true;
    if (t == null || s == null) return false;
    if (t.val != s.val) return false;
    return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}

继续做前中后序遍历!

层次遍历：

广度优先即可

前中后序遍历：

BST：

Trie：

数组与矩阵：

看到：5. 有序矩阵的 Kth Element

图：

//java建图模板
	g = new ArrayList[n];
	Arrays.setAll(g, e -> new ArrayList<>() );
	for(var e : edges){
    int x = e[0], y = e[1];
    g[x].add(y);
    g[y].add(x);
  }

二分图：

如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么这个图就是二分图。

//判断是否是二分图⬇️

boolean judge = true;
   public boolean isBipartite(int[][] graph) {
       //color记录每个节点的颜色，0为还没被染色，1、2分别为两种颜色
       int color[] = new int[graph.length];
       //我认为应该深度遍历这个图，给遍历过的结点染色，
       //如果遇到已经染色的，看看如果和自己颜色相同，则不是二分图！
       for(int i = 0; i < graph.length; i++){
           //对于每棵子树，如果有一个节点被dfs过，那么如果可以构成二分子图的话，这颗子树上的所有节点都不必再进行dfs了，故此处只找还未被涂色的节点进行dfs！
           if(color[i] == 0) {
               dfs(graph, i, 1, color);
           }
       }
       return judge;
   }

   void dfs(int[][] graph, int i, int thisColor, int[] color){
       if(!judge)return;
       color[i] = thisColor;
       for(int j = 0; j < graph[i].length; j++){
           if(color[graph[i][j]] == 0){
               dfs(graph, graph[i][j], thisColor==1?2:1, color);
           }else{
               if(color[i] == color[graph[i][j]]){
                   judge = false;
                   return;
               }
           }
       }
   }

拓扑排序：

//将邻接矩阵转换为邻接表：
int[][] prerequisites //邻接矩阵
List<Integer>[] graphic = new List[numCourses];
for (int i = 0; i < numCourses; i++) {
    graphic[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
    graphic[pre[0]].add(pre[1]);
}


//方法1: 深度优先
/**
*定义三种状态：0->未搜索；1->搜索中；2->已完成
*遍历所有结点，对未搜索的结点进行dfs，
*对于dfs：先将该结点置为1状态，遍历所有该结点需要的结点，如果没有依赖的结点或者依赖的结点的状态都为2，则该结点也
*可以标记成2；如果该结点依赖的结点状态为0，则dfs依赖的结点；如果依赖的结点的状态为1，则说明存在环，不满足拓扑排
*序！
*/
//深度优先判断拓扑排序⬇️
    boolean loop = false;
    public int[] findOrderByDFS(int numCourses, int[][] prerequisites) {
        //1.构建图
        List<Integer>[] relation = new ArrayList[numCourses];
        for(int i = 0; i < numCourses; i++){
            relation[i] = new ArrayList<Integer>();
        }
        for(int[] arr: prerequisites){
            relation[arr[0]].add(arr[1]);
        }
        //构建数组，存放每门课程的状态0，1，2
        int[] status = new int[numCourses];
        LinkedList<Integer> stack = new LinkedList<>();//用于存放课程
        for(int i = 0; i < numCourses; i++){
            if(status[i] == 0){ //未搜索过，于是对其进行dfs搜索！
                dfs(i, relation, status,stack);
            }
        }
        if(loop){
            return new int[0];
        }
        int[] res = new int[numCourses];
        for(int i = numCourses - 1; i >= 0; i--){
            res[i] = stack.pop();
        }

        return res;

    }
    void dfs(int curCourse, List<Integer>[] relation, int[] status, LinkedList<Integer> stack){
        if(loop)return;
        status[curCourse] = 1;
        for(int next: relation[curCourse]){
            if(status[next] == 0){
                dfs(next, relation, status,stack);
            }else if(status[next] == 1){
                loop = true;
                return;
            }
        }
        stack.push(curCourse);
        status[curCourse] = 2;
    }



//方法2: 广度优先
	/**
	*将邻接矩阵转化为邻接表 其中：A需要B == B->A 因此 任务K入度为0表示K可以直接完成！
  *使用队列，将入度为0的任务添加至队列，遍历这些任务，将它们指向的队列的入度--；将操作后入度为0的再添加进队列
  *直到队列为空(如果从队列弹出的任务总数 < 总任务数，则说明图中有环，不能构成拓扑排序)
  */
//广度优先判断拓扑排序
    public int[] findOrderByBFS(int numCourses, int[][] prerequisites) {
        //1.构建图
        //广度优先，a需要b 则 b->a
        //每次记录入度为0的课程,因此需要创建数组记录每个课程的入度
        List<Integer>[] relation = new ArrayList[numCourses];
        int []inDegree = new int[numCourses];
        for(int i = 0; i < numCourses; i++){
            relation[i] = new ArrayList<Integer>();
        }
        for(int[] arr: prerequisites){
            relation[arr[1]].add(arr[0]);
            inDegree[arr[0]]++;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        //队列初始化：将所有入度为0的课程都加入queue
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                queue.offer(i);
            }
        }
        int[] res = new int[numCourses];
        int index = 0;
        //初始化完毕，开始常规bfs
        while(!queue.isEmpty()){
            int sz = queue.size();
            while(sz-- > 0){
                int curCourse = queue.poll();
                for(int i: relation[curCourse]){
                    inDegree[i]--;
                    if(inDegree[i] == 0){
                        queue.offer(i);
                    }
                }
                res[index++] = curCourse;
            }
        }
        return index == numCourses? res: new int[0];
    }

并查集：

并查集可以动态地连通两个点，并且可以非常快速地判断两个点是否连通。

/**
 *===============================并查集模板，可直接使用！！！=====================================
 * 数组模拟树，实现并查集。数组内的元素表示父亲的下角表，相当于指针。
 */
public class UnionFind {
    private int[] parent;
    private int size;
 
    public UnionFind(int size) {
        this.size = size;
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }
 
    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
        if (firstRoot == secondRoot) {
            return;
        }
        parent[firstRoot] = secondRoot;
    }
}



//并查集的应用：
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        UnionFind unionfind =  new UnionFind(edges.length + 1);
        for(int[] edge:edges){
            if(!unionfind.isConnected(edge[0],edge[1])){
                unionfind.unionElements(edge[0], edge[1]);
            }else{
                return edge;
            }
        }
        return null;

    }
}

寻找图中的最大环：

计数排序

用于值域较小的大量数字的排序，将各个数字的值与个数作为一个数组的下标和值通过遍历数组，累加arr[]的值 = k得到第k小的数字

桶排序：

设置若干个桶 bucket[i] 存储出现次数为i的数， bucket定义为 ArrayList[ ] 类型

快速选择：

平常人们选择数据中某个第几大的数据，往往使用先排序在选择的方法，这种方法的时间复杂度最快为Onlogn（快排时间复杂度），但在数据较大时往往会超出时间限制，故本次介绍时间复杂度为On的快速选择方法

快速选择算法：算法核心为递归和分治，和快速排序算法有一定的相似度，算法大概过程为
1.先判断区间的端点l,r和比较数pivot,pivot可取为arr[l],arr[r],arr[(l + r) / 2)]。

2.进行排序交换，使区间分为两部分，左边部分小于等于pivot，右边部分大于等于pivot。

3.递归排序左右边，当要求的第K个数,k >= sl，则递归排序右边，否则递归排序左边，如果区间只有一个数则返回。

public static int quickChoose(int l,int r,int [] arr,int k){
        //如果当前只有一个数存在
        if(l == r){
           return arr[l];
        }
        //否则进行排序和查找
        int i = l - 1,j = r + 1,pivot = arr[l];
        //本次返回j,j + 1
        //当前元素区间不止为一个数时
        while(i < j){
            while(arr[++i] < pivot);
            while(arr[--j] > pivot);
            //如果满足区间元素不为1
            if(i < j){
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //如果在左半部分，直接排序左边求解
        int s1 = j - l + 1;
        if(s1 >= k){
            return quickChoose(l,i - 1,arr,k);
        }else{
            //否则排序右边数组
            k = k - s1;
            return quickChoose( i,r,arr,k);
        }
    }

匈牙利算法：

匈牙利算法主要用来解决两个问题：求二分图的最大匹配数和最小点覆盖数。

求二分图最大连通数模版⬇️

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for(int i = 0; i < n; i++){
            int temp = in.nextInt();
            if(temp % 2 == 0){even.add(temp);}
            else{odd.add(temp);}
        }
        int count = 0;
        int [] match = new int [even.size()];
        if(odd.size() == 0 || even.size() == 0){ //缺少奇数或者偶数无法构成素数
            System.out.println(count);
            return;
        }
        for(int i: odd){
            boolean [] used = new boolean [even.size()];
            if(find(i,even, match, used))count++;
        }
        
        System.out.println(count);

    }

    private static boolean find(int i, List<Integer> even, int[] match,boolean [] used) {
        // TODO
        for(int j = 0; j < even.size(); j++){
            if(isPrime(i + even.get(j)) && !used[j]){
                used[j] = true;
                if(match[j] == 0 || find(match[j], even, match,used)){
                    match[j] = i;  
                    return true;
                }
            }
        }
        return false;
    }
    private static boolean isPrime(int n){
        if(n == 1) return false;
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0)return false;
        }
        return true;
    }
}

多路归并：

1	https://lfool.github.io/LFool-Notes/algorithm/多路归并技巧总结.html

21.合并两个有序链表(简单)
23.合并K个升序链表(困难)

每次从所有链表头中选择数值最小的值加入结果链表中即可。自己做时只使用了遍历的方法，但是发现大神们使用小根堆来获取最小的链表头部！
- 还可以使用归并的方法，(合并n个链表—–分半分半再分半—–>合并2个链表)，针对合并2个链表编写代码
- 还可以使用PriorityQueue优先队列，它自动将队列内的元素按照提供的重写的compare方法来排序，每次poll出最小的，再把它的next(如果有)放入队列

单调栈：

用于处理获取递增子序列之类的题目

遍历所给的数据，并维护一个栈，

比如现在需要找出长度为n的最小字典序子字符串

如果获得的数据比栈顶的小，则弹出栈顶，直到栈为空或栈顶元素小于所持元素， (这里还注意：因为我们需要的是长度为n的子序列，所以在我们每次想要pop的时候都需要判断：栈中元素以及未遍历的元素总数是否达到了了n，若>n，则允许pop)

最后将栈中的数据依次pop，再reverse一下即可

🌟TreeSet的使用：

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        TreeSet<Integer> treeSet = new TreeSet<>();
        in.next();
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            treeSet.add(in.nextInt());           
        }
        Iterator<Integer> tree = treeSet.iterator();
        while (tree.hasNext()){
            System.out.println(tree.next());
        }
}

//ceiling(E e)：返回大于等于给定元素的最小元素，如果不存在则返回 null。 
//  floor(E e)：返回小于等于给定元素的最大元素，如果不存在则返回 null。

System.arraycopy()的使用

/** 
* @param      src      the source array. 源数组
* @param      srcPos   starting position in the source array. 源数组的起始位置
* @param      dest     the destination array. 目标数组
* @param      destPos  starting position in the destination data. 目标数组的起始位置
* @param      length   the number of array elements to be copied. 复制的长度
*/
arraycopy(Object src,int srcPos,Object dest, int destPos, int length)；

动态规划：

1031. 两个非重叠子数组的最大和

1
2
3

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。
长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。
子数组是数组的一个 连续 部分。

使用动态规划：

dp1[ i ]表示前i个数中长度为firstLen的子数组的最大值 (若 i < firstLen)则dp1[ i ] = 前i个数之和

dp2[ i ]表示前i个数中长度为secondLen的子数组的最大值

我们得到dp1[ ]与dp2[ ]数组后，对于每个i，我们可以让res = Max{res, 数组1(firstLen)包含了最新的第i位，数组2(secondLen)包含了最新的第i位}

public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        int res = 0;
        int[] arr1 = new int[nums.length];
        int[] arr2 = new int[nums.length];
        arr1[0] = nums[0];
        arr2[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            arr1[i] = firstLen>i?nums[i]: Math.max(nums[i] - nums[i - firstLen],arr1[i - 1]);
            arr2[i] = secondLen>i?nums[i]: Math.max(nums[i] - nums[i - secondLen],arr2[i - 1]);
            if (firstLen + secondLen > i){
                res = nums[i];
            }else{
                res = Math.max(res, nums[i] - nums[i - firstLen] + arr2[i - firstLen]);
                res = Math.max(res, nums[i] - nums[i - secondLen] + arr1[i - secondLen]);
            }
        }
        return res;
    }

**1606自己做的超时了，答案的数据结构有点复杂，不知道什么时候有空再看看～

**2151 二进制枚举，有空来复盘！