数据结构与算法整理

                                    链表

（1）链表的技巧

快慢指针（找环，环入口，环长度）
双指针（倒数K个节点）
合并链表（递归求解）
约瑟夫环（环形链表）

（2）链表的基本操作

删除
删除重复节点
反转链表
```
                                  树
```

树的基本遍历方法

1.前序
2.后序
3.中序
4.层序遍历
很多题目对树的操作其实就是对树的不同层次的遍历。
【例】判断二叉树是否是平衡二叉树（剑指 offer）
利用后序遍历的方式，即在访问某一个节点之前，该节点的左右子树已经被访问过了，此时可以将左右子树的深度进行判断是否在[-1,1]范围之内，同时将判断结果抛给上一层（递归调用），从而完成平衡二叉树的判断。

public class Solution {
    //后续遍历时，遍历到一个节点，其左右子树已经遍历  依次自底向上判断，每个节点只需要遍历一次
     
    private boolean isBalanced=true;
    public boolean IsBalanced_Solution(TreeNode root) {
         
        getDepth(root);
        return isBalanced;
    }
    public int getDepth(TreeNode root){
        if(root==null)
            return 0;
        int left=getDepth(root.left);
        int right=getDepth(root.right);
         
        if(Math.abs(left-right)>1){
            isBalanced=false;
        }

        // left,right是对当前节点的左右子节点进行遍历，return Math.max(left,right)+1
         // 则是求出当前节点的深度，并将结果抛给上一层。
        // 这三个步骤相结合则是一次后序遍历（左右根）
        return right>left ?right+1:left+1;
         
    }
}

【例】求解有序有叉树第k大的节点
这个题明显就是考察中序遍历（左中右）。那么有两中方式进行中序遍历：递归和迭代。通常迭代的难度要高于递归。迭代主要操作就是利用辅助栈来代替递归的栈帧调用。

（1）建立辅助栈。
（2）新见节点（node）= root。
（3）判断node节点的左子节点是否为空，如果不为空则将左子节点入栈，如此往复直到node节点为空。
（4）node节点为空时候，将栈顶元素赋值给node，并同时判断node的右子节点是否为空，不为空则将右子节点入栈。
（5）直到整个栈为空，则整个二叉树访问结束。

还原二叉树

1.前中
2.中后
这两种不管是哪一种都是中序遍历确定左、右子树的划分点（即root在哪里），以根据前中序结果为例：前序遍历（根左右）结果序列中第一个位置就是root节点，将此root节点带回中序遍历序列找出对应位置（x），那么可以找出左右子树（x的左边就是左子树，右边就是右子树），此时递归的进行如此判断则可将二叉树还原。

树的衍生

红黑树
红黑树主要有5个特性：
（1）只有两种颜色：红、黑
（2）叶子节点都是黑色
（3）红色节点的子节点的颜色必然为黑色
（4）从某节点到所有叶子节点的所有路径上的黑色节点数目相同
（5）根节点为黑色
1.1 红黑树的操作
插入
按照插入节点大小划分，分三种情况插入。假定插入节点为T
（1）T是最小的。
（2）T是最大的。
（3）T是中间大小的。
总体过程如图所示：

image.png

红黑树保持特性操作
（1）左旋：当从右侧插入节点后，节点是红色的，则需要左旋。
左旋步骤
1）将父节点（假设为r）右节点（即刚插入的节点，加上为a）指向a的左节点。
2）将a的左节点指向r。
3）给a赋予r的颜色，给r赋予红色（相当于新插入节点）。
（2）右旋：右旋是当节点的左子节点是红色，且左子节点的左子节点还是红色时。核心：左子节点调整到中心，而将中心节点变为左子节点的右子节点
（3）变色：发生在节点颜色为黑色，左右节点为红色的时候，进行颜色反转（变色）。

删除操作。

B树

树的操作

删除
添加

树的性质

                                    算法

排序算法

排序分类

以快排为例，使用分别使用递归和迭代进行比较。
第一步先找基准点（通常以第一个数为基准点x），然后从后往前找小于x的数y，并放于x的位置，此时y所在的位置空出，这时候开始从后面开始往前去寻找大于x的数，将其放于y空出来的位置中，退出的时候x放在最后一个空出来的位置。
方法：使用两个指针，一个指针先从后往前搜索，找到y之后，另一个指针从前往后搜索，将找出来的数放在y空出来的位置。在退出时两个指针是相遇的，将基准点放回这个相遇的位置，这样第一遍交换就完成了。同时需要注意将第一遍交换后的基准点的位置返回，以便于后面的递归操作。

int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
{
    int i = l, j = r;
    int x = s[l]; //s[l]即s[i]就是第一个坑
    while (i < j)
    {
        // 从右向左找小于x的数来填s[i]
        while(i < j && s[j] >= x) 
            j--;  
        if(i < j) 
        {
            s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
            i++;
        }
 
        // 从左向右找大于或等于x的数来填s[j]
        while(i < j && s[i] < x)
            i++;  
        if(i < j) 
        {
            s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
            j--;
        }
    }
    //退出时，i等于j。将x填到这个坑中。
    s[i] = x;
 
    return i;
}

完成了第一遍交换之后，后面对第一遍交换分出来的左右两块分别进行这样的交换。这个操作可以通过递归来完成。


void quick_sort1(int s[], int l, int r)
{
    if (l < r)
    {
        int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
        quick_sort1(s, l, i - 1); // 递归调用 
        quick_sort1(s, i + 1, r);
    }
}

复杂度分析

使用场景

动态规划

动态规划大体上分这么几类：
（1）组合问题
其中比较经典的就是：1. 分钱币问题（背包问题）

掷骰子问题
爬台阶的组合

（2）最优化问题
较为经典的是：

剪绳子
dp[i]代表长度为i的绳子能够被剪获得的最大值。
最大连续子序列和的问题

int maxsequence3(int a[], int len)  
{  
    int maxsum, maxhere;  
    maxsum = maxhere = a[0];   //初始化最大和为a【0】  
    for (int i=1; i<len; i++) {  
        if (maxhere <= 0)  
            maxhere = a[i];  //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]  
        else  
            maxhere += a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和  
        if (maxhere > maxsum) {  
            maxsum = maxhere;  //更新最大连续子序列和  
        }  
    }  
    return maxsum;  
}

【例】[乘积最大子序列]
由于本题中有可能出现负数,那么乘积最大就有可能就是两个负数之积，如此则有必要对负数的乘积进行记录。所以在下面的代码中minSub[i]就是记录到i时的乘积最小值，如果i之前都是正数，那么minSub[i]就会记录当中最小的数（包括当前值nums[i]），如果i之前当中出现了一次负数，那么minSub[i]会记录到一直相乘到当前值nums[i]的乘积。如果出现了2次负数，那么负负得正，将此正数与nums[i]相比较取得最小的那一个。

class Solution {
    public int maxProduct(int[] nums) {
        // 本题目由于含有负数，所以最大值有可能是两个负数相乘得到
        int[] maxSub = new int[nums.length];
        int[] minSub = new int[nums.length];
        int global = nums[0];
        maxSub[0] = minSub[0] = nums[0];
        
        for(int i = 1;i < nums.length;i++){
            if(nums[i] > 0){
                maxSub[i] = Math.max(maxSub[i - 1]*nums[i],nums[i]);
                minSub[i] = Math.min(minSub[i - 1]*nums[i],nums[i]);
            }else{
                // nums[i]的符号不同的时候，最大值、最小值的构成也会相反。
                maxSub[i] = Math.max(minSub[i - 1] * nums[i],nums[i]);
                minSub[i] = Math.min(maxSub[i - 1]*nums[i],nums[i]);
            }
            
            global = Math.max(maxSub[i],global);
        }
        
        return global;
    }
}

【例】#### 分割回文串 II
这个题分成两步骤：（1）判断是否是回文
（2）统计回文长度
判断一串字符串中的某些字串是否是回文占用O(n2)的复杂度。进行回文的切割占用O(n1)的复杂度，同时还需要筛选出最小的切割数，所以这两步总共占用O(n2)的复杂度。
注意：在进行切割的时候只有在是回文的时候才会进行切割，所以需要首先对是否是回文进行判断。

class Solution {
    public int minCut(String s) {
        final int len = s.length();
        int[] count = new int[len + 1];
        //boolean[][] dp = new boolean[len][len];
        int min = len;
        
        for(int i = 0;i < len;i++){
            count[i] = i;
            for(int j = 0;j <= i;j++){
                if(s.charAt(i) == s.charAt(j) && (i-j <= 1 || dp[j + 1][i - 1])){
                    dp[j][i] = true;
                    if(j == 0){
                        count[i] = 0;
                    }else{
                        count[i] = Math.min(count[j - 1] + 1,count[i]);
                    }
                    //count[i] = Math.max(count[i],count[j+1] + 1);
                }
            }
        }
        
        return count[len-1];
    }
}

（3）区间DP
【例】爆裂气球

贪心算法

深度优先搜索

与记忆化递归的区别就是：
记忆化递归并不需要构成完成的搜索树，比如剑指 offer中的字符串构成（能否组成bfg）。按照记忆化递归的来解释，首先寻找b（及入口），然后按照深度优先搜索的方式进行搜索，如果没有找到（1. 一直访问到叶子节点 2. 下一个要找的点是f，但是出现了g，那么退回）则需要回退操作（回退包含，将访问节点从路径中删除，将访问标识回置）。

记忆化递归

【例】矩阵中的路径