前言：容易让人理解的文章行文方式应该是从特殊到一般也即从具体例子到抽象理论的过程。这里反其道而行，让别人容易读懂不是本文的主要目的，主要目的是仅作为自己阅读的总结以备忘。

更多可参阅 labuladong算法总结 （或这个）。 

-------------

总纲！！

计算机算法的本质是穷举，穷举有两个关键难点：无遗漏、无冗余：遗漏，会直接导致答案出错；冗余，会拖慢算法的运行速度；因此，对于一道算法题通常需要考虑的是如何穷举（即无遗漏地穷举所有可能解）及如何聪明地穷举（即做到无冗余的计算）。不同类型的题目，难点是不同的，有的题目难在「如何穷举」，有的题目难在「如何聪明地穷举」。

如何穷举，一般是递归类问题，回溯算法、动态规划算法等本质都是穷举。

如何聪明地穷举，一些常用的非递归算法技巧，都可归为此类，例如动态规划的备忘录、并查集算法、贪心算法、双指针、滑动窗口算法、前缀和、差分数组等等。详见labuladong刷题新的之一些常用的算法技巧。

-------------

1、方法论

DFS、BFS

DFS：本质就是回溯算法，见后文。

所有递归的算法，你不管它是干什么的，本质上都是在遍历一棵（递归）树，然后在节点（前或中或后序位置）上执行代码，你要写递归算法，本质上就是要告诉每个节点需要做什么。

BFS：见labuladong BFS算法解题套路框架、二叉树、多叉树、图的BFS类比演变。BFS算法框架伪代码：

//BFS算法框架
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue q; // 核心数据结构
    Set visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            //visited.add(cur);//也可将visit操作放这，另两处就不用了，这样更简洁

            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;

            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

BFS算法框架

传统BFS的思想就是从起点开始向四周扩散，直到到达终点为止；还有一种小优化的双向BFS算法用于在某些场景下提高执行效率，详见第一篇文章的介绍。

无论传统 BFS 还是双向 BFS，无论做不做优化，从 Big O 衡量标准来看，时间复杂度都是一样的，只能说双向 BFS 是一种 trick，算法运行的速度会相对快一点，掌握不掌握其实都无所谓。最关键的是把 BFS 通用框架记下来，反正所有 BFS 算法都可以用它套出解法。

从框架代码可见，主要就是借助队列来存每一个节点的周围的节点，实际上不一定要用队列，用Set等数据结构也可，只不过此时无法按节点加入Set的顺序访问节点了（在树的层次遍历中通常要求每层上元素从前往后或从后往前访问）。

关于两者的比较及适用场景，具体可参阅上述文章。总的来说，找最短路径的时候使用 BFS（典型的如求树的最近的子节点、求数字锁的最小旋转次数等，详见上述文章），其他时候还是 DFS 使用得多一些（主要是递归代码好写）。

单链表、二叉树、多叉树、图的DFS、BFS算法本质上是类似的，可由DFS、BFS算法套路框架稍作修改得到！！

几大算法模型

分治算法

将大问题分解为互不重叠的若干子问题，分别解决子问题后即完成大问题的解。

回溯算法

用来解决多阶段决策最优解问题

理论

回溯算法相当于穷举搜索：穷举所有的情况，然后对比得到最优解。通常是深度优先递归搜索。由于是暴力算法（万金油），所以可用动态规划等解决的问题也可用回溯法解决，只不过后者用了一些技巧（如备忘录）来“更聪明地穷举”——以空间换时间。

回溯算法的时间复杂度通常非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。

递归时间复杂度（可参与 labuladong-递归时间复杂度分析）

=递归的次数 x 函数本身的时间复杂度
= 递归树节点个数 x 每个节点的时间复杂度
= 状态个数 x 计算每个状态的时间复杂度
= 子问题个数 x 解决每个子问题的时间复杂度

解法模板：

回溯算法就是个 N 叉树的前后序遍历问题，没有例外。

（可参阅：https://github.com/labuladong/fucking-algorithm/blob/master/算法思维系列/回溯算法详解修订版.md）

回溯过程是穷举的过程，实际上就是决策树（或称搜索树）的遍历过程：开始时在根节点，每做一次决策就是选择往当前节点的某条边走从而进入某个子节点，当到达叶节点时停止，此时走过的各边组成的路径即为一个解。时间复杂度通常为决策树叶节点个数，因此时间复杂度通常从问题的决策树去分析。

result = [] //路径列表
 backtrack(已选边列表, 可选边列表){
    if 满足结束条件:
        result.add(已选边列表)//得到一个解。也可直接打印该解，视题目要求；有时可能不需要所有解而是要最优解，这种情况只需保存截至当前的最优解并在此动态更新之
        return
    
    for 边 in 可选边列表{
        做选择：该边从可选列表移除并加入到已选列表
        backtrack(已选边列表, 可选边列表)
        撤销选择：撤销上述选择的操作
    }
}

回溯法穷举的时间复杂度高，但某些问题（如有些最优解问题）可以通过剪枝减少子问题的数量以提高时间效率，此即分支限界算法。

例1：全排列，以下两种实现本质上一样，都是上述模板的具体化，其时间都是复杂度O(n!)。

实现1：代码中用[s, curs)相当于已选择边列表、[curs, e]相当于可选择边列表。

代码：（参阅：）

void myFullPerm(int *data,int s,int curs,int e)//各参数分别为序列、序列起点下标、当前进行全排列的序列起点下标、序列终点下标。s ≤ curs ≤ e 
{
    if(s>curs || curs>e) return;
    
    int i;
    if(curs==e)
    {
        for(i=s;i<=e;i++) printf("%d ",data[i]);
        printf("\n");
    }
    else
    {
        for(i=curs;i<=e;i++)
        {
            swap(data[curs],data[i]);//做选择
            myFullPerm(data,s,curs+1,e);//递归
            swap(data[curs],data[i]);//撤销选择
        }
    }
}

void swap(int &a,int &b)
{
    int tmp=a;
    a=b;
    b=tmp;
}

其对应的决策树为：

实现2：

代码：

List> res = new LinkedList<>();

/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List> permute(int[] nums) {
    // 记录「路径」
    LinkedList track = new LinkedList<>();
    backtrack(track, nums);
    return res;
}


// 结束条件：nums 中的元素全都在 track 中出现
void backtrack( LinkedList track, int[] nums) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(track, nums);
        // 取消选择
        track.removeLast();
    }
}

其对应的决策树为：

更多可参与 labuladong-回溯算法解决9种排列组合问题。 

时间复杂度 = 子问题个数 * 每个子问题的时间复杂度 = O(n*n!  *  n)

例2：求n个元素的所有子集

// 回溯算法计算所有子集（幂集）
void backtrack(int[] nums, int start) {

    // 每个节点的值都是一个子集，O(N)
    res.add(new LinkedList<>(track));

    // 遍历子节点，O(N)
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

时间复杂度 = 子问题个数 * 每个子问题的时间复杂度 = O(2ⁿ  *  n)

例3：n皇后问题：将n个“皇后”摆在n*n的棋盘上使得皇后不能互相攻击（即对于一个皇后来说，其同行同列及同对角线上不存在其他皇后）。注，有些n下（如为2、3时）是无解的。

思路：从第1到n行依次放皇后，每次放置时检查与前面的行放置的皇后不冲突。

代码：

时间复杂度为O(nⁿ)。（与具体实现有关，可通过剪纸技巧减少时间复杂度，参阅：https://sites.google.com/site/nqueensolver/home/algorithm-results）

/* 输入棋盘边长 n，返回所有合法的放置 */
void solveNQueens(int n) {
    int selectedCols[n] = {-1};//初始为-1表示未选
backtrack(selectedCols, n, 0);
}

// selectedCols[i]：存储第i行中摆放皇后的列的位置
// row：将要对第row行选择一个列位置来摆放第(row+1)个皇后
void backtrack(int  selectedCols[], int n, int row) {
    // 触发结束条件
    if (row == n) {
        print selectedCols;
        return;
    }
    
    for (int col = 0; col < n; col++) {
        // 排除不合法选择
        if (!isValid(selectedCols, row, col)) 
            continue;
        // 做选择
        selectedCols[row] = col;
        // 进入下一行决策
        backtrack(selectedCols, n, row + 1);
        // 撤销选择
        selectedCols[row] = -1;
    }
}

/* 是否可以在（row, col)位置放置皇后？ */
bool isValid(int selectedCols[], int row, int col) {
    // 列检查：检查是否 与 前面已放置的各行上的皇后所处的列 冲突
    for (int i = 0; i < row; i++) {
        if (selectedCols[i] == col )
            return false;
    }
    // 检查右上方是否有皇后互相冲突
    for (int i = row - 1, j = col + 1; 
            i >= 0 && j < n; i--, j++) {
        if (selectedCols[i] == j )
            return false;
    }
    // 检查左上方是否有皇后互相冲突
    for (int i = row - 1, j = col - 1;
            i >= 0 && j >= 0; i--, j--) {
        if (selectedCols[i] == col )
            return false;
    }
    return true;
}

例4：数独游戏

 

动态规划

用来解决多阶段决策最优解问题。

理论

（可参阅：https://blog.csdn.net/qq_25800311/article/details/90635979）

一个模型——多阶段决策最优解模型：动态规划问题是求最优解的问题，解决问题的过程需要经历多个决策阶段。每个决策阶段都对应一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

三个性质：适合用动态规划解决的问题必须有满足三个条件：

最优子结构：问题的最优解由【若干个子问题】的最优解组成。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面状态推导出来。关于最优子结构，可参阅：https://github.com/labuladong/fucking-algorithm/blob/master/动态规划系列/最优子结构.md。

子问题重叠：不同的决策序列，到达某个相同的阶段时，可能会产生一样的状态。

无后效性：两层含义——当前阶段的状态由前面若干阶段的状态决定，且不必关心前面的这若干状态是怎么来的；某阶段的状态一旦确定就不受后面阶段决策的影响。这条一般都满足。

 解法：

很多动态规划问题的解决实际上就是在遍历一棵树——决策树。

（可参阅：https://github.com/labuladong/fucking-algorithm/blob/master/动态规划系列/动态规划详解进阶.md）

可以用动态规划解决的问题，解决的步骤：

定义状态变量的含义（通常考虑变量是一维或二维或更多维、包含或不包含当前元素）。

找出状态转移方程（类似数学中的递推式），这是关键点和难点。

确定base case：根据状态转移方程和其中的参数取值范围确定base case。

根据递推式实现（自顶向下或自底向上）。

根据递推式实现，即将递推式翻译成代码（实际上，状态转移方程自身就代表着暴力解法，我们可采用一些技巧来描述该方程从而提高执行效率，例如下面要介绍的备忘录）：

1、回溯法（穷举法）

能用动态规划解决的也能用回溯法解决——即将递推式翻译成代码即可，代码通常是递归算法，其时间复杂度通常很高（因重复计算子问题）。

2、动态规划算法：根据状态转移方程，通常有两法求解动态规划问题，与暴力解法相比其主要原理是借助“备忘录”（可以是数组、Map等）记住当前问题的结论以免重复计算当前问题。

（1）自顶向下递归的“备忘录”法（递归法）：将递推式翻译成代码，只不过进一步借助“备忘录”记住当前问题的结论，因当前问题会重叠故再遇到时直接从“备忘录”取结论而不用重复计算。解决问题为主，构造备忘录为辅。

（2）自底向上迭代的“备忘录”法（非递归法）：从小的子问题到大的子问题依次迭代计算，也借助“备忘录”记住当前问题的结论，当计算更大问题过程中用到子问题时就可从“备忘录”获取子问题结论而不用重复计算。构造备忘录为主，附带借助备忘录得到问题解。

自底向上实现时要注意的是base case应该初始化谁、以及变量迭代方向，这与递推式有关，结论是：应初始化与变量递推方向相反的值；变量也按与递推相反方向迭代。如：若dp(i, j)=dp(i-1,j-1)+... 则初始化左上角、i和j均从小到大；若dp(i,j)=dp(i+1, j-1)+... 则初始化左下角、i从大到小j从小到大，可看后面最长回文子串示例。

备忘录通常采用多维数组，但通常需要对多维数组进行与base case对应的初始化或注意数组越界问题；因此，也可改用Map做备忘录免去这些corner case，更简洁，见下面高楼扔鸡蛋一例。

通常自底向上者比较容易理解；并不是所有动态规划问题在有了状态转移方程后都可轻易用三种方法解决，特别是自底向上者有时不易实现；采用哪种解法更好也跟具体问题有关而非一成不变。

空间复杂度方面，自底向上、自顶向下的备忘录量级通常一样，但自顶向下还会有OS递归产生的额外栈开销；时间复杂度方面，两法也是一样的。

计算机解决问题其实没有奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性，算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。找状态转移方程就是在解决如何穷举、动态规划的备忘录就是在解决如何聪明地穷举，因此动态规划本质上也是穷举，只不过通过空间换时间来降低时间复杂度。

时间复杂度：递归算法（分治、回溯、动态规划等）的时间复杂度为 子问题个数 * 每个子问题的时间复杂度。前者是指实际解决的子问题个数（例如对于子问题重叠的一个递归算法，解决过程中是否采用备忘录会影响实际解决的子问题个数）；后者是指汇总子问题结果的复杂度，通常是O(1) 或 循环的O(n) 或 二分查找的O(lgn)等，详见下例。

例1：斐波那契数列

其状态转移方程为：f(n)=f(n-1)+f(n-2)且n>2、f(1)=1、f(2)=1

1、回溯法（穷举解法）：

时间复杂度O(2ⁿ)、空间复杂度O(1)

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

2、自顶向下：与暴力法很像，只不过多了查备忘录的步骤以免重复计算重叠的子问题

时间复杂度O(n)、空间复杂度O(n)

int fib(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    vector<int> memo(N + 1, 0);
    // 初始化最简情况
    return helper(memo, N);
}
 
int helper(int  memo[], int n) {
    // base case 
    if (n == 1 || n == 2) return 1;
    // 已经计算过
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + 
                helper(memo, n - 2);
    return memo[n];
}

3、自底向上：

时间复杂度O(n)、空间复杂度O(n)

int fib(int N) {
    vector<int> dp(N + 1, 0); //初始化为全0
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

有些情况下，自底向上方法中的“备忘录”可以不用数组而是用几个变量即可，此时时间复杂度O(n)、空间复杂度O(1)

int fib(int n) {
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

例2：矩阵左上角到右下角的最短路径（权值和最小的路径）

状态转移方程为：f(i,j)=matrix[i][j]+ min{ f(i-1,j), f(i,j-1) }，f(i,j)表示(0,0)到(i, j)的最短路径的长度，其中，i∈[0,m], j∈[0,n]

1、回溯法（穷举解法）：

时间复杂度O(2^mn)、空间复杂度O(1)

//调用minDist(n-1,n-1)
int minDist(int i, int j) {
    if (i == 0 && j == 0) return matrix[0][0];
    //if (mem[i][j] > 0) return mem[i][j];//有此步的话则为动态规划递归算法
 
    int minLeft = INT_MAX;
    if (j - 1 >= 0) {
        minLeft = minDist(i, j - 1);
    }
 
    int minUp = INT_MAX;
    if (i - 1 >= 0) {
        minUp = minDist(i - 1, j);
    }
 
    int curMinDIst = matrix[i][j] + min(minLeft, minUp);
    mem[i][j] = curMinDIst;
    return curMinDIst;
}

2、自顶向下：与暴力法很像，只不过多了查备忘录的步骤以免重复计算重叠的子问题

时间复杂度O(mn)、空间复杂度O(mn)

//调用minDist(n-1,n-1)
int minDist(int i, int j) {//mem[][]为备忘录，初始为全0
    if (i == 0 && j == 0) return matrix[0][0];
    if (mem[i][j] > 0) return mem[i][j];
 
    int minLeft = INT_MAX;
    if (j - 1 >= 0) {
        minLeft = minDist(i, j - 1);
    }
 
    int minUp = INT_MAX;
    if (i - 1 >= 0) {
        minUp = minDist(i - 1, j);
    }
 
    int curMinDIst = matrix[i][j] + min(minLeft, minUp);
    mem[i][j] = curMinDIst;
    return curMinDIst;
}

3、自底向上：

时间复杂度O(mn)、空间复杂度O(mn)

int minDistDP(const vectorint>> &matrix, int m, int n) {
    vectorint>> mem;
    int sum = 0;
    for (int j = 0; j < n; ++j) {//初始化mem的第一列数据
        sum += matrix[0][j];
        mem[0][j] = sum;
    }
 
    sum = 0;
    for (int i = 0; i < m; ++i) { //初始化mem的第一行数据
        sum += matrix[i][0];
        mem[i][0] = sum;
    }
 
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            mem[i][j] = matrix[i][j] + min(mem[i - 1][j], states[i][j - 1]);
        }
    }
 
    return mem[n - 1][n - 1];
}

例3：给定k种面值各不相同的硬币coins[k]，每种硬币有无限多个，求凑得总金额amount的最少硬币数dp[amount]，不可能凑出则返回-1。

状态转移方程：f(n)=1+ min{ f(n-coins[i]) }，其中i∈[0, k-1]、n=0时f(n)=0、n<0时f(n)=-1

回溯法、自顶向下、自底向上三种方法：

//回溯法
int minCoinCount(int coins[], int k, int amount){//-1表示不存在方案
    if(amount==0) return 0;
    if(amount<0 || k<=0) return -1;

    int minRes = INT_MAX, tmpRes;
    for (int i=0;i):
        if(amount >= conins[i]){
            tmpRes = minCoinCount(coins,k,amount-coins[i]);
            if(-1==tmpRes) continue;
            tmpRes+=1;
            if(minRes>tmpRes) minRes=tmpRes;
        }
    minRes= INT_MAX==minRes?-1:minRes;//amount<0情况也会被此处理到，故可不用对该情况特殊处理
    return minRes;
}

//自顶向下
int mem[amount+1]={-2};//-2表示未赋值
int minCoinCount(int coins[], int k, int amount){//不存在方案则返回-1

    if(amount==0) return 0;
    if(amount<0 || k<=0) return -1;

    if(mem[amount]!=-2) return mem[amount];

    int minRes = INT_MAX, tmpRes;
    for (int i=0;i):
        if(amount >= conins[i]){
            tmpRes = minCoinCount(coins,k,amount-coins[i]);
            if(-1==tmpRes) continue;
            tmpRes+=1;
            if(minRes>tmpRes) minRes=tmpRes;
        }
    minRes= INT_MAX==minRes?-1:minRes;
    mem[amount]=minRes;
    return minRes;
}


//自底向上
int mem[amount+1]={-2};
int minCoinCount(int coins[], int k, int amount){//不存在方案则返回-1
    mem[0]=0;
    for(int i=1;i<=amount;i++){//从前往后为mem赋值
        mem[i]=INT_MAX;
        for(int j=0;j){
            if(i>=coins[j] && -1!=mem[i-coins[j]]){
                if(mem[i]>mem[i-coins[j]]+1)
                    mem[i]=mem[i-coins[j]]+1;
            }
        }
        mem[i]= INT_MAX==mem[i]?-1:mem[i];
    }
}

时间复杂度为 状态数 * 计算该状态的时间 =O(nk)，n为amount、k为coins个数。

例4：LeetCodeCode-887.高楼抛鸡蛋问题：给定k个鸡蛋n层楼，至少要t次可确保找到扔下鸡蛋不破的最高楼层F。这里F是∈[1,n]的任意值。

状态转移方程：f(k, n)=min_i∈[1,n] { 1+ max{ f(k-1,i-1), f(k,n-i) } }，其中f(1,n)=n、f(k,0)=0。时间复杂度为 min操作的复杂度 * 子问题个数，后者为kn、前者则取决于具体实现（一遍循环则为O(n)、二分查找则为O(lgn)），详见下面的实现。

自顶向下方法实现：

一遍扫描的实现会超时（时间复杂度O(kn2)），这里列出二分查找的实现（时间复杂度O(knlgn)），其他优化（O(kn)）的实现可参阅LeetCode官方题解。

精髓在于为何可用二分查找（因为函数具有单调性）及如何用二分查找。

class Solution {
    int[][] memo;
    public int superEggDrop(int k, int n) {
        if(k<1 || n<1) return 0;

        memo = new int[k][n];
        return dp(k,n);
    }
    //对于给定的正整数k、n，至少要扔多少次才能确保找到”鸡蛋扔下不坏的最高层f“。f可以是[0,n]间的任意一个确定值
    //f(k, n)=min i∈[1,n] {1+max{f(k-1,i-1),f(k,n-i)}}
    //时间复杂度O(knlgn)
    int dp(int k, int n){
        //base case
        if(n==0) return 0;
        if(k==1) return n;

        //memo firse
        if(memo[k-1][n-1]!=0) return memo[k-1][n-1];

        //如下解法理论上可行，但时间复杂度O(kn2)，执行超过时间限制。转而通过二分查找解决
        //递归：穷举所有选择。通过第一次的扔法来确定状态转移
        // int res = Integer.MAX_VALUE;
        // for(int i=1;i<=n;i++){//第一次可能是在任一层扔下
        //     int tmpRes = 1 + Math.max(dp(k-1, i-1), dp(k, n-i));
        //     if(res > tmpRes){
        //         res = tmpRes;
        //     }
        // }

        // v1随i单调递增、v2随i单调递减；而我们要求的是 min {1+max{v1,v2}}，故可二分查找满足【v1≥v2】的最小i（或者满足【v1≤v2】的最大i），则该min值的位置就是i-1、i二者之一。
        // 结合v1、v2单调性及v1初值、v2末均为0可知这样的i一定存在于1
        int left=1, right=n;
        while(left<=right){
            int i = left + (right-left)/2;
            int v1 = dp(k-1, i-1);
            int v2 = dp(k, n-i);
            if(v1>=v2){
                right = i-1;
            }else{
                left = i+1;
            }
        }
        int res = n;
        // if(left>n){//说明符合条件的i不存在，则v1恒小于v2，从而min值为i=n处的v2，即dp(k,0)。实际上不会出现这种情况
        //     res = 1+dp(k, n-n);
        // }else{//说明符合条件的i存在，即left处，则从 left-1、left两处确定min值
            for(int i=left-1; i<=left;i++){
                if(i<1) continue;
                int tmpRes = 1 + Math.max(dp(k-1, i-1), dp(k, n-i));
                if(res > tmpRes){
                    res = tmpRes;
                }
            }
        // }

        memo[k-1][n-1] = res;
        return res;
    }

    //O(nkn)时间复杂度的解法，自底向上迭代。超时
    // public int superEggDrop(int K, int N) {
    //     int[][] middleResults = new int[K + 1][N + 1];
    //     for (int i = 1; i <= N; i++) {
    //         middleResults[1][i] = i; // only one egg
    //         middleResults[0][i] = 0; // no egg
    //     }
    //     for (int i = 1; i <= K; i++) {
    //         middleResults[i][0] = 0; // zero floor
    //     }

    //     for (int k = 2; k <= K; k++) { // start from two egg
    //         for (int n = 1; n <= N; n++) {
    //             int tMinDrop = N * N;
    //             for (int x = 1; x <= n; x++) {
    //                 tMinDrop = Math.min(tMinDrop, 1 + Math.max(middleResults[k - 1][x - 1], middleResults[k][n - x]));
    //             }
    //             middleResults[k][n] = tMinDrop;
    //         }
    //     }

    //     return middleResults[K][N];
    // }

}


//与上法本质上一样，只是更简洁的实现。注意备忘录的定义(不是用数组而是用map)和使用技巧
class Solution1 {
    Map memo = new HashMap();
    int kMax=100;
    public int superEggDrop(int k, int n) {
        return dp(k, n);
    }

    public int dp(int k, int n) {
        if (!memo.containsKey(n * kMax + k)) {
            int ans;
            if (n <= 0) {
                ans = 0;
            } else if (k == 1) {
                ans = n;
            } else {
                //二分查找满足t1≤t2的最大位置，这样的位置一定存在且在范围(1,n)内。hi即为所求
                int lo = 1, hi = n;
                while (lo <= hi) {
                    int x = lo + (hi - lo) / 2;
                    int t1 = dp(k - 1, x - 1);
                    int t2 = dp(k, n - x);
                    if (t1 <= t2) {
                        lo = x+1;
                    } else {
                        hi = x-1;
                    }
                }

                ans = 1 + Math.min(Math.max(dp(k - 1, lo - 1), dp(k, n - lo)), Math.max(dp(k - 1, hi - 1), dp(k, n - hi)));
            }

            memo.put(n * kMax + k, ans);
        }
        return memo.get(n * kMax + k);
    }

}

superEggDrop

另一种逆向思维的解法（详见该题解）：给定k个鸡蛋和t次扔的机会时最多可确定多少个F，因此让t从小到大直到F≥n时t即为所求。此法与后面二分查找一节中“求子数组最大和的最小值”的逆向思维解法很类似。

状态转移方程：f(k, t)= f(k-1,t-2) +  f(k,t-1)+1，其中，f(1,t)=t、f(k,1)=1

自底向上实现：时间复杂度O(kn)，朴素实现的空间复杂度为O(kn)

class Solution{
    //设dp(k,t)表示给定k个鸡蛋t次扔蛋机会时最多能确定的f的个数。
    //则有dp(k,t)= dp(k-1,t-1)  +    dp(k,t-1)+1，两项分别表示在在最合适的一层（这里不用知道是哪一层）扔下后确定的f个数
    int[][] memo;
    public int superEggDrop(int k, int n) {
        memo = new int[k+1][n+1];

        //从小到大一遍循环确定t
        for(int t=1;t<=n;t++){
            if(dp(k,t)>=n) return t;
        }
        return 0;

        // //二分查找确定t。无法用二分查找？
        // int left=1,right=n;
        // while(left<=right){
        //     int t=left+(right-left)/2;
        //     int tmp=dp(k,t);
        //     if(tmp>=n){
        //         right=t-1;
        //     }else{
        //         left=t+1;
        //     }
        // }
        // return left;
        
    }
    private int dp(int k, int t){
        //base case
        if(k==1) return t;
        if(t==1) return 1;
        //memo first
        if(memo[k][t]!=0) return memo[k][t];
        //递归
        memo[k][t]=dp(k-1,t-1)+dp(k,t-1)+1;
        return memo[k][t];
    }
}

注意，通常最优解问题才可用动态规划解决，如 最大子段和问题 可用动态规划解决、而 和等于k的子段数 问题则不用动态规划而是用前缀和解决。

贪心算法

用来解决多阶段决策最优解问题

在解决问题时总是选择当前阶段的最优解，即贪心选择，通过所有阶段都选择局部最优解，最终产生全局最优解。贪心算法际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。

能用贪心算法解决的问题需要满足三个条件：最优子结构、无后效性、贪心选择性

分治、贪心、回溯、动态规划算法的区别

贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类，因为它跟其他三个都不大一样。为什么这么说呢？前三个算法解决问题的模型，都可以抽象成我们多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。

回溯算法是个“万金油”。基本上能用动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，所求问题的整体最优解可以通过一系列局部最优的选择来达到，通过局部最优的选择能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

树/图相关算法（遍历、建立等）

见 

并查集算法

见 

排序算法

见 

随机算法

随机洗牌算法

数组元素洗牌，见 

通用的洗牌算法：见下面的水塘采样算法。特点：一遍扫描、不需要事先知道元素总数、不需要交换元素、空间复杂度低、对数组或链式存储的场景均适用。

 

随机选择算法

这类算法五花八门，且算法的解也有很多。下面列的若干算法解只是比较优美的一种可行方案，而不是唯一方案。

等概率的随机选择

只要算法使得每个元素被选中的概率均为1/n即可。

若元素用数组存储则直接可知n值，此时算法就很简单了：用Random(n)确定要选的元素标、或者用洗牌算法洗出前k个元素、或者给每个元素生成一个随机数然后按随机数排序后或按大小根堆提取前k个（按权重的随机选择可以用此思路），等等。

这里要讨论的是元素用单链表存储场景下的随机选择问题，且要求只能遍历一遍（当然，先遍历一遍确定n然后按数组场景的算法去解决也能得到正确结果，但不符合一次遍历的约束）。

下列算法名为水塘采样（Reservoir sampling）算法，其对元素用数组存储的场景 或 元素个数无限的场景 或 元素无法全加载到内存的场景 均适用！！其名字正来源于其应用场景：当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。

（更多详情可参阅 labuladong-序列元素的随机选择算法）。

随机选择k个元素（要求不允许重复选择同一元素，若允许重选则执行k次选一元素的算法即可），思路和代码非常简洁：

 1 (* S has items to sample, R will contain the result *)
 2 ReservoirSample(S[1..n], R[1..k])
 3   // fill the reservoir array
 4   for i := 1 to k
 5       R[i] := S[i]
 6 
 7   // replace elements with gradually decreasing probability
 8   for i := k+1 to n
 9     (* randomInteger(a, b) generates a uniform integer from the inclusive range {a, ..., b} *)
10     j := randomInteger(1, i)
11     if j <= k
12         R[j] := S[i]

具体实现：

    //从nums[s,e]之间随机选k个元素
    int[] randomSelect(int[] nums, int s, int e, int k){
        if(null==nums || s<0 || e>=nums.length || s>e || e-s+1<k){
            return null;
        }
        //先选中前k个
        int[] res=new int[k];
        for(int i=0;i){
            res[i]=nums[s+i];
        }
        //判断第k个之后的元素是否选中
        for(int i=s+k;i<=e;i++){
            int j=random.nextInt(i-s+1)+1;//随机生成一个[1,i-s+1]间的数字
            if(j<=k){
                res[j]=nums[i];
            }
        }
        return res;
    }

核心思想：前1~ k个元素先选上，然后对于其后的第i个元素，生成[1, i]的一个随机数j，当j∈[1, k]时则选中该元素存入R[j]位置。即给截止到当前元素为止的各元素编号（从1起）并随机选择一个编号，当编号小于等于k时编号对应的元素选中。

在实际实现中通常数组下标从0起且j=random(i)的值域是[0,i)，此时条件是 j

正确性的证明：

当i>k时，P(第i个元素在全部选择完成后仍被选到R中的概率) = P(第i次选择时该元素被选到R中) * P(第i+1、i+2、...、n次选择时均未将元素选到第i次选择时得到的位置) = k/i *  [ i/(i+1) * (i+1)/(i+2) * ... * (n-1)/n ]= k/n；

当i≤k时，P(第i个元素在全部选择完成后仍被选到R中的概率) = P(第k+1、k+2、...、n次选择时均未将元素选到第i次时得到的位置) =  k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = k/n；

综上，第i个元素被选到R中的概率是k/n，从而被选到某个位置j上的概率是1/n。

复杂度：时间复杂度O(n)、空间复杂度O(k)。

优点：不需要事先知道元素有多少个，不需要进行元素比较，只需要一遍扫描等。实际上，洗牌算法也可用此法完成，此时空间效率甚至更高。

缺点：每个元素都需要调用一次随机数生成的函数，因此时间效率可能较低。若已经知道n值则也许用基于数组的随机数选择方案更好？

随机选择一个元素：让上述算法的k=1即可。当然，由于此时randomInteger(1, 1)值恒为1，故可将第一个for归入到第二个for中进行简化，伪代码如下：

1  (* S has items to sample, R will contain the result *)
2  ReservoirSample(S[1..n], R)
3    for i := 1 to n
4      j := randomInteger(1, i)
5      if j ==1
6          R := S[i]

核心思想：虽然是选k个元素的特例，但也可按更简单的思路去理解——对于第i个元素，生成[1, i]的一个随机数j，若j==1则选中。

应用示例：LeetCode 398.随机数索引、382.链表随机节点。

class Solution {
    ListNode head;
    Random random=new Random();
    public Solution(ListNode head) {
        this.head=head;
    }
    
    public int getRandom() {
        ListNode p=head, res=head;
        int i=1;
        while(p!=null){
            if(random.nextInt(i)==0) res=p;
            p=p.next;
            i++;
        }
        return res.val;
    }
}

randomNode

 

带权重的随机选择

从数组元素中按权重随机选一个。比较简单，前缀和+二分查找，示例见LeetCode 528.带权重的随机选择。

带黑名单的随机选择

给定待选数据数组S和黑名单数组B，要求从S随机选择一个不在B中的数据（这里 O(|S| >> O(|B|))、两者各自内部元素不重、且B含于S ），且调用语言内置的随机数生成函数尽可能少，示例见题目 710.黑名单中的随机数。

直觉做法（无法AC）：

法1：借助Map或Set维护B，然后从S中随机选择一个数据，若在B中则重新选否则返回该数据。空间复杂度O(|B|)、预处理的时间复杂度O(|B|)、pick的时间复杂度O(1)。缺点：无法AC——元素重时重复调用随机函数会导致超时。

法2：维护白名单W=S-B，然后从W随机选一个返回即可。空间复杂度O(|S|-|B|)、预处理的时间复杂度O(|S|)、pick的时间复杂度O(1)。缺点：无法AC——运行过程会超过内存限制、扫描一遍S会超时。

正确做法（可AC，此法前提是S是连续且有序的数据，比如上题中S是数字n。详情可参阅题解）：

分析：为免法1那样的超时，须使得只调用一次语言内置的随机数生成函数；为免法2的超内存限制，不能创建新数组或列表或Map等来存白名单；不得扫描一遍S否则会超时。

方案：对法1的改进——随机生成的是黑名单元素时不重新随机生成而是选择其映射到的白名单元素，相当于间接维护了白名单。分析和代码见：

class Solution {
    //B含于S，S是连续的若干数字。设两者大小分别为m、n， n个数中有m个是黑名单数字，以n-m为边界把n个数字分为两部分S1=W1+B1、S2=W2+B2，则S1中黑名单B1的个数与S2中非黑名单W2的个数一样，将这两者元素进行映射即可（B2中的不用映射，否则可能出错），有多种映射方案。这里S、B、S1、S2、B1、B2相当于是已知的，因此关键是求W2。
    //时间复杂度：预处理O(m)、pick O(1)；空间复杂度：O(m)，即只与黑名单大小有关

    Map blackToNotOne=new HashMap<>();//记录B1与W2的映射关系
    int numOfWhite=0;
    Random random = new Random();

    public Solution(int n, int[] blacklist) {
        numOfWhite = n-blacklist.length;

        Set blacks=new HashSet<>();
        for(int b:blacklist){ blacks.add(b); }

        //B1与W2建立映射的关系方式1，顺序选择映射到的W2位置
        // int last = n-1;
        // for(int b: blacklist){
        //     if(b>=numOfWhite) continue;//不在B1的，不用映射，否则会出错
        //     while(blacks.contains(last)){
        //         last--;
        //     }
        //     blackToNotOne.put(b, last);
        //     last--;
        // }

        //B1与W2建立映射的关系方式2，任意顺序
        //得到W2：W2=S2-B 或 W2=S2-B2
        Set w2=new HashSet<>();
        for(int i=numOfWhite;i){ w2.add(i); }
        w2.removeAll(blacks);
        Iterator w2i = w2.iterator();
        for(int b: blacklist){
            if(b>=numOfWhite) continue;//不在B1的，不用映射，否则会出错
            blackToNotOne.put(b, w2i.next());
        }
    }
    public int pick() {
        int val = random.nextInt(numOfWhite);
        return blackToNotOne.getOrDefault(val, val);
    }


   
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */

复杂度：空间复杂度O(|B|)、预处理的时间复杂度O(|B|)、pick的时间复杂度O(1)。

当然，由于S是连续且有序的，故也可用二分查找：对B排序后，在随机生成一个数i时通过二分查找B中小于等于i的个数k，则 k+i 即是结果。

复杂度：空间复杂度取决于B的排序算法O(B)或O(1)、预处理的时间复杂度(BlgB)、pick的时间复杂度O(lgB)

 

FloodFill算法

（可参阅：https://github.com/labuladong/fucking-algorithm/blob/master/算法思维系列/FloodFill算法详解及应用.md）

what：

比如一张图片里选择某个像素后相邻的同颜色像素也都被选中，成为一个区域，从而实现同颜色区域的选择或染色。岛屿问题、扫雷游戏、消消乐游戏、绘图软件的区域选取及颜色填充等都用到此算法。

算法模板：

本质上就是矩阵的遍历，可以用DFS或BFS。

DFS

（输入是二维矩阵，初始从某个点开始访问，递归地向该点的四周扩展访问，直到无法扩展为止，其实相当于四叉树的深度优先前序递归遍历）

int[][] floodFill(int[][] image,
        int srow, int scol, int newColor) {

    int origColor = image[srow][scol];
    fill(image, srow, scol, origColor, newColor);//旧新颜色参数允许一样
    return image;
}

//借助if(origColor==newColor) 来处理旧新颜色一样时递归停不下的问题
void fill(int[][] image, int x, int y,
        int origColor, int newColor) {
    // 参数验证：超出边界
    if (!(x >= 0 && x < image.length
        && y >= 0 && y < image[0].length)) return;

    // 旧新颜色不一样且当前像素需要被替换
    if (image[x][y] == origColor)
    {
        //旧新颜色一样，不用替换
        if(origColor==newColor) return;

        image[x][y] = newColor;
        fill(image, x, y + 1, origColor, newColor);
        fill(image, x, y - 1, origColor, newColor);
        fill(image, x - 1, y, origColor, newColor);
        fill(image, x + 1, y, origColor, newColor);
    }
}

//借助replaced[][]数组来处理旧新颜色一样时递归停不下的问题，用于标记是否已被替换
void fill(int[][] image, int x, int y,
        int origColor, int newColor, int [][]visited) {
    // 参数验证：超出边界
    if (!(x >= 0 && x < image.length
        && y >= 0 && y < image[0].length)) return;


    // 旧新颜色不一样且当前像素需要被替换
    if (image[x][y] == origColor)
    {
        if(replaced[x][y]) return;

        image[x][y] = newColor;
        replaced[x][y]=true;
        fill(image, x, y + 1, origColor, newColor);
        fill(image, x, y - 1, origColor, newColor);
        fill(image, x - 1, y, origColor, newColor);
        fill(image, x + 1, y, origColor, newColor);
    }
}

对于区域内的像素，当访问像素a时，该像素四周的也会被访问，而分别访问四周的像素时也会访问到a，故区域内的每个像素会被访问 (1+四周同颜色像素数) 遍，大多为5。

当旧新颜色一样时，会在当前像素和四周像素间来回递归停不下来，处理方法有两种：判断旧新颜色不一样、借助标记数组，分别对应上述两种代码实现。前者比较简单，但后者适用范围更广（例如抠图时只对边界染色的场景需要用此法，见下文）。当然，也可以不用额外空间作标记数组而是直接修改数组值。

BFS

    public int[][] bfs(int[][] image, int sr, int sc, int newColor) {
        int m=image.length, n=image[0].length;
        if(sr<0 || sr>=m || sc<0 || sc>=n) return image;//边界判断

        int srcColor=image[sr][sc];
        if(srcColor==newColor) return image;//corner case

        int[][] diff=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{sr,sc});
        while(!queue.isEmpty()){
            int[] p=queue.poll();
            image[p[0]][p[1]]=newColor;
            for(int i=0;i){
                int x = p[0] + diff[i][0];
                int y = p[1] + diff[i][1];
                if(0<=x && xsrcColor){
                    queue.offer(new int[]{x,y});
                }
            }
        }
        return image;
    }

拓展：很多绘图软件有抠图功能，其可以选择图像中的前景物体或背景，这与上述染色的区别有二：1是被选择出来的区域中各像素颜色并不完全相同、2是并不对区域染色而是只对边界染色。

解决：

对于第一点可以定义个阈值，将像素值差在阈值内的颜色视为同一种。 return Math.abs(image[x][y] - origColor) <= threshold; //判断某像素是否得被染色 

对于第二点其实就是找区域的边界：对区域内的一个像素来说，其值与上下左右的像素的值相同，而边界的像素则非如此，可据此找出边界像素并对其染色即可。

代码：（基于第二种实现稍加修改即可）

int[][] floodFill(int[][] image,
        int srow, int scol, int newColor) {

    int origColor = image[srow][scol];
    fill(image, srow, scol, origColor, newColor);//旧新颜色参数允许一样
    return image;
}

//借助replaced[][]数组来处理旧新颜色一样时递归停不下的问题，用于标记是否已被替换
void fill(int[][] image, int x, int y,
        int origColor, int newColor, int [][]visited) {
    // 参数验证：超出边界
    if (!(x >= 0 && x < image.length
        && y >= 0 && y < image[0].length)) return;


    // 旧新颜色不一样且当前像素需要被替换
    if (image[x][y] == origColor)
    {
        if(replaced[x][y]) return;

        replaced[x][y]=true;
    
        fill(image, x, y + 1, origColor, newColor);
        fill(image, x, y - 1, origColor, newColor);
        fill(image, x - 1, y, origColor, newColor);
        fill(image, x + 1, y, origColor, newColor);

        //边界元素有没被替换的则说明当前像素是区域的边界
        if( !(replaced[x][y+1] && replaced[x][y-1] && replaced[x+1][y] && replaced[x-1][y] ) ) {
            image[x][y] = newColor;
        }
    }
}

 真题 LeetCode 1034.边界着色 的解法：

class Solution {
    //将指定位置开始的同色块的边界着为指定颜色
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m=grid.length, n=grid[0].length;
        boolean[][] replaced=new boolean[m][n];
        dfs(grid,row,col,grid[row][col],color,replaced);
        return grid;
    }
    
    public void dfs(int[][]grid, int x, int y, int srcColor, int newColor, boolean[][] replaced){
        int m=grid.length, n=grid[0].length;
        if(x<0 || x>=m || y<0 || y>=n) return;
        if(grid[x][y]!=srcColor || replaced[x][y]) return;

        replaced[x][y]=true;
        int[][] diff=new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
        for(int i=0;i){
            int r=x+diff[i][0];
            int c=y+diff[i][1];
            dfs(grid, r, c, srcColor, newColor, replaced);
            //当前元素是边界元素或者当前元素的边界元素没被替换，说明当前元素是边界元素
            if(r<0 || r>=m || c<0 || c>=n || !replaced[r][c]){
                grid[x][y]=newColor;
            }
        }
    }
}

 

有序数组的二分查找算法

1 总纲

只要记住两点即可：

二分查找的代码框架：只要记住有序数组数字的二分查找的代码框架即可，其他各种场景的二分查找都可以之稍加修改得到甚至不用修改。见下面“基本内容”一节。

二分查找适用的场景：一言以蔽之，二分查找是用来查找有序序列中【“符合条件”的某个值】 或 【“符合条件”的最左值或最右值（也即最值）】(有些序列非完全有序的场景也可用二分查找)，所有二分查找的题目都可根据这句话快速写出解题核心代码框架。实际上前者也可以认为是后者的特例。

三种实现方式，三类应用场景（指定值、最左值、最右值）。

==== 以下为分析过程 ==== 

2 基本内容

参考资料：Labuladong 二分查找详解、LeetCode 二分查找专题总结。

（以下叙述中假设有序数组是升序的！！）

用于从一个有序元素序列中找出与给定值一样的元素的位置。当给定元素在元素序列中存在时，根据该元素是否唯一，可以有三种查找方式：

唯一时：普通的二叉查找，如从 [1, 2, 3, 5, 6]中查找2。

不唯一时：返回最左边元素、返回最右边元素，如，如从 [1, 2, 2, 2, 3, 5, 6]中查找2时要求返回最左边的2或最右边的2的位置。

实现1：搜索范围左右均闭区间。代码实现比较简单，这里要强调的是如何深刻理解并容易记忆这个代码的细节：

//由于初始left=0,right=len-1，故搜索范围为[left, right]，从而结束时left=right+1
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {//搜索范围内
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int leftBinarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {//搜索范围内
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 找到，right左移
            right = mid - 1;
        }
    }

    //由于right左移，故若找到则可能位置只能为left
    if (left >= nums.length || nums[left] != target)// 未找到的情况：越界或未找到
        return -1;
    else //找到
        return left;
}


int rightBinarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {//搜索范围内
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 找到，left右移
            left = mid + 1;
        }
    }

    //由于left右移，故若找到则可能位置只能为right
    if (right < 0 || nums[right] != target)// 未找到的情况：越界或未找到
        return -1;
    else //找到
        return right;
}

3 binary search algorithms

注：

1、判断找到时是取left还是right的方法：以只有一个元素且该元素即为所要找到为例即可。从上面实现可看出找最左边元素时取left、找最右边时取right。

2、考虑了越界条件，越界出现的实际场景：待查元素比序列中所有元素大或小的场景

3、循环的条件为“处于搜索范围时”，结束的条件是“不在搜索范围”，范围的具体值取决于left、right的初始定义，上面代码中分别为元素的始终值，即[0、len-1]。

4、对于元素不唯一的情形，按照“查找大于等于给定元素的最左值”（最右值同理）可以将两个条件分支合为一个，更简洁。

5、实际上，元素不唯一的情景有个更简洁的实现方案——与元素唯一时的实现类似，找到一个目标元素时向旁边扩张即可。示例：

    //找到一个元素时分别向左右扩大同元素的范围即可。
    public int[] searchRange2(int[] nums, int target) {
        int left=0, right=nums.length-1;
        while(left<=right){
            int mid= left+(right-left)/2;
            if(target==nums[mid]){
                //发现相等时从左右扩展即可
                int l=mid, r=mid;
                while(l>0 && nums[l-1]==target) l--;
                while(r;
                return new int[]{l, r};
            }
            else if(target;
            else left=mid+1;
        }
        return new int[]{-1,-1};
    }

不过，这种实现方式的效率并没有上述纯二分查找的高，特别是要查找的元素有重复元素且重复元素多时很容易变成局部的线性查找。故知道此法即可但不推荐使用。

当然，某些情形下是有用的，比如若要求【在元素重复时随机选一个而非固定选最左或最右者】则此法适用，实际题目可参阅LeetCode-随机选择重复元素。 

实现2：以左闭右开形式定义“范围”即[0, len) 来实现上述三个算法的等价形式，代码如下：

//由于初始left=0,right=len，故搜索范围为[left, right)，从而结束时left=right
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length; //nums.length - 1; 
    while(left//while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; //mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int leftBinarySearch(int[] nums, int target) {
    int left = 0, right = nums.length; //nums.length - 1;
    while(left//while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; //mid - 1;
        } else if (nums[mid] == target) {
            right = mid; //mid - 1;
        }
    }

    //由于right左移，故若找到则可能位置只能为left
    if (left >= nums.length || nums[left] != target)// 未找到的情况：越界或未找到
        return -1;
    else //找到
        return left;
}


int rightBinarySearch(int[] nums, int target) {
    int left = 0, right = nums.length; //nums.length - 1;
    while(left//while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; //mid - 1;
        } else if (nums[mid] == target) {
            left = mid + 1;
        }
    }

    right--;//因right是开的故结束时可转为闭的算法的情形

    //由于left右移，故若找到则可能位置只能为right
    if (right < 0 || nums[right] != target)// 未找到的情况：越界或未找到
        return -1;
    else //找到
        return right;
}

实现3：上述实现的改版，区别在于要求搜索区间至少有两个或三个元素，因此搜索结束时通常需要对区间内的几个剩余元素进行判断。这种思想的实现应用场景较少，适用于需要在收搜索过程中与左或右边元素比较的场景，例如后面找无序序列峰值的题目。

以实现1的改版为例（实现2也可用同理进行这种改版，这里就不列代码了），代码如下（与实现1的区别：循环条件不同、循环结束后多了步判断）：

    //实现3，实现1的改版。适用于搜索过程中需要与右元素比较的场景（因为这里两个元素时的mid是第一个元素）
    public int search3(int[] nums, int target) {
        int left=0, right=nums.length-1;//搜索范围[left, right]
        while(left < right){//长度至少为2的搜索范围内的每个元素。结束时left=right
            int mid=left+(right-left)/2;
            if(target==nums[mid]) return mid;
            else if(target;
            else left=mid+1;
        }
        //只有一个元素时。可根据只剩两个元素时上面搜索循环中左右指针的走动知道该元素位置
        if(nums[left]==target) return left;
        //找不到
        return -1;
    }
    //实现4，实现1的改版。适用于搜索过程中需要与左或右元素比较的场景
    int search4(int[] nums, int target) {
        int left = 0, right = nums.length-1;//搜索范围[left, right]
        while(left+1//长度至少为3的搜索范围内的每个元素。结束时left+1=right
            int mid=left+(right-left)/2;
            if(target==nums[mid]) return mid;
            else if(target;
            else left=mid+1;
        }
        //只有一个、两个元素时。可分别根据只剩三个、四个元素时上面搜索循环中左右指针的走动知道该元素位置
        if(nums[left]==target) return left;
        if(nums[right]==target) return right;
        //找不到
        return -1;
    }





    //实现1
    public int search1(int[] nums, int target) {
        int left=0, right=nums.length-1;//搜索范围[left,right]
        while(left <= right){//搜索范围内的每个元素。结束时left-1=right
            int mid=left+(right-left)/2;
            if(target==nums[mid]) return mid;
            else if(target;
            else left=mid+1;
        }
        return -1;
    }
    //实现2
    public int search2(int[] nums, int target) {
        int left=0, right=nums.length;//搜索范围[left,right)
        while(left < right){//搜索范围内的每个元素。结束时left=right
            int mid=left+(right-left)/2;
            if(target==nums[mid]) return mid;
            else if(targetmid;
            else left=mid+1;
        }
        return -1;
    }
    

 

上述三种实现中绝大多数场景下用实现1，其他两种用的较少。

3 推广和适用场景总结

实际上，有序数组（假设为升序）的二分查找可归纳为两种情形，其解法即为上述的两个模板，其应用场景也归纳为这两种情形：

1、查指定元素：从有序数组中查找“符合指定条件”的元素。这种场景下“符合条件”的元素只有一个，例如：

从数组查找值为target的元素时元素唯一的情形就属于这种。

从两个正序数组确定中位数的线性时间复杂度解法（详见后文）中“符合条件”指“划分位置的两左部分最大值≤两右部分最小值”的位置。

2、查最值：从有序数组中查找“符合指定条件”的最左边元素、从有序数组中查找“符合指定条件”的最右边元素。这种场景下“符合条件”的元素可能不唯一，因此通常要求取最左或最右甚至随机一个元素；由于数组有序，故这种场景等价于找“符合条件”的最小值或最大值。例如：

A，查找大于等于给定值的最左元素（给定值不一定要在数组中存在）、查找小于等于给定值的最右边元素（给定值不一定要在数组中存在）。

示例1：上面元素不唯一的情形就是这种。

示例2：LeetCode-带权重的随机选择。

示例3：用二分查找实现从升序数组找最小值——找不小于原数组最右值的最左值即可。找最大值同理类比。

B，更一般的情况，这里的“条件”可以是更一般的情形，例如下面的“最大子数组和的最小值”一题的“条件”就表示“有效的划分”、前文动态规划中“高楼抛鸡蛋”的二分查找、符合条件的最小值（如875.猴子吃香蕉、1011.在D天内送完包裹的最小运载能力）等，详情可参阅这些题的解法，细细体会其精髓。

以吃香蕉问题为例，体会二分搜索在其中的作用，代码如下：

class Solution {
    //最大值最小化问题。类似问题都可以二分查找
    //速度为max(piles)时肯定符合，因此从[1, max(piles)]中从小到大找第一个符合的速度，显然可以二分搜索
    //O(nlgn)
    public int minEatingSpeed(int[] piles, int h) {
        int max=0;
        for(int pile: piles){
            if(maxpile;
        }

        int left=1, right=max;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(spendHour(piles,mid)<=h){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    //以speed吃，需要花费多少时间
    private int spendHour(int[]piles, int speed){
        int res=0;
        for(int pile:piles){
            res+= Math.ceil(pile*1.0/speed);
        }
        return res;
    }
}

再以 658.从有序序列找到离给定值最近的k各元素为例，体会其“条件”的定义，代码如下：

class Solution {
    public List findClosestElements(int[] arr, int k, int x) {
        return findClosestElements3(arr,k,x);
    }
    //法1，从两侧删除直到只剩k个元素。O(n-k)
    public List findClosestElements1(int[] arr, int k, int x) {
        int left=0, right=arr.length-1;
        while(right-left+1>k){
            if(x-arr[left]<=arr[right]-x) right--;
            else left++;
        }
        //包装结果
        List res=new ArrayList<>();
        for(int i=left;i<=right;i++){
            res.add(arr[i]);
        }
        return res;
    }
    //法2，二分查找确定与x最靠近的元素作为起点，然后从该起点开始向两边扩。O(lgn+k)
    public List findClosestElements2(int[] arr, int k, int x) {
        //大于等于目标值的最左值
        int left=0, right=arr.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(arr[mid]>=x) right=mid-1;
            else left=mid+1;
        }
        int start;
        if(left==arr.length){//不存在，说明都比x小
            start=arr.length-1;
        }else if(left==0){//说明都大于等于x
            start=0;
        }else{
            start=left;
            if(arr[start]-x >= x-arr[start-1]) start--;
        }
        int end=start;
        //从起始点开始往两边扩
        while(end-start+1<k){
            left=start-1;
            right=end+1;
            if(left==-1){
                end++;
            }else if(right==arr.length){
                start--;
            }else{
                int disLeft=Math.abs(arr[left]-x);
                int disRight=Math.abs(arr[right]-x);
                if(disLeft<=disRight) start--;
                else end++;
            }
        }
        //包装结果
        //System.out.println(start+" "+end);
        List res=new ArrayList<>();
        for(int i=start;i<=end;i++){
            res.add(arr[i]);
        }
        return res;
    }
    //法3（推荐），二分确定大小为k的区间的起点，即找 x-arr[i]≤a[i+k]-x 的最左边位置。O(lgn)
    public List findClosestElements3(int[] arr, int k, int x) {
        int left=0, right=arr.length-1-k;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(x-arr[mid]<=arr[mid+k]-x) right=mid-1;
            else left=mid+1;
        }
        //包装结果
        List res=new ArrayList<>();
        for(int i=0;i){
            res.add(arr[i+left]);
        }
        return res;
    }
}

再以719.从数组找第k小个距离，分析和实现见“后文top k部分的此题分析”。

C，最值问题：

很多最值问题可用二分搜索替代线性扫描来提高效率，其思路是先确定值的取值范围，然后从该范围二分查找“符合条件”的值作为最值。例如上面B部分的例子都是最值问题。

甚至很多非最值问题可以换个角度理解成最值问题，然后用二分查找解决。例如下面“确定正整数n的算术平方根的下取整”一题就是在i∈[1,n]中二分查找满足i*i≤n的最大i。

更多示例可参阅后面应用一节。

更通用的形式：上述的“符合条件”实际上有单调性约束——对于函数f(i)和有序数组 [s,e]，其中i∈[s,e]，只要fun(i) 是关于i的单调函数都可在[s,e]上用二分查找。详见这篇文章。

// func(i) 是 i 的单调函数（递增递减都可以）
int func(int i)
// 形如这种 for 循环可以用二分查找技巧优化效率
for (int i = s; i <=e; i++) {
    if (func(i) == target)//这里是查找精确值。当然，也可以是查最左值、最右值情形，与有序数组的类似
        return i;
}

当fun(i) = nums[i]且nums[]是有序数组时就是有序数组的二分查找。

用二分搜索解决的最值问题的暴力解法通常是这种形式，[s,e]是最值的取值范围、fun(i)是值为i时的一种方案，此时把循环改为二分查找即可。例如上面的高楼抛鸡蛋、吃香蕉、运包裹等问题。 

 

变种：序列不是全部有序但仍可使用二分查找的场景

总结：

主要有【有序序列循环左移后求指定值、求最值；无序序列求极大或极小值、递增再递减序列的极大值】几种情形。

实现原理：由于序列不是整体有序故没法直接套用上面有序情形的框架，通常是利用局部有序序列来缩小范围处理，且处理过程中收缩范围时可能需要包含mid位置。具体结合下面几个示例体会。

1、升序序列循环左移若干位（右移也可，实现完全一样；可以是0位，此时是有序序列；元素不可重）后仍可使用折半查找指定元素（见 LeetCode 33.旋转排序数组的指定值）：

class Solution {//nums[]为递增序列


    //推荐用此法
    public int search(int[] nums, int target) {
        if(null==nums || nums.length==0) return -1;

        int l=0, r=nums.length-1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(nums[m]==target) return m;

            //若序列是递减的，则改变下面所有不等号方向即可
            else if(nums[m]>=nums[l]){//左半部分是有序序列
                if(nums[l]<=target && target//待查元素在有序序列内
                    r=m-1;
                }else{
                    l=m+1;
                }
            }else{//右半部分是有序序列
                if(nums[m]//待查元素在有序序列内
                    l=m+1;
                }else{
                    r=m-1;
                }
            }

        }
        return -1;
    }
    
    //比较简洁的写法，但确定r左移的条件非常容易绕晕，故推荐用上面的方法
    public int search1(int[] nums, int target) {
        if(null==nums || nums.length==0) return -1;

        int l=0, r=nums.length-1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(nums[m]==target) return m;

            //三种情况：左半子序列递增且目标元素位于其间、左半子序列非递增且目标元素位于其前段、左半子序列非递增且目标元素位于其后段
            else if((nums[l]<=target && target=nums[l]) ||(nums[m]nums[m])){
            //对于递减的情形，只要将上面各不等号取反即可，即
            //else if((nums[l]>=target && target>nums[m]) || (nums[m]>nums[l] && target<=nums[l]) ||(nums[m]>nums[l] && target>nums[m])){
                r=m-1;
            }
            else l=m+1;
        }
        return -1;
    }

}

原理：判断“target是否位于有序的那半部分子序列内”来缩小查找范围。

如何判断子序列是否有序？对于升序序列，若num[left]<=num[mid]则前半有序否则后半有序；对于降序序列，改变不等号方向即可。不用记忆，理解其原理即可。

对该实现的说明：元素不可重；降序者同理，只要关键部分不等号改为反向即可。

允许输入序列元素有重的变种（见 LeetCode 81.选择排序数组的指定值）：与元素不可重的实现一样，只不过多了一步首尾元素一样时的去重操作。

    public boolean search(int[] nums, int target) {

        int l=0, r=nums.length-1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(r>l && nums[l]==nums[r]) l++;//r-- 也可
            else if(nums[m]==target) return true;

            //若序列是递减的，则改变下面所有不等号方向即可
            else if(nums[m]>=nums[l]){//左半部分是有序序列
                if(nums[l]<=target && target//待查元素在有序序列内
                    r=m-1;
                }else{
                    l=m+1;
                }
            }else{//右半部分是有序序列
                if(nums[m]//待查元素在有序序列内
                    l=m+1;
                }else{
                    r=m-1;
                }
            }

        }
        return false;
    }

 

 

2、升序序列循环左移（右移也可，实现完全一样；可以是0位，此时是有序序列；元素不可重）若干位后查找最小值（见LeetCode 153.旋转排序数组的最小值）：

（总结：利用局部有序来缩小范围；注意缩小范围时包含mid，这点与前面有序序列二分查找最值不同）

不用记实现代码，理解原理即可，很容易写出来！！！

实现1（元素不可重）：推荐此法

    //序列有序则最小值是最左值；否则序列有有序和无序两个子序列，最小值在无序子序列中。因此只要始终向无序子序列收缩即可。
    //收缩时注意包含mid的情形：根据输入序列是否升序及找最大还是最小，有四种组合：【升序找最小、降序找最大】则往左收缩时要包括mid元素，【升序找最大、降序找最小】则右收缩时要包括mid。如何记？考虑最大值位置、最小值位置、mid位置三者的相对位置，前两者肯定相邻且无序子序列肯定包含前两者，故向无序子序列收缩时若mid位置离要查找目标位置更近则收缩时要包含mid；另一记法是看序列有序时返回的是最左（右），则向左（右）范围收缩时要包含mid。可以上述四种组合想象验证下。
    public int findMin(int[] nums) {
        if(null==nums || nums.length==0) return -1;

        int l=0, r=nums.length-1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(nums[l]<=nums[r]){//序列有序
                return nums[l];
            }else if(nums[l]<=nums[m]){//左子序列有序
                l=m+1;
            }
            else r=m;//注意不是r=m-1

        }
        return -1;
    }

findMin

原理：序列有序则是最左值，否则一半有序一半无序此时最小值出现在无序一侧。须注意范围收缩时包含mid的情形。

对该实现的说明：根据序列升序、降序，查最大、最小值，有四种组合，其实现参照实现原理类比即可，很简单。如何确定范围收缩是否要包含mid的：收缩时 最大值位置、最小值位置 离mid位置 近者刚好也是要求的值时，收缩须包含mid。

实现2（元素不可重）：

    //找【升序序列循环左移或右移若干位后的无序序列】中的最小值，移动位数可为0，此时就是原始升序序列。
    //找出不大于最右值的最左值即可。同理如果题目要求最大值，则找不小于最左值的最右值即可。符合自总结的二分查找框架
    public int findMin2(int[] nums) {
        if(null==nums || nums.length==0) return -1;

        int l=0, r=nums.length-1;
        int last=nums[r];//不能取nums[l]，否则此移动位数为0的场景不适用
        while(l<=r){
            int m=l+(r-l)/2;
            if(nums[m]<=last){// 用 (nums[m]<=nums[r]) 不对，考虑[3,1,2]的情形
                r=m-1;
            }
            else l=m+1;

        }
        return nums[l];
    }

原理：找不大于num[length-1]的最左边元素即可。代码实现与从有序序列查最小值的完全一样，实际上可假设移动了0位即序列是有序的情形来实现。

注意体会该原理成立的充分条件——在值域 [num_min, num[length-1]] 内, num[i] 是关于i单调的。反例：对于先递增再递减序列找最大值的情形用此法则行不通，因为递增序列中元素值有可能也不大于num[length-1]，也即值域内单调性不成立。

对该实现的说明：根据序列升序、降序，查最大、最小值，有四种组合，其实现参照实现原理类比即可，很简单。

允许输入序列元素有重的变种（见 LeetCode 154.旋转排序数组的最小值）：与元素不可重的实现一样，只不过多了一步首尾元素一样时的去重操作。

class Solution {//参阅元素不可重的版本https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/submissions/


    //与元素不可重的实现一样，只不过多了一步去除重复元素的过程。考虑例子 [3,3,1,3]
    //与元素不可重者相比，首末元素相同会影响判断，故只需对该情形进行处理
    public int findMin(int[] nums) {
        //return findMin1(nums);
        return findMin2(nums);
    }

    public int findMin1(int[] nums) {
        if(null==nums || nums.length==0) return -1;

        int l=0, r=nums.length-1;
        while(l<=r){
            int m=l+(r-l)/2;

            //与元素不可重复的版本比，多了此步处理
            if(r>l && nums[l]==nums[r]){
                l++;//r-- 也可
            }

            else if(nums[l]<=nums[r]){//序列有序
                return nums[l];
            }
            else if(nums[l]<=nums[m]){//左子序列有序
                l=m+1;
            }
            else r=m;//注意不是r=m-1

        }
        return -1;
    }

    public int findMin2(int[] nums) {
        if(null==nums || nums.length==0) return -1;

        int l=0, r=nums.length-1;
        int last=nums[r];//不能取nums[l]，否则此移动位数为0的场景不适用
        while(l<=r){
            int m=l+(r-l)/2;

            //与元素不可重复的版本比，多了此步处理
            if(r>l && nums[l]==nums[r]){
                l++;//r-- 不可
            }

            else if(nums[m]<=last){// 用 (nums[m]<=nums[r]) 不对
                r=m-1;
            }
            else l=m+1;

        }
        return nums[l];
    }

}

 

3、从【相邻元素不等】且【nums[-1] = nums[n] = -∞】的无序数组中找任一峰值（见LeetCode 162.寻找峰值）：

   
    //从【相邻元素不等】且【nums[-1] = nums[n] = -∞】的数组中找峰值：二分法爬坡 ———— 通过相邻元素比较来逼近局部极大值，返回哪个极大值不定
    public int findPeakElement(int[] nums) {
        return findPeakElement3(nums);
    }

    //找不小于相邻右元素的最左元素。推荐此法
    //与后元素比较来爬坡。由于只有两个元素时算出的mid是第一个元素，此时若与前一元素比较会越界，故推荐与后元素比较。
    public int findPeakElement3(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high){//至少2个元素
            int mid = low + (high - low) / 2;
            if(nums[mid] >= nums[mid + 1]){
                high = mid;
            }else{
                low = mid + 1;
            }

        }
        return low;//high也可
    }



    //与前元素比较来爬坡
    public int findPeakElement2(int[] nums) {
        if(nums==null|| nums.length==0) return -1;

        int left=0,right=nums.length-1;
        while(left<=right){
            int mid= left+(right-left)/2;
            if(left==mid){//说明只有1或2个元素
                if(mid==right) return left;//只有一个元素
                else{//有两个元素
                    return nums[left]>nums[right]?left:right;
                }
            }
            else if(nums[mid]>nums[mid-1]){//爬坡，须严格大于
                left=mid;//注意不是mid+1
            }else{
                right=mid-1;
            }
        }
        return -1;
    }

    //题意翻译解法。不推荐
    public int findPeakElement1(int[] nums) {
        if(nums==null|| nums.length==0) return -1;

        int left=0,right=nums.length-1;
        while(left<=right){
            int mid= left+(right-left)/2;
            boolean gtl = mid==0 || nums[mid]>nums[mid-1];
            boolean gtr = mid==nums.length-1 || nums[mid]>nums[mid+1];
            if(gtl && gtr){
                return mid;
            }
            else if(gtl){//爬坡，须严格大于
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return -1;
    }

原理：爬坡法——通过相邻元素比较陷入局部有序序列的峰值，因此有多个峰值时返回哪个都有可能。注意爬坡缩小范围时包含mid。不同的实现都是基于此原理，只不过初始值不一样使得不用专门考虑base case，推荐与右元素比较的解法。

说明：元素是无序的；寻找波谷值同理。

前面循环左移序列的最值问题理论上也可由此法稍加改造求解，但由于存在多个坡故如何确保是小值的坡是个难题。不过，实际上，实现1也可认为是此爬坡法的特例。另一方面，上面循环左移序列求最值的两法都不适用于这里，因为不满足单调性。

 

4、从递增再递减序列中找最大值或最小值。

解法：求峰值的特例，只会有一个峰值。注意，上面循环左移序列求最值的两法都不适用于这里，因为不满足单调性。

 

4 应用

与两种场景对应——从有序序列查指定元素、查最值。

查指定元素：简单，没啥可说的。

查最值：

很多求最值的问题可用二分搜索（很多非最值问题也可转为最值问题最终用二分搜索解决），其思路是先确定值的取值范围，然后从该范围二分查找“符合条件”的最值。下面举几个例子。

示例1：比如前面介绍的高楼抛鸡蛋、吃香蕉、运货物等问题，及「使……最大值尽可能小」的问题等都可用二分搜索。再如可用二分法求正整数n的近似整数算术平方根x，其本质就是求满足 x*x ≤n 的最大正整数x，因此是求最右值的二分查找。代码很简单：

    public int mySqrt(int x) {
        if(x==0) return 0;

        int left=1, right=x;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(mid <= x/mid){//注意防mid*mid溢出
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return right;
    }

有很多类似的问题可以这样解决，如判断一个数是否是完全平方数。

示例2：将非负整数数组 num[n] 分成m个连续子数组，求最大子数组和的最小值（hard）。现实场景：n堆货物要车恰好m躺运完，问车的最小载重量是多少。

思路：确定最大子数组和的取值范围，为 [最大元素, 各元素和]，然后从小到大从该范围找到（通过二分查找更快）第一个满足如下条件的值res：存在一种划分方案使得各子数组的和不大于res且划分数k是最少的，当k≤m时res即为所求。如何找该方案呢？贪心策略——num从前往后将和不大于res的元素归为一组即可，可用反证法证明该策略得到的k是最小的。

实现：时间复杂度O(n*lg(sum-maxn))、空间复杂度O(1)。

class Solution {
    public int splitArray(int[] nums, int m) {
        if(null==nums || nums.lengthreturn -1;

        //确定元素和和最大元素
        int left=0, right=0;
        for(int num:nums){
            right+=num;
            left=leftnum:left;
        }

        //二分搜索找符合条件的最小值
        while(left<=right){
            int mid=left+(right-left)/2;
            //贪心策略确定是否存在“最大子数组和不大于mid且划分数不大于m”的划分方案。尽可能多装货物使得装的趟数count最小
            int count=1;
            int sum=0;
            for(int num:nums){
                if(sum+num>mid){
                    count++;
                    sum=num;
                }else{
                    sum+=num;
                }
            }
            if(count<=m){//符合条件
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}

splitArray

举一反三：这里 m∈[1, n] ，有C_n^m种分法，第 i 种划分时m个子数组的和的极值为m_i，则所有划分方案中的极值为M。根据m、M是最大值还是最小值，有四种组合：

最大子数组和的最小值：即题述问题。

最大子数组和的最大值：与上一样，只不过从大到小找res。

最小子数组和的最大值：完全类似的解法——确定最小子数组和的取值范围为，[最小元素, 各元素和]，然后从大到小找到第一个满足如下条件的res：num从前往后将和不小于res的元素归为一组，得到划分数k，当k≥m时，该res即为所求。

最小子数组和的最小值：与上一样，只不过从小到大找res。显然res就是数组的最小元素值。

当然，对于序列非完全有序的一些情景下也可用二分查找，详见前面“变种”部分。

 

2、具体问题归类总结 

0、双指针

（参阅 labuladong双指针技巧总结）

主要有快慢指针、左右指针、滑动窗口等类型。

数组双指针主要包括：从中心向两端扩展的双指针（回文串），从两端向中心收缩的双指针（nSum，二分搜索），快慢指针（滑动窗口，原地去重）。

快慢指针

找单链表某节点（中点、环起始点）的问题大多可用快慢指针解决；

找出单链表的中间节点：快慢指针每次分别走1、2步，当循环结束时慢者即为中点：

ListNode findMiddleNode(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;        
    }

    //可通过此时fast是否为null判断节点个数的奇偶性：fast!=null 时为奇数

    return slow; //slow位置：节点数为奇数时在中，偶数时中偏右
}

findMiddleNode

也可借之确定节点有奇数个还是偶数个：结束时fast为null时有偶数个。

从上述解法同理可得到求任意n分位点的解法：只要让快指针每次比慢指针多走n-1步即可（即快、慢指针每次分别走1、n步）。

用途：对用链表存储的一组数据进行归并排序，此时需要先找中点、然后递归地对两个子链表排序、最后将两个有序子链表合并。

判断单链表是否有环：快慢指针相遇则说明有环。

分析：

慢指针每次走1步、快指针每次走2步，则当慢者走k步（即边数）时快者多走了k步；

当两者相遇时慢者肯定没走完环；且快者比慢者多的刚好是环长（边数）的n倍：若环边数比环前的边数多很多则是1倍，否则可能是多倍

代码：

boolean hasCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast == slow) return true;
    }
    return false;
}

hasCycle

找出含环的单链表中环的起始节点：相遇时分别从相遇节点和单链表起始节点开始，每次走一步，直到再次相遇时即是环起始节点

分析：

基于上面的结论，进一步地，相遇时假设环起始节点到相遇节点有m步，则单链表起始节点到环起始节点有k-m（慢者步数k减去m）；

而由于第一次相遇时快者比慢者多走的k步是环长的倍数，故从该相遇点再走k-m步也将到达环起始节点（此过程绕了环n-1圈）

代码：（与上面的类似）

    public ListNode detectCycle(ListNode head) {
        ListNode slow=head, fast=head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){//说明有环
                slow=head;
                while(slow!=fast){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;
            }
        }
        return null;//说明无环
    }

detectCycleStartNode

应用示例：LeetCode 287.n个元素中取n+1次，只有一个元素有重，寻找该元素。

找出单链表的倒数第k个节点：快慢指针，快指针先行k步，然后两指针同速前行，快者为null时慢者即为所求

    private ListNode reverseKthNode(ListNode head, int n){
        ListNode slow=head, fast=head;
        for(int i=0;i){
            if(null==fast) return null;
            fast=fast.next;
        }
       
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }


//也可用后序遍历的递归解法，不过得加虚拟头节点
    head=new ListNode(-1, head);
    public  int reverseKthNode(ListNode head, int n){//返回值为head的编号
        if(head==null) return 0;
        int num=traverse(head.next, n);
        //if(num==n) head.next=head.next.next;//删除倒数第k个节点
        return num+1;
    }

reverseKthNode

有序数组元素删除的系列场景：详情可参阅此文章（easy）。

这类问题解法和实现都很简单，但双指针在其中的原理和发挥的作用很值得体会和借鉴，在很多其他题目也能用到。

这里以 LeetCode-80.删除有序数组中的重复元素 为例，代码如下：

class Solution {
    //通用解法，k为元素重复时最多要保留的元素的个数，要求k≥1
    //从后向前找重的思路
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int k = 2;
        if (n <= k) {
            return n;
        }
        int slow = k, fast = k;
        while (fast < n) {
            if (nums[slow - k] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            fast++;
        }
        return slow;
    }

    //从前往后找重的思路。只适用于k=2的场景，不通用
    public int removeDuplicates1(int[] nums) {
        if(null==nums || nums.length==0) return 0;
        int left=0, right=1;
        while(right<nums.length){
            if(nums[right]!=nums[left] || right==nums.length-1 ||( nums[right+1]!=nums[left])){
                nums[++left]=nums[right];
            }
            right++;
        }
        return left+1;
    }
}

removeDuplicates

左右指针

其他双指针问题：有序数组二分查找（见前面一节）、有序数组two sum问题、反转数组、原地删除有序数组重复元素等。有序数组two sum问题示例：

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    // 不存在这样两个数
    return new int[]{-1, -1};
}

滑动窗口

解题有大概的模板，分析可参阅“滑动窗口技巧及解题模板”。

滑动窗口思想主要用来解决字符串子段——即子串相关的问题，几个示例：

最短覆盖子串：从字符串S中找出包含 字符串P中所有字符（P中字符可能有重） 的最短子串，即LeetCode-76

class Solution {
    public String minWindow(String s, String t) {
        int resStart = 0, minLen = Integer.MAX_VALUE;//结果信息

        Map windowChCntMap = new HashMap<>();//窗口信息
        Map patternChCntMap = new HashMap<>();
        int left = 0, right = 0, matchCnt = 0;//双指针

        char ch;
        // 初始化patternChCntMap
        for (int i = t.length() - 1; i >= 0; i--) {
            ch = t.charAt(i);
            patternChCntMap.put(ch, patternChCntMap.getOrDefault(ch, 0) + 1);
        }
        // 滑动右边界
        while (right < s.length()) {
            ch = s.charAt(right);
            // 若右边界字符有效：窗口右字符是pattern中的字符
            if (patternChCntMap.containsKey(ch)) {
                // 更新窗口记录信息
                int chCntInWindow = windowChCntMap.getOrDefault(ch, 0) + 1;
                windowChCntMap.put(ch, chCntInWindow);
                if (chCntInWindow == patternChCntMap.get(ch)) {
                    matchCnt++;

                    // 若找到匹配的覆盖串
                    while (matchCnt == patternChCntMap.size()) {
                        // 更新结论
                        if (right - left + 1 < minLen) {
                            resStart = left;
                            minLen = right - left + 1;
                        }
                        // 滑动左边界
                        ch = s.charAt(left);
                        if (patternChCntMap.containsKey(ch)) {
                            chCntInWindow = windowChCntMap.get(ch) - 1;
                            windowChCntMap.put(ch, chCntInWindow);
                            if (chCntInWindow < patternChCntMap.get(ch)) {
                                matchCnt--;
                            }
                        }
                        left++;
                    }
                }

            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(resStart, resStart + minLen);
    }
}

minWindowSubstring

最长不重复子串：即LeetCode-3

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int resStart=0,maxLen=0;//结果信息

        Set chSet= new HashSet<>();//窗口信息

        int left=0,right=0;
        char ch;
        //滑动右边界
        while(right<s.length()){
            ch=s.charAt(right);
            //当前右边界字符有效
            if(!chSet.contains(ch)){
                //更新窗口信息
                chSet.add(ch);
                //更新结论
                if(maxLen){
                    resStart=left;
                    maxLen=right-left+1;
                }
            }else{
                //滑动左边界
                while(s.charAt(left)!=ch){
                    chSet.remove(s.charAt(left));
                    left++;
                }
                left++;
            }
            right++;
        }
        return maxLen;
    }
}

maxUniqueSubstring

 最长递增子串：见后文 “字符串问题-子段” 一节

  

1、位操作妙用

位操作的若干技巧见： 中的节31处

整数二进制形式中1的个数（LeetCode-338）

给定一非负Integer num，求[0,num]每个数的二进制形式中1的个数  f[num+1]。

解法：可用最朴素的方法逐个求，但其实有规律： f[i] = f[i / 2] + i % 2 或  f[i] = f[i&(i-1)] + 1; 

2、Single Number

一组Integer类型的数，除了一个出现N次外，其他都出现M次，找出此数（N ≠ M）。（相关题目：https://leetcode.com/problems/single-number-ii/#/description）

法1：排序，时间复杂度最少O(nlgn)

法2：利用哈希表计每个数出现此时，时间复杂度近似O(n)，空间复杂度为O(n)

法3：（推荐）思路：每个Integer32位，对于每一位，各个数该位上的值的和对M求模，结果即为特殊的数在该位上的和的N倍（若N>M则为 N%M倍）。时间复杂度为O(n)，空间复杂度为O(1)

代码如下：

 1     public int singleNumber(int[] nums, int M, int N) {// with constant memory
 2         int res = 0;
 3         int tmpCurBitSum = 0;
 4         for (int bit = 0; bit < 32; bit++) {
 5             tmpCurBitSum = 0;
 6             for (int i : nums) {
 7                 tmpCurBitSum += ((1 << bit) & i) >>> bit;
 8             }
 9             res |= ((tmpCurBitSum % M)/(N%M)) << bit;
10         }
11         return res;
12     }

特殊情况：M为偶数，N为奇数，如当M=2，N=1时候即为经典的题“除了一个数出现一次外其他数都出现2次”，此时还可以用更简单的方法：所有数异或，结果即为特殊数。

题目变换：有两个分别出现奇数次，其他的都出现偶数次。仍可以用法1或法2解决，但空间复杂度高；另法：所有数异或得到特殊的那两个数的异或值a，对于a中值为1的位，在原两数中该位上的值肯定不同，故可选一位将所有数分成两组，两特殊数分别在两组中，两组各自异或得到两个数即为结果。（相关题目：https://leetcode.com/problems/single-number-iii/#/solutions）

3、子段/子序列问题

假设有数组 a[1, 2, ..., n]，引入如下概念：

子段：a的子数组，为连续的若干个元素，如 a[3, 4, 5] 。子串：当a是字符串时子段也称为子串。

子序列：a的若干个元素组成的数组，不要求元素连续，如 a[1, 3, 4]

问题分类：根据a的元素“当成 ”数值还是字符处理，子段、子序列问题均可分为两类：[ 子段、子序列 ] * [ 数值、字符 ]。注意这里是“当成”，也就是说跟题意有关：如对于a=[3, 2, 4, 5, 1]，虽元素是数值，但既可以求最大子段和、又可以求最长不重复子段，后者就是“当成”字符处理。

解决方法：子段、子序列问题大多可用动态规划解决。当然，有的问题还有更好的解决方式，如有些子段和问题用前缀和、有些子串问题用滑动窗口解决更好。

注：子段也是种特殊的子序列，反之则不是。

3.1 数值问题-子段/子序列

子段和用动态规划或前缀和解决；用动态规划时，对于子段问题假设的状态变量通常包含当前末尾元素、对于子序列问题则否，不过并不绝对。

1、子段/子序列和的最大值

1、最大子段和（一个子段）：设 b[j] 为 a[1,2,...,j] 包含 a[j] 的最大子段和，根据子段是否仅包含a[j]有（也可根据b[j-1]是否大于0得到）： b[j] = max{a[j], b[j-1]+a[j] } 

 1 int maxSum(int n,int *a)
 2 {
 3   int sum=0,b=0;
 4   for(int i=0;i)
 5   {
 6     if(b>0) b+=a[i];
 7     else b=a[i];
 8     if(sumb;
 9   }
10   return sum;
11 }

这实际上是下面最大m子段和问题的特例。

2、最大m子段和（找出m个子段，可以相邻）：设 b[i,j] 为 a[1,2,...,j] 前j项中i个子段的最大和且第i个子段包含a[j]（1≤i≤m, i≤j≤n），则根据第i个子段是否仅仅包含a[j]有：

b[i,j]= 0 (i=0或j=0时)

b[i-1,j-1]+a[j] (i==j时)

max{ b[i,j-1]+a[j], (max b[i-1,t])+a[j] } (i

由于元素可相邻，故此问题可以看看成是子段和问题，也可以看成是子序列问题。

3、最大不相邻子段和（找出任意个不相邻子段使和最大）：设 b[j] 为 a[1,2,...,j] 不相邻子段和的最大值（不要求包括a[j]），则根据 b[j] 是否包括 a[j] 有：b[j]= max{ a[j]+b[j-2], b[j-1] }。相关：LeetCode198：House Robber

 1     public int maxNonadjacentSun(int[] nums) {
 2         if(nums.length==0)return 0;
 3         if(nums.length==1)return nums[0];
 4         
 5         int b1=0,b2=nums[0],tmp;
 6         for(int i=1;i)
 7         {
 8             tmp=b1+nums[i];
 9             b1=b2;
10             if(b2<tmp)
11             {
12                 b2=tmp;
13             }
14         }
15         return b2;
16     }

对于第一、第三种，由于b[j]只和前一个或两个状态有关，因此可以不设数组b[]而是采用数个变量来求；对于第二种同理可以只用两个数组来实现。

4、推广：

最小子段和

最大/最小连续子段积

设有序列 a[1,2,...,n]，设f(k)为a[1,2,...k]中包含a[k]元素的最大连续子数组积，相应的g(k)为包含a[k]的最小连续子数组积，

则 f(k) = max( f(k-1) * a[k], a[k], g(k-1) * a[k] ), g(k) = min( g(k-1) * a[k], a[k], f(k-1) * a[k] ) ，从而易在O(n)内求之。

2、和为给定值的种数

 设有序列 a[1,2,...,n]，给定数sum。

1、子段和的种数（和为sum的子段种数）

（1）有O(n)时间复杂度的算法，具体见后文的“前缀和问题”一节。 

（2）（非最优解）当各元素非负时可用动态规划：设dp[i,j]为从序列前i个数中选若干个数使得和为j的种数（要求选中的必须包含a[i]），有：

dp[i,j]= 

0，i=0时；

a[i]==j?1:0，i=1时；

a[i]==j?1:0 + dp[i-2, j] ，i>1且a[i]>j时；

( a[i]==j?1:0 + dp[i-2, j] ) + ( dp[i-1, j-a[i] ] )，i>1且a[i]≤j时 （根据dp[i,j]是否仅包含a[i]）

时间复杂度、空间复杂度均为O(n*sum) 。这显然不是好的方法，特别是sum很大时；此外，此法应用场景有限，要求各元素非负，写于此只是用于说明动态规划在此题的用法。

另外，上述的递推式实际上是适合于自底向上动态规划实现的递推式（其特点是i、j非负），相应地，我们可以写出适合于自顶向下动态规划实现的递推式（特点是i、j可负）：

dp(i, j)=

0, i<=0或j<0时;

( a[i]==j?1:0 + dp(i-2, j) ) + ( dp(i-1, j-a[i] ) )，其他

可见，这种形式更简洁，通过允许i、j负值使得几个分支合并到最后分支了。

2、子序列种数（和为sum的子序列的种数）

1、求序列中两数和等于sum的种数：LeetCode1：TwoSum

public int[] twoSum1(int[] nums, int target) {//O(n2),O(1)
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}


public int[] twoSum2(int[] nums, int target) {//two pass,O(n),O(n)
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

public int[] twoSum(int[] nums, int target) {//one pass,O(n),O(n)
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

 

2、求序列中若干个数和等于sum的种数。

（1）最优解法是？

（2）当各元素非负时可用动态规划：设dp[i,j]为从序列前i个数中选若干个数使得和为j的种数，则：

dp[i,j]=

1，i=0且j=0时；

0, i=0且j>=0时；

dp[i-1,j]，a[i]>j时；

（ dp[ i-1,j-a[i] ] )+ ( dp[i-1,j] ), a[i]≤j时  （根据是否包含a[i]有两种情况）

 1     public static int resolve(int[] a, int sum) {// num of solutions that addup to sum
 2         if (a == null || a.length == 0) {
 3             return 0;
 4         }
 5         int n = a.length;
 6         int[][] dp = new int[n + 1][sum + 1];
 7         dp[0][0] = 1;
 8         // dp[i][k]=0,k>0，默认被初始化了
 9         for (int i = 1; i <= n; i++) {
10             for (int j = 0; j <= sum; j++) {
11                 if (a[i - 1] > j) {
12                     dp[i][j] = dp[i - 1][j];
13                 } else {
14                     dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]];
15                 }
16                 System.out.printf("(%d,%d):%d\n", i, j, dp[i][j]);
17             }
18         }
19         return dp[n][sum];
20     }

时间复杂度、空间复杂度均为O(n*sum) 

3.2、字符串问题-子段

字符串的子段即子串。子串问题通常用动态规划或滑动窗口解决 

1、一个字符串的子串问题通常用滑动窗口方法解决。如：

最短覆盖子串：LeetCode-76。具体可参阅上面双指针部门内容。

最长不重复子串：LeetCode-3 

最长递增子串：

动态规划法：设dp[i]为a的前i个元素中以a[i]结尾的最长递增子串，则dp[i]= (a[i]≥a[i-1]) ? (dp[i-1]+1) : 1  ，base case：dp[1]=1。

时间复杂度O(n)，空间复杂度O(n)，由于当前状态只跟前一状态有关故可使用一个变量记录上一状态值从而使得空间复杂度降到O(1)

// 动态规划法
    public int resolveByDynamic(int[] nums) {
        int[] dp = new int[nums.length];

        int res = 0;

        // ==== 空间复杂度O(n) =====
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            // 求dp[i]
            dp[i] = nums[i] >= nums[i - 1] ? dp[i - 1] + 1 : 1;
            // 更新结果
            if (res < dp[i]) {
                res = dp[i];
            }
        }
        // ==== 空间复杂度O(1) =====
        int curMaxlen = 1;// 对应上面dp[0]=1
        for (int i = 1; i < nums.length; i++) {
            curMaxlen = nums[i] >= nums[i - 1] ? curMaxlen + 1 : 1;
            if (res < curMaxlen) {
                res = curMaxlen;
            }
        }

        return res;
    }

滑动窗口法，与动态规划有点像：

O(n)、O(1)

    // 滑动窗口法
    public int resolveByWindow(int[] nums) {
        int resStart = 0, maxLen = 0;

        int s = 0, e = 0;

        while (e < nums.length) {
            // 右边界有效
            if (s == e || nums[e] >= nums[e - 1]) {
                // 更新窗口：do nothing

                // 更新结论
                if (maxLen < e - s + 1) {
                    resStart = s;
                    maxLen = e - s + 1;
                }
            } else {
                // 滑动左边界
                s = e;
            }
            e++;
        }

        return maxLen;// 若要返回该串则可借助resStart
    }

 

2、最长公共子串：

设 dp[i,j]  为序列a1[1,2,...,i ]、a2[1,2,...j ] 的包含未元素的最长公共子串的长度，则dp[i,j]= (a1[i]==a2[j])? (dp[i-1,j-1]+1): 0 }

 1     private static int resolve(String s1, String s2) {
 2         if (s1 == null || s2 == null) {
 3             return 0;
 4         }
 5         int n = s1.length();
 6         int m = s2.length();
 7         int max = 0;
 8         int[][] dp = new int[n + 1][m + 1];
 9         for (int i = 1; i <= n; i++) {
10             for (int j = 1; j <= m; j++) {
11                 dp[i][j] = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? (dp[i - 1][j - 1] + 1) : 0;
12                 if (max < dp[i][j]) {
13                     max = dp[i][j];
14                 }
15             }
16         }
17         return max;
18     }

3、最长回文子串：LeetCode-5

设dp[i,j]表示si,...,sj是否为回文子串，则dp[i,j]= dp[i+1,j-1] && (s[i]==s[j]), i≤j; 初始：dp[i,i]=true,dp[i,i+1]=s[i]==s[i+1]
O(n2),O(n2)

 1 public class Solution {
 2     //最长回文子串和最长回文子序列不一样。。
 3     //设dp[i,j]表示si,...,sj是否为回文子串，则dp[i,j]= dp[i+1,j-1] && (s[i]==s[j]), i≤j; 初始：dp[i,i]=true,dp[i,i+1]=s[i]==s[i+1]
 4     //O(n2),O(n2)
 5     public String longestPalindrome(String s) {
 6         if(s==null || s.length()==0) return "";
 7         int len=s.length();
 8         
 9         boolean [][]dp=new boolean[len][len];//标记dp[i+1,j-1]即左下角是否为回文子串
10         int resI=0,resJ=0;
11         for(int i=len-1;i>=0;i--)
12         {
13             dp[i][i]=true;//dp[i,i]=true;
14             for(int j=i+1;j)
15             {
16                 dp[i][j]= (j==i+1)?(s.charAt(i)==s.charAt(j)):(dp[i+1][j-1] && (s.charAt(i)==s.charAt(j)));
17                 if((dp[i][j]==true) && (resJ-resI+1 < j-i+1))
18                 {
19                     resI=i;
20                     resJ=j;
21                 }
22             }
23         }
24         return s.substring(resI,resJ+1);
25     }
26 }

 需要注意，一个串及其逆串的最长公共子串不一定是原串的最长回文串，例如 "aacxycaa"。

此题是少有的动态规划不是最优解的问题：

存在将空间复杂度降为O(1)的解法：以i位置的元素为中心向两边扩并判断可达得到最长回文串，遍历所有i位置即可。

还存在时间复杂度为O(n) 的 Manacher's Algorithm（马拉车算法），比较复杂。

 

3.3、字符串问题-子序列

子序列问题通常用动态规划解决。

1、最长公共子序列（LCS）：设 dp[i,j]  为序列a1[1,2,...,i ]、a2[1,2,...j ] 的最长公共子序列的长度，则dp[i,j]= (a1[i]==a2[j])? (dp[i-1,j-1]+1): max{ dp[i-1,j], dp[i,j-1] }

a与a的排序序列的LCS为a的LIS；a与a的反转序列的LCS为a的最长回文子序列。子串则没有这个结论！！！

2、最长递增子序列（LIS）：

动态规划：设dp[i]为a的前i个元素中以a[i]结尾的最长递增子序列，则dp[i]= max{ dp[j] } +1，其中j∈[1,i-1]且a[i]≥a[j]，，base case：dp[k]=1，k∈[1,n]。

O(n²)、O(n)

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];

        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            // 求dp[i]
            dp[i] = 1;// 初始为1
            for (int j = 0; j < i; j++) {
                if (nums[i] >= nums[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            // 更新结果
            if (res < dp[i]) {
                res = dp[i];
            }
        }

        return res;
    }

也可将序列排序后求排序序列与原序列的最长公共子序列，时间复杂度也是O(n²)

有O(nlgn)的贪心算法——LeetCode-354）：给定一批信封，每个有长宽两个属性，如 [[5,4],[6,4],[6,7],[2,3]] 。求能互相嵌套（能把小的放到大的里）的最多信封数。解法：把每个信封看做一维形式中的每个数即可，不同之处在于这里数间相对位置不是固定的而是可以移动，故先根据一个维度排序再用上述一维形式求解即可；此外这里须是严格递增。可参阅：https://github.com/labuladong/fucking-algorithm/blob/master/算法思维系列/信封嵌套问题.md

代码：时间复杂度为 排序复杂度+一维LIS复杂度

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
               return a[0] == b[0] ? 
                    b[1] - a[1] : a[0] - b[0];
          }
        });
        return lengthOfLIS(envelopes);
    }
    public int lengthOfLIS(int[][] nums) {//O(n2)
        int[] dp = new int[nums.length];

        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            // 求dp[i]
            dp[i] = 1;// 初始为1
            for (int j = 0; j < i; j++) {
                if (nums[i][0] > nums[j][0] && nums[i][1] > nums[j][1] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            // 更新结果
            if (res < dp[i]) {
                res = dp[i];
            }
        }

        return res;
    }
}

 

3、最长回文子序列：https://leetcode.com/problems/longest-palindromic-subsequence/#/description

法1：即求字符串S与逆串的最长公共子序列

 1     public int longestPalindromeSubseq1(String s) {
 2         if(s==null || s.length()==0) return 0;
 3         
 4         int len=s.length();
 5         int [][]c=new int[len+1][len+1];
 6         for(int i=0;i)
 7         {
 8             c[0][i]=0;
 9             c[i][0]=0;
10         }
11         
12         for(int i=1;i<=len;i++)
13         {
14             for(int j=1;j<=len;j++)
15             {
16                 if(s.charAt(i-1)==s.charAt(len-j))
17                 {
18                     c[i][j]=c[i-1][j-1]+1;
19                 }
20                 else
21                 {
22                     c[i][j] = c[i-1][j]>c[i][j-1] ? c[i-1][j] : c[i][j-1];
23                 }
24             }
25         }
26         return c[len][len];
27     }

法2：动态规划

设dp[i,j]表示si,...sj的最长回文子序列的长度，其中i≤j，则dp[i,j]= 

dp[i+1,j-1]+2, si=sj时；

max{ dp[i,j-1], dp[i+1,j] }, si≠sj时

代码（可以仿照上面最长回文子串的实现方式）：

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

也可以啰嗦点实现：

设字符串为s，f(i,j)表示s[i..j]的最长回文子序列。 最长回文子序列长度为f(0, s.length()-1)
状态转移方程如下：
当i>j时，f(i,j)=0。
当i=j时，f(i,j)=1。
当i当i注：如果i+1=j并且s[i]=s[j]时，f(i,j)=f(i+1,j-1)+2=f(j,j-1)+2=2，这就是当i>j时f(i,j)=0的好处。

 1     public int longestPalindromeSubseq(String s) {
 2         if(s==null || s.length()==0) return 0;
 3         
 4         int len=s.length();
 5         int [][]f=new int[len][len];
 6         
 7         for(int i=len-1;i>=0;i--)//由于递推式每次最多后移一行，因此从最后一行起
 8         {
 9             // for(int j=0;j//由于递推式每次最多前移一列，因此从第一列起。但由于创建f时元素自动初始化为0，所以这里可以从i起
10             for(int j=i;j)
11             {
12                 if(i>j) f[i][j]=0;
13                 else if(i==j) f[i][j]=1;
14                 else
15                 {//i
16                     if(s.charAt(i)==s.charAt(j)) f[i][j]=f[i+1][j-1]+2;
17                     else f[i][j]=Math.max(f[i+1][j],f[i][j-1]);
18                 }
19             }
20         }
21         return f[0][len-1];
22     }

4、最小编辑距离问题。

class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length(), n=word2.length();

        int[][] dp=new int[m+1][n+1];
        for(int i=0;ii;
        for(int j=0;jj;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{//插入、删除、修改三选一
                    int min=Math.min(dp[i-1][j],dp[i][j-1]);
                    min=Math.min(min, dp[i-1][j-1]);
                    dp[i][j]=min+1;
                }
            }
        }
        return dp[m][n];
    }
}

 

4、前缀和数组问题

主要用于解决不修改原始数组场景下频繁查询某个区间累加和的问题。O(1)时间复杂度求区间和。

原理：针对数组 num[] 建立个等长度的辅助数组preSum[]，preSum[i] 的值为 num[0,...i] 的和。当然，视具体问题而定，有时候不需要 preSum[] 而是直接只用一个preSum变量。

示例1：303.求给定不可变数组的子数组和。典型的前缀和问题，解法：

class NumArray {
    // 前缀和数组, preSum[i] 表示nums[0,...i-1]的和
    private int[] preSum;

    /* 输入一个数组，构造前缀和 */
    public NumArray(int[] nums) {
        // preSum[0] = 0，便于计算累加和
        preSum = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    /* 查询闭区间 [left, right] 的累加和 */
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

示例2：304.求给定不可变二维矩阵的子矩阵和。可直接构造二维前缀和矩阵、或者基于二维矩阵构造一维前缀和数组。两种解法：

    //法1
    int[] preSum;
    int hight;
    int width;
    public NumMatrix(int[][] matrix) {
        hight=matrix.length;
        width=matrix[0].length;
        int length=hight*width;
        preSum=new int[length+1];
        for(int i=0;i){
            for(int j=0;j){
                int index=i*width+j+1;
                preSum[index]=preSum[index-1]+matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res=0;
        for(int row=row1;row<=row2;row++){
            int rowSum=preSum[row*width+col2+1]-preSum[row*width+col1];
            res+=rowSum;
        }
        return res;
    }

    //法2
    private int[][] preMatrixSum;
    public NumMatrix(int[][] matrix) {
        preMatrixSum = new int[matrix.length + 1][matrix[0].length + 1];
        for(int i = 1;i <= matrix.length; i ++){
            for(int j = 1;j <= matrix[0].length;j ++){
                preMatrixSum[i][j] = preMatrixSum[i-1][j] + preMatrixSum[i][j-1] + matrix[i- 1][j - 1] - preMatrixSum[i-1][j-1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preMatrixSum[row2 + 1][col2 + 1] - preMatrixSum[row2 + 1][col1] - preMatrixSum[row1][col2 + 1] + preMatrixSum[row1][col1];
    }

示例3：560.给定一个数组a[n]，求和为给定数字k的子数组（即元素要连续）的个数。

暴力法：两层循环以穷举每个子数组、再一层循环以求子数组和，然后判断是否等于k

时间复杂度O(n³)、空间复杂度O(1)

改进法1：不借助求和数组，而是只借助一个变量来记住子数组和。

时间复杂度O(n²)、空间复杂度O(1)

int subAryCount(int a[], int n, int k){
    int res=0;
    for(int i=0; i){
        int sum=0;
        for(int j=i; j){
            sum+=a[j];
            if(sum==k){ res++; }
        }
    }
    return res;
}

改进法2：借助前缀数和以去掉第三层循环，避免每次计算子数组和：借助一个数组sum[n]计算到当前元素为止的元素累加和，则子数组a[i, ..., j]的和为sum[j]-sum[i-1]或sum[j]

时间复杂度O(n²)、空间复杂度O(n)

改进法2：利用前缀和以去掉第二层循环——在sum[]上做文章，两层循环以检查sum[j]-sum[i]为k的情况数，换个角度有sum[j]-k=sum[i]，因此可以用map记住截止到当前元素a[i]时前缀和sum[i]出现的次数，从而看a[i]-k出现的次数即可。这样只要一次扫描。

时间复杂度O(n)、空间复杂度O(n)，借助 前缀和+Map 来空间换时间。

通用实现，可返回具体的所有方案或仅返回方案数或仅返回是否存在方案：

    //preSum[j]-k==preSum[i]时nums[i+1,...j]即为所求
    //“补数”：差为k的其他状态
    public int subarraySum(int[] nums, int k) {
        //状态：key为前缀和的值、value为前缀和为该值的元素下标列表
        Map> map =new HashMap<>();
        //初始化第一次遇到[0,..j]为一个解时的状态，此时preSum[j]-k为0、i+1为0，故添加{0,[-1]}元素
        map.computeIfAbsent(0, key->(new HashSet())).add(-1);

        int res=0;
        for(int i=0, preSum=0;i){
            preSum += nums[i];
            //通过状态信息找”补数“并确定是否存在可行解
            int preKey = preSum - k;
            Set indexes = map.get(preKey);
            if(null != indexes && indexes.size()>0 ){//说明存在可行解
                //对于indexes中的每个元素j，nums[j+1,...i]都是一个可行解
                res += indexes.size();
            }
            //更新到当前元素时的“状态”
            int curKey = preSum;
            indexes = map.get(curKey);
            if(null==indexes){
                indexes = new HashSet<>();
                map.put(curKey, indexes);
            }
            indexes.add(i);
        }
        return res;
    }

若仅需知道方案个数或是否存在方案，则实现可简化，代码非常简洁：

    public int subarraySum1(int[] nums, int k) {
        //状态：key为前缀和的值、value为前缀和为该值的位置数
        Map map =new HashMap<>();
        //初始化第一次遇到[0,..j]为一个解时的状态
        map.put(0,1);
        int res=0;
        for(int i=0, preSum=0;i){
            preSum += nums[i];
            res += map.getOrDefault(preSum-k, 0);
            map.put(preSum, map.getOrDefault(preSum,0)+1);
        }
        return res;
    }

与此解法类似的还有题目974.和为k的倍数的子数组数目，其复杂度与上者相同且通用实现与上者大同小异：

    //b-a是k的倍数 <=> b、a除以k的余数相同，因此可通过前缀和的余数来找"补数"的对应关系：preSum[i]%k==preSum[j]%k 且i+1//“补数”：同余数的其他状态
    public int subarraysDivByK1(int[] nums, int k) {
        //状态：key为前缀和模k的值、value为前缀和模k为该值的元素下标列表
        Map> map =new HashMap<>();
        //初始化第一次遇到[0,..j]为一个解时的状态，此时preSum[j]%k为0、i+1为0，故添加{0,[-1]}元素
        map.computeIfAbsent(0, key->(new HashSet())).add(-1);

        int res = 0;
        for(int i=0, preSum=0;i){
            preSum += nums[i];
            //通过状态信息找”补数“并确定是否存在可行解
            int curKey = preSum % k;
            curKey = (curKey+k)%k;//解决负数求模结果为负数的问题，不同语言对负数求模结果可能不一样，有的是正有的是负
            Set indexes = map.get(curKey);
            if(null != indexes && indexes.size()>0 ){//说明存在可行解
                //对于indexes中的每个元素j，nums[j+1,...i]都是一个可行解
                res+=indexes.size();
            }
            //更新到当前元素时的“状态”
            int preKey = curKey;
            indexes = map.get(preKey);
            if(null==indexes){
                indexes = new HashSet<>();
                map.put(preKey, indexes);
            }
            indexes.add(i);
        }
        
        return res;
    }

同样地，若仅需知道方案个数或是否存在方案，则实现可简化，代码非常简洁：

    public int subarraysDivByK(int[] nums, int k) {
        Map map =new HashMap<>();
        map.put(0,1);
        int res=0;
        for(int i=0, preSum=0;i){
            preSum+=nums[i];
            int key = preSum%k;
            key= (key+k)%k;//解决负数求模结果为负数的问题，不同语言对负数求模结果可能不一样，有的是正有的是负
            res+=map.getOrDefault(key,0);
            map.put(key, map.getOrDefault(key,0)+1);
        }
        return res;
    }

该题还有个变种523.和为k的倍数且长度至少为2的子数组是否存在，实现大同小异，可与上面两题对比，体会解法。代码如下：

class Solution {//b-a是k的倍数 <=> b、a除以k的余数相同，因此可通过前缀和的余数来找"补数"的对应关系：preSum[i]%k==preSum[j]%k 且i+1//“补数”：同余数的其他状态
    public boolean checkSubarraySum1(int[] nums, int k) {
        //状态：key为前缀和模k的值、value为前缀和模k为该值的元素下标列表
        Map> map =new HashMap<>();
        //初始化第一次遇到[0,..j]为一个解时的状态，此时preSum[j]%k为0、i+1为0，故添加{0,[-1]}元素
        map.computeIfAbsent(0, key->(new HashSet())).add(-1);

        boolean res = false;
        for(int i=0, preSum=0;i){
            preSum += nums[i];
            //通过状态信息找”补数“并确定是否存在可行解
            int curKey = preSum % k;
            curKey= (curKey+k)%k;//解决负数求模结果为负数的问题，不同语言对负数求模结果可能不一样，有的是正有的是负
            Set indexes = map.get(curKey);
            if(null != indexes && indexes.size()>0 ){//说明存在可行解
                //对于indexes中的每个元素j，nums[j+1,...i]都是一个可行解
                //return true;
                //排除可行解子数组大小为1的情形
                if(!(indexes.size()==1 && indexes.contains(i-1))){
                    res = true;
                    break;
                }
            }
            //更新到当前元素时的“状态”
            int preKey = curKey;
            indexes = map.get(preKey);
            if(null==indexes){
                indexes = new HashSet<>();
                map.put(preKey, indexes);
            }
            indexes.add(i);
        }
        return res;
    }

    public boolean checkSubarraySum2(int[] nums, int k) {
        //状态：key为前缀和模k的值、value为前缀和模k为该值的首个元素下标
        Map map =new HashMap<>();
        //初始化第一次遇到[0,..j]为一个解时的状态
        map.put(0,-1);
        boolean res=false;
        for(int i=0, preSum=0;i){
            preSum += nums[i];
            int key = preSum % k;
            key= (key+k)%k;//解决负数求模结果为负数的问题，不同语言对负数求模结果可能不一样，有的是正有的是负
            Integer index = map.get(key);
            if(null!=index){
                if(i-index>=2){
                    res=true;
                    break;
                }
            }else{//置于else中以让下标尽可能小
                map.put(key, i);
            }
        }
        return res;
    }
}

这里需要注意负数求模的问题：负数求模时不同语言的结果可能不一样（详见这篇文章），为了确保整数 a%k 求模结果为正，可如下处理：mod=(a%k+k)%k

子段和相关的问题可以考虑用前缀和，但是可能并不是最优的解法，如最大子段和用前缀和的效率比动态规划差。

5、差分数组问题

主要适用场景是频繁对原始数组的某个区间的元素进行增或减操作。O(1)时间复杂度对区间元素统一增加a的操作。

原理：针对数组 num[] 建立个等长度的辅助数组diff[]，diff[i] 的值为 num[i]-num[i-1] 。这样对 num[i,...,j] 各元素执行增加a的操作等价于 diff[i]+=a、diff[j+1]-=a。

原数组的差分数组 的前缀和数组就是原数组。

比较简单，详情可参阅 labuladong 差分数组。

6、单链表操作

注：单链表题目涉及到节点指向修改时（如增加、减少、链表合并、反转等）通常会设置一个虚拟头结点，这样可以避免很多边界情况的处理，实现上更简洁。例如：链表合并、删除链表倒数第k个节点等。

单链表节点查找（中点、环检测、环起始点、倒数第k点、相交点等）

（详见labuladong一文搞定单链表解题套路）

1、【中点、环点、倒数k点】相关见前文双指针部分。

2、判断两个单链表公共部分的首节点，即相交的节点：

法1：B加到A末尾、A加到B末尾分别得到两新链，然后分别遍历，相同者记为所求

    // B加到A末尾作为一条链、A加到B末尾作为一条链，然后分别遍历两条链，相等节点记为所求
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        //两单链表不相交时，如下执行最后p、q均为null，故仍能覆盖该case。
        ListNode p=headA, q=headB;
        while(p!=q){
            p=p==null?headB:p.next;
            q=q==null?headA:q.next;
        }
        return p;
    }

法2：转为寻找环节点的问题——B末尾连其首，然后找A的环节点即可。

法3：让长链表的指针先走差值的步数，再齐头并进，那么如果两个指针相等则是相交的位置。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = 0, lenB = 0;
    // 计算两条链表的长度
    for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
        lenA++;
    }
    for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
        lenB++;
    }
    // 让 p1 和 p2 到达尾部的距离相同
    ListNode p1 = headA, p2 = headB;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            p1 = p1.next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            p2 = p2.next;
        }
    }
    // 看两个指针是否会相同，p1 == p2 时有两种情况：
    // 1、要么是两条链表不相交，他俩同时走到尾部空指针
    // 2、要么是两条链表相交，他俩走到两条链表的相交点
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

单链表修改（反转、删除节点等）

模板：

    public ListNode listOpt(ListNode head) {
        ListNode vNode=new ListNode(-1,head);//设置虚拟头结点以减少边界情况讨论
        ListNode pre=vNode, cur=head;
        while(cur!=null){
            ListNode next=cur.next;

            //对当前节点的操作，例如反转节点、删除重复元素等
            // some code logic here

            pre=cur;
            cur=next;
        }
        return vNode.next;
    }

基于该单链表操作的模板，可以解决很多链表修改（删除、反转等）问题，例如【每两个反转、奇数节点串一起放前面、删除链表中的指定元素、删除链表中的重复元素】等，下面的各种反转情形也可由此模板稍加修改解决。

主要有如下几种情形：

反转整个单链表

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

反转单链表开头的若干个元素。b=null时就是上述情形。

/** 反转区间 [a, b) 的元素，注意是左闭右开。当b=null时就是反转整个单链表 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }

    //原头结点后接无需反转者
    a.next=cur;

    // 返回反转后的头结点
    return pre;
}

//另一法，基于反转整个单链表的实现稍加修改。本质上与上法一样
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        if(cur==b) break;
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }

    //原头结点后接无需反转者
    a.next=cur;

    // 返回反转后的头结点
    return pre;
}

反转单链表指定范围内的元素

    //基于单链表反转是算法稍微修改即可
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode pre=null, cur=head, next=null, p=null, q=null;
        int i=1;
        while(cur!=null){
            next=cur.next;
            
            if(left<=i && i<=right){
                cur.next=pre;
                if(i==left){
                    p=cur;
                }
                if(i==right){
                    q=cur;
                    break;
                }
            }

            pre=cur;
            cur=next;
            i++;
        }
        if(p.next!=null){
            p.next.next=q;
        }else{
            head=q;
        }
        p.next=next;

        return head;
    }

反转单链表以k个元素分组的各组元素

ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    // 区间 [a, b) 包含 k 个待反转元素
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) return head;
        b = b.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverse(a, b);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k);
    return newHead;
}



//AC解
    public ListNode reverseKGroup(ListNode head, int k) {
        if(null==head || k<2) return head;

        //不足k个则不反转
        int i=1;
        for(ListNode p=head; p!=null && i<=k; i++, p=p.next){
        }
        if(i<=k) return head;

        // 反转前k个
        ListNode pre=null, cur=head, next=null;
        i=1;
        while(cur!=null && i++ <= k){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }

        //递归
        head.next= reverseKGroup(next,k);
        return pre;
    }

其中前三种依次为从特殊到一般的关系，即前者是后者的特殊情形。

链式结构（链表、树、连式存储的图等）天然很适合递归，故通常都有递归解法。上述各情形的递归解法如下：

//递归解法的效果相当于依次将 底n-1、n-2、...、1个元素插入到第n个元素后面

//反转单链表
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode newHead = reverseList(head.next);

        ListNode tmp = head.next;
        head.next = tmp.next;
        tmp.next = head;

        return newHead;
    }

//反转单链表的前n个元素
    public ListNode reverseList(ListNode head, int n) {
        if(head==null || head.next==null || n<=1){
            return head;
        }
        ListNode newHead = reverseList(head.next, n-1);

        //插入到第n个元素后面
        ListNode tmp = head.next;
        head.next = tmp.next;
        tmp.next = head;
        
        return newHead;
    }

//反转单链表指定区间内的元素
    public ListNode reverseList(ListNode head, int m, int n) {
        if(m==1){
            return reverseList(head, n);
        }
        head.next = reverseList(head.next, m-1, n-1);    
        return head;
    }

递归解法从效果上看相当于依次将 第n-1、n-2、...、1个元素插入到第n个元素后面。

注：虽然看上去递归比较简洁，时间效率和非递归的一样也是O(n)，但递归的空间效率也是O(n)显然比非递归的O(1)高，故实用角度看还是非递归好。

可见，不论是否是递归，都是基于单链表反转的算法模板稍加修改而得！！

实际上，对于反转类链表类的问题，有技巧性更强的解法，所谓的“头插法”，以“反转单链表指定范围内的元素”为例（其他同理），推荐用此法，解法如下：

    public ListNode reverseBetween(ListNode head, int left, int right) {//left, right从1起
        // 设置虚拟头节点，便于处理
        ListNode vNode = new ListNode(0, head);

        //分别表示 整个序列中要反转的首个节点的前一节点、要被反转的首个节点，即p、q分别为left-1处、 left处元素
        ListNode p = vNode, q = p.next;
        for(int i=1;i){
            if(q==null){break;}// null处理
            p=p.next;
            q=p.next;
        }

        //反转：依次将q后面的第一个元素移动到p后面即可
        for(int i=left+1;i<=right;i++){
            if(q.next==null){break;}//null处理

            ListNode tmp = q.next;
            q.next = tmp.next;

            tmp.next = p.next;
            p.next = tmp;
        }
        return vNode.next;
    }

其特点有二：1、增加虚拟头结点来避免边界情况的讨论；2、设置一个固定的“guard”结点，每次将待反转元素移到该节点后面，从而达到反转目的，这不同于上述依次将元素反转指向前一元素的做法。

7、单调栈

用于求解“序列元素中最近的下一个更大元素”的问题。模板代码：

    //推荐此法
    //从后往前遍历，依次将元素入栈；入栈前将栈中不大于当前元素者出栈，然后得到当前元素的”目标值“
    //时间复杂度O(n)，因为每个都入栈一次且最多出栈一次
    public int[] nextGreaterElement1(int[] nums2) {
        int[] res = new int[nums2.length];
        Stack stack = new Stack<>();
        for(int i=nums2.length-1; i>=0; i--){

            while(!stack.isEmpty() && nums2[i]>=stack.peek()){
                stack.pop();
            }
            res[i] = stack.isEmpty()?-1:stack.peek();

            stack.push(nums2[i]);
        }
        return res;
    }


    //从前往后遍历，依次将元素入栈；入栈前将栈中小于当前元素者出栈，并得到这些元素的”目标值“
    //时间复杂度O(n)，因为每个都入栈一次且最多出栈一次
    public int[] nextGreaterElement2(int[] nums) {
        HashMapmap=new HashMap<>();
        Stack stack=new Stack();
        for(int i=0;i){
            while(!stack.isEmpty() && stack.peek()<nums[i] ){
                map.put(stack.pop(),nums[i]);
            }
            stack.push(nums[i]);
        }

        int[] res = new int[nums.length];
        for(int i=0;i){
            res[i]=map.getOrDefault(nums[i],-1);
        }
        return res;
    }

原理：有从后往前（从后往前依次将元素入栈，则栈中自顶向下第一个比当前元素大者记为当前元素的下一个更大元素）或从前往后（从前往后依次将元素入栈，则栈中自顶向下比当前元素小者的下一个元素就是当前元素）两种实现。推荐前者，因为前者更简洁。

栈中放的可以是元素值或元素下标，视具体需求而定。容易发现栈中元素是自栈底到栈顶降序的。

时间复杂度：O(n)，因为每个元素都恰好被入栈一次且最多出栈一次。相比暴力算法的O(n²)好很多了。

若是求更小元素，可同理类比，修改while循环中不等号方向即可。

原理和应用可参阅 labuladong-单调栈。

更多单调栈相关的应用题目可参阅LeetCode单调栈专题，例如：

316.字符串元素去重并保持元素相对顺序：

class Solution {
    //思路见 labuladong https://mp.weixin.qq.com/s/Yq49ZBEW3DJx6nXk1fMusw
    public String removeDuplicateLetters1(String s) {
        if(null==s || s.length()<2){
            return s;
        }

        List list = new ArrayList<>();
        Set set = new HashSet<>();
        Map chCount = new HashMap<>();
        for(int i=0;i){
            char c = s.charAt(i);
            Integer count = chCount.getOrDefault(c,0)+1;
            chCount.put(c, count);
        }
        //System.out.println(chCount);
        for(int i=0;i){
            char c = s.charAt(i);
            chCount.put(c,chCount.get(c)-1);//当前元素后面的同元素个数
            if(set.contains(c)){
                continue;
            }
            //保证字典序：大于当前元素的元素pre 且 当前元素后面还有pre的，删掉pre
            char pre;
            while(!list.isEmpty() && (pre = list.get(list.size()-1))>c && chCount.get(pre)>0){
                list.remove(list.size()-1);
                set.remove(pre);
            }
            //
            list.add(c);
            set.add(c);
        }
        return list.stream().map(String::valueOf).collect(Collectors.joining(""));
    }
    //等价的更简洁的写法
    public String removeDuplicateLetters(String s){
        Stack stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character c=s.charAt(i);
            if(stack.contains(c))
                continue;
            while(!stack.isEmpty()&&stack.peek()>c&&s.indexOf(stack.peek(),i)!=-1)
                stack.pop();
            stack.push(c);
        }

        StringBuilder res = new StringBuilder();
        for(char c : stack){
            res.append(c);
        }
        return res.toString();
    }
}

402.从一个数中移除k个数字使得剩下的数最大/小（镜像问题：选k个数字使得按相对顺序组成一个数最大）：

class Solution {//单调栈同系列题目，见 https://leetcode-cn.com/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/

    //镜像问题：选保持相对数字的k个数字使其组成的数最大

    public String removeKdigits(String num, int k) {
        if(null==num || num.length()==0 || k<1){
            return num;
        }

        int n = num.length();
        Stack stack = new Stack<>();
        //依次将数字入栈，入栈前将比当前元素大的各栈顶元素弹出移除，移除个数达到k即可。可见，栈中元素是升序的。
        //该策略正确性的证明：因为数的高位比低位优先级高，故高位应尽可能小；上述策略保证了最终结果的任一位就是最小的，因为比它大的数字都被弹出了
        for(int i=0;i){
            char c = num.charAt(i);
            while(!stack.isEmpty() && stack.peek()>c && k>0){
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        //没移除足够个数，栈是升序的，故从最后继续移除
        while(k-- > 0){
            stack.pop();
        }

        //包装结果，注意去掉前导0
        // return stack.stream().map(String::valueOf).collect(Collectors.joining(""));
        int i=0;
        while(i < stack.size() && stack.get(i)=='0'){
            i++;
        }
        String res ="";
        while(i < stack.size()){
            res += stack.get(i);
            i++;
        }
        return res.length()==0?"0":res;
        
    }
}

321.从两个数中删除k各数字使得剩下的两数数字组合的结果最大，与上题类似。

可见其特点是用栈来维护单调性的元素并借助该栈来进行元素筛选。

8、借助Map、Set处理求和问题

例如前面【两数和问题、和为k的子数组个数、和为k的倍数的子数组数】等问题的时间复杂度低的解法是借助Map或Set来存储原数或其“补数”（例如后者两者中的“补数”分别减去k的值、除以k的余数），这样可加快查找数据，本质上是空间换时间。

若要求的是方案或方案数则可用Map；若要求的只是方案是否存在则用Set即可。可见，用Map更通用。

9、n数和的通用解法

求k个数和target的通用方法（这里要求k≥2），核心思路：依次固定选取一个元素a，然后转为递归求k-1个数和为target-a的问题，最终变为求2数和问题。

而2数和有两种典型的解法：一种是排序+双指针，即把问题变为有序数组的两数和问题，时间复杂度O(nlgn+n)、空间复杂度O(1)；另一种是借助Map存补数来空间换时间，时间复杂度O(n)、空间复杂度O(n)。

根据两数和用哪种解法，k数和也有对应的两种通用解法：

一种是预先排序：时间复杂度为O(n^(k-1)+nlgn) ，可见=2时为O(nlgn)、k>2时为O(n^(k-1)) ；空间复杂度O(1)。代码：

    // 基于排序预处理来做，时间复杂度为O(n^(k-1)+nlgn) (可见=2时为O(nlgn)、k>2时为O(n^(k-1)) )、空间复杂度O(1)
    public List> nSum1(int[] nums, int s, int e, int n, int target) {
        // !! nums 须确保是有序的 !!

        // 参数检查
        if (s < 0 || e >= nums.length || s > e || e - s + 1 < n || n < 2)
            return Collections.emptyList();
        // 正文
        List> res = new ArrayList<>();
        if (n == 2) {
            int i = s, j = e;
            while (i < j) {// 至少2个元素
                int sum = nums[i] + nums[j];
                if (sum < target)
                    i++;
                else if (sum > target)
                    j--;
                else {
                    List tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    res.add(tmp);
                    i++;
                    j--;
                }

                // 去重，与最近一次处理过的一样者忽略
                while (i > s && i <= e && nums[i] == nums[i - 1])
                    i++;
                while (j < e && j >= s && nums[j] == nums[j + 1])
                    j--;
            }
        } else {// n>2
            for (int i = s; i <= e; i++) {
                List> subs = nSum(nums, i + 1, e, n - 1, target - nums[i]);
                for (List sub : subs) {
                    sub.add(nums[i]);
                    res.add(sub);
                }
                // 去重，后面与当前处理的元素一样者忽略
                while (i < e && nums[i + 1] == nums[i])
                    i++;
            }
        }
        return res;
    }

在实际中元素可能有重复故通常还需要对方案去重，若要求返回的是元素下标则不用去重。

另一种是预处理存补数：时间复杂度为O(n^(k-1))；而因为每个2数和问题（共C(k-2,n)个）都要构建对应的补数Map，故空间复杂度则为O(C(k-2,n)*n)，远大于O(n)。

综上，基于排序的方案更好。

10、top k问题

总结：

三类问题：第k大元素、前k大元素、前k个高频元素。

三种方法：排序、堆、快排划分思想。后两种详见 。

三类问题都可用三种方法来解决，但如果数据是动态增加的则用堆解决更合适、对于前k个高频元素问题用排序或划分方法实现比较麻烦。从时间效率和代码实现综合来看，堆方法最推荐。

以寻找第k大元素为例：

法1：排序后取倒数第k个元素接口，时间复杂度O(nlgn)。

法2：用堆解决的Java实现：时间复杂度O(nlgk)

int findKthLargest(int[] nums, int k) {
    // 小顶堆，堆顶是最小元素
    PriorityQueue 
        pq = new PriorityQueue<>();
    for (int e : nums) {
        // 每个元素都要过一遍二叉堆
        pq.offer(e);
        // 堆中元素多于 k 个时，删除堆顶元素
        if (pq.size() > k) {
            pq.poll();
        }
    }
    // pq 中剩下的是 nums 中 k 个最大元素，
    // 堆顶是最小的那个，即第 k 个最大元素
    return pq.peek();
}

法3：用快排划分思想的Java实现：时间复杂度O(n)

 class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest3(nums,k);
    }

    //通过小顶堆选出最大的k个元素，则最后堆顶元素即为所求。时间复杂度O(nlgk)
    public int findKthLargest1(int[] nums, int k) {
        if(null==nums || nums.length==0) return -1;
        if(k<0 || k>nums.length) return -1;

        PriorityQueue pq = new PriorityQueue<>();
        for(int num:nums){
            pq.offer(num);
            if(pq.size()>k){
                pq.poll();
            }
        }
        return pq.peek();
    }


    //快排思想的快速选择，时间复杂度O(n)
    public int findKthLargest2(int[] nums, int k) {
        if(null==nums || nums.length==0) return -1;
        if(k<0 || k>nums.length) return -1;

        int left=0, right=nums.length-1;
        k = nums.length-k;//升序排序后第k大元素应在的位置
        while(left<=right){
            int p = partition(nums,left,right);
            if(p==k) return nums[p];
            else if(p;
            else right=p-1;
        }
        return -1;
    }
    //把一个元素放到它应在的位置，即其左边均不比其大、右边均不比其小
    private int partition(int[] nums, int s, int e){
        if(s>=e) return s;
        
        int pivot=s;
        int i=s,j=e+1;
        while(true){
            do{i++;}while(!(i==e || nums[i]>=nums[pivot]));
            do{j--;}while(!(j==s || nums[j]<=nums[pivot]));
            if(i<j){
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }else{
                break;
            }
        }

        int tmp=nums[j];
        nums[j]=nums[pivot];
        nums[pivot]=tmp;

        return j;
    }

    //快排思想的快速选择，时间复杂度O(n)。另一种实现
    public int findKthLargest3(int[] nums, int k) {
        return sort(nums,0,nums.length-1,k);
    }

    private int sort(int[] nums, int s, int e, int k){
        if(null==nums || nums.length==0) return -1;
        if(k<0 || k>nums.length) return -1;
        if(s<0 || e>=nums.length) return -1;

        if(s>=e) return nums[s];
        int pivot=s;
        int i=s,j=e+1;
        while(true){
            do{i++;}while(!(i==e || nums[i]>=nums[pivot]));
            do{j--;}while(!(j==s || nums[j]<=nums[pivot]));
            if(i<j){
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }else{
                break;
            }
        }

        int tmp=nums[j];
        nums[j]=nums[pivot];
        nums[pivot]=tmp;

        int tarIndex = nums.length-k;//升序排序后第k大元素应在的位置
        if(j==tarIndex) return nums[j];
        else if(jreturn sort(nums,j+1,e,k);
        else return sort(nums,s,j-1,k); 
    }

}

法2、3相比，后者的时间复杂度低些但前者在实现上更简单，如果数据是动态增加的则用堆解决更合适。

其他示例：LeetCode 347.前k个高频元素、973.最接近远点的k个元素 等，两者的代码实现分别如下，可参阅上述方法在其中的应用：

class Solution {
    //实际上就是统计频次后找前k个元素的问题
    //设元素个数为n，去重后个数为m，则有多种方法：按元素次数排序O(mlgm)、借助小堆找最大的k个频次O(mlgk)、借助快排划分思想O(m)

    public int[] topKFrequent(int[] nums, int k) {
        Map count=new HashMap<>();
        for(int num:nums){
            count.put(num, count.getOrDefault(num,0)+1);
        }

        //按频数构建小顶堆
        PriorityQueue> pq=new PriorityQueue<>( (e1,e2) -> e1.getValue()-e2.getValue() );
        for(Map.Entry entry:count.entrySet()){
            pq.offer(entry);
            if(pq.size()>k){
                pq.poll();
            }
        }
        //
        int[] res=new int[k];
        for(int i=0;i){
            res[i]=pq.poll().getKey();
        }
        return res;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        //return kClosest1(points,k);
        return kClosest2(points,k);
    }

    //法1，堆
    public int[][]  kClosest1(int[][] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((v1,v2)-> (distance(v2)-distance(v1)));
        for(int[] num:nums){
            pq.offer(num);
            if(pq.size()>k){
                pq.poll();
            }
        }
        int[][] res=new int[k][2];
        for(int i=0;i){
            res[i]=pq.poll();
        }
        return res;
    }
    private int distance(int[] point){
        int x=point[0],y=point[1];
        return x*x+y*y;
    }

    //法2，快排思想。确定第k小元素位置
    public int[][]  kClosest2(int[][] nums, int k) {
        int kthMinIndex=sort(nums,0,nums.length-1,k);

        int[][] res=new int[k][2];
        for(int i=0;i){
            res[i]=nums[i];
        }
        return res;
    }
    //按频数升序排序
    private int sort(int[][] nums, int s, int e, int k){
        if(s>=e) return s;
        int pivot=s;
        int i=s,j=e+1;
        while(true){
            do{i++;}while(!(i==e || distance(nums[i])>=distance(nums[pivot]) ));
            do{j--;}while(!(j==s || distance(nums[j])<=distance(nums[pivot]) ));
            if(i<j){
                int[] tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }else{
                break;
            }
        }

        int[] tmp=nums[j];
        nums[j]=nums[pivot];
        nums[pivot]=tmp;

        int tarIndex = k-1;//升序排序后第k小元素应在的位置
        if(j==tarIndex) return j;
        else if(jreturn sort(nums,j+1,e,k);
        else return sort(nums,s,j-1,k); 
    }

}

理论上来说，上面三种方法都可用来解决这些问题，但对于前题如果用排序快排划分思想则需要单独对去重元素排序且需要额外空间存去重元素和频次，故这些方法对该类题可用但不太适用。

综合所知，堆的方法最通用，推荐用堆方法解决top k问题。

变种：不是所有的第k大问题都适合用上述方法解决，这里举几个例子

4.从两个升序数组中找到按升序合并后处于第k小的元素。该场景用上述方法解决的话时间复杂度和空间复杂度高，故不合适，而是利用快排划分思想减少一半搜索范围，分析和实现详见代码：

时间复杂度：O(lg(m+n))

    //从两个有序数组中找合并后的第k小元素，通用。O(lgk)
    private int findKthMin(int[] nums1,int s1,int e1,int[] nums2,int s2,int e2,int k){
        //base case
        if(e1-s1+1+e2-s2+1return -1;//确保元素个数够
        if(s1>e1){//nums1空则直接从nums2确定
            return nums2[s2+k-1];
        }else if(s2>e2){//nums2空则直接从nums1确定
            return nums1[s1+k-1];
        }else if(k==1){
            return nums1[s1]nums1[s1]:nums2[s2];
        }
        //递归
        int len1=e1-s1+1, len2=e2-s2+1;
        int t1=s1+Math.min(k/2,len1)-1;
        int t2=s2+Math.min(k/2,len2)-1;
        if(nums1[t1]//小者则[s1,t1]的元素肯定在两数组合并排序后的第k小元素的前面，借之减少k/2个搜索范围
            return findKthMin(nums1,t1+1,e1,nums2,s2,e2,k-(t1-s1+1));
        }else{
            return findKthMin(nums1,s1,e1,nums2,t2+1,e2,k-(t2-s2+1));
        }
    }

findKthMin

719.从数组中找第k小个距离值。与上题类似，若直接求出所有距离再求解则时间复杂度O(n²)太高了。更好的解法是二分法，分析和实现详见代码：

时间复杂度：O(nlgn+nlgw)

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        return smallestDistancePair1(nums,k);
    }
    //排序后知道了距离的范围，用二分法确定第k小的距离。
    //定义“条件”：f(x):=距离值中不大于x的个数，可知f(x)是单调递增的，故可用二分查找；由于对于距离排序后的任意两个相邻距离i、j，当x∈[i,j)时f(x)的值都是一样的，而此时i才属于距离值域，故需找的是f(x)≥k的最左值
    //O(nlgn+nlgw)，w为最大距离
    public int smallestDistancePair1(int[] nums, int k) {
        Arrays.sort(nums);
        int left=0,right=nums[nums.length-1]-nums[0];
        while(left<=right){
            int mid=left+(right-left)/2;
            if(f(mid,nums)>=k){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    //因数组升序，故可通过双指针O(n)复杂度找不大于指定距离的距离对的个数
    private int f(int distance, int[]nums){
        int n=nums.length;
        int res=0;
        int left=0, right=1;
        while(left){
            while((rightdistance)){
                right++;
            }
            res += right-left-1;
            left++;
        }
        return res;
    }
}

3、其他有趣的问题或小技巧

1、遍历某元素周围的元素：以统一而非手动穷举的方式遍历元素a[i][j]的上下左右元素：（借助方向数组）

// 方向数组 d 是上下左右搜索的常用手法
int[][] d = new int[][]{{-1,0}, {0,1}, {1,0}, {0,-1}};
for (int k = 0; k < 4; k++) {
    int x = i + d[k][0];
    int y = j + d[k][1];
    //(x, y)分别为(i, j)的四周的元素
}

2、String to Integer（atoi）：逐个字符处理，res=res*10+ ch-'0';，但是需要判断溢出，细节处理有点麻烦。可以换个思路判断：res> (Integer.MAX_VALUE-(ch-'0'))/10 时即溢出，这样可以省很多细节。

相关题目：https://leetcode.com/problems/string-to-integer-atoi/#/description

3、矩阵骚操作

（更多可参阅二维数组的花式遍历技巧）

将输入的二维矩阵顺时针旋转90°

直接旋转用编程方式不易实现，变换思路——顺时针旋转90° <=> 沿主对角线镜像（即转置操作）再沿竖中线镜像；同理，逆时针旋转90° <=> 沿次对角线镜像再沿竖中线镜像。因此，只需要编程实现两次反转即可。

当然，也可观察到旋转前后的元素对应关系：matrixnew?[col][n?row?1] = matrix[row][col] ，按该对应关系实现即可。

两种的时间复杂度均为O(n²)，但空间复杂度分别为O(1)、O(n²)。

按螺旋方式打印矩阵：

    public List spiralOrder(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int up=0,down=m-1,left=0,right=n-1;

        List res =new ArrayList<>();
        int cnt=0;//已访问的个数
        while(cnt!=m*n){
            //往右
            if(up<=down){
                for(int i=left;i<=right;i++){
                    res.add(matrix[up][i]);
                    cnt++;
                }
                up++;
            }
            //往下
            if(left<=right){
                for(int i=up;i<=down;i++){
                    res.add(matrix[i][right]);
                    cnt++;
                }
                right--;
            }
            //往左
            if(up<=down){
                for(int i=right;i>=left;i--){
                    res.add(matrix[down][i]);
                    cnt++;
                }
                down--;
            }
            //往上
            if(left<=right){
                for(int i=down;i>=up;i--){
                    res.add(matrix[i][left]);
                    cnt++;
                }
                left++;
            }
        }
        return res;
    }

spiralOrder

蛇形打印方阵：（打印对角行元素，只不过每次右上、左下方向依次交换）

 1 #include 
 2 
 3 #define M 100
 4 
 5 void traverse(int a[][M],int n)
 6 {//每次打印的数据个数为1、2、3、...、n、n-1、...、2、1，依次打印之，只不过右上方向和左下方向时坐标相应地增减下 
 7     int i=0,j=0;
 8     int count,loop;
 9     int dir=1;
10     for(count=1;count<=n;count++)
11     {
12         if(dir==1)
13         {//右上方向 
14             for(loop=1;loop)
15             {
16                 printf("%d ",a[i--][j++]);
17             }
18             printf("%d ",a[i][j]);
19             if(j==n-1) i++;
20             else j++;
21         }
22         else
23         {//左下方向 
24             for(loop=1;loop)
25             {
26                 printf("%d ",a[i++][j--]);
27             }
28             printf("%d ",a[i][j]);
29             if(i==n-1) j++;
30             else i++;
31         }
32         dir=-dir;
33     }
34     
35     for(count=n-1;count>0;count--)
36     {
37         if(dir==1)
38         {
39             for(loop=1;loop)
40             {
41                 printf("%d ",a[i--][j++]);
42             }
43             printf("%d ",a[i][j]);
44             if(j==n-1) i++;
45             else j++;
46         }
47         else
48         {
49             for(loop=1;loop)
50             {
51                 printf("%d ",a[i++][j--]);
52             }
53             printf("%d ",a[i][j]);
54             if(i==n-1) j++;
55             else i++;
56         }
57         dir=-dir;
58     }
59 }
60 
61 int main(int argc,char *argv[])
62 {
63     int n=4;
64     int a[n][M];
65     for(int i=0;i)
66     {
67         for(int j=0;j)
68         {
69             a[i][j]=n*i+j+1;
70         }
71     }
72     traverse(a,n);
73 }

4、n! 中0的个数：直接求n!的值再数0的个数显然数据一大几乎不可能求得。转换方向：由于0由2*5产生（就算是4*5等产生，最终也是由2*5产生），所以n! 中0的个数="2*5"的个数=5的个数（因为一个数的因子中2的个数肯定比5的个数多）

求n! 中5的个数：由于n!=1*2*...*n，（详情参阅：n的阶乘末尾0的个数）

法1：穷举法，求1~n中每个数的因子5的个数

 1 int fun1(int n)
 2 {
 3     int num = 0;
 4     int i,j;
 5     for (i = 5;i <= n;i += 5)
 6     {
 7         j = i;
 8         while (j % 5 == 0)
 9         {
10             num++;
11             j /= 5;
12         }
13     }
14     return num;
15 }

法2：Z = N/5 + N /(5*5) + N/(5*5*5)，直到式子为0

 1 int fun2(int n)
 2 {
 3     int num = 0;
 4     
 5     while(n)
 6     {
 7         num += n / 5;
 8         n = n / 5;
 9     }
10     
11     return num;
12 }

5、给定n、m，求使得 i*j 为完全平方数的序列 (i,j) 的个数，其中 i ∈[1,n]、j ∈[1,m]：

 1     public static void main(String[] args) {
 2         Scanner sc = new Scanner(System.in);
 3         int res = 0;
 4         int n = sc.nextInt();
 5         int m = sc.nextInt();
 6         // ssr(a,b)是整数 等价于sqrt(a*b)是整数 等价于a*b是完全平方数
 7         // 暴力O(n*m)在大数据时超时，以下为O(n*sqrt(m))的方法
 8         for (int i = 1; i <= n; i++) {
 9             // 找到能整除i的最大的完全平方数s
10             int s = 1;
11             for (int x = 2; x * x <= i; x++) {
12                 if (i % (x * x) == 0) {
13                     s = x * x;
14                 }
15             }
16             int r = i / s;// n去掉s因子后的结果
17             // 要使a*b是完全平方数，b需要因子r和一个完全平方数
18             for (int y = 1; y * y * r <= m; y++) {
19                 res++;
20             }
21         }
22         System.out.println(res);
23         sc.close();
24     }

6、给定一个由数字组成的字符串，求出其可能回复的所有IP地址。如"25525512110"对应的ip地址可以为[255,255,121,10, 255,255,12,110]

 1     private static void split(long sVal, int[] segments, int segmentId, List ips) {// split(Long.parseLong(str), new int[4], 3, ipStrs);
 2         if (segmentId == 0) {
 3             if (0 <= sVal && sVal <= 255) {
 4                 ips.add(sVal + "," + segments[1] + "," + segments[2] + "," + segments[3]);
 5             }
 6         } else {
 7             int mod, segmentVal;
 8             for (int exp = 1; exp <= 3; exp++) {
 9                 mod = (int) Math.pow(10, exp);
10                 segmentVal = (int) (sVal % mod);
11                 if (0 <= segmentVal && segmentVal <= 255) {
12                     segments[segmentId] = segmentVal;
13                     split(sVal / mod, segments, segmentId - 1, ips);
14                 }
15             }
16         }
17     }

7、给定一个随机生成器，生成0和1的概率分别为0.5，如何构造生成0和1的概率分别为0.3、0.7的随机生成器？

法：对0、1进行组合。

 1 int MyFun()
 2 {
 3   int n1=fun();
 4   int n2=fun();
 5   int n3=fun();
 6   int n4=fun();
 7   int n=n1;
 8   n|=n2<<1;
 9   n|=n3<<2;
10   n|=n4<<3;
11   if(n<=2) return 0;
12   else if(n<10) return 1;
13   else return MyFun();
14 }

随机生成器生成0和1的概率分别为p和1-p，如何构造等概率随机生成0和1的生成器？

法：由于生成01和10的概率均为p(1-p)，所以可以根据之实现：

 1 int MyFun()
 2 {
 3   int n1=fun();
 4   int n2=fun();
 5   int n=n1();
 6   n|=n2<<1;
 7   if(n==2) return 0;
 8   else if(n==1) return 1;
 9   else return MyFun();
10 }

8、大整数乘法（字符串整数乘法）

大整数通常超过了整型的表示范围，因此用字符串表示整数，如 "321" * "753"，求其同样用字符串表示的结果。LeetCode-43

思路：模拟竖式计算，设每个数下标从右到左且从0起，num1的每位数分别与num2的每位数相乘。用到的技巧：

num1[i]*num2[j]结果的个位刚好位于  [i+j]  位置上；

每位相乘不计算进位，而是最后统一处理进位。

代码：时间复杂度O(mn)、空间复杂度O(m+n)，m、n分别为两个串的长度

class Solution {//设每个数下标从右到左且从0起。模拟竖式计算：num1的每位数分别与num2的每位数相乘，num1[i]*num2[j]结果位于[i+j]中，每位相乘不计算进位，而是最后统一处理进位

    public String multiply(String num1, String num2) {

        int m=num1.length();
        int n=num2.length();
        int []tmpRes=new int[m+n];
    
        for(int i=0;i){
            for(int j=0;j){
                int mul=(num1.charAt(m-1-i)-'0') * (num2.charAt(n-1-j)-'0');
                tmpRes[i+j]+=mul;
            }   
        }

        //处理进位
        for(int i=0;i){
            if(tmpRes[i]>9){
                tmpRes[i+1]+=tmpRes[i]/10;
                tmpRes[i]%=10;
            }
        }

        //去除前导0
        int i=m+n-1;
        while(i>0 && tmpRes[i]==0){
            i--;
        }
        //转为字符串
        StringBuffer sb=new StringBuffer();
        for(;i>=0 ; i--){
            sb.append((char)(tmpRes[i]+'0'));
        }
        return sb.toString();
    }

multiply string

9、

O(1)时间复杂度等概率随机选择一个元素

要使得时间复杂度为O(1)的选择，底层只能用数组存储元素、且数组是紧凑的（用Set、Map等也无法满足要求），这样我们就可以直接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素。

使用示例见 380.O(1)时间复杂度实现插入、删除、查找、随机选择、381.允许元素重复的变种，前三种操作用Map可满足O(1)、最后者用数组可满足等概率和O(1)时间复杂度，故思路就是 数组+Map 空间换时间，代码：

class RandomizedSet {
    Stack nums;
    Map map;
    Random random = new Random();
    public RandomizedSet() {
        nums = new Stack<>();
        map = new HashMap<>();
    }
    
    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }else{
            nums.push(val);
            map.put(val, nums.size()-1);
            return true;
        }
    }
    
    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }else{
            int index = map.get(val);
            nums.set(index, nums.get(nums.size()-1));
            map.put(nums.get(index), index);
            nums.pop();
            map.remove(val);
            return true;
        }
    }
    
    public int getRandom() {
        return nums.get( random.nextInt(nums.size()) );
    }
}

O(1)时间复杂度计算滑动窗口内的最大值（最小值同理）（见 LeetCode 239.滑动窗口中的最大值）。代码：

class Solution {//单调队列解法，时间复杂度O(n)。队列里可存元素下标或元素值，视具体需求而定

    public int[] maxSlidingWindow(int[] nums, int k) {
        return maxSlidingWindow2(nums, k);
    }


    public int[] maxSlidingWindow1(int[] nums, int k) {
        if(null==nums || nums.lengthreturn null;

        int[] res = new int[nums.length-k+1];
        MaxQueue record = new MaxQueue();
        for(int i=0; i){
            record.add(nums[i]);
            int windowLeft=i-k+1;
            if(windowLeft>=1){
                record.remove(nums[windowLeft-1]);
            }
            if(windowLeft>=0){
                res[windowLeft] = record.getMax();
            }
        }
        return res;
    }

    /** 以O(1)时间复杂度维护窗口内最大值的数据结构，名为单调队列，队列里存元素值 */
    class MaxQueue{
        private LinkedList list = new LinkedList<>();

        /** 返回最大值，不存在则返回null */
        public Integer getMax(){
            return list.isEmpty()?null:list.peek();
        }

        public void add(int val){
            while(!list.isEmpty() && list.peekLast()//注意是严格小于，因为元素允许重，例如最大值add了两次则rermove一次后getMax应仍是该最大值
                list.pollLast();
            }
            list.offer(val);
        }

        /** 删除指定元素 */
        public void remove(int val){
            //由于查询方法只有获取最大值，故若不是删除最大值则啥也不用操作
            if(!list.isEmpty() && val==list.peek()){
                list.poll();
            }
        }
    }

    //本质上与上法一样，只不过直接在方法内展开了。这里单调队列里存的是元素下标。
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if(null==nums || nums.lengthreturn null;

        int[] res = new int[nums.length-k+1];
        LinkedList list = new LinkedList<>();//单调链表，首元素为最大值
        for(int i=0; i){
            //新值存入窗口
            while(!list.isEmpty() && nums[list.peekLast()]<nums[i]){
                list.pollLast();
            }
            list.offer(i);
            //最早值从窗口移除。lazy remove: 因要求的是最大值，故若非最大值就不移除
            int windowLeft=i-k+1;
            if(windowLeft>=1){
                if(!list.isEmpty() && list.peek()==windowLeft-1){
                    list.poll();
                }
            }
            //获取窗口内最大值
            if(windowLeft>=0){
                res[windowLeft] = nums[list.peek()];
            }
        }
        return res;
    }

}

原理：维护有序链表，在插入和删除操作上做文章，详见代码注释。链表中放的可以是元素值或元素下标，视具体需求而定。

问题整体时间复杂度：O(n)。因为每个元素恰好被放入链表一次且最多被被删掉一次。比基于大顶堆求方案的O(nlgn)效率高。

 

O(1)时间复杂度计算栈内的最大值（最小值同理）（见 LeetCode 165.最小栈）：思路很简单，同时保存到当前栈顶元素时的最大值。

10、包含负数的整数求模

详见这篇文章。

在数学理论中，余数是非负数，然而在不同的编程语言中对包含负数的除法实现可能不同，导致余数也不同，例如 -3%5 = -1余2 或 = 0余-3。

大多数语言的处理方式都与 C/Java 一致，采用了 truncate 除法，其特点是余数与被除数的正负符号相同，因此-3%5=-1、3%(-5)=3。

当然，不管哪种实现都有如下特点：

都有“余数的绝对值<除数的绝对值”；

为了确保 a%k 为正，可做如下处理：mod=(a%k+k)%k 。这个特性在前面“前缀和”一节中的子数组和问题中有用到。

 

11、优势洗牌（即田忌赛马）：给定两数组A[]、B[]，元素值表示马的战力。要求改变A的元素顺序使得马按序依次对战后胜场最多。

解法：对B降序排序后从大到小确地每个元素b的对手A元素：从A找未对战过的最大战力的马，若该马能战得过b则取该马、否则取A未战斗过的最小战力马给b送人头。

实现：

class Solution {
    //两个数组元素个数允许不同，但前者个数须不少于后者
    //允许元素重复
    public int[] advantageCount(int[] nums1, int[] nums2) {
        if(nums1==null || nums2==null) return null;
        if(nums1.length < nums2.length) return null;

        //对nums2排序，需同时记录排序前元素位置
        int n = nums2.length;
        // PriorityQueue maxPq = new PriorityQueue<>((v1, v2)-> v2[1]-v1[1]);
        // for(int i=0;i//     maxPq.add(new int[]{i, nums2[i]});
        // }//借助优先队列实现排序
        int[][] nums2Sort = new int[n][2];
        for(int i=0;i){
            nums2Sort[i][0] = i;
            nums2Sort[i][1] = nums2[i];
        }
        Arrays.sort(nums2Sort, (v1, v2)-> v2[1]-v1[1]);

        //对nums1排序
        Arrays.sort(nums1);

        
        //对战
        int[] res = new int[n];
        int left=0, right=nums1.length-1;
        for(int i=0;i){
            //int[] ele = maxPq.poll();
            int[] ele = nums2Sort[i];
            if(nums1[right]>ele[1]){
                res[ele[0]] = nums1[right];
                right--;
            }else{
                res[ele[0]] = nums1[left];
                left++;
            }
        }
        return res;
    }
}

advantageCount

12、659.分隔数组为若干个不少有指定长度的连续子序列——给定一堆牌（一个元素可重的排好序的数字序列），判断是否可按若干个“顺子”将牌连续出完。其实就是判断斗地主游戏中能否按连续顺子打出“春天”。

法1：依次判断每个元素，若可加到已有序列后面则选最短的序列加到其后，否则作为新序列。

实现1：上述方案的翻译，时间复杂度O(n²)

    //法1，O(n2)。模拟：扫描一遍，对于每个元素看是否可以接到已有序列后面，若可以则选可以的序列中最短的一个接上，否则成立新序列。
    public boolean isPossible1(int[] nums) {
        int minLen=3;
        Map> end = new HashMap<>();//存储以某元素结尾的序列起点列表，列表中元素可能有重，例如输入为[1,1,2,2]时
        for(int num:nums){
            // List starts=end.get(num-1);
            // if(null!=starts && !starts.isEmpty()){//可接到已有序列后面，取序列最短者（即start最大者）接上
            //     //确定最短序列的起始点
            //     int indexOfMaxStart=0;
            //     for(int i=1;i//         if(starts.get(indexOfMaxStart)//     }
            //     int start=starts.remove(indexOfMaxStart);//元素可能有重故通过下标删
            //     starts=end.getOrDefault(num, new ArrayList());
            //     starts.add(start);
            //     end.put(num, starts);
            // }else{//无法接到已有序列后面
            //     starts=end.getOrDefault(num, new ArrayList());
            //     starts.add(num);
            //     end.put(num,starts);
            // }

            //以下为以上的简化版
            List starts=end.get(num-1);
            int start;
            if(null != starts && !starts.isEmpty()){//可接到已有序列后面，找出序列最短者（即start最大者）
                //确定最短序列的起始点
                int indexOfMaxStart=0;
                for(int i=1;i){
                    if(starts.get(indexOfMaxStart)i;
                }
                start=starts.remove(indexOfMaxStart);//元素可能有重故通过下标删
            }else{
                start=num;
            }
            //成立新序列
            starts=end.getOrDefault(num, new ArrayList());
            starts.add(start);
            end.put(num,starts);
            //System.out.println(end);
        }
        //检查各序列长度是否合格
        for(Map.Entry> entry:end.entrySet()){
            int e=entry.getKey();
            for(int s:entry.getValue()){
                if(e-s+1<minLen){
                    return false;
                }
            }
        }
        return true;
    }

实现2：优化——借助堆找最短序列，时间复杂度O(nlgn)

    //法2：O(nlgn)。法1的改进版，以优先队列存终点相同的序列序列起点列表
    public boolean isPossible2(int[] nums) {
        int minLen=3;
        Map> end = new HashMap<>();//存储以某元素结尾的序列起点列表，列表中序列短者放前面即起点值大者放前面
        for(int num:nums){
            PriorityQueue starts=end.get(num-1);
            int start;
            if(null != starts && !starts.isEmpty()){//可接到已有序列后面，找出序列最短者（即start最大者）
                start=starts.poll();
            }else{
                start=num;
            }
            //成立新序列
            starts=end.getOrDefault(num, new PriorityQueue((v1,v2)->v2-v1));
            starts.offer(start);
            end.put(num,starts);
        }
        //检查各序列长度是否合格
        for(Map.Entry> entry:end.entrySet()){
            int e=entry.getKey();
            PriorityQueue starts=entry.getValue();
            if(!starts.isEmpty()){//堆顶者是最短序列故不用循环了
                int s=starts.peek();
                if(e-s+1<minLen){
                    return false;
                }
            }
        }
        return true;
    }

法2：与上法类似，只不过成立新序列时就检查序列长度约束，因此若可加到序列后则随机选一个即可而不用选最小者，从而时间复杂度O(n)

    //法3：O(n)。
    public boolean isPossible3(int[] nums) {
        int minLen=3;
        Map> end = new HashMap<>();//存储以某元素结尾的序列起点列表，列表中元素可能有重，例如输入为[1,1,2,2]时
        Map unusedCount = new HashMap<>();//存尚未被加入到序列的某个元素的个数
        for(int num:nums){
            unusedCount.put(num,unusedCount.getOrDefault(num,0)+1);
        }

        for(int num:nums){
            //被新建子序列时提前用完了
            if(unusedCount.get(num)<1) continue;

            List starts=end.get(num-1);
            if(null!=starts && !starts.isEmpty()){//可接到已有序列后面，取序列最短者（即start最大者）接上
                //因为新建序列时保证了长度，故随便选一个序列即可
                int indexOfMaxStart=0;
                int start=starts.remove(indexOfMaxStart);//元素可能有重故通过下标删
                starts=end.getOrDefault(num, new ArrayList());
                starts.add(start);
                end.put(num, starts);
                //
                unusedCount.computeIfPresent(num, (key, oldVal)->oldVal-1);
            }else{//无法接到已有序列后面
                //校验从当前元素起至少有minLen个存在，若都存在则对这些元素归为一个新序列
                for(int base=num,i=0;i){
                    num=base+i;
                    if(unusedCount.getOrDefault(num,0)<1){
                        return false;
                    }
                    unusedCount.computeIfPresent(num, (key, oldVal)->oldVal-1);
                }
                starts=end.getOrDefault(num, new ArrayList());
                starts.add(num-minLen+1);
                end.put(num, starts);
            }
        }
        //System.out.println(end);
        return true;
    }

13、4.寻找两个正序数组的中位数。 

朴素的方法是对两个数组合并排序后取中位数即可，但时间复杂度高。这里提供另外三种解法：

法1：模拟二路归并处理过程，计数到一半个数的元素时即得到中位数。O(m+n)

法2：转为寻找两正序数组的第k小的元素，寻找第k小的过程类似于快排划分的过程。O(lg(m+n))

法3：划分思想，将两个数组分别分为两部分，两左部分的元素个数和为总体的一半。然后找使得划分位置的【两个左边界元素的最大值≤两个右边界元素的最小值】的划分即可。可顺序找该位置甚至用二分查找该位置，后者O(lg(min{m,n}))。

代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        return findMedianSortedArrays3(nums1,nums2);
    }
    //法1，二路归并思想。O(m+n)，O(1)
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int m=nums1.length, n=nums2.length;
        int total=m+n;
        int head1=0, head2=0;//下一个要比较的元素位置对
        int cnt=0, last=-1, cur=-1;//总元素个数、最近两个合并的元素值
        while(cnt< total){
            if(head1==m){
                cur=nums2[head2++];
            }else if(head2==n){
                cur=nums1[head1++];
            }else if(nums1[head1]<=nums2[head2]){
                cur=nums1[head1++];
            }else{
                cur=nums2[head2++];
            }
            cnt++;
            if((total%2==1) && (cnt== (1+total)/2)){//共奇数个，中间即是
                return cur;
            }else if((total%2==0) && (cnt== (1+total)/2+1)){//供偶数个，中间两个平均
                return (last+cur)/2.0;
            }else{
                ;
            }
            last=cur;
        }
        return -1;
    }
    //法2，转为找两数组合并后的第k小元素。O(lg(m+n))，O(1)
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int len1=nums1.length, len2=nums2.length;
        int total=len1+len2;
        if(total%2==0){
            int kLeft= findKthMin(nums1,0,len1-1,nums2,0,len2-1,total/2);
            int kRight=findKthMin(nums1,0,len1-1,nums2,0,len2-1,total/2+1);
            return (kLeft+kRight)/2.0;
        }else{
            return findKthMin(nums1,0,len1-1,nums2,0,len2-1,total/2+1);
        }
    }
    //从两个有序数组中找合并后的第k小元素，通用。O(lgk)，O(1)
    private int findKthMin(int[] nums1,int s1,int e1,int[] nums2,int s2,int e2,int k){
        //base case
        if( k<1 || e1-s1+1+e2-s2+1return -1;//确保元素个数够
        if(s1>e1){//nums1空则直接从nums2确定
            return nums2[s2+k-1];
        }else if(s2>e2){//nums2空则直接从nums1确定
            return nums1[s1+k-1];
        }else if(k==1){
            return nums1[s1]nums1[s1]:nums2[s2];
        }
        //递归
        int len1=e1-s1+1, len2=e2-s2+1;
        int t1=s1+Math.min(k/2,len1)-1;
        int t2=s2+Math.min(k/2,len2)-1;
        if(nums1[t1]//小者则[s1,t1]的元素肯定在两数组合并排序后的第k小元素的前面，借之减少k/2个搜索范围
            return findKthMin(nums1,t1+1,e1,nums2,s2,e2,k-(t1-s1+1));
        }else{
            return findKthMin(nums1,s1,e1,nums2,t2+1,e2,k-(t2-s2+1));
        }
    }
    //法3（推荐），划分思想：对两个数组分别都划分为左右两部分，由”中位数“的含义知，只要第一个数组左部分个数确定了则第二个数组左部分个数唯一也确定。因此，只要从第一个数组中找到满足如下条件的划分位置即可：使得划分位置的【两个左边界元素的最大值≤两个右边界元素的最小值】，该位置是唯一的。
    //非二分时O(min(m,n))、二分时O(lg(min(m,n)))，O(1)
    public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int m=nums1.length, n=nums2.length;
        if(m>n) return findMedianSortedArrays3(nums2,nums1);//确保第一个数组元素个数更少，从而减少循环次数。当然，也可不进行该处理
        int total=m+n;
        int leftCnt=total/2;//两数组合并后左半部分的元素个数，total偶数时对半、奇数时比右部分少1

        //确定第一个数组左部分划分个数的范围：aLeftCnt+bLeftCnt=leftCnt，且aLeftCnt∈[0,m]、bLeftCnt∈[0,n]，据之可得aLeftCnt的取值范围[low,high]
        int low=Math.max(0,leftCnt-n), high=Math.min(m,leftCnt);
        //顺序查找或二分查找目标位置
        while(low<=high){
            //1.1 二分查找
            // int aLeftCnt=low+(high-low)/2;
            // int bLeftCnt=leftCnt-aLeftCnt;
            // if(m-aLeftCnt>0 && bLeftCnt>0 && nums1[aLeftCnt]//     low=aLeftCnt+1;
            //     continue;
            // }else if(aLeftCnt>0 && n-bLeftCnt>0 && nums1[aLeftCnt-1]>nums2[bLeftCnt]){
            //     high=aLeftCnt-1;
            //     continue;
            // }

            //1.2 顺序查找
            int aLeftCnt=low++;
            int bLeftCnt=leftCnt-aLeftCnt;

            //2 判断是否 leftMax≤rightMin
            int leftMax=Integer.MIN_VALUE,rightMin=Integer.MAX_VALUE;
            if(aLeftCnt>0 || bLeftCnt>0){
                if(aLeftCnt>0 && bLeftCnt>0){
                    leftMax= nums1[aLeftCnt-1]>=nums2[bLeftCnt-1]?nums1[aLeftCnt-1]:nums2[bLeftCnt-1];
                }else{
                    leftMax= aLeftCnt>0?nums1[aLeftCnt-1]:nums2[bLeftCnt-1];
                }
            }
            if(m-aLeftCnt>0 || n-bLeftCnt>0){
                if(m-aLeftCnt>0 && n-bLeftCnt>0){
                    rightMin= nums1[aLeftCnt]<=nums2[bLeftCnt]?nums1[aLeftCnt]:nums2[bLeftCnt];
                }else{
                    rightMin= m-aLeftCnt>0?nums1[aLeftCnt]:nums2[bLeftCnt];
                }
            }
            if(leftMax<=rightMin){
                return total%2==0?(leftMax+rightMin)/2.0:rightMin;
            }
    
        }
        return -1;
    }
}

14、两个数组的元素是数字0-9，如何在两个数中各自的数字相对顺序保持不变的情况下合并组成的数最大？

示例：[2,5,6]、[7,7,6,2] 合并的最大值是 [7,7,6,2,5,6,2] 而非 [7,7,6,2,2,5,6]

思路：按字典序比较两个数，大者首元素被取。实际上类似于二路归并思路，只不过元素值一样时需要往后看不一样的第一个数字谁大来确定取谁。

    public boolean gerater(int[]num1,int i1, int[]num2, int i2){
        if(num1==null) return false;
        if(num2==null) return true;

        int m=num1.length;
        int n=num2.length;
        while(i1num2[i2]){
            i1++;
            i2++;
        }
        if(i1>=m) return false;
        if(i2>=n) return true;
        return num1[i1]>=num2[i2]?true:false;
    }

15、Java 中 int[] 和 List 间的转换。

刷题时通常在实现方法中会用到List来动态增减数据，但方法返回类型是 int[] ，可以自己在尾部进行包装转换但对于这种无任何技术含量的工作用语法糖最好不过了，从Java 8起可借助Stream实现两者互相转换：

        int[] num = new int[] { 2, 4, 1, -4, 7 };
        // int[] 转 List
        List list = Arrays.stream(num).boxed().collect(Collectors.toList());
        // List 转 int[]
        num = list.stream().mapToInt(Integer::intValue).toArray();

float等其他类型同理。

 

16、股票买卖的最佳时机

（可参阅 labuladong-一文团灭LeetCode股票买卖问题） 

问题：给定数组表示某只股票每天的价格，求最多允许k次交易时的最大利润。这里要求卖了后才能再买即手里最多一手。

解决思路（动态规划的典型应用）：

设dp[i][k][j] 表示最多允许k次交易的前提下前i天内、状态为j（用1、0分别表示是否有股票）时的手上的资金（或叫利润，可设初始为0），其中i、k 为正整数且k∈[1,i/2]。状态转换：

dp[i][k][0] = max( dp[i-1][k][0] , dp[i-1][k][1]+prices[i] ) ，第i天结束后无股票，则要么当天没操作、要么当天卖出了。
dp[i][k][1] = max( dp[i-1][k][1] , dp[i-1][k-1][0]-prices[i] )，第i天结束后有股票，则要么当天没操作，要么当天买入了。

注：

买入后卖出算一次交易，可认为交易次数就是买的次数，当然也可认为是卖的次数，只要保持一致即可，采用哪种对结果无影响但对递推方程式和base case初始化有影响，这里用前者。

当k为1时dp[i-1][k-1][0]=0、当k无穷大时（实际上这里k>n/2即可认为无穷大）可认为k和k-1相等，故此时递推式与k之无关；

这里递推式是三维数组，实际上也可定义成两个二维数组dp1[i][k]、dp2[i][k]分别表示第i天结束后有、无股票时的手上的现金。

实现：

class Solution {
    public int maxProfit(int k, int[] prices) {
        //return maxProfit1(prices,k);
        return maxProfitFull(prices,k,1,0);
    }

    //一只股票的买卖问题（要求卖了后才能再买即手里最多一手）：dp[i][k][j] 表示最多允许k次交易的前提下前i天内、状态为j（用1、0分别表示是否有股票）时的手上的资金（或者利润，可设初始为0），i、k 为正整数且k∈[1,i/2]
    // dp[i][k][0]=max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]) ，第i天结束后无股票，则要么当天没操作、要么当天卖出了。
    // dp[i][k][1]=max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])，第i天结束后有股票，则要么当天没操作，要么当天买入了。
    //注意：买入后卖出算一次交易，可认为交易次数就是买的次数，当然也可认为是卖的次数，只要保持一致即可，采用哪种对结果无影响但对递推方程式和base case初始化有影响，这里用前者；当k为1时dp[i-1][k-1][0]=0、当k无穷大时（实际上这里k>n/2即可认为无穷大）可认为k和k-1相等，故此时递推式与k之无关；这里递推式是三维数组，实际上也可定义成两个二维数组dp1[i][k]、dp2[i][k]分别表示第i天结束后有、无股票时的手上的现金
    //时间复杂度O(nk)、空间复杂度O(nk)
    public int maxProfit1(int[] prices, int maxK) {
        int n=prices.length;
        maxK=Math.min(maxK, n/2);//取有效的k即可，不然过大会内存溢出

        int[][][] dp=new int[n+1][maxK+1][2];//i=0||k==0时值为0，让语言自动初始化而不用coder手动初始化
        for(int i=1;i<=n;i++){
            for(int k=1;k<=maxK;k++){
                if(i==1){//第一天
                    dp[i][k][0]=0;//第一天结束后无股票，由于是第一天所以没得卖，从而说明当天只能啥也没干
                    dp[i][k][1]=-prices[i-1];//第一天结束后有股票，由于是第一天，从而说明当天买入了
                }else{
                    dp[i][k][0]=Math.max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1]);
                    dp[i][k][1]=Math.max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i-1]);
                }
                //System.out.println(i+" "+k+" "+dp[i][k][0]+" "+dp[i][k][1]);
            }
        }
        return dp[n][maxK][0];
    }

    //递推式中i维度的i状态仅与i-1状态有关，故实现时可省略i维度的数组。k维度则不可省，因与k、k-1状态都有关。
    //时间复杂度O(nk)、空间复杂度O(k)
    public int maxProfit2(int[] prices, int maxK) {
        int n=prices.length;
        maxK=Math.min(maxK, n/2);

        int[][] dp=new int[maxK+1][2];//i=0||k==0时值为0，让语言自动初始化而不用coder手动初始化
        for(int i=1;i<=n;i++){
            for(int k=1;k<=maxK;k++){
                if(i==1){//第一天
                    dp[k][0]=0;//第一天结束后无股票，由于是第一天所以没得卖，从而说明当天只能啥也没干
                    dp[k][1]=-prices[i-1];//第一天结束后有股票，由于是第一天，从而说明当天买入了
                }else{
                    dp[k][0]=Math.max(dp[k][0], dp[k][1]+prices[i-1]);
                    dp[k][1]=Math.max(dp[k][1], dp[k-1][0]-prices[i-1]);
                }
                //System.out.println(i+" "+k+" "+dp[i][k][0]+" "+dp[i][k][1]);
            }
        }
        return dp[maxK][0];
    }

    //拓展——大一统方法，加冷冻期（今天卖出后隔几天能卖，cooldown≥1）和每笔交易（买入再卖出是一笔交易）费用
    // dp[i][k][0]=max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]+fee) ，第i天结束后无股票，则要么当天没操作、要么当天卖出
    // dp[i][k][1]=max(dp[i-1][k][1], dp[i-cooldown][k-1][0]-prices[i])
    public int maxProfitFull(int[] prices, int maxK, int cooldown, int fee) {
        int n=prices.length;

        if(maxK>n/2) return maxProfitFull(prices,n/2,cooldown,fee);
        //maxK=Math.min(maxK, n/2);//取有效的k即可，不然过大会内存溢出

        int[][][] dp=new int[n+1][maxK+1][2];//i=0||k==0时值为0，让语言自动初始化而不用coder手动初始化
        for(int i=1;i<=n;i++){
            for(int k=1;k<=maxK;k++){
                if(i==1){//第一天
                    dp[i][k][0]=0;//第一天结束后无股票，由于是第一天所以没得卖，从而说明当天只能啥也没干
                    dp[i][k][1]=-prices[i-1];//第一天结束后有股票，由于是第一天，从而说明当天买入了
                }else{
                    dp[i][k][0]=Math.max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1]-fee);
                    dp[i][k][1]=Math.max(dp[i-1][k][1], i-cooldown<0?0:dp[i-cooldown][k-1][0]-prices[i-1]);
                }
                //System.out.println(i+" "+k+" "+dp[i][k][0]+" "+dp[i][k][1]);
            }
        }
        return dp[n][maxK][0];
    }
}

时间复杂度O(nk)、空间复杂度O(nk)或O(k)。注意这有两种实现：一种是直接翻译上述递推式；另一种是因递推式中i维度的i状态仅与i-1状态有关，故实现时可省略i维度的数组而不用三维组。

另外这里还提供了带冷冻期cooldown、交易费fee的扩展实现，下面实现一节将会讲到相关题目。

应用：LeetCode六道股票买卖题目都可由上述模板解决。知道模板实现即可，所有变种问题都可由该模板推出。

188.买卖股票的最佳时机4，即上述问题。

121.买卖股票的最佳时机1。上述问题的k=1的情形，解决：

public class Solution {
    public int maxProfit(int[] prices) {
        //return maxProfit3(prices);
        return maxProfit2(prices,1);
    }



    // 6道股票买卖题目一个模板搞定（https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv），其中k=1即此题的解。
    //时间复杂度O(nk)、空间复杂度O(nk)
    public int maxProfit1(int[] prices, int maxK) {
        int n=prices.length;
        maxK=Math.min(maxK, n/2);//取有效的k即可，不然过大会内存溢出

        int[][][] dp=new int[n+1][maxK+1][2];//i=0||k==0时值为0，让语言自动初始化而不用coder手动初始化
        for(int i=1;i<=n;i++){
            for(int k=1;k<=maxK;k++){
                if(i==1){//第一天
                    dp[i][k][0]=0;//第一天结束后无股票，由于是第一天所以没得卖，从而说明当天只能啥也没干
                    dp[i][k][1]=-prices[i-1];//第一天结束后有股票，由于是第一天，从而说明当天买入了
                }else{
                    dp[i][k][0]=Math.max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1]);
                    dp[i][k][1]=Math.max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i-1]);
                }
                //System.out.println(i+" "+k+" "+dp[i][k][0]+" "+dp[i][k][1]);
            }
        }
        return dp[n][maxK][0];
    }

    //递推式中i维度的i状态仅与i-1状态有关，故实现时可省略i维度的数组。k维度则不可省，因与k、k-1状态都有关。
    //时间复杂度O(nk)、空间复杂度O(k)
    public int maxProfit2(int[] prices, int maxK) {
        int n=prices.length;
        maxK=Math.min(maxK, n/2);

        int[][] dp=new int[maxK+1][2];//i=0||k==0时值为0，让语言自动初始化而不用coder手动初始化
        for(int i=1;i<=n;i++){
            for(int k=1;k<=maxK;k++){
                if(i==1){//第一天
                    dp[k][0]=0;//第一天结束后无股票，由于是第一天所以没得卖，从而说明当天只能啥也没干
                    dp[k][1]=-prices[i-1];//第一天结束后有股票，由于是第一天，从而说明当天买入了
                }else{
                    dp[k][0]=Math.max(dp[k][0], dp[k][1]+prices[i-1]);
                    dp[k][1]=Math.max(dp[k][1], dp[k-1][0]-prices[i-1]);
                }
                //System.out.println(i+" "+k+" "+dp[i][k][0]+" "+dp[i][k][1]);
            }
        }
        return dp[maxK][0];
    }

    //上述动规中K=1的简化版，此时dp[i-1][k-1][0]=0，故递推式如下，可见与k无关了；进一步地，因当前状态只与前一个i有关故可以省去空间数组。
    // dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
    // dp[i][1]=Math.max(dp[i-1][1], -prices[i]);
    //时间复杂度O(n)、空间复杂度O(1)
    public int maxProfit3(int[] prices) {
        int n=prices.length;

        int dp_i_0=0, dp_i_1=0;//初始值任意，因为下面i=1时会初始化。用dp[2]更直观？
        for(int i=1;i<=n;i++){
            if(i==1){//第一天
                dp_i_0=0;//第一天结束后无股票，由于是第一天所以没得卖，从而说明当天只能啥也没干
                dp_i_1=-prices[i-1];//第一天结束后有股票，由于是第一天，从而说明当天买入了
            }else{
                dp_i_0=Math.max(dp_i_0, dp_i_1+prices[i-1]);
                dp_i_1=Math.max(dp_i_1, -prices[i-1]);
            }
            //System.out.println(i+" "+dp_i_0+" "+dp_i_1);
        }
        return dp_i_0;
    }

    //针对本题的解法
    public int maxProfit4(int[] prices) {
        int minprice=Integer.MAX_VALUE,maxProfit=0;
        for(int i=0;i)
        {
            if(prices[i]prices[i];
            else if(maxProfitminprice;
        }
        return maxProfit;
    }



}

法1：直接用上述模板AC。

法2：上述模板中k=1时，dp[i-1][k-1][0]=0 故递推式只与 i-1状态有关，从而可去掉辅助数组达到O(1)空间复杂度。

法3：扫一遍的过程中动态计算若当天卖出时的最大利润。

123.买卖股票的最佳时机3。上述问题的k=2的情形，解决：

class Solution {
    public int maxProfit(int[] prices) {
        // return maxProfit1(prices,2);
        return maxProfit2(prices);
    }

    // 6道股票买卖题目一个模板搞定（https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv），其中k=2的情形即此题的解。
    //时间复杂度O(nk)、空间复杂度O(nk)
    public int maxProfit1(int[] prices, int maxK) {
        int n=prices.length;
        maxK=Math.min(maxK, n/2);

        int[][] dp=new int[maxK+1][2];
        for(int i=1;i<=n;i++){
            for(int k=1;k<=maxK;k++){
                if(i==1){
                    dp[k][0]=0;
                    dp[k][1]=-prices[i-1];
                }else{
                    dp[k][0]=Math.max(dp[k][0], dp[k][1]+prices[i-1]);
                    dp[k][1]=Math.max(dp[k][1], dp[k-1][0]-prices[i-1]);
                }
                //System.out.println(i+" "+k+" "+dp[i][k][0]+" "+dp[i][k][1]);
            }
        }
        return dp[maxK][0];
    }

    //由于k=2，比较小，所以可以定义几个变量，省去数组。
    //时间复杂度O(n)、空间复杂度O(1)
    public int maxProfit2(int[] prices) {
        int n=prices.length;

        int dp_k10=0, dp_k11=0, dp_k20=0, dp_k21=0;//初始值任意，因为下面i=1时会初始化
        for(int i=1;i<=n;i++){
            if(i==1){
                dp_k10=dp_k20=0;
                dp_k11=dp_k21=-prices[i-1];
            }else{
                dp_k10=Math.max(dp_k10, dp_k11+prices[i-1]);
                dp_k11=Math.max(dp_k11, -prices[i-1]);
                dp_k20=Math.max(dp_k20, dp_k21+prices[i-1]);
                dp_k21=Math.max(dp_k21, dp_k10-prices[i-1]);
            }
        }
        return dp_k20;
    }
}

法1：直接用上述模板AC。

法2：上述模板中k=2时由于k较小故可定义几个变量，从而可去掉辅助数组达到O(1)空间复杂度。

122.买卖股票的最佳时机2。上述问题的k=﹢? 的情形，解决：

class Solution {
    public int maxProfit(int[] prices) {
        return maxProfit2(prices);
    }

    // 6道股票买卖题目一个模板搞定（https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv），其中k为无穷的情形即此题的解，当然，也可以将k置为n/2进行求解。
    //k无穷大时k和k-1可认为相等，故此时递推式与k无关了
    // dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
    // dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
    //时间复杂度O(n)、空间复杂度O(n)
    public int maxProfit1(int[] prices) {
        int n=prices.length;

        int[][] dp=new int[n+1][2];
        for(int i=1;i<=n;i++){
            if(i==1){
                dp[i][0]=0;
                dp[i][1]=-prices[i-1];
            }else{
                dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+prices[i-1]);
                dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i-1]);
            }
        }
        return dp[n][0];
    }

    //进一步地，因当前状态只与前一个i有关故可以省去空间数组。
    //时间复杂度O(n)、空间复杂度O(1)
    public int maxProfit2(int[] prices) {
        int n=prices.length;

        int dp_i_0=0, dp_i_1=0;//初始值任意，因为下面i=1时会初始化
        for(int i=1;i<=n;i++){
            if(i==1){
                dp_i_0=0;
                dp_i_1=-prices[i-1];
            }else{
                int tmp=dp_i_0;
                dp_i_0=Math.max(dp_i_0, dp_i_1+prices[i-1]);
                dp_i_1=Math.max(dp_i_1,tmp -prices[i-1]);
            }
            //System.out.println(i+" "+dp_i_0+" "+dp_i_1);
        }
        return dp_i_0;
    }

    //针对本题的解法
    //贪心算法策略：因不限交易次数，故只要与前天差为正则虚拟交易（股价上涨则交易赚到利润、否则不操作以不亏），效果：res= (p5-p4)+(p4-p3)=p5-p3，即吃尽每个连续的涨价区间
    public int maxProfit3(int[] prices) {
        int maxProfit=0;
        for(int i=1;i)
        {
            int diff=prices[i]-prices[i-1];
            if(diff>0) maxProfit+=diff;
        }
        return maxProfit;
    }

}

法1：直接用上述模板，但须注意k>n/2时须转为n/2，不过此时很肯能超过内存限制从而不能AC，故最好用下面方法。

法2：上述模板中k=﹢?时，可认为k与k-1相等，故递推式与k维度无关了（当然你也可不当做上述特例而是直接定义dp[i][j]的含义，这样理解和实现更快）。

法3：递推式只与 i-1状态有关，从而可去掉辅助数组达到O(1)空间复杂度。

法4：贪心策略，因不限交易次数故只要今天与昨天差为正则虚拟交易。效果：res= (p5-p4)+(p4-p3)=p5-p3，即吃尽每个连续的涨价区间利润。

309.带冷冻期的买卖股票最佳时机。与上题一样k是无穷大的，只不过多了冷冻期限制。解法：上题的中间两种解法稍微改动即可。

714.带交易手续费的买卖股票最佳时机。与上题一样k是无穷大的，只不过多了交易手续费条件。解法：上题的中间两种解法稍微改动即可。

 

17、用栈实现队列、用队列实现栈

前者用两个栈即可，栈的读顺序与写相反，古“负负得正”——两个栈的效果相当于队列。

后者用一个队列或两个队列均可，pop：将前n-1个元素依次从队列取出并添加到队列末尾，则此时队列头元素即为栈顶元素。

class MyQueue {
    private Stack s1,s2;
    public MyQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        peek();
        return s2.pop();
    }
    
    public int peek() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}



class MyStack {//用一个队列来实现栈，栈的pop操作：将队列的前n-1个元素依次取出并重新添加到队列，然后队头元素即为栈顶元素
    Queue queue;
    Integer last=null;
    public MyStack() {
        queue=new LinkedList<>();
    }
    
    public void push(int x) {
        queue.offer(x);
        last=x;
    }
    
    public int pop() {
        int size=queue.size();
        while(size > 1){
            push(queue.poll());
            size--;
        }
        return queue.poll();
    }
    
    public int top() {
        return last;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

MyQueue MyStack

推荐参考资料

普林斯顿算法课-COS423