数据结构与算法

稀疏数组sparse

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

队列

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

单向链表

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

双向链表

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

单向环形列表：CircleSingleLinkedList

• 约瑟夫问题

栈

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

递归

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

排序算法

快速排序思路

树

赫夫曼树 （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;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}
}

平衡二叉树（AVL树）

• 左旋
• 右旋

多路查找树

图

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

算法

二分查找算法

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

动态规划

• 背包

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;}@Overridepublic String toString() {return "Coordinate{" +"row=" + row +", col=" + col +'}';}
}