数组结构与算法

数据结构与算法

稀疏数组sparse

• 二维数据转稀疏数组（chessToSparse）
• 稀疏数组转二维数组（sparseToChess）
• IO存盘

队列

• 使用数组模拟循环队列（ArrayCircleQueue）
  元素个数：rear + maxsize + front % maxsize
  判断队列是否为空：
• 使用链表模拟队列

单向链表

• 链表新增
• 链表删除
• 链表修改
• 链表反转

双向链表

• 链表新增
• 链表删除
• 链表修改

单向环形列表：CircleSingleLinkedList

• 约瑟夫问题

栈

• 实现计算器计算【722-5+1-5+3-4=？】的结果
• 前缀表达式
• 中缀表达式
• 后缀表达式
• 中缀转后缀
  

package com.semanteme.demo.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class CalcDemo {



    public static void main(String[] args) {

        String mathExpression = "2+3*4-(2*3+4)+5";
//        String mathExpression = "3*4-(3+4)+5";
//        String mathExpression = "1+((2+3)*4)-5";

        int result = CalcUtil.calc(mathExpression);
        System.out.println("计算结果：" + result);

    }

}

class CalcUtil{

    public static int calc(String mathExpression) {

        String inFixExpression = toInFixExpression(mathExpression);
        System.out.println("中缀表达式：" + inFixExpression);

        List<String> suffixExpressionList = inFixToSuffixExpressionList(inFixExpression);
        System.out.println("后缀表达式：" + suffixExpressionList.toString());

        // 操作符栈
        Stack<String> operatorStack = new Stack<>();

        // 数字栈
        Stack<Integer> numbersStack = new Stack<>();
        for (String expression : suffixExpressionList) {

            if(expression.matches("\\d+")){

                numbersStack.push(Integer.parseInt(expression));
            }else {
                Integer pop1 = numbersStack.pop();
                Integer pop2 = numbersStack.pop();
                if("+".equals(expression)){
                    numbersStack.push(pop2 + pop1);
                }else if("-".equals(expression)){
                    numbersStack.push(pop2 - pop1);
                }else if("*".equals(expression)){
                    numbersStack.push(pop2 * pop1);
                }else if("/".equals(expression)){
                    numbersStack.push(pop2 / pop1);
                }
            }
        }
        return numbersStack.pop();
    }

    /**
     * 将数学表达式转成中缀表达式
     * @param mathExpression
     * @return
     */
    private static String toInFixExpression(String mathExpression){

        StringBuffer stringBuffer = new StringBuffer();

        char[] charArray = mathExpression.toCharArray();

        StringBuffer temp = new StringBuffer();
        for (char c : charArray) {

            String expression = String.valueOf(c);
            if(expression.matches("\\d+")){
                temp.append(c);
            }else {

                if(temp.length() > 0){
                    stringBuffer.append(temp.toString() + " ");
                    temp = new StringBuffer();
                }

                stringBuffer.append(expression + " ");
            }
        }

        if(temp.length() > 0){
            stringBuffer.append(temp.toString());
        }

        return stringBuffer.toString();
    }

    /**
     * 将中缀表达式转成后缀表达式
     *
     * @param inFixExpression
     * @return
     */
    private static List<String> inFixToSuffixExpressionList(String inFixExpression) {

        // 操作符栈
        Stack<String> operatorStack = new Stack<>();

        // 数字栈
        Stack<Integer> numbersStack = new Stack<>();

        List<String> suffixExpressionList = new ArrayList<>();

        String[] expressions = inFixExpression.split(" ");

        for (String expression : expressions) {

            if(expression.matches("\\d+")){

                suffixExpressionList.add(expression);
            }else if(expression.equals("(")){

                operatorStack.push(expression);
            }else if(expression.equals(")")){

                while (!operatorStack.peek().equals("(")){
                    suffixExpressionList.add(operatorStack.pop());
                }

                operatorStack.pop();
            }else {

                while (operatorStack.size() != 0 && Operation.getValue(expression) <= Operation.getValue(operatorStack.peek())){
                    suffixExpressionList.add(operatorStack.pop());
                }

                operatorStack.push(expression);
            }
        }

        while (!operatorStack.isEmpty()){
            suffixExpressionList.add(operatorStack.pop());
        }

        return suffixExpressionList;
    }

}

class Operation{

    private static int ADD = 1;

    private static int SUB = 1;

    private static int MUL = 2;

    private static int DIV = 2;

    public static int getValue(String operation){

        int result = 0;
        switch (operation){
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                result = 0;
        }

        return result;
    }
}

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

递归

• 打印阶乘
• 找出口：最优路径方法：列出所有策略的方法，找出最短路径
• 八皇后问题

排序算法

快速排序思路

树

赫夫曼树 （HuffmanTree）

• 数组构建赫夫曼树
• 赫夫曼编解码

二叉排序树（Binary sort tree）

• 构建二叉排序树
• 中序遍历
• 删除指定节点值

构建二叉树

遍历二叉树

package com.semanteme.demo.tree;

import java.util.*;

public class TreeBase {

    public static void main(String[] args) {

        Node root = new Node(7);

        Node node2 = new Node(5);
        root.setLeft(node2);
        Node node1 = new Node(11);
        root.setRight(node1);

        Node node3 = new Node(6);
        node2.setRight(node3);
        Node node4 = new Node(2);
        node2.setLeft(node4);

        Node node5 = new Node(3);
        node4.setRight(node5);
        Node node6 = new Node(1);
        node4.setLeft(node6);

        Node node7 = new Node(13);
        node1.setRight(node7);
        Node node8 = new Node(9);
        node1.setLeft(node8);

        Node node9 = new Node(14);
        node7.setRight(node9);
        Node node10 = new Node(12);
        node7.setLeft(node10);

        NodeUtil nodeUtil = new NodeUtil();

        nodeUtil.preOrder(root);
        System.out.println("====================");
        nodeUtil.inOrder(root);
        System.out.println("====================");
        nodeUtil.sufOrder(root);
        System.out.println("====================");

        List<Node> list = new ArrayList<>();
        list.add(root);
        nodeUtil.levelOrder(list);
        nodeUtil.levelOrderTraversal(root);
    }

}

class NodeUtil{

    /**
     * 前序遍历
     * @param node
     */
    public void preOrder(Node node) {

        System.out.print(node.getValue() + " ");

        if(node.getLeft() != null){
            preOrder(node.getLeft());
        }

        if(node.getRight() != null){
            preOrder(node.getRight());
        }
    }

    /**
     * 中序遍历
     * @param node
     */
    public void inOrder(Node node) {

        if(node.getLeft() != null){
            inOrder(node.getLeft());
        }

        System.out.print(node.getValue() + " ");

        if(node.getRight() != null){
            inOrder(node.getRight());
        }
    }

    /**
     * 后续遍历
     * @param node
     */
    public void sufOrder(Node node){

        if(node.getLeft() != null){
            sufOrder(node.getLeft());
        }

        if(node.getRight() != null){
            sufOrder(node.getRight());
        }

        System.out.print(node.getValue() + " ");
    }

    /**
     * 层级遍历
     *
     * @param list
     */
    public void levelOrder(List<Node> list){

        ArrayList<Node> nextList = new ArrayList<>();

        for (Node node : list) {

            System.out.print(node.getValue() + " ");

            if(node.getLeft() != null){
                nextList.add(node.getLeft());
            }

            if(node.getRight() != null){
                nextList.add(node.getRight());
            }
        }
        System.out.println("====================");

        if(!nextList.isEmpty()){
            levelOrder(nextList);
        }
    }

    public void levelOrderTraversal(Node node){

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()){

            Node poll = queue.poll();
            System.out.print(poll.getValue() + " ");

            if(poll.getLeft() != null){
                queue.add(poll.getLeft());
            }

            if(poll.getRight() != null){
                queue.add(poll.getRight());
            }

        }
    }
}

class Node{

    private int value;

    private Node root;

    private Node left;

    private Node right;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }



    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}


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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

平衡二叉树（AVL树）

• 左旋
• 右旋

多路查找树

图

• 图的表示
• 深度优先遍历（DFS）
• 广度优先遍历（BFS）

算法

二分查找算法

• 递归写法
• 非递归写法
• 汉诺塔游戏算法

package com.semanteme.demo.search;

public class BinarySearchDemo {

    public static void main(String[] args) {

        int[] searchArray = new int[]{1,4,6,7,8,10,34,45,67,89};

        int target = 2;

        int index = search(searchArray, target, 0, searchArray.length);
        System.out.println("二分法查找目标值结果：" + index);
    }

    public static int search(int[] searchArray, int target, int leftIndex, int rightIndex){

        int mid = (leftIndex + rightIndex) / 2;

        if(mid == rightIndex || mid == leftIndex){
            return -1;
        }

        if(searchArray[mid] > target){
            return search(searchArray, target, 0, mid);
        }else if(searchArray[mid] < target){
            return search(searchArray, target, mid, rightIndex);
        }else{
            return mid;
        }
    }
}

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

非递归方法

package com.semanteme.demo.search;

public class BinarySearchDemo2 {

    public static void main(String[] args) {

        int[] searchArray = new int[]{1,4,6,7,8,10,34,45,67,89};

        int target = 1;

        int index = search(searchArray, target);
        System.out.println("二分法查找目标值结果：" + index);
    }

    public static int search(int[] searchArray, int target){

        int leftIndex = 0;
        int rightIndex = searchArray.length;

        int mid = (leftIndex + rightIndex) / 2;
        while (searchArray[mid] != target){

            if(mid == leftIndex || mid == rightIndex){
                return -1;
            }

            if(searchArray[mid] > target){
                rightIndex = mid;
            }else if(searchArray[mid] < target){
                leftIndex = mid;
            }

            mid = (leftIndex + rightIndex) / 2;
        }

        return mid;
    }
}

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

动态规划

• 背包

package com.semanteme.demo.dynamicprogram;

public class BagDemo {

    public static void main(String[] args) {

        int[] W = new int[]{1, 4, 3};

        int[] V = new int[]{1500, 3000, 2000};

        Bag bag = new Bag(W, V);

        int max = bag.peek(3, 4);
        System.out.println("背包可装的最大价值为：" + max);
    }

}

class Bag{

    private int[] W = new int[]{0, 1, 4, 3};

    private int[] V = new int[]{0, 1500, 3000, 2000};

    public Bag(int[] w, int[] v) {
        W = w;
        V = v;
    }

    public int peek(int maxN, int maxW) {

        int[][] sum = new int[maxN + 1][maxW + 1];

        for (int i = 1; i < sum.length; i++) {

            for (int j = 1; j < sum[i].length; j++) {

                if(j == W[i - 1]){
                    sum[i][j] = V[i - 1];
                }else if(j < W[i - 1]){
                    sum[i][j] = sum[i - 1][j];
                }else if(j > W[i - 1]){
                    sum[i][j] = Math.max(sum[i - 1][j], V[i - 1] + sum[i - 1][j - W[i - 1]]);
                }
            }
        }


        for (int i = 0; i < sum.length; i++) {
            for (int j = 0; j < sum[i].length; j++) {

                System.out.print(sum[i][j] + " ");
            }
            System.out.println();
        }

        return sum[maxN][maxW];
    }
}


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

KMP

贪心算法

普利姆算法

• 修路最短

克鲁斯卡尔算法

迪杰斯特拉算法

弗洛伊德算法

马踏棋盘

package com.semanteme.demo.dst;


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

public class HorseChessBoard  {

    public static void main(String[] args) {
        int X = 8;
        int Y = 8;

        ChessBoard chessBoard = new ChessBoard(X, Y);
        System.out.println("周游前===========");
        chessBoard.show();

        long startTime = System.currentTimeMillis();
        chessBoard.travel(3, 2, 1);
        System.out.println("周游后===========;总共耗时：" + (System.currentTimeMillis() - startTime));
        chessBoard.show();

    }



}

class ChessBoard {

    private int X;
    private int Y;
    private int[][] chessBoard;

    private boolean[] visitChess;

    private boolean isFinished;

    public ChessBoard(int X, int Y){
        this.X = X;
        this.Y = Y;
        this.chessBoard = new int[X][Y];
        this.visitChess = new boolean[X * Y];
    }

    public void travel(int row, int col, int step){

        chessBoard[row][col] = step;
        visitChess[row * Y + col] = true;

        List<Coordinate> next = next(new Coordinate(row, col));
        sort(next);

        while (!next.isEmpty()){
            Coordinate remove = next.remove(0);

            // 未被访问过
            if(!visitChess[remove.getRow() * Y + remove.getCol()]){
                travel(remove.getRow(), remove.getCol(), step+1);
            }

        }

        if(step < X * Y && !isFinished){
            chessBoard[row][col] = 0;
            visitChess[row * Y + col] = false;
        }else {
            isFinished = true;
        }
    }

    private void sort(List<Coordinate> list){
        list.sort((o1, o2) -> {

            List<Coordinate> next1 = next(o1);
            List<Coordinate> next2 = next(o2);
            return next1.size() - next2.size();
        });
    }

    private List<Coordinate> next(Coordinate p){

        List<Coordinate> nextPoints = new ArrayList<>(8);

        // 添加0位置
        if(p.getRow() - 1 >= 0 && p.getCol() + 2 < Y){
            Coordinate point = new Coordinate(p.getRow() - 1, p.getCol() + 2);
            nextPoints.add(point);
        }

        // 添加1位置
        if(p.getRow() + 1 < X && p.getCol() + 2 < Y){
            Coordinate point = new Coordinate(p.getRow() + 1, p.getCol() + 2);
            nextPoints.add(point);
        }

        // 添加2位置
        if(p.getRow() + 2 < X && p.getCol() + 1 < Y){
            Coordinate point = new Coordinate(p.getRow() + 2, p.getCol() + 1);
            nextPoints.add(point);
        }

        // 添加3位置
        if(p.getRow() + 2 < X && p.getCol() - 1 >= 0){
            Coordinate point = new Coordinate(p.getRow() + 2, p.getCol() - 1);
            nextPoints.add(point);
        }

        // 添加4位置
        if(p.getRow() + 1 < X && p.getCol() - 2 >= 0){
            Coordinate point = new Coordinate(p.getRow() + 1, p.getCol() - 2);
            nextPoints.add(point);
        }

        // 添加5位置
        if(p.getRow() - 1 > 0 && p.getCol() - 2 >= 0){
            Coordinate point = new Coordinate(p.getRow() - 1, p.getCol() - 2);
            nextPoints.add(point);
        }

        // 添加6位置
        if(p.getRow() - 2 >= 0 && p.getCol() - 1 >= 0){
            Coordinate point = new Coordinate(p.getRow() - 2, p.getCol() - 1);
            nextPoints.add(point);
        }

        // 添加7位置
        if(p.getRow() - 2 >= 0 && p.getCol() + 1 < Y){
            Coordinate point = new Coordinate(p.getRow() - 2, p.getCol() + 1);
            nextPoints.add(point);
        }

        return nextPoints;
    }

    public void show() {
        for (int[] chess : chessBoard) {
            for (int i : chess) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

/**
 * 坐标
 */
class Coordinate{

    public int row;

    public int col;

    public Coordinate(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getCol() {
        return col;
    }

    public void setCol(int col) {
        this.col = col;
    }

    @Override
    public String toString() {
        return "Coordinate{" +
                "row=" + row +
                ", col=" + col +
                '}';
    }
}

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183