面试中的算法-总结

开设这个专栏主要是在面试中算法避免一些踩坑，首先，经过我本人亲自实践+网上各位大佬总结:

当我们刷算法题的时候，比如力扣、牛客这些网站，很多的题目只需要我们写出函数体（核心代码），平台就可以自动帮助我们补齐输入输出，进行调试，但，在笔试和面试中，往往需要自己写出可以运行的完整代码（ACM模式），这个时候，需要我们去了解一下自己所使用的语言下的输入输出如何去设计。

Leetcode hot100题解以及平时学习的一些算法模板以及例题全部放到云盘，欢迎大家获取

https://www.123pan.com/s/e7ipTd-RUh5H.html

核心代码模式与ACM模式

当我们刷算法题的时候，比如力扣、牛客这些网站，很多的题目只需要我们写出函数体（核心代码），平台就可以自动帮助我们补齐输入输出，进行调试，但，在笔试和面试中，往往需要自己写出可以运行的完整代码（ACM模式），这个时候，需要我们去了解一下自己所使用的语言下的输入输出如何去设计。

首先给出几个注意事项：

1.笔试平台用的比较多的，比如牛客，赛码，可以提前去熟悉熟悉上面的操作。

2.有些笔试，需要自己写输入输出，有些，则不需要，但我们必须要把输入输出搞懂，这样就不怕是什么类型的笔试了，而且输入输出本身是不难的，学习一下就可以完全掌握。最好不要出现，算法题的核心思路会写，卡在了输入输出上，这样就很难受了。

3.有些笔试，还会让大伙自己设计测试用例，这个平时练习的时候也可以注意一下，主要核心的思想就是测试用例设计的几个原则。

4.不仅仅是笔试，有些面试，也会要求你写输入输出和测试用例。

面试手撕代码的几种形式

1.平台类

去面试官给定的平台上去面试，上面可以编写代码，调试和运行，这些平台有的写好了函数框架，有的是白板，需要自己写全部内容

2.自己的IDE

面试官要求候选人打开自己的ide，并共享桌面进行编写，这种肯定是要自己写全输入输出了

3.要求补齐测试用例

有些面试官，比如微软的面试官，可能会让你写完代码后，自己设计尽可能全面的测试用例，对你编写的代码进行测试。

java处理输入输出

然后我是javaer，所以就给出java的acm模式处理输入输出的方式:

因为我之前参加算法比赛中，一般都是对时间卡的比较严格，所以都是用java的快读快写，但是笔试或者面试中手撕，一般不会要求那么严格，或者测试用例比较少，所以我么们直接使用Scanner就完全够用了

情况1: 全都是数字的输入，每行数字个数不定

情况2:每行第一个数字为确定的数字n，后面跟着n个数字

情况3: 每行确定有n个数字的情况

情况4: 第一行是一个数字n, 第二行是n个字符串

避坑点

• 全局只能new出一个Scanner对象，如果有多个，会出现不可预见的问题！
• 关于next() 函数、nextInt()函数、nextLine()函数：

​ nextInt(): 只读取整数类型数据， nextInt()在读取完输入后把光标放在读取数据的同一行，该数据的后面。

​ next(): 只读取到空格，不能读取被空格分开的两个单词（也就是不能读取空格），并且在读取完后把光标放在读取数据的同一行，该数据的后面。（同上）

​ nextLine(): 读取整行的数据包括单词间的空格，到回车结束（也就是从开始读一整行包括回车），读取结束后，光标放在下一行开头。

总结:

不论是acm模式，还是核心代码模式，面试官考察的还是算法能力，要提高算法能力，说再多也没用，练就有效，像leetcode,牛客，洛谷，都是非常好的刷题网站，如果是零基础，并且要用java去应对笔试，我推荐去b站上搜索左程云老师，先入门，再刷题，每天坚持，无问西东。

各类算法模板(只提供JAVA):

只记录比较死的模板。各类算法模板学习自–左程云老师

更多java模板以及例题我已经上传至云盘，欢迎获取 https://www.123pan.com/s/e7ipTd-RUh5H.html

1.选择排序、插入排序、冒泡排序

public class SelectBubbleInsert {

        // 数组中交换i和j位置的数
        public static void swap(int[] arr, int i, int j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
        }

        // 选择排序
        public static void selectionSort(int[] arr) {
                if (arr == null || arr.length < 2) {
                        return;
                }
                for (int minIndex, i = 0; i < arr.length - 1; i++) {
                        minIndex = i;
                        for (int j = i + 1; j < arr.length; j++) {
                                if (arr[j] < arr[minIndex]) {
                                        minIndex = j;
                                }
                        }
                        swap(arr, i, minIndex);
                }
        }
        // 冒泡排序
        public static void bubbleSort(int[] arr) {
                if (arr == null || arr.length < 2) {
                        return;
                }
                for (int end = arr.length - 1; end > 0; end--) {
                        for (int i = 0; i < end; i++) {
                                if (arr[i] > arr[i + 1]) {
                                        swap(arr, i, i + 1);
                                }
                        }
                }
        }

        // 插入排序
        public static void insertionSort(int[] arr) {
                if (arr == null || arr.length < 2) {
                        return;
                }
                for (int i = 1; i < arr.length; i++) {
                        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                                swap(arr, j, j + 1);
                        }
                }
        }

}

2.二叉树及其三种序

public static class TreeNode {
                public int val;
                public TreeNode left;
                public TreeNode right;

                public TreeNode(int v) {
                        val = v;
                }
        }
 // 先序打印所有节点，递归版
        public static void preOrder(TreeNode head) {
                if (head == null) {
                        return;
                }
                System.out.print(head.val + " ");
                preOrder(head.left);
                preOrder(head.right);
        }

        // 中序打印所有节点，递归版
        public static void inOrder(TreeNode head) {
                if (head == null) {
                        return;
                }
                inOrder(head.left);
                System.out.print(head.val + " ");
                inOrder(head.right);
        }

        // 后序打印所有节点，递归版
        public static void posOrder(TreeNode head) {
                if (head == null) {
                        return;
                }
                posOrder(head.left);
                posOrder(head.right);
                System.out.print(head.val + " ");
        }
        
        // 先序打印所有节点，非递归版
        public static void preOrder(TreeNode head) {
                if (head != null) {
                        Stack<TreeNode> stack = new Stack<>();
                        stack.push(head);
                        while (!stack.isEmpty()) {
                                head = stack.pop();
                                System.out.print(head.val + " ");
                                if (head.right != null) {
                                        stack.push(head.right);
                                }
                                if (head.left != null) {
                                        stack.push(head.left);
                                }
                        }
                        System.out.println();
                }
        }

        // 中序打印所有节点，非递归版
        public static void inOrder(TreeNode head) {
                if (head != null) {
                        Stack<TreeNode> stack = new Stack<>();
                        while (!stack.isEmpty() || head != null) {
                                if (head != null) {
                                        stack.push(head);
                                        head = head.left;
                                } else {
                                        head = stack.pop();
                                        System.out.print(head.val + " ");
                                        head = head.right;
                                }
                        }
                        System.out.println();
                }
        }

        // 后序打印所有节点，非递归版
        // 这是用两个栈的方法
        public static void posOrderTwoStacks(TreeNode head) {
                if (head != null) {
                        Stack<TreeNode> stack = new Stack<>();
                        Stack<TreeNode> collect = new Stack<>();
                        stack.push(head);
                        while (!stack.isEmpty()) {
                                head = stack.pop();
                                collect.push(head);
                                if (head.left != null) {
                                        stack.push(head.left);
                                }
                                if (head.right != null) {
                                        stack.push(head.right);
                                }
                        }
                        while (!collect.isEmpty()) {
                                System.out.print(collect.pop().val + " ");
                        }
                        System.out.println();
                }
        }
        

3.归并排序

public static int[] sortArray(int[] nums) {
                if (nums.length > 1) {
                        // mergeSort1为递归方法
                        // mergeSort2为非递归方法
                        // 用哪个都可以
                        // mergeSort1(nums);
                        mergeSort2(nums);
                }
                return nums;
        }
public static int MAXN = 50001;
public static int[] help = new int[MAXN];
// 归并排序递归版
        public static void mergeSort1(int[] arr) {
                sort(arr, 0, arr.length - 1);
        }

        public static void sort(int[] arr, int l, int r) {
                if (l == r) {
                        return;
                }
                int m = (l + r) / 2;
                sort(arr, l, m);
                sort(arr, m + 1, r);
                merge(arr, l, m, r);
        }
        
        
 // 归并排序非递归版
        public static void mergeSort2(int[] arr) {
                int n = arr.length;
                for (int l, m, r, step = 1; step < n; step <<= 1) {
                        l = 0;
                        while (l < n) {
                                m = l + step - 1;
                                if (m + 1 >= n) {
                                        break;
                                }
                                r = Math.min(l + (step << 1) - 1, n - 1);
                                merge(arr, l, m, r);
                                l = r + 1;
                        }
                }
        }
        
        
        

        public static void merge(int[] arr, int l, int m, int r) {
                int i = l;
                int a = l;
                int b = m + 1;
                while (a <= m && b <= r) {
                        help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
                }
                while (a <= m) {
                        help[i++] = arr[a++];
                }
                while (b <= r) {
                        help[i++] = arr[b++];
                }
                for (i = l; i <= r; i++) {
                        arr[i] = help[i];
                }
        }

4.快速排序

public static int[] sortArray(int[] nums) {
         if (nums.length > 1) {
                 quickSort(nums, 0, nums.length - 1);
         }
         return nums;
 }
 // 随机快速排序
 public static void quickSort(int[] arr, int l, int r) {
         if (l >= r) {
                 return;
         }
         // 随机这一下，常数时间比较大
         // 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
         int x = arr[l + (int) (Math.random() * (r - l + 1))];
         partition(arr, l, r, x);
         // 为了防止底层的递归过程覆盖全局变量
         // 这里用临时变量记录first、last
         int left = first;
         int right = last;
         quickSort(arr, l, left - 1);
         quickSort(arr, right + 1, r);
 }
 // 荷兰国旗问题
 public static int first, last;

 // 已知arr[l....r]范围上一定有x这个值
 // 划分数组 <x放左边，==x放中间，>x放右边
 // 把全局变量first, last，更新成==x区域的左右边界
 public static void partition(int[] arr, int l, int r, int x) {
         first = l;
         last = r;
         int i = l;
         while (i <= last) {
                 if (arr[i] == x) {
                         i++;
                 } else if (arr[i] < x) {
                         swap(arr, first++, i++);
                 } else {
                         swap(arr, i, last--);
                 }
         }
 }
 
 public static void swap(int[] arr, int i, int j) {
         int tmp = arr[i];
         arr[i] = arr[j];
         arr[j] = tmp;
 }

5.含有嵌套的表达式求值

public static int calculate(String str) {
                where = 0;
                return f(str.toCharArray(), 0);
        }

        public static int where;

        // s[i....]开始计算，遇到字符串终止 或者 遇到)停止
        // 返回 : 自己负责的这一段，计算的结果
        // 返回之间，更新全局变量where，为了上游函数知道从哪继续！
        public static int f(char[] s, int i) {
                int cur = 0;
                ArrayList<Integer> numbers = new ArrayList<>();
                ArrayList<Character> ops = new ArrayList<>();
                while (i < s.length && s[i] != ')') {
                        if (s[i] >= '0' && s[i] <= '9') {
                                cur = cur * 10 + s[i++] - '0';
                        } else if (s[i] != '(') {
                                // 遇到了运算符 + - * /
                                push(numbers, ops, cur, s[i++]);
                                cur = 0;
                        } else {
                                // i (.....)
                                // 遇到了左括号！
                                cur = f(s, i + 1);
                                i = where + 1;
                        }
                }
                push(numbers, ops, cur, '+');
                where = i;
                return compute(numbers, ops);
        }

        public static void push(ArrayList<Integer> numbers, ArrayList<Character> ops, int cur, char op) {
                int n = numbers.size();
                if (n == 0 || ops.get(n - 1) == '+' || ops.get(n - 1) == '-') {
                        numbers.add(cur);
                        ops.add(op);
                } else {
                        int topNumber = numbers.get(n - 1);
                        char topOp = ops.get(n - 1);
                        if (topOp == '*') {
                                numbers.set(n - 1, topNumber * cur);
                        } else {
                                numbers.set(n - 1, topNumber / cur);
                        }
                        ops.set(n - 1, op);
                }
        }

        public static int compute(ArrayList<Integer> numbers, ArrayList<Character> ops) {
                int n = numbers.size();
                int ans = numbers.get(0);
                for (int i = 1; i < n; i++) {
                        ans += ops.get(i - 1) == '+' ? numbers.get(i) : -numbers.get(i);
                }
                return ans;
        }

6.最大公约数和最小公倍数

public static long gcd(long a, long b) {
                return b == 0 ? a : gcd(b, a % b);
        }

        public static long lcm(long a, long b) {
                return (long) a / gcd(a, b) * b;
        }

7.返回无序数组中累加和为给定值的最长子数组长（一维构建前缀信息）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;

public class Code02_LongestSubarraySumEqualsAim {

        public static int MAXN = 100001;

        public static int[] arr = new int[MAXN];

        public static int n, aim;

        // key : 某个前缀和
        // value : 这个前缀和最早出现的位置
        public static HashMap<Integer, Integer> map = new HashMap<>();

        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StreamTokenizer in = new StreamTokenizer(br);
                PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
                while (in.nextToken() != StreamTokenizer.TT_EOF) {
                        n = (int) in.nval;
                        in.nextToken();
                        aim = (int) in.nval;
                        for (int i = 0; i < n; i++) {
                                in.nextToken();
                                arr[i] = (int) in.nval;
                        }
                        out.println(compute());
                }
                out.flush();
                out.close();
                br.close();
        }

        public static int compute() {
                map.clear();
                // 重要 : 0这个前缀和，一个数字也没有的时候，就存在了
                map.put(0, -1);
                int ans = 0;
                for (int i = 0, sum = 0; i < n; i++) {
                        sum += arr[i];
                        if (map.containsKey(sum - aim)) {
                                ans = Math.max(ans, i - map.get(sum - aim));
                        }
                        if (!map.containsKey(sum)) {
                                map.put(sum, i);
                        }
                }
                return ans;
        }

}

8.一维差分

例题链接

public static int[] corpFlightBookings(int[][] bookings, int n) {
                int[] cnt=new int[n+2];
                for (int[] book : bookings) {
                        cnt[book[0]]+=book[2];
                        cnt[book[1]+1]-=book[2];
                }
                for (int i = 1; i < cnt.length; i++) {
                        cnt[i]+=cnt[i-1];
                }
                int[] ans=new int[n];
                for (int i = 0; i < ans.length; i++) {
                        ans[i]=cnt[i+1];
                }
                return ans;
        }

9.二维构建前缀信息

public int[][] sum;

                public NumMatrix(int[][] matrix) {
                        int n = matrix.length;
                        int m = matrix[0].length;
                        sum = new int[n + 1][m + 1];
                        for (int a = 1, c = 0; c < n; a++, c++) {
                                for (int b = 1, d = 0; d < m; b++, d++) {
                                        sum[a][b] = matrix[c][d];
                                }
                        }
                        for (int i = 1; i <= n; i++) {
                                for (int j = 1; j <= m; j++) {
                                        sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
                                }
                        }
                }

                public int sumRegion(int a, int b, int c, int d) {
                        c++;
                        d++;
                        return sum[c][d] - sum[c][b] - sum[a][d] + sum[a][b];
                }

10.二维差分

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Code03_DiffMatrixNowcoder {

        public static int MAXN = 1005;

        public static int MAXM = 1005;

        public static long[][] diff = new long[MAXN][MAXM];

        public static int n, m, q;

        public static void add(int a, int b, int c, int d, int k) {
                diff[a][b] += k;
                diff[c + 1][b] -= k;
                diff[a][d + 1] -= k;
                diff[c + 1][d + 1] += k;
        }

        public static void build() {
                for (int i = 1; i <= n; i++) {
                        for (int j = 1; j <= m; j++) {
                                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                        }
                }
        }

        public static void clear() {
                for (int i = 1; i <= n + 1; i++) {
                        for (int j = 1; j <= m + 1; j++) {
                                diff[i][j] = 0;
                        }
                }
        }

        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StreamTokenizer in = new StreamTokenizer(br);
                PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
                while (in.nextToken() != StreamTokenizer.TT_EOF) {
                        n = (int) in.nval;
                        in.nextToken();
                        m = (int) in.nval;
                        in.nextToken();
                        q = (int) in.nval;
                        for (int i = 1; i <= n; i++) {
                                for (int j = 1; j <= m; j++) {
                                        in.nextToken();
                                        add(i, j, i, j, (int) in.nval);
                                }
                        }
                        for (int i = 1, a, b, c, d, k; i <= q; i++) {
                                in.nextToken();
                                a = (int) in.nval;
                                in.nextToken();
                                b = (int) in.nval;
                                in.nextToken();
                                c = (int) in.nval;
                                in.nextToken();
                                d = (int) in.nval;
                                in.nextToken();
                                k = (int) in.nval;
                                add(a, b, c, d, k);
                        }
                        build();
                        for (int i = 1; i <= n; i++) {
                                out.print(diff[i][1]);
                                for (int j = 2; j <= m; j++) {
                                        out.print(" " + diff[i][j]);
                                }
                                out.println();
                        }
                        clear();
                }
                out.flush();
                out.close();
                br.close();
        }

}

11.滑动窗口

以“累加和大于等于target的最短子数组长度”为例

public static int minSubArrayLen(int target, int[] nums) {
                int ans = Integer.MAX_VALUE;
                for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
                        sum += nums[r];
                        while (sum - nums[l] >= target) {
                                // sum : nums[l....r]
                                // 如果l位置的数从窗口出去，还能继续达标，那就出去
                                sum -= nums[l++];
                        }
                        if (sum >= target) {
                                ans = Math.min(ans, r - l + 1);
                        }
                }
                return ans == Integer.MAX_VALUE ? 0 : ans;
        }

12.二分答案法

以“爱吃香蕉的珂珂”为例

public class Code01_KokoEatingBananas {

        // 时间复杂度O(n * log(max))，额外空间复杂度O(1)
        public static int minEatingSpeed(int[] piles, int h) {
                // 最小且达标的速度，范围[l,r]
                int l = 1;
                int r = 0;
                for (int pile : piles) {
                        r = Math.max(r, pile);
                }
                // [l,r]不停二分
                int ans = 0;
                int m = 0;
                while (l <= r) {
                        // m = (l + r) / 2
                        m = l + ((r - l) >> 1);
                        if (f(piles, m) <= h) {
                                // 达标！
                                // 记录答案，去左侧二分
                                ans = m;
                                // l....m....r
                                // l..m-1
                                r = m - 1;
                        } else {
                                // 不达标
                                l = m + 1;
                        }
                }
                return ans;
        }

        // 香蕉重量都在piles
        // 速度就定成speed
        // 返回吃完所有的香蕉，耗费的小时数量
        public static long f(int[] piles, int speed) {
                long ans = 0;
                for (int pile : piles) {
                        // (a/b)结果向上取整，如果a和b都是非负数，可以写成(a+b-1)/b
                        // "讲解032-位图"讲了这种写法，不会的同学可以去看看
                        // 这里不再赘述
                        ans += (pile + speed - 1) / speed;
                }
                return ans;
        }

13.单调栈

求每个位置左右两侧，离当前位置最近、且值严格小于/大于的位置

public static int MAXN = 1000001;

 public static int[] arr = new int[MAXN];

 public static int[] stack = new int[MAXN];

 public static int[][] ans = new int[MAXN][2];

 public static int n, r;

 // arr[0...n-1]
 public static void compute() {
         r = 0;
         int cur;
         for (int i = 0; i < n; i++) {
                 while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
                         cur=stack[--r];
                         ans[cur][0]=r>0?stack[r-1]:-1;
                         ans[cur][1]=i;
                 }
                 stack[r++]=i;
         }
         //总结阶段
         while (r>0) {
                 cur=stack[--r];
                 ans[cur][0]=r>0?stack[r-1]:-1;
                 ans[cur][1]=-1;
         }
         //修正阶段
         for (int i = n-2; i >=0; i--) {
                 if (ans[i][1]!=-1&&arr[ans[i][1]]==arr[i]) {
                         ans[i][1]=ans[ans[i][1]][1];
                 }
         }

14.单调队列

以“滑动窗口最大值”为例

public static int MAXN = 100001;

        public static int[] deque = new int[MAXN];

        public static int h, t;

        public static int[] maxSlidingWindow(int[] arr, int k) {
                h = t = 0;
                int n = arr.length;
                // 先形成长度为k-1的窗口
                for (int i = 0; i < k - 1; i++) {
                        // 大 -> 小
                        while (h < t && arr[deque[t - 1]] <= arr[i]) {
                                t--;
                        }
                        deque[t++] = i;
                }
                int m = n - k + 1;
                int[] ans = new int[m];
                // 当前窗口k-1长度
                for (int l = 0, r = k - 1; l < m; l++, r++) {
                        // 少一个，要让r位置的数进来
                        while (h < t && arr[deque[t - 1]] <= arr[r]) {
                                t--;
                        }
                        deque[t++] = r;
                        // 收集答案
                        ans[l] = arr[deque[h]];
                        // l位置的数出去
                        if (deque[h] == l) {
                                h++;
                        }
                }
                return ans;
        }

15.并查集模板

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Code02_UnionFindLuogu {

        public static int MAXN = 10001;

        public static int[] father = new int[MAXN];

        public static int n;

        public static void build() {
                for (int i = 0; i <= n; i++) {
                        father[i] = i;
                }
        }

        public static int find(int i) {
                if (i != father[i]) {
                        father[i] = find(father[i]);
                }
                return father[i];
        }

        public static boolean isSameSet(int x, int y) {
                return find(x) == find(y);
        }

        public static void union(int x, int y) {
                father[find(x)] = find(y);
        }

        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StreamTokenizer in = new StreamTokenizer(br);
                PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
                while (in.nextToken() != StreamTokenizer.TT_EOF) {
                        n = (int) in.nval;
                        build();
                        in.nextToken();
                        int m = (int) in.nval;
                        for (int i = 0; i < m; i++) {
                                in.nextToken();
                                int z = (int) in.nval;
                                in.nextToken();
                                int x = (int) in.nval;
                                in.nextToken();
                                int y = (int) in.nval;
                                if (z == 1) {
                                        union(x, y);
                                } else {
                                        out.println(isSameSet(x, y) ? "Y" : "N");
                                }
                        }
                }
                out.flush();
                out.close();
                br.close();
        }

16.洪水填充问题

以“岛屿数量”为例

// 洪水填充的做法
        // board : n * m
        // O(n*m)最优解！
        public static int numIslands(char[][] board) {
                int n = board.length;
                int m = board[0].length;
                int islands = 0;
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < m; j++) {
                                if (board[i][j] == '1') {
                                        islands++;
                                        dfs(board, n, m, i, j);
                                }
                        }
                }
                return islands;
        }

        public static void dfs(char[][] board, int n, int m, int i, int j) {
                if (i < 0 || i == n || j < 0 || j == m || board[i][j] != '1') {
                        return;
                }
                // board[i][j] = '1'
                board[i][j] = 0;
                dfs(board, n, m, i - 1, j);
                dfs(board, n, m, i + 1, j);
                dfs(board, n, m, i, j - 1);
                dfs(board, n, m, i, j + 1);
        }

17.三种建图方式

import java.util.ArrayList;
import java.util.Arrays;

public class Code01_CreateGraph {

        // 点的最大数量
        public static int MAXN = 11;

        // 边的最大数量
        // 只有链式前向星方式建图需要这个数量
        // 注意如果无向图的最大数量是m条边，数量要准备m*2
        // 因为一条无向边要加两条有向边
        public static int MAXM = 21;

        // 邻接矩阵方式建图
        public static int[][] graph1 = new int[MAXN][MAXN];

        // 邻接表方式建图
        // public static ArrayList<ArrayList<Integer>> graph2 = new ArrayList<>();
        public static ArrayList<ArrayList<int[]>> graph2 = new ArrayList<>();

        // 链式前向星方式建图
        public static int[] head = new int[MAXN];

        public static int[] next = new int[MAXM];

        public static int[] to = new int[MAXM];

        // 如果边有权重，那么需要这个数组
        public static int[] weight = new int[MAXM];

        public static int cnt;

        public static void build(int n) {
                // 邻接矩阵清空
                for (int i = 1; i <= n; i++) {
                        for (int j = 1; j <= n; j++) {
                                graph1[i][j] = 0;
                        }
                }
                // 邻接表清空和准备
                graph2.clear();
                // 下标需要支持1~n，所以加入n+1个列表，0下标准备但不用
                for (int i = 0; i <= n; i++) {
                        graph2.add(new ArrayList<>());
                }
                // 链式前向星清空
                cnt = 1;
                Arrays.fill(head, 1, n + 1, 0);
        }

        // 链式前向星加边
        public static void addEdge(int u, int v, int w) {
                // u -> v , 边权重是w
                next[cnt] = head[u];
                to[cnt] = v;
                weight[cnt] = w;
                head[u] = cnt++;
        }

        // 三种方式建立有向图带权图
        public static void directGraph(int[][] edges) {
                // 邻接矩阵建图
                for (int[] edge : edges) {
                        graph1[edge[0]][edge[1]] = edge[2];
                }
                // 邻接表建图
                for (int[] edge : edges) {
                        // graph2.get(edge[0]).add(edge[1]);
                        graph2.get(edge[0]).add(new int[] { edge[1], edge[2] });
                }
                // 链式前向星建图
                for (int[] edge : edges) {
                        addEdge(edge[0], edge[1], edge[2]);
                }
        }

        // 三种方式建立无向图带权图
        public static void undirectGraph(int[][] edges) {
                // 邻接矩阵建图
                for (int[] edge : edges) {
                        graph1[edge[0]][edge[1]] = edge[2];
                        graph1[edge[1]][edge[0]] = edge[2];
                }
                // 邻接表建图
                for (int[] edge : edges) {
                        // graph2.get(edge[0]).add(edge[1]);
                        // graph2.get(edge[1]).add(edge[0]);
                        graph2.get(edge[0]).add(new int[] { edge[1], edge[2] });
                        graph2.get(edge[1]).add(new int[] { edge[0], edge[2] });
                }
                // 链式前向星建图
                for (int[] edge : edges) {
                        addEdge(edge[0], edge[1], edge[2]);
                        addEdge(edge[1], edge[0], edge[2]);
                }
        }

        public static void traversal(int n) {
                System.out.println("邻接矩阵遍历 :");
                for (int i = 1; i <= n; i++) {
                        for (int j = 1; j <= n; j++) {
                                System.out.print(graph1[i][j] + " ");
                        }
                        System.out.println();
                }
                System.out.println("邻接表遍历 :");
                for (int i = 1; i <= n; i++) {
                        System.out.print(i + "(邻居、边权) : ");
                        for (int[] edge : graph2.get(i)) {
                                System.out.print("(" + edge[0] + "," + edge[1] + ") ");
                        }
                        System.out.println();
                }
                System.out.println("链式前向星 :");
                for (int i = 1; i <= n; i++) {
                        System.out.print(i + "(邻居、边权) : ");
                        // 注意这个for循环，链式前向星的方式遍历
                        for (int ei = head[i]; ei > 0; ei = next[ei]) {
                                System.out.print("(" + to[ei] + "," + weight[ei] + ") ");
                        }
                        System.out.println();
                }
        }

18.拓扑排序模板

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;

public class Code02_TopoSortDynamicNowcoder {

        public static int MAXN = 200001;

        // 拓扑排序，用到队列
        public static int[] queue = new int[MAXN];

        public static int l, r;

        // 拓扑排序，入度表
        public static int[] indegree = new int[MAXN];

        // 收集拓扑排序的结果
        public static int[] ans = new int[MAXN];

        public static int n, m;

        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StreamTokenizer in = new StreamTokenizer(br);
                PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
                while (in.nextToken() != StreamTokenizer.TT_EOF) {
                        n = (int) in.nval;
                        in.nextToken();
                        m = (int) in.nval;
                        // 动态建图，比赛肯定不行，但是一般大厂笔试、面试允许
                        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
                        for (int i = 0; i <= n; i++) {
                                graph.add(new ArrayList<>());
                        }
                        Arrays.fill(indegree, 0, n + 1, 0);
                        for (int i = 0, from, to; i < m; i++) {
                                in.nextToken();
                                from = (int) in.nval;
                                in.nextToken();
                                to = (int) in.nval;
                                graph.get(from).add(to);
                                indegree[to]++;
                        }
                        if (!topoSort(graph)) {
                                out.println(-1);
                        } else {
                                for (int i = 0; i < n - 1; i++) {
                                        out.print(ans[i] + " ");
                                }
                                out.println(ans[n - 1]);
                        }
                }
                out.flush();
                out.close();
                br.close();
        }

        // 有拓扑排序返回true
        // 没有拓扑排序返回false
        public static boolean topoSort(ArrayList<ArrayList<Integer>> graph) {
                l = r = 0;
                for (int i = 1; i <= n; i++) {
                        if (indegree[i] == 0) {
                                queue[r++] = i;
                        }
                }
                int fill = 0;
                while (l < r) {
                        int cur = queue[l++];
                        ans[fill++] = cur;
                        for (int next : graph.get(cur)) {
                                if (--indegree[next] == 0) {
                                        queue[r++] = next;
                                }
                        }
                }
                return fill == n;
        }

}

19.Prim算法模版

Prim与Kruskal都是用来求最小生成树的，但更推荐使用Prim，所以就只给出Prim的模板

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.PriorityQueue;

// 时间复杂度O(n + m) + O(m * log m)
public class Code02_PrimDynamic {

        public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StreamTokenizer in = new StreamTokenizer(br);
                PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
                while (in.nextToken() != StreamTokenizer.TT_EOF) {
                        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
                        int n = (int) in.nval;
                        for (int i = 0; i <= n; i++) {
                                graph.add(new ArrayList<>());
                        }
                        in.nextToken();
                        int m = (int) in.nval;
                        for (int i = 0, u, v, w; i < m; i++) {
                                in.nextToken();
                                u = (int) in.nval;
                                in.nextToken();
                                v = (int) in.nval;
                                in.nextToken();
                                w = (int) in.nval;
                                graph.get(u).add(new int[] { v, w });
                                graph.get(v).add(new int[] { u, w });
                        }
                        // int[] record
                        // record[0] : 到达的节点
                        // record[1] : 到达的花费
                        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
                        for (int[] edge : graph.get(1)) {
                                heap.add(edge);
                        }
                        // 哪些节点已经发现过了
                        boolean[] set = new boolean[n + 1];
                        int nodeCnt = 1;
                        set[1] = true;
                        int ans = 0;
                        while (!heap.isEmpty()) {
                                int[] edge = heap.poll();
                                int next = edge[0];
                                int cost = edge[1];
                                if (!set[next]) {
                                        nodeCnt++;
                                        set[next] = true;
                                        ans += cost;
                                        for (int[] e : graph.get(next)) {
                                                heap.add(e);
                                        }
                                }
                        }
                        out.println(nodeCnt == n ? ans : "orz");
                }
                out.flush();
                out.close();
                br.close();
        }

20.BFS

以“地图分析”为例

public static int MAXN = 101;

        public static int MAXM = 101;

        public static int[][] queue = new int[MAXN * MAXM][2];

        public static int l, r;

        public static boolean[][] visited = new boolean[MAXN][MAXM];

        // 0:上，1:右，2:下，3:左
        public static int[] move = new int[] { -1, 0, 1, 0, -1 };
        //                                      0  1  2  3   4
        //                                               i
        // (x,y)  i来到0位置 : x + move[i], y + move[i+1] -> x - 1, y
        // (x,y)  i来到1位置 : x + move[i], y + move[i+1] -> x, y + 1
        // (x,y)  i来到2位置 : x + move[i], y + move[i+1] -> x + 1, y
        // (x,y)  i来到3位置 : x + move[i], y + move[i+1] -> x, y - 1

        public static int maxDistance(int[][] grid) {
                l = r = 0;
                int n = grid.length;
                int m = grid[0].length;
                int seas = 0;
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < m; j++) {
                                if (grid[i][j] == 1) {
                                        visited[i][j] = true;
                                        queue[r][0] = i;
                                        queue[r++][1] = j;
                                } else {
                                        visited[i][j] = false;
                                        seas++;
                                }
                        }
                }
                if (seas == 0 || seas == n * m) {
                        return -1;
                }
                int level = 0;
                while (l < r) {
                        level++;
                        int size = r - l;
                        for (int k = 0, x, y, nx, ny; k < size; k++) {
                                x = queue[l][0];
                                y = queue[l++][1];
                                for (int i = 0; i < 4; i++) {
                                        // 上、右、下、左
                                        nx = x + move[i];
                                        ny = y + move[i + 1];
                                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                                                visited[nx][ny] = true;
                                                queue[r][0] = nx;
                                                queue[r++][1] = ny;
                                        }
                                }
                        }
                }
                return level - 1;
        }

21.dijkstra

以“最小体力消耗路径”为模板

// 0:上，1:右，2:下，3:左
public static int[] move = new int[] { -1, 0, 1, 0, -1 };

public int minimumEffortPath(int[][] heights) {
        // (0,0)源点
        // -> (x,y)
        int n = heights.length;
        int m = heights[0].length;
        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                        distance[i][j] = Integer.MAX_VALUE;
                }
        }
        distance[0][0] = 0;
        boolean[][] visited = new boolean[n][m];
        // 0 : 格子的行
        // 1 : 格子的列
        // 2 : 源点到当前格子的代价
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>((a, b) -> a[2] - b[2]);
        heap.add(new int[] { 0, 0, 0 });
        while (!heap.isEmpty()) {
                int[] record = heap.poll();
                int x = record[0];
                int y = record[1];
                int c = record[2];
                if (visited[x][y]) {
                        continue;
                }
                if (x == n - 1 && y == m - 1) {
                        // 常见剪枝
                        // 发现终点直接返回
                        // 不用等都结束
                        return c;
                }
                visited[x][y] = true;
                for (int i = 0; i < 4; i++) {
                        int nx = x + move[i];
                        int ny = y + move[i + 1];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                                int nc = Math.max(c, Math.abs(heights[x][y] - heights[nx][ny]));
                                if (nc < distance[nx][ny]) {
                                        distance[nx][ny] = nc;
                                        heap.add(new int[] { nx, ny, nc });
                                }
                        }
                }
        }
        return -1;
}

22.Floyd算法

public static int MAXN = 101;

public static int MAXM = 10001;

public static int[] path = new int[MAXM];

public static int[][] distance = new int[MAXN][MAXN];

public static int n, m, ans;

// 初始时设置任意两点之间的最短距离为无穷大，表示任何路不存在
public static void build() {
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                        distance[i][j] = Integer.MAX_VALUE;
                }
        }
}

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
                n = (int) in.nval;
                in.nextToken();
                m = (int) in.nval;
                for (int i = 0; i < m; i++) {
                        in.nextToken();
                        path[i] = (int) in.nval - 1;
                }
                // 这道题给的图是邻接矩阵的形式
                // 任意两点之间的边权都会给定
                // 所以显得distance初始化不太必要
                // 但是一般情况下，distance初始化一定要做
                build();
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                                in.nextToken();
                                distance[i][j] = (int) in.nval;
                        }
                }
                floyd();
                ans = 0;
                for (int i = 1; i < m; i++) {
                        ans += distance[path[i - 1]][path[i]];
                }
                out.println(ans);
        }
        out.flush();
        out.close();
        br.close();
}

public static void floyd() {
        // O(N^3)的过程
        // 枚举每个跳板
        // 注意，跳板要最先枚举！跳板要最先枚举！跳板要最先枚举！
        for (int bridge = 0; bridge < n; bridge++) { // 跳板
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                                // i -> .....bridge .... -> j
                                // distance[i][j]能不能缩短
                                // distance[i][j] = min ( distance[i][j] , distance[i][bridge] + distance[bridge][j])
                                if (distance[i][bridge] != Integer.MAX_VALUE 
                                                && distance[bridge][j] != Integer.MAX_VALUE
                                                && distance[i][j] > distance[i][bridge] + distance[bridge][j]) {
                                        distance[i][j] = distance[i][bridge] + distance[bridge][j];
                                }
                        }
                }
        }
}

23.子数组最大累加和

// 动态规划
        public static int maxSubArray1(int[] nums) {
                int n = nums.length;
                // dp[i] : 子数组必须以i位置的数做结尾，往左能延伸出来的最大累加和
                int[] dp = new int[n];
                dp[0] = nums[0];
                int ans = nums[0];
                for (int i = 1; i < n; i++) {
                        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
                        ans = Math.max(ans, dp[i]);
                }
                return ans;
        }

24.最长递增子序列

public static int lengthOfLIS(int[] nums) {
                int n = nums.length;
                int[] ends = new int[n];
                // len表示ends数组目前的有效区长度
                // ends[0...len-1]是有效区，有效区内的数字一定严格升序
                int len = 0;
                for (int i = 0, find; i < n; i++) {
                        find = bs(ends, len, nums[i]);
                        if (find == -1) {
                                ends[len++] = nums[i];
                        } else {
                                ends[find] = nums[i];
                        }
                }
                return len;
        }
        
        // "最长递增子序列"使用如下二分搜索 :
        // ends[0...len-1]是严格升序的，找到>=num的最左位置
        // 如果不存在返回-1
        public static int bs(int[] ends, int len, int num) {
                int l = 0, r = len - 1, m, ans = -1;
                while (l <= r) {
                        m = l+(r-l) / 2;
                        if (ends[m] >= num) {
                                ans = m;
                                r = m - 1;
                        } else {
                                l = m + 1;
                        }
                }
                return ans;
        }

25. 01背包

// 严格位置依赖的动态规划
// n个物品编号1~n，第i号物品的花费cost[i]、价值val[i]
// cost、val数组是全局变量，已经把数据读入了
public static int compute1() {
        int[][] dp = new int[n + 1][t + 1];
        for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= t; j++) {
                        // 不要i号物品
                        dp[i][j] = dp[i - 1][j];
                        if (j - cost[i] >= 0) {
                                // 要i号物品
                                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost[i]] + val[i]);
                        }
                }
        }
        return dp[n][t];
}

26.有依赖的背包

        public static int MAXN = 33001;

        public static int MAXM = 61;

        public static int[] cost = new int[MAXM];

        public static int[] val = new int[MAXM];

        public static boolean[] king = new boolean[MAXM];

        public static int[] fans = new int[MAXM];

        public static int[][] follows = new int[MAXM][2];

        public static int[] dp = new int[MAXN];

        public static int n, m;

        public static void clean() {
                for (int i = 1; i <= m; i++) {
                        fans[i] = 0;
                }
        }
// 严格位置依赖的动态规划
        public static int compute1() {
                // dp[0][....] = 0 : 无商品的时候
                int[][] dp = new int[m + 1][n + 1];
                // p : 上次展开的主商品编号
                int p = 0;
                for (int i = 1, fan1, fan2; i <= m; i++) {
                        if (king[i]) {
                                for (int j = 0; j <= n; j++) {
                                        // dp[i][j] : 0...i范围上，只关心主商品，并且进行展开
                                        //            花费不超过j的情况下，获得的最大收益
                                        // 可能性1 : 不考虑当前主商品
                                        dp[i][j] = dp[p][j];
                                        if (j - cost[i] >= 0) {
                                                // 可能性2 : 考虑当前主商品，只要主
                                                dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i]] + val[i]);
                                        }
                                        // fan1 : 如果有附1商品，编号给fan1，如果没有，fan1 == -1
                                        // fan2 : 如果有附2商品，编号给fan2，如果没有，fan2 == -1
                                        fan1 = fans[i] >= 1 ? follows[i][0] : -1;
                                        fan2 = fans[i] >= 2 ? follows[i][1] : -1;
                                        if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {
                                                // 可能性3 : 主 + 附1
                                                dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i] - cost[fan1]] + val[i] + val[fan1]);
                                        }
                                        if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {
                                                // 可能性4 : 主 + 附2
                                                dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i] - cost[fan2]] + val[i] + val[fan2]);
                                        }
                                        if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0) {
                                                // 可能性5 : 主 + 附1 + 附2
                                                dp[i][j] = Math.max(dp[i][j],
                                                                dp[p][j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);
                                        }
                                }
                                p = i;
                        }
                }
                return dp[p][n];
        }

27.分组背包

public static int MAXN = 1001;

public static int MAXM = 1001;

// arr[i][0] i号物品的体积
// arr[i][1] i号物品的价值
// arr[i][2] i号物品的组号
public static int[][] arr = new int[MAXN][3];

public static int[] dp = new int[MAXM];

public static int m, n;
public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
                m = (int) in.nval;
                in.nextToken();
                n = (int) in.nval;
                for (int i = 1; i <= n; i++) {
                        in.nextToken();
                        arr[i][0] = (int) in.nval;
                        in.nextToken();
                        arr[i][1] = (int) in.nval;
                        in.nextToken();
                        arr[i][2] = (int) in.nval;
                }
                Arrays.sort(arr, 1, n + 1, (a, b) -> a[2] - b[2]);
                out.println(compute1());
        }
        out.flush();
        out.close();
        br.close();
}

public static int compute1() {
        int teams = 1;
        for (int i = 2; i <= n; i++) {
                if (arr[i - 1][2] != arr[i][2]) {
                        teams++;
                }
        }
        // 组的编号1~teams
        // dp[i][j] : 1~i是组的范围，每个组的物品挑一件，容量不超过j的情况下，最大收益
        int[][] dp = new int[teams + 1][m + 1];
        // dp[0][....] = 0
        for (int start = 1, end = 2, i = 1; start <= n; i++) {
                while (end <= n && arr[end][2] == arr[start][2]) {
                        end++;
                }
                // start ... end-1 -> i组
                for (int j = 0; j <= m; j++) {
                        // arr[start...end-1]是当前组，组号一样
                        // 其中的每一件商品枚举一遍
                        dp[i][j] = dp[i - 1][j];
                        for (int k = start; k < end; k++) {
                                // k是组内的一个商品编号
                                if (j - arr[k][0] >= 0) {
                                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[k][0]] + arr[k][1]);
                                }
                        }
                }
                // start去往下一组的第一个物品
                // 继续处理剩下的组
                start = end++;
        }
        return dp[teams][m];
}

28.完全背包

public static int MAXM = 10001;

public static int MAXT = 10000001;

public static int[] cost = new int[MAXM];

public static int[] val = new int[MAXM];

public static long[] dp = new long[MAXT];

public static int t, m;

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
                t = (int) in.nval;
                in.nextToken();
                m = (int) in.nval;
                for (int i = 1; i <= m; i++) {
                        in.nextToken();
                        cost[i] = (int) in.nval;
                        in.nextToken();
                        val[i] = (int) in.nval;
                }
                out.println(compute2());
        }
        out.flush();
        out.close();
        br.close();
}

// 严格位置依赖的动态规划
// 会空间不够，导致无法通过全部测试用例
public static long compute1() {
        // dp[0][.....] = 0
        int[][] dp = new int[m + 1][t + 1];
        for (int i = 1; i <= m; i++) {
                for (int j = 0; j <= t; j++) {
                        dp[i][j] = dp[i - 1][j];
                        if (j - cost[i] >= 0) {
                                dp[i][j] = Math.max(dp[i][j], dp[i][j - cost[i]] + val[i]);
                        }
                }
        }
        return dp[m][t];
}

29.多重背包

public static int MAXN = 1001;

public static int MAXW = 40001;

// 把每一种货物根据个数做二进制分组，去生成衍生商品
// 衍生出来的每一种商品，价值放入v、重量放入w
public static int[] v = new int[MAXN];

public static int[] w = new int[MAXN];

public static int[] dp = new int[MAXW];

public static int n, t, m;

// 时间复杂度O(t * (log(第1种商品的个数) + log(第2种商品的个数) + ... + log(第n种商品的个数)))
// 对每一种商品的个数取log，所以时间复杂度虽然大于O(n * t)，但也不会大多少
// 多重背包最常用的方式
public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
                n = (int) in.nval;
                in.nextToken();
                t = (int) in.nval;
                m = 0;
                for (int i = 1, value, weight, cnt; i <= n; i++) {
                        in.nextToken(); value = (int) in.nval;
                        in.nextToken(); weight = (int) in.nval;
                        in.nextToken(); cnt = (int) in.nval;
                        // 整个文件最重要的逻辑 : 二进制分组
                        // 一般都使用这种技巧，这段代码非常重要
                        // 虽然时间复杂度不如单调队列优化的版本
                        // 但是好写，而且即便是比赛，时间复杂度也达标
                        // 二进制分组的时间复杂度为O(log cnt)
                        for (int k = 1; k <= cnt; k <<= 1) {
                                v[++m] = k * value;
                                w[m] = k * weight;
                                cnt -= k;
                        }
                        if (cnt > 0) {
                                v[++m] = cnt * value;
                                w[m] = cnt * weight;
                        }
                }
                out.println(compute());
        }
        out.flush();
        out.close();
        br.close();
}

// 01背包的空间压缩代码(模版)
public static int compute() {
        Arrays.fill(dp, 0, t + 1, 0);
        for (int i = 1; i <= m; i++) {
                for (int j = t; j >= w[i]; j--) {
                        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
        }
        return dp[t];
}

我将记录手撕题目:

写一个快速排序

链接

public static int[] sortArray(int[] nums) {
        if (nums.length > 1) {
                quickSort(nums, 0, nums.length - 1);
        }
        return nums;
}
// 随机快速排序
public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
                return;
        }
        // 随机这一下，常数时间比较大
        // 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
        int x = arr[l + (int) (Math.random() * (r - l + 1))];
        partition(arr, l, r, x);
        // 为了防止底层的递归过程覆盖全局变量
        // 这里用临时变量记录first、last
        int left = first;
        int right = last;
        quickSort(arr, l, left - 1);
        quickSort(arr, right + 1, r);
}
// 荷兰国旗问题
public static int first, last;

// 已知arr[l....r]范围上一定有x这个值
// 划分数组 <x放左边，==x放中间，>x放右边
// 把全局变量first, last，更新成==x区域的左右边界
public static void partition(int[] arr, int l, int r, int x) {
        first = l;
        last = r;
        int i = l;
        while (i <= last) {
                if (arr[i] == x) {
                        i++;
                } else if (arr[i] < x) {
                        swap(arr, first++, i++);
                } else {
                        swap(arr, i, last--);
                }
        }
}

public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
}

求最长递增子序列

链接

public static int lengthOfLIS(int[] nums) {
                int n = nums.length;
                int[] ends = new int[n];
                // len表示ends数组目前的有效区长度
                // ends[0...len-1]是有效区，有效区内的数字一定严格升序
                int len = 0;
                for (int i = 0, find; i < n; i++) {
                        find = bs1(ends, len, nums[i]);
                        if (find == -1) {
                                ends[len++] = nums[i];
                        } else {
                                ends[find] = nums[i];
                        }
                }
                return len;
        }
        
        // "最长递增子序列"使用如下二分搜索 :
        // ends[0...len-1]是严格升序的，找到>=num的最左位置
        // 如果不存在返回-1
        public static int bs1(int[] ends, int len, int num) {
                int l = 0, r = len - 1, m, ans = -1;
                while (l <= r) {
                        m = (l + r) / 2;
                        if (ends[m] >= num) {
                                ans = m;
                                r = m - 1;
                        } else {
                                l = m + 1;
                        }
                }
                return ans;
        }

        // 如果求最长不下降子序列，那么使用如下的二分搜索 :
        // ends[0...len-1]是不降序的
        // 在其中找到>num的最左位置，如果不存在返回-1
        // 如果求最长不下降子序列，就在lengthOfLIS中把bs1方法换成bs2方法
        // 已经用对数器验证了，是正确的
        public static int bs2(int[] ends, int len, int num) {
                int l = 0, r = len - 1, m, ans = -1;
                while (l <= r) {
                        m = (l + r) / 2;
                        if (ends[m] > num) {
                                ans = m;
                                r = m - 1;
                        } else {
                                l = m + 1;
                        }
                }
                return ans;
        }
     

LRU缓存

链接

class LRUCache {

                class DoubleNode {
                        public int key;
                        public int val;
                        public DoubleNode last;
                        public DoubleNode next;

                        public DoubleNode(int k, int v) {
                                key = k;
                                val = v;
                        }
                }

                class DoubleList {
                        private DoubleNode head;
                        private DoubleNode tail;

                        public DoubleList() {
                                head = null;
                                tail = null;
                        }

                        public void addNode(DoubleNode newNode) {
                                if (newNode == null) {
                                        return;
                                }
                                if (head == null) {
                                        head = newNode;
                                        tail = newNode;
                                } else {
                                        tail.next = newNode;
                                        newNode.last = tail;
                                        tail = newNode;
                                }
                        }

                        public void moveNodeToTail(DoubleNode node) {
                                if (tail == node) {
                                        return;
                                }
                                if (head == node) {
                                        head = node.next;
                                        head.last = null;
                                } else {
                                        node.last.next = node.next;
                                        node.next.last = node.last;
                                }
                                node.last = tail;
                                node.next = null;
                                tail.next = node;
                                tail = node;
                        }

                        public DoubleNode removeHead() {
                                if (head == null) {
                                        return null;
                                }
                                DoubleNode ans = head;
                                if (head == tail) {
                                        head = null;
                                        tail = null;
                                } else {
                                        head = ans.next;
                                        ans.next = null;
                                        head.last = null;
                                }
                                return ans;
                        }

                }

                private HashMap<Integer, DoubleNode> keyNodeMap;

                private DoubleList nodeList;

                private final int capacity;

                public LRUCache(int cap) {
                        keyNodeMap = new HashMap<>();
                        nodeList = new DoubleList();
                        capacity = cap;
                }

                public int get(int key) {
                        if (keyNodeMap.containsKey(key)) {
                                DoubleNode ans = keyNodeMap.get(key);
                                nodeList.moveNodeToTail(ans);
                                return ans.val;
                        }
                        return -1;
                }

                public void put(int key, int value) {
                        if (keyNodeMap.containsKey(key)) {
                                DoubleNode node = keyNodeMap.get(key);
                                node.val = value;
                                nodeList.moveNodeToTail(node);
                        } else {
                                if (keyNodeMap.size() == capacity) {
                                        keyNodeMap.remove(nodeList.removeHead().key);
                                }
                                DoubleNode newNode = new DoubleNode(key, value);
                                keyNodeMap.put(key, newNode);
                                nodeList.addNode(newNode);
                        }
                }

        }

反转链表

一般要求递归和迭代都要写出来

链接

迭代：

public ListNode reverseList(ListNode head) {
     ListNode next=null;
     ListNode pre=null;
     while(head!=null){
         next=head.next;
         head.next=pre;
         pre=head;
         head=next;
     }
     return pre;
 }

递归：

public ListNode reverseList(ListNode head) {
    return recur(head, null);    // 调用递归并返回
}
private ListNode recur(ListNode cur, ListNode pre) {
    if (cur == null) return pre; // 终止条件
    ListNode res = recur(cur.next, cur);  // 递归后继节点
    cur.next = pre;              // 修改节点引用指向
    return res;                  // 返回反转链表的头节点
}

无重复字符的最长子串

经典滑动窗口

链接

public int lengthOfLongestSubstring(String str) {
        char[] s = str.toCharArray();
        int n=s.length;
        int[] last=new int[256];
        Arrays.fill(last,-1);
        int ans=0;
        for (int l = 0,r=0; r<n; r++) {
            l=Math.max(l,last[s[r]]+1);//如果s[r]之前没出现过，那么l就还是l，如果出现过，则l就变成新的位置
            ans=Math.max(ans,r-l+1);
            last[s[r]]=r;
        }
        return ans;
    }

K个一组翻转链表

链接

public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start=head;
        ListNode end=teamEnd(start,k);
        if(end==null) {
            return head;
        }
        head=end;
        reverse(start,end);
        ListNode lastTeamEnd=start;
        while(lastTeamEnd.next!=null) {
            start=lastTeamEnd.next;
            end=teamEnd(start,k);
            if(end==null) {
                return head;
            }
            reverse(start,end);
            lastTeamEnd.next=end;
            lastTeamEnd=start;
        }
        return head;
    }
    private void reverse(ListNode s, ListNode e) {
           // TODO Auto-generated method stub
           e=e.next;
           ListNode pre=null,cur=s,next=null;
           while (cur != e) {
               next = cur.next;
               cur.next = pre;
               pre = cur;
               cur = next;
           }
           s.next = e;
       }

       private ListNode teamEnd(ListNode s, int k) {
           // TODO Auto-generated method stub
           while (--k!=0&&s!=null) {
               s=s.next;
           }
           return s;
       }

数组中的第K个最大元素

链接

要实现O(n)的算法，实际上就是写一个快排。

public static void quickSort(int[] arr, int l, int r) {
               if (l >= r) {
                       return;
               }
               // 随机这一下，常数时间比较大
               // 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
               int x = arr[l + (int) (Math.random() * (r - l + 1))];
               partition(arr, l, r, x);
               // 为了防止底层的递归过程覆盖全局变量
               // 这里用临时变量记录first、last
               int left = first;
               int right = last;
               quickSort(arr, l, left - 1);
               quickSort(arr, right + 1, r);
       }
       // 荷兰国旗问题
       public static int first, last;

       // 已知arr[l....r]范围上一定有x这个值
       // 划分数组 <x放左边，==x放中间，>x放右边
       // 把全局变量first, last，更新成==x区域的左右边界
       public static void partition(int[] arr, int l, int r, int x) {
               first = l;
               last = r;
               int i = l;
               while (i <= last) {
                       if (arr[i] == x) {
                               i++;
                       } else if (arr[i] < x) {
                               swap(arr, first++, i++);
                       } else {
                               swap(arr, i, last--);
                       }
               }
       }
       
       public static void swap(int[] arr, int i, int j) {
               int tmp = arr[i];
               arr[i] = arr[j];
               arr[j] = tmp;
       }
   
   public int findKthLargest(int[] nums, int k) {
       quickSort(nums,0,nums.length-1);
       return nums[nums.length-k];
   }

三数之和

链接

public List<List<Integer>> threeSum(int[] nums){
    int n=nums.length;
    Arrays.sort(nums);  //一定得排序那么一下
    List<List<Integer>> ans=new ArrayList<>();
    for(int first=0;first<n;first++){
        if(first>0&&nums[first]==nums[first-1]){
            continue;
        }
        int third=n-1;
        int target=-nums[first];
        for(int second=first+1;second<n;second++){
            if(second>first+1&&nums[second]==nums[second-1]){
                continue;
            }
            while(second<third&&nums[second]+nums[third]>target){
                --third;
            }
            if(second==third){
                break;
            }
            if(nums[second]+nums[third]==target){
                List<Integer> list=new ArrayList<>();
                list.add(nums[first]);
                list.add(nums[second]);
                list.add(nums[third]);
                ans.add(list);
            }
        }
    }
    return ans;
    }

合并两个有序链表

链接

public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
       if (head1 == null || head2 == null) {
           return head1 == null ? head2 : head1;
       }
       ListNode head = head1.val <= head2.val ? head1 : head2;
       ListNode h1 = head.next;
       ListNode h2 = head == head1 ? head2 : head1;
       ListNode pre = head;
       while (h1 != null && h2 != null) {
           if (h1.val <= h2.val) {
               pre.next = h1;
               h1 = h1.next;
           } else {
               pre.next = h2;
               h2 = h2.next;
           }
           pre = pre.next;
       }
       pre.next = h1 != null ? h1 : h2;
       return head;
   }

排序数组

链表

public static int first, last;

   public int[] sortArray(int[] nums) {
       int n = nums.length;
       if (n > 1) {
           quickSort(nums, 0, n - 1);
       }
       return nums;
   }

   public static void quickSort(int[] nums, int l, int r) {
       if (l >= r) {
           return;
       }
       int x = nums[l + (int) (Math.random() * (r - l + 1))];
       partition(nums, l, r,x);
       int left = first;
       int right=last;
       quickSort(nums,l,left-1);
       quickSort(nums,right+1,r);
   }
   public static void partition(int[] nums,int l,int r,int x){
       first=l;
       last=r;
       int i=l;
       while(i<=last){
           if(nums[i]==x){
               i++;
           }else if(nums[i]<x){
               swap(nums,first++,i++);
           }else{
               swap(nums,i,last--);
           }
       }
   }
   public static void swap(int[] nums,int i,int j){
       int temp=nums[i];
       nums[i]=nums[j];
       nums[j]=temp;
   }

搜索旋转排序数组

链接

public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start <= end){
            int mid = start + (end -start)/2;
            if (nums[mid] == target){
                return mid;
            }

            //后半部分有序
            if(nums[mid] < nums[end]){
                if(nums[mid] < target && target <= nums[end]){
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                 if(nums[mid] > target && target >= nums[start]){
                    end = mid - 1;
                } else {
                    start = mid + 1;
                    
                }
            }
        }
        return -1;
        
    }

合并K个排序数组

链接

 public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
            for (ListNode head : lists)
                if (head != null)
                    pq.offer(head);

            ListNode dummy = new ListNode(); // 哨兵节点，作为合并后链表头节点的前一个节点
            ListNode cur = dummy;
            while (!pq.isEmpty()) { // 循环直到堆为空
                ListNode node = pq.poll(); // 剩余节点中的最小节点
                if (node.next != null) // 下一个节点不为空
                    pq.offer(node.next); // 下一个节点有可能是最小节点，入堆
                cur.next = node; // 合并到新链表中
                cur = cur.next; // 准备合并下一个节点
            }
            return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点
    }

反转链表||

链接

public ListNode reverseBetween(ListNode head, int left, int right) {
      // 设置 dummyNode 是这一类问题的一般做法
      ListNode dummyNode = new ListNode(-1);
      dummyNode.next = head;
      ListNode pre = dummyNode;
      for (int i = 0; i < left - 1; i++) {
          pre = pre.next;
      }
      ListNode cur = pre.next;
      ListNode next;
      for (int i = 0; i < right - left; i++) {
          next = cur.next;
          cur.next = next.next;
          next.next = pre.next;
          pre.next = next;
      }
      return dummyNode.next;
  }

二叉树的层序遍历

链接

public static int MAXN = 2001;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;

public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root != null) {
        l = r = 0;
        queue[r++] = root;
        while (l < r) {
            int size = r - l;
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue[l++];
                list.add(cur.val);
                if (cur.left != null) {
                    queue[r++] = cur.left;
                }
                if (cur.right != null) {
                    queue[r++] = cur.right;
                }
            }
            ans.add(list);

        }
    }
    return ans;
}

最长回文子串

链接

public String longestPalindrome(String s) {
   int len=s.length();
   int left=0,right=0,res=0;
   boolean[][] dp=new boolean[len][len];
   for(int i=len-1;i>=0;i--){
    for(int j=i;j<len;j++){
        if(s.charAt(i)==s.charAt(j)&&(j-i<=1||dp[i+1][j-1])){
            dp[i][j]=true;
            if(j-i>res){
                res=j-i;
                left=i;
                right=j;
            }
        }
    }
   
   }
    return s.substring(left,right+1);
}

相似题目–最长回文子序列

  public static int longestPalindromeSubseq2(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        return f(s, 0, n - 1, dp);
}

public static int f(char[] s, int l, int r, int[][] dp) {
        if (l == r) {
                return 1;
        }
        if (l + 1 == r) {
                return s[l] == s[r] ? 2 : 1;
        }
        if (dp[l][r] != 0) {
                return dp[l][r];
        }
        int ans;
        if (s[l] == s[r]) {
                ans = 2 + f(s, l + 1, r - 1, dp);
        } else {
                ans = Math.max(f(s, l + 1, r, dp), f(s, l, r - 1, dp));
        }
        dp[l][r] = ans;
        return ans;
}

二叉树的锯齿形层序遍历

链接

public static int MAXN=2001;
public static TreeNode[] queue=new TreeNode[MAXN];
public static int l,r;

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans=new ArrayList<>();
    if (root!=null) {
        l=r=0;
        queue[r++]=root;
        boolean reverse=false;
        while (l<r) {
            int size=r-l;
            ArrayList<Integer> list=new ArrayList<>();
            for (int i = reverse?r-1:l,k=0;k < size; i += reverse?-1:1, k++) {
                TreeNode cur = queue[i];
                list.add(cur.val);
            }
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue[l++];
                if (cur.left != null) {
                    queue[r++] = cur.left;
                }
                if (cur.right != null) {
                    queue[r++] = cur.right;
                }
            }
            ans.add(list);
            reverse = !reverse;
        }
    }
    return ans;
}

二叉树的最近公共祖先

链接

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if(root==null||p==root||q==root){
        return root;
      }
      TreeNode left= lowestCommonAncestor(root.left,p,q);
      TreeNode right=  lowestCommonAncestor(root.right,p,q);
      if(left!=null&&right!=null) return root;
      if(left==null) return right;
      return left;
    }

最大子数组和

链接

public int maxSubArray(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];
        dp[0]=nums[0];
        int ans=dp[0];
        for(int i=1;i<n;i++) {
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            ans=Math.max(dp[i],ans);
        }
        return ans;
    }

重排链表

链接

public void reorderList(ListNode head) {
      // 快慢指针找到链表中点
      ListNode fast = head, slow = head;
      while (fast.next != null && fast.next.next != null) {
          slow = slow.next;
          fast = fast.next.next;
      }

      // cur 指向右半部分链表
      ListNode cur = slow.next;
      slow.next = null;

      // 反转右半部分链表
      ListNode pre = null;
      while (cur != null) {
          ListNode t = cur.next;
          cur.next = pre;
          pre = cur;
          cur = t;
      }
      cur = head;

      // 此时 cur, pre 分别指向链表左右两半的第一个节点
      // 合并
      while (pre != null) {
          ListNode t = pre.next;
          pre.next = cur.next;
          cur.next = pre;
          cur = pre.next;
          pre = t;
      }
  }

相交链表

链接

public ListNode getIntersectionNode(ListNode h1, ListNode h2) {
   if(h1==null||h2==null){
    return null;
   }
   int diff=0;
   ListNode a=h1;
   ListNode b=h2;
   while(a.next!=null){
    a=a.next;
    diff++;
   }
   while(b.next!=null){
    b=b.next;
    diff--;
   }
   if(diff>=0){
    a=h1;
    b=h2;
   }else{
    a=h2;
    b=h1;
   }
   diff=Math.abs(diff);
   while(diff-->0){
    a=a.next;
   }
   while(a!=b){
    a=a.next;
    b=b.next;
   }
   return a;
}

螺旋矩阵

链接

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> list = new ArrayList<Integer>();
    if(matrix == null || matrix.length == 0)
        return list;
    int m = matrix.length;
    int n = matrix[0].length;
    int i = 0; 

    //统计矩阵从外向内的层数，如果矩阵非空，那么它的层数至少为1层
    int count = (Math.min(m, n)+1)/2;
    //从外部向内部遍历，逐层打印数据
    while(i < count) {
        for (int j = i; j < n-i; j++) {
            list.add(matrix[i][j]);
        }
        for (int j = i+1; j < m-i; j++) {
            list.add(matrix[j][(n-1)-i]);
        }
        
        for (int j = (n-1)-(i+1); j >= i && (m-1-i） != i; j--) {
            list.add(matrix[(m-1)-i][j]);
        }
        for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) != i; j--) {
            list.add(matrix[j][i]);
        }
        i++;
    }    
    return list;

}

接雨水

链接

public int trap(int[] nums) {
        int l=1,r=nums.length-2,lmax=nums[0],rmax=nums[nums.length-1];
        int ans=0;
        while(l<=r){
            if(lmax<=rmax){
                ans+=Math.max(0,lmax-nums[l]);
                lmax=Math.max(lmax,nums[l++]);
            }else{
                ans+=Math.max(0,rmax-nums[r]);
                rmax=Math.max(rmax,nums[r--]);
            }
        }
        return ans;
    }

岛屿数量

链接

public int numIslands(char[][] grid) {
       int n=grid.length;
       int m=grid[0].length;
       int island=0;
       for(int i=0;i<n;i++){
           for(int j=0;j<m;j++){
               if(grid[i][j]=='1'){
               island++;
               dfs(grid,i,j,n,m);
               }
           }
       }
        return island;
   }
   public void dfs(char[][] grid,int i,int j,int n,int m){
       if(i<0||i>=n||j<0||j>=m||grid[i][j]!='1'){
           return;
       }
       grid[i][j]='0';
       dfs(grid,i+1,j,n,m);
       dfs(grid,i-1,j,n,m);
       dfs(grid,i,j+1,n,m);
       dfs(grid,i,j-1,n,m);
   }

环形链表

链接

public boolean hasCycle(ListNode head) {
      ListNode slow=head;
      ListNode fast=head;
      while(fast!=null&&fast.next!=null){
       slow=slow.next;
       fast=fast.next.next;
       if(slow==fast){
           return true;
       }
      }
      return false;
   }

买卖股票的最佳时机

链接

public static int maxProfit(int[] prices) {
    int ans = 0;
    for (int i = 1, min = prices[0]; i < prices.length; i++) {
        // min : 0...i范围上的最小值
        min = Math.min(min, prices[i]);
        ans = Math.max(ans, prices[i] - min);
    }
    return ans;
}

全排列

链接

public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> ans=new ArrayList<>();
       f(nums,0,ans);
       return ans; 
   }

   private void f(int[] nums,int i,List<List<Integer>> ans){
       if(i==nums.length){
           List<Integer> list=new ArrayList<>();
           for(int j=0;j<nums.length;j++){
               list.add(nums[j]);
           }
           ans.add(list);
       }else{
          for (int j = i; j < nums.length; j++) {
               swap(nums,i,j);
               f(nums, i+1, ans);
               swap(nums,i,j);
           }
       }
   }

   private void swap(int[] nums,int i,int j){
       int temp=nums[i];
       nums[i]=nums[j];
       nums[j]=temp;
   }

最长递增子序列

链接

public static int lengthOfLIS(int[] nums) {
                int n = nums.length;
                int[] ends = new int[n];
                // len表示ends数组目前的有效区长度
                // ends[0...len-1]是有效区，有效区内的数字一定严格升序
                int len = 0;
                for (int i = 0, find; i < n; i++) {
                        find = bs(ends, len, nums[i]);
                        if (find == -1) {
                                ends[len++] = nums[i];
                        } else {
                                ends[find] = nums[i];
                        }
                }
                return len;
        }
        
        // "最长递增子序列"使用如下二分搜索 :
        // ends[0...len-1]是严格升序的，找到>=num的最左位置
        // 如果不存在返回-1
        public static int bs(int[] ends, int len, int num) {
                int l = 0, r = len - 1, m, ans = -1;
                while (l <= r) {
                        m = l+(r-l) / 2;
                        if (ends[m] >= num) {
                                ans = m;
                                r = m - 1;
                        } else {
                                l = m + 1;
                        }
                }
                return ans;
        }

两数之和

链接

public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            if(map.containsKey(target-nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }

合并两个有序数组

链接

public void merge(int[] nums1, int m, int[] nums2, int n) {
       if (n == 0) return;
       int i = m + n - 1;
       m--;
       n--;
       while (n >= 0) {
           if (m < 0 || nums2[n] > nums1[m]) {
               nums1[i--] = nums2[n--];
           } else {
               nums1[i--] = nums1[m--];
           }
       }
   }

删除排序链表中的重复元素II

链接

public ListNode deleteDuplicates(ListNode head) {
     if (head == null) {
         return head;
     }
     ListNode dummy = new ListNode(0, head);
     ListNode cur = dummy;
     while (cur.next != null && cur.next.next != null) {
         if (cur.next.val == cur.next.next.val) {
             int x = cur.next.val;
             while (cur.next != null && cur.next.val == x) {
                 cur.next = cur.next.next;
             }
         } else {
             cur = cur.next;
         }
     }
     return dummy.next;
 }

有效的括号

链接

public boolean isValid(String s) {
       Deque<Character> stack=new LinkedList<>();
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           if (c=='('){
               stack.push(')');
           }else if (c=='['){
               stack.push(']');
           }else if (c=='{'){
               stack.push('}');
           }else {
               if (!stack.isEmpty()&&c==stack.peek()){
                   stack.pop();
               }else {
                   return false;
               }
           }
       }
       return stack.isEmpty();
   }

字符串相加

链接

public String addStrings(String num1, String num2) {
       int i = num1.length() - 1, j = num2.length() - 1, add = 0;
       StringBuffer ans = new StringBuffer();
       while (i >= 0 || j >= 0 || add != 0) {
           int x = i >= 0 ? num1.charAt(i) - '0' : 0;
           int y = j >= 0 ? num2.charAt(j) - '0' : 0;
           int result = x + y + add;
           ans.append(result % 10);
           add = result / 10;
           i--;
           j--;
       }
       // 计算完以后的答案需要翻转过来
       ans.reverse();
       return ans.toString();
   }

环形链表II

链接

public ListNode detectCycle(ListNode head) {
           ListNode fast = head, slow = head;
           while (true) {
               if (fast == null || fast.next == null) return null;
               fast = fast.next.next;
               slow = slow.next;
               if (fast == slow) break;
           }
           fast = head;
           while (slow != fast) {
               slow = slow.next;
               fast = fast.next;
           }
           return fast;
       }

合并区间

链接

public int[][] merge(int[][] intervals){
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        List<int[]> res=new ArrayList<>();
        for(int[] interval:intervals) {
            if(res.size()==0||interval[0]>res.get(res.size()-1)[1]) {
                res.add(interval);
            }else {
                res.get(res.size()-1)[1]=Math.max(res.get(res.size()-1)[1],interval[1]);
            }
        }
         return res.toArray(new int[res.size()][2]);
    }

二叉树中的最大路径和

链接

public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode() {}
 TreeNode(int val) { this.val = val; }
 TreeNode(int val, TreeNode left, TreeNode right) {
 this.val = val;
 this.left = left;
 this.right = right;
     }
 }
 
 int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }

编辑距离

链接

public int minDistance(String word1, String word2) {
       return editDistance(word1,word2,1,1,1);
   }

   private int editDistance(String word1, String word2, int a, int b, int c) {
       // TODO Auto-generated method stub
       char[] s1 = word1.toCharArray();
       char[] s2 = word2.toCharArray();
       int n=s1.length;
       int m=s2.length;
       int[][] dp=new int[n+1][m+1];
       for (int i= 1; i <=n; i++) {
           dp[i][0]=i*b;
       }
       for (int j = 1; j <=m; j++) {
           dp[0][j]=j*a;
       }
       for (int i = 1; i <=n; i++) {
           for (int j = 1; j <=m; j++) {
               int p1=Integer.MAX_VALUE;
               if (s1[i-1]==s2[j-1]) {
                   p1=dp[i-1][j-1];
               }
               int p2=Integer.MAX_VALUE;
               if (s1[i-1]!=s2[j-1]) {
                   p2=dp[i-1][j-1]+c;
               }
               int p3=dp[i][j-1]+a;
               int p4=dp[i-1][j]+b;
               dp[i][j]=Math.min(Math.min(p1, p2),Math.min(p3, p4));
           }
       }
       return dp[n][m];
   }

复原IP地址

List<String> ans=new ArrayList<>();
   char[] s1;
   public List<String> restoreIpAddresses(String s) {
        s1 = s.toCharArray();
        dfs(0,s1.length, new ArrayList<>());
        return ans;
   }
   void dfs(int ids,int n,List<Integer> cur){
       if(cur.size()>4) return;
       if(ids==n){
           if(cur.size()==4){
               StringBuilder sb=new StringBuilder();
               for(int i=0;i<4;i++) sb.append(cur.get(i)).append(".");
               ans.add(sb.substring(0,sb.length()-1));
           }
       }else{
           for(int i=ids;i<n;i++){
               int t=0;
               for(int j=ids;j<=i;j++) t=t*10+(s1[j]-'0');
                if (s1[ids] == '0' && i != ids) break;
               if (t > 255) break;
               cur.add(t);
               dfs(i + 1, n, cur);
               cur.remove(cur.size() - 1);
           }
       }
       
   }

最长公共子序列

链接

public int longestCommonSubsequence(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int n=s1.length;
        int m=s2.length;
        int[][] dp=new int[n+1][m+1];
        for (int len1 = 1; len1 <=n; len1++) {
            for (int len2 = 1; len2 <=m; len2++) {
                if (s1[len1-1]==s2[len2-1]) {
                    dp[len1][len2]=dp[len1-1][len2-1]+1;
                }else {
                    dp[len1][len2]=Math.max(dp[len1-1][len2],dp[len1][len2-1]);
                }
            }
        }
        return dp[n][m];
    }

二叉树的中序遍历

链接

public List<Integer> inorderTraversal(TreeNode root) {
      // List<Integer> res = new ArrayList<Integer>();
      // inorder(root, res);
      // return res;
      List<Integer> res=new ArrayList<>();
      Deque<TreeNode> stack=new LinkedList<TreeNode>();
      while(root!=null||!stack.isEmpty()){
          while(root!=null){
              stack.push(root);
              root=root.left;
          }
          root=stack.pop();
          res.add(root.val);
          root=root.right;
      }
      return res;
  }

  // public void inorder(TreeNode root, List<Integer> res) {
  //     if(root==null){
  //         return;
  //     }
  //     inorder(root.left,res);
  //     res.add(root.val);
  //     inorder(root.right,res);
  // }

二分查找

链接

public int search(int[] nums, int target) {
       int i=0;
       int j=nums.length-1;

       while (i<=j){
           int m=(i+j)>>>1;
           if (nums[m]<target){
               i=m+1;
           }else if (nums[m]>target){
               j=m-1;
           }else {
               return m;
           }
       }
       return -1;
   }

二叉树的右视图

链接

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if(root == null) return res;
        queue.offer(root);
        for(;!queue.isEmpty();){
            int size = queue.size();
            TreeNode lastOne = null;
            for(int i=0; i<size; i++){
                lastOne = queue.poll();
                if(lastOne.left != null) queue.offer(lastOne.left);
                if(lastOne.right != null) queue.offer(lastOne.right);
            }
            res.add(lastOne.val);
        }
        return res;
    }

寻找两个正序数组中的中位数

链接

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
           if (nums1.length > nums2.length) {
               return findMedianSortedArrays(nums2, nums1);
           }
           int m = nums1.length;
           int n = nums2.length;
           int left = 0, right = m;
           // median1：前一部分的最大值
           // median2：后一部分的最小值
           int median1 = 0, median2 = 0;
           while (left <= right) {
               // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
               // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
               int i = (left + right) / 2;
               int j = (m + n + 1) / 2 - i;
               // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
               int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
               int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
               int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
               int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);
               if (nums_im1 <= nums_j) {
                   median1 = Math.max(nums_im1, nums_jm1);
                   median2 = Math.min(nums_i, nums_j);
                   left = i + 1;
               } else {
                   right = i - 1;
               }
           }
           return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
       }

下一个排列

链接

public void nextPermutation(int[] nums) {
           int n = nums.length, k = n - 1;
           while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;
           if (k == 0) {
               reverse(nums, 0, n - 1);
           } else {
               int u = k;
               while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;
               swap(nums, k - 1, u);
               reverse(nums, k, n - 1);
           }
       }
       void reverse(int[] nums, int a, int b) {
           int l = a, r = b;
           while (l < r) swap(nums, l++, r--);
       }
       void swap(int[] nums, int a, int b) {
           int c = nums[a];
           nums[a] = nums[b];
           nums[b] = c;
       }

用栈实现队列

链接

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack=new ArrayDeque<Integer>();
        outStack=new ArrayDeque<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
    
    public int peek() {
        if(outStack.isEmpty()){
             while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();

    }
    
    public boolean empty() {
        return inStack.isEmpty()&&outStack.isEmpty();
    }
}

只要我还在刷题，持续更新