算法合集(持续更新)

更新于 2024-12-15 分类于算法本文字数： 5k 阅读时长 ≈ 18 分钟

数学
最短路径
二分 + BFS
并查集
线段树
记忆化搜索
单例模式

1. 数学

1.1 C_n^m计算

思路

用公式 C_n^m = C_n-1^m + C_n-1^m-1

处理好边界值 C₀^0^ = 1 , C0^1^ = 0 , C1^0^ = 1

//
public static long calCnm1(int n, int m) {
        if (n == m)
            return 1;
        if (n == 0)
            return 0;
        if (m == 0) {
            return 1;
        }
        return calCnm1(n - 1, m) + calCnm1(n - 1, m - 1);
    }

直接用展开式阶乘计算

public static long calCnm2(int n, int m) {
        if (m > n || m < 0) return 0;
    //消除分子、分母重叠部分，只是为了简化计算，去掉这行也能运行
        m = Math.min(m, n - m);
        long result = 1;
        for (int k = 1; k <= m; k++) {
            result = result * (n - k + 1) / k;
        }
        return result;
    }

1.2 快速幂

思路：

幂计算可以暴力O(n)复杂度直接for循环乘 x 得到，但是会重复计算部分值。

考虑将n用位运算按二进制进行拆分（例：5^9^ = 5^2⁰ * 5^2³ 即 5^9^ = 5^1^ * 5^8^）。5^1^*5^1^ = 5^2^ 5^2^ * 5^2^ = 5^4^ 5^4^ * 5^4^ = 5^8^ 这样可以将时间复杂度缩减到 O(log n)

public class fastPow {
    static int MOD = 100000007;
    public static void main(String[] args) {
        System.out.println(pow(3, 4));
    }
    
    public static long pow(int x, int n) {
        long ans = 1;
        while (n > 0) {
            //对应二进制位为1则乘上结果
            if ((n & 1) == 1) {
                ans = ans * x % MOD;
            }
            //更新中间结果
            x = x * x % MOD;
            //位运算右移一位
            n >>= 1;
        }
        return ans;
    }
}

1.3 质数筛选 (埃氏筛)

时间复杂度为O(nloglog(n))

public int countPrime(int n){
        boolean []isPrime = new boolean[n];
        //初始化所有数都为质数
        Arrays.fill(isPrime,true);
        int ans = 0;
        for (int i = 2; i < n; i++) {
            //如果是质数
            if(isPrime[i]){
                ans+=1;
                //将i*i, 2i*i,3i*i都标记为非质数。
                if((long)i*i<n){
                    for (int j = i*i; j < n; j+=i) {
                        isPrime[j] = false;
                    }
                }
            }
        }
        return ans;
    }

2. 最短路径

2.1 Dijkstra

2.1.1 LeetCode_1514

前提：路径无负值。

思路（贪心）：

一点与其相邻点之间的距离最短的那一点一定是最短距离。

例：A的相邻点和距离分别为{B,C,D,E,F} ，{5,2,3,4,9}。那么A点到C点的最短距离一定是2。
求一点到另一点的最短路径，可以由一点和他相邻点的最短路径推出来。

接着上面的例子，假设C到F的距离是1，因为 9 > 2+1 那么A与其他点的距离为{B,C,E,F} {5,3,4,3}，那么A到F点的最短距离是3，到C点的最短距离也为3。

路径信息不建议使用数组存放，数组会记录许多无效路径，可能超内存。

数组版

//LeetCode_1514为例，数组版会超时
public double djst1(int n, int start, int end, int[][] edges, double[] succProb) {
    //dist存放其它节点与起点最近距离
        double[] dist = new double[n];
    //优先队列获取最小值，避免O(n)时间复杂度遍历dist数组
       Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> Double.compare(dist[o2], dist[o1]));
        double[][] graph = new double[n][n];
    //1.初始化
        for (int i = 0; i < edges.length; i++) {
            graph[edges[i][0]][edges[i][1]] = succProb[i];
            graph[edges[i][1]][edges[i][0]] = succProb[i];
            if (edges[i][0] == start) {
                dist[edges[i][1]] = succProb[i];
                queue.add(edges[i][1]);
            } else if (edges[i][1] == start) {
                dist[edges[i][0]] = succProb[i];
                queue.add(edges[i][0]);
            }
        }
    //2.具体更新距离逻辑
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int i = 0; i < n; i++) {
                //更新距离逻辑，可根据题目变化更改具体的判断逻辑，只要符合求最小值的逻辑即可
                if (graph[node][i] != 0 && dist[i] < graph[node][i] * dist[node]) {
                    dist[i] = graph[node][i] * dist[node];
                    queue.add(i);
                }
            }
        }
        return dist[end];
    }

邻接矩阵版

public double djst2(int n, int start, int end, int[][] edges, double[] succProb) {
        double[] dist = new double[n];
         Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> Double.compare(dist[o2], dist[o1]));
        double[][] graph = new double[n][n];
        for (int i = 0; i < edges.length; i++) {
            graph[edges[i][0]][edges[i][1]] = succProb[i];
            graph[edges[i][1]][edges[i][0]] = succProb[i];
            if (edges[i][0] == start) {
                dist[edges[i][1]] = succProb[i];
                queue.add(edges[i][1]);
            } else if (edges[i][1] == start) {
                dist[edges[i][0]] = succProb[i];
                queue.add(edges[i][0]);
            }
        }
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int i = 0; i < n; i++) {
                if (graph[node][i] != 0 && dist[i] < graph[node][i] * dist[node]) {
                    dist[i] = graph[node][i] * dist[node];
                    queue.add(i);
                }
            }
        }
        return dist[end];
    }

class Pair {
    double succProb;
    int node;

    public Pair(double succProb, int node) {
        this.succProb = succProb;
        this.node = node;
    }
}

2.2 Floyd

思路：动态规划

节点i、j之间的最小值一定由i、k与k、j之间转移过来

public void floyd(int n,int[][] arr) {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
                }
            }
        }
    }

Floyd时间复杂度为O(n^3^)，Dijkstra为O(n^2^)，不过Floyd可以求每两点之前最小值，并且把min改成max就可以求最大路径了。

3. 二分答案

3.1 华为2024_9_19笔试_2（二分+BFS）

描述

有一个NxN 大小的迷宫。初始状态下，配送员位于迷官的左上角，他希望前往迷宫的右下角。
配送员只能沿着上下左右四个方向移动，从每个格子移动到相邻格子所需要的时间是1个单位，他必须用最多 K个(也可以少于 K 个)单位时间到达右下角格子。
迷宫的每个格子都有辐射值，配送员必须穿着防护能力不低于相应辐射值的防护服，才能通过该格子。他希望知道，防护服的防护能力最少要达到多少，他才能顺利完成任务。注意:配送员需要通过迷官的左上角和右下角，因此防护服的防护能力必须大于等于这两个格子的辐射值。

输入描述

前两行各包含一个正整数，分别对应N和K，后 N 行各包含 N 整数，以空格分隔，表示地图上每个位置的辐射值。
2≤N≤100 。K≥2N-2，以保证题目有解。所有辐射值都是非负整数，绝对值不超过 10^4

输出描述

一个整数，表示配送员穿着防护服的最低防护能力。

用例输入

用例输出

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @description: 二分+BFS，DFS需重复判断depth会超时
 * @author：ruizhi
 * @date: 2024/10/27
 * @Copyright：
 */
public class ProtectiveEquipment_20240919_2 {
    static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[][] arr = new int[n][n];
        int right = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = in.nextInt();
                right = Math.max(arr[i][j], right);
            }
        }
        int left = Math.max(arr[0][0], arr[n - 1][n - 1]);
        int result = right;
        //结果可能区间二分判断
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (check(mid, arr, n, k)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(result);
    }
    /*
    	判断防护值为limit，k步内是否能走到右下角
    */
    public static boolean check(int limit, int[][] arr, int n, int k) {
        boolean[][] used = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        used[0][0] = true;
        int depth = 0;
        while (!queue.isEmpty() && depth < k) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                for (int[] ints : dir) {
                    int newI = pos[0] + ints[0];
                    int newJ = pos[1] + ints[1];
                    if (newI == n - 1 && newJ == n - 1)
                        return true;
                    if (newI >= 0 && newJ >= 0 && newI < n && newJ < n && !used[newI][newJ] && arr[newI][newJ] <= limit) {
                        used[newI][newJ] = true;
                        queue.add(new int[]{newI, newJ});
                    }
                }
            }
        }
        return false;
    }
}

3.2 分割数组的最大值

LeetCode_410 分割数组的最大值

class Solution {
    public int splitArray(int[] nums, int k) {
        int right = 0;
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            left = Math.max(left, nums[i]);
            right += nums[i];
        }
        while (left < right) {
            int mid = left + (right-left)/2;
            if(check(nums,mid,k)){
                right = mid;
            }else {
                left = mid +1;
            }
        }
        return right;
    }

    public boolean check(int[] nums, int num, int k) {
        int sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.length; i++) {
            if (sum + nums[i] > num) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        return cnt <= k;
    }
}

4. 并查集

/**
 * @description: 并查集，主要是图的连通块相关的题目
 * @author：ruizhi
 * @date: 2024/10/28
 * @Copyright：
 */
public class UnionFind {
    public void demo (int[][] edges,int n) {
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
           //并查集生成过程
            int[] edge = edges[i];
            //连通边
            int node1 = edge[0], node2 = edge[1];
            //根节点不相同，则合并
            if (find(parent, node1) != find(parent, node2)) {
                union(parent, node1, node2);
            }
        }
        //可以遍历数组来看有几个不同的根节点看连通块
        //可以在遍历过程中看有几条对连通无效的边
    }
    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }
    //递归查找，并统一将子节点指向同一个根节点
    public int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
}

5. 线段树

作用：线段树可以在O(log N)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值)等操作。

/**
 * @description: 线段树模版
 * @author：ruizhi
 * @date: 2024/10/31
 * @Copyright：
 */
public class SegmentTree {
    private int[] tree;
    private int[] nums;

    public SegmentTree(int[] nums) {
        this.nums = nums;
        tree = new int[nums.length * 2 + 1];
        constructTree(0, nums, 0, nums.length - 1);
    }

    private void constructTree(int node, int[] nums, int left, int right) {
        if (left == right) {
            tree[node] = nums[left];
        } else {
            int mid = left + (right - left) / 2;
            constructTree(node * 2 + 1, nums, left, mid);
            constructTree(node * 2 + 2, nums, mid + 1, right);
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }

    public void updateTree(int index, int val) {
        updateTree(0, index, val, 0, nums.length - 1);
    }

    private void updateTree(int node, int index, int val, int left, int right) {
        if (left == right) {
            tree[node] = val;
        } else {
            int mid = left + (right - left) / 2;
            if (index >= left && index <= mid) {
                updateTree(node * 2 + 1, index, val, left, mid);
            } else {
                updateTree(node * 2 + 2, index, val, mid + 1, right);
            }
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }

    public int queryTree(int left, int right) {
        return queryTree(0, left, right, 0, nums.length - 1);
    }

    private int queryTree(int node, int left, int right, int l, int r) {
        if (left == l && right == r) {
            return tree[node];
        } else {
            int mid = l + (r - l) / 2;
            if (right <= mid) {
                return queryTree(node * 2 + 1, left, right, l, mid);
            } else if (left > mid) {
                return queryTree(node * 2 + 2, left, right, mid + 1, r);
            } else {
                return queryTree(node * 2 + 1, left, mid, l, mid) + queryTree(node * 2 + 2, mid + 1, right, mid + 1, r);
            }
        }
    }
}

LeetCode_3165

```

# 6. 记忆化搜索

[参考牛马OJ][https://niumacode.com/archives]

## 6.1 魔法石碑

题目描述：

在一个神秘的魔法世界里，有一个奇怪的魔法数字石碑，上面刻着一个正整数 。
这个数字石碑有一种神奇的属性，可以通过特定的魔法操作将数字变成1。石碑的守护者希望你能找到一种方法，以最少的操作次数将石碑上的数字变成1，从而解开古老的谜题。

你可以做如下操作：

如果 n 是偶数，则用 n/2 替换 n 。
如果 n 是奇数，则可以用 n+1 或 n-1 替换 n 。
你的任务是找到将 变为 1 所需的最小替换次数。

输入描述:
输入包含一个正整数n。1<=n<=2^32-1
输出描述:
输出一个整数，表示将 n 变为 1 所需的最小替换次数。

输入 8 输出 3
输入 7 输出 4

```java
//从小到大dp时间复杂度为O(n)超时，因为会记录许多无效数据
// 使用dfs+Map记忆化时间复杂度为O(logN)且不需要使用O(n)的数组
public class MagicStoneMonument {
    static Map<Long,Integer> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        System.out.println(dfs(n));
    }
    public static int dfs(long n){
        if(n==1)
            return 0;
        if(map.containsKey(n)){
            return map.get(n);
        }
        int num;
        if(n%2==0){
            num = 1+dfs(n/2);
        }else{
            num = 1+Math.min(dfs(n-1),dfs(n+1));
        }
        map.put(n,num);
        return num;
    }
}

6.2 小马的数组构造

描述

小马拿到了一个数组a，她准备构造一个数组b满足：

b的每一位都和a对应位置不同，即 bi != ai
b 的所有元素之和都和 a 相同。
b的数组均为正整数。请你告诉小马有多少种构造方式。由于答案过大，请对 10^9+7取模。

输入描述

第一行输入一个正整数n，代表数组的大小。第二行输入n个正整数ai，代表小美拿到的数组

1<=n<=100, 1<=ai<=300, 1<=Σai <= 500

输出描述

一个整数，代表构造方式对 10^9+7取模的值。

用例输入 1

1
2

3
1 1 3

用例输出 1

用例输入 2

1
2

3
1 1 1

用例输出 2

dfs遍历每一个位置的可能数，使用数组存放信息。

import java.util.*;

public class ConstructArray {
    static int MOD = 1000000007;
    static int[][] dp;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int []arr = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            sum += arr[i];
        }
        dp = new int[n+1][sum+1];
        for (int i = 0; i < dp.length; ++i) {
            Arrays.fill(dp[i], -1);
        }
        System.out.println(dfs(sum,arr,0));
    }
    //dfs表示从start位置构造数组使数组结果等于sum有多少种情况
     public static int dfs(int sum,int[] arr,int start){
        if(start == arr.length-1){
            return sum != arr[arr.length - 1] ? 1 : 0;
        }
        if(dp[start][sum]!=-1){
            return dp[start][sum];
        }
        int count = 0;
        for (int i = 1; i <= sum - (arr.length-start)+1; i++) {
            if(arr[start]==i)
                continue;
            count=(count+dfs(sum-i,arr,start+1))%MOD;
        }
        dp[start][sum] = count;
        return count;
    }
}

6.3 人员派遣

描述

某公司有n名员工，第i名员工具有的能力可以用一个正整数ai描述，称为员工的能力值，现在，公司有一个项目需要交给恰好[n/2]名员工负责。为了保证项目能顺利进行，要求负责该项目的所有员工能力值之和大于等于x。
公司希望你可以帮忙求出，有多少种不同的派遣员工来负责这个项目的方案。
上文中，[x]风表示大于等于x的最小整数，例[4] =4，[4.2]=5。认为两个方案不同，当且仅当存在一名员工在一种方案中负责该项目，而在另一种方案中不负责.

输入描述

输入包含多组数据，输入第一行包含一个整数T (1<=T<=10) ，表示数据组数.
接下来2T行，每两行描述了一组数据.
每组数据第一行包含两个正整数n(1<=n<=16) 和x (1<=x<=210^4)，分别表示公司的员工总数和项目对负责员工能力值之和的要求。
每组数据第二行包含n个整数，第i个整数表示第i名员工的能力值ai(1<=ai<=10^3)。
对于100%的数据，满足1<=n<=16，1<=x<=2104，1<=T<=10，1<=ai<=103。

输出描述

输出包含T行。对于每组数据输出一行一个整数，表示可行的派遣方案数.

用例输入 1

3
5 10
3 2 3 4 5
3 3
1 1 1
10 10
3 1 2 8 5 4 2 9 12 7

用例输出 1

1
2
3

7
0
252

public class ProjectDispatch {
    static int[][][] dp;
    //最大能力值和
    static int MAXSUM = 16001;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T-->0) {
            int n = in.nextInt();
            int x = in.nextInt();
            int []arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            int num = n%2==0?n/2:(n/2+1);
            dp = new int[n+1][num+1][MAXSUM];
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < dp[i].length; j++) {
                    Arrays.fill(dp[i][j],-1);
                }
            }
            System.out.println(dfs(num,x,0,arr,0));
        }
    }
    public static int dfs(int num,int x,int depth,int[] arr,int sum){
        if(num == 0){
            return sum>=x?1:0;
        }
        if(num<0||depth>=arr.length){
            return 0;
        }

        if(dp[depth][num][sum]!=-1)
            return dp[depth][num][sum];
        int count = dfs(num-1,x,depth+1,arr,sum+arr[depth])+dfs(num,x,depth+1,arr,sum);
        dp[depth][num][sum] = count;
        return count;
    }
}

6.4 总结

记忆化搜索一般用于构造数据有多少种情况之类的题目，这类题目通常需要将多个位置排列组合后判断是否合理，需要通过dfs，dfs会通过重复路径，这时可用dp数组或者map之类的数据存放已经计算出的结果，减少消耗时间。

dfs步骤：

边界判断
判断是否已经计算过该种情况
按题意进行dfs
记录结果

public static int dfs(int sum,int[] arr,int start){
    //1. 边界判断
         if(start == arr.length-1){
            return sum != arr[arr.length - 1] ? 1 : 0;
        }
    //2. 判断是否已经计算过该种情况
        if(dp[start][sum]!=-1){
            return dp[start][sum];
        }
    //3. 按题意进行dfs
    	int count = 0;
        for (int i = 1; i <= sum - (arr.length-start)+1; i++) {
            if(arr[start]==i)
                continue;
            count=(count+dfs(sum-i,arr,start+1))%MOD;
        }
    //4. 记录结果
        dp[start][sum] = count;
        return count;
}

7. 动态规划

[参考牛马OJ][https://niumacode.com/archives]

7.1 背包问题模版

普通背包问题

int n, C; //n个物品， C表示背包容量
int[] v,  w; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int[][] dp = new int[n + 1][C + 1]; //容器规模
dp[0][j]; //初始化
for (int i = 1 ; i <= n ; i++) {
    for (int j = 0 ; j <= C ; j++) {
        if (j >= v[i - 1]) 
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i - 1]);
        else 
            dp[i][j] = dp[i - 1][j];
    }
}
return dp[n][C];

完全背包问题

int n, C; //n个物品， C表示背包容量
int[] v,  w; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int[][] dp = new int[n + 1][C + 1]; //容器规模
dp[0][j]; //初始化
for (int i = 1 ; i <= n ; i++) {
    for (int j = 0 ; j <= C ; j++) {
        if (j >= v[i - 1]) 
            //选择该物品或者不选该物品
            dp[i][j] = max(dp[i-1][j], dp[i][j-v[i-1]] + w[i - 1]);
        else 
            dp[i][j] = dp[i - 1][j];
    }
}
return dp[n][C];

注意：使用滚动数组优化时注意状态变更情况，可能需要从大到小遍历。

面试

1. 单例模式

1.1 类直接持有单例

/**
 * @description: 饿汉模式
 * @author：ruizhi
 * @date: 2024/10/26
 * @Copyright：
 */
public class SingletonPattern2 {
    public static final SingletonPattern2 INSTANCE = new SingletonPattern2();
    public SingletonPattern2 getInstance(){
        return INSTANCE;
    }
}

1.2 类间接持有属性

1.2.1 双检校验

/**
 * @description: 双检锁实现,懒汉模式
 * @author：ruizhi
 * @date: 2024/10/26
 * @Copyright：
 */
public class SingletonPattern1 {
    //volatile 用于禁止JVM指令重排
    public static volatile SingletonPattern1 INSTANCE;
    //常规的双检锁校验
    public SingletonPattern1 getINSTANCE() {
        if(INSTANCE == null){
            synchronized (SingletonPattern1.class){
                if(INSTANCE == null){
                    //具体的初始化逻辑
                    INSTANCE = new SingletonPattern1();
                    try{
                        Thread.sleep(350L);
                    }catch (InterruptedException e){
                        e.printStackTrace();
                    }
                }
            }
        }
        return INSTANCE;
    }
    private SingletonPattern1(){
        //将构造方法改为静态，防止外部调用
    }
}

1.2.2 静态内部类

/**
 * @description: 使用静态内部类持有单例对象，静态内部类会在使用时被加载
 * @author：ruizhi
 * @date: 2024/10/26
 * @Copyright：
 */
public class SingletonPattern4 {
    private static boolean instanceCreated = false;
    private SingletonPattern4(){    
        instanceCreated = true;
    }
    public static class InnerSingleton {
        private static SingletonPattern4 instance=new SingletonPattern4();// 自行创建实例
    }

    public static SingletonPattern4 getInstance() {
        return InnerSingleton.instance;/
    }
}

1.2.3 枚举

最推荐的实现方式，枚举可以懒汉式的加载，又可以防止反射和反序列化攻击，使得对象单例的保证。

防止反射攻击：

枚举的构造方法在 java.lang.reflect.Constructor 中有特殊检查，无法通过反射调用

防止反序列化攻击：

序列化过程中，枚举类型使用 Enum.readResolve() 方法，确保反序列化返回相同的枚举实例，而不是创建新的对象。

/**
 * @description: 使用枚举持有单例对象，反序列化不会创建新对象；枚举实例也是在第一次使用时被加载
 * @author：ruizhi
 * @date: 2024/10/26
 * @Copyright：
 */
public class SingletonPattern3 {
    private SingletonPattern3(){

    }
    private enum Singleton{
        INSTANCE;

        private final SingletonPattern3 instance;
        Singleton(){
            instance = new SingletonPattern3();
        }
        private SingletonPattern3 getInstance(){
            return instance;
        }
    }
    public static SingletonPattern3 getInstance(){
        return Singleton.INSTANCE.getInstance();
    }
}

2. 链表

2.1 leetcode19. 删除链表的倒数第 N 个结点

思路：

两次遍历：统计链表长度，定位到要删除的节点

一次遍历：快慢指针，快指针先走n步，慢指针再随着快指针一直遍历到尾部（快指针比慢指针快n步，到尾部时慢指针后一个节点就是倒数第n个节点）。

class ListNode {
     int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    //两次遍历
    public ListNode removeNthFromEnd1(ListNode head, int n) {
 		ListNode p = head;
        int num = 0;
        // num为链表长度+1
        while(p!=null){
            p=p.next;
            num++;
        }
        p = head;
        //遍历到链表后面有n个节点
        for (int i = 0; i < num - n - 1; i++) {
            p=p.next;
        }
        //边界情况判断，可以通过添加前导节点解决。
        if(n == num){
            head = head.next;
        }else{
            p.next = p.next.next;
        }
        return head;
    }
    //一次遍历
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //添加前导节点处理要删除的是头结点情况
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

2.2 leetcode_143. 重排链表

美团、途虎

思路：

链表顺序访问变随机访问：使用map记录结点位置
快慢指针反转后后半部分：使用快慢指针（快走两步、慢走一步），反转后半部分链表后再遍历。

1. 数学

1.1 Cnm计算

1.2 快速幂

1.3 质数筛选 (埃氏筛)

2. 最短路径

2.1 Dijkstra

2.1.1 LeetCode_1514

2.2 Floyd

3. 二分 答案

3.1 华为2024_9_19笔试_2（二分+BFS）

3.2 分割数组的最大值

4. 并查集

5. 线段树

6.2 小马的数组构造

6.3 人员派遣

6.4 总结

7. 动态规划

7.1 背包问题模版

面试

1. 单例模式

1.1 类直接持有单例

1.2 类间接持有属性

1.2.1 双检校验

1.2.2 静态内部类

1.2.3 枚举

2. 链表

2.1 leetcode19. 删除链表的倒数第 N 个结点

2.2 leetcode_143. 重排链表

1.1 C_n^m计算

3. 二分答案