1. 二分查找

二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。

相似例题：704. 二分查找

 

1.1 基础版本

需求：在有序数组 A 内，查找值 target

• 如果找到返回索引
• 如果找不到返回 -1

算法描述
前提	给定一个内含 n 个元素的有序数组（升序） A，满足 A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}，一个待查值 target
1	设置 i=0，j=n-1
2	如果 i \gt j，结束查找，没找到
3	设置 m = floor(\frac {i+j}{2}) ，m 为中间索引，floor 是向下取整（\leq \frac {i+j}{2} 的最小整数）（Java中int计算自动去除后面小数点）
4	如果 target < A_{m} 设置 j = m - 1，跳到第2步 (以数轴形式脑补，<更合理)
5	如果 A_{m} \lt target 设置 i = m + 1，跳到第2步
6	如果 A_{m} = target，结束查找，找到了

public class BinarySearch {

    /**
     * <h3>二分查找基础版</h3>
     *
     * <ol>
     *     <li>i, j, m 指针都可能是查找目标</li>
     *     <li>因为 1. i > j 时表示区域内没有要找的了</li>
     *     <li>每次改变 i, j 边界时, m 已经比较过不是目标, 因此分别 m+1 m-1</li>
     *     <li>if else 向左查找, 不用执行else语句，比较次数少, 向右查找, 比较次数多。</li>
     * </ol>
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回索引</p>
     * <p>找不到返回 -1</p>
     */
    public static int binarySearchBasic(int[] a, int target) {
        int lo = 0;
        int hi = a.length -1;

        while (lo <= hi) {
            // 使用无符号右移1位，不会因取值过大导致中间值为负数
            // int mid = (lo + hi) / 2;
            int m = (lo + hi) >>> 1;
            // 以数轴形式看，大的右边，小的左边，一目了然
            if (target < a[mid]) {
               hi = mid - 1;
           } else if (a[mid] < target) {
               lo = mid + 1;
           } else {
               return mid;
           }
        }

        return -1;
    }
}

Q1：while条件如果不加 lo==hi 行不行？

不行，因为这意味着 lo,hi 共同指向的元素会漏过比较

Q2：(lo + hi) / 2 有没有问题？

当hi 为int的最大值Integer.MAX_VALUE - 1时会出问题！最高位是符号位，所以中间值mid会变为负数。【负数右移（最高位1）1位后，最高位为0，变回正数】

此外，无符号右移适配更多语言，JavaScript也适用

Q3：关于上面文档注释，在找不到的情况下，找不到的值在数组max值右边，次数会多，因为中间值向下取整（偶数偏左边，以数组【1 2 3 4 5 6】查找0为例，第一次选中间3 4偏左边的3，第二次选 1 2 偏左边的1）。如数组【2 3 4 5】，查找1比较2次，查找6比较3次。

int mid = left + (right - left) / 2;

 

1.2 改动版本

    /**
     * <h3>二分查找改动版</h3>
     *
     * <ol>
     *     <li>i, m 指针可能是查找目标</li>
     *     <li>j 指针不可能是查找目标</li>
     *     <li>此时 i >= j 时表示区域内没有要找的了</li>
     *     <li>改变 i 边界时, m 已经比较过不是目标, 因此需要 i=m+1</li>
     *     <li>改变 j 边界时, m 已经比较过不是目标, 同时因为 （j 指针不可能是查找目标） 所以 j=m</li>
     * </ol>
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回索引</p>
     * <p>找不到返回 -1</p>
     */
    public static int binarySearchAlternative(int[] a, int target) {
        int i = 0;
        int j = a.length;  // 修改1  去 -1  （j作为边界，指向的一定不是查找目标）

        while (i < j) {   // 修改2  去 = （如果不去掉等于，查找不存在的元素时，会陷入死循环）
            int mid = (i + j) >>> 1;

            if (target < a[mid]) {
                j = mid;   // 修改3  去 -1   // 往左
            } else if (a[mid] < target) {
                i = mid + 1;  // 往右
            } else {
                return mid;
            }
        }
        return -1;
    }
}

• 原版中，i,j 对应着搜索区间 [0,a.length-1]（注意是闭合的区间），i<=j 意味着搜索区间内还有未比较的元素，i,j 指向的元素也可能是比较的目标。
• 改动版本中，i,j 对应着搜索区间 [0,a.length)（注意是左闭右开的区间），i<j 意味着搜索区间内还有未比较的元素，j 指向的一定不是查找目标。
• 如果某次要缩小右边界，那么 j=m，因为此时的 m 已经不是查找目标了

 

1.3 二分查找性能

时间复杂度

• 最坏情况：O(\log n)
• 最好情况：如果待查找元素恰好在数组中央，只需要循环一次 O(1)

空间复杂度

• 需要常数个指针 i,j,m，因此额外占用的空间是 O(1)

 

1.4 二分查找平衡版

上面的代码，二分查找如果被查找的元素在最左边，则while内if else比较次数为 L 次的话，如果在最右边，则比较次数为 2L 次。

不同点，比较方式变为 low 和 high 之间的距离是否紧挨着。i 指向的也有可能是目标，但还是会继续比较。

    /**
     * <h3>二分查找平衡版</h3>
     *
     * <ol>
     *     <li>不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的(通过 i)</li>
     *     <li>i 指针可能是查找目标</li>
     *     <li>j 指针不可能是查找目标</li>
     *     <li>因为上面 1. 2. 3. 点所提，当区域内还剩一个元素时, 表示为 j - i == 1</li>
     *     <li>改变 i 边界时, m 可能就是目标, 同时因为 i 指向的可能是目标. 所以有 i=m</li>
     *     <li>改变 j 边界时, m 已经比较过不是目标, 同时因为 j 指针不可能是查找目标. 所以有 j=m</li>
     *     <li>三分支改为二分支, 循环内比较次数减少</li>
     * </ol>
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回索引</p>
     * <p>找不到返回 -1</p>
     */
public static int binarySearchBalance(int[] a, int target) {
    int i = 0, j = a.length;
    while (j - i > 1) {  // 在范围内待比较的元素个数 > 1
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m;   // j指向的不是目标
        } else {  // >= 也有可能是等于  a[m] <= target 
            i = m;  // 它指向的可能是目标，因此不能m+1
        }
    }
    return (a[i] == target) ? i : -1;
}

思想：

1. 左闭右开的区间，i 指向的可能是目标，而 j 指向的不是目标
2. 不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 i）
   • j - i > 1 的含义是，在范围内待比较的元素个数 > 1
3. 改变 i 边界时，它指向的可能是目标，因此不能 m+1
4. 循环内的平均比较次数减少了
5. 时间复杂度 \Theta(log(n))。（最好和最坏都是(log(n))）

 

1.5 二分查找Java版

Arrays的 binarySearch 方法：

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    // -(insertion point) - 1 ：返回的是负的插入点 - 1
    return -(low + 1);  // key not found.
}

• 例如 [1,3,5,6] 要插入 2 那么就是找到一个位置，这个位置左侧元素都比它小。（应该插入位置为1，实际结果为-2）
  • 等循环结束，若没找到，low 左侧元素肯定都比 target 小，因此 low 即插入点。（最后一次遍历时low = mid + 1; 加了1，捡回去）
• 插入点取负是为了与找到情况区分
• 返回值还要再-1是为了把索引 0 位置的插入点与找到的情况进行区分。（假如预计插入点为0，则应该返回-1，而不是 -0）

 

相似例题：35. 搜索插入位置，例题直接放回low就行

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

参考答案1：直接把上面 Java 版的返回值修改为 low 就行

参考答案2：用二分查找平衡版改写，平衡版中

• 如果 target == a[i] 返回 i 表示找到
• 如果 target < a[i]，例如 target = 2，a[i] = 3，这时就应该在 i 位置插入 2
• 如果 a[i] < target，例如 a[i] = 3，target = 4，这时就应该在 i+1 位置插入 4

public static int searchInsert(int[] a, int target) {
    int i = 0, j = a.length;
    while (1 < j - i) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m;
        } else {
            i = m;
        }
    }
    return (target <= a[i]) ? i : i + 1;
    // 原始 (target == a[i]) ? i : -1;
}

 

参考答案3：用 leftmost 版本解，返回值即为插入位置（并能处理元素重复的情况）

public int searchInsert(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while(i <= j) {
        int m = (i + j) >>> 1;
        if(target <= a[m]) {
            j = m - 1;
        } else {
            i = m + 1;
        } 
    }
    return i;
}

 

 

1.6 Leftmost 与 Rightmost

有时我们希望返回的是最左侧的重复元素，如果用 Basic 二分查找

• 对于数组 [1, 2, 3, 4, 4, 5, 6, 7]，查找元素4，结果是索引3
• 对于数组 [1, 2, 4, 4, 4, 5, 6, 7]，查找元素4，结果也是索引3，并不是最左侧的元素
• 解决方法：找到值后不急着返回，先用变量记录下来，继续调整边界，向左右查找

/**
 * <h3>二分查找 Leftmost </h3>
 *
 * @param a      待查找的升序数组
 * @param target 待查找的目标值
 * @return <p>找到则返回最靠左索引</p>
 * <p>找不到返回 -1</p>
 */
public static int binarySearchLeftmost1(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {   // 中间值和目标相等时，不急着返回
            candidate = m; // 记录候选位置
            j = m - 1;     // 继续向左找
        }
    }
    return candidate;
}

如果希望返回的是最右侧元素

/**
 * <h3>二分查找 Rightmost </h3>
 *
 * @param a      待查找的升序数组
 * @param target 待查找的目标值
 * @return <p>找到则返回最靠右索引</p>
 * <p>找不到返回 -1</p>
 */
public static int binarySearchRightmost1(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            candidate = m; // 记录候选位置
            i = m + 1;	   // 继续向右找
        }
    }
    return candidate;
}

 

修改代码返回值，返回一个比 -1 更有用的值

Leftmost 改为

/**
 * <h3>二分查找 Leftmost </h3>
 *
 * @param a      待查找的升序数组
 * @param target 待查找的目标值
 * @return <p>返回 &ge; target 的最靠左索引</p>
 */
public static int binarySearchLeftmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target <= a[m]) {  // leftmost，即使等于，我也要向左继续找（向左找移动的是j）。如果左边的值和target不一样，那肯定小于target，会触发i = m + 1使得i超过j，此时i就是插入点。
            j = m - 1;
        } else {
            i = m + 1;  // 中间值小，i（插入点）的位置至少得在它（中间值）的后面，后面退出循环时返回i
        }
    }
    return i;   // 大于等于目标的最靠左的索引位置
}

• leftmost 返回值的另一层含义：\lt target 的元素个数。大于等于目标的最靠左的索引位置 （预计插入点索引）
• 例如：int[] a = {1, 2, 4, 4, 4, 7, 9}，lenght = 7。
  • 查找不存在的0，返回值为大于0的元素1所在的索引0；
  • 查找不存在的3，返回值为大于3的元素4所在的索引2；
  • 查找不存在的6，返回值为大于6的元素7所在的索引5；
• 小于等于中间值，都要向左找

Rightmost 改为

/**
 * <h3>二分查找 Rightmost </h3>
 *
 * @param a      待查找的升序数组
 * @param target 待查找的目标值
 * @return <p>返回 &le; target 的最靠右索引</p>
 */
public static int binarySearchRightmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {  // 理由看下面一行的注释
            j = m - 1;
        } else {
            // rightmost，即使等于，我也要向右继续找（向右找移动的是 i）
            i = m + 1;  // target >= a[m]
        }
    }
    return i - 1;  // 上一步 加了1
}

• 返回值：小于等于目标的，最靠右的索引位置。
• 例如：int[] a = {1, 2, 4, 4, 4, 5, 6, 7}，lenght = 8。
  • 查找不存在的0，返回值为-1 （i一直是0，没移动过）；
  • 查找不存在的3，返回值为2所在索引1；
  • 查找不存在的8，返回值为7的索引值7。
• 大于等于中间值，都要向右找

 

名词解释：

范围查询：

• 查询 x \lt 4，0 .. leftmost(4) - 1 （到最左边的4的前一位截止）
• 查询 x \leq 4，0 .. rightmost(4)
• 查询 4 \lt x，rightmost(4) + 1 .. \infty （从最右边的4的后一位开始）
• 查询 4 \leq x， leftmost(4) .. \infty
• 查询 4 \leq x \leq 7，leftmost(4) .. rightmost(7)
• 查询 4 \lt x \lt 7，rightmost(4)+1 .. leftmost(7)-1

求排名：leftmost(target) + 1 （索引+1）

• target 可以不存在，如：leftmost(5)+1 = 6
• target 也可以存在，如：leftmost(4)+1 = 3

求前任（predecessor）：leftmost(target) - 1

• leftmost(3) - 1 = 1，前任 a_1 = 2
• leftmost(4) - 1 = 1，前任 a_1 = 2

求后任（successor）：rightmost(target)+1

• rightmost(5) + 1 = 5，后任 a_5 = 7
• rightmost(4) + 1 = 5，后任 a_5 = 7

求最近邻居：

• 前任和后任距离更近者。5和4相差1，5和7相差2，因此5的最近邻居为4。

 

1.6.1 例题

例题1：

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

// leftMost + rightMost candidate版本
class Solution {
    public int[] searchRange(int[] a, int target) {
        int x = left(a, target);
        if (x == -1) {
            return new int[]{-1, -1};
        } else {
            return new int[]{x, right(a, target)};
        }
    }

    public int left(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;  // 等于的话继续向左找
            }
        }
        return candidate;
    }

    public int right(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;  // 等于的话继续向右找
            }
        }
        return candidate;
    }
}

 

例题2：

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

输入：x = 4
输出：2

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

// rightMost 既视感  
// 当找不到目标时（有小数），返回结果要小的。即小于等于目标的，最靠右的索引值

代码：

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;  // 一个数的平方根，不可能超过自己
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;  // 只要是小的，就先记录
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

 

1.7 二分查找递归版

建议先行查看下面递归

public class E03BinarySearch {

    public static int search(int[] a, int target) {
        return f(a, target, 0, a.length - 1);
    }

    /**
     * <h3>递归(子问题)函数：查找 [i .. j] 范围内的目标</h3>
     *
     * @param a      数组
     * @param target 待查找值
     * @param i      起始索引
     * @param j      结束索引
     * @return <p>找到返回索引</p><p>找不到返回 -1</p>
     */
    private static int f(int[] a, int target, int i, int j) {
        if (i > j) {
            return -1;
        }

        int m = (i + j) >>> 1;
        if (target < a[m]) {
            return f(a, target, i, m - 1);
        } else if (a[m] < target) {
            return f(a, target, m + 1, j);
        } else {
            return m;
        }
    }
}

 

 

2. 衡量算法的好坏

2.1 时间复杂度

计算机科学中，时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本

• 不依赖于环境因素

 

以线性查找和二分查找为例，考虑最坏情况。

线性查找：

public static int search(int[] a, int k) {
    for (
        int i = 0;
        i < a.length;
        i++
    ) {
        if (a[i] == k) {
            return i;
        }
    }
    return -1;
}

考虑最坏情况下（没找到）例如 [1,2,3,4] 查找 5

• int i = 0 只执行一次
• i < a.length 受数组元素个数 n 的影响，比较 n+1 次
• i++ 受数组元素个数 n 的影响，自增 n 次
• a[i] == k 受元素个数 n 的影响，比较 n 次
• return -1，执行一次

假设每次执行时间一样，则总执行时间为：T = (3*n+3)t

 

二分查找：

// 规律：
        1 [2,3,4,5] 5 // 右侧没找到更差
            
        int i = 0, j = a.length - 1;    2次
        return -1;                      1次
        元素个数                循环次数
        4-7                    3        floor(log_2(4)) = 2+1
        8-15                   4        floor(log_2(8)) = 3+1
        16-31                  5        floor(log_2(16)) = 4+1
        32-63                  6        floor(log_2(32)) = 5+1
        ...                    ...

        循环次数 L  = floor(log_2(n)) + 1
// 执行次数：
        i <= j                   L+1
        int m = (i + j) >>> 1;   L
        target < a[m]            L
        a[m] < target            L
        i = m + 1;               L
// 总次数：
        (floor(log_2(n)) + 1) * 5 + 4

// 当n = 4:
        二分：(3) * 5 + 4 = 19*t        		线性：15t
// 当n = 1024:
        二分：(10 + 1) * 5 + 4 = 59*t   		线性：3075t

• 假设算法要处理的数据规模是 n，代码总的执行行数用函数 f(n) 来表示，例如：
  • 线性查找算法的函数 f(n) = 3*n + 3
  • 二分查找算法的函数 f(n) = (floor(log_2(n)) + 1) * 5 + 4

 

两个算法比较，可以看到 n 在较小的时候，二者花费的次数差不多。

 

为了对 f(n) 进行化简，应当抓住主要矛盾，找到一个变化趋势与之相近的表示法

 

2.2 大O表示法

其中

• c, c_1, c_2 都为一个常数
• f(n) 是实际执行代码行数与 n 的函数
• g(n) 是经过化简，变化趋势与 f(n) 一致的 n 的函数
• 图一，g(n)乘上某一常数后，某一个点之后，所有的值都比f(n) 大，g(n)为f(n) 的渐进上界。同理，图二渐进下届，图三，渐进紧界。

 

2.2.1 渐进上界

渐进上界（asymptotic upper bound）：从某个常数 n_0开始，c*g(n) 总是位于 f(n) 上方，那么记作 O(g(n))

• 代表算法执行的最差情况

例1：

• f(n) = 3*n+3
• g(n) = n
• 取 c=4，即【cg(n) = 4n】，那么在n_0=3 之后，g(n) 可以作为 f(n) 的渐进上界，因此表示法写作O(g(n))，即： O(n)

例2：

• f(n) = 5*floor(log_2(n)) + 9
• g(n) = log_2(n)
• O(log_2(n))

 

已知 f(n) 来说，求 g(n)

• 表达式中相乘的常量，可以省略，如
  • f(n) = 100*n^2 中的 100
• 多项式中数量规模更小（低次项）的表达式，可以省略，如
  • f(n)=n^2+n 中的 n
  • f(n) = n^3 + n^2 中的 n^2
• 不同底数的对数，渐进上界可以用一个对数函数 \log n 表示
  • 例如：log_2(n) 可以替换为 log_{10}(n)，因为（换底公式：） log_2(n) = \frac{log_{10}(n)}{log_{10}(2)}，相乘的常量 \frac{1}{log_{10}(2)} 可以省略
• 类似的，对数的常数次幂可省略
  • 如：log(n^c) = c * log(n)

 

2.2.2 常见的大o表示法

按时间复杂度从低到高

• 黑色横线 O(1)，常量时间，意味着算法时间并不随数据规模而变化
• 绿色 O(log(n))，对数时间
• 蓝色 O(n)，线性时间，算法时间与数据规模成正比
• 橙色 O(n*log(n))，拟线性时间
• 红色 O(n^2) 平方时间
• 黑色朝上 O(2^n) 指数时间
• 没画出来的 O(n!)

 

2.2.3 渐进下界

渐进下界（asymptotic lower bound）：从某个常数 n_0开始，c*g(n) 总是位于 f(n) 下方，那么记作 \Omega(g(n))。算法执行的最佳情况。

 

2.2.4 渐进紧界

渐进紧界（asymptotic tight bounds）：从某个常数 n_0开始，f(n) 总是在 c_1*g(n) 和 c_2*g(n) 之间，那么记作 \Theta(g(n))。既能代表最佳情况，也能代表最坏情况。

 

2.2.5 空间复杂度

与时间复杂度类似，一般也使用大 O 表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本

public static int binarySearchBasic(int[] a, int target) {
    int i = 0, j = a.length - 1;    // 设置指针和初值  (4个字节 * 2)
    while (i <= j) {                // i~j 范围内有东西
        int m = (i + j) >>> 1;      // （4个字节）
        if(target < a[m]) {         // 目标在左边
            j = m - 1;
        } else if (a[m] < target) { // 目标在右边
            i = m + 1;
        } else {                    // 找到了
            return m;
        }
    }
    return -1;
}

空间复杂度：O(1)

 

2.3 示例

用函数 f(n) 表示算法效率与数据规模的关系，假设每次解决问题需要 1 微秒（10^{-6} 秒），进行估算：

1. 如果 f(n) = n^2 那么 1 秒能解决多少次问题？1 天呢？
2. 如果 f(n) = log_2(n) 那么 1 秒能解决多少次问题？1 天呢？
3. 如果 f(n) = n! 那么 1 秒能解决多少次问题？1 天呢？

 

参考解答

1. 1秒 \sqrt{10^6} = 1000 次，1 天 \sqrt{10^6 * 3600 * 24} \approx 293938 次
2. 1秒 2^{1,000,000} 次，一天 2^{86,400,000,000}
3. 推算如下
   • 10! = 3,628,800 1秒能解决 1,000,000 次，因此次数为（10-1=） 9 次
   • 14!=87,178,291,200，一天能解决 86,400,000,000 次，因此次数为 （14-1=）13 次

3. 数组

3.1 概述

在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识。

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：

int[] array = {1,2,3,4,5}

 

知道了数组的数据起始地址 BaseAddress，就可以由公式 BaseAddress + i * size 计算出索引 i 元素的地址

• i 即索引，在 Java、C 等语言都是从 0 开始
• size 是每个元素占用字节，例如 int 占 4，double 占 8

 

3.2 性能

空间占用

Java 中数组结构为

• 8 字节 markword
• 4 字节 class 指针（类指针）（压缩 class 指针的情况）
• 4 字节 数组大小（存储数组size）（决定了数组最大容量是 2^{32}）
• 数组元素 + 对齐字节（java 中所有对象大小都是 8 字节的整数倍，不足的要用对齐字节补足）

例如

int[] array = {1, 2, 3, 4, 5};

的大小为 40 个字节，组成如下

8 + 4 + 4 + 5*4 + 4(alignment)

 

随机访问性能

即根据索引查找元素，时间复杂度是 O(1)

 

3.3 动态数组

 

实现方式：还是数组

通过变量 size 记录实际容量，需要扩容时进行数组拷贝替换。

实际输出时，也是通过 size 剔除掉数组中的空值。

• 以下这些方法实现，都简化了 index 的有效性判断，假设输入的 index 都是合法的

 

3.3.1 初始及添加方法

public class DynamicArray implements Iterable<Integer> {
    private int size = 0; // 逻辑大小
    private int capacity = 8; // 容量
    private int[] array = {};

    // 笔记003-四-2桶排序
    // 拷贝并返回数组（有效部分）
    public int[] array() {
        return Arrays.copyOf(array, size);
    }

    /**
     * 向最后位置 [size] 添加元素
     *
     * @param element 待添加元素
     */
    public void addLast(int element) {
//        array[size] = element;
//        size++;
        add(size, element);
    }

    /**
     * 向 [0 .. size] 位置添加元素
     *
     * @param index   索引位置
     * @param element 待添加元素
     */
    public void add(int index, int element) {
        checkAndGrow();

        // 添加逻辑
        // index等于size直接相当于addLast，直接执行下面的分支外的代码
        if (index >= 0 && index < size) {
            // 向后挪动一位, 空出待插入位置
            System.arraycopy(array, index,
                    array, index + 1, size - index); // 以索引来理解要移动的个数就是：末尾索引（size - 1） - 插入点前一个的索引(index - 1)
        }
        array[index] = element;
        size++;
    }
}    

 

3.3.2 检查和扩容

private void checkAndGrow() {
    // 容量检查
    if (size == 0) {
        array = new int[capacity];
    } else if (size == capacity) {
        // 进行扩容, 1.5倍
        capacity += capacity >> 1;
        int[] newArray = new int[capacity];
        System.arraycopy(array, 0,
                newArray, 0, size);
        array = newArray;
    }
}

 

3.3.3 三种遍历方法

/**
 * 查询元素
 *
 * @param index 索引位置, 在 [0..size) 区间内
 * @return 该索引位置的元素
 */
public int get(int index) {
    return array[index];
}

/**
 * 遍历方法1
 * 函数式接口
 * @param consumer 遍历要执行的操作, 入参: 每个元素
 * Iterable中也有forEach方法
 */
public void foreach(Consumer<Integer> consumer) {
    for (int i = 0; i < size; i++) {
        // 提供 array[i]
        // 返回 void
        consumer.accept(array[i]);
    }
}

/**
 * 遍历方法2 - 迭代器遍历
 */
@Override
public Iterator<Integer> iterator() {
    return new Iterator<Integer>() {
        int i = 0;

        @Override
        public boolean hasNext() { // 有没有下一个元素
            return i < size;
        }

        @Override
        public Integer next() { // 返回当前元素,并移动到下一个元素
            return array[i++];
        }
    };
}

/**
 * 遍历方法3 - stream 遍历
 *
 * @return stream 流
 */
public IntStream stream() {
    // IntStream.of(array) 无效部分 有效部分都会被遍历，如：1，2，3，4，0，0，0，0（逻辑大小和实际容量）
    return IntStream.of(Arrays.copyOfRange(array, 0, size));
}

 

3.3.4 删除方法

/**
 * 从 [0 .. size) 范围删除元素
 *
 * @param index 索引位置
 * @return 被删除元素
 */
public int remove(int index) { // [0..size)
    int removed = array[index];
    // 删除的不是【最后】一个元素：
    if (index < size - 1) {
        // 向前挪动
        System.arraycopy(array, index + 1,
                array, index, size - index - 1);// 以索引来理解要移动的个数就是：末尾索引（size - 1） - 插入点的索引(index)
    }
    size--;
    return removed;
}

 

3.3.5 性能

头部位置，时间复杂度是 O(n)

中间位置，时间复杂度是 O(n)，（ 1/2n 也是n）

尾部位置，时间复杂度是 O(1)（均摊来说）

 

3.4 二维数组

int[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};

 

内存图：

• 冷知识：在3.2中提到过，markword 占8个字节，类指针4个字节，后面一个存储数组大小为4个字节，剩下的数据部分补齐到8的倍数。
• 上图的二维数组占 32 （8+4+4+4*4）个字节，其中 array[0]，array[1]，array[2] 三个元素分别保存了指向三个一维数组的引用
• 三个一维数组各占 40 个字节
• 它们在内层布局上是连续的

 

更一般的，对一个二维数组 Array[m][n]

• m 是外层数组的长度，可以看作 row 行
• n 是内层数组的长度，可以看作 column 列
• 当访问 Array[i][j]，0\leq i \lt m, 0\leq j \lt n时，就相当于
  • 先找到第 i 个内层数组（行）
  • 再找到此内层数组中第 j 个元素（列）

 

byte二维数组案例：

Java 环境下（不考虑类指针和引用压缩，此为默认情况），有下面的二维数组

byte[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};

已知 array 对象起始地址是 0x1000，那么 23 这个元素的地址是什么？

答：

• 起始地址 0x1000
• 外层数组大小：16字节对象头 + 3元素 * 每个引用4字节 + 4 对齐字节 = 32 = 0x20
• 第一个内层数组大小：16字节对象头 + 5元素 * 每个byte1字节 + 3 对齐字节 = 24 = 0x18
• 第二个内层数组，16字节对象头 = 0x10，待查找元素索引为 2
• 最后结果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a

 

3.5 局部性原理

这里只讨论空间局部性

• cpu 读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，在缓存中能读到的话，就不必读内存了
• 缓存的最小存储单位是缓存行（cache line），一般是 64 bytes，一次读的数据少则不划算啊，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其临近的数据，这就是所谓空间局部性。

 

对效率的影响

比较下面 ij 和 ji 两个方法的执行效率

    /*
        CPU      缓存     内存
        皮秒              纳秒
                 64字节
                 缓存行 cache line

                 空间局部性
     */
int rows = 1000000;
int columns = 14;
int[][] a = new int[rows][columns];

StopWatch sw = new StopWatch();
sw.start("ij");
ij(a, rows, columns);
sw.stop();
sw.start("ji");
ji(a, rows, columns);
sw.stop();
System.out.println(sw.prettyPrint());

ij 方法

public static void ij(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

ji 方法

public static void ji(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int j = 0; j < columns; j++) {
        for (int i = 0; i < rows; i++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

执行结果

0
0
StopWatch '': running time = 96283300 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
016196200  017%  ij
080087100  083%  ji

可以看到 ij 的效率比 ji 快很多，为什么呢？

• 缓存是有限的，当新数据来了后，一些旧的缓存行数据就会被覆盖
• 如果不能充分利用缓存的数据，就会造成效率低下

 

以 ji 执行为例，第一次内循环要读入 [0,0] 这条数据，由于局部性原理，读入 [0,0] 的同时也读入了 [0,1] ... [0,13]，如图所示

但很遗憾，第二次内循环要的是 [1,0] 这条数据，缓存中没有，于是再读入了下图的数据

这显然是一种浪费，因为 [0,1] ... [0,13] 包括 [1,1] ... [1,13] 这些数据虽然读入了缓存，却没有及时用上，而缓存的大小是有限的，假设共8行，等执行到第九次内循环时

缓存的第一行数据已经被新的数据 [8,0] ... [8,13] 覆盖掉了，以后如果再想读，比如 [0,1]，又得到内存去读了

举一反三

1. I/O 读写时同样可以体现局部性原理
2. 数组可以充分利用局部性原理，那么链表呢？
   

   答：链表不行，因为链表的元素并非相邻存储

 

3.6 越界检查

java 中对数组元素的读写都有越界检查，类似于下面的代码

bool is_within_bounds(int index) const        
{ 
    return 0 <= index && index < length(); 
}

• 代码位置：openjdk\src\hotspot\share\oops\arrayOop.hpp

只不过此检查代码，不需要由程序员自己来调用，JVM 会帮我们调用

 

3.7 合并有序数组练习

【改编】力扣88. 合并两个有序数组，（原题题解见下面）

将数组内两个区间内的有序元素合并

例

[1, 5, 6, 2, 4, 10, 11]

上面数组 可以视作 两个有序区间合并后的结果

[1, 5, 6] 和 [2, 4, 10, 11]

合并后，结果仍存储于原有空间

[1, 2, 4, 5, 6, 10, 11]

 

 

方法一：递归。每次比较两个区间的值，小的值插入新数组，索引+1递归。

• 每次递归把更小的元素复制到结果数组

merge(left=[1,5,6],right=[2,4,10,11],a2=[]){
    merge(left=[5,6],right=[2,4,10,11],a2=[1]){
        merge(left=[5,6],right=[4,10,11],a2=[1,2]){
            merge(left=[5,6],right=[10,11],a2=[1,2,4]){
                merge(left=[6],right=[10,11],a2=[1,2,4,5]){
                    merge(left=[],right=[10,11],a2=[1,2,4,5,6]){
						// 拷贝10，11
                    }
                }
            }
        }
    }
}

代码：

    /*
        a1 原始数组  a2 结果数组 (a2添加元素的起始索引k)
        i, iEnd 第一个有序区间的起点终点, j, jEnd 第二个有序区间的起点终点
     */
    // 方法1  递归
    public static void merge(int[] a1, int i, int iEnd, int j, int jEnd,
                             int[] a2, int k) {
        if (i > iEnd) {
            System.arraycopy(a1, j, a2, k, jEnd - j + 1);
            return;
        }
        if (j > jEnd) {
            System.arraycopy(a1, i, a2, k, iEnd - i + 1);
            return;
        }
        if (a1[i] < a1[j]) {
            a2[k] = a1[i];
            merge(a1, i + 1, iEnd, j, jEnd, a2, k + 1);
        } else {
            a2[k] = a1[j];
            merge(a1, i, iEnd, j + 1, jEnd, a2, k + 1);
        }
    }

 

方法二：非递归，逐个比较两边，小的插入。

    /*
        i
        1   5   6

        j
        2   4   10  11

        k

     */
    // 方法2
    public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
        int k = i;
        while (i <= iEnd && j <= jEnd) {
            if (a1[i] < a1[j]) {
                a2[k] = a1[i];
                i++;
            } else {
                a2[k] = a1[j];
                j++;
            }
            k++;
        }
        if (i > iEnd) {
            System.arraycopy(a1, j, a2, k, jEnd - j + 1);
        }
        if (j > jEnd) {
            System.arraycopy(a1, i, a2, k, iEnd - i + 1);
        }
    }

 

原题：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
// ==================================================
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
// ==================================================
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

方法一：直接合并后排序

最直观的方法是先将数组 nums2 放进数组 nums1的尾部，然后直接对整个数组进行排序。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

方法二：双指针

方法一没有利用数组 nums1 与 nums2 已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示：

我们为两个数组分别设置一个指针 p_1 与 p_2 来作为队列的头部指针。代码实现如下：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

方法三：逆向双指针

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
}

 

4. 链表

4.1 概述

定义：在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续

可以分类为：

• 单向链表，每个元素只知道其下一个元素是谁

• 双向链表，每个元素知道其上一个元素和下一个元素

• 循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head

 

链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示

 

性能：

随机访问性能

根据 index 查找，时间复杂度 O(n)

插入或删除性能

• 起始位置：O(1)
• 结束位置：如果已知 tail 尾节点是 O(1)，不知道 tail 尾节点是 O(n)
• 中间位置：根据 index 查找时间 + O(1)。如果要在index 2 和 3中间，则先找到2，再新建节点，改变节点指向。

 

4.2 单向链表

 

4.2.1 节点类

首先定义一个存储 value 和 next 指针的类 Node，和一个描述头部节点的引用

/**
 * 单向链表
 */
public class SinglyLinkedList implements Iterable<Integer> { // 整体
    
    private Node head = null; // 头指针
    
	/**
     * 节点类
     * private 对外隐藏细节
     */
    private static class Node {
        int value; // 值 int类型
        Node next; // 下一个节点指针

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

• Node 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构
• 定义为 static 内部类，是因为 Node 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 Node 类定义

---

 

4.2.2 添加

头部添加：

    /**
     * 向链表头部添加
     *
     * @param value 待添加值
     */
    public void addFirst(int value) {
        // 1. 链表为空
//        head = new Node(value, null);  // 为空时，head == null，插入第一个后，head.next 还是 null
        // 2. 链表非空
        head = new Node(value, head);
    }

• 如果 this.head == null，新增节点指向 null，并作为新的 this.head
• 如果 this.head != null，新增节点指向原来的 this.head，并作为新的 this.head
  • 这里的 head节点其实是，链表的第一个节点。
  • 注意赋值操作执行顺序是从右到左

 

尾部添加：

// 找到最后一个节点
private Node findLast() {
    if (head == null) { // 空链表
        return null;
    }

    Node p;
    for (p = head; p.next != null; p = p.next) {

    }
    return p;
}

/**
 * 向链表尾部添加
 *
 * @param value 待添加值
 */
public void addLast(int value) {
    Node last = findLast();
    if (last == null) { // 空链表
        addFirst(value);
        return;
    }

    last.next = new Node(value, null);
}

• 注意，找最后一个节点，终止条件是 curr.next == null
• 分成两个方法是为了代码清晰，而且 findLast() 之后还能复用

 

尾部添加多个

public class SinglyLinkedList {
    // ...
	public void addLast(int first, int... rest) {
        
        Node sublist = new Node(first, null);
        Node curr = sublist;
        for (int value : rest) {
            curr.next = new Node(value, null);
            curr = curr.next;
        }
        
        Node last = findLast();
        if (last == null) {
            this.head = sublist;
            return;
        }
        last.next = sublist;
    }
}

• 先串成一串 sublist
• 再作为一个整体添加

 

---

4.2.3 遍历

（1）while..Consumer遍历：

    /**
     * 遍历链表1
     *
     * @param consumer 要执行的操作
     */
    public void loop1(Consumer<Integer> consumer) {
        Node p = head;
        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

 

（2）for..Consumer遍历：

    /**
     * 遍历链表2
     *
     * @param consumer 要执行的操作
     */
    public void loop2(Consumer<Integer> consumer) {
        for (Node p = head; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }

以上两种遍历都可以把要做的事以 Consumer 函数的方式传递进来

• Consumer 的规则是一个参数，无返回值，因此像 System.out::println 方法等都是 Consumer
• 调用 Consumer 时，将当前节点 curr.value 作为参数传递给它

 

（3）迭代器遍历

增强for循环底层就是迭代器遍历

public class SinglyLinkedList implements Iterable<Integer> {
    
    private Node head = null;
    
    @Override
    public Iterator<Integer> iterator() {
        // 匿名内部类 -> 带名字内部类
        return new NodeIterator();
    }
    
    private class NodeIterator implements Iterator<Integer> {
        // 用到了外部类的head，该类不能加static
        Node p = head;

        @Override
        public boolean hasNext() { // 是否有下一个元素
            return p != null;
        }

        @Override
        public Integer next() { // 返回当前值, 并指向下一个元素
            int v = p.value;
            p = p.next;
            return v;
        }
    }
    
}

• hasNext 用来判断是否还有必要调用 next
• next 做两件事
  • 返回当前节点的 value
  • 指向下一个节点
• NodeIterator 要定义为非 static 内部类，是因为它与 SinglyLinkedList 实例相关，是对某个 SinglyLinkedList 实例的迭代。

 

（4）递归遍历

    public void loop3(Consumer<Integer> before,
                      Consumer<Integer> after) {
        recursion(head, before, after);
    }


    private void recursion(Node curr,
                           Consumer<Integer> before, Consumer<Integer> after) { // 某个节点要进行的操作
        if (curr == null) {
            return;
        }
		// 前面做些事
        before.accept(curr.value);
        recursion(curr.next, before, after);
        // 后面做些事
        after.accept(curr.value);
    }

//=============测试：==========================
    @Test
    @DisplayName("测试递归遍历")
    public void test() {
        SinglyLinkedList list = getLinkedList();  // 1-2-3-4
        list.loop3(value -> {
            System.out.println("before:" + value);
        }, value -> {
            System.out.println("after:" + value);
        });
    }
// 输出结果：
// before:1
// before:2
// before:3
// before:4
// after:4
// after:3
// after:2
// after:1

 

4.2.4 获取

    /**
     * 根据索引返回节点
     * @param index 索引
     * @return 索引对应的节点
     */

    private Node findNode(int index) {
        int i = 0;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null; // 没找到
    }

    /**
     * 根据索引查找，返回value
     *
     * @param index 索引
     * @return 找到, 返回该索引位置节点的值
     * @throws IllegalArgumentException 找不到, 抛出 index 非法异常
     */
    public int get(int index) throws IllegalArgumentException {
        Node node = findNode(index);
        if (node == null) {
            throw illegalIndex(index);
        }
        return node.value;
    }

	/**
	* 该方法负责 按指定信息 抛出异常
	*/
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

 

4.2.5 插入insert

    /**
     * 向索引位置插入
     *
     * @param index 索引
     * @param value 待插入值
     * @throws IllegalArgumentException 找不到, 抛出 index 非法异常
     */
    public void insert(int index, int value) throws IllegalArgumentException {
        if (index == 0) {
            addFirst(value);
            return;
        }
        Node prev = findNode(index - 1); // 找到上一个节点 
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        // 原本的前面节点 的 next 指向变成 新节点
        // 原来的前面节点 的 下一个节点 成为 新节点的下一个节点
        // 1  -> 3
        // 1  -> [2]  -> 3
        prev.next = new Node(value, prev.next);
    }

• 插入包括下面的删除，都必须找到上一个节点

 

4.2.6 删除

删除头部：

    /**
     * 删除第一个
     *
     * @throws IllegalArgumentException - 如果不存在, 抛出 index 非法异常
     */
    public void removeFirst() throws IllegalArgumentException {
        // 链表不存在节点
        if (head == null) {
            throw illegalIndex(0);
        }
        head = head.next;
    }

 

删除指定索引节点：

    /**
     * 从索引位置删除
     *
     * @param index 索引
     * @throws IllegalArgumentException 找不到, 抛出 index 非法异常
     */
    public void remove(int index) throws IllegalArgumentException {
        // findNode从0开始，特殊情况
        if (index == 0) {
            removeFirst();
            return;
        }

        Node prev = findNode(index - 1); // 上一个节点
        // 找不到该节点
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node removed = prev.next; // 被删除的节点
        // 假如我有索引 0 1 2 3，但我删除索引4，前一个节点可以找到，但没有下一个节点
        if (removed == null) {
            throw illegalIndex(index);
        }
        prev.next = removed.next;
    }
}

 

4.2.7 单向链表（带哨兵）

观察之前单向链表的实现，发现每个方法内几乎都有判断是不是 head（index == 0） 这样的代码，能不能简化呢？

用一个不参与数据存储的特殊 Node 作为哨兵，它一般被称为哨兵或哑元，拥有哨兵节点的链表称为带头链表

public class SinglyLinkedListSentinel {
    // ...
    private Node head = new Node(Integer.MIN_VALUE, null);
}

• 具体存什么值无所谓，因为不会用到它的值

 

修改后的代码：

/**
 * 单向链表(带哨兵)
 */
public class SinglyLinkedListSentinel implements Iterable<Integer> { // 整体
    private Node head = new Node(666, null); // 头指针(哨兵)
    
}

尾部添加：

原先的findLast方法需要先判断head是否为null，即链表是否为空，现在不用判断。

原先的addLast方法需要先通过findLast方法找到尾结点，如果尾结点==null，说明为空链表。现在有了哨兵，空链表尾结点为哨兵，不可能为null，修改哨兵下一个节点为新节点即可。

    private Node findLast() {
        Node p;
        for (p = head; p.next != null; p = p.next) {

        }
        return p;
    }

    /**
     * 向链表尾部添加
     *
     * @param value 待添加值
     */
    public void addLast(int value) {
        Node last = findLast();
        last.next = new Node(value, null);
    }

 

调整遍历代码：

因为多了哨兵节点，所以要修改起始节点，改为head.next

while..consumer；for..consumer 方法同理，以下省略。

    private class NodeIterator implements Iterator<Integer> {
        // 起始节点改为：head.next
        Node p = head.next;

        @Override
        public boolean hasNext() { // 是否有下一个元素
            return p != null;
        }

        @Override
        public Integer next() { // 返回当前值, 并指向下一个元素
            int v = p.value;
            p = p.next;
            return v;
        }
    }

 

查找节点：

将索引初始值改为 -1，否则下方insert方法插入index=0时，索引-1查找不到。

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null; // 没找到
    }

 

插入节点：

原先的插入，先判断索引是否为0，是的话addFirst，因为索引0没有前一个节点，findNode(-1)抛异常。

现在则不用判断，head为-1，可以找到。

    /**
     * 向索引位置插入
     *
     * @param index 索引
     * @param value 待插入值
     * @throws IllegalArgumentException 找不到, 抛出 index 非法异常
     */
    public void insert(int index, int value) throws IllegalArgumentException {
        Node prev = findNode(index - 1); // 找到上一个节点
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        prev.next = new Node(value, prev.next);
    }

//=============addFirst方法============================
// 直接insert(0)即可
    public void addFirst(int value) {
        insert(0, value);
    }

 

删除：

原先remove方法，需要先判断index是否等于0，是的话则调用removeFirst方法。现在不用判断直接去掉即可。

removeFirst方法，原先是需要先判断是否为空，然后将head节点的下一个节点变为head，现在则等同于remove(0)

    public void removeFirst() throws IllegalArgumentException {
        remove(0);
    }

    public void remove(int index) throws IllegalArgumentException {
        Node prev = findNode(index - 1); // 上一个节点
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node removed = prev.next; // 被删除的节点
        if (removed == null) {
            throw illegalIndex(index);
        }
        prev.next = removed.next;
    }

 

4.3 【链表练习】

 

4.3.1 反转单向链表

本题为后端高频面试题，收录于《热招技术岗上岸指南》

对应力扣题目 206. 反转链表 - 力扣（LeetCode）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：[1,2]
输出：[2,1]

输入：[]
输出：[]

定义指针，记录需要的地址值

 

方法1

构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的。// 头部插入：新的头部 指向 老的头部

public ListNode reverseList(ListNode o1) {
    ListNode newHead = null;  // 新链表的第一个节点
    ListNode p = o1;  // 第一次为head
    while (p != null) {  
        // 第一次循环：新的尾结点 = new ListNode(val, null)
        // 尾结点没赋值前是null，赋值后表示尾结点下一个节点是null
        // 从右边看起，右边的n1代表原链表中上一个节点的地址，在新链表中将会是下一个节点的next。最后一轮过后变为尾结点。
        // 头部插入：新的头部 指向 老的头部
        newHead = new ListNode(p.val, newHead); 
        p = p.next;
    }
    return newHead;
}

评价：简单直白，就是得新创建节点对象

 

方法2

与方法1 类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点

static class List {
    ListNode head;

    public List(ListNode head) {
        this.head = head;
    }

    public ListNode removeFirst(){
        ListNode first = head;  // first用来记录当前的头结点
        if (first != null) {
            head = first.next;  // 更新头结点
        }
        return first;
    }

    public void addFirst(ListNode first) {
        first.next = head;   // 头部插入，新的节点将指向old head
        head = first;    // 插入后，更新head
    }
}

代码

public ListNode reverseList(ListNode head) {
    List list1 = new List(head);
    List list2 = new List(null);
    ListNode first;
    while ((first = list1.removeFirst()) != null) {
        list2.addFirst(first);
    }
    return list2.head;
}

评价：更加面向对象，如果实际写代码而非刷题，更多会这么做

 

方法3：迭代（需要存储pre curr next并更新）

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

 

方法4：递归

在归时让 5 \rightarrow 4，4 \rightarrow 3 ...

首先，写一个递归方法，返回值用来拿到最后一个节点

public ListNode reverseList(ListNode p) {
    if (p == null || p.next == null) { // 不足两个节点
        return p; // 最后一个节点
    }
    ListNode last = reverseList(p.next);
    return last;
}

• 注意1：递归终止条件是 curr.next == null，目的是到最后一个节点就结束递归，与之前递归遍历不一样
• 注意2：需要考虑空链表即 p == null 的情况

可以先测试一下

ListNode o5 = new ListNode(5, null);
ListNode o4 = new ListNode(4, o5);
ListNode o3 = new ListNode(3, o4);
ListNode o2 = new ListNode(2, o3);
ListNode o1 = new ListNode(1, o2);
ListNode n1 = new E01Leetcode206().reverseList(o1);
System.out.println(n1);

会打印

[5]

下面为伪码调用过程，假设节点分别是 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null，先忽略返回值

reverseList(ListNode p = 1) {
    reverseList(ListNode p = 2) {
    	reverseList(ListNode p = 3) {
    		reverseList(ListNode p = 4) {
    			reverseList(ListNode p = 5) {
    				if (p == null || p.next == null) {
                        return p; // 返回5
                    }
				}
                // 此时p是4, p.next是5
			}
            // 此时p是3, p.next是4
		}
        // 此时p是2, p.next是3
	}
    // 此时p是1, p.next是2
}

接下来，从 p = 4 开始，要让 5 \rightarrow 4，4 \rightarrow 3 ...

reverseList(ListNode p = 1) {
    reverseList(ListNode p = 2) {
    	reverseList(ListNode p = 3) {
    		reverseList(ListNode p = 4) {
    			reverseList(ListNode p = 5) {
    				if (p == null || p.next == null) {
                        return p; // 返回5
                    }
				}
                // 此时p是4, p.next是5, 要让5指向4,代码写成 p.next.next=p
                // 还要注意4要指向 null, 否则就死链了。（此时p.next还是5）
			}
            // 此时p是3, p.next是4
		}
        // 此时p是2, p.next是3
	}
    // 此时p是1, p.next是2
}

最终代码为：

public ListNode reverseList(ListNode p) {    
    if (p == null || p.next == null) { // 不足两个节点  // 要先判断是否为null再判断next，否则报空指针异常
        return p; // 最后一个节点
    }
    //递归传入下一个节点，目的只是为了到达最后一个节点
    ListNode last = reverseList(p.next);
    // 上面代码 递 完后，last是最后一个节点，p是倒数第二个节点
    // 进入 归 往回过程
    p.next.next = p;
    p.next = null;
    return last;
}

 /*
            第一轮出栈，head为5，head.next为空，返回5
            第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
                      把当前节点的子节点的子节点指向当前节点
                      此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
                      此时链表为1->2->3->4<-5
                      返回节点5
            第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
                      此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
                      此时链表为1->2->3<-4<-5
                      返回节点5
            第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
                      此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
                      此时链表为1->2<-3<-4<-5
                      返回节点5
            第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
                      此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
                      此时链表为1<-2<-3<-4<-5
                      返回节点5
            出栈完成，最终头节点5->4->3->2->1
         */

Q：为啥不能在递的过程中倒序？

A：比如

• 1 \rightarrow 2 \rightarrow 3 如果递的过程中让 2 \rightarrow 1 那么此时 2 \rightarrow 3 就被覆盖，不知道接下来递给谁
• 而归的时候让 3 \rightarrow 2 不会影响上一层的 1 \rightarrow 2

评价：单向链表没有 prev 指针，但利用递归的特性【记住了】链表每次调用时相邻两个节点是谁

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
• 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为n层。

 

方法5，指针

从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束

1. 设置指针 o1(旧头)、n1(新头)、o2(旧老二)，分别指向第一，第一，第二节点

\frac{n1 \ o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null

2. 将 o2 节点从链表断开，即 o1 节点指向第三节点

\frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null ，\frac{o2}{2}

3. o2 节点链入链表头部，即

\frac{o2}{2} \rightarrow \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null

4. n1 指向 o2

\frac{n1 \ o2}{2} \rightarrow \frac{o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null

5. o2 指向 o1 的下一个节点，即

\frac{n1}{2} \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{3} \rightarrow 4 \rightarrow 5 \rightarrow null

6. 重复以上 2\sim5 步，直到 o2 指向 null
7. 还应当考虑边界条件，即链表中不满两个元素时，无需走以上逻辑

 

参考答案

public ListNode reverseList(ListNode o1) {    
    if (o1 == null || o1.next == null) { // 不足两个节点
        return o1;
    }
    ListNode o2 = o1.next;
    ListNode n1 = o1;
    while (o2 != null) {
        o1.next = o2.next;  // o1指向下一个
        o2.next = n1;  // o2指向 新的头部 头部插入
        n1 = o2;  // o2成为新头后，更改新头指针
        o2 = o1.next;  // 更新o2
    }
    return n1;
}

 

方法6

要点：把链表分成两部分，思路就是不断从链表2的头，往链表1的头搬移

1. n1 指向 null，代表新链表一开始没有元素，o1 指向原链表的首节点

\frac{n1}{null}，\frac{o1}{1} \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null

2. 开始循环，o2 指向原链表次节点

\frac{n1}{null}，\frac{o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null

3. 搬移

\frac{o1}{1} \rightarrow \frac{n1}{null} ， \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null

4. 指针复位

\frac{n1}{1} \rightarrow null ， \frac{o1 \ o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null

5. 重复 2\sim4 步
6. 当 o1 = null 时退出循环

 

参考答案

public ListNode reverseList(ListNode o1) {
    if (o1 == null || o1.next == null) {
        return o1;
    }
    ListNode n1 = null;
    while (o1 != null) {
        ListNode o2 = o1.next;
        o1.next = n1;
        n1 = o1;
        o1 = o2;
    }
    return n1;
}

评价：本质上与方法2 相同，只是方法2更为面向对象

 

4.3.2 根据值删除节点

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

203. 移除链表元素

输入：head = [1,2,6,3,6], val = 6
输出：[1,2,3]

输入：head = [], val = 1
输出：[]

输入：head = [7,7,7,7], val = 7
输出：[]

方法1

图中 s 代表 sentinel 哨兵（如果不加哨兵，则删除第一个节点要特殊处理），例如要删除 6

p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

• 如果 p2 不等于目标，则 p1，p2 不断后移

	 p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

	 	  p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

• p2 == 6，删除它，注意 p1 此时保持不变，p2 后移

	 	  p1   p2
s -> 1 -> 2 -> 3 -> 6 -> null

• p2 不等于目标，则 p1，p2 不断后移

	 	  	   p1   p2
s -> 1 -> 2 -> 3 -> 6 -> null

• p2 == 6，删除它，注意 p1 此时保持不变，p2 后移

	 	  	   p1   p2
s -> 1 -> 2 -> 3 -> null

• p2 == null 退出循环

最后代码

public ListNode removeElements(ListNode head, int val) {
    ListNode sentinel = new ListNode(-1, head);
    ListNode pre = sentinel;  // 相当于 prev 记录前一个节点
    ListNode curr;
    while((curr = pre.next) != null) {
        if(curr.val == val) {
            pre.next = curr.next;  // 如果第一个值要被删除，此时sentinel.next会被改动，否则，pre将指向下一个节点，不会因为地址值而影响
        } else {
            pre = curr;
        }
    }
    return sentinel.next;
}

 

方法2

思路，递归函数负责返回：从当前节点（我）开始，完成删除的子链表

1. 若我与 v 相等，应该返回下一个节点递归结果
2. 若我与 v 不等，应该返回我，但我的 next 应该更新（让我能带上后续删过的子链表）

removeElements(ListNode p=1, int v=6){
    1.next=removeElements(ListNode p=2, int v=6){
    	2.next=removeElements(ListNode p=6, int v=6){
    		removeElements(ListNode p=3, int v=6){
    			3.next=removeElements(ListNode p=6, int v=6){
    				removeElements(ListNode p=null, int v=6){
    					// 没有节点,返回
                        return null
					}
				}
                return 3
			}
		}
        return 2
    }
    return 1
}

代码

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    if (head.val == val) {
        // 如果值一样，那么就让上一个节点“head.next”指向“我”的后面链表
        return removeElements(head.next, val);
    } else {
        // 如果值不一样，就return我自己“head”,让上一个的next指向我，更新因删除而断开的链表
        head.next = removeElements(head.next, val);
        return head;
    }
}

 

4.3.3 删除链表的倒数第N个结点

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

• 链表至少一个节点
• n 只会在合理范围

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

方法1，递归

思路，写一个递归函数，用来返回下一个节点的倒数序号

recursion(ListNode p=1, int n=2) {
    recursion(ListNode p=2, int n=2) {
    	recursion(ListNode p=3, int n=2) {
    		recursion(ListNode p=4, int n=2) {
    			recursion(ListNode p=5, int n=2) {
    				recursion(ListNode p=null, int n=2) {
    					return 0; // 最内层序号0
					}
                    return 1; // 上一次返回值+1
				}
                return 2;
			}
            if(返回值 == n == 2) {
                // 删除 next
            }
            return 3;
		}
        return 4;
	}
    return 5;
}

但上述代码有一个问题，就是若删除的是第一个节点，它没有上一个节点，（所以删除时没有上一个节点执行删除操作）因此可以加一个哨兵来解决

    // 方法1
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        recursion(s, n);
        return s.next;
    }

    private int recursion(ListNode p, int n) {
        if (p == null) {  // 结尾的null可以看做倒数第0个，最后一个才是倒数第一个
            return 0;
        }
        int nth = recursion(p.next, n); // 下一个节点的倒数位置
        if (nth == n) {
            // 这里的p代表要删除节点的上一个节点
            // p=3  p.next=4 p.next.next=5
            p.next = p.next.next;
        }
        return nth + 1;
    }

Q：p.next.next 不怕空指针吗？

A：

• p 是待删除节点的上一个节点，如果能递归回到 p，那么 p.next 肯定有值，不会是 null
• 且题目说明了 n >=1，不会因为 nth == 0 而让 p.next 指向最后的 null

 

方法2

快慢指针，p1 指向待删节点的上一个，p2 先走 n + 1 步

// 假如n=2, 那p2就先走三步，p1 p2中间相差3步，当p2到达尾部null时，p1刚好位于要被删除节点的上一个节点
i=0
p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

     i=1
     p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

          i=2
          p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

               i=3 从此开始 p1 p2 依次向右平移, 直到 p2 移动到末尾
p1             p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

               p1             p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2 = s;
    for (int i = 0; i < n + 1; i++) {
        p2 = p2.next;
    }
    while (p2 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    p1.next = p1.next.next;
    return s.next;
}

 

4.3.4 有序链表去重

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。83. 删除排序链表中的重复元素

• 题目数据保证链表已经按升序 排列
• 重复元素保留一个

输入：head = [1,1,2]
输出：[1,2]

输入：head = [1,1,2,3,3]
输出：[1,2,3]

方法1

p1   p2
1 -> 1 -> 2 -> 3 -> 3 -> null

• p1.val == p2.val 那么删除 p2，注意 p1 此时保持不变

p1   p2
1 -> 2 -> 3 -> 3 -> null

• p1.val != p2.val 那么 p1，p2 向后移动

     p1   p2
1 -> 2 -> 3 -> 3 -> null
         
          p1   p2
1 -> 2 -> 3 -> 3 -> null     

• p1.val == p2.val 那么删除 p2

          p1   p2
1 -> 2 -> 3 -> null   

• 当 p2 == null 退出循环

代码：

public ListNode deleteDuplicates(ListNode head) {
    // 链表节点 < 2
    if (head == null || head.next == null) {
        return head;
    }
    // 链表节点 >= 2
    ListNode p1 = head;
    ListNode p2;
    while ((p2 = p1.next) != null) {
        if (p1.val == p2.val) {
            p1.next = p2.next;
        } else {
            p1 = p1.next;
        }
    }
    return head;
}

方法2

递归函数负责返回：从当前节点（我）开始，完成去重的链表

1. 若我与 next 重复，返回 next
2. 若我与 next 不重复，返回我，但 next 应当更新

deleteDuplicates(ListNode p=1) {
    deleteDuplicates(ListNode p=1) {
        1.next=deleteDuplicates(ListNode p=2) {
            2.next=deleteDuplicates(ListNode p=3) {
                deleteDuplicates(ListNode p=3) {
					// 只剩一个节点，返回
                    return 3
                }                
            }
            return 2
        }
        return 1
    }
}

代码

public ListNode deleteDuplicates(ListNode p) {
    if (p == null || p.next == null) {
        return p;
    }
    if(p.val == p.next.val) {
        return deleteDuplicates(p.next);  // 注意递归函数写在if里面
    } else {
        p.next = deleteDuplicates(p.next);  // 如果重复，则返回较后的元素
        return p;
    }
}

// 下面写法超时：
 ListNode p1 = deleteDuplicates3(head.next);
if (head.val == p1.val) {
    return p1;
} else {
    head.next = deleteDuplicates3(head.next);
    return head;
}

 

4.3.5 有序链表去所有重

82. 删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。(与上面题目区别在于，这里要删除所有重复过的元素，不保留一个)

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

输入：head = [1,1,1,2,3]
输出：[2,3]

 

方法1：指针迭代

pre是待删除的上一个节点，每次循环对比 p1、p2的值

• 如果 p1 与 p2 的值重复，那么 p2继续后移，直到找到与p1不重复的节点，pre指向p2完成删除
• 如果p1与p2的值不重复，pre，p1，p2向后平移一位，继续上面的操作
• p1或 p2为 null 退出循环
  • p1 为 null 的情况，比如链表为 1 1 1 null

pre p1 p2
s, 1, 1, 1, 2, 3, null

pre p1    p2
s, 1, 1, 1, 2, 3, null

pre p1       p2
s, 1, 1, 1, 2, 3, null

pre p2
s, 2, 3, null

pre p1 p2
s, 2, 3, null

   pre p1 p2
s, 2, 3, null

代码：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode s = new ListNode(-1, head);
    ListNode pre = s;
    ListNode p1;
    ListNode p2;
    while ((p1 = pre.next) != null
            && (p2 = p1.next) != null) {

        if (p1.val == p2.val) {
            while ((p2 = p2.next) != null
                    && p2.val == p1.val) {
            }
            // p2 找到了不重复的值
            pre.next = p2;
        } else {
            pre = pre.next;
        }
    }
    return s.next;
}

 

方法2：递归

递归函数负责返回：从当前节点（我）开始，完成去重的链表

1. 若我与 next 重复，一直找到下一个不重复的节点，以它的返回结果为准
2. 若我与 next 不重复，返回我，同时更新 next

deleteDuplicates(ListNode p = 1) {
    // 找下个不重复的
	deleteDuplicates(ListNode p = 1) {
        deleteDuplicates(ListNode p = 1) {
			deleteDuplicates(ListNode p = 2) {
                2.next=deleteDuplicates(ListNode p = 3) {
					// 只剩一个节点，返回
                    return 3
                }
                return 2
			}
        }
    }
}

代码：

public ListNode deleteDuplicates1(ListNode p) {
    if (p == null || p.next == null) {
        return p;
    }
    if (p.val == p.next.val) {
        ListNode x = p.next.next;
        while (x != null && x.val == p.val) {
            x = x.next;
        }
        return deleteDuplicates1(x); // x 就是与 p 取值不同的节点
    } else {
        p.next = deleteDuplicates1(p.next);
        return p;
    }
}

 

4.3.6 合并有序链表

力扣21 ——合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
    
输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

方法1

• 谁小，把谁链给 p，p 和小的都向后平移一位
• 当 p1、p2 有一个为 null，退出循环，把不为 null 的链给 p

p1
1	3	8	9	null

p2
2	4	null

p		
s	null

代码

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
    // 新链表sentinel
    ListNode s = new ListNode(-1, null);
    // 新链表curr节点
    ListNode p = s;  // 在第一次p.next被赋值后，s.next就有了值，p随后p.next不影响sentinel对象
    while (p1 != null && p2 != null) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if (p1 != null) {
        p.next = p1;
    }
    if (p2 != null) {
        p.next = p2;
    }
    return s.next;
}

 

方法2

递归函数应该返回

• 更小的那个链表节点，并把它剩余节点与另一个链表再次递归
• 返回之前，更新此节点的 next

mergeTwoLists(p1=[1,3,8,9], p2=[2,4]) {
    1.next=mergeTwoLists(p1=[3,8,9], p2=[2,4]) {
        2.next=mergeTwoLists(p1=[3,8,9], p2=[4]) {            
            3.next=mergeTwoLists(p1=[8,9], p2=[4]) {
                4.next=mergeTwoLists(p1=[8,9], p2=null) {
                    return [8,9]
                }
                return 4
            }
            return 3
        }
        return 2
    }
	return 1
}

代码：

    public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        if (p2 == null) {
            return p1;
        }
        if (p1 == null) {
            return p2;
        }
        if (p1.val < p2.val) {
            p1.next = mergeTwoLists(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeTwoLists(p1, p2.next);
            return p2;
        }
    }

 

4.3.7 合并链表数组

力扣23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

 

方法1：递归，拆数组。拆成两个就可以按上道题解。

/**
 * 合并多个有序链表
 */
public class E07Leetcode23 {
    // 合并两个有序链表, 代码参考上题
    public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        if (p2 == null) {
            return p1;
        }
        if (p1 == null) {
            return p2;
        }
        if (p1.val < p2.val) {
            p1.next = mergeTwoLists(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeTwoLists(p1, p2.next);
            return p2;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {  // 数组无链表
            return null;
        }
        return split(lists, 0, lists.length - 1);
    }

    // 返回合并后的链表, i, j 代表左右边界。分而治之
    private ListNode split(ListNode[] lists, int i, int j) {
        if (i == j) { // 数组内只有一个链表
            return lists[i];
        }
        int m = (i + j) >>> 1;
        ListNode left = split(lists, i, m);  // 左边合并后的链表
        ListNode right = split(lists, m + 1, j);  // 右边合并后的链表
        return mergeTwoLists(left, right);
    }

    /**
     * <h3>Divide and Conquer 分而治之（分、治、合）</h3>
     * <h3>Decrease and Conquer 减而治之</h3>
     */

    public static void main(String[] args) {
        ListNode[] lists = {
                ListNode.of(1, 4, 5),
                ListNode.of(1, 3, 4),
                ListNode.of(2, 6),
        };
        ListNode m = new E07Leetcode23().mergeKLists(lists);
        System.out.println(m);
    }
}

优先级队列方法：【笔记002 - 4.4】

 

4.3.8 查找链表中间节点

力扣876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

例如

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])

• 偶数节点时，中间点是靠右的那个

 

解法：快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到链表结尾时，慢指针恰好走到链表的一半

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {  // 需要判断fast.next，以免fast.next.next爆空指针异常
            slow = slow.next;
            fast = fast.next.next;  // 快指针一次两步
        }
        return slow;
    }
}

快慢指针挺好用。

 

4.3.9 判断回文链表

力扣234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

所谓回文指正着读、反着读，结果一样，例如:[1,2,2,1]，[1,2,3,2,1]

示例：

输入：head = [1,2,2,1]
输出：true

输入：head = [1,2]
输出：false

1.找中间点

2.中间点后半个链表反转

3.反转后链表与原链表逐一比较

// 基本土方法：
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = middle(head);
        ListNode rightHalf = reverse(mid);

        while(head.next != null) {
            if(head.val != rightHalf.val) {
                return false;
            }
            head = head.next;
            rightHalf = rightHalf.next;
        }
        return true;
    }

    public ListNode middle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode mid) {
        ListNode newHead = null;
        ListNode oldHead = mid;
        ListNode oldSecond;

        while(oldHead != null) {
            oldSecond = oldHead.next;
            oldHead.next = newHead;
            newHead = oldHead;
            oldHead = oldSecond;
        }
        return newHead;
    }
}

 

方法合并后，优化前两个方法，找中间点的同时反转前半个链表

   /*
        步骤1. 找中间点的同时反转前半个链表
        步骤2. 反转后的前半个链表 与 中间点开始的后半个链表 逐一比较
                p1      p2
        1   2   2   1   null

        n1
        2   1

     */
    public boolean isPalindrome(ListNode head) {
        ListNode p1 = head; // 慢
        ListNode p2 = head; // 快
        ListNode n1 = null; // 新头
        ListNode o1 = head; // 旧头
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            // 反转链表
            o1.next = n1;
            n1 = o1;
            o1 = p1;  // p1刚好是 o1.next
        }
        System.out.println(n1);
        System.out.println(p1);

        if (p2 != null) { // 奇数节点  否则1 2 3 2 1结果是2 1和 3 2 1
            p1 = p1.next;  // 后半部分（除去中间值）与前半部分对比
        }

        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            n1 = n1.next;
            p1 = p1.next;
        }
        return true;
    }

 

4.3.10 判断环形链表

力扣141. 环形链表

力扣142. 环形链表 II

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

// 示例1：如上图
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
// ============================================
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
// ============================================
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

 

本题以及下题，实际是 Floyd's Tortoise and Hare Algorithm （Floyd 龟兔赛跑算法）

如果链表上存在环，那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。算法分为两个阶段

阶段1

• 龟一次走一步，兔子一次走两步
• 当兔子能走到终点时，不存在环
• 当兔子能追上龟时，可以判断存在环

阶段2

• 从它们第一次相遇开始，龟回到起点，兔子保持原位不变
• 龟和兔子一次都走一步
• 当再次相遇时，地点就是环的入口

为什么呢？

• 设起点到入口走 a 步（本例是 7步），绕环一圈长度为 b（本例是 5），
• 那么从起点开始，走 a + 绕环 n 圈，都能找到环入口（！插眼！）
• 第一次相遇时
  • 兔走了 a + 绕环 n 圈（本例 2 圈） + k，k 是它们相遇距环入口位置（本例是 3，不重要）
  • 龟走了 a + 绕环 n 圈（本例 0 圈） + k，当然它绕的圈数比兔少
  • 兔走的距离是龟的两倍，所以龟走的 = 兔走的 - 龟走的 = 绕环 n 圈
• 而前面（插眼处）分析过，如果走 a + 绕环 n 圈，都能找到环入口，因此从相遇点开始，（乌龟）再走 a 步，就是环入口。（因此此时兔子改为走一步，充当乌龟，按照理论，再走a步后兔子到达入口，而乌龟从起点处走a步也到达入口，第二次相遇。）

 

阶段1 参考代码（判断是否有环）：

    public boolean hasCycle(ListNode head) {
        ListNode slow = head;  // 乌龟
        ListNode fast = head;  // 兔子

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

阶段二，找到入口

    public ListNode detectCycle1(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (fast == slow) {
                // 有环
                slow = head;
                // 先判断，避免全部节点都在环里的情况（一个圆: 那么此时时兔子走了两圈，乌龟一圈）
                while(slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        // 无环
        return null;
    }

 

4.3.11 删除节点【简单？】

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中。
• 链表中的节点数应该减少 1。
• node 前面的所有值顺序相同。
• node 后面的所有值顺序相同。

• 链表中节点的数目范围是 [2, 1000]
• -1000 <= Node.val <= 1000
• 链表中每个节点的值都是 唯一 的
• 需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

例如：（这里参数传递的是ListNode，不是value）

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]


输入：head = [4,5,1,9], node = 1
输出：[4,5,9]

注意：被删除的节点不是末尾节点

思路：要删除节点，就要让上一个节点指向他的下一个节点。然而目前没有给头结点，找不到它的上一个节点。所以，我们把这个被删除的节点变为下一个节点，成为它的备份，就可以无所顾忌的删除下一个节点了。(替死鬼)

参考代码：

public class Ex1Leetcode237 {
    /**
     *
     * @param node 待删除节点, 题目已说明肯定不是最后一个节点
     */
    public void deleteNode(ListNode node) {
        node.val = node.next.val;		// 下一个节点值赋值给待"删除"节点
        node.next = node.next.next;		// 把下一个节点删除
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        new E0xLeetcode237().deleteNode(o3);
        System.out.println(o1);
    }
}

 

4.3.12 相交链表

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

共链 p1

例如，下图的两个链表 [1, 2, 4, 5] 与 [3, 4, 5] 它们中 [4, 5] 是相同的，此时应返回节点 4

非共尾的情况，如下图所示，此时返回 null

思路，称两个链表为 a=[1, 2, 4, 5]，b=[3, 4, 5]，图中用 N 代表 null

1. 遍历 a，遇到 null 时改道遍历 b
2. 与此同时，遍历 b，遇到 null 时改道遍历 a
3. 在此过程中，如果遇到相同的节点，即为找寻目标，返回即可，如下图中的第二次出现的 4
4. 相同节点应该比较其引用值，图中数字只是为了便于区分

(此方法同时是力扣官方题解的方法二：双指针)

1	2	4	5	N	3	4	5	N
3	4	5	N	1	2	4	5	N

如果两个链表长度相同，则可以更早找到目标，例如 a=[1, 4, 5]，b=[3, 4, 5]，第一次出现 4 时，即可返回

1	4	5	N	3	4	5	N
3	4	5	N	1	4	5	N

如果是非共尾的情况，如 a=[1, 2, 4]，b=[3, 5]，可以看到，唯一相等的情况，是遍历到最后那个 N 此时退出循环

1	2	4	N	3	5	N
3	5	N	1	2	4	N

该方法参考代码：

public ListNode getIntersectionNode(ListNode a, ListNode b) {
    ListNode p1 = a;
    ListNode p2 = b;
    while (true) {
        if (p1 == p2) {
            return p1;
        }
        if (p1 == null) {
            p1 = b;
        } else {
            p1 = p1.next;
        }
        if (p2 == null) {
            p2 = a;
        } else {
            p2 = p2.next;
        }            
    }
}

力扣参考代码：

两链表不相交：

如果长度相等，则两个指针会同时到达两个链表的尾节点，然后同时变成空值null，（null == null）此时返回null；

如果长度不等，则两个指针都会移动m+n次（m n为两链表长度），最后同时到达结尾null，（null == null）此时返回null；

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 都不为空时，两个链表才可能相交
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            // pA不为空，则移动到下一个节点，为空则移动到headB
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

• 时间复杂度：O(m+n)，其中m和n是分别是链表headA和headB的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
• 空间复杂度：O(1)。

 

方法二：用集合存储哈希值

思路：判断两个链表是否相交，可以使用哈希集合存储链表节点。

首先遍历链表headA，并将链表headA中的每个节点加入哈希集合中。然后遍历链表headB，对于遍历到的每个节点，判断该节点是否在哈希集合中

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

• 时间复杂度：O(m+n)，其中 m 和 n 是分别是链表headA和headB的长度。需要遍历两个链表各一次。
• 空间复杂度：O(m)，其中m是链表headA的长度。需要使用哈希集合存储链表headA中的全部节点。

 

 

4.4 双向链表（带哨兵）

增加尾结点，每个节点增加prev指针指向前一个节点。

/**
 * 双向链表(带哨兵)
 */
public class DoublyLinkedListSentinel implements Iterable<Integer> {
    static class Node {
        Node prev; // 上一个节点指针
        int value; // 值
        Node next; // 下一个节点指针

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node head; // 头哨兵
    private Node tail; // 尾哨兵

    public DoublyLinkedListSentinel() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;   // 头的next指向尾
        tail.prev = head;   // 尾的prev指向头
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    public void addFirst(int value) {
        insert(0, value);
    }

    public void removeFirst() {
        remove(0);
    }

    public void addLast(int value) {
        Node last = tail.prev;
        Node added = new Node(last, value, tail);
        last.next = added;
        tail.prev = added;
    }

    public void removeLast() {
        Node removed = tail.prev;
        if (removed == head) {
            throw illegalIndex(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    public void insert(int index, int value) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;
    }

    public void remove(int index) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node removed = prev.next;
        if (removed == tail) {  // 待删除元素是尾哨兵
            throw illegalIndex(index);
        }
        Node next = removed.next;

        prev.next = next;
        next.prev = prev;
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;  // 头的value无意义

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

 

4.5 环形链表（带哨兵）

双向环形链表带哨兵，这时哨兵既作为头，也作为尾

 

代码实现：

public class DoublyLinkedListSentinel implements Iterable<Integer> {

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    private static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private final Node sentinel = new Node(null, -1, null);

    public DoublyLinkedListSentinel() {
        sentinel.prev = sentinel;  // 初始时哨兵的prev和next都指向自己
        sentinel.next = sentinel;
    }

    /**
     * 添加到第一个
     *
     * @param value 待添加值
     */
    public void addFirst(int value) {  // 需要找到前面的哨兵和下一个节点
        Node a = sentinel;  // 哨兵
        Node b = sentinel.next;  // 如果链表为空，那这里还是哨兵
        Node added = new Node(a, value, b);
        a.next = added;
        b.prev = added;
    }

    /**
     * 添加到最后一个
     *
     * @param value 待添加值
     */
    public void addLast(int value) {
        Node a = sentinel.prev;  // 哨兵的前一个为尾结点，尾结点下一个为哨兵
        Node b = sentinel;
        Node added = new Node(a, value, b);
        a.next = added;
        b.prev = added;
    }

    /**
     * 删除第一个
     */
    public void removeFirst() {
        Node removed = sentinel.next; // // 找到第一个节点
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    /**
     * 删除最后一个
     */
    public void removeLast() {
        Node removed = sentinel.prev;  // 找到最后一个节点
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = removed.prev;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    /**
     * 根据值value删除
     *
     * @param value 目标值
     */
    public void removeByValue(int value) {
        Node removed = findByValue(value);
        if (removed == null) {
            return; // 找不到，不用删
        }
        Node a = removed.prev;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    private Node findByValue(int value) {
        Node p = sentinel.next;
        while (p != sentinel) {
            if (p.value == value) {
                return p;
            }
            p = p.next;
        }
        return null;
    }
}

 

5. 递归

5.1 概述

定义：计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集

 

比如单链表递归遍历的例子：

void f(Node node) {
    if(node == null) {
        return;
    }
    println("before:" + node.value)
    f(node.next);
    println("after:" + node.value)
}

说明：

1. 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）
2. 每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归
3. 内层函数调用（子集处理）完成，外层函数才能算调用完成

 

原理

假设链表中有 3 个节点，value 分别为 1，2，3，以上代码的执行流程就类似于下面的伪码

// 1 -> 2 -> 3 -> null  f(1)

void f(Node node = 1) {
    println("before:" + node.value) // 1
    void f(Node node = 2) {
        println("before:" + node.value) // 2
        void f(Node node = 3) {
            println("before:" + node.value) // 3
            void f(Node node = null) {
                if(node == null) {
                    return;
                }
            }
            println("after:" + node.value) // 3
        }
        println("after:" + node.value) // 2
    }
    println("after:" + node.value) // 1
}

 

思路

1. 确定能否使用递归求解
2. 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件

 

例如之前遍历链表的递推关系为

 

• 深入到最里层叫做递
• 从最里层出来叫做归
• 在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到

 

5.2 单路递归Single Recursion

E01. 阶乘

用递归方法求阶乘

• 阶乘的定义 n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅n，其中 n 为自然数，当然 0! = 1
• 递推关系

代码

private static int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n - 1);
}

拆解伪码如下，假设 n 初始值为 3

f(int n = 3) { // 解决不了,递
    return 3 * f(int n = 2) { // 解决不了,继续递
        return 2 * f(int n = 1) {
            if (n == 1) { // 可以解决, 开始归
                return 1;
            }
        }
    }
}

 

E02. 反向打印字符串

用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置

• 递：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1
• 归：从 n == str.length() 开始归，从归打印，自然是逆序的

递推关系

代码为：

运用之前链表时遍历的Consumer方法思路，运行测试方法时，传入两个lambda表达式，直接用于输出。

递到最后return后，说明到了最后，此时才输出。

// 测试方法：
public static void main(String[] args) {
    String str = "你好，我是乔治华生。abc123";

    reversePrint(str, 0, System.out::printf, System.out::printf);

}

// 遍历代码：
public static void reversePrint(String str, int index, Consumer<String> normal, Consumer<String> reverse) {
    if (index == str.length()) {  // 这里应该是等于 length, 超出索引就退出
        normal.accept("\n");  // normal吃完后多吃个 换行
        return;
    }
    normal.accept(String.valueOf(str.charAt(index)));
    reversePrint(str, index+1, normal, reverse);
    reverse.accept(String.valueOf(str.charAt(index)));
}

思路2，从尾部开始递归，测试方法里索引0改为str.length()-1，方法中if退出条件改为index == -1， 递归内部index+1改为index-1。此时normal为逆序，reverse为正序。

 

5.3 冒泡排序（递归版）

冒泡排序，相邻元素比较，大的靠右，每一回合最大的元素沉底。array.length-1轮后完成排序。

思路：将数组分为已排序部分（右边）和未排序部分（左边），每回合已排序部分数量+1，即未排序部分索引-1。

优化：发生交换，意味着有无序情况。使用变量x记录每回合最后一次交换的索引，意味这索引后面的元素是有序的，不需要再交换，下次遍历到索引x即可。

public class E04BubbleSort {

    public static void sort(int[] a) {
        bubble(a, a.length - 1);
    }

    /**
     * <h3>递归函数 在范围 [0 .. j] 内冒泡最大元素到右侧</h3>
     *
     * @param a 数组
     * @param j 未排序区域右边界，初始时默认到最右侧索引都是无序
     */
    private static void bubble(int[] a, int j) {
        if (j == 0) {
            return;
        }
        
        int x = 0;
        /*
            假设经过了1次递归后数组：[2, 1, 3, 4, 5, 6, 7], 此时仅仅遍历到 6，还需遍历4次，
            而其实只要改变 2和1的位置即可，所以记录用来记录最后一次发生改变的位置。（没有发生交换的地方意味着有序）
            x及其x后面的都是有序的，（最后一次交换中，x位置被换到了小的，但不是其中的最大）
         */
        for (int i = 0; i < j; i++) {
            if (a[i] > a[i + 1]) {
                int t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                x = i;
            }
        }
        bubble(a, x);
    }

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

}

 

5.4 插入排序（递归版）

分为前面已排序和后面未排序部分，每回合选取未排序的第一个，依次和前面已排序的比较，小于则交换，直到找到合适位置。

扑克牌

package algorithms.recursion;

/**
 * 递归插入排序
 * <ul>
 *     <li>将数组分为两部分 [0 .. low-1]  [low .. a.length-1]</li>
 *     <li>左边 [0 .. low-1] 是已排序部分</li>
 *     <li>右边 [low .. a.length-1] 是未排序部分</li>
 *     <li>每次从未排序区域取出 low 位置的元素, 插入到已排序区域</li>
 * </ul>
 */
public class E05InsertionSort {
    public static void sort(int[] a) {
        insertion(a, 1);
//        insertion2(a, 1);
    }

    /**
     * <h3>递归函数 将 unsortIndex 位置的元素插入至 [0..unsortIndex-1] 的已排序区域</h3>
     *
     * @param array   数组
     * @param unsortIndex 未排序区域的左index，初始时默认数组第一个元素（索引0）是有序。
     */
    private static void insertion(int[] array, int unsortIndex) {
        // unsortIndex == array.length-1时，最后一个元素尚未有序（未向前面插入）
        if (unsortIndex == array.length) {
            return;
        }
        // 拿未排序的第一个值，一直和前面已排序的比较，直到碰上一个小于它的元素，放在它后面。
        int unsortValue = array[unsortIndex];  // 未排序的值
        int sortedIndex = unsortIndex - 1; // 已排序区域右index  // sortedIndex改名为will_insert_index会好一点

        // 没有找到插入位置
        // sortedIndex==0时，说明被比较的元素是最小的，应该放在头，此时退出循环时sortedIndex=-1
        while (sortedIndex >= 0 && array[sortedIndex] > unsortValue) { // 没有找到插入位置
            array[sortedIndex + 1] = array[sortedIndex]; // 空出插入位置
            sortedIndex--;
        }

        // 找到插入位置
        // 未排序的元素比已排序的最大元素还大，此时不用交换
        if (sortedIndex + 1 != unsortIndex) {
            // 碰上一个小于等于它的元素，放在它后面。
            array[sortedIndex + 1] = unsortValue;
        }

        // 递归下一个元素
        insertion(array, unsortIndex + 1);
    }

    // 另一种插入排序的实现，缺点: 交换多导致赋值次数较多
    private static void insertion2(int[] a, int low) {
        if (low == a.length) {
            return;
        }

        int i = low - 1;  // 已排序的右index
        while (i >= 0 && a[i] > a[i + 1]) {
            int t = a[i];
            a[i] = a[i + 1];
            a[i + 1] = t;

            i--;
        }

        insertion(a, low + 1);
    }
}

• 扩展：利用二分查找 leftmost 版本，改进寻找插入位置的代码

 

 

5.5 多路递归 Multi Recursion

5.5.0 斐波那契数列

• 之前的例子是每个递归函数只包含一个自身的调用，这称之为 single recursion
• 如果每个递归函数例包含多个自身调用，称之为 multi recursion

递推关系

 

下面的表格列出了数列的前几项

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13
0	1	1	2	3	5	8	13	21	34	55	89	144	233

函数的调用次数与上面值有关：（见下图 gif）

f(3)=5,即 f(3)的调用次数 = 2 * F4 - 1 = 5。F4的值见上图， f(4)=9,f(5)=15，f(3)的调用次数等于f(4)的值乘于2然后-1。

实现

public static int f(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}

执行流程

• 绿色代表正在执行（对应递），灰色代表执行结束（对应归）
• 递不到头，不能归，对应着深度优先搜索。
• f(5) = f(4) + f(3)，得先执行计算完f(4)，才能开始算f(3)，而计算f(4)则又要先计算它下面的f(3)。

时间复杂度

• 递归的次数也符合斐波那契规律，2 * f(n+1)-1
• 时间复杂度推导过程
  • 斐波那契通项公式 f(n) = \frac{1}{\sqrt{5}}*({\frac{1+\sqrt{5}}{2}}^n - {\frac{1-\sqrt{5}}{2}}^n)
  • 简化为：f(n) = \frac{1}{2.236}*({1.618}^n - {(-0.618)}^n)
  • 带入递归次数公式 2*\frac{1}{2.236}*({1.618}^{n+1} - {(-0.618)}^{n+1})-1
  • 时间复杂度为 \Theta(1.618^n)

1. 以上时间复杂度分析，未考虑大数相加的因素

 

 

5.6 递归优化——记忆法

上述代码存在很多重复的计算，例如求 f(5) 递归分解过程

可以看到（颜色相同的是重复的）：

• f(3) 重复了 2 次
• f(2) 重复了 3 次
• f(1) 重复了 5 次
• f(0) 重复了 3 次

随着 n 的增大，重复次数非常可观，可以用将结果存放在数组，需要时直接获取。

 

Memoization 记忆法（也称备忘录）是一种优化技术，通过存储函数调用结果（通常比较昂贵），当再次出现相同的输入（子问题）时，就能实现加速效果，改进后的代码

/**
 * 递归求斐波那契第n项
 */
public class E01Fibonacci {

    /**
     * <h3>使用 Memoization(记忆法, 也称备忘录) 改进</h3>
     *
     * @param n 第 n 项
     * @return 第 n 项的值
     */
    public static int fibonacci(int n) {
        int[] cache = new int[n + 1];
        // -1表示该索引对应的值尚未被计算出来。
        Arrays.fill(cache, -1); // [-1,-1,-1,-1,-1,-1]
        cache[0] = 0;
        cache[1] = 1; // [0,1,-1,-1,-1,-1]
        return f(n, cache);
    }


    private static int f(int n, int[] cache) {
        /*if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }*/
        // 不是-1,表示该值已被计算出过
        if (cache[n] != -1) {
            return cache[n];
        }

        int x = f(n - 1, cache);
        int y = f(n - 2, cache);
        cache[n] = x + y; // // [0,1,?,-1,-1,-1] 存入数组
        return cache[n];
    }

    public static int fibonacci2(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int x = fibonacci2(n - 1);
        int y = fibonacci2(n - 2);
        return x + y;
    }
}

优化后的图示，只要结果被缓存，就不会执行其子问题

• 改进后的时间复杂度为 O(n)

注意

1. 记忆法是动态规划的一种情况，强调的是自顶向下的解决
2. 记忆法的本质是空间换时间

 

5.7 递归优化——尾递归

5.7.1 爆栈问题

用递归做 n + (n-1) + (n-2) ... + 1

public static long sum(long n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

当n过大时，如 n = 12000 时，爆栈

Exception in thread "main" java.lang.StackOverflowError
	at Test.sum(Test.java:10)
	at Test.sum(Test.java:10)
	...

• 每次方法调用是需要消耗一定的栈内存的，这些内存用来存储方法参数、方法内局部变量、返回地址等等
• 方法调用占用的内存需要等到方法结束时才会释放
• 递归调用不到最深不会回头，最内层方法没完成之前，外层方法都结束不了
  • 例如，sum(3) 这个方法内有个需要执行 3 + sum(2)，sum(2) 没返回前，加号前面的 3 不能释放
  • 看下面伪码

long sum(long n = 3) {
    return 3 + long sum(long n = 2) {
        return 2 + long sum(long n = 1) {
            return 1;
        }
    }
}

 

5.7.2 尾调用

尾调用

如果函数的最后一步是调用一个函数，那么称为尾调用，例如

function a() {
    return b()
}

 

下面三段代码不能叫做尾调用

// 因为最后一步并非调用函数
function a() {
    const c = b()
    return c
}

// 最后一步执行的是加法
function a() {
    return b() + 1
}

// 最后一步执行的是加法
function a(x) {
    return b() + x
}

 

一些语言 (C++，Scala)的编译器能够对尾调用做优化，例如

function a() {
    // 做前面的事
    return b() 
}

function b() {
    // 做前面的事
    return c()
}

function c() {
    return 1000
}

a()

没优化之前的伪码

function a() {
    return function b() {
        return function c() {
            return 1000
        }
    }
}

优化后伪码如下

a()
b()
c()

调用 a 时

• a 返回时发现：没什么可留给 b 的，将来返回的结果 b 提供就可以了，用不着我 a 了，我的内存就可以释放

调用 b 时

• b 返回时发现：没什么可留给 c 的，将来返回的结果 c 提供就可以了，用不着我 b 了，我的内存就可以释放

如果调用 a 时

• 不是尾调用，例如 return b() + 1，那么 a 就不能提前结束，因为它还得利用 b 的结果做加法

 

5.7.3 尾递归

安装Scala：

Scala 入门

object Main {
  def main(args: Array[String]): Unit = {
    println("Hello Scala")
  }
}

• Scala 是 java 的近亲，java 中的类都可以拿来重用
• 类型是放在变量后面的
• Unit 表示无返回值，类似于 void
• 不需要以分号作为结尾，当然加上也对

 

还是先写一个会爆栈的函数

def sum(n: Long): Long = {
    if (n == 1) {
        return 1
    }
    return n + sum(n - 1)
}

• Scala 最后一行代码若作为返回值，可以省略 return

不出所料，在 n = 11000 时，还是出了异常

println(sum(11000))

Exception in thread "main" java.lang.StackOverflowError
	at Main`.sum(Main.scala:25)
	at Main`.sum(Main.scala:25)
	at Main`.sum(Main.scala:25)
	at Main`.sum(Main.scala:25)
	...

 

这是因为以上代码，还不是尾调用，要想成为尾调用，那么：

1. 最后一行代码，必须是一次函数调用
2. 内层函数必须摆脱与外层函数的关系，内层函数执行后不依赖于外层的变量或常量

def sum(n: Long): Long = {
    if (n == 1) {
        return 1
    }
    return n + sum(n - 1)  // 依赖于外层函数的 n 变量
}

如何让它执行后就摆脱对 n 的依赖呢？

• 不能等递归回来再做加法，那样就必须保留外层的 n
• 把 n 当做内层函数的一个参数传进去，这时 n 就属于内层函数了
• 传参时就完成累加, 不必等回来时累加

sum(n - 1, n + 累加器)

 

改写后代码如下

@tailrec
def sum(n: Long, accumulator: Long): Long = {
    if (n == 1) {
        return 1 + accumulator
    } 
    return sum(n - 1, n + accumulator)
}

• accumulator 作为累加器
• @tailrec 注解是 scala 提供的，用来检查方法是否符合尾递归
• 这回 sum(10000000, 0) 也没有问题，打印 50000005000000

 

执行流程如下，以伪码表示 sum(4, 0)

// 首次调用
def sum(n = 4, accumulator = 0): Long = {
    return sum(4 - 1, 4 + accumulator)
}

// 接下来调用内层 sum, 传参时就完成了累加, 不必等回来时累加，当内层 sum 调用后，外层 sum 空间没必要保留
def sum(n = 3, accumulator = 4): Long = {
    return sum(3 - 1, 3 + accumulator)
}

// 继续调用内层 sum
def sum(n = 2, accumulator = 7): Long = {
    return sum(2 - 1, 2 + accumulator)
}

// 继续调用内层 sum, 这是最后的 sum 调用完就返回最后结果 10, 前面所有其它 sum 的空间早已释放
def sum(n = 1, accumulator = 9): Long = {
    if (1 == 1) {
        return 1 + accumulator
    }
}

本质上，尾递归优化是将函数的递归调用，变成了函数的循环调用

 

改循环避免爆栈

public static void main(String[] args) {
    long n = 100000000;
    long sum = 0;
    for (long i = n; i >= 1; i--) {
        sum += i;
    }
    System.out.println(sum);
}

 

5.8 递归时间复杂度-Master theorem

5.8.1 公式

若有递归式

其中

• T(n) 是问题的运行时间，n 是数据规模
• a 是子问题个数
• T(\frac{n}{b}) 是子问题运行时间，每个子问题被拆成原问题数据规模的 \frac{n}{b}
• f(n) 是除递归外执行的计算

令 x = \log_{b}{a}，即 x = \log_{子问题缩小倍数}{子问题个数}

那么

 

5.8.2 代入数据例题

例1

T(n) = 2T(\frac{n}{2}) + n^4

• 此时 x = 1 < 4(n的c次方，c=4)，由后者决定整个时间复杂度 \Theta(n^4)
• 如果觉得对数不好算，可以换为求【b 的几次方能等于 a】

 

例2

T(n) = T(\frac{7n}{10}) + n

• a=1, b=\frac{10}{7}, x=0, c=1
• 此时 x = 0 < 1，由后者决定整个时间复杂度 \Theta(n)

 

例3

T(n) = 16T(\frac{n}{4}) + n^2

• a=16, b=4, x=2, c=2
• 此时 x=2 = c，时间复杂度 \Theta(n^2 \log{n})

 

例4

T(n)=7T(\frac{n}{3}) + n^2

• a=7, b=3, x=1.?, c=2
• 此时 x = \log_{3}{7} < 2，由后者决定整个时间复杂度 \Theta(n^2)

 

例5

T(n) = 7T(\frac{n}{2}) + n^2

• a=7, b=2, x=2.?, c=2
• 此时 x = log_2{7} > 2，由前者决定整个时间复杂度 \Theta(n^{\log_2{7}})

 

例6

T(n) = 2T(\frac{n}{4}) + \sqrt{n}

• a=2, b=4, x = 0.5, c=0.5
• 此时 x = 0.5 = c，时间复杂度 \Theta(\sqrt{n}\ \log{n})

 

5.8.3 实际运用例题

例7. 二分查找递归

int f(int[] a, int target, int i, int j) {
    if (i > j) {
        return -1;
    }
    int m = (i + j) >>> 1;
    if (target < a[m]) {
        return f(a, target, i, m - 1);
    } else if (a[m] < target) {
        return f(a, target, m + 1, j);
    } else {
        return m;
    }
}

• 子问题个数 a = 1，（每次递归时只有一个出口）
• 子问题数据规模缩小倍数 b = 2，（数据规模每次缩小一半）
• 除递归外执行的计算是常数级 c=0，（比较运算，移位运算）

综上：T(n) = T(\frac{n}{2}) + n^0

• 此时 x=0 = c，时间复杂度 \Theta(\log{n})

 

例8. 归并排序递归

void split(B[], i, j, A[])
{
    if (j - i <= 1)                    
        return;                                
    m = (i + j) / 2;             
    
    // 递归
    split(A, i, m, B);  
    split(A, m, j, B); 
    
    // 合并
    merge(B, i, m, j, A);
}

• 子问题个数 a=2
• 子问题数据规模缩小倍数 b=2
• 除递归外，主要时间花在合并上，它可以用 f(n) = n 表示

T(n) = 2T(\frac{n}{2}) + n

• 此时 x=1=c，时间复杂度 \Theta(n\log{n})

 

例9. 快速排序递归

algorithm quicksort(A, lo, hi) is 
  if lo >= hi || lo < 0 then 
    return
  
  // 分区
  p := partition(A, lo, hi) 
  
  // 递归
  quicksort(A, lo, p - 1) 
  quicksort(A, p + 1, hi) 

• 子问题个数 a=2，（两次递归）
• 子问题数据规模缩小倍数
  • 如果分区分的好，b=2
  • 如果分区没分好，例如分区1 的数据是 0，分区 2 的数据是 n-1
• 除递归外，主要时间花在分区上，它可以用 f(n) = n 表示

 

情况1 - 分区分的好

T(n) = 2T(\frac{n}{2}) + n

• 此时 x=1=c，时间复杂度 \Theta(n\log{n})

 

情况2 - 分区没分好

T(n) = T(n-1) + T(1) + n

• 此时不能用主定理求解

---

 

5.9 递归时间复杂度-展开求解

像下面的递归式，都不能用主定理求解

例1 - 递归求和

long sum(long n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

T(n) = T(n-1) + c（if判断，加法），T(1) = c

下面为展开过程

T(n) = T(n-2) + c + c

T(n) = T(n-3) + c + c + c

...

T(n) = T(n-(n-1)) + (n-1)c

• 其中 T(n-(n-1)) 即 T(1)
• 带入求得 T(n) = c + (n-1)c = nc，(c是常数，时间复杂度里可以省略)

时间复杂度为 O(n)

 

例2 - 递归冒泡排序

// 未优化版本
void bubble(int[] a, int high) {
    if(0 == high) {
        return;
    }
    for (int i = 0; i < high; i++) {
        if (a[i] > a[i + 1]) {
            swap(a, i, i + 1);
        }
    }
    bubble(a, high - 1);
}

T(n) = T(n-1) + n（这里是n，for循环内n次比较），T(1) = c

下面为展开过程

T(n) = T(n-2) + (n-1) + n

T(n) = T(n-3) + (n-2) + (n-1) + n

...

T(n) = T(1) + 2 + ... + n = T(1) + (n-1)\frac{2+n}{2} = c + \frac{n^2}{2} + \frac{n}{2} -1

时间复杂度 O(n^2)

注：

• 等差数列求和为 个数*\frac{\vert首项-末项\vert}{2}

 

例3 - 递归快排

快速排序分区没分好的极端情况

T(n) = T(n-1) + T(1) + n，T(1) = c

T(n) = T(n-1) + c + n

下面为展开过程：

T(n) = T(n-2) + c + (n-1) + c + n

T(n) = T(n-3) + c + (n-2) + c + (n-1) + c + n

...

T(n) = T(n-(n-1)) + (n-1)c + 2+...+n = \frac{n^2}{2} + \frac{2cn+n}{2} -1

时间复杂度 O(n^2)

 

不会推导的可以进入 https://www.wolframalpha.com/

• 例1 输入 f(n) = f(n - 1) + c, f(1) = c
• 例2 输入 f(n) = f(n - 1) + n, f(1) = c
• 例3 输入 f(n) = f(n - 1) + n + c, f(1) = c

 

5.10 【递归练习】

5.10.1 兔子问题

• 第一个月，有一对未成熟的兔子（黑色，注意图中个头较小）
• 第二个月，它们成熟
• 第三个月，它们能产下一对新的小兔子（蓝色）
• 所有兔子遵循相同规律，求第 n 个月的兔子数

分析

兔子问题如何与斐波那契联系起来呢？设第 n 个月兔子数为 f(n)

• f(n) = 上个月兔子数 + 新生的小兔子数
• 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
• 因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
• 上个月兔子数，即 f(n-1)
• 上上个月的兔子数，即 f(n-2)

因此本质还是斐波那契数列，只是从其第一项开始

 

5.10.2 爬楼梯问题

• 楼梯有 n 阶
• 青蛙要爬到楼顶，可以一次跳一阶，也可以一次跳两阶
• 只能向上跳，问有多少种跳法

分析

n	跳法	规律
1	(1)	暂时看不出
2	(1,1) (2)	暂时看不出
3	(1,1,1) (1,2) (2,1)	暂时看不出
4	(1,1,1,1) (1,2,1) (2,1,1) (1,1,2) (2,2)	最后一跳，跳一个台阶的，基于f(3) 最后一跳，跳两个台阶的，基于f(2)
5	...	...

• 因此本质上还是斐波那契数列，只是从其第二项开始。

有坑：对应 leetcode 题目 70. 爬楼梯 - 力扣（LeetCode）

记忆法：

普通递归，显示超时，使用计划法优化，算出来的值存在数组里，需要时随用随取。以下代码初始时没有填充数组，值为0：

动态规划（原始）：

在方法内用数据循环获取值，无方法递归

动态规划（循环数组）：

通过三个数据不断滚动，实现降低空间复杂度为O(1)

更多解法在此忽略。。。

 

5.10.3 汉诺塔

Tower of Hanoi，规定：

• 一次只能移动一个圆盘
• 小圆盘上不能放大圆盘

下面的动图演示了4片圆盘的移动方法

使用程序代码模拟圆盘的移动过程，并估算出时间复杂度

思路

• 假设每根柱子标号 a，b，c，每个圆盘用 1，2，3 ... 表示其大小，圆盘初始在 a，要移动到的目标是 c
• 如果只有一个圆盘，此时是最小问题，可以直接求解
  • 移动圆盘1 a \mapsto c

  

• 如果有两个圆盘，那么
  • 圆盘1 a \mapsto b
  • 圆盘2 a \mapsto c
  • 圆盘1 b \mapsto c

  

• 如果有三个圆盘，（忽略中间过程）那么
  • 圆盘1+2 a \mapsto b
  • 圆盘3 a \mapsto c
  • 圆盘1+2 b \mapsto c

  

• 如果有四个圆盘，那么
  • 圆盘 123 a \mapsto b
  • 圆盘4 a \mapsto c
  • 圆盘 123 b \mapsto c

 

题解

package algorithms.recursion_multi;

import org.springframework.util.StopWatch;

import java.util.LinkedList;

/**
 * 递归汉诺塔
 */
public class E02HanoiTower {
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();

    /**
     * 初始化原盘
     * @param n 个数
     */
    static void init(int n) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);  // 大的原盘在底部  4 3 2 1
        }
    }

    /**
     * <h3>移动圆盘</h3>
     *
     * @param n 圆盘个数
     * @param a 由
     * @param b 借
     * @param c 至
     * 注意递归方法里的形参和实参名字不一样
     */
    static void move(int n, LinkedList<Integer> a,
                     LinkedList<Integer> b,
                     LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        move(n - 1, a, c, b);   // 把 n-1 个盘子由a,借c,最终移至b
        c.addLast(a.removeLast()); // 把最后的盘子由 a 移至 c
//        print();
        move(n - 1, b, a, c);   // 把 n-1 个盘子由b,借a,移至c
    }

    // T(n) = 2T(n-1) + c,  T(n)=c(2^n-1), 时间复杂度：O(2^n)


    public static void main(String[] args) {
        StopWatch sw = new StopWatch();
        int n = 1;
        init(n);
        print();
        sw.start("n=1");
        move(n, a, b, c);
        sw.stop();
        print();
        System.out.println(sw.prettyPrint());
    }

    private static void print() {
        System.out.println("----------------");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}

 

5.10.4 杨辉三角

分析

把它斜着看

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

• 行 i，列 j，那么 [i][j] 的取值应为 [i-1][j-1] + [i-1][j]
• 当 j=0 或 i=j 时，[i][j] 取值为 1

 

题解：

    /**
     * <h3>直接递归(未优化)</h3>
     *
     * @param i 行坐标
     * @param j 列坐标
     * @return 该坐标元素值
     */
    private static int element(int i, int j) {
        if (j == 0 || i == j) {
            return 1;
        }
        return element(i - 1, j - 1) + element(i - 1, j);
    }

    /**
     * 补足每行前面的空格
     * @param n 总行数
     * @param i 第几行（索引）
     */
    private static void printSpace(int n, int i) {
        int num = (n - 1 - i) * 2;
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

    public static void print(int n) {
        for (int i = 0; i < n; i++) {
//            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element(i, j));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
//        System.out.println(element(4, 2));
        print2(6);
    }

 

上面解法，实际运行时，重复计算的数据很多，可以用 static AtomicInteger counter = new AtomicInteger(0) 来查看递归函数的调用总次数

事实上，可以用 memoization 来进行优化：

    /**
     * <h3>优化1 - 使用二维数组记忆法</h3>
     *
     * @param triangle 二维数组
     * @param i        行坐标
     * @param j        列坐标
     * @return 该坐标元素值
     */
    private static int element1(int[][] triangle, int i, int j) {
        if (triangle[i][j] > 0) {  // 初始值为0，大于0表示已经有值
            return triangle[i][j];
        }

        if (j == 0 || i == j) {
            triangle[i][j] = 1;
            return 1;
        }
        triangle[i][j] = element1(triangle, i - 1, j - 1) + element1(triangle, i - 1, j);
        return triangle[i][j];
    }

    public static void print1(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) { // 行
            triangle[i] = new int[i + 1];  // 第0行，有1列
//            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element1(triangle, i, j));
            }
            System.out.println();
        }
    }

 

优化2（动态规划）：

将二维数组变为一维，实现数组重用

            1   3   3   1
            1   4   6   4   1
        
假如已知：  1   3   3   1   0
新一行新的最后一位，为当前值+前一位，0+1=1，   1   3   3   1   1
倒数第二位则：1+3=4，  1   3   3   4   1
倒数第三位：3+3=6，  1   3   6   4   1
...

    /**
     * <h3>优化2 - 使用一维数组记忆法</h3>
     * i 行号index
     */
    /*
        0   0   0   0   0   0   初始状态
        1   0   0   0   0   0   i=0
        1   1   0   0   0   0   i=1
        1   2   1   0   0   0   i=2
        1   3   3   1   0   0   i=3
        1   4   6   4   1   0   i=4 *
     */
    private static void createRow(int[] row, int i) {
        if (i == 0) {
            row[0] = 1;
            return;
        }
        // 生成每一行的数据，从尾部开始求值，第i行的最后一个索引为i
        for (int j = i; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }

    public static void print2(int n) {
        int[] row = new int[n];
        for (int i = 0; i < n; i++) { // 输出每一行
            createRow(row, i);
//            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", row[j]);
            }
            System.out.println();
        }
    }

力扣对应题目，但递归不适合在力扣刷高分，因此只列出相关题目，不做刷题讲解了

• 118. 杨辉三角 - 力扣（LeetCode）
• 119. 杨辉三角 II - 力扣（LeetCode）

118：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }
}

 

119：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]

示例 2:
输入: rowIndex = 0
输出: [1]

示例 3:
输入: rowIndex = 1
输出: [1,1]

// 使用滚动数组的思想优化空间复杂度。
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> cur = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }
}