菜鸟基础算法

一、排序

1、选择排序

package 马士兵算法;/* Created by Mayz* Date 2023/3/29 16:16* Description 选择排序：每个元素依次和后面所有元素一一比较*/
public class Class03_SelectSort {public static void main(String[] args) {int[] array = {1, 2, 10, 3, 6, 21, 9, 6, 8, 1, 3, 2, 7};selectSort(array);printArray(array);}/* 打印数组元素 @param array*/public static void printArray(int[] array) {for (int i = 0; i < array.length; i++) {int i1 = array[i];System.out.print(i1 + " ");}System.out.println();}public static void selectSort(int[] array) {if (array == null || array.length <= 1) {return;}int temp = 0;for (int i = 0; i < array.length; i++) {for (int j = i + 1; j < array.length; j++) {if (array[i] > array[j]) {temp = array[i];array[i] = array[j];array[j] = temp;}}}}
}

2、冒泡排序

package 马士兵算法;/* Created by Mayz* Date 2023/3/29 16:18* Description 冒泡排序：相邻两个元素依次比较大小*/
public class Class04_bubbleSort {public static void main(String[] args) {int[] array = {1, 2, 10, 3, 6, 21, 9, 8, 11, 13, 7};bubbleSort(array);Class03_SelectSort.printArray(array);}public static void bubbleSort(int[] array) {int temp = 0;if (array == null || array.length <= 1) return;for (int end = array.length - 1; end >= 0; end--) {for (int j = 1; j <= end; j++) {if (array[j] > array[j - 1]) {temp = array[j];array[j] = array[j - 1];array[j - 1] = temp;}}}}
}

3、插入排序

package 马士兵算法;/* Created by Mayz* Date 2023/3/29 22:11* Description 插入排序：保证范围内有序，即从下标0开始，依次对所有元素进行插入操作，直到保证所有元素顺序* 类似扑克牌*/
public class Class05_InsertSort {public static void main(String[] args) {int[] array = {1, 2, 10, 3, 6, 21, 9, 8, 11, 13, 7};
//        insertSort(array);insertSortBetter(array);Class03_SelectSort.printArray(array);}/* 插入排序 @param array*/public static void insertSort(int[] array) {int temp = 0;if (array == null || array.length < 2) return;for (int end = 1; end < array.length; end++) {int newNumIndex = end;while (newNumIndex - 1 >= 0 && array[newNumIndex - 1] > array[newNumIndex]) {temp = array[newNumIndex];array[newNumIndex] = array[newNumIndex - 1];array[newNumIndex - 1] = temp;newNumIndex--;}}}/* 插入排序优化 @param array*/public static void insertSortBetter(int[] array) {int temp = 0;if (array == null || array.length < 2) return;for (int end = 1; end < array.length; end++) {for (int pre = end - 1; pre >= 0 && array[pre] > array[pre + 1]; pre--) {temp = array[pre];array[pre] = array[pre + 1];array[pre + 1] = temp;}}}
}

二、随机数

Math.random()属于[0,1)上等概率

1、X²随机概率

		/* x的平方概率*/public static double xChengX() {return Math.max(Math.random(), Math.random());}

2、X³随机概率

    /* x的三次方概率*/public static double xChengXAndX() {return Math.max(Math.random(), Math.max(Math.random(), Math.random()));}

3、(1-X)² 随机概率

    /* 1-x的平方概率*/public static double minPercent() {return Math.min(Math.random(), Math.random());}

4、已知f()函数为随机返回1-5的函数，设法返回1-7的随机函数

    /* 题目里条件函数f()，可以返回1-5随机 @return*/public static int f() {return (int) (Math.random() * 5) + 1;}/* 改造函数随机机制，只可以使用f()函数 @return 等概率返回0或1* 1和2：返回0* 3：重新调用函数f()* 4和5：返回1*/public static int f1() {int ans = 0;do {ans = f();} while (ans == 3);return ans < 3 ? 0 : 1;}/* 构造函数：使用三个二进制位，返回000～111等概率 @return*/public static int f2() {return (f1() << 2) + (f1() << 1) + f1();}/* 构造函数：类似f1函数，如果调用结果为0，则重新调用f3() @return*/public static int f3() {int ans = 0;do {ans = f2();} while (ans == 0);return ans;}/* 目标函数g()，可以返回1-7随机 @return*/public static int g() {return f3();}

5、已知x()函数为不等概率返回0或1的函数，设法得到等概率返回0或1的函数

    /* 已知函数，非等概率返回0或者1，不清楚概率为多少(0.82为随意设置，可以设置任何[0,1)的小数)，只能看到调用函数返回为0或1 @return 0或者1*/public static int x() {return Math.random() < 0.82 ? 0 : 1;}/* 目标函数* 利用x()函数，构造为等概率返回0或1* 思路：调用两次x()函数，抛弃两次调用一样的结果（0、0和1、1），只保留0、1和1、0结果（概率相同）* @return*/public static int y() {int ans = 0;do {ans = x();} while (ans == x());return ans;}

三、对数器

对数器的概念和使用：

1. 有一个你想要测试的方法a；
2. 实现一个绝对正确但是复杂度不好的方法b；
3. 实现一个随机样本生产器；
4. 实现对比的方法；
5. 把方法a和方法b对比多次来验证方法是否正确；
6. 如果一个样本使得对比出错，打印样本分析是哪个方法除错，当样本数量很多时，对比测试依然正确，可以确定方法a正确。

package 马士兵算法;/* Created by Mayz* Date 2023/4/1 15:40* Description 对数器*/
public class Class07_Duishuqi {public static void main(String[] args) {int[] randomArray = returnRandomArray(1000, 9999);Class05_InsertSort.insertSortBetter(randomArray);int[] copyArray = copyArray(randomArray);if (!isSorted(randomArray)) {for (int i = 0; i < copyArray.length; i++) {System.out.print(copyArray[i] + " ");}System.out.println("选择排序出错了！！！");}for (int value : copyArray) {System.out.print(value + " ");}}/* 构造随机长度以及最大值随机的数组 @param maxLength* @param maxValue* @return*/public static int[] returnRandomArray(int maxLength, int maxValue) {int length = (int) (Math.random() * maxLength);int[] array = new int[length];for (int i = 0; i < array.length; i++) {array[i] = (int) (Math.random() * maxValue);}return array;}public static boolean isSorted(int[] array) {if (array.length < 2) return true;int max = array[0];for (int i = 0; i < array.length; i++) {if (max > array[i]) {return false;}max = Math.max(max, array[i]);}return true;}public static int[] copyArray(int[] array) {int[] arrayCopy = new int[array.length];for (int i = 0; i < array.length; i++) {arrayCopy[i] = array[i];}return arrayCopy;}
}

四、二分查找

1、有序数组查找num值

 /* 有序数组查找num值 @param array* @param num* @return*/public static boolean find(int[] array, int num) {if (array == null || array.length == 0) return false;int lIndex = 0;int rIndex = array.length - 1;while (lIndex <= rIndex) {int mid = (lIndex + rIndex) / 2;if (array[mid] == num) {return true;} else if (array[mid] < num) {lIndex = mid + 1;} else {rIndex = mid - 1;}}return false;}

2、有序数组查找num值最左位置

 /* 查找大于num值最左的位置，即返回最小的大于num值的Index @param array* @param num* @return*/public static int findMinIndex(int[] array, int num) {int index = -1;if (array == null || array.length == 0) return index;int lIndex = 0;int rIndex = array.length - 1;while (lIndex <= rIndex) {int mid = (lIndex + rIndex) / 2;if (array[mid] >= num) {index = mid;rIndex = mid - 1;}else if (array[mid] < num){lIndex = mid + 1;}}return index;}

作业：有序数组查找<=num最右边的位置

    /* 有序数组重找到<=num最右的位置 @return*/public static int findRightIndex(int[] array, int num) {int index = -1;if (array == null || array.length == 0) return index;int lIndex = 0;int rIndex = array.length - 1;while (lIndex <= rIndex) {int mid = (lIndex + rIndex) / 2;if (array[mid] >= num) {index = mid;rIndex = mid - 1;} else if (array[mid] < num) {lIndex = mid + 1;}}return index;}

3、局部最小值

package 马士兵算法;/* Created by Mayz* Date 2023/4/1 18:42* Description 局部最小值问题* 定义：无序数组中满足相邻的元素不相等*/
public class Class09_MinValue {public static void main(String[] args) {int maxLen = 10000;int maxValue = 999;int times = 1000;int[] generateArray = generateArray(maxLen, maxValue);int minValueIndex = returnOneMinValueIndex(generateArray);System.out.println("测试开始");for (int i = 0; i < times; i++) {if (!check(generateArray, minValueIndex)) {printArray(generateArray);}}System.out.println("测试结束");}public static void printArray(int[] array) {for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}}/* test @param array* @return*/public static boolean check(int[] array, int oneMinValue) {if (array == null || array.length == 0) return oneMinValue == -1;if (array.length < 1) return array[0] == oneMinValue;int L = oneMinValue - 1;int R = oneMinValue + 1;boolean ifLTrue = L >= 0 && array[L] > array[oneMinValue];boolean ifRTrue = R >= 0 && array[R] > array[oneMinValue];return ifLTrue && ifRTrue;}/* 构造定义数组 @param maxLen* @param maxValue* @return*/public static int[] generateArray(int maxLen, int maxValue) {int len = (int) (Math.random() * maxLen);int[] array = new int[len];if (array.length > 0) {array[0] = (int) (Math.random() * maxValue);for (int i = 1; i < len; i++) {do {array[i] = (int) (Math.random() * maxValue);} while (array[i] == array[i - 1]);}}return array;}/* 返回局部最小值，即这个元素是它相邻元素中最小的那个 @param array* @return*/public static int returnOneMinValueIndex(int[] array) {if (array == null || array.length == 0) return -1;int len = array.length;if (array[0] < array[1]) return 0;if (array[len - 1] > array[len - 2]) return len - 1;int L = 0;int R = len - 1;while (L < R) {int mid = (L + R) / 2;//情况1：mid值比相邻左右元素都小，则mid为局部最小值if (array[mid] < array[mid - 1] && array[mid] < array[mid + 1]) {return mid;} else {if (array[mid] < array[mid - 1]) {//情况2：mid小于左边相邻元素值，舍弃mid右边所有元素R = mid - 1;} else {//情况3：mid小于右边相邻元素值，舍弃mid左边元素L = mid + 1;}}}//避免出现L与mid重合的情况return array[L] < array[R] ? L : R;}
}

4、时间复杂度

• 常数时间操作（➕➖✖️➗以及数组寻址）：O(1)
• O(n!)<O(kⁿ)<O(3ⁿ)<O(2ⁿ)<O(n^k)<O(n³)<O(n²)<O(nlogn)<O(n)<O(logn)<O(1)

5、有序表：treemap

• firstkey()：返回最小的key；
• lastKey()：返回最大的key；
• floorkey(参数)：返回小于等于入参的key；
• ceilingkey(参数)：返回大于等于入参的key；

五、链表（单链表、双链表）&& 队列 && 栈

1、链表反转（或倒序）

package 马士兵算法;/* Created by Mayz* Date 2023/4/2 19:05* Description*/
public class Class10_Reverse {public static void main(String[] args) {Node n1 = new Node(1);n1.next = new Node(2);n1.next.next = new Node(3);printNode(n1);System.out.println();n1 = reverseNode(n1);printNode(n1);}public static void printNode(Node head) {while (head != null) {System.out.print(head.value+" ");head = head.next;}}/* 单链表*/public static class Node {public int value;public Node next;public Node(int value) {this.value = value;}}/* 双链表*/public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int value) {this.value = value;}}/* 单链表反转 @param node*/public static Node reverseNode(Node head) {Node next = null;Node pre = null;while (head != null) {//记next指向的位置next = head.next;//将next指向nullhead.next = pre;pre = head;//head后移head = next;}return pre;}/* 双链表反转 @param node*/public static DoubleNode reverseDoubleNode(DoubleNode head) {DoubleNode next = null;DoubleNode pre = null;while (head.next != null) {next = head.next;head.next = pre;head.last = next;pre = head;head = next;}return pre;}}

2、单链表实现栈和队列

package 马士兵算法;/* Created by Mayz* Date 2023/4/8 20:46* Description 单链表实现栈*/
public class Class11_NodeStackAndQueue {public static class Node<V> {public V value;public Node<V> next;public Node(V v) {this.value = v;next = null;}}public static class MyStack<V> {public Node<V> head;public int size;public MyStack() {head = null;size = 0;}public int size() {return size;}public boolean isEmpty() {return size == 0;}public void push(V value) {Node<V> node = new Node<>(value);if (head == null) {head = node;} else {node.next = head;head = node;}size++;}public V pop() {V v = null;if (head != null) {v = head.value;head = head.next;size--;}return v;}}public static class MyQueue<V> {public Node<V> head;public Node<V> tail;public int size;public MyQueue() {head = null;tail = null;size = 0;}public int size() {return size;}public boolean isEmpty() {return size == 0;}public void offer(V v) {Node<V> node = new Node<>(v);if (tail == null) {head = node;tail = node;} else {tail.next = node;tail = node;}size++;}}
}

3、双链表实现双端队列

package 马士兵算法;/* Created by Mayz* Date 2023/4/9 17:31* Description*/
public class Class12_DoubleQueue {public static void main(String[] args) {}public static class Node<V> {public V value;public Node<V> last;public Node<V> next;public Node(V value) {this.value = value;}}public static class DoubleQueue<V> {public Node<V> head;public Node<V> tail;public int size;public int size() {return size;}public boolean isEmpty() {return size == 0;}public DoubleQueue() {this.head = null;this.tail = null;this.size = 0;}public void pushHead(V value) {Node<V> node = new Node<>(value);if (head == null) {head = node;tail = node;} else {node.next = head;head.last = node;head = node;}size++;}public void pushTail(V value) {Node<V> node = new Node<>(value);if (tail == null) {head = node;tail = node;} else {tail.next = node;node.last = tail;tail = node;}size++;}public V pollHead(){V v = null;size--;if (head == tail){head = null;tail = null;}else {v = head.value;head = head.next;}return v;}public V pollTail(){V v = null;if (head == tail){head = null;tail = null;}else {v = tail.value;tail = tail.last;tail.next = null;}return v;}}
}

4、K个节点组内逆序调整

package 马士兵算法;/* Created by Mayz* Date 2023/4/9 18:34* Description*/
public class class13_kGroupReserve {public static void main(String[] args) {Node node = new Node(9);node.next = new Node(8);node.next.next = new Node(1);printNode(node);System.out.println();Node reverseNode = reverseInnerKGroup(node, 2);printNode(reverseNode);}public static void printNode(Node head){while (head != null) {System.out.print(head.value+" ");head = head.next;}}public static Node reverseInnerKGroup(Node head, int k) {//得到第一组的start和endNode startNode = head;Node endNode = getGroupEndNode(startNode, k);//凑不齐k个为一组的第一组情况if (endNode == null) return head;//head指向新的头部head = endNode;//实现组内反转reverse(startNode, endNode);//上一组的结尾节点Node lastEndNode = startNode;//判断只要不是最终节点，都会遍历进行下去while (lastEndNode.next != null) {//本组头节点startNode = lastEndNode.next;//尾节点endNode = getGroupEndNode(startNode, k);if (endNode == null){return head;}//组内倒序reverse(startNode, endNode);//上一组的尾节点调整指针指向下一组倒序后的头节点lastEndNode.next = endNode;lastEndNode = startNode;}return head;}/* 思路：k个为一组，组内逆序，原先start位置指向end的下一个位置 @param start* @param end* @return*/public static void reverse(Node start, Node end) {end = end.next;Node pre = null;Node next = null;Node cur = start;while (cur != end) {next = cur.next;cur.next = pre;pre = cur;cur = next;}//原先start位置指向end的下一个位置start.next = end;}/* 得到以k个为一组的尾节点 @param head* @param k* @return*/public static Node getGroupEndNode(Node head, int k) {while (--k != 0 && head != null) {head = head.next;}return head;}
}

5、两个链表相加

思路：

1. 先求两个链表的长度，得到长链表L和短链表S；
2. 先按照短链表位数，长短链表后移，直至短链表结束；
3. 长链表继续后移，直至长链表结束；
4. 进位非空则增加节点存储，结束。

public static Node addTwoNodesValue(Node longNode, Node shortNode) {Node sumNode = new Node(0);Node head = sumNode;//进位int carry = 0;while (longNode != null) {int sum = longNode.value + shortNode.value + carry;int value = sum % 10;carry = sum / 10;sumNode.value = value;if (longNode.next != null) {sumNode.next = new Node(0);sumNode = sumNode.next;if (shortNode.next == null) {shortNode.next = new Node(0);}shortNode = shortNode.next;}longNode = longNode.next;}if (carry != 0) {sumNode.next = new Node(carry);}return head;}

6、两个有序列表合并

public static Node mergeTwoLinkedNodes(Node longNode, Node shortNode) {if (longNode == null || shortNode == null) {return longNode == null ? shortNode : longNode;}Node head = longNode.value <= shortNode.value ? longNode : shortNode;Node pre = head;Node cur1 = head.next;Node cur2 = head == longNode ? shortNode : longNode;while (longNode != null && shortNode != null) {if (longNode.value <= shortNode.value) {pre.next = cur1;cur1 = cur1.next;} else {pre.next = cur2;cur2 = cur2.next;}pre = pre.next;}pre.next = cur1 != null ? cur1 : cur2;return head;}

六、位图bitmap

1、位图

package 马士兵算法;/* Created by Mayz* Date 2023/4/10 19:19* Description*/
public class BitMap {public static void main(String[] args) {int a = 8;System.out.println(a / 2);System.out.println(a >> 1);}private long[] bits;// (max + 64) >> 6 等同于 (max + 64)/64public BitMap(int max) {bits = new long[(max + 64) >> 6];}// num % 64 相当于 num & 63public void add(int num) {bits[num >> 6] |= (1L << (num & 63));}public void delete(int num) {bits[num >> 6] &= ~(1L << (num & 63));}public boolean contains(int num) {return (bits[num >> 6] & (1L << (num & 63))) != 0;}
}

2、位运算实现±*/

• 异或运算（^）：无进位相加；
• 与运算（&）：同1则1，否则为0；
• 或运算（｜）：有1则1，同0则0；
• 非运算（～）：0变1，1变0，即取反；
• 进位信息：与运算左移一位；
• 相反数：～num+1；
• 加法：无进位信息+进位信息；
• 减法：a+(-b)

package 马士兵算法;/* Created by Mayz* Date 2023/4/11 10:14* Description*/
public class Class15_BitAddMinusMultDiv {public static void main(String[] args) {}public static int add(int a, int b) {int sum = a;while (b != 0) {sum = a ^ b;b = (a & b) << 1;a = sum;}return sum;}/* 正负转换 @param num* @return*/public static int negative(int num) {return ~num + 1;}// a-b = a+(-b)public static int minus(int a, int b) {return add(a, negative(b));}/* a和b相乘，即a上的每一位和b的每一位相乘，b向右不断位移，直至为0结束* 同时为保证b右移后的乘积保持不变，a需要配合b左移 @param a* @param b* @return*/public static int multi(int a, int b) {int result = 0;while (b != 0) {if ((b & 1) != 0) {result = add(result, a);}a <<= 1;b >>>= 1;}return result;}/* 判断是否为负数 @param num* @return*/public static boolean isNegative(int num) {return num < 0;}public static int div(int a, int b) {//a和b都转为绝对值int x = isNegative(a) ? negative(a) : a;int y = isNegative(b) ? negative(b) : b;int result = 0;for (int i = 30; i >= 0; i--) {//采用x右移的方式，相当于y左移，但是y左移存在移动到符号位的风险if ((x >> i) >= y) {result |= (1 << i);x = minus(x, y << i);}}//a和b符号相等则返回result，一正一负则返回result的相反数return isNegative(a) ^ isNegative(b) ? result : negative(result);}
}

3、解决系统最小值除法

public static int divMin(int a, int b) {//除数和被除数都是系统最小值的情况if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {return 1;} else if (b == Integer.MIN_VALUE) {//除数是系统最小值return 0;} else if (a == Integer.MIN_VALUE) {//被除数是系统最小值if (b == negative(1)) {//leecode规定的return Integer.MAX_VALUE;} else {//首先需要用系统限制的最大值除以除数b，得到商c，再用余数d除以除数b，得到商e，最后c+e即为所求int c = div(add(a, 1), b);int d = minus(a, c);int e = div(d, b);return add(c, e);}} else {return div(a, b);}}

七、比较器、优先级队列、二叉树

1、比较器

2、合并k个有序链表

package 马士兵算法;import java.util.Comparator;
import java.util.PriorityQueue;/* Created by Mayz* Date 2023/4/11 11:53* Description*/
public class Class16_KTreeMerge {public static void main(String[] args) {}public class ListNode {private int val;private ListNode next;}public static class ListNodeCompator implements Comparator<ListNode> {@Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val - o2.val;}}public static ListNode merge(ListNode[] listNodes) {PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeCompator());//首先把每个Listnode链表的头节点放到小根堆，小根堆会自动排序for (ListNode listNode : listNodes) {heap.add(listNode);}//依次按照小根堆里的头节点找到nextif (heap.isEmpty()) {return null;}ListNode head = heap.poll();ListNode pre = head;if (pre.next != null) {heap.add(pre.next);}while (!heap.isEmpty()) {ListNode curNode = heap.poll();//改变前一个节点的指针指向heap的后一个节点pre.next = curNode;pre = curNode;//存储入堆节点的nextif (curNode != null) {heap.add(curNode.next);}}return head;}
}

3、判断两棵二叉树是否相同

• 先序：递归序第一次遍历时打印；
• 中序：递归序第二次遍历时打印；
• 后序：递归序第三次遍历时打印；

package 马士兵算法;/* Created by Mayz* Date 2023/4/11 12:29* Description*/
public class Class17_Tree {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}public static boolean twoTreeIsSimilar(TreeNode p, TreeNode q) {if (p == null ^ q == null) {return false;}if (p == null && q == null) {return true;}//递归return p.val == q.val && twoTreeIsSimilar(p.left, q.left) && twoTreeIsSimilar(p.right, q.right);}public static void pre(TreeNode treeNode) {System.out.print(treeNode.val+" ");pre(treeNode.left);pre(treeNode.right);}public static void mid(TreeNode treeNode) {pre(treeNode.left);System.out.print(treeNode.val+" ");pre(treeNode.right);}public static void last(TreeNode treeNode) {pre(treeNode.left);pre(treeNode.right);System.out.print(treeNode.val+" ");}}

4、判读一棵树是否是镜像树

package 马士兵算法;/* Created by Mayz* Date 2023/4/11 12:49* Description*/
public class Class18_Mirror {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}public static boolean isMirrorTree(TreeNode root) {return isMirror(root,root);}public static boolean isMirror(TreeNode p, TreeNode q) {if (p == null ^ q == null) {return false;}if (p == null && q == null) {return true;}return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left);}
}

5、求一棵树的最大深度

    public static int maxDeepth(Class18_Mirror.TreeNode root) {if (root == null) return 0;return Math.max(maxDeepth(root.left), maxDeepth(root.right)) + 1;}

6、先序数组、中序数组、后序数组重建一棵树

package 马士兵算法;import java.util.HashMap;/* Created by Mayz* Date 2023/4/11 16:58* Description*  有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]* 	请建出整棵树返回头节点*/
public class Class20_RebulidTree {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public static TreeNode buildTree(int[] pre, int[] in) {if (pre == null || in == null || pre.length != in.length) return null;HashMap<Integer, Integer> valueIndexMap = new HashMap<>();for (int i = 0; i < in.length; i++) {valueIndexMap.put(in[i], i);}return build(pre, 0, pre.length - 1, in, 0, in.length - 1, valueIndexMap);}public static TreeNode build(int[] pre, int l1, int r1, int[] in, int l2, int r2,HashMap<Integer, Integer> valueIndexMap) {if (l1 > r1) return null;TreeNode head = new TreeNode(pre[1]);if (l1 == r1) return head;int find = valueIndexMap.get(head);head.left = build(pre, l1 + 1, l1 + find - l2, in, l2, find - 1, valueIndexMap);head.right = build(pre, l1 + find - l2 + 1, r1, in, find + 1, r2, valueIndexMap);return head;}
}

7、二叉树按层遍历

package 马士兵算法;import java.util.LinkedList;
import java.util.List;
import java.util.Queue;/* Created by Mayz* Date 2023/4/11 17:45* Description*/
public class Class21_Traverse {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}/* 思路：新建一个队列，从头节点开始将元素压入队列，队列弹出元素个数与队列中元素个数相同* 弹出元素时判断元素左右孩子是否有节点，有的话压入队列中 @param root* @return*/public static List<List<Integer>> traverse(TreeNode root) {List<List<Integer>> resultList = new LinkedList<>();if (root == null) return resultList;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (queue != null) {int size = queue.size();List<Integer> innerList = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode pollNode = queue.poll();innerList.add(pollNode.val);if (pollNode.left != null) {queue.add(pollNode.left);}if (pollNode.right != null) {queue.add(pollNode.right);}}resultList.add(0, innerList);}return resultList;}
}

8、判断是否是二叉树

package 马士兵算法;/* Created by Mayz* Date 2023/4/11 18:31* Description*/
public class Class22_BalanceTree {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public static class Info {//是否平衡private boolean isBalanced;//高private int height;public Info(boolean isBalanced, int height) {this.isBalanced = isBalanced;this.height = height;}}/* 思路： @param treeNode* @return*/public static boolean isBalanced(TreeNode treeNode) {return process(treeNode).isBalanced;}public static Info process(TreeNode root) {if (root == null) return new Info(true, 0);Info leftInfo = process(root.left);Info rightInfo = process(root.right);int height = Math.max(leftInfo.height, rightInfo.height) + 1;boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced && Math.abs(leftInfo.height - rightInfo.height) < 2;return new Info(isBalanced, height);}
}

9、判断是否是平衡搜索二叉树

搜索二叉树：左孩子<根节点<右孩子

package 马士兵算法;/* Created by Mayz* Date 2023/4/11 19:01* Description*/
public class Class23_BinarySearchTree {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public static class Info {private boolean isBST;private int max;private int min;public Info(boolean isBST, int max, int min) {this.isBST = isBST;this.max = max;this.min = min;}}public static boolean isBST(TreeNode treeNode) {return process(treeNode).isBST;}public static Info process(TreeNode root) {if (root == null) return null;Info leftInfo = process(root.left);Info rightInfo = process(root.right);int max = root.val;int min = root.val;if (leftInfo != null) {max = Math.max(max, leftInfo.max);min = Math.min(min, leftInfo.min);}if (rightInfo != null) {max = Math.max(max, rightInfo.max);min = Math.min(min, rightInfo.min);}boolean leftBST = leftInfo == null ? true : leftInfo.isBST;boolean rightBST = rightInfo == null ? true : rightInfo.isBST;boolean leftMaxLessRoot = leftInfo == null ? true : leftInfo.max < root.val;boolean rightMinMoreRoot = rightInfo == null ? true : rightInfo.min > root.val;boolean isBst = leftBST && rightBST && leftMaxLessRoot && rightMinMoreRoot;return new Info(isBst, max, min);}
}

10、能否组成路径和

package 马士兵算法;/* Created by Mayz* Date 2023/4/11 18:32* Description*/
public class Class24_PathSum {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public static boolean isSum = false;public static boolean hasPathSum(TreeNode root, int sum) {if (root == null) return false;process(root, 0, sum);return isSum;}public static void process(TreeNode root, int preSum, int sum) {//叶子结点if (root.left == null && root.right == null) {if (preSum + root.val == sum) {isSum = true;}return;}//非叶子节点preSum += root.val;if (root.left != null) {process(root.left, preSum, sum);}if (root.right != null) {process(root.right, preSum, sum);}}
}

11、收集达标路径和

package 马士兵算法;import java.util.ArrayList;
import java.util.List;/* Created by Mayz* Date 2023/4/11 18:33* Description*/
public class Class25_SearchPath {public static void main(String[] args) {}public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public static List<List<Integer>> searchPath(TreeNode root, int sum) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;List<Integer> path = new ArrayList<>();process(root, sum, 0, path, result);return result;}public static void process(TreeNode root,int sum,int preSum,List<Integer> path,List<List<Integer>> result) {//叶子结点if (root.left == null && root.right == null) {if (preSum + root.val == sum) {path.add(root.val);result.add(path);path.remove(path.size() - 1);}}path.add(root.val);preSum += root.val;//非叶子节点if (root.left != null) {process(root.left, sum, preSum, path, result);}if (root.right != null) {process(root.right, sum, preSum, path, result);}path.remove(path.size() - 1);}
}

八、归并排序和快速排序

1、归并排序

// 递归方法实现public static void mergeSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}// arr[L...R]范围上，请让这个范围上的数，有序！public static void process(int[] arr, int L, int R) {if (L == R) {return;}// int mid = (L + R) / 2int mid = L + ((R - L) >> 1);process(arr, L, mid);process(arr, mid + 1, R);merge(arr, L, mid, R);}public static void merge(int[] arr, int L, int M, int R) {int[] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}// 要么p1越界，要么p2越界// 不可能出现：共同越界while (p1 <= M) {help[i++] = arr[p1++];}while (p2 <= R) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}}

2、非递归排序（步长一定是2ⁿ，并且小于数组的总长度）

public static void mergeSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}int step = 1;int N = arr.length;while (step < N) {int L = 0;while (L < N) {int M = 0;if (N - L >= step) {M = L + step - 1;} else {M = N - 1;}if (M == N - 1) {break;}int R = 0;if (N - 1 - M >= step) {R = M + step;} else {R = N - 1;}merge(arr, L, M, R);if (R == N - 1) {break;} else {L = R + 1;}}if (step > N / 2) {break;}step *= 2;}}

3、快排

import java.util.Stack;public class Code26_PartitionAndQuickSort {public static void splitNum1(int[] arr) {int lessEqualR = -1;int index = 0;int N = arr.length;while (index < N) {if (arr[index] <= arr[N - 1]) {swap(arr, ++lessEqualR, index++);} else {index++;}}}public static void splitNum2(int[] arr) {int N = arr.length;int lessR = -1;int moreL = N - 1;int index = 0;// arr[N-1]while (index < moreL) {if (arr[index] < arr[N - 1]) {swap(arr, ++lessR, index++);} else if (arr[index] > arr[N - 1]) {swap(arr, --moreL, index);} else {index++;}}swap(arr, moreL, N - 1);}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// arr[L...R]范围上，拿arr[R]做划分值，// L....R < = >public static int[] partition(int[] arr, int L, int R) {int lessR = L - 1;int moreL = R;int index = L;while (index < moreL) {if (arr[index] < arr[R]) {swap(arr, ++lessR, index++);} else if (arr[index] > arr[R]) {swap(arr, --moreL, index);} else {index++;}}swap(arr, moreL, R);return new int[] { lessR + 1, moreL };}public static void quickSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {if (L >= R) {return;}int[] equalE = partition(arr, L, R);process(arr, L, equalE[0] - 1);process(arr, equalE[1] + 1, R);}public static class Job {public int L;public int R;public Job(int left, int right) {L = left;R = right;}}public static void quickSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}Stack<Job> stack = new Stack<>();stack.push(new Job(0, arr.length - 1));while (!stack.isEmpty()) {Job cur = stack.pop();int[] equals = partition(arr, cur.L, cur.R);if (equals[0] > cur.L) { // 有< 区域stack.push(new Job(cur.L, equals[0] - 1));}if (equals[1] < cur.R) { // 有 > 区域stack.push(new Job(equals[1] + 1, cur.R));}}}public static int[] netherlandsFlag(int[] arr, int L, int R) {if (L > R) {return new int[] { -1, -1 };}if (L == R) {return new int[] { L, R };}int less = L - 1;int more = R;int index = L;while (index < more) {if (arr[index] == arr[R]) {index++;} else if (arr[index] < arr[R]) {swap(arr, index++, ++less);} else {swap(arr, index, --more);}}swap(arr, more, R); // <[R] =[R] >[R]return new int[] { less + 1, more };}public static void quickSort3(int[] arr) {if (arr == null || arr.length < 2) {return;}process3(arr, 0, arr.length - 1);}public static void process3(int[] arr, int L, int R) {if (L >= R) {return;}swap(arr, L + (int) (Math.random() * (R - L + 1)), R);int[] equalArea = netherlandsFlag(arr, L, R);process3(arr, L, equalArea[0] - 1);process3(arr, equalArea[1] + 1, R);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {
//		int[] arr = { 7, 1, 3, 5, 4, 5, 1, 4, 2, 4, 2, 4 };
//
//		splitNum2(arr);
//		for (int i = 0; i < arr.length; i++) {
//			System.out.print(arr[i] + " ");
//		}int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;System.out.println("test begin");for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);int[] arr3 = copyArray(arr1);quickSort1(arr1);quickSort2(arr2);quickSort3(arr3);if (!isEqual(arr1, arr2) || !isEqual(arr1, arr3)) {System.out.println("Oops!");succeed = false;break;}}System.out.println("test end");System.out.println(succeed ? "Nice!" : "Oops!");}
}