常见数据结构和算法

本文最后更新于：1 年前

[TOC]

常见数据结构

根据数据访问的特点，可分为线性数据结构和非线性数据结构。

线性结构：数组、链表、栈、队列等。

非线性结构：散列表、树、堆、图等。

数组

最基本最常见的数据结构。数组一般用来存储相同类型的数据，可通过数组名和下标进行数据的访问和更新。

数组中元素的存储是按照先后顺序进行的，同时在内存中也是按照这个顺序进行连续存放。

数组相邻元素之间的内存地址的间隔一般就是数组数据类型的大小。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比与线性数据表结构，操作复杂。

由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而线性表和顺序表相应的时间复杂度分别是 O(logn)和 O(1)。

链表相较于数组，除了数据域，还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问，使得链表的自由度更高。

这表现在对节点进行增加和删除时，只需要对上一节点的指针地址进行修改，而无需变动其它的节点。不过事物皆有两极，指针带来高自由度的同时，自然会牺牲数据查找的效率和多余空间的使用。

一般常见的是有头有尾的单链表，对指针域进行反向链接，还可以形成双向链表或者循环链表。

跳表

跳表也叫跳跃表，是一种动态的数据结构。如果我们需要在有序链表中进行查找某个值，需要遍历整个链表，二分查找对链表不支持，二分查找的底层要求为数组，遍历整个链表的时间复杂度为 O(n)。

我们可以把链表改造成 B 树、红黑树、AVL 树等数据结构来提升查询效率，但是 B 树、红黑树、AVL 树这些数据结构实现起来非常复杂，里面的细节也比较多。

跳表就是为了提升有序链表的查询速度产生的一种动态数据结构，跳表相对 B 树、红黑树、AVL 树这些数据结构实现起来比较简单，但时间复杂度与 B 树、红黑树、AVL 树这些数据结构不相上下，时间复杂度能够达到 O(logn)。

跳表一般使用单链表来实现，这样比较节约空间。我使用双向链表来实现跳表，因为双向链表相对单向链表来说比较容易理解跳表的实现。

跳表的性质：

由很多层结构组成
每一层都是一个有序的链表
最底层(Level 1)的链表包含所有元素
如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
从上面的对比中可以看出，链表虽然通过增加指针域提升了自由度，但是却导致数据的查询效率恶化。特别是当链表长度很长的时候，对数据的查询还得从头依次查询，这样的效率会更低。跳表的产生就是为了解决链表过长的问题，通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从 O(n)提升至 O(logn)。

栈和队列

树

在二叉树的概念下又衍生出满二叉树和完全二叉树的概念

完全二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上（除了最后一层结点，其它层的结点数都达到了最大值；同时最后一层的结点都是按照从左到右依次排布。

满二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边（除了最后一层，其它层的结点都有两个子结点）。

平衡二叉树

平衡二叉树又被称为 AVL 树，它是一棵二叉排序树，且具有以下性质：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树

二叉排序树：是一棵空树，或者：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉排序树。

树的高度：结点层次的最大值。

二叉排序树意味着二叉树中的数据是排好序的，顺序为左结点<根节点<右结点，这表明二叉排序树的中序遍历结果是有序的。

平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序，当插入一个有序程度十分高的序列时，生成的二叉排序树会持续在某个方向的字数上插入数据，导致最终的二叉排序树会退化为链表，从而使得二叉树的查询和插入效率恶化。

二叉树的遍历方式

先序遍历：先根节点->遍历左子树->遍历右子树

中序遍历：遍历左子树->根节点->遍历右子树

后序遍历：遍历左子树->遍历右子树->根节点

深度优先搜索（DFS）与广度优先搜索（BFS）

实现：

bfs＝队列，入队列，出队列一次访问一条路径；

queue.add(root);
   while (!queue.isEmpty()){
       int size=queue.size();
       List<Integer> temp=new ArrayList<>();
       for (int i = 0; i < size; i++) {
           TreeNode poll = queue.poll();
           temp.add(poll.val);
           if (poll.left!=null)queue.offer(poll.left);
           if (poll.right!=null)queue.offer(poll.right);
       }
       res.add(temp);
   }

dfs=栈，压栈，出栈一次访问多条路径；

//递归
public static void helper(TreeNode root,List<Integer>res) {
    if (root == null) return;
    res.add(root.val);
    helper(root.left,res);
    helper(root.right,res);
}

前序遍历是中左右，每次先处理的是中间节点，那么先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。这样出栈的时候才是中左右的顺序。

st.push(root);
   while (!st.isEmpty()) {
       TreeNode node = st.pop();                       // 中 
       result.add(node->val);
       if (node.right) st.push(node.right);           // 右（空节点不入栈）
       if (node.left) st.push(node.left);             // 左（空节点不入栈）
   }

因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进 result 数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

TreeNode cur = root;
     while (cur != NULL || !st.isEmpty()) {
         if (cur != NULL) { // 指针来访问节点，访问到最底层
             st.push(cur); // 将访问的节点放进栈
             cur = cur.left;                // 左
         } else {
             cur = st.pop(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
             result.add(cur.val);     // 中
             cur = cur.right;               // 右
         }
     }
     return result;

2 3

4 5 6 7

1-2-4

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转 result 数组，输出的结果顺序就是左右中了。

关系：

用 DFS 解决的问题都可以用 BFS 解决。DFS 易于编写（递归），时间消耗较少但是容易发生爆栈，而 BFS 可以控制队列的长度。

红黑树

平衡二叉树（AVL）为了追求高度平衡，需要通过平衡处理使得左右子树的高度差必须小于等于 1。高度平衡带来的好处是能够提供更高的搜索效率，其最坏的查找时间复杂度都是 O(logN)。但是由于需要维持这份高度平衡，所付出的代价就是当对树种结点进行插入和删除时，需要经过多次旋转实现复衡。这导致 AVL 的插入和删除效率并不高。

为了解决这样的问题，能不能找一种结构能够兼顾搜索和插入删除的效率呢？红黑树可以解决。

红黑树具有五个特性：

每个结点要么是红的要么是黑的。
根结点是黑的。
每个叶结点（叶结点即指树尾端 NIL 指针或 NULL 结点）都是黑的。
如果一个结点是红的，那么它的两个儿子都是黑的。
对于任意结点而言，其到叶结点树尾端 NIL 指针的每条路径都包含相同数目的黑结点。

红黑树通过将结点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低。红黑树不追求完全平衡，只要求达到部分平衡。这是一种折中的方案，大大提高了结点删除和插入的效率。

散列表（hash 表）

散列表也叫哈希表，是一种通过键值对直接访问数据的机构。

散列表的实现原理正是映射的原理，通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现 O(1)的数据访问效率。在映射的过程中，事先设定的函数就是一个映射表，也可以称作散列函数或者哈希函数。

确定好散列函数之后，通过某个 key 值的确会得到一个唯一的 value 地址。但是却会出现一些特殊情况。即通过不同的 key 值可能会访问到同一个地址，这个现象称之为冲突。

冲突在发生之后，当在对不同的 key 值进行操作时会使得造成相同地址的数据发生覆盖或者丢失，是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。

hash 冲突：

开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对 Key 哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。

再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。

链地址法：链地址法其实就是对 Key 通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的。

公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。目前比较常用的冲突解决方法是链地址法，一般可以通过数组和链表的结合达到冲突数据缓存的目的。

考虑到链表过长造成的问题，还可以使用红黑树替换链表进行冲突数据的处理操作，来提高散列表的查询稳定性。

B 树

B 树是一种多路搜索树，它的每个节点可以拥有多于两个孩子节点。M 路的 B 树最多拥有 M 个孩子节点。

文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中

如果一棵树都无法一次性加载进内存，该怎么查找呢？

B 树的多路存储的威力就在于此，可以每次加载 B 树的一个节点，然后，一步步往下找。

查找时候，每次载入一个节点进内存就行，如果在内存中，红黑树比 B 树效率更高，但是涉及到磁盘操作，B 树就更优了。

B+树是在 B 树基础上进行改造的，它的数据都在叶子节点，同时叶子节点之间还加了指针形成链表。

B+树在数据库的索引中用的比较多，如果数据库 select 数据，不一定只选一条，很多时候选多条，比如按照 id 排序后选 10 条。

这样如果是多条的话，B 树需要做局部的中序遍历，可能需要跨层访问，而 B+树由于所有数据都在叶子节点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。

存储密度：顺序存储结构是一个一个挨着，基本上是一个空间对应一个数据；而链式存储由于每个结点都含有指针区域，故存储空间占用比较大，存储密度也就相对来说比较少。

排序

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它是不稳定排序。

堆的性质
① 是一棵完全二叉树
② 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。

一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了

a.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

public static void main(String[] args) {
       int[] nums = {4, 10, 3, 6, 1, 2};
       heapsort(nums, nums.length);
       System.out.println(Arrays.toString(nums));
   }

   public static void heapsort(int[] tree, int n) {
       build_heap(tree, n);
       for (int i = n - 1; i >= 0; i--) {
           swap(tree, i, 0);
           heapify(tree, i, 0);
       }
   }

   public static void build_heap(int[] nums, int n) {
       int last = n - 1;
       int par = (last - 1) / 2;
       for (int j = par; j >= 0; j--) {
           heapify(nums, n, j);
       }
   }

   public static void heapify(int[] nums, int n, int i) {
       if (i >= n) return;
       int c1 = 2 * i + 1;
       int c2 = 2 * i + 2;
       int max = i;
       if (c1 < n && nums[c1] > nums[max]) {
           max = c1;
       }
       if (c2 < n && nums[c2] > nums[max]) {
           max = c2;
       }
       if (max != i) {
           swap(nums, i, max);
           heapify(nums, n, max);
       }
   }

时间复杂度

一.初始化建堆
　　初始化建堆只需要对二叉树的非叶子节点调用 build_heap()函数，由下至上，由右至左选取非叶子节点来调用函数。那么倒数第二层的最右边的非叶子节点就是最后一个非叶子结点。
　　假设高度为 k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。
　　那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要下调比较的次数。
　　S = 2^(k-2) * 1 + 2^(k-3)2……..+2(k-2)+2^(0)*(k-1) ===> 因为叶子层不用交换，所以 i 从 k-1 开始到 1；
　　S = 2^k -k -1；又因为 k 为完全二叉树的深度，而 log(n) =k，把此式带入；
　　得到：S = n - log(n) -1，所以时间复杂度为：O(n)

二.排序重建堆
　　在取出堆顶点放到对应位置并把原堆的最后一个节点填充到堆顶点之后，需要对堆进行重建，只需要对堆的顶点调用 heapify()函数。
　　每次重建意味着有一个节点出堆，所以需要将堆的容量减一。重建堆一共需要 n-1 次循环，每次循环的比较次数为 log(i)，则相加为：log2+log3+……+log(n-1)+log(n)≈log(n!)。可以证明 log(n!)和 nlog(n)是同阶函数：
∵(n/2)^n/2≤n!≤n^n,∵(n/2)^n/2≤n!≤n^n,
∴n/4log(n)=n/2log(n1/2)≤n/2log(n/2)≤log(n!)≤nlog(n)∴n/4log⁡(n)=n/2log⁡(n1/2)≤n/2log⁡(n/2)≤log⁡(n!)≤nlog⁡(n)
　　所以时间复杂度为 O(nlogn)

　　初始化建堆的时间复杂度为 O(n)，排序重建堆的时间复杂度为 nlog(n)，所以总的时间复杂度为**O(n+nlogn)=O(nlogn)**。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。

快排

选取基准值，左边小于其，右边大于其。左右子序列重复此过程。
大量数据时表现良好。
数据越乱表现越好。数据接近有序是退化成冒泡排序。
一种不稳定的排序方式。
也是一种交换排序。

public static int[] sort(int[] nums) {
    quicksort(nums, 0, nums.length - 1);
    return nums;
}

private static void quicksort(int[] nums, int left, int right) {
    if (left >= right) return;
    int pindex = partition(nums, left, right);
    quicksort(nums, left, pindex - 1);
    quicksort(nums, pindex + 1, right);
}

private static int partition(int[] nums, int left, int right) {
    Random r = new Random();
    int rindex = left + r.nextInt(right - left + 1);
    swap(nums, rindex, left);

    int pivot = nums[left];
    int l = left;
    for (int i = left + 1; i <= right; i++) {
        if (nums[i] < pivot) {
            l++;
            swap(nums, i, l);
        }
    }
    swap(nums, left, l);
    return l;
}

选择排序

每次都选择最大（最小）的元素放在最前面，依次往后。
堆排序亦是选择排序：利用堆来选择数据。时间复杂度降低。

for (int i = 0; i < len; i++) {
    int min = i;
    for (int j = i + 1; j < len; j++) {
        if (nums[j] < nums[min]) {
            min = j;
        }
    }
    swap(nums, min, i);
}

插入排序

始终维持一个有序的队列。

元素越接近于稳定时，效率越高。
稳定的排序方式。
希尔排序是对直接插入排序的优化。

for (int i = 1; i < len; i++) {//第一个数有序
    int temp=nums[i];
    int j=i;
    while (j>0&&nums[j-1]>temp){
        nums[j]=nums[j-1];
        j--;
    }
    nums[j]=temp;
}

冒泡排序

比较相邻两个值的大小，出现逆序就交换。
稳定的排序。
慢：每次只能移动相邻的两个数据。
一种交换排序。

for (int i = 0; i < len; i++) {//扫苗多少趟
    for (int j = 0; j < len-1; j++) {
        if (nums[j] > nums[j + 1]) {
            swap(nums, j, j + 1);
        }
    }
}

归并排序

分治法的应用。
合并有序的子序列。
o(n)的空间复杂度。更多考虑解决磁盘外部排序的问题。

public static int[] sort(int[] nums){
    int[] temp=new int[nums.length];
    mergesort(nums,0,nums.length-1,temp);
    return nums;
}

private static void mergesort(int[] nums, int left, int right, int[] temp) {
    if (left>=right)return;
    int mid=left+(right-left)>>1;
    mergesort(nums, left,mid,temp);
    mergesort(nums,mid+1,right,temp);
    //数组有序，不用merge
    if (nums[mid]<=nums[mid+1]){
        return;
    }
    merge(nums,left,mid,right,temp);
}

private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
    //System.arraycopy(nums,left,temp,left,right-left+1);
    for (int i = left; i <= right; i++) {
        temp[i]=nums[i];
    }
    //左右两半的起点
    int i=left;
    int j=mid+1;
    for (int k = left; k <= right; k++) {
        if (i==mid+1)nums[k]=temp[j++];
        else if (j==right+1)nums[k]=temp[i++];
        else if (temp[i]<=temp[j])nums[k]=temp[i++];
        else nums[k]=temp[j++];
    }
}

比较

稳定性：相同数值的元素经过排序以后，相对的位置保持不变。
内部排序：数据全部放在内存中。
外部排序：内存装不下

二叉树

二叉树遍历

深度优先便利–广度优先遍历

前序：preorder 根-左-右

中序：inorder 左-根-右

后序：postorder 左-右-根

层序：levelorder

前序遍历
递归
迭代
中序遍历
递归
迭代
后序遍历
递归
迭代

递归

//递归版本
public static List<Integer> preorder2(TreeNode root){
    List<Integer> res = new ArrayList<>();
    helper(root,res);
    return res;
}
public static void helper(TreeNode root,List<Integer>res) {
    if (root == null) return;
    res.add(root.val);
    helper(root.left,res);
    helper(root.right,res);
}

public static void preorder(TreeNode root){
    if (root==null)return;
    System.out.print(root.val+" ");
    preorder(root.left);
    preorder(root.right);
}
//迭代统一写法
public static List<Integer> preorder3(TreeNode root){
    List<Integer> res=new ArrayList<>();
    if (root==null)return res;
    Stack<TreeNode> stack=new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()){
        TreeNode top = stack.peek();
        if (top!=null){
            stack.pop();
            if (top.right!=null)stack.push(top.right);
            if (top.left!=null)stack.push(top.left);
            stack.push(top);
            stack.push(null);
        }else{
            stack.pop();
            TreeNode pop = stack.pop();
            res.add(pop.val);
        }
    }
    return res;
}

层序遍历

public static List<List<Integer>> levelorder(TreeNode root){
    if (root==null)return null;
    List<List<Integer>>res=new ArrayList<>();
    LinkedList<TreeNode> queue=new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        int size=queue.size();
        List<Integer> temp=new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            temp.add(poll.val);
            if (poll.left!=null)queue.offer(poll.left);
            if (poll.right!=null)queue.offer(poll.right);
        }
        res.add(temp);
    }
    return res;
}

右视图-只需要判断一下是否是最后一个。

 for (int i = 0; i < size; i++) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
    if (i == size - 1)  //将当前层的最后一个节点放入结果列表
        res.add(node.val);
}

n 叉数层序遍历

public static List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> res = new ArrayList<>();
    Deque<Node> que = new LinkedList<>();
    if (root == null) return res;
    que.offer(root);
    while (!que.isEmpty()) {
        int size = que.size();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node poll = que.poll();
            temp.add(poll.val);

            List<Node> children = poll.children;
            if (children == null || children.size() == 0) {
                continue;
            }
            for (Node child : children) {
                if (child != null) que.offer(child);
            }
        }
        res.add(temp);
    }
    return res;
}

class Node {
    public int val;
    public List<Node> children;
    public Node() {
    }
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

锯齿形层序遍历

/**
 * z字形遍历-偶数层倒序遍历
 * @param root
 * @return
 */
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 该层的节点数量
        int size = queue.size();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 根据层次来判断顺序
            if (result.size() % 2 == 0) {
                temp.add(node.val);
            } else {
                temp.add(0, node.val);//插到最前面
            }
            if (node.left != null) queue.add(node.left);
            if (node.right != null)queue.add(node.right);
        }
        result.add(temp);
    }
    return result;
}

理解使用队列进行层序遍历的本质。
z 字形遍历时，result.size 一开始是 0，第二层时为 1，所以奇数时插到前面。

两节点最近路径

public static List<Integer> findDistance(TreeNode root, TreeNode p, TreeNode q) {
    if (p == q) {
        return new ArrayList<>(p.val);
    }
    List<Integer> res = new ArrayList<>();
    List<TreeNode> list1 = findPath(root, p);
    List<TreeNode> list2 = findPath(root, q);

    //单独考虑在同一条路径的情况
    if (list1.containsAll(list2) || list2.containsAll(list1)) {
        int max = Math.max(list1.size(), list2.size());
        List<TreeNode> llist = list1.size() == max ? list1 : list2;
        List<TreeNode> slist = list1.size() == max ? list2 : list1;
        for (int i = 0; i < slist.size(); i++) {
            System.out.print(slist.get(i).val+" ");
        }
        System.out.println();
        for (int i = 0; i < llist.size(); i++) {
            System.out.print(llist.get(i).val+" ");
        }
        for (int i = slist.size()-1; i < llist.size(); i++) {
            res.add(llist.get(i).val);
        }
    } else {
        //去重
        int lastSame = 0;
        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i) == list2.get(i)) {
                lastSame = i;
            } else {
                break;
            }
        }
        for (int i = list1.size() - 1; i > lastSame; i--) {
            res.add(list1.get(i).val);
        }
        for (int i = lastSame; i < list2.size(); i++) {
            res.add(list2.get(i).val);
        }
    }
    return res;
}

private static List<TreeNode> findPath(TreeNode root, TreeNode node) {
    List<TreeNode> res = new ArrayList<>();
    getPathFromRoot(root, node, res);
    return res;
}

public static boolean getPathFromRoot(TreeNode root, TreeNode node, List<TreeNode> pathArray) {
    if (root == null || node == null) return false;
    pathArray.add(root);
    if (root == node) return true;
    if (root.left != null && getPathFromRoot(root.left, node, pathArray) == true)
        return true;
    if (root.right != null && getPathFromRoot(root.right, node, pathArray) == true)
        return true;
    //回溯
    pathArray.remove(pathArray.size() - 1);
    return false;
}

是平衡二叉树吗？

public static boolean isBalanced(TreeNode root) {
    return getHeight(root) != -1;
}
//返回以该节点为根节点二叉树的深度
private static int getHeight(TreeNode root) {
    if (root==null)return 0;
    int left=getHeight(root.left);
    if (left==-1)return -1;
    int right=getHeight(root.right);
    if (right==-1)return -1;
    if (Math.abs(left-right)>1)return -1;
    return Math.max(left,right)+1;
}

最大路径和？（任意节点出发）
最大深度
前序遍历中序（中序和后序）遍历构造二叉树
路径和等于 target 的路径（根节点出发）
翻转二叉树
根节点到叶子结点的数字之和
对称二叉树？
二叉搜索树？
二叉搜索树第 k 大节点？

第二小的节点（根节点=左右节点较小的值）

public int findSecondMinimumValue(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) return -1;//没有最小节点
    //找出候选数，默认就是子节点值，如果子节点值和root值相同，递归，在子树中寻找候选数
    int left = root.left.val;
    int right = root.right.val;
    if (root.left.val == root.val) left = findSecondMinimumValue(root.left);
    if (root.right.val == root.val) right = findSecondMinimumValue(root.right);
    //如果左右候选数都正常，返回较小值就可
    if (left != -1 && right != -1) {
        return Math.min(left, right);
    }
    //如果候选数有-1，说明整个子树中没有可供候选的数
    if (left != -1) {
        //左子树正常，答案就是左边的候选数
        return left;
    } else {
        //右子树正常，返回答案
        //或者右子树也没有候选数，返回-1，即right
        return right;
    }
}

路径总和

路径总和 3-不限起点

int pathnumber;
public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    Sum(root, sum);
    pathSum(root.left, sum);
    pathSum(root.right, sum);
    return pathnumber;
}


public void Sum(TreeNode root, int sum) {
    if (root == null) return;
    sum -= root.val;
    if (sum == 0) {
        pathnumber++;
    }
    Sum(root.left, sum);
    Sum(root.right, sum);
}

路径总和 2（根节点到叶子节点有无）

public static boolean hasPathSum2(TreeNode root, int sum) {
    if (root == null) return false;
    return traversal(root, sum - root.val);
}

private static boolean traversal(TreeNode cur, int count) {
    if (cur.left == null && cur.right == null && count == 0)return true;
    if (cur.left == null && cur.right == null) return false;
    if (cur.left != null) {
        count = count - cur.left.val;
        if (traversal(cur.left, count)) return true;
        count = count + cur.left.val;
    }
    if (cur.right != null) {
        count = count - cur.right.val;
        if (traversal(cur.right, count)) return true;
        count = count + cur.right.val;//回溯
    }
    return false;
}

public static boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    if (root.left == null && root.right == null && sum == root.val) {
        return true;
    }
    boolean l = hasPathSum(root.left, sum - root.val);
    boolean r = hasPathSum(root.right, sum - root.val);
    return l || r;
}

路径总和（打印上一题的路径）

public static List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(root, sum, 0, new ArrayList<>(), res);
    return res;
}

private static void dfs(TreeNode root, int sum, int total,
                        List<Integer> list, List<List<Integer>> res) {
    if (root == null) return;
    list.add(root.val);
    total = total + root.val;
    if (root.left == null && root.right == null) {
        if (sum == total) {
            res.add(new ArrayList<>(list));
        }
        list.remove(list.size() - 1);
        return;
    }
    dfs(root.left, sum, total, list, res);
    dfs(root.right, sum, total, list, res);
    list.remove(list.size() - 1);
}

路径总和（打印所有路径）

public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<>();
    if (root == null)return res;
    List<Integer> paths = new ArrayList<>();
    traversal(root, paths, res);
    return res;
}

private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
    paths.add(root.val);
    // 叶子结点
    if (root.left == null && root.right == null) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < paths.size() - 1; i++) {
            sb.append(paths.get(i)).append("->");
        }
        sb.append(paths.get(paths.size() - 1));
        res.add(sb.toString());
        return;
    }
    if (root.left != null) {
        traversal(root.left, paths, res);
        paths.remove(paths.size() - 1);// 回溯
    }
    if (root.right != null) {
        traversal(root.right, paths, res);
        paths.remove(paths.size() - 1);// 回溯
    }
}

红黑树

红黑树的本质其实也是对概念模型：2-3-4 树的一种实现。

2-3-4 树是阶数为 4 的 B 树，B 树，全名 BalanceTree，平衡树。这种结构主要用来做查找。

红黑树也是二叉查找树，它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

性质 1：每个节点要么是黑色，要么是红色。
性质 2：根节点是黑色。
性质 3：每个叶子节点（NIL）是黑色。
性质 4：每个红色结点的两个子结点一定都是黑色。
性质 5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

堆

双堆找中位数：

如果一个数字要添加到小根堆，就先添加到大根堆，再将大根堆堆顶的元素转移至小根堆；反之亦然，以此能够保证小根堆中的元素永远大于大根堆中的元素。

链表

单链表+1

public static ListNode plusOne(ListNode head) {
      //翻转链表
      ListNode newHead = null;
      while (head != null) {
          ListNode temp = head.next;
          head.next = newHead;
          newHead = head;
          head = temp;
      }

      int count = 1;
      ListNode temp = newHead;
      while (count > 0) {
          temp.val += count;
          count = 0;
          if (temp.val >= 10) {
              temp.val -= 10;
              count = 1;
          }
          if (count > 0 && temp.next == null) {
              temp.next = new ListNode(count);
              count = 0;
          }
          temp = temp.next;
      }
      //再次反转
      head = null;
      while (newHead != null) {
          temp = newHead.next;
          newHead.next = head;
          head = newHead;
          newHead = temp;
      }
      return head;
  }

反转链表

public static ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode pre = null;
    ListNode temp = null;
    while (cur != null) {
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

k 个一组反转链表

public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;
    ListNode end = dummy;
    while (end.next != null) {
        for (int i = 0; i < k && end != null; i++) {
            end = end.next;//分组，end指向小组最后一个节点
        }
        if (end == null) {
            break;//链表长度小于k，不翻转
        }
        ListNode next = end.next;//下一组起点
        end.next = null;//断开
        ListNode start = pre.next;//要翻转的头结点

        pre.next = reverse(start);
        start.next = next;
        pre = start;//要翻转节点的上一个节点
        end = start;
    }
    return dummy.next;
}

环形链表

public static ListNode detectCycle(ListNode head) {
       ListNode fast = head;
       ListNode slow = head;
       while (true) {
           if (fast == null || fast.next == null) return null;//无环
           fast = fast.next.next;
           slow = slow.next;
           if (fast == slow) break;
       }
       //到这里一定有环
       fast = head;
       while (slow != fast) {
           slow = slow.next;
           fast = fast.next;
       }
       return slow;
   }

链表相交

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if (headA == null || headB == null) return null;
       ListNode a = headA;
       ListNode b = headB;
       while (a != b) {
           a = a == null ? headB : a.next;
           b = b == null ? headA : b.next;
       }
       return a;
   }

合并链表

public static ListNode mergeTwoLists(ListNode n1, ListNode n2) {
    ListNode dummy = new ListNode(-1);
    ListNode head = dummy;
    while (n1 != null && n2 != null) {
        if (n1.val >= n2.val) {
            head.next = n2;
            n2 = n2.next;
        } else {
            head.next = n1;
            n1 = n1.next;
        }
        head = head.next;
    }
    if (n1 == null) {
        head.next = n2;
    } else {
        head.next = n1;
    }
    return dummy.next;
}

合并 k 个有序链表

public static ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    ListNode dummyHead = new ListNode(0);
    ListNode curr = dummyHead;
    PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    });
    for (ListNode list : lists) {
        if (list == null) continue;
        pq.add(list);
    }

    while (!pq.isEmpty()) {
        ListNode nextNode = pq.poll();
        curr.next = nextNode;
        curr = curr.next;
        if (nextNode.next != null) {
            pq.add(nextNode.next);
        }
    }
    return dummyHead.next;
}

字符串

大数加法

public static String addStrings(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int c = 0;
    int i = num1.length() - 1;
    int j = num2.length() - 1;

    while (i >= 0 || j >= 0 || c != 0) {
        int n1 = i >= 0 ? num1.charAt(i--) - '0' : 0;
        int n2 = j >= 0 ? num2.charAt(j--) - '0' : 0;
        int temp = n1 + n2 + c;
        sb.append(temp % 10);
        c = temp / 10;
    }
    return sb.reverse().toString();
}

数组

哈希表

两数之和

public static int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if (nums.length == 0) return null;
    Map<Integer, Integer> map = new HashMap<>();
    int temp=0;
    for (int i = 0; i < nums.length; i++) {
        temp=target-nums[i];
        if (map.containsKey(temp)) {
            res[1] = i;
            res[0] = map.get(temp);
        }
        map.put(nums[i], i);
    }
    return res;
}

无重复字符最大子串

public static int lengthOfLongestSubstring(String s) {
    int res = 0;
    Set<Character> set = new HashSet<>();
    for (int r = 0, l = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        while (set.contains(c)) {
            set.remove(s.charAt(l));
            l++;
        }
        set.add(c);
        res = Math.max(res, r - l + 1);
    }
    return res;
}

旋转数组

public static int[] reverse(int[] nums, int i) {
       rev(nums, 0, nums.length - 1);
       rev(nums, 0, i - 1);
       rev(nums, i, nums.length - 1);
       return nums;
   }

   public static int[] rev(int[] nums, int start, int end) {
       int l = start;
       int r = end;
       while (r > l) {
           int temp = nums[l];
           nums[l] = nums[r];
           nums[r] = temp;
           r--;
           l++;
       }
       return nums;
   }

二分法

顺序集合的查找

循环不变量

1，[left,right]

while (l<=r){
    int mid=l+(r-l)/2;
    if (nums[mid]>target){
        r=mid-1;
    }else if (nums[mid]<target){
        l=mid+1;
    }else {
        return mid;
    }
}

2，[left,right)

while (l<r){
    int mid=l+(r-l)/2;
    if (nums[mid]>target){
        r=mid;
    }else if (nums[mid]<target){
        l=mid+1;
    }else {
        return mid;
    }
}

滑动窗口

public static int[] maxSlidingWindow(int[] nums, int k) {
       if (nums.length == 0) return new int[0];
       int[] res = new int[nums.length - k + 1];
       LinkedList<Integer> queue = new LinkedList<>();
       for (int i = 0, j = 0; i < nums.length; i++) {
           if (!queue.isEmpty() && i - queue.peekFirst() >= k) {
               queue.pollFirst();
           }
           while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
               queue.pollLast();
           }
           queue.addLast(i);
           if (i >= k - 1) {
               res[j] = nums[queue.peek()];
               j++;
           }
       }
       return res;
   }

最长不重复子串

public static int lengthOfLongestSubstring(String s) {
    int res = 0;
    int l = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int r = 0; r < s.length(); r++) {
        if (map.containsKey(s.charAt(r))) {
            l = Math.max(l, map.get(s.charAt(r)));
        }
        res = Math.max(res, r - l + 1);
        map.put(s.charAt(r), r + 1);
    }
    return res;
}

 public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }
        return res;
    }

动态规划

简单

斐波拉切数列

public static int fib(int n) {
    if (n==0)return 0;
    if (n==1)return 1;
    int[] dp=new int[n+1];
    dp[0]=0;
    dp[1]=1;
    for (int i = 2; i <= n; i++) {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

public static int fib2(int n){
    if (n==0)return 0;
    if (n==1)return 1;
    int dp0=0;
    int dp1=1;
    for (int i = 2; i <= n; i++) {
        int sum=dp0+dp1;
        dp0=dp1;
        dp1=sum;
    }
    return dp1;
}

爬楼梯

public static int climb(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
//dp[0]在此没有意义。
//拓展：最少花费爬楼梯
public static int minCostClimbingStairs(int[] cost) {
    if (cost == null || cost.length == 0) return 0;
    if (cost.length == 1) return cost[0];

    int[] dp = new int[cost.length];
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < cost.length; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    //最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}

不同路径

public static int uniquepaths2(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

//考虑某些位置有障碍
int m=grid.length();
int n=grud[0].length();
//初始化
for (int i = 0; i < m&&grid[i][0]==0; i++) {
        dp[i][0] = 1;
   }
for (int i = 0; i < n&&grid[0][j]==0; i++) {
        dp[0][i] = 1;
   }
//遍历-加上判断条件即可
if(grid[i][j]==1)continue;

整数拆分

1，贪心算法-拆成 333*3……

if(n==2)return 1;
if(n==3)return 2;
if(n==4)return 4;
int res=1;
while(n>4){
    res=res*3;
    n=n-3;
}
res=res*n;
return res;
//数学证明？

2，动态规划

int[] dp=new int[n+1];
dp[2]=1;
for(int i=3;i<=n;i++){
    for(int j=1;j<i-1;j++){
        dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
    }
} 
return dp[n];

背包问题

01 背包

问题描述：物品 N 件，背包重量 W，物品的价值与重量为 value[i]，weight[i]。

dp[i][j]表示在下标[0,i-1]的物品中任意取，存放到容量为 j 的背包的最大价值。

1，递推公式。

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])。

第 i 个物品不取。

第 i 个物品取。dp[i-1][j-weight[i]]+value[i]为背包放 i 物品的最大价值。

2，初始化。

dp[i][0]=0,背包容量为 0，一定是 0。

dp[0][j]=?存放 0 号物品时，最大价值？

dp[0][j]=dp[0][j-weight[0]]+value[0]

倒序遍历！

3，遍历顺序。

先遍历物品好理解。

public static int bag(int bagweight, int[] weight, int[] value) {
    int[][] dp = new int[weight.length][bagweight + 1];
    for (int i = bagweight; i >= weight[0]; i--) {
        dp[0][i] = dp[0][i - weight[0]] + value[0];
    }
    for (int i = 1; i < weight.length; i++) {
        for (int j = 0; j <= bagweight; j++) {
            if (j >= weight[i]) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    return dp[weight.length-1][bagweight];
}

public static void main(String[] args) {
    int[] w = {1, 3, 4};
    int[] v = {15, 20, 30};
    System.out.println(bag(4, w, v));
}

一维 dp[ ]数组。

遍历背包大小时倒序遍历-为了保证每个物品只用一次。

public static int bag1(int bagweight, int[] weight, int[] value){
    int[] dp=new int[bagweight+1];
    for (int i = 0; i < weight.length; i++) {
        for (int j = bagweight; j >= weight[i]; j--) {
            dp[j]= Math.max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    return dp[bagweight];
}

完全背包-每个物品都可以被放入无数次。
只需要改变遍历背包时的遍历顺序。

完全背包

public static int bag2(int bagweight, int[] weight, int[] value) {
    int[] dp = new int[bagweight + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int j = weight[i]; j <= bagweight; j++) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[bagweight];
}

零钱兑换（1,2,5）
可以先遍历总金额吗？不能。
如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。
如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品

public static int coinnum(int[] coins,int money){
    int[] dp=new int[money+1];
    dp[0]=1;
    for (int i = 0; i < coins.length; i++) {//遍历物品
        for (int j = coins[i]; j <= money; j++) {//遍历容量
            dp[j]=dp[j-coins[i]]+dp[j];
        }
    }
    return dp[money];
}

爬楼梯进阶
每次都可以爬 1,2,3,4，，，，n 步？
等价于完全背包问题。
物品就是一步两步三步。
总量就是总的台阶步数。

public static int climb3(int n, int m) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    //排列问题-先遍历背包
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {//遍历物品
            if (i - j >= 0) {
                dp[i] = dp[i] + dp[i - j];
            }
        }
    }
    return dp[n];
}

零钱兑换最少的硬币数

public static int coinmin(int[] coins, int sum) {
    int[] dp = new int[sum + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {
        for (int j = coins[i]; j <= sum; j++) {
            if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
            }
        }
    }
    if (dp[sum] == Integer.MAX_VALUE) return -1;
    return dp[sum];
}

构成完全平方数的最小个数

public static int sqmin(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i <= n; i++) {//遍历背包
        for (int j = 1; j * j <= i; j++) {//遍历物品
            dp[j] = Math.min(dp[i - j * j] + 1, dp[i]);
        }
    }
    return dp[n];
}

打家劫舍

初级打家劫舍

public static int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[nums.length - 1];
}

环形打家劫舍

public static int rob(int[] nums) {
    int len=nums.length;
    if (len==0)return 0;
    if (len==1)return nums[0];
    int res1=helper(nums,0,nums.length-2);
    int res2=helper(nums,1,nums.length-1);
    return Math.max(res1,res2);
}

private static int helper(int[] nums, int start, int end) {
    if (start==end)return nums[start];
    int[] dp=new int[nums.length];
    dp[start]=nums[start];
    dp[start+1]=Math.max(nums[start],nums[start+1]);
    for (int i = start+2; i <= end; i++) {
        dp[i]= Math.max(dp[i-2]+nums[i],dp[i-1]);
    }
    return dp[end];
}

树形打家劫舍

public static int rob(TreeNode root){
   //表示偷某个节点和不偷某个节点的最大值
    int[] res=robtree(root);
    return Math.max(res[0],res[1]);
}

private static int[] robtree(TreeNode cur) {
    if (cur==null)return new int[2];
    int[] left = robtree(cur.left);
    int[] right = robtree(cur.right);
    
    int val1=cur.val+left[0]+right[0];
    int val2=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
    return new int[]{val2,val1};
}

股票问题

买股票最佳时机（只能买卖一次）

public static int maxProfit(int[] prices) {
    int low=prices[0];
    int res=0;
    for(int i=1;i<prices.length;i++){
        low=Math.min(prices[i],low);
        res=Math.max(res,prices[i]-low);
    }
    return res;
}

买股票最佳时机（可以买卖多次）

public int maxProfit(int[] prices) {
    int res=0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i]>prices[i-1]){
            res=res+(prices[i]-prices[i-1]);
        }
    }
    return res;
}

买股票最佳时机（最多买卖 2 次，同时只能有一支）

动态规划：每天有 5 个状态，第一/二天买入/出，无操作

public int maxProfit(int[] prices) {
    if (prices.length == 0) return 0;
    int[][] dp = new int[prices.length][5];
    dp[0][1] = -prices[0];
    dp[0][3] = -prices[0];
    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }
    return dp[prices.length - 1][4];
}

买股票最佳时机（最多买卖 k 次，同时只能有一支）

public int maxProfit(int k, int[] prices) {
    if (prices.length == 0) return 0;
    int[][] dp = new int[prices.length][2 * k + 1];
    //奇数代表卖入，偶数代表买
    for (int i = 1; i < 2 * k; i += 2) {
        dp[0][i] = -prices[0];
    }
    for (int i = 1; i < prices.length; i++) {
        for (int j = 0; j < 2 * k - 1; j += 2) {
            dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
            dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
        }
    }
    return dp[prices.length - 1][2 * k];
}

买股票最佳时机（买卖多次，冷冻期一天）

public int maxProfit(int[] prices) {
    if (prices.length == 0) return 0;
    //状态：买入，卖出（两天前就卖出，今天卖出），冷冻期
    int[][] dp = new int[prices.length][4];
    dp[0][0] = -prices[0];
    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
        dp[i][2] = dp[i - 1][0] + prices[i];
        dp[i][3] = dp[i - 1][2];
    }
    return Math.max(dp[prices.length - 1][3],
            Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]));
}

子序列问题

最长递增子序列

public static int maxlts(int[] nums) {
    if (nums.length <= 1) return nums.length;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int res = 0;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
    }
    System.out.println(Arrays.toString(dp));
    return res;
}

最长连续递增子序列

public static int maxlts(int[] nums) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int res = 1;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i + 1] > nums[i]) {
            dp[i + 1] = dp[i] + 1;
        }
        res = Math.max(res, dp[i]);
    }
    System.out.println(Arrays.toString(dp));
    return res;
}

//贪心算法
public static int maxlts2(int[] nums) {
    if (nums.length == 0) return 0;
    int res = 1;
    int count = 1;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i + 1] > nums[i]) {
            count++;
        } else {
            count = 1;
        }
        res = Math.max(res, count);
    }
    return res;
}

最长重复子数组

public static int maxarray(int[] nums1,int[] nums2){
    int[][] dp=new int[nums1.length+1][nums2.length+1];
    int res=0;
    for (int i = 1; i <= nums1.length; i++) {
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i-1]==nums2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            res= Math.max(res,dp[i][j]);
        }
    }
    for (int i = 0; i < dp.length; i++) {
        for (int j = 0; j < dp[0].length; j++) {
            System.out.print(dp[i][j]+"   ");
        }
        System.out.println();
    }
    return res;
}

最长公共子序列

public static int maxarray(int[] nums1,int[] nums2){
    int[][] dp=new int[nums1.length+1][nums2.length+1];
    int res=0;
    for (int i = 1; i <= nums1.length; i++) {
        for (int j = 1; j <= nums2.length; j++) {
            if (nums1[i-1]==nums2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
            res= Math.max(res,dp[i][j]);
        }
    }
    for (int i = 0; i < dp.length; i++) {
        for (int j = 0; j < dp[0].length; j++) {
            System.out.print(dp[i][j]+"   ");
        }
        System.out.println();
    }
    return res;
}

最大子序和

public static int maxsubarray(int[] nums){
    int res=Integer.MIN_VALUE;
    int count=0;
    for (int i = 0; i < nums.length; i++) {
        count=count+nums[i];
        if (count>res){
            res=count;
        }
        if (count<=0)count=0;
    }
    return res;
}

public static int maxsubarray2(int[] nums){
    if (nums.length==0)return 0;
    int[] dp=new int[nums.length];
    dp[0]=nums[0];
    int res=nums[0];
    for (int i = 1; i < nums.length; i++) {
        dp[i]= Math.max(dp[i-1]+nums[i],nums[i]);
        res= Math.max(res,dp[i]);
    }
    return res;
}

回文子串

public static int countSubstrings(String s){
    int res=0;
    for (int i = 0; i < s.length(); i++) {
        res=res+extend(s,i,i,s.length());
        res=res+extend(s,i,i+1,s.length());
    }
    return res;
}

private static int extend(String s, int i, int j, int length) {
     int re=0;
     while (i>=0&&j<length&&s.charAt(i)==s.charAt(j)){
         i++;
         j--;
         re++;
     }
     return re;
}
public static int huiwen(String s){
    boolean[][] dp=new boolean[s.length()][s.length()];
    int res=0;
    for (int i = s.length()-1; i >=0; i--) {
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(i)==s.charAt(j)){
                if (j-i<=1){
                    res++;
                    dp[i][j]=true;
                }else if(dp[i+1][j-1]){
                    res++;
                    dp[i][j]=true;
                }
            }
        }
    }
    return res;
}
//最长回文子串
public static String maxhuiwen(String s){
    if (s.length()<2)return s;
    int start=0;
    int max=1;
    int len=s.length();
    for (int i = 0; i < len; ) {
        //剩下的已经不可能更长了。
        if (len-i<=max/2)break;
        int l=i;
        int r=i;
        while (r<len-1&&s.charAt(r)==s.charAt(r+1)){
            r++;
        }
        i=r+1;
        while (r<len-1&&l>0&&s.charAt(r+1)==s.charAt(l-1)){
            r++;
            l--;
        }
        if (r-l+1>max){
            max=r-l+1;
            start=l;
        }
    }
    return s.substring(start,start+max);
}

最长回文子序列

public static int longestPalindromeSubseq(String s) {
    int[][] dp = new int[s.length()][s.length()];
    for (int i = s.length() - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][s.length() - 1];
}

判断子序列

public static boolean isSubsequence(String s, String t) {
       if (s.length() == 0) return true;
       int ss = 0;
       for (int i = 0; i < t.length(); i++) {
           if (s.charAt(ss) == t.charAt(i)) {
               ss++;
               if (ss == s.length()) return true;
           }
       }
       return false;
   }

编辑距离

public static int minDistance(String s1,String s2){
    int[][] dp=new int[s1.length()+1][s2.length()+1];
    for (int i = 0; i <= s1.length(); i++) {
        dp[i][0]=i;
    }
    for (int i = 0; i <= s2.length(); i++) {
        dp[0][i]=i;
    }
    for (int i = 1; i <= s1.length(); i++) {
        for (int j = 1; j <= s2.length(); j++) {
            if (s1.charAt(i-1)==s2.charAt(j-1)){
                dp[i][j]=dp[i-1][j-1];
            }else {
                //s1增加一个元素dp[i-1][j]+1==as asd
                //s2添加一个元素dp[i][j-1]+1==asd as
                //替换元素dp[i-1][j-1]+1==asd ase
                dp[i][j]= Math.min(Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1), dp[i][j - 1] + 1);
            }
        }
    }
    return dp[s1.length()][s2.length()];
}

hotcode

LRU

public class LRUCache {
    private class node {
        //双向链表类
        int val;
        int key;
        node pre;
        node next;
        public node(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }

    private HashMap<Integer, node> map;
    private int capacity;
    private node dummyfirst;
    private node dummylast;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        dummyfirst = new node(-1, -1);
        dummylast = new node(-1, -1);

        dummyfirst.next = dummylast;
        dummylast.pre = dummyfirst;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        //缓存中有
        node n = map.get(key);
        //删除该节点
        n.pre.next = n.next;
        n.next.pre = n.pre;
        //移到最后面
        movetolast(n);
        return n.val;
    }

    public void put(int key, int value) {
        if (get(key) != -1) {//已经有了
            map.get(key).val = value;//更新值就可以
            return;
        }
        //之前没有
        node add = new node(key, value);
        map.put(key, add);
        //移到最后面
        movetolast(add);
        //满了就移除
        if (map.size() > capacity) {
            //删除最前面的（最久未用）
            map.remove(dummyfirst.next.key);
            dummyfirst.next = dummyfirst.next.next;
            dummyfirst.next.pre = dummyfirst;
        }
    }

    private void movetolast(node n) {
        n.next = dummylast;
        n.pre = dummylast.pre;
        dummylast.pre = n;
        n.pre.next = n;
    }
}

接雨水

public static int trap(int[] height) {
    int len = height.length;
    int[] maxl = new int[len];
    int[] maxr = new int[len];
    int res = 0;
    for (int i = 1; i < len; i++) {
        maxl[i] = Math.max(maxl[i - 1], height[i - 1]);
    }
    for (int i = len - 2; i >= 0; i--) {
        maxr[i] = Math.max(maxr[i + 1], height[i + 1]);
    }

    for (int i = 0; i < len; i++) {
        int h = Math.min(maxl[i], maxr[i]);
        if (h > height[i]) {
            res = res + h - height[i];
        }
    }
    return res;
}

单例模式

public class Singleton {
    private volatile static Singleton uniqueInstance;
    private Singleton(){
        
    }
    public static Singleton getUniqueInstance(){
        if (uniqueInstance==null){
            synchronized (Singleton.class){
                if (uniqueInstance==null){
                    uniqueInstance=new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

TOPK 问题

public static int findKthLargest(int[] nums, int k) {
    int len = nums.length;
    PriorityQueue<Integer> minheap = new PriorityQueue<>(len, (a, b) -> a - b);//默认最小堆
    for (int i = 0; i < len; i++) {
        minheap.add(nums[i]);
    }
    for (int i = 0; i < len - k; i++) {
        minheap.poll();
    }
    return minheap.peek();
}

public int findKthLargest2(int[] nums, int k) {
    int len = nums.length;
    // 最小堆
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
    for (int num : nums) {
        priorityQueue.add(num);
        if (priorityQueue.size() == k + 1) {
            priorityQueue.poll();
        }
    }
    return priorityQueue.peek();
}

杨辉三角

public List<Integer> getRow(int rowIndex) {
    List<Integer> list = new ArrayList<>();
    while (rowIndex >= 0) {
        rowIndex--;
        list.add(1);
        for (int i = list.size() - 2; i > 0; i--) {
            list.set(i, list.get(i) + list.get(i - 1));
        }
    }
    return list;
}

第一个缺失的正数

public static int firstMissingPositive(int[] nums) {
   Set<Integer> set=new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
    }
    for (int i = 1; i <= nums.length; i++) {
        if (!set.contains(i)){
            return i;
        }
    }
    return nums.length+1;
}
public static int firstMissingPositive2(int[] nums) {
    int len=nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i]<=0)nums[i]=len+1;
    }
    for (int i = 0; i < len; i++) {
        int num= Math.abs(nums[i]);
        if (num<=len){
            nums[num-1]=-Math.abs(nums[num-1]);
        }
    }
    for (int i = 0; i < len; i++) {
        if (nums[i]>0){
            return i+1;
        }
    }
    return len+1;
}

多数元素

public int majorityElement(int[] nums) {
       int major=nums[0];
       int count=0;
       for(int i=0;i<nums.length;i++){
           if(count==0){
               major=nums[i];
               count=1;
           }else if(major==nums[i]){
               count++;
           }else {
               count--;
           }
       }
       count=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==major){
                count++;
            }
        }
        return count>nums.length/2?major:-1;
   }

top

#basic

设计模式上一篇

Redis-缓存一致性下一篇

常见数据结构和算法