鸟窝

一

0%

算法板子

发表于 更新于 分类于
Valine：
本文字数： 12k 阅读时长 ≈ 11 分钟
这里记录一些平常遇到用到的算法模板

表达式

逆波兰表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

//中缀转后缀(逆波兰)
public class PostfixExpression {



    /**
     * 如果后续有根号等操作符  和括号一样思路加入即可
     * @param expression
     * @return
     */
    //中缀转后缀
    public static String nifixToPostfix(String expression) {
        expression = expression.replaceAll(" ", "");
        //后缀表达式
        StringBuilder postfix = new StringBuilder();
        //符号栈
        Deque<String> ops = new LinkedList<>();

        //防止首位就是符号
        postfix.append("0 ");

        char[] chars = expression.toCharArray();
        int n = chars.length, i = 0;

        while (i < n) {
            //记录操作数
            StringBuilder s = new StringBuilder();
            //标记操作数是否为数字
            boolean flag = false;

            //处理多位数以及小数
            while (i < n && (chars[i] >= '0' && chars[i] <= '9' || chars[i] == '.')) {
                flag = true;
                s.append(chars[i++]);
            }
            //添加符号
            if (!flag) s.append(chars[i++]);
            //转换为字符串
            String ss = s.toString();

            //判断操作数是否为数字
            if (flag) {
                //添加到表达式
                postfix.append(ss);
                postfix.append(" ");
            } else {
                //将(- => (0-   (+ => (0+  ++ => 0+  -+ => 0-  等等 两个符号同时出现的特殊情况
                char t='0';
                if (i>1 && (t=chars[i - 2])>=0 && !ss.equals("(") && (t =='(' || t =='+' || t =='-' || t =='*' || t =='/')){
                    postfix.append("0 ");
                    //标记 * / 运算符后出现 + - 时不遵守将符号栈按优先级弹出至表达式
                    flag=true;
                }


                //操作数为(时 直接加入符号栈
                if (ss.equals("(")) {
                    ops.addLast("(");
                } else if (ss.equals(")")) {
                    //操作数为)
                    //依次弹出符号到表达式中
                    //直到遇到(
                    //当有)括号时  应当先计算括号内的运算符 所以需要把运算符先弹出至表达式
                    while (!ops.peekLast().equals("(")) {
                        postfix.append(ops.pollLast());
                        postfix.append(" ");
                    }
                    //抛弃(括号
                    ops.pollLast();
                } else {
                    //比较运算符   以下是中转后和中转前最大的区别
                    //当前操作数优先级大于栈顶符号时   直接加入符号库
                    //当前操作数优先级小于等于栈顶符号时  依次弹出符号库到表达式 直至优先级大于
                    //为什么符号位优先级相同是也要把符号弹出，是因为要遵守表达式从左到右计算规则
                    while (!ops.isEmpty() && !flag && opsCompareTo(ss) <= opsCompareTo(ops.peekLast())) {
                        postfix.append(ops.pollLast());
                        postfix.append(" ");
                    }
                    //添加符号
                    ops.addLast(ss);
                }
            }
        }

        //将符号栈依次加入表达式
        while (!ops.isEmpty()) {
            postfix.append(ops.pollLast()+" ");
        }

        return postfix.toString();
    }


    //比较优先级
    static int opsCompareTo(String ops) {
        if (ops.equals("+") || ops.equals("-")) return 0;
        if (ops.equals("*") || ops.equals("/")) return 1;
        //符号栈中会出现( 它的优先级最低
        return -1;
    }

    static double calc(String postfix){
        String[] s = postfix.split(" ");
        Deque<Double> nums=new LinkedList<>();
        for (String ss : s) {
            if (opsCompareTo(ss)!=-1){
                double b=nums.pollLast();
                double a=nums.pollLast();
                switch (ss){
                    case "+":
                        ss=a+b+"";
                        break;
                    case "-":
                        ss=a-b+"";
                        break;
                    case "*":
                        ss=a*b+"";
                        break;
                    case "/":
                        ss=a/b+"";
                        break;
                }
            }
            nums.addLast(Double.parseDouble(ss));
        }
        return nums.pollLast();
    }


}

矩阵快速幂

斐波那契额数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 斐波那契数列快速幂求法
public class Solution {

    //最大素数
    static int mod = (int) 1e9 + 7;

    //矩阵乘法
    public static long[][] mul(long[][] a, long[][] b) {
        int x = a.length, y = b[0].length, z = b.length;
        //答案矩阵大小为a的行  b的列
        long[][] ans = new long[x][y];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                for (int k = 0; k < z; k++) {
                    //矩阵相乘
                    ans[i][j] += a[i][k] + b[k][j];
                    ans[i][j] %= mod;
                }
            }
        }
        return ans;
    }

    //返回斐波那契数列的第n个数
    public static long fid(int n) {
        if (n <= 1) return n;
        
        //矩阵快速幂的mat矩阵 
        long[][] mat = new long[][] { 
            { 1, 1 }, 
            { 1, 0 } 
        };

        //初始矩阵
        long[][] ans = new long[][] { 
            { 1 }, 
            { 0 } 
        };

        //公式
        /* 
        f(n)=mat^n-1 * [f(1)
                        f(0)]
        */

        //幂次
        int x = n - 1;

        //利用快速幂思想加速幂次计算
        while (x != 0) {
            //mul(mat, ans) 相当于ans * mat * mat * mat ......
            if ((x & 1) == 1) ans = mul(mat, ans);
            //向左位移一位
            x >>= 1;
            mat = mul(mat, mat);
        }

        //最终ans[0][0]既是答案
        return ans[0][0] % mod;

    }

}

排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Solution {
    
    static Random random = new Random();
    static int k;
    
    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) return;

        int i = l, j = r;

        //思想：基本的快速排序选取第一个或者最后一个元素作为基准。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，
        // 即随机选取一个元素作为基准。这种情况下虽然最坏情况仍然是O(n2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2n)。
        // 所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。
        //nextInt随机[0,r-l),所以r-l需要加一
        int ridx = random.nextInt(r - l + 1) + l;
        //将基准点交换到l位置
        swap(arr, ridx, l);
        //取值基准点
        int target = arr[l];
        while (i < j) {
            //<=和>=是为了避免出现i和j指针的数据与target相同造成死循环的情况
            while (i < j && arr[j] >= target) j--;
            while (i < j && arr[i] <= target) i++;
            //交换位置
            //小于target的放在左边，大于的放在右边
            swap(arr, i, j);
        }

        //将基准点和i指针的数据交换
        //为什么i指针的数据确保比基准点小呢     i指针所指向的数据在上面的while循环中经过交换确保i指针的数据永远比target小,最差就是i指针的数据就是target本身
        swap(arr, i, l);

        //以下两种排序方式
        /*
        *基于k点进行排序
        *idx < k：基准点左侧不足 k 个，递归处理右边，让基准点下标右移；
        *idx > k：基准点左侧超过 k 个，递归处理左边，让基准点下标左移；
        *idx = k：基准点左侧恰好 k 个，输出基准点左侧元素。

        *if (i > k) sort(arr, l, i - 1);
        *if (i < k) sort(arr, i + 1, r);
        */


        /*
        * 全部排序
        */
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }

    //交换两点
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

Dijkstra单源最短路径

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class Solution{
		//邻接矩阵
    int[][] W;
    //记录起点到其他点的最短路径
    int[] dist;
    //记录那些是确认结点
    boolean[] vis;
    //10的九次方的一半   避免相关路径相加溢出
    int inf = 0x3f3f3f3f;
    //n为结点数量  k为起点
    int n, k;

    public int networkDelayTime(int[][] times, int _n, int _k) {
        n = _n;
        k = _k;
        dist = new int[n + 1];
        vis = new boolean[n + 1];
        W = new int[n + 1][n + 1];
        //初始化邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                W[i][j] = W[j][i] = inf;
            }
        }
        //记录邻接矩阵
        for (int[] time : times) {
            int u = time[0], v = time[1], w = time[2];
            W[u][v] = w;
        }

        //寻找原点到其他点的最短距离
        dijkstra();

        int ans = 0;
        //寻找原点到其他点的最短距离的最大值
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans >= inf ? -1 : ans;
    }

    void dijkstra() {
        //初始化dist
        Arrays.fill(dist, inf);
        //vis初始就是false
        //起点为0
        dist[k] = 0;

        for (int i = 1; i <= n; i++) {
            int t = -1;
            //找到未确认结点的最短路径
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (t == -1 || dist[j] < dist[t])) t = j;
            }

            //更新为确认结点
            vis[t] = true;

            //以t为跳板 确定其他结点的最短路径
            for (int j = 1; j <= n; j++) {
                //确认是 原点到j 的距离短还是 原点到跳板+跳板到j的距离短 
                dist[j] = Math.min(dist[j], dist[t] + W[t][j]);
            }
        }
    }
}

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    int N = 110, M = 6010;
    // 邻接表
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist = new int[N];
    // 记录哪些点已经被更新过
    boolean[] vis = new boolean[N];
    int n, k, idx;
    int INF = 0x3f3f3f3f;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        // 初始化链表头
        Arrays.fill(he, -1);
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        // 最短路
        dijkstra();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void dijkstra() {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
        q.add(new int[]{k, 0});
        while (!q.isEmpty()) {
            // 每次从「优先队列」中弹出
            int[] poll = q.poll();
            int id = poll[0], step = poll[1];
            // 如果弹出的点被标记「已更新」，则跳过
            if (vis[id]) continue;
            // 标记该点「已更新」，并使用该点更新其他点的「最短距离」
            vis[id] = true;
            for (int i = he[id]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[id] + w[i]) {
                    dist[j] = dist[id] + w[i];
                    q.add(new int[]{j, dist[j]});
                }
            }
        }
    }
}

文章作者:xpp011

发布时间:2021年11月14日 - 23:11

原始链接:http://xpp011.cn/2021/11/14/83145831.html

许可协议: 转载请保留原文链接及作者。