常数时间的操作：一个操作跟数据量没有关系，每次都是固定的时间内完成，叫做常数操作，一般表示O(1)。
指标常用O来表示，读作big O，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要系数，那么剩下的部分就是时间复杂度O(f(N)).
额外空间复杂度：除了原需要的数据以外，是否还需要额外开辟的空间。
对数器是用来验证写出的方法的准确性，在多次重复的情况下，让写出的方法接近完全正确。
1.自己写完了一个想测的方法a
2.实现一个绝对正确，复杂度无所谓的方法b
3.实现对比方法
4.把a和b对比很多次，如果出错，把出错的结果打印出来
5.当样本数量很多，对比测试依然正确，那么可以基本上确定，方法a已经正确。
实现代码如下，计算时间的也顺便帖了上去，方便对比哪个方法更快。
public static long concurrentTime1, concurrentTime2, concurrentMemory1, concurrentMemory2; // 生成随机数组，参数是传一个数组的最大长度和最大值 public static int[] generateRandomArray(int size, int value) { // 利用传过来的size来随机生成一个在size内大小的数组 int[] arr = new int[(int)((size + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { // 数组内的每个值都是在value正负范围内的值 arr[i] = (int)((value + 1) * Math.random()) - (int)((value + 1) * Math.random()); } return arr; } // 绝对正确的方法 public static void absoluteRightMethod(int[] arr) { // 这时候不用管时间复杂度，只要保证结果是绝对正确就可以 Arrays.sort(arr); } // 复制一模一样的数组 public static int[] copyArray(int[] arr) { int[] arrCopy = new int[arr.length]; for (int i = 0; i < arrCopy.length; i++) { arrCopy[i] = arr[i]; } return arrCopy; } // 验证两个数组是否一样 public 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; } // 打印数组 public static void printArray(int[] arr) { for (int i : arr) { System.out.print(i + " "); } } //计算系统开始时间 public static void start() { //得到程序开始时的系统时间（纳秒级，最终转化毫秒，保留小数点后两位） concurrentTime1 = System.nanoTime(); //得到虚拟机运行、程序开始执行时jvm所占用的内存。 Runtime runtime = Runtime.getRuntime(); concurrentMemory1 = runtime.totalMemory()-runtime.freeMemory(); } //计算系统结束时间 public static void end() { //得到程序执行完毕时的系统时间（毫秒级） concurrentTime2 = System.nanoTime(); //得到虚拟机运行、所要测试的执行代码执行完毕时jvm所占用的内存（byte）。 Runtime runtime = Runtime.getRuntime(); concurrentMemory2 = runtime.totalMemory()-runtime.freeMemory(); //计算start和end之间的代码执行期间所耗时间(ms)与内存(M)。 // 1毫秒(ms) = 1000微秒(us) = 1000 000纳秒(ns) // 1M = 1*2^20 byte = 1024 * 1024 byte; String time = String.valueOf((double)(concurrentTime2 - concurrentTime1)/1000000); String memory = String.valueOf((double)(concurrentMemory2-concurrentMemory1)/1024/1024) ; System.out.println("---------------您的代码执行时间为：" + time.substring(0,time.equals("0.0") ? 1 : (time.indexOf(".")+3)) + " ms, 消耗内存：" + memory.substring(0,memory.equals("0.0") ? 1 : (memory.indexOf(".")+3)) + " M + !---------------"); } // for test public static void main(String[] args) { // 测试次数 int testTime = 500000; // 数组的大小 int size = 10; // 值的大小范围 int value = 100; boolean succeed = true; start(); for (int i = 0; i < testTime; i++) { // 创建一个随机数组和两个一模一样的数组 int[] arr1 = generateRandomArray(size, value); int[] arr2 = copyArray(arr1); // 输出错误时的数组 int[] arr3 = copyArray(arr1); // 调用自己的方法，比如冒泡排序方法 Sort.bubbleSort(arr1); // 调用绝对正确的方法 absoluteRightMethod(arr2); // 比较是否完全相同 if (!isEqual(arr1,arr2)) { succeed = false; // 打印出不相同时，生成出的数组 printArray(arr3); break; } } end(); System.out.println(succeed ? "正确" : "错误"); }冒泡排序就是每次两个两个比较，大的数字到后面，以下标表示的话就是，0和1比较，比较完1和2比较，以此类推，一轮下来之后，最大的就到了最后，那么这时候就再排倒数第二个位置，最后整个下来排完。
总结：两两比较，取最大，每次确定最大值到后面。
// 冒泡排序 public static void bubbleSort() { int[] arr = {2, 4, 0, 9, 7, 6}; // 这里外层循环的是最终确认的位置，也就是最大值的位置，第一次最后一个，之后最大的确定了，再排倒数第二个，以此类推 for (int i = arr.length - 1; i > 0; i--) { // 这里是从头开始，一直排到外层的位置 for (int j = 0; j < i; j++) { // 如果前面的大于后面的，那就交换位置 if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } // 打印输出 for (int i : arr) { System.out.print(i + " "); } }时间复杂度O(N²)，空间复杂度O(1)
与冒泡排序类似相反的排序，选择排序是循环一整个数组之后，选择最小的值，放在第一个位置，然后再从第二个位置开始，再循环下标1到最后一个位置，以此类推。
总结：每次循环找到最小的位置，与最前面的位置交换。
// 选择排序 public static void selectionSort() { int[] arr = {2, 4, 0, 9, 7, 6}; // 这里外层循环的是确定最小的位置，从第一个开始，再确定第二个，依此类推 for (int i = 0; i < arr.length - 1; i++) { // 每次设置一个最小值的变量，先以第i个值开始 int minNum = i; // 从第i个位置开始往后循环，找最小的值 for (int j = i + 1; j < arr.length; j++) { // 每次和最小值判断，只要比这个小，就把最小值给到minNum minNum = arr[j] < arr[minNum] ? j : minNum; } if (minNum != i) { int temp = arr[i]; arr[i] = arr[minNum]; arr[minNum] = temp; } } for (int i : arr) { System.out.print(i + " "); } }时间复杂度O(N²)，空间复杂度O(1)
插入排序就是每次定义一个区间，然后后面加入的值与这个区间开始排序，以下标举例，1是新加入的值，与00区间比较，也就是和0比较，然后排序，然后新加入的2与01区间排序，先与1比较，如果比1大，就直接跳过，如果1，2交换，那么就比较交换过的0，1，最后排好序的0~2与新加入的3比较，以此类推。
总结：每次把区间排好序，将后来新加入的值与这个区间比较排序。
// 插入排序 public static void insertSort() { int[] arr = {2, 4, 0, 9, 7, 6}; // 从第二个位置开始，因为0~0本身就一个数，不用排，所以从第二个位置开始 for (int i = 1; i < arr.length; i++) { // 从i的前一个位置开始，和i进行比较，如果前面的要大于i，就把i和前一个位置互换，再往前两两比较，这里就有点类似冒泡的比较方式 // 如果后面的的值直接比前面已经排好序的值大，那么就不用直接跳过 for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } for (int i : arr) { System.out.print(i + " "); } }时间复杂度和数据状况相关，如果本身就是有序的，每次判断都不需要排序，那么循环一遍就完事了，时间复杂度为O(N)，相反，最坏情况，是倒叙的，那么每次都要在区间里全都重排，那么时间复杂度为O(N²)，空间复杂度O(1)，如果数据状况未知，那么一律按最坏情况估计。
时间复杂度O(N²)，空间复杂度O(1)
就是在运行的过程中调用自己，把大问题分解成若干个小问题，最终要有一个结束条件，在实现上，每次调用时，压入栈中，然后调用自己，再次调用时，还是压入栈中，依此类推，最后返回结束条件，就会出栈一个，然后继续往下走，结束后再次出栈，依此类推，递归的时间复杂度可以用master公式来推导：
T(N) = aT(n/b) + O(n^d)
N是指样本数据量，a是递归的行为发生的次数，b是分成了多少个n，例如把数组分成两个n/2，分别调用自己的方法，那么a就是2，b也是2，O(n^d)就是除了调用自己的方法外的时间复杂度。
1.log(b,a)>d->复杂度为O(N^log(b,a))
2.log(b,a)=d->复杂度为O(N^d*logN)
3.log(b,a)=d->复杂度为O(N^d)
可以用上述判断，来算出递归的时间复杂度
利用递归的特性，将数组分成若干个部分，每个部分排好序之后，两个排好序的数组再合并成一个有序的数组。
假如分成两个数组，每个数组执行原来的一半那么根据master公式：T(N) = 2T(n/2) + O(N)，a=2,b=2,d=1，log(b,a)=d，那么时间复杂度为：O(N * logN)，额外空间复杂度为O(N)，理论上可以优化成空间复杂度O(1)，但是非常难，论文级。
代码执行如下：
// 归并排序 public static void mergeSort(int[] arr) { // 判断长度是否大于1 if (arr == null || arr.length < 2) { return; } // 调用mergeSort mergeSort(arr, 0, arr.length - 1); } // 将数组分割 public static void mergeSort(int[] arr, int left, int right) { // 当左右相等，也就是只剩一个数字时，作为终止条件 if (left == right) { return; } int mid = (left + right) / 2; // 分割成两部分，调用自己，直到足够小为止 mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // 将两个数组合并，这里才是真正执行排序的方法 merge(arr, mid, left, right); } // 对分好的两个数组进行排序合并 public static void merge(int[] arr, int mid, int left, int right) { // 创建新的分割后的数组 int[] help = new int[right - left + 1]; // 从下标0开始给这个数组赋值 int i = 0; // 左侧数组的指针 int pl = left; // 右侧数组的指针 int pr = mid + 1; // 两侧数组从头开始遍历比较，按照由小到大把值给新的数组 while (pl <= mid && pr <= right) { help[i++] = arr[pl] > arr[pr] ? arr[pr++] : arr[pl++]; } // 这两个是哪个没执行完，就把剩下的值赋给新数组 while (pl <= mid) { help[i++] = arr[pl++]; } while (pr <= right) { help[i++] = arr[pr++]; } // 将新数组的值依次给到对应的原数组相应的位置，那么原数组对应的元素就是这些元素已经排好序的结果 for (int j= 0; j < help.length; j++) { arr[left + j] = help[j]; } }算出数组中，每个元素左边小于自己的总和。
例如：[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16
这里的解题思路为：这题的本质等同于左边这个数，有多少个右边的数比它大，那么就会乘多少次这个数加上去，例如上面这个例子，和为：1 * 4 + 2 * 1 + 3 * 2 + 4 * 1 = 16
代码的实现与归并一样，只不过每次排序前，算出右边的数量乘上这个数。
// 归并排序 public int mergeSort(int[] arr) { // 判断长度是否大于1 if (arr == null || arr.length < 2) { return 0; } // 调用mergeSort return mergeSort(arr, 0, arr.length - 1); } // 将数组分割 public int mergeSort(int[] arr, int left, int right) { // 当左右相等，也就是只剩一个数字时，作为终止条件 if (left == right) { return 0; } int mid = (left + right) / 2; // 将两个数组合并，这里才是真正执行排序的方法 // 分割成两部分，调用自己，直到足够小为止 // 将每个数组得出来得最小值结果相加返回 return mergeSort(arr, left, mid) + mergeSort(arr, mid + 1, right) + merge(arr, mid, left, right); } // 对分好的两个数组进行排序合并 public static int merge(int[] arr, int mid, int left, int right) { int result = 0; // 创建新的分割后的数组 int[] help = new int[right - left + 1]; // 从下标0开始给这个数组赋值 int i = 0; // 左侧数组的指针 int pl = left; // 右侧数组的指针 int pr = mid + 1; // 两侧数组从头开始遍历比较，按照由小到大把值给新的数组 while (pl <= mid && pr <= right) { // 如果右边大于左边，那么就把左边这个数乘右边数量，就代表右边数组都会加一次左边的这个值。 result += arr[pl] < arr[pr] ? (right - pr + 1) * arr[pl] : 0; help[i++] = arr[pl] < arr[pr] ? arr[pl++] : arr[pr++]; } // 这两个是哪个没执行完，就把剩下的值赋给新数组 while (pl <= mid) { help[i++] = arr[pl++]; } while (pr <= right) { help[i++] = arr[pr++]; } // 将新数组的值依次给到对应的原数组相应的位置，那么原数组对应的元素就是这些元素已经排好序的结果 for (int j= 0; j < help.length; j++) { arr[left + j] = help[j]; } return result; }在说明快速排序前引入一个题，来更好的说明快速排序。
指定一个数，定义数组的左右判断界限，如果比这个数大，则放右边，如果比这个数小，放左边，与这个数相等，放中间。
解题思路：首先将左右边界-1作为比这个数小和大的区域，如果有数字比这个数小或者大，就把这个区域向里扩大，并与现在所在下标的交换位置。
代码实现为：
// 数组中的交换位置 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 荷兰国旗问题 // 参数left和right分别是要判断的数组的左右边界，num则是用来判断的数 public static int[] partition(int[] arr, int left, int right, int num) { // 一开始比num小的数在边界左尽头 int less = left - 1; // 一开始比num大的数在边界右尽头 int more = right; // 这里用left来表示现在走到的数 while (left < more) { // 如果比num小，那么将左边的数扩大一区域，并把现在的数向前移 if (arr[left] < num) { swap(arr, ++less, left++); // 如果比num大，那么将右边的数向右扩大一区域，与现在的数进行交换 } else if (arr[left] > num) { swap(arr, --more, left); } else { // 相等的情况就推进一个 left++; } } // 最后输出与num相等的界限 return new int[] {less + 1, more - 1}; }通过荷兰国旗问题，就可以发现，我们可以把数组也按照这个方式分割，然后每个区域进行再分割，经典的快速排序是分为小于等于x和大于x的区域，通过优化可以分成和荷兰国旗那样的三个区域，那么等于x的就可以不用进行排了。最后就可以得到有序的数组。
代码实现如下：
// 快速排序 public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int left, int right) { if (left < right) { // 这里的优化是随机选取范围内的一个值，与左右边的值交换，当作判断基准数 swap(arr, left + (int)(Math.random() * (right - left + 1)), right); // 得到相同字段的左右边界 int[] p = partition(arr, left, right); // 再次分割左边，进行排序 quickSort(arr, left, p[0] - 1); // 再次分割右边，进行排序 quickSort(arr, p[1] + 1, right); } } private static int[] partition(int[] arr, int left, int right) { int less = left - 1; int more = right; while (left < more) { if (arr[left] < arr[right]) { swap(arr, ++less, left++); // 如果比num大，那么将右边的数向右扩大一区域，与现在的数进行交换 } else if (arr[left] > arr[right]) { swap(arr, --more, left); } else { // 相等的情况就推进一个 left++; } } // 因为最右边的数字没参与排序，因为以这个数来判断，所以他与more的最右边交换 swap(arr, more, right); return new int[] { less + 1, more }; }时间复杂度是O(NlogN)到O(N²)，但是根据随机快排时，普遍期望为O(NlogN)，所以时间复杂度可以当作为O(NlogN)，额外空间复杂度O(logN)，因为每次都需要空间去记录分割的点，之后左边再次进行分割，还需要分割的点的记录，依此类推，所以是logN。
理论上堆可以看作是一个完全二叉树，每个节点的左子节点就是2*i + 1，右子节点就是2 *i + 2，反推就可以得到父节点，那么根据这个性质，我们可以先得出整个数组的大根堆，大根堆就是父节点大于两个子节点的堆结构，那么堆顶必然是最大的，然后把堆顶与最后一个数进行交换，那么最大的数字就到了最后，然后把剩下的N-1的堆再进行大根堆排序，反复会得到最大的堆顶，依次放到后面就会得到有序的数组。
代码实现为：
// 堆排序 public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 从0~0，0~1，0~2等等依次取得这个区域的大根堆，也就是建立大根堆的过程，这里的时间复杂度为O(N) for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int size = arr.length; // 将堆顶与最后一个数进行交换 swap(arr, 0, --size); while (size > 0) { // 剩下的数进行大根堆调整 heapify(arr, 0, size); // 得到堆顶后，再次与最后一位数交换，区间减少一位 swap(arr, 0, --size); } } // 依次按顺序插入形成大根堆的方法 public static void heapInsert(int[] arr, int index) { // 判断新加入的数与前面的大根堆进行大小的判断，是否大于它的父节点 while (arr[index] > arr[(index - 1) / 2]) { // 大于，则交换 swap(arr, index, (index - 1) / 2); // 将下标变为新的父节点，再循环到前面与这个节点的父节点进行比较 index = (index - 1) / 2; } } // 当前下标的值是否符合大根堆，不符合则重新调整 public static void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; // 判断左子节点是否越界 while (left < heapSize) { // 右子节点不越界而且大于左节点，那么最大值就是右节点，否则就是左节点 int larger = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; // 判断左右节点最大值后与父节点进行比较 larger = arr[larger] > arr[index] ? larger : index; // 如果最大值还是父节点，那么就不需要调整，直接跳出循环 if (larger == index) { break; } // 交换节点，并且继续向下判断 swap(arr, larger, index); index = larger; left = index * 2 + 1; } }时间复杂度为O(N*logN)，额外空间复杂度O(1)，建立堆的过程O(N)
稳定性就是相同的元素排序之后的位置与原位置的顺序是相同的。以上排序中能达到稳定性的有：冒泡(相同时不交换)，插入(相同时，插入到后面)，归并(左右数组合并时，先合并左边)
不满足的：选择排序，快速排序，堆排序
选择排序：找到最小的值与前面的值交换，如果中间有相同的，那么就会破坏稳定性。
快速排序：因为基准数与右边界交换，排好之后再换回来，所以会破坏稳定性，但是理论上可以实现，很难，论文级，暂时不要求掌握
堆排序：因为每次交换是与自己的左右节点交换，如果子节点与自己的中间有相同的值，那么就会破坏稳定性。
在工程使用中是综合许多排序在不同情况下综合使用，如果元素量小于60的情况，就会使用插入排序，第一，不会破坏稳定性，第二，虽然时间复杂度为O(N²)，但是数据量小的时候，并没有什么差距，而且常数项低，额外空间复杂度为O(1)，如果排序里的元素是基础数据类型，那么就会用快排，因为不需要考虑稳定性，所以选择时间复杂度低的，但是如果里面是类，那么就有可能会要求有稳定性的排序，所以会用到归并排序，保证数据的稳定性。
比较器是给类进行排序的时候，以里面的某一元素进行排序时使用，实现Comparator里的compare方法，如果返回的是负数，代表前面的数更小，返回正数就是前面的更大，相等就是两元素相等。例如以Student为例子，代码实现为：
public class Student{ public String name; public int age; public int id; public Student(String name, int id, int age) { this.name = name; this.id = id; this.age = age; } } // 按照id进行排序 public static class IdAscendingComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.id - o2.id; } } // 按照name进行排序 public static class NameAscendingComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.name.compareTo(o2.name); } } // 按照age进行排序 public static class AgeAscendingComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.age - o2.age; } }利用比较器，就可以实现比较，比如Arrays.sort(集合，比较器)，创建优先队列(原理就是堆)PriorityQueue students = new PriorityQueue<>(new IdAscendingComparator());
桶排序不基于比较进行排序，而是把对应的元素放到已经有序的位置，然后根据元素出现的频率等直接进行还原(计数排序)，例如数组里的范围只有0~60，那么我们可以创建一个新的数组，把下标当作元素创建大小为61的数组，然后数字出现时，将对应下标的位置的值进行累加，最后把0出现几次直接写到另一个数组上，1出现几次也在后面继续写入等等，时间复杂度也是O(N)，空间复杂度也是O(N)，但是这种情况是有局限性的，范围过大就不适合使用，就算是基数排序，按照个位数百位数的顺序进行计数，桶数比较少，但还是根据数据状况有关。
给定一组数组，要求算出这个数组排序后的最大间隙，不能使用排序算法。因为不能使用排序算法，这时候就可以用到桶排序，先可以利用这个数组最大值和最小值分成N+1大小的桶，然后桶里有boolean，判断是否空，max这个桶的最大值，min这个桶的最小值，最后得到每个非空桶最小值与前一个桶的最大值的大小，再比较所有的这个差值，就可以得到最大间隙。
代码实现为：
// 返回最大间隙值 public static int getMaxGap(int[] arr) { // 如果只有数组内小于2，那么间隙就是0 if (arr == null || arr.length < 2) { return 0; } int len = arr.length; int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; // 取得数组内的最大值与最小值 for (int i = 0; i < len; i++) { min = Math.min(min, arr[i]); max = Math.max(max, arr[i]); } // 最大值与最小值相等，说明都是一样的数 if (min == max) { return 0; } // 创建0 ~ len的桶，每个桶有一个判断是否空桶的boolean，最大值，最小值 boolean[] hasNum = new boolean[len + 1]; int[] maxs = new int[len + 1]; int[] mins = new int[len + 1]; for (int i = 0; i < len; i++) { // 通过计算当前值所在的桶的位置 int bucket = getBucket(arr[i], len, max, min); // 得到这个桶内的最大值与最小值，如果是空桶，那么都是它本身 mins[bucket] = hasNum[bucket] ? Math.min(arr[i], mins[bucket]) : arr[i]; maxs[bucket] = hasNum[bucket] ? Math.max(arr[i], maxs[bucket]) : arr[i]; // 状态改为不是空桶 hasNum[bucket] = true; } // 最大间隙值 int result = 0; // 上一个桶的最大值 int lastMax= maxs[0]; for (int i = 1; i <= len; i++) { // 从下标为1开始，判断当前桶是否为空 if (hasNum[i]) { // 这个桶的最小值 - 上个桶的最大值与现在的最大间隙值做比较，取最大 result = Math.max(mins[i] - lastMax, result); // 将这个桶的最大值当作下个桶的前一个桶的最大值 lastMax = maxs[i]; } } // 得到最大间隙值 return result; } public static int getBucket(long num, long len, long max, long min) { // 通过最大值与最小值之差得到这个值所在的桶的位置 return (int) ((num - min) * len / (max - min)); } // for test public static int comparator(int[] nums) { if (nums == null || nums.length < 2) { return 0; } Arrays.sort(nums); int gap = Integer.MIN_VALUE; for (int i = 1; i < nums.length; i++) { gap = Math.max(nums[i] - nums[i - 1], gap); } return gap; }就是用bit的方式来存储结果，适用于0，1返回要求的情况，但是由于通过hash算法得到的结果可能是相同的，那么就会存在失误率，所以布隆过滤器如果查询到结果不存在，那么就一定不存在，如果存在，则可能是存在的结果。
公式：1）m = - (n * lnP / (ln2)²)，n是样本量，P是允许的失误率，就可以得到需要开辟的bit量。
2）确定hash函数的个数：K = ln2 * (m / n) ；
3）真实失误率：P = (1 - e的-(n*k/m))k次方；
一致性哈希可以比作一个环结构，然后将特有的属性通过hash值计算，得到的位置对应到环结构中，比如机器的ip地址，假如将某个值记录到机器中，这时候有三个机器，那么这个记录可以通过hash计算后得到的位置，顺时针找到最近的机器中，就可以把这个值通过这个机器去存，也就是两台机器之间的所有hash得到的值，都可以通过顺时针找到的那台机器去存储，在进行增减机器的时候，就可以只把部分数据进行修改到新机器或分摊到下一个机器中就可以，比原来所有的hash都要变化的代价小得多。
因为机器也是通过hash得到的位置，所以很有可能出现的位置不负载均衡，或者本身负载均衡，但是由于加减机器，变得不负载均衡，这时候可以利用虚拟节点，比如每个机器设置1000个虚拟节点，然后通过虚拟节点来到哈希环中找到自己的位置，负责自己的区域，然后再通过虚拟节点，找到自己对应的物理节点机器来实现，那么不管是增减机器，都只要增加虚拟节点或删除虚拟节点的方式就可以实现负载均衡。
并查集结构可以查看两个对象，是不是属于并集，然后可以将两个集合进行连接。具体代码实现如下：
public static class Node { // whatever you like } public static class UnionFindSet { // 两个成员变量，一个是存储node和它的父node public HashMap<Node, Node> fatherMap; // 一个是存储node的大小 public HashMap<Node, Integer> sizeMap; // 初始化 public UnionFindSet(List<Node> nodes) { fatherMap = new HashMap<>(); sizeMap = new HashMap<>(); // 将所有的node存到成员变量中，且size为1 for (Node node : nodes) { fatherMap.put(node, node); sizeMap.put(node, 1); } } // 查找链头 public Node findHead(Node node) { // 得到父节点 Node father = fatherMap.get(node); // 如果父节点不等于自己，那么说明上面还有父节点 if (father != node) { // 循环调用，直到找到最后一个父节点 father = findHead(father); } // 将查询过程中的所查询节点上面的所有节点的父节点改成头节点 fatherMap.put(node, father); // 返回头节点 return father; } // 查看是否为同一集合，如果在同一集合，那么头节点一定是相同的 public boolean isSameSet(Node node1, Node node2) { return findHead(node1) == findHead(node2); } // 合并两个节点 public void union(Node node1, Node node2) { if (node1 == null || node2 == null) { return; } // 找两个的头节点 Node head1 = findHead(node1); Node head2 = findHead(node2); // 小的链连在大的链后面，然后size等于两个链相加 if (sizeMap.get(head1) <= sizeMap.get(head2)) { fatherMap.put(head1, head2); sizeMap.put(head2, sizeMap.get(head1) + sizeMap.get(head2)); } else { fatherMap.put(head2, head1); sizeMap.put(head1, sizeMap.get(head1) + sizeMap.get(head2)); } } }有一个矩阵，用0和1表示，如果有1相连则构成一个岛，问这个矩阵有多少个岛。
思路：先遍历矩阵，然后找到第一个1的时候通过递归来找到它的上下左右是不是1，然后将这些1改成2的值，直到连着的1都变为2，然后岛的数量加一，代码实现如下：
// 遍历二维数组 public static int countIslands(int[][] nums) { if (nums == null || nums[0] == null) { return 0; } int length = nums.length; int high = nums[0].length; int size = 0; for (int i = 0; i < length; i++) { for (int j = 0; j < high; j++) { // 如果第一次找到1的时候，岛的数量加一，并且进入infect方法 if (nums[i][j] == 1) { size++; infect(nums, i, j, length, high); } } } return size; } // 递归的判断这个位置的上下左右，一直走到不是1为止，并把所有经过的值改为2 public static void infect(int[][] nums, int i, int j, int length, int high) { if (i < 0 || i > length - 1 || j < 0 || j > high - 1 || nums[i][j] != 1) { return; } nums[i][j] = 2; infect(nums, i - 1, j, length, high); infect(nums, i, j - 1, length, high); infect(nums, i + 1, j, length, high); infect(nums, i, j + 1, length, high); } public static void main(String[] args) { int[][] m1 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 }, { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, }; System.out.println(countIslands(m1)); int[][] m2 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 }, { 0, 1, 1, 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, }; System.out.println(countIslands(m2)); }这个是单核cpu时这么可以做到，如果要说可以用到多核cpu并行执行，那么就可以用到上面所介绍的并查集结构，将整个矩阵分成若干个，然后并行判断独立矩阵的岛的个数，并且每个独立矩阵内的岛记上标记，之后对于每个岛，获取到边界的状态，然后判断这个矩阵上下左右挨着的矩阵的边界是否都为1，如果为1，判断这两个连着的岛的标记是否为并集，如果不是，则合成并集，且岛的数量减一，如果是，则跳过判断下一个，直到所有的矩阵的上下左右都判断完成，就可以并行得到岛的数量。
前缀树就是如果相同的前缀字符串的话就共用，那么在查询前缀的数量的时候就很快。代码实现如下：
// 创建节点 public static class TrieNode { // 经过这个节点的次数 private int path; // 以这个节点为结尾的次数 private int end; // 这个节点展开的链 private TrieNode[] nexts; // 初始化 public TrieNode() { path = 0; end = 0; nexts = new TrieNode[26]; } } public static class Trie { // 根节点 private TrieNode root; public Trie() { root = new TrieNode(); } // 插入字符串 public void insert(String word) { if (word == null || "".equals(word)) { return; } // 转成char数组 char[] chars = word.toCharArray(); TrieNode node = root; int index = 0; // 循环char数组 for (int i = 0; i < chars.length; i++) { // a~z对应的就是acs码 97~121，那么相减就是0~25 index = chars[i] - 'a'; // 查看这个节点对应的结果字符的位置是否为null，空则创建一个新的对象 if (node.nexts[index] == null) { node.nexts[index] = new TrieNode(); } // 将这个node指向字符对应的位置的Node node = node.nexts[index]; // 并把经过的值加一 node.path++; } // 循环结束后就是末尾，所以把这个字符结束的末尾加一 node.end++; } // 查找相应的字符串有多少个 public int search(String word) { if (word == null || "".equals(word)) { return 0; } char[] chars = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chars.length; i++) { index = chars[i] - 'a'; // 如果下一个对应的位置为null，那么说明不存在这个单词，返回0 if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } // 结束后找到了对应的位置，那么end就是以这个链为结尾的次数 return node.end; } // 查询这个字符串前缀的次数 public int prefixNumber(String word) { if (word == null || "".equals(word)) { return 0; } char[] chars = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chars.length; i++) { index = chars[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } // 返回经过的次数 return node.path; } // 删除对应的字符串 public void delete(String word) { // 查找到有这个字符串时，才进行删除 if (search(word) != 0) { char[] chars = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chars.length; i++) { index = chars[i] - 'a'; // 如果下一个字符对应的经过次数为1，减后为0，那么说明只经过了一次，后面的也只经过一次 // 把这个字符对应的位置指向null，jvm就可以当成垃圾进行回收 if (--node.nexts[index].path == 0) { node.nexts[index] = null; return; } node = node.nexts[index]; } // 如果经过的次数都不为1，那么将最后的end次数减一 node.end--; } } } public static void main(String[] args) { Trie trie = new Trie(); System.out.println(trie.search("zuo")); trie.insert("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuo"); trie.insert("zuo"); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuoa"); trie.insert("zuoac"); trie.insert("zuoab"); trie.insert("zuoad"); trie.delete("zuoa"); System.out.println(trie.search("zuoa")); System.out.println(trie.prefixNumber("zuo")); }栈：先进后出，可以用一个指针来判断，代码实现如下：
// 用数组实现栈 public static class ArrayStack { // 初始化数组和指针 public Integer[] arr; public Integer index; // 指定数组大小 public ArrayStack(int initSize) { if (initSize <= 0) { throw new IllegalArgumentException("The init size is less than 0"); } arr = new Integer[initSize]; index = 0; } // 取得栈顶 public Integer peek() { if (index == 0) { return null; } return arr[index - 1]; } // 插入数据 public void push(int num) { // 当前数已经超过上下标 if (index == arr.length) { throw new ArrayIndexOutOfBoundsException("The queue is full"); } arr[index++] = num; } public Integer pop() { // 当前数已经是第一个了，取不到前一个的数 if (index == 0) { throw new ArrayIndexOutOfBoundsException("The queue is empty"); } return arr[--index]; } }队列：先进先出，可以用两个指针和目前的实际大小来判断，代码实现如下:
// 用数组实现队列 public static class ArrayQueue { public Integer[] arr; // 取出的下标 public Integer popIndex; // 插入的下标 public Integer pushIndex; // 数组内的大小 public Integer size; // 初始化数据 public ArrayQueue(int initSize) { if (initSize < 0) { throw new IllegalArgumentException("The init size is less than 0"); } arr = new Integer[initSize]; size = 0; popIndex = 0; pushIndex = 0; } // 取出队列的第一个 public Integer peek() { if (size == 0) { return null; } return arr[popIndex]; } // 插入值到队列中 public void push(int num) { if (size == arr.length) { throw new ArrayIndexOutOfBoundsException("The queue is full"); } // 把值给到对应的下标中 arr[pushIndex] = num; // 大小自增 size++; // 如果到了下标末尾，那么就跳到数组的第一个位置 pushIndex = pushIndex == arr.length - 1 ? 0 : pushIndex + 1; } // 取出值，并删除 public Integer poll() { if (size == 0) { throw new ArrayIndexOutOfBoundsException("The queue is empty"); } // 大小自减 size--; // 先用临时变量保存要返回的值 int temp = arr[popIndex]; // 如果到了下标末尾，那么就跳到数组的第一个位置 popIndex = popIndex == arr.length - 1 ? 0 : popIndex + 1; return temp; } }思路：由于队列是先进先出，那么每次只要取到队列的最后一个数，剩下的数传给另一个队列就可以实现，代码实现为：
// 队列转换成栈结构 public static class TwoQueueToStack{ // 创建两个队列 public Queue<Integer> queuePush; public Queue<Integer> queuePop; // 初始化 public TwoQueueToStack() { queuePush = new LinkedList<Integer>(); queuePop = new LinkedList<Integer>(); } // 给专门放数据的队列加新插入的值 public void push(int num) { queuePush.add(num); } // 取数据，并删除 public Integer pop() { if (queuePush.isEmpty()) { throw new RuntimeException("Stack is empty!"); } // 把要取出的数据以外，都加到另一个队列，那么就实现了拿出最后一个数，跟栈的性质一样了 while (queuePush.size() > 1) { queuePop.add(queuePush.poll()); } // 用临时变量取出最后一个数 int result = queuePush.poll(); // 把两个队列交换位置 swap(); return result; } // 与pop方法一样() public Integer peek() { if (queuePush.isEmpty()) { throw new RuntimeException("Stack is empty!"); } while (queuePush.size() > 1) { queuePop.add(queuePush.poll()); } int result = queuePush.poll(); // 由于peek方法不删除数据，那么取出后的数据也要加回到queuePop队列中 queuePop.add(result); swap(); return result; } // 交换两个队列位置 public void swap() { Queue<Integer> temp = queuePop; queuePop = queuePush; queuePush = temp; } }思路：由于栈是先进先出，那么传到另一个栈是顺序正好是队列要的顺序，而且还要等另一个栈必须空之后才能再次传入，因为另一个栈的栈顶是队列的第一个数，有数据的情况再次插入则不是队列的第一个，代码实现为：
// 栈转换成结队列构 public static class TwoStackToQueue{ // 创建两个栈 public Stack<Integer> stackPoll; public Stack<Integer> stackPush; public TwoStackToQueue() { stackPoll = new Stack<>(); stackPush = new Stack<>(); } // 给放数据的栈加入值 public void push(int num) { stackPush.push(num); } // 拿出数据 public Integer peek() { if (stackPoll.empty() && stackPush.empty()) { throw new RuntimeException("Queue is empty!"); } // 将push栈倒入到poll栈中 dao(); // 取出poll栈的栈顶 return stackPoll.peek(); } // 与peek方法一样 public Integer pop() { if (stackPoll.empty() && stackPush.empty()) { throw new RuntimeException("Queue is empty!"); } dao(); // 这里因为要删除数据，所以调用pop() return stackPoll.pop(); } // 将push栈的数据一次性放入到poll栈中 public void dao() { // 如果poll栈不为空，那么就不能放进去，要不然新加入的值就不是队列中的第一个值，变为push栈中栈底的值了 if (!stackPoll.empty()) { return; } // 所以只有不为空的时候，全部放入poll栈中。 while (!stackPush.isEmpty()) { stackPoll.push(stackPush.pop()); } } }实现一种猫狗对俄的结构，要求add方法将cat类或dog类放入队列中，pollAll方法按照队列先后顺序依次弹出，pollDog弹出狗，pollCat弹出猫，isEmpty检查队列是否为空，isDogEmpty和isCatEmpty也是相同的功能。
思路：本题不难，主要是考察怎么判断猫狗进出的顺序，多加一个类来添加成员变量判断即可，代码实现如下：
// 原始条件 public static class Pet { private String type; public Pet(String type) { this.type = type; } public String getPetType() { return this.type; } } public static class Dog extends Pet { public Dog() { super("dog"); } } public static class Cat extends Pet { public Cat() { super("cat"); } } // 每次加宠物时，除了pet外，增加一个count值来判断宠物的位列 public static class PetEnterQueue { private Pet pet; private long count; public PetEnterQueue(Pet pet, long count) { this.pet = pet; this.count = count; } public long getCount() { return this.count; } public Pet getPet() { return this.pet; } } public static class DogCatQueue { //狗队列 Queue<PetEnterQueue> dogQueue; //猫队列 Queue<PetEnterQueue> catQueue; // 这个实例此时此刻的位列 long count; // 初始化 public DogCatQueue() { dogQueue = new LinkedList<>(); catQueue = new LinkedList<>(); count = 0; } // 添加宠物 public void add(Pet pet) { // 判断宠物的类别，并且添加时将count分配到PetEnterQueue进行自增 if ("dog".equals(pet.getPetType())) { dogQueue.add(new PetEnterQueue(pet, count++)); } else if ("cat".equals(pet.getPetType())) { catQueue.add(new PetEnterQueue(pet, count++)); } else { throw new RuntimeException("this pet is not dog or cat"); } } // 取出宠物 public Pet pollAll() { // 判断两个队列是否为空 if (!dogQueue.isEmpty() && !catQueue.isEmpty()) { // count值小的说明是更早添加的，根据队列先进后出的原则，比较count后取出对应的宠物 return dogQueue.peek().getCount() < catQueue.peek().getCount() ? dogQueue.poll().getPet() : catQueue.poll().getPet(); } else if (!dogQueue.isEmpty()) { return dogQueue.poll().getPet(); } else if (!catQueue.isEmpty()) { return catQueue.poll().getPet(); } else { throw new RuntimeException("there have not pet"); } } // 取出狗 public Pet pollDog() { if (!dogQueue.isEmpty()) { return dogQueue.poll().getPet(); } else { throw new RuntimeException("there have not dog"); } } // 取出猫 public Pet pollCat() { if (!catQueue.isEmpty()) { return catQueue.poll().getPet(); } else { throw new RuntimeException("there have not cat"); } } public boolean isEmpty() { return dogQueue.isEmpty() && catQueue.isEmpty(); } public boolean isDogEmpty() { return dogQueue.isEmpty(); } public boolean isCatEmpty() { return catQueue.isEmpty(); } } public static void main(String[] args) { DogCatQueue test = new DogCatQueue(); Pet dog1 = new Dog(); Pet cat1 = new Cat(); Pet dog2 = new Dog(); Pet cat2 = new Cat(); Pet dog3 = new Dog(); Pet cat3 = new Cat(); test.add(dog1); test.add(dog1); test.add(dog1); test.add(cat1); test.add(dog2); test.add(cat2); test.add(dog3); test.add(cat3); while (!test.isEmpty()) { System.out.println(test.pollAll().getPetType()); } }给定一个整型正方形矩阵，把矩阵调整成顺时针旋转90度的样子，要求额外空间复杂度为O(1)。
思路为：旋转的话可以每一个框进行旋转，每个边上的点，也就是4个点之间旋转，循环整个边长，就可以得到相应的旋转后的位置。代码实现为：
// 按照坐标轴，把初始坐标和最大坐标的位置给过去 public static void rotate(int[][] matrix) { int startRow = 0; int startCol = 0; int endRow = matrix.length - 1; int endCol = matrix[0].length - 1; // 因为是正方形，这里用Col相减也可以 while (startRow < endRow) { // 每次初始坐标像右上靠近，最大坐标向左下靠近 rotateEdge(matrix, startRow++, startCol++, endRow--, endCol--); } } // 进行顺时针旋转90° public static void rotateEdge(int[][] matrix, int startRow, int startCol, int endRow, int endCol) { // 旋转相当于每个边上的位置替换到了相邻边的位置，那么循环次数就是边长，假设这里边长为4的话 for (int i = 0; i < endRow - startRow; i++) { // 先把最开始要赋予值用临时变量保存下来，在这里举例的话就是0，1 int temp = matrix[startRow][startCol + i]; // 0，1 的位置被 3，0代替 matrix[startRow][startCol + i] = matrix[endRow - i][startCol]; // 3，0 的位置被 4，3代替 matrix[endRow - i][startCol] = matrix[endRow][endCol - i]; // 4，3 的位置被 1，4代替 matrix[endRow][endCol - i] = matrix[startRow + i][endCol]; // 1，4 的位置被 0，1代替 matrix[startRow + i][endCol] = temp; } } // 打印矩阵 public static void printMatrix(int[][] matrix) { for (int i = 0; i != matrix.length; i++) { for (int j = 0; j != matrix[0].length; j++) { System.out.print(matrix[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; printMatrix(matrix); rotate(matrix); System.out.println("========="); printMatrix(matrix); }给定一个矩阵，按照“之”字形打印矩阵，且额外空间复杂度O(1)，例如：
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
那么要打印出来的顺序就是 1，2，5，9，6，3，4，7，10，11，8，12这样的蛇形输出。
思路：这时候光靠一个指针变化是得不到这个输出，蛇形输出的话也就是对角线输出，那么就可以利用两个指针，一个向右，一个向下，然后到头之后一个向下，一个向右，这样就可以一直输出对角线，再通过一个boolean判断输出方向就可以完成这道题。
代码实现如下：
// 之字型输出 public static void printZigMatrix(int[][] matrix) { // 点a的初始坐标 int aRow = 0; int aCol = 0; // 点b的初始坐标 int bRow = 0; int bCol = 0; // 最大行的下标 int endRow = matrix.length - 1; // 最大列的下标 int endCol = matrix[0].length - 1; // 设置向右上遍历还是左下遍历 boolean judge = false; // 当一开始横着走的b点往下走到头的时候就代表结束 while (bRow < endCol + 1) { // 调用输出 printLevel(matrix, aRow, aCol, bRow, bCol, judge); // a点是先往下走，在往右走，如果已经走到最底部，那么列就该往右走 aCol = aRow == endRow ? aCol + 1 : aCol; aRow = aRow == endRow ? aRow : aRow + 1; // b点是先往右走，再往下走，如果已经走到最后边，那么就该往下走 bRow = bCol == endCol ? bRow + 1 : bRow; bCol = bCol == endCol ? bCol : bCol + 1; // 与之前的输出方向相反 judge = !judge; } } public static void printLevel(int[][] matrix, int aRow, int aCol, int bRow, int bCol, boolean judge) { // 如果是true，则往左下输出，如果是false，往右上输出 if (judge) { while (bRow < aRow + 1) { System.out.print(matrix[bRow++][bCol--] + " "); } } else { while (aCol < bCol + 1) { System.out.print(matrix[aRow--][aCol++] + " "); } } }思路：如果空间复杂度没有要求，那么直接可以用栈结构，如果空间复杂度要求O(1)，那么可以将中间以后的指针反转过来，再从头和从尾依次遍历到中间，判断是否符合要求，再把链表还原。
代码实现如下：
// 实现链表回文结构 public static class Node { public int value; public Node next; public Node(int data) { this.value = data; } } // 额外空间复杂度O(N) public static boolean isPalindrome1(Node head) { if (head == null || head.next == null) { return true; } // 创建一个栈 Stack<Node> stack = new Stack<>(); Node cur = head; // 从头到尾把所有的链表存入栈中 while (cur != null) { stack.push(cur); cur = cur.next; } // 栈中弹出就是从后到前，与从前倒后依次比较 while (!stack.isEmpty()) { if (stack.pop().value != head.value) { return false; } head = head.next; } return true; } // 额外空间复杂度O(N/2) public static boolean isPalindrome2(Node head) { if (head == null || head.next == null) { return true; } // 也是创建一个栈 Stack<Node> stack = new Stack<>(); // 指定两个指针，一个慢指针，一个快指针，那么当快指针到最后时，慢指针一定在中间 Node mid = head; Node cur = head.next; // 如果快指针的下一个或下下一个为空，就可以停止了 while (cur.next != null && cur.next.next != null) { mid = mid.next; cur = cur.next.next; } // 这时候把中间轴之后和元素存到栈中 while (mid != null) { stack.push(mid); mid = mid.next; } // 然后依次弹出即可 while (!stack.isEmpty()) { if (stack.pop().value != head.value) { return false; } head = head.next; } return true; } // 额外空间复杂度O(1) public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } // 也是需要快慢指针 Node n1 = head; Node n2 = head.next; while (n2.next != null && n2.next.next != null) { n1 = n1.next; n2 = n2.next.next; } // 到达中间位置时，把中间位置指向null，然后将后面的指针都转到前一个 n2 = n1.next; n1.next = null; Node n3; while (n2 != null) { n3 = n2.next; n2.next = n1; n1 = n2; n2 = n3; } n2 = head; // 用n3保存一下最后一个位置 n3 = n1; boolean result = true; // 如果从头和从尾开始向中间遍历，右一个的下一个指向null，就可以结束了 while (n2 != null && n1 != null) { if (n2.value != n1.value) { result = false; break; } n2 = n2.next; n1 = n1.next; } // 验证后，需要把链表还原，利用到之前保存过的最后一个位置，一直到中间指向null为止。 n2 = n3.next; n3.next = null; while (n2 != null) { n1 = n2.next; n2.next = n3; n3 = n2; n2 = n1; } return result; } // 打印链表 public static void printLinkedList(Node node) { System.out.print("Linked List: "); while (node != null) { System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(2); head.next.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome3(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); }给定一个单向链表的头节点和一个指定的整数，实现功能。
思路：如果不考虑稳定性和额外空间复杂度，可以利用荷兰国旗问题，放入到数组中进行排序，之后再依次指向后一个节点。
如果要考虑稳定性和额外空间复杂度，那么可以创建6个节点，分别表示小，相等，大的节点头和尾，然后遍历链表分别放入6个节点，最后判断节点的状态，将小尾，相等头和尾，大头节点连接就可以得到结果。
代码实现如下：
public static class Node { public int value; public Node next; public Node(int data) { this.value = data; } } // 利用荷兰国旗问题的解法，不考虑稳定性，不考虑额外空间复杂度 public static Node listPartition1(Node head, int pivot) { if (head == null || head.next == null) { return head; } Node cur = head; // 定义一个Node的集合，这里可以用数组，我不想再循环一遍得到链表的长度，所以用的集合 List<Node> nodeList = new ArrayList<>(); // 放入集合中 while (cur != null) { nodeList.add(cur); cur = cur.next; } // 调用整理 arrPartition(nodeList, pivot); // 连起来 for (int i = 1; i < nodeList.size(); i++) { nodeList.get(i - 1).next = nodeList.get(i); } // 把最后的next指向为null nodeList.get(nodeList.size() - 1).next = null; // 返回链表头 return nodeList.get(0); } // 调整为止 private static void arrPartition(List<Node> nodeList, int pivot) { // 因为是整个数组，所以从头开始 int less = -1; int index = 0; int more = nodeList.size(); // 与荷兰国旗问题一样 while (index < more) { if (nodeList.get(index).value < pivot) { swap(nodeList, ++less, index++); } else if (nodeList.get(index).value > pivot) { swap(nodeList, index, --more); } else { index++; } } } // 考虑到稳定性和空间复杂度 public static Node listPartition2(Node head, int pivot) { if (head == null || head.next == null) { return head; } // 定义六个变量，分别是小的链表头和尾，相等的链表头和尾，大的链表头和尾 Node lessTop = null; Node lessButtom = null; Node equalTop = null; Node equalButtom = null; Node moreTop = null; Node moreButtom = null; // 把链表循环一次 while (head != null) { // 如果比pivot小，就放到小的链表中 if (head.value < pivot) { if (lessTop == null) { lessTop = head; lessButtom = head; } else { lessButtom.next = head; lessButtom = head; } // 如果与pivot相等，就放到相等的链表中 } else if (head.value > pivot) { if (moreTop == null) { moreTop = head; moreButtom = head; } else { moreButtom.next = head; moreButtom = head; } // 如果比pivot大，就放到大的链表中 } else { if (equalTop == null) { equalTop = head; equalButtom = head; } else { equalButtom.next = head; equalButtom = head; } } // 将head指向下一个 head = head.next; } // 如果小的链表有数据 if (lessButtom != null) { // 就把小的链表尾指向相等的链表头 lessButtom.next = equalTop; // 相等链表尾如果为空，则变为小的链表尾 equalButtom = equalButtom == null ? lessButtom : equalButtom; } // 如果相等的链表有数据 if (equalButtom != null) { // 把相等的链表尾指向大的链表头 equalButtom.next = moreTop; } // 如果大的链表头有数据，就把尾部指为null if (moreButtom != null) { moreButtom.next = null; } // 看哪个数据头不为空，则已这个数据头为链表头返回 return lessTop != null ? lessTop : equalTop != null ? equalTop : moreTop; } public static void swap(List<Node> nodeList, int a, int b) { Node tmp = nodeList.get(a); nodeList.set(a, nodeList.get(b)); nodeList.set(b, tmp); } public static void printLinkedList(Node node) { System.out.print("Linked List: "); while (node != null) { System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { Node head1 = new Node(7); head1.next = new Node(9); head1.next.next = new Node(1); head1.next.next.next = new Node(8); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(2); head1.next.next.next.next.next.next = new Node(5); printLinkedList(head1); //head1 = listPartition1(head1, 5); head1 = listPartition2(head1, 4); printLinkedList(head1); }除了next外，还有rand指针对应节点，是随机的节点，且不构成循环结构，请在时间复杂度O(N)的情况下解决
思路：1.如果不考虑空间复杂度，那么可以利用map的特性，来把旧值当作键，新值当作值存入，且调用的时间复杂度为O(1)
2.如果要考虑时间复杂度，就可以用旧链表和新链表组成一个链表，形成旧值->新值->旧值->新值的链表结构，那么旧值的rand之后的next就一定是对应新值的rand值，然后再拆分出来，返回新链表
代码实现如下：
public static class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } } // 如果不考虑空间问题，可以用map来简单做出来 public static Node copyListWithRand1(Node head) { // 创建键值都为Node的哈希表 HashMap<Node, Node> map = new HashMap<>(); Node cur = head; // 将所有的Node存入到map中，值为新创建的new Node； while (cur != null) { map.put(cur, new Node(cur.value)); cur = cur.next; } cur = head; // 通过map的键，也就是新拷贝的Node的值的next和rand指向next和rand为键的值 while (cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).rand = map.get(cur.rand); cur = cur.next; } // 将第一个头的拷贝值返回 return map.get(head); } // 如果不可以用哈希表的结构，空间复杂度要求O(1)，就得将旧值新值放在一个链表上，在进行rand的分配和next拆分 public static Node copyListWithRand2(Node head) { if (head == null) { return null; } Node cur = head; Node next; // 循环出一个旧值->新值->旧值->新值的链表 while (cur != null) { next = cur.next; cur.next = new Node(cur.value); cur.next.next = next; cur = next; } cur = head; // 将返回的新值链表头保存 Node res = head.next; Node curCopy; // 将rand值对应，新值的rand值就是旧值的rand值的next while (cur != null) { next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand != null ? cur.rand.next : null; cur = next; } cur = head; // 将链表拆分成旧链表和新链表 while (cur != null) { next = cur.next.next; curCopy = cur.next; cur.next = next; curCopy.next = next != null ? next.next : null; cur = next; } return res; } public static void printRandLinkedList(Node head) { Node cur = head; System.out.print("order: "); while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); cur = head; System.out.print("rand: "); while (cur != null) { System.out.print(cur.rand == null ? "- " : cur.rand.value + " "); cur = cur.next; } System.out.println(); } public static void main(String[] args) { Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head.rand = head.next.next.next.next.next; // 1 -> 6 head.next.rand = head.next.next.next.next.next; // 2 -> 6 head.next.next.rand = head.next.next.next.next; // 3 -> 5 head.next.next.next.rand = head.next.next; // 4 -> 3 head.next.next.next.next.rand = null; // 5 -> null head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4 Node res1 = copyListWithRand1(head); printRandLinkedList(res1); printRandLinkedList(head); Node res2 = copyListWithRand2(head); printRandLinkedList(res2); printRandLinkedList(head); System.out.println("========================="); }单链表可能有环也可能无环，给定两个单链表的头节点，如果两个链表相交，返回相交第一个节点，不相交，返回null，时间复杂度(N+M), 空间复杂度O(1)
思路： 1.不考虑空间复杂度，可以使用HashSet来遍历链表，放入进去，如果发现有相同的，那么就有环，之后另一个链表遍历，不放入进去，每次判断自己的节点是否在HashSet中，有代表两个链表有交点，返回那个交点即可，这个不实现了，不要求空间时候很快实现。
2.也是本题要求，那么我们可以用慢节点和快节点先获取到进入循环的入口，没有环就是null，如果连个都没有环，那么有可能是相交成一个链表，取得两链表长度，然后让长的链表先走它们的差值，然后一起往下遍历，相交的第一个点就是交点，如果有环，且入口是相同的，那么两个链表是相交后进入环，那么交点还是可以用前面的方法取得，如果进入循环的点不同，那么让一个链表在环中循环一次，检查有没有另一个链表的loop，有就是两表有交点，只不过进入的顺序可能不同，位置也有可能不同，如果发现没有loop，那么就是两个独立的链表，返回null。
代码实现如下：
public static class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public static Node getIntersectNode(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } // 调用方法，取得两个链表的刚进入环的节点，没有则null Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); // 如果两个节点都是null，那么两个都没有环，就调用没有环时判断有无交点的方法 if (loop1 == null && loop2 == null) { return noLoop(head1, head2, loop1, loop2); // 如果两个节点都有环，就调用有环时有无交点的方法 } else if (loop1 != null && loop2 != null) { return bothLoop(head1, head2, loop1, loop2); } else { // 一个有环，一个没环一定没有交点 return null; } } public static Node getLoopNode(Node head) { // 为了用快指针和慢指针要先判断后两个节点是否为null if (head.next == null || head.next.next == null) { return null; } // 慢节点 Node slow = head.next; // 快节点 Node fast = head.next.next; // 当快节点追上慢节点，一定有环 while (slow != fast) { // 如果为null，那么就是没环 if (fast.next == null || fast.next.next == null){ return null; } slow = slow.next; fast = fast.next.next; } // 追上后，快节点从头开始遍历，那么和慢节点相交的位置就是进入环的节点loop fast = head; while (fast != slow) { slow = slow.next; fast = fast.next; } return fast; } // 都没有环时的方法 public static Node noLoop(Node head1, Node head2, Node loop1, Node loop2) { // 定义长度 int count = 0; Node cur1 = head1; Node cur2 = head2; // head1遍历，count++ while (cur1.next != loop1) { cur1 = cur1.next; count++; } // head1遍历，count-- while (cur2.next != loop2) { cur2 = cur2.next; count--; } // 如果count大于0，就是head1是长的，就把head1给cur1，否则head2给cur1，因为后面要遍历cur1到多出来的长度 cur1 = count > 0 ? head1 : head2; // cur2则是与cur1相反 cur2 = cur1 == head1 ? head2 :head1; // 取绝对值 count = Math.abs(count); // 将cur1走到与cur2一样的长度 while (count > 0) { count--; cur1 = cur1.next; } // 那么一起遍历相等的地方就是两个链表的交点 while (cur1 != cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } // 都有环时的方法 public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) { // 如果两个进入环的节点相同，那么之前的情况可以想成没有环时相交的情况，可以重复用noLoop方法，只不过loop不为null，遍历到进入环前就可以 if (loop1 == loop2) { return noLoop(head1, head2, loop1, loop2); } else { // 如果不相同，则要么是进入环的先后顺序不同，要么是两个独立的环，没有交点 Node cur = loop1.next; // cur开始遍历环 while (cur != loop1) { // 如果遇到了loop2，表示两个链表都用一个环，先后顺序不同，返回哪个都可以，对应自己来说都是最近的相交点 if (cur == loop2) { return loop1; } cur = cur.next; } // 循环环发现没找到，那么就属于两个独立的环，没有交点 return null; } } public static void main(String[] args) { // 1->2->3->4->5->6->7->null Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); // 0->9->8->6->7->null Node head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println(getIntersectNode(head1, head2).value); // 1->2->3->4->5->6->7->4... head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); head1.next.next.next.next.next.next = head1.next.next.next; // 7->4 // 0->9->8->2... head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next; // 8->2 System.out.println(getIntersectNode(head1, head2).value); // 0->9->8->6->4->5->6.. head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println(getIntersectNode(head1, head2).value); }思路：递归的就比较简单，在相应调递归的方法的对应位置，就可以输出得到结果
非递归可以用栈结构来存储，递归本身也是用的栈来实战，所以我们也可以用相应的结构来实现，具体代码实现如下：
public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } // 用递归都是在对应递归的位置输出就可以 public static void preOrderRecur(Node head) { if (head == null) { return; } System.out.print(head.value + " "); preOrderRecur(head.left); preOrderRecur(head.right); } public static void inOrderRecur(Node head) { if (head == null) { return; } inOrderRecur(head.left); System.out.print(head.value + " "); inOrderRecur(head.right); } public static void posOrderRecur(Node head) { if (head == null) { return; } posOrderRecur(head.left); posOrderRecur(head.right); System.out.print(head.value + " "); } // 先序遍历 public static void preOrderUnRecur(Node head) { if (head == null) { return; } // 创建一个栈 Stack<Node> stack = new Stack<>(); // 先把第一个节点加进去，进行输出 stack.add(head); while (!stack.isEmpty()) { // 取栈顶输出 head = stack.pop(); System.out.print(head.value + " "); // 由于先进后出原则，如果要先输出左边，那么就要先压入右边 if (head.right != null) { stack.push(head.right); } if (head.left != null) { stack.push(head.left); } } System.out.println(); } // 中序遍历 public static void inOrderUnRecur(Node head) { if (head == null) { return; } // 先创建一个栈 Stack<Node> stack = new Stack<>(); // stack为空，并且head也为null说明遍历完 while (!stack.isEmpty() || head != null) { // 因为是左中右，所以先把值存进去 if (head != null) { stack.push(head); // 然后指向左边 head = head.left; } else { // 如果head为null，说明到左边头了，那么就输出 head = stack.pop(); System.out.print(head.value + " "); // 然后将指针指向右 head = head.right; } } } // 后序遍历，后序遍历用一个栈实现起来比较绕，这里可以使用两个栈来输出 public static void posOrderUnRecur(Node head) { if (head == null) { return; } // 第一个栈用来遍历中右左，那么存到另一个栈中输出就变成了左右中 Stack<Node> stack = new Stack<>(); stack.push(head); // 输出的栈 Stack<Node> stackPrint = new Stack<>(); while (!stack.isEmpty()) { // 要输出的值保存在stackPrint中 head = stack.pop(); stackPrint.push(head); // 然后先压入左边 if (head.left != null) { stack.push(head.left); } // 再压入右边 if (head.right != null) { stack.push(head.right); } } // 然后输出的就是左右中 while (!stackPrint.isEmpty()) { System.out.print(stackPrint.pop().value + " "); } System.out.println(); } public static void main(String[] args) { Node head = new Node(5); head.left = new Node(3); head.right = new Node(8); head.left.left = new Node(2); head.left.right = new Node(4); head.left.left.left = new Node(1); head.right.left = new Node(7); head.right.left.left = new Node(6); head.right.right = new Node(10); head.right.right.left = new Node(9); head.right.right.right = new Node(11); // recursive System.out.println("==============recursive=============="); System.out.print("pre-order: "); preOrderRecur(head); System.out.println(); System.out.print("in-order: "); inOrderRecur(head); System.out.println(); System.out.print("pos-order: "); posOrderRecur(head); System.out.println(); // unrecursive System.out.println("============unrecursive============="); preOrderUnRecur(head); inOrderUnRecur(head); System.out.println(); posOrderUnRecur(head); }这个二叉树节点多一个parent，可以找到自己的父节点，在中序遍历中，node的下一个节点就是后继节点
思路为：因为是中序遍历，如果这个节点有右子树，那么右子树的最左节点一定就是下一个要输出的节点，没有右子树，那么就可以找自己的parent的左子树是不是自己，不是就继续往上找，直到找到为止。 代码实现如下：
public static class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; } } public static Node getSuccessorNode(Node node) { if (node == null) { return node; } // 如果有右子树，那么右子树的最左节点就是后继节点 if (node.right != null) { return getLeftNode(node.right); } else { // 如果没有右子树，那么就找parent的左节点是不是自己，如果是的话parent就是后继节点 Node parent = node.parent; while (parent != null && parent.left != node) { node = parent; parent = node.parent; } return parent; } } public static Node getLeftNode(Node node) { // 一直寻找左节点 while (node.left != null) { node = node.left; } return node; } public static void main(String[] args) { Node head = new Node(6); head.parent = null; head.left = new Node(3); head.left.parent = head; head.left.left = new Node(1); head.left.left.parent = head.left; head.left.left.right = new Node(2); head.left.left.right.parent = head.left.left; head.left.right = new Node(4); head.left.right.parent = head.left; head.left.right.right = new Node(5); head.left.right.right.parent = head.left.right; head.right = new Node(9); head.right.parent = head; head.right.left = new Node(8); head.right.left.parent = head.right; head.right.left.left = new Node(7); head.right.left.left.parent = head.right.left; head.right.right = new Node(10); head.right.right.parent = head.right; Node test = head.left.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.left.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.right.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.left.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.right; // 10's next is null System.out.println(test.value + " next: " + getSuccessorNode(test)); }就是将二叉树持久化成别的结构，然后再通过这个结构恢复一个树结构
思路：用什么方式序列化就要用什么方法反序列化，这里用先序和层级遍历的方式，代码实现如下：
public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } // 通过先序遍历，将链表序列化成字符串 public static String serialByPre(Node head) { if (head == null) { return "#!"; } String str = head.value + "!"; str += serialByPre(head.left); str += serialByPre(head.right); return str; } // public static Node reconByPreString(String str) { String[] res = str.split("!"); Queue<String> result = new LinkedList<>(); // 将字符串按照预定好的结构遍历进队列中 for (int i = 0; i < res.length; i++) { result.add(res[i]); } // 调用解析Node方法 return reconPreOrder(result); } // 递归队列 public static Node reconPreOrder(Queue<String> queue) { // 拿出第一个 String str = queue.poll(); if ("#".equals(str)) { return null; } // 将这个值给到head中 Node head = new Node(Integer.valueOf(str)); // 左子树递归后给left head.left = reconPreOrder(queue); // 右子树递归后给right head.right = reconPreOrder(queue); return head; } // 通过层级遍历 public static String serialByLevel(Node head) { if (head == null) { return "#!"; } // 一层一层赋予给res String res = head.value + "!"; Queue<Node> queue = new LinkedList<Node>(); // 先将第一层放入队列 queue.offer(head); while (!queue.isEmpty()) { // 拿出队列的元素 head = queue.poll(); // 左子树不为空，就加到字符串中，并且加到列队中，之后对这个左子树当成父节点进行一样的操作 if (head.left != null) { res += head.left.value + "!"; queue.offer(head.left); } else { // 如果是空，就直接加到字符串就可以 res += "#!"; } if (head.right != null) { res += head.right.value + "!"; queue.offer(head.right); } else { res += "#!"; } } return res; } // 层级遍历解析 public static Node reconByLevelString(String levelStr) { String[] values = levelStr.split("!"); // 定义下标，对应的顺序就是从第一层一直到最后一层 int index = 0; // 取得顶点 Node head = generateNodeByString(values[index++]); Queue<Node> queue = new LinkedList<>(); // 放入到队列中 if (head != null) { queue.offer(head); } Node node; // 与层级遍历序列化一样，需要遍历队列，一层一层还原给父node while (!queue.isEmpty()) { // 拿出的父node node = queue.poll(); // 左节点，右节点对应数组的下标取得节点 node.left = generateNodeByString(values[index++]); node.right = generateNodeByString(values[index++]); // 不为null则放入到队列中 if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } // 返回头部 return head; } // 生成Node返回 public static Node generateNodeByString(String val) { if (val.equals("#")) { return null; } return new Node(Integer.valueOf(val)); } // for test -- print tree public static void printTree(Node head) { System.out.println("Binary Tree:"); printInOrder(head, 0, "H", 17); System.out.println(); } public static void printInOrder(Node head, int height, String to, int len) { if (head == null) { return; } printInOrder(head.right, height + 1, "v", len); String val = to + head.value + to; int lenM = val.length(); int lenL = (len - lenM) / 2; int lenR = len - lenM - lenL; val = getSpace(lenL) + val + getSpace(lenR); System.out.println(getSpace(height * len) + val); printInOrder(head.left, height + 1, "^", len); } public static String getSpace(int num) { String space = " "; StringBuffer buf = new StringBuffer(""); for (int i = 0; i < num; i++) { buf.append(space); } return buf.toString(); } public static void main(String[] args) { Node head = null; printTree(head); String pre = serialByPre(head); System.out.println("serialize tree by pre-order: " + pre); head = reconByPreString(pre); System.out.print("reconstruct tree by pre-order, "); printTree(head); String level = serialByLevel(head); System.out.println("serialize tree by level: " + level); head = reconByLevelString(level); System.out.print("reconstruct tree by level, "); printTree(head); System.out.println("===================================="); head = new Node(1); printTree(head); pre = serialByPre(head); System.out.println("serialize tree by pre-order: " + pre); head = reconByPreString(pre); System.out.print("reconstruct tree by pre-order, "); printTree(head); level = serialByLevel(head); System.out.println("serialize tree by level: " + level); head = reconByLevelString(level); System.out.print("reconstruct tree by level, "); printTree(head); System.out.println("===================================="); head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.right.right = new Node(5); printTree(head); pre = serialByPre(head); System.out.println("serialize tree by pre-order: " + pre); head = reconByPreString(pre); System.out.print("reconstruct tree by pre-order, "); printTree(head); level = serialByLevel(head); System.out.println("serialize tree by level: " + level); head = reconByLevelString(level); System.out.print("reconstruct tree by level, "); printTree(head); System.out.println("===================================="); head = new Node(100); head.left = new Node(21); head.left.left = new Node(37); head.right = new Node(-42); head.right.left = new Node(0); head.right.right = new Node(666); printTree(head); pre = serialByPre(head); System.out.println("serialize tree by pre-order: " + pre); head = reconByPreString(pre); System.out.print("reconstruct tree by pre-order, "); printTree(head); level = serialByLevel(head); System.out.println("serialize tree by level: " + level); head = reconByLevelString(level); System.out.print("reconstruct tree by level, "); printTree(head); System.out.println("===================================="); }搜索二叉树就是左节点的值大于父节点，父节点的值小于右节点。
思路：如果用非递归的方式可以将之前实现的中序遍历的输出结果进行比较，查看是否是递增的，不是则返回false，如果用递归的方式，就要判断左右子树分别是不是符合搜索二叉树的要求，再判断左节点和右节点的值与父节点的值满不满足要求。
代码实现如下：
public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } // 通过之前的中序遍历，可以改几个地方就可以判断搜索二叉树 public static boolean inOrderBST(Node head) { if (head == null) { return true; } // 先定义一个比较的值 int max = Integer.MIN_VALUE; // 剩下的都是一样的 Stack<Node> stack = new Stack<>(); while (!stack.isEmpty() || head != null) { if (head != null) { stack.push(head); head = head.left; } else { head = stack.pop(); // 这里就不进行输出，而是将取出的值与之前比较过的最大值进行比较 max = Math.max(head.value, max); // 如果取出的值不是最大值，那么左子树向上就不是递增的，那么就不符合搜索树，返回false if (max != head.value) { return false; } head = head.right; } } return true; } // 递归方法判断搜索树 public static boolean isBST(Node head) { if (head == null) { return true; } // 先将左子树的判断结果得到 boolean leftNode = isBST(head.left); // 如果左子树已经不是搜索树了，那么直接返回false if (!leftNode) { return false; } // 右子树的判断结果得到 boolean rightNode = isBST(head.right); // 如果右子树已经不是搜索树了，也返回false if (!rightNode) { return false; } // 定义一个变量 boolean result = true; // 左子树不为空，且左子树的值大于父节点，那么就不符合 if (head.left != null && head.left.value > head.value) { result = false; } // 右子树不为空，且右子树的值大于父节点，那么就不符合 if (head.right != null && head.right.value < head.value) { result = false; } // 走到这里说明左子树和右子树都符合搜索树，且左子树的值小于父节点，右子树的值大于父节点 return result; } // for test -- print tree public static void printTree(Node head) { System.out.println("Binary Tree:"); printInOrder(head, 0, "H", 17); System.out.println(); } public static void printInOrder(Node head, int height, String to, int len) { if (head == null) { return; } printInOrder(head.right, height + 1, "v", len); String val = to + head.value + to; int lenM = val.length(); int lenL = (len - lenM) / 2; int lenR = len - lenM - lenL; val = getSpace(lenL) + val + getSpace(lenR); System.out.println(getSpace(height * len) + val); printInOrder(head.left, height + 1, "^", len); } public static String getSpace(int num) { String space = " "; StringBuffer buf = new StringBuffer(""); for (int i = 0; i < num; i++) { buf.append(space); } return buf.toString(); } public static void main(String[] args) { Node head = new Node(4); head.left = new Node(2); head.right = new Node(6); head.left.left = new Node(1); head.left.right = new Node(3); head.right.left = new Node(5); printTree(head); System.out.println(isBST(head)); }思路：根据二叉树的性质，从左边依次填满，所以可以利用层级遍历来判断，如果出现右节点不为null，左节点为null，那么必然不是完全二叉树，如果右节点为null，不管左节点是不是null，之后的节点都必须为叶子节点，代码实现如下：
// 用层级遍历判断是否为完全二叉树 public static boolean isCBT(Node head) { if (head == null) { return true; } // 先定义一个变量，判断之后的是否必须是叶子节点 boolean leaf = false; // 创建一个队列，将每层依次放入队列中 Queue<Node> queue = new LinkedList<>(); queue.add(head); while (!queue.isEmpty()) { head = queue.poll(); // 如果需要下一个必须是叶子节点的情况，左节点和右节点只要不是null，那么就不是叶子节点，返回false if (leaf && (head.left != null || head.right != null) // 如果右节点不为null，做节点为null，那么一定不是完全二叉树 || (head.left == null && head.right != null)) { return false; } // 左右节点不为null的话就存到队列中 if (head.left != null) { queue.offer(head.left); } if (head.right != null) { queue.offer(head.right); } else { // 因为上面已经判断过左节点为null，右节点不为null的情况 // 所以这里只需要判断右节点为null的时候，不管左节点有没有值，都必须之后的节点都为叶子节点 leaf = true; } } return true; }输出结果可以用上面的搜索二叉树来输出。
思路：由于是完全二叉树，如果右子树到达了最底端，那么左子树此时一定是满二叉树，根据公式可得出数量，如果右子树没到达，那么右子树一定是高度-1的满二叉树，也可以得到，然后递归得到最终的数量，代码实现如下：
public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } // 主方法得到这个数的节点个数 public static int nodeNum(Node head) { if (head == null) { return 0; } return bs(head, 1, mostLeftHeight(head, 1)); } // level是层，h是高度 public static int bs(Node node, int level, int h) { // 如果层与高度相等，那么就是叶子节点，它的子树的节点数量就是它自己 if (level == h) { return 1; } // 调用右子树的左子树的最深高度，是否等于这个树的高度，等于，那么说明右子树到达了树的最底端 if (mostLeftHeight(node.right, level + 1) == h) { // 那么左子树的数量就是2的高度-层的次方，然后再递归调用右子树的节点个数 return (1 << (h - level)) + bs(node.right, level + 1, h); } else { // 如果不等于，说明右子树没到最底端，那么右节点是满二叉树，高度少一个，再算出左子树的节点个数就可以 return (1 << (h - level - 1)) + bs(node.left, level + 1, h); } } // 获得左子树的最左节点所在的高度 public static int mostLeftHeight(Node node, int level) { while (node != null) { node = node.left; level++; } return level - 1; } public static void main(String[] args) { Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); System.out.println(nodeNum(head)); }设计一种结构，insert，delete还有getRandom等概率返回结构中的任何一个key，并且所有的方法的时间复杂度为O(1)。
思路：可以设计两个hash来完成这个功能，然后用key，Integer和Integer，key来实现，并且用size来查看当前的大小，具体代码实现如下：
// 先定义两个hash表和一个size大小 public static class Pool<K> { private HashMap<K, Integer> keyIndexHash; private HashMap<Integer, K> indexKetHash; int size; // 初始化 public Pool() { this.keyIndexHash = new HashMap<>(); this.indexKetHash = new HashMap<>(); this.size = 0; } // 插入时，如果没有，则往里添加，integer值就是size自增 public void insert(K key) { if (!this.keyIndexHash.containsKey(key)) { this.keyIndexHash.put(key, this.size); this.indexKetHash.put(this.size++, key); } } // 如果size不为0，就可以随机返回 public K getRandom() { if (this.size == 0) { return null; } // indexKetHash里存的是key，然后根据Math.random()绝对等概率的返回其key值 return this.indexKetHash.get((int)(Math.random() * this.size)); } // 删除时，如果右空洞，那么math.random就会打空，那么就会重新math.random，浪费时间 public void delete(K key) { if (this.keyIndexHash.containsKey(key)) { // 先得到要删除的Index int deleteIndex = this.keyIndexHash.get(key); // 然后得到最后一个index int lastIndex = --this.size; // 得到最后一个index对应的key K lastKey = this.indexKetHash.get(lastIndex); // 将要删除的index位置的key更新成最后一个key this.indexKetHash.put(deleteIndex, lastKey); // 因为indexKetHash改了，那么keyIndexHash对应的最后位置key的index就要改成deleteIndex this.keyIndexHash.put(lastKey, deleteIndex); // 然后删除掉最后一个index this.indexKetHash.remove(lastIndex); // 这里就正常删除就可以 this.keyIndexHash.remove(key); } } } public static void main(String[] args) { Pool<String> pool = new Pool<String>(); pool.insert("xiao"); pool.insert("xiao"); pool.insert("bai"); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); }一块金条要切成指定的大小，比如60长度的金条要切成数组[10,20,30]的大小，每次切的时候都会花费切的金条长度的铜板，比如60要切成30和30，就要消耗60铜板，切的比例随便，用最小代价来实现。
代码实现如下：
public static int lessMoney(int[] arr) { // 创建小根堆 PriorityQueue<Integer> queue = new PriorityQueue<>(); for (int i = 0; i < arr.length; i++) { queue.add(arr[i]); } int sum = 0; int cur = 0; // 每次将两个最小的拿出，然后相加，这个值就是切这个的最小代价，再放回到队列中，然后sum加上这个最小代价 while (queue.size() > 1) { cur = queue.poll() + queue.poll(); queue.add(cur); sum += cur; } return sum; } public static class MinHeapComparator implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } } public static class MaxHeapComparator implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } } public static void main(String[] args) { // solution int[] arr = { 6, 7, 8, 9 }; System.out.println(lessMoney(arr)); int[] arrForHeap = { 3, 5, 2, 7, 0, 1, 6, 4 }; // min heap PriorityQueue<Integer> minQ1 = new PriorityQueue<>(); for (int i = 0; i < arrForHeap.length; i++) { minQ1.add(arrForHeap[i]); } while (!minQ1.isEmpty()) { System.out.print(minQ1.poll() + " "); } System.out.println(); // min heap use Comparator PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinHeapComparator()); for (int i = 0; i < arrForHeap.length; i++) { minQ2.add(arrForHeap[i]); } while (!minQ2.isEmpty()) { System.out.print(minQ2.poll() + " "); } System.out.println(); // max heap use Comparator PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxHeapComparator()); for (int i = 0; i < arrForHeap.length; i++) { maxQ.add(arrForHeap[i]); } while (!maxQ.isEmpty()) { System.out.print(maxQ.poll() + " "); } }有两个数组，一个是项目所花费金额的数组，一个是项目所获得的利润的数组，给定总金额w和最大次数k，在k次下，每做完一个项目，马上获得收益，支持你做下一个项目，那么最后返回所获得的最大钱数。
代码实现如下：
// 创建一个对象，里面包含有这个项目的消耗金额和利润 public static class Node { public int cost; public int profit; public Node(int cost, int profit) { this.cost = cost; this.profit = profit; } } // 最小消耗堆 public static class MinHeapCostComparator implements Comparator<Node> { @Override public int compare(Node o1, Node o2) { return o1.cost - o2.cost; } } // 最大利润堆 public static class MaxHeapProfitComparator implements Comparator<Node> { @Override public int compare(Node o1, Node o2) { return o2.profit - o1.profit; } } // 返回可获得的总金额 public static int findMaximizedCaptial(int k, int w, int[] Profits, int[] Capital) { // 创建项目 Node[] nodes = new Node[Profits.length]; // 将每个项目的消耗和利润赋予 for (int i = 0; i < Profits.length; i++) { nodes[i] = new Node(Capital[i], Profits[i]); } // 创建两个堆 PriorityQueue<Node> minCostQueue = new PriorityQueue<>(new MinHeapCostComparator()); PriorityQueue<Node> maxProfitQueue = new PriorityQueue<>(new MaxHeapProfitComparator()); // 将消耗金额堆赋予 for (int i = 0; i < Capital.length; i++) { minCostQueue.add(nodes[i]); } // 完成k次最多 for (int i = 0; i < k; i++) { // 如果还有项目可以做，并且最小的消耗金额要不大于总金额，就可以把这个项目传到最大利润堆中 while (!minCostQueue.isEmpty() && minCostQueue.peek().cost <= w) { maxProfitQueue.add(minCostQueue.poll()); } // 利润堆如果为空，说明现在的金额无法做目前最小消耗金额的项目，直接返回 if (maxProfitQueue.isEmpty()) { return w; } // 加上利润 w += maxProfitQueue.poll().profit; } return w; }有几个不同开始时间和结束时间的会议，给定现在的时间，如何去安排这些会议，可以安排最多次数。
代码实现如下：
// 开始时间和结束时间 public static class Program { private Date start; private Date end; public Program(Date start, Date end) { this.start = start; this.end = end; } } // 按照结束顺序的大小进行排序 public static class ProgramComparator implements Comparator<Program> { @Override public int compare(Program o1, Program o2) { return o1.end.compareTo(o2.end); } } // 返回可安排的次数 public static int bestArrange(Program[] programs, Date start) { // 按照结束时间对原数组进行排序 Arrays.sort(programs, new ProgramComparator()); int result = 0; for (int i = 0; i < programs.length; i++) { // 如果数组中的开始时间在给定时间的后面，则可以安排 if (programs[i].start.after(start)) { // 那么给定的时间就要变成这个会议的结束时间 start = programs[i].end; // 次数自增 result++; } } return result; }有三个杆，将最左边移动到最右边的过程，像塔一样从下到上逐渐是小的，切大的不能亚小的。N为塔的层数
思路：可以将问题拆分成N-1移动到中间，然后N移动到右边，然后再把N-1从中间移动到右边的过程，那么就可以用递归来实现，代码实现如下：
// N是塔的高度， from是要挪动的杆，help是可以借助的杆，to是目标杆 public static void move(int N, String from, String help, String to) { // 如果只有1，那么直接将1挪动到目标杆 if (N == 1) { System.out.println("move 1 from " + from + " to " + to); return; } // 先将N-1从from移动到help，然后to这时候变成借助杆 move(N - 1, from, to, help); // 挪动完了，那么N移动到目标杆 System.out.println("move " + N + " from " + from + " to " + to); // N移动后，将help中剩下的移动到to，这时候from为空，那么from就可以变为借助杆 move(N - 1, help, from, to); } public static void main(String[] args) { move(3, "左", "中", "右"); }代码实现如下：
// 字符串的所有序列化 public static void print(String str) { process(str.toCharArray(), 0); } // 递归数组，打印全序列 public static void process(char[] chs, int i) { // 如果i加到了长度，那么就输出，然后返回 if (i == chs.length) { System.out.println(String.valueOf(chs)); return; } // 分成第二个位置同样执行 process(chs, i + 1); char temp = chs[i]; // 第一个位置为空的时候 chs[i] = ' '; // 再次调用 process(chs, i + 1); // 将第一个位置还原 chs[i] = temp; } // 字符串的所有排序列 public static void printAllPermutations(String str) { char[] chs = str.toCharArray(); processPermutations(chs, 0); } public static void processPermutations(char[] chs, int i) { if (i == chs.length) { System.out.println(String.valueOf(chs)); return; } // 从传入的i的位置开始调换位置，并且将调换位置之后的数组再次进行递归分成小问题 for (int j = i; j < chs.length; j++) { swap(chs, j, i); processPermutations(chs, i + 1); // 递归后，要将交换的位置还原 swap(chs, j, i); } } public static void swap(char[] chs, int i, int j) { char tmp = chs[i]; chs[i] = chs[j]; chs[j] = tmp; } public static void main(String[] args) { String test = "abc"; print(test); printAllPermutations(test); }KMP算法是判断字符串B是否在字符串A中，那么可以将字符串B的每个字符前最大的公共前缀后缀相等，然后对于A,B判断时，如果某个字符不相等，那么就可以通过这个B中的字符的最大公共前后缀部分，然后通过前缀的后一个与A的那个字符进行判断，代码实现如下：
// 获取index位置 public static int getIndexOf(String str1, String str2) { if (str1 == null || str2 == null || str2.length() < 1 || str2.length() > str1.length()) { return -1; } char[] chars1 = str1.toCharArray(); char[] chars2 = str2.toCharArray(); int i1 = 0; int i2 = 0; // 获取str2的最大公共前缀后缀相等的长度的数组 int[] next = getNextArray(chars2); // 任意下标大于长度即可跳出循环 while (i1 < chars1.length && i2 < chars2.length) { // 如果两个位置相等，那么都往前移，进行下一个判断 if (chars1[i1] == chars2[i2]) { i1++; i2++; // 如果不相等，且str2的第一个位置，那么i1就往前推进 } else if (next[i2] == - 1) { i1++; // 如果不相等，但不是第一个位置，那么就与对应的最大公共前缀后缀相等的长度的位置进行判断 } else { i2 = next[i2]; } } // 如果i2已经走完了，说明一定包含，那么就是i1已经走过的区域-i2的长度就是index了，如果不相等， 那么说明i2没有判断完，说明不存在 return i2 == chars2.length ? i1 - i2 : -1; } // 获取str2的最大公共前缀后缀相等的长度的数组 public static int[] getNextArray(char[] str) { // 如果只有一个元素，那么直接返回-1的就可以了 if (str.length == 1) { return new int[] { -1 }; } // 创建数组 int[] next = new int[str.length]; // 下标1的时候，前面只有一个元素，那么肯定是0 next[0] = -1; next[1] = 0; // 0，1位置已经确定了，那么从2开始判断 int i = 2; int cn = 0; while (i < str.length) { // 相等，那么这个位置的长度就是cn推进的长度 if (str[i] == str[cn]) { next[i++] = ++cn; // 如果不相等，且cn还大于0，那么就可以继续拆分到cn所在位置的最大前后缀相等长度的前缀后一个位置 } else if (cn > 0) { cn = next[cn]; } else { // 如果cn都等于0或-1，那么就不可能有前后缀相同，那么长度就是0 next[i++] = 0; } } return next; } public static void main(String[] args) { String a = "ababababa"; String b = "babababa"; System.out.println(getIndexOf(a,b)); }判断最大回文串长度，因为在偶数的不好判断，比如1221，从2位置判断前后不相等的问题，因此可以先将结构变成#1#2#2#1这种结构，那么不管是奇数偶数，都会有中心点相对称，得到每个位置的最大回文半径，就可以得到整个字符串的最大回文数了，为了减少判断次数，可以进行以下优化：
如果最右边的R位置小于要判断的i的位置，那么R就直接往前推移，并继续判断。如果最右边的R位置大于要判断的i的位置：(1) 如果i对应的C对称的p的位置的回文半径也就是i的回文半径，小于R的话，那么这个直接是i的回文半径。
(2)如果p的回文半径大于R了，那么R-i就是i的最大回文半径，因为最大R里没有包括p的，那么i的回文数只在R-i内与p相等，之后肯定不相等。
(3)如果正好p的回文半径与R相等，赋予之后还要继续判断后面的是否与前面的相等，因为有可能i的回文数要比p更大。
代码实现如下：
// 构造#1#2#1#的结构 public static char[] manacherString(String str) { char[] charstr = str.toCharArray(); char[] res = new char[2 * charstr.length + 1]; int index = 0; for (int i = 0; i < res.length; i++) { // 如果i是偶数，下标从0开始，那么就赋予#，否则赋予原字符，下标自增 res[i] = (i & 1) == 0 ? '#' : charstr[index++]; } return res; } // 判断字符串中最大回文数 public static int maxLcpsLength(String str) { if (str == null || str.length() == 0) { return 0; } char[] charArr = manacherString(str); // 每个位置对应的回文半径 int[] pArr = new int[charArr.length]; // 初始值为-1 int R = -1; // 最大回文中心 int C = -1; // 初始化最大值 int max = Integer.MIN_VALUE; for (int i = 0; i < charArr.length; i++) { // 如果i在R内的情况下，当前对应C对称的位置的回文长度与半径和i的位置回文长度相比，小的赋予给这个位置的半径，否则就是他本身1。 pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1; // 如果R小于i或者R与i正好相等的时候，就会进入循环，剩下两种情况会直接break while (i + pArr[i] < charArr.length && i - pArr[i] > -1) { // 左右是否相等，相等则++ if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) { pArr[i]++; } else { break; } } // 如果范围已经超过R，那么R就是现在的范围，i就是中心C if (i + pArr[i] > R) { R = i + pArr[i]; C = i; } // 判断之前的max与最大回文半径哪个更大 max = Math.max(max, pArr[i]); } // 本身的半径值就是原字符串的回文长度，且要减去最边上的# return max - 1; } public static void main(String[] args) { String str = "abbbcdbbba"; System.out.println(maxLcpsLength(str)); }用来解决类似荷兰国旗的问题，求第k个大小的数，以前的方式可以进行快排或者堆排，可以得到结果，但是时间复杂度是O(NlogN)，为了加快优化，就这可以使用这个思想，也就是快排时随机选取的点，用更加合理的方式选择，使整个过程时间复杂度为O(N)。
1.先将数组分成以5个为一个组的数组
2.将每个5个内进行排序，并选取其中的中位数
3.再将所有的中位数拿出，选择这里的中位数组中的中位数
4.最后就以这个取得的数为基准数，进行筛选，那么所筛选出的区域就是我们要选择的区域
比如：选择到了6，要求第8个小的数，比6小的有50个，6相等的有10个，比6大的有90个，那么我们只需在比6小的50个范围中继续递归选取然后筛选得到第8个即可。
代码实现如下：
// 取得第K的数 public static int getMinKthByBFPRT(int[] arr, int k) { // 复制数组，保留原数组 int[] copyarr = copyArray(arr); // 调用bfprt方法 return bfprt(copyarr, 0, copyarr.length - 1, k - 1); } public static int[] copyArray(int[] arr) { int[] res = new int[arr.length]; for (int i = 0; i < res.length; i++) { res[i] = arr[i]; } return res; } // bfprt方法，得到第i下标的数 public static int bfprt(int[] arr, int begin, int end, int i) { // 如果相等，表示只有一个数，直接返回 if (begin == end) { return arr[begin]; } // 取得中位数数组中的中位数 int pivot = midianOfMedians(arr, begin, end); // 将得到的中位数为基准数进行筛选 int[] pivotRange = patition(arr, begin, end, pivot); // 如果筛选的相等范围里有i，那么直接返回这个值 if (i >= pivotRange[0] && i <= pivotRange[1]) { return arr[i]; // 如果小于左边界，那么就递归调用左边区域再次进行判断 } else if (i < pivotRange[0]) { return bfprt(arr, begin, pivotRange[0] - 1, i); // 如果大于右边界，那么就递归调用右边区域再次进行判断 } else { return bfprt(arr, pivotRange[1] + 1, end, i); } } // 返回中位数数组的中位数 public static int midianOfMedians(int[] arr, int begin, int end) { // 得到要切分的中位数数组长度 int num = end - begin + 1; // 如果不被5整除，那么剩下的为一组，所以长度加一 int offset = num % 5 == 0 ? 0 :1; int[] mArr = new int[num / 5 + offset]; for (int i = 0; i < mArr.length; i++) { // 开始的位置 int beginI = begin + i * 5; // 结束的位置 int endI = beginI + 4; // 得到这个这个区域的中位数，返回给中位数数组，因为末尾有可能不是完整的，所以endI可能会越界，所以取end和endI的最小值 mArr[i] = getMedian(arr, beginI, Math.min(end, endI)); } // 得到中位数数组后，调用bfprt得到中位数数组的中位数，也就是第mArr的长度的一半的数 return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2); } // 获取中位数 public static int getMedian(int[] arr, int begin, int end) { // 调用插入排序，因为最多只有5个进行排序 insertSort(arr, begin, end); // 排序后获得他们的mid位置 int sum = end + begin; int mid = (sum / 2) + (sum % 2); // 返回中位数 return arr[mid]; } // 插入排序 public static void insertSort(int[] arr, int begin, int end) { for (int i = begin + 1; i != end + 1 ; i++) { for (int j = i; j != begin ; j--) { if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); } else { break; } } } } // 筛选，以基准数进行判断 public static int[] patition(int[] arr, int begin, int end, int pivotValue) { int small = begin - 1; int cur = begin; int big = end + 1; while (cur != big) { if (arr[cur] < pivotValue) { swap(arr, ++small, cur++); } else if (arr[cur] > pivotValue) { swap(arr, cur, --big); } else { cur++; } } // 将相等的两个边界返回 int[] range = new int[2]; range[0] = small + 1; range[1] = big - 1; return range; } public static void swap(int[] chs, int i, int j) { int tmp = chs[i]; chs[i] = chs[j]; chs[j] = tmp; } public static void main(String[] args) { int[] arr = {3,2,3,8,5,6,120,8}; System.out.println(getMinKthByBFPRT(arr, 1)); }窗口的数据结构为右边界往前推移，左边界也往前推移，都不能后退，只要左边界不等于右边界就可以形成窗口，窗口右两个特性，最大值特性，利用的是双端队列结构，也就是每次右边界推进时，与双端队列中的最后一个数进行比较，如果比最后的数大或相等，那么就将最后一个数弹出，继续比较，保留下标，左边界向前推移时，要判断双端队列的最大值的下标与左边界推移的下标相比是否过期，如果过期了，那么就将这个最大值弹出。
代码实现如下：
// 取得窗口最大值数组 public static int[] getMaxWindow(int[] arr, int w) { if (arr == null || w < 1 || arr.length < w) { return null; } // LinkedList就是双端队列 LinkedList<Integer> res = new LinkedList<>(); // 要返回的数组 int[] resultMax = new int[arr.length - w + 1]; // resultMax的下标 int index = 0; for (int i = 0; i < arr.length; i++) { // 如果res里不为空，且最后的值小于i的值，那么就弹出最后的值 while (!res.isEmpty() && arr[res.peekLast()] <= arr[i]) { res.pollLast(); } // 弹出后将新值放入到队列中 res.addLast(i); // 如果最大值的下标等于现在窗口到达的右边界位置，那么就弹出目前的最大值 if (res.peekFirst() == i - w) { res.pollFirst(); } // 如果i已经大于等于窗口大小 - 1，意味着已经形成了窗口，那么就把现在最大位置的值记录到返回的数组中 if (i >= w - 1) { resultMax[index++] = arr[res.peekFirst()]; } } return resultMax; } public static void main(String[] args) { int[] arr = {4,2,9,4,10,120,7}; int[] res = getMaxWindow(arr, 3); for (int i = 0; i < res.length; i++) { System.out.print(res[i] + " "); } }给定数组arr和整数num，返回每个arr子数组最大值-最小值小于等于num时的数量，要求时间复杂度为O(N)的解法，思路：如果暴力解法会用到O(N³)的复杂度，我们可以利用上面的窗口结构，使用两个双端队列分别得到最大值和最小值，然后依次推进，如果右边界推进到了比num大的时候停，那么整个区域的子数组都可以满足要求，max值不可能更大，min值不可能更小，那么一定满足max-min<=num。然后左边界向前推移，右边界继续向右推进判断，最后得到结果，代码实现如下：
// 返回arr子数组最大值-最小值小于等于num的数量 public static int getNum(int[] arr, int num) { if (arr == null || arr.length == 0) { return 0; } // 创建最大值和最小值的双端队列 LinkedList<Integer> queMax = new LinkedList<>(); LinkedList<Integer> queMin = new LinkedList<>(); int L = 0; int R = 0; int result = 0; // 窗口指针进行推移 while (L < arr.length) { while (R < arr.length) { // 分别存入最大值和最小值 while (!queMax.isEmpty() && arr[queMax.peekLast()] <= arr[R]) { queMax.pollLast(); } queMax.addLast(R); while (!queMin.isEmpty() && arr[queMin.peekLast()] >= arr[R]) { queMin.pollLast(); } queMin.addLast(R); // 如果出现大于num的情况，那么就跳出循环，否则R++ if (arr[queMax.peekFirst()] - arr[queMin.peekFirst()] > num) { break; } R++; } // L推进，所以将最大值和最小值的双端队列进行更新 if (queMax.peekFirst() == L) { queMax.pollFirst(); } if (queMin.peekFirst() == L) { queMin.pollFirst(); } result += R - L; // L推进，如果R没有推进的情况下，那么R就要等于L L++; R = Math.max(R, L); } return result; } public static void main(String[] args) { int[] arr = {1,2,3,4,5,6,7,8}; System.out.println(getNum(arr, -1)); }找到数组中，每一个数对应的左边最近比它大的或小的数和右边最近比它大的或小的数，栈中按照顺序排，如果下一个位置的值大于栈顶，那么就弹出这个值，那么这个值的右边的值就是比较的值，左边的值就是现在新的栈顶的值。
给定一个矩阵，其中只有0和1，那么全是1的矩形最大的数量，1 1 1 0，那么矩形区域为3，如果
1 0 1 0
1 1 1 1
1 1 1 0
那么矩形区域就是6。
思路：可以每层递加得到的层数，利用单调栈进行判断，查看左右边界。代码实现如下：
// 返回最大矩形的1 public static int maxRecSize(int[][] map) { if (map == null || map.length == 0 || map[0].length == 0) { return 0; } int max = 0; int[] height = new int[map[0].length]; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { // 将每次循环的高度累加 height[j] = map[i][j] == 1 ? height[j] + 1 : 0; } // 从高度数组中得到最大值 max = Math.max(max, maxRecFromBottom(height)); } return max; } // 递增层级的最大矩形 public static int maxRecFromBottom(int[] height) { if (height == null || height.length == 0) { return 0; } int maxArea = 0; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < height.length; i++) { // 单调栈按照从下到上由小到大的方式排列 while (!stack.isEmpty() && height[stack.peek()] >= height[i]) { // 得到栈顶 int j = stack.pop(); // 得到左边界 int k = stack.isEmpty() ? -1 : stack.peek(); // 取得矩形的大小 int curArea = (i - k - 1) * height[j]; // 获得最大值 maxArea = Math.max(maxArea, curArea); } stack.push(i); } // 剩下的值就是右边界没有限制到 while (!stack.isEmpty()) { int j = stack.pop(); int k = stack.isEmpty() ? -1 : stack.peek(); int curArea = (height.length - k - 1) * height[j]; maxArea = Math.max(maxArea, curArea); } return maxArea; } public static void main(String[] args) { int[][] map = { {1,1,1,1,1}, /*{1,1,0,1}, {1,1,1,0}, {1,1,1,0}*/}; System.out.println(maxRecSize(map)); }给定一个环形数组，每个位置之间可以看到，并且可以看到路径上的值不大于两个值中最小的值，比如[1,2,3,3,7]，2能看到3，也能看到1，也可以通过1这条路径看到7，因为路径上没有大于2的数。求得到的对数。
思路：如果数组没有相同的，那么直接2 * n - 3就可以得到答案，如果有相同的，那么就要利用单调栈来解决这个问题，先找到这个数组的最大值，放入栈中，那么之后的每个数都不可能比它大，那么左边界就可以确定，然后按照从下到上由大到小放入，找到第一个比它大的数，那么它一定有两个可以看到的对数，下一个栈顶和现在比它大的数，这两个边界，如果有相同的就把次数自增，那么相同数之间是可以看到的，通过C²n可以得到，再加上每个数都有两个边界能看到，也就是2 * n，所以弹出时对数为：C²n + 2 * n。如果都判断完之后，栈中的元素，如果还剩下2个以上，那么这两个必然就是两个边界，也是如上的对数，如果是倒数第二个，那么就要看最后一个的次数，如果是2个以上，那么就表明有两个边界，否则就一个边界，就只加1次的n，最后一个就只有互相可以看到，那么就是C²n。
代码实现如下：
// 存放对象为值得大小和次数 public static class Pair{ public int value; public int times; public Pair(int value) { this.value = value; this.times = 1; } } // 获得下一个index位置 public static int getNextIndex(int[] arr, int now) { return now < arr.length - 1 ? now + 1 : 0; } // 获得数组中最大值得index public static int getMaxArrIndex(int[] arr) { int max = 0; for (int i = 0; i < arr.length; i++) { max = arr[max] < arr[i] ? i : max; } return max; } // 或者这个大小得C2组合的值 public static long getCSum(int num) { return num * (num - 1) / 2L; } // 可看到的对数 public static long communications(int[] arr) { if (arr == null || arr.length < 2) { return 0; } // 先将最大值的下标取得，并将最大值放入到栈中 int maxIndex = getMaxArrIndex(arr); Stack<Pair> stack = new Stack<>(); stack.push(new Pair(arr[maxIndex])); long result = 0; // 将下一个下标取得开始循环 int index = getNextIndex(arr, maxIndex); // 当回到最大值的位置时，停止 while (index != maxIndex) { // 如果栈中的值小于这个位置的值，那么就弹出，得到对应次数的对数 while (!stack.isEmpty() && stack.peek().value < arr[index]) { int times = stack.pop().times; result += getCSum(times) + 2 * times; } // 如果下一个值与这个值相等，那么次数相加，否则新加入 if (!stack.isEmpty() && stack.peek().value == arr[index]) { stack.peek().times++; } else { stack.push(new Pair(arr[index])); } index = getNextIndex(arr, index); } // 将还没有弹出的位置对应的对数取得 while (!stack.isEmpty()) { // 获得次数 int times = stack.pop().times; // 不管是最后一个还是倒数第二个还是其他的，都一定会有C组合的对数 result += getCSum(times); // 判断取出的是否为最后一个 if (!stack.isEmpty()) { // 不是的话至少有一对 result += times; // 如果本次不是倒数第二次，那么就就在加一对 if (stack.size() > 1) { result += times; // 如果是倒数第二次，就要查看最后一个的次数 } else { result += stack.peek().times > 1 ? times : 0; } } } return result; } public static void main(String[] args) { int[] arr = {5,6,5,5,4,4,7,6}; System.out.println(communications(arr)); }morris遍历相当于手写版的递归，只不过递归每次会回到自己三次，而morris遍历只回到自己两次，递归是通过行号记录，morris是通过左子树的最右节点的指向来判断，如果左子树的最右节点的right为null，那么就让right指向自己，然后自己指向自己的左节点，继续循环这个过程，当下一次判断到最右节点的right不为null时，那么就还原成null，表示自己的左子树的最右节点已经到达过一次那么自己就指向自己的右节点，反复上面的过程，每次相当于回到自己两次，如果没有左子树就是一次，所以就可以利用这个特点进行遍历。时间复杂度为O(N)，空间复杂度O(1)。
代码实现如下：
public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } // morris前序遍历 public static void morrisPre(Node head) { if (head == null) { return; } Node cur = head; Node mostRight; while (cur != null) { // 每次取得左子树的最右节点 mostRight = cur.left; // 如果左子树不为空 if (mostRight != null) { // 循环得到最右点 while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } // 如果第一次到达，那么就将最右点的右节点指向现在的cur节点 if (mostRight.right == null) { // 这时已经找到了自己的最右节点，那么可以先输出自己了 System.out.print(cur.value + " "); mostRight.right = cur; // 然后cur指向自己的左节点，继续循环得到 cur = cur.left; continue; } else { // 是第二次来到，那么将右节点再回null mostRight.right = null; } // 这时候发现没有左子树，那么不会第二次回到自己的位置，那么先输出自己 } else { System.out.println(cur.value + " "); } // 左子树已经全部得到，指向右子树 cur = cur.right; } } // morris中序遍历 public static void morrisIn(Node head) { if (head == null) { return; } Node cur = head; Node mostRight; while (cur != null) { mostRight = cur.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.right = cur; cur = cur.left; continue; } else { mostRight.right = null; } } // 其他与先序一样，只不过输出的位置不同，找到自己的最左节点，进行输出 System.out.print(cur.value + " "); cur = cur.right; } } // morris后序遍历 public static void morrisPos(Node head) { if (head == null) { return; } Node cur = head; Node mostRight; while (cur != null) { mostRight = cur.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.right = cur; cur = cur.left; continue; } else { mostRight.right = null; // 在第二次找到自己的节点时，所有的右边界逆序输出 printEdge(cur.left); } } cur = cur.right; } // 将主节点的右边界也逆序进行输出 printEdge(head); } // 右边界逆序输出 public static void printEdge(Node head) { // 先将右边界进行指针反转，得到末尾 Node tail = reversRight(head); Node cur = tail; // 之后将末尾逆序输出 while (tail != null) { System.out.print(tail.value + " "); tail = tail.right; } // 再还原 reversRight(cur); } // 反转右子树边界 public static Node reversRight(Node head) { if (head == null) { return null; } Node nextNode; Node lastNode = null; while (head != null) { nextNode = head.right; head.right = lastNode; lastNode = head; head = nextNode; } return lastNode; } public static void main(String[] args) { Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); morrisPre(head); }水平面上有 N 座大楼，每座大楼都是矩阵的形状，可以用一个三元组表示 (start, end, height)，分别代表其在x轴上的起点，终点和高度。大楼之间从远处看可能会重叠，求出 N 座大楼的外轮廓线。
外轮廓线的表示方法为若干三元组，每个三元组包含三个数字 (start, end, height)，代表这段轮廓的起始位置，终止位置和高度。
思路：根据每个位置的最高高度，和上升下降的时候的位置，可以画出轮廓来，代码实现为：
// 先创建一个类，类中的信息为：上下，位置喝高度 public static class Node { public boolean isUp; public int position; public int h; public Node(boolean isUp, int position, int h) { this.isUp = isUp; this.position = position; this.h = h; } } // 做比较器 public static class BuildingConparator implements Comparator<Node> { @Override public int compare(Node o1, Node o2) { // 位置不同，前的位置在前面 if (o1.position != o2.position) { return o1.position - o2.position; } // 上的位置在前面 if (o1.isUp != o2.isUp) { return o1.isUp ? -1 : 1; } // 如果在一个位置，且上下也一样，那么就表示一样 return 0; } } // 返回建筑外围 public static List<List<Integer>> buildingOutLine(int[][] building) { // 定义Node数组，大小为building的两倍 Node[] nodes = new Node[2 * building.length]; // 偶数为起始位置和高度，且表示上，奇数为结束为止和高度，表示下 for (int i = 0; i < building.length; i++) { nodes[2 * i] = new Node(true, building[i][0], building[i][2]); nodes[2 * i + 1] = new Node(false, building[i][1], building[i][2]); } // 对数组进行排序 Arrays.sort(nodes, new BuildingConparator()); // 创建两个红黑树 TreeMap<Integer, Integer> hMap = new TreeMap<>(); TreeMap<Integer, Integer> pMap = new TreeMap<>(); for (int i = 0; i < nodes.length; i++) { // 如果是上 if (nodes[i].isUp) { // hmap中包括的话就添加进去，如果已经有了，那么次数 + 1 if (!hMap.containsKey(nodes[i].h)) { hMap.put(nodes[i].h, 1); } else { hMap.put(nodes[i].h, hMap.get(nodes[i].h) + 1); } // 如果是下 } else { // 次数为1，直接删除 if (hMap.get(nodes[i].h) == 1) { hMap.remove(nodes[i].h); } else { // 否则次数 - 1 hMap.put(nodes[i].h, hMap.get(nodes[i].h) - 1); } } // pMap记录每个为止的最高高度 if (hMap.isEmpty()) { pMap.put(nodes[i].position, 0); } else { pMap.put(nodes[i].position, hMap.lastKey()); } } // 高度和起始位置 int high = 0; int start = 0; List<List<Integer>> result = new ArrayList<>(); for (Integer i : pMap.keySet()) { // 当前位置 int curPosition = i; // 最高高度 int mostHigh = pMap.get(i); // 如果高度和最高高度不同，那么就需要更新 if (high != mostHigh) { // 高度为0表示还没有形成轮廓 if (high != 0) { List<Integer> list = new ArrayList<>(); list.add(start); list.add(curPosition); list.add(high); result.add(list); } // 更新高度和起始位置 high = mostHigh; start = curPosition; } } return result; }