二分

二分思想

  • 二分思想其实非常简单，就是我们小时候玩的猜数字游戏：我说一个数字，你来猜，每次我会说大了或者小了，然后你根据我的回答去调整，继续猜，知道猜到为止
  • 二分其实不仅仅可以二分，还可以三分，N 分….这是一种思想
  • 二分虽然简单，但往往越简单的东西细节越重要
    • while（left < right）还是 while（left <= right）？这里有什么不同，我们在什么情况该用哪种？
    • left = mid + 1 ,right = mid - 1 还是 left = mid + 1，right = mid？到底用哪种？

二分样板

基本的二分查找

  • 场景：在 nums 数组中搜索一个数（target），如果存在 返回索引，不存在 返回 -1；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; // 注意
//退出条件 left == right + 1
    while(left <= right) {
        int mid = left + (right - left) / 2;
        // int mid = left + ((right -left) >> 1) 还可以用右移操作代替除法 提高性能
        if(nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}
或
int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; // 注意
    //退出条件 left == right
    while(left < right) {
        int mid = left + (right - left) / 2;
        // int mid = left + ((right -left) >> 1) 还可以用右移操作代替除法 提高性能
        if(nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return nums[left] == target ? left : -1;
}
  • 循环条件：left <= right
  • 中间位置计算：int mid = left + (right - left) / 2;
  • 左边界更新：left = mid + 1;
  • 右边界更新：right = mid - 1;
  • 返回值： mid / -1
  • 左右边界相遇时候 返回值只会是：
    • left/mid , right (left, mid 指向同一个数，right 指向它的下一个数)
    • left/mid/right （left, mid, right 指向同一个数）
  • 为什么 while 循环的条件中是 <=，而不是 <？

因为 right = nums.length - 1 ，是最后一个元素索引，而非 nums.length （数组的长度）

假如right取前者意味着此时的区间 为：两端都闭区间 [left, right]

假如right取后者意味着此时的区间 为：左闭右开区间 [left, right)

在 while 循环中，我们什么时候应该停止搜索呢？

  1. 找到了目标值

    1
    2
    if(nums[mid] == target)
        return mid;

  2. 没有找到目标值，while 循环终止

    1. while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]

      比如 right = 1，那么区间此时是[2,1] 在这个区间内不存在任何一个实数吧？

    2. while(left < right) 的终止条件是 left == right，写成区间的形式就是 [left, right]

      比如 right = 1，那么区间此时是[1,1]，在这区间此时是存在一个数 1 的, 但我们的这个数 1 是没有被检索的 被漏掉了

      必须要打补丁，判断一下这个 left 索引对应的值是否等于目标值，是的话返回索引，不然返回 -1 ;

      ps：right 还是 length - 1 哦

      1
      return nums[left] == target ? left : -1;
  • 为什么 left = mid + 1，right = mid - 1？

因为我们的搜索区间是左闭右闭的：[left, right]，那么收缩的可能性就两种 向左或向右

向左：[left, mid - 1]

向右：[mid + 1, right]

寻找左侧边界的二分查找

  • 什么叫寻找左侧边界 意思是 假如在一个nums = [1,2,2,2,3]中，target 为 2,我想要得到最左侧的 2 也就是索引为 1 的二分查找法
  • 由于这种题我经常分不清 right 和 while 循环条件中的配合问题 于是我把全部的四种（2×2）方法全部写了一遍！以后再应该不会出问题了吧！！！

最后一位 + < 的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //此时退出条件是：left == right
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                right = mid;
            } else if(nums[mid] == target) {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

  • right 初始值：nums.length - 1
  • 循环条件：left < right
  • 中间位置计算： int mid = left + (right - left) / 2;
  • 左边界更新：left = mid + 1
  • 右边界更新：right = mid
  • 返回值： nums[left] == target ? left : -1

数组长度 + < 的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        int left = 0;
        int right = nums.length;
        //终止条件为left == right
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid;
            else if(nums[mid] == target)
                right = mid;
        }
        if(left == nums.length) return -1;
        else return nums[left] == target ? left : -1;
    }
}

  • 这写法和上面不同点在于我的 right 取值 假如是最后一个索引而非长度，那就不需要特判 不然的话有可能越界 要特判

  • right 初始值：nums.length

  • 循环条件：left < right

  • 中间位置计算： int mid = left + (right - left) / 2;

  • 左边界更新：left = mid + 1

  • 右边界更新：right = mid

  • 返回值：

    • if(left == nums.length) return -1;
    • else return nums[left] == target ? left : -1;

最后一位 + <= 的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //此时退出条件是 left == right + 1
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                //由于我们右边界是能取到的 因此必须收缩哦
                right = mid - 1;
            } else if(nums[mid] == target) {
                right = mid - 1;
            }
        }
        //如果target是大于数组里面全部数时候，left是=nums.length的 会越界 因此必
        if (left >= nums.length || nums[left] != target)  return -1;
        return left;
    }
}
  • right 初始值：nums.length - 1
  • 循环条件：left <= right
  • 中间位置计算： int mid = left + (right - left) / 2;
  • 左边界更新：left = mid + 1
  • 右边界更新：right = mid - 1
  • 返回值：
    • if (left >= nums.length || nums[left] != target) return -1;
    • else return left;

数组长度 + <= 的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        //此时退出条件是 left == right + 1
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //防止越界
            if(mid == nums.length) break;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                //由于我们右边界是能取到的 因此必须收缩哦
                right = mid - 1;
            } else if(nums[mid] == target) {
             	right = mid - 1;
            }
        }
        //如果target是大于数组里面全部数时候，left是=nums.length的 会越界 因此必
        if (left >= nums.length || nums[left] != target)  return -1;
        else return left;
    }
}
  • right 初始值：nums.length
  • 循环条件：left <= right
  • 中间位置计算： int mid = left + (right - left) / 2;
  • 左边界更新：left = mid + 1
  • 右边界更新：right = mid - 1
  • 返回值：
    • if (left >= nums.length || nums[left] != target) return -1;
    • else return left;

寻找左侧 总结

我们看上面的四个 Demo 代码，我们不难发现，我们为了限制我们的左侧是不能被取到的，我们的配合其实无非就那么几种

假如 while 是 <= ，无论初始值我们的 right 是多少，那么我们的 right 的变化就是 mid - 1 保证 向左收缩

假如 while 是< ，我们的 right 变化就是取 mid；

寻找右侧边界的二分查找

  • 什么叫寻找右侧边界 意思是 假如在一个nums = [1,2,2,2,3]中，target 为 2,我想要得到最右侧的 2 也就是索引为 3 的二分查找法

最后一位 + <的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //此时退出条件是：left == right
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] == target) {
                left = mid + 1;
            }
        }
        if(right == 0 && nums[right] != target) return -1;
        if(nums[right] == target) return right;
        else return nums[right - 1] == target ? right - 1 : -1;
    }
}
  • right 初始值：nums.length - 1
  • 循环条件：left < right
  • 中间位置计算： int mid = left + (right - left) / 2;
  • 左边界更新：left = mid + 1
  • 右边界更新：right = mid
  • 返回值：
    • if(right == 0 && nums[right] != target) return -1;
    • if(nums[right] == target) return right;
    • else return nums[right - 1] == target ? right - 1 : -1;

数组长度 + < 的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        //此时退出条件是：left == right
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] == target) {
                left = mid + 1;
            }
        }
        if(left == 0) return -1;
        return nums[right - 1] == target ? (right - 1) : -1;
    }
}
  • right 初始值：nums.length
  • 循环条件：left < right
  • 中间位置计算： int mid = left + (right - left) / 2;
  • 左边界更新：left = mid + 1
  • 右边界更新：right = mid
  • 返回值：
    • if(left == 0) return -1;
    • return nums[right - 1] == target ? (right - 1) : -1;

最后一位 + <= 的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //此时退出条件是：left == right
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] == target) {
                left = mid + 1;
            }
        }
        if(right < 0 || nums[right] != target) return -1;
        return nums[right] == target ? right : -1;
    }
}

  • right 初始值：nums.length - 1

  • 循环条件：left <= right

  • 中间位置计算： int mid = left + (right - left) / 2;

  • 左边界更新：left = mid + 1

  • 右边界更新：right = mid - 1

  • 返回值 ：

    • if(right < 0 || nums[right] != target) return -1;
    • return nums[right] == target ? right : -1;

数组长度 + <= 的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        //此时退出条件是：left == right + 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if(mid == nums.length) break;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] == target) {
                left = mid + 1;
            }
        }
        //检查越界
        if(right < 0)  return -1;
        if(right >= 0 && right < nums.length && nums[right] == target) return right;
        if(nums[right - 1] == target) return right - 1;
        return -1;
    }
}
  • right 初始值：nums.length
  • 循环条件：left <= right
  • 中间位置计算： int mid = left + (right - left) / 2;
  • 左边界更新：left = mid + 1
  • 右边界更新：right = mid - 1
  • 返回值：
    • if(right < 0) return -1;
    • if(right >= 0 && right < nums.length && nums[right] == target) return right;
    • if(nums[right - 1] == target) return right - 1;return -1;

第四种方法比较麻烦，不是很推荐，其实写了种也不是为了把八种写法都记住；

只是想通过一次次排查问题找到二分的各种细节，让以后的二分之路更轻松! 最好就是用一套规范把，比如说以后都用 最后一位 + <= 这种框架，然后里面细节按照题意再改就好了！

八种方法都测试过了：都是 ok 的

image-20201020140256461

二分-LeetCode 相关

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

image-20210828162342979

一开始看到这个题，想到的是进行两个有序数组的合并，然后根据 m + n 的奇偶数情况去求出中位数

但这样的做法时间复杂度为$O（m + n）$，本题的建议是$Olong（m + n）$,看到了这个$log$我们想到的是二分查找。

那么如何用二分查找去帮助我们解决这道题呢？

通过二分法，我们在两个有序数组寻找中位数的思路就是：

使用一条分割线把两个数组分别分割成两部分，同时达到以下两个要求

  1. 分割线的左右两边元素个数相同 或者 分割线的左侧元素比右侧元素个数多 1 个
  2. 分割线左边的所有元素数值 <= 分割线右边的所有元素数值

image-20210828164132396

达到这个要求后，我们可以根据元素个数之和的奇偶情况去得到中位数：

  • 数组元素之和为奇数时

image-20210828164427270

中位数 = 分割线的左侧元素中较大的那个数

  • 数组元素之和为偶数时

image-20210828164611196

中位数 = （分割线的左侧元素中较大的那个数 + 分割线右侧元素中较小的那个数）/ 2

  • 具体实现方法

要满足分割线的第一条性质：分割线的左右两边元素个数相同 或者 分割线的左侧元素比右侧元素个数多 1 个

设：数组 1 长度为 m，数组 2 长度为 n

  1. m + n 为奇数时，分割线划分位置 = $m + n + 1 / 2$
  2. m + n 为偶数时：分割线划分位置 = $m + n / 2$，但由于 java 的除法是向下取整的，因此也可以写成 $m + n + 1 / 2$，这样就可以不用分奇偶讨论了

要满足分割线的第二条性质：分割线左边的所有元素数值 <= 分割线右边的所有元素数值

我们只需要满足，在交叉部分：

  1. 第一个数组在分割线左侧的最大数值 >= 第二个数组在分割线右侧的最小数值

    如果不满足，说明分割线左边的数值太大了

    需要将中位数分割线在第一个数组的位置左移（相应的，分割线在第二个数组位置就会右移）

    image-20191216165734716

  2. 第二个数组在分割线左侧的最大数值 >= 第一个数组在分割线右侧的最小数值

    如果不满足，说明分割线右边的数值太小了。

    需要将中位数分割线在第一个数组的位置右移（相应的，分割线在第二个数组位置就会左移）

    image-20191216164952779

  • 极端情况

细节 1：

我们设 i 为在第一个数组中（我们称为 A）划分分割线的位置，j 为在第二个数组（我们称为 B）中划分分割线的位置

那难道两个数组哪个作为 A 哪个作为 B 是无所谓的吗？

不是的，在搜索的过程中，我们会比较分割线左边和右边的数，即 nums[i]、 nums[i - 1]、 nums[j]、 nums[j - 1]，因此 这几个数的下标不能越界

假如我们选用长数组作为 A，短数组作为 B，如下图所示：

image-20191216170435095

此时，分割线在第 2 个数组的左边没有值，会导致 nums2[j - 1] 的访问越界。因此我们必须在短的数组上搜索 i 。i 的定义是分割线的右边，而它的左边一定有值。这样就能保证，分割线在第 2 个数组的左右两边一定有元素，即分割线一定可以在第 2 个数组的中间切一刀。

因此，在正式算法执行前，需要进行数组的交换（如果有必要的话），以保证第一个数组为短数组

细节 2：

上面明确了，要在在短数组上搜索边界 i ，还真就可能遇到 i 或者 j 的左边或者右边取不到元素的情况，它们一定出现在退出循环的时候。

image-20191216170934239

为此，我们单独做一个判断就可以了。

image-20191216171333129

最后，我们把关心的「边界线」两旁的 4 个数的极端情况都考虑一下：

  • 考虑 nums1：
    • 当 i = 0 的时候，对应上图右边，此时数组 nums1 在红线左边为空，可以设置 nums1_left_max = 负无穷。
      这样在最终比较的时候，因为左边部分要选择出最大值，它一定不会被选中，于是能兼容其它情况；
    • 当 i = m 的时候，对应上图左边，此时数组 nums1 在红线右边为空，可以设置 nums1_right_min = 正无穷。
      这样在最终比较的时候，因为右边蓝色部分要选择出最小值，它一定不会被选中，于是能兼容其它情况。
  • 考虑 nums2：
    • 当 j = 0 的时候，对应上图左边，此时数组 nums2 在红线左边为空，可以设置 nums2_left_max = 负无穷。
      这样在最终比较的时候，因为左边部分要选择出最大值，它一定不会被选中，于是能兼容其它情况；
    • 当 j = n 的时候，对应上图右边，此时数组 nums2 在红线右边为空，可以设置 nums2_right_min = 正无穷。
      这样在最终比较的时候，因为右边蓝色部分要选择出最小值，它一定不会被选中，于是能兼容其它情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //保证第一个数组为短数组
        if(nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }

        int m = nums1.length;
        int n = nums2.length;

        //分割线左侧需要满足的条件：元素个数为 m + n + 1 / 2
        int LeftTotal = (m + n + 1) / 2;

        //由于在第二个数组的分割线位置取决于在第一个数组的位置
        //因此这里的left 和 right 只需要在第一个数组上面移动

        int left = 0;
        int right = m;

        while(left < right) {

            int i = left + (right - left + 1) / 2;
            int j = LeftTotal - i;

            //如果第一个数组在线左侧最大值 >= 第二个数组在线右侧最小值
            //去小区间搜
            if(nums1[i - 1] >= nums2[j]) {
                right = i - 1;
            //第二个数组在线左侧最大值 >= 第一个数组在线右侧最小值
            //去大区间搜
            } else {
                left = i;
            }

        }

        //得到了i和j, 即 分割线在两个数组上线的具体位置

        int i = left;
        int j = LeftTotal - i;

        //进行边界线的特判
        //1.考虑nums1 得到第一个数组线左侧最大和右侧最小
        int nums1_left_max = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1_right_min = i == m ? Integer.MAX_VALUE : nums1[i];
        //2.考虑nums2 得到第二个数组线左侧最大
        int nums2_left_max = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2_right_min = j == n ? Integer.MAX_VALUE : nums2[j];

        //最后, 根据奇偶性求解
        if((m + n) % 2 == 0) {
            //偶数的话，返回（分割线左侧元素中较大那个数 + 分割线右侧元素中较小那个数） / 2
            return (double) ((Math.max(nums1_left_max, nums2_left_max)) + Math.min(nums1_right_min, nums2_right_min)) / 2;
        } else {
            //奇数的话，返回 分割线左侧元素中较大的那个数
            return Math.max(nums1_left_max, nums2_left_max);
        }

69.X 的平方根

image-20201020181457188

4 的平凡根是 2，把 4 展开成[1,2,3,4]的数组，用二分法找 4 的平凡根为 2，正好在数组中间

9 的平凡根是 3，把 9 展开成[1,2,3,4,5,6,7,8,9]，二分法找 9 的平凡根为 3，在数组偏左侧

随着数的增加，其平凡根会逐渐相对【偏向左】

但这都是我们自己的猜测，我们需要算一下这个【边界值】，看看从什么时候开始一个数的平方根从这个数的一半开始向左收缩：

$(a/2)^2 ≥ a$ 得出结果为 $a ≥ 4 或 a ≤ 0$

因此边界值为 4。意味着小于 4 的数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int mySqrt(int x) {
        //特判 不然会出现除数为0的情况
        if(x == 0) return 0;
        if(x == 1 || x == 2) return 1;
        int left = 0;
        int right = x - 1;
        //结束条件 left == right + 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(mid  == x / mid) {
                return mid;
            } else if(mid > x / mid) {
                right = mid - 1;
            } else if(mid < x / mid) {
                left = mid + 1;
            }
        }
        //退出的时候left > right,所以right反而是偏小的那个数
        //由于是向下去整，我们就取小一点的那个数
        return right;
    }
}

DP（Dynamic Programming）

DP 思想/概念

技术参考：《运筹学》第三版 - 清华大学出版社

要明白 DP 首先需要明白五个名词:

  • 阶段：一个大问题过程拆分成若干个有关联的阶段，用于按照一定的次序去求解问题

    划分的依据是什么呢？比如说你要完成一个项目，我每天做一点，这就是按照时间为单位划分

    我们写题一般以空间为单位（即数组）每个数组代表某一个特定的阶段

  • 状态：表示某阶段所处的状况/条件。再以数组为例：现在有一个数组int money[i] 这个 i 表示我在第 i 天，拥有着 money[i]这么多钱

    这句话：在第 i 阶段，拥有某种属性 就是状态

    • 状态应该具有的性质:无后效性，什么意思呢？简单来说就是 我未来变化只与此刻（此状态）相关，与我如何达到此刻（此状态无关）

  • 决策：状态不可能一成不变，肯定是要变化的。而造成状态改变的就是决策

    而决策往往有多种选择，在写题目的时候需要我们将题目的决策/选择抽象出来。

  • 策略：策略是按照顺序排列的决策的集合。我们的 DP 方法的终极目标就是求出：最优策略/最优解

  • 状态转移方程：决策 导致了 状态的变化，而状态转移方程就是决策的具象化，在不同题目中的转移方式多种多样（比如取两种决策中利益最大的啊，把之前的状态加在一起啊之类的）

    这也是我们后面学习 DP 的重点问题！一定要重点理解

  • DP 的最优性原理和最优性定理（理论依据）:

    img

    简单来说就是:子问题最优解会直接导致到整个问题的最优解（局部最优化 → 全局最优化）

    以下面一个例子来解释:

    如下图所示，如果给定从 A 到 C 的最优路线（这是前提，谨记），那么最优路线上任意一点 B 到 C 的路线 Ⅱ 必须是 B 到 C 的最优路线。

    image-20201122202839453

    换而言之：若：弧 AB+弧 Ⅱ = A→C 最优解，弧 Ⅱ 一定是 B→C 的最优路线

    证明：反证法：若弧 Ⅰ 是 B→C 是比弧 Ⅱ 有更小代价最小路线，那么 AB+弧 Ⅰ 就优于 AB+弧 Ⅱ，这与我们的前提:给定从 A 到 C 的最优路线（AB+弧 Ⅱ）是矛盾的

    QED

DP 解题思路

  • DP 解题思路
    • 确定状态：由于我们解决动态规划通常需要去开一个数组，既然是数组就需要明白其中的下标i 和 j代表什么意思
      • 研究最优策略最后一步
      • 大问题拆分成小问题，小问题划分成小小问题…
    • 转移方程：DP 解决问题的精髓就是这个，由不同的题不同考虑
    • 初始条件与边界条件：
      • 通常是 a[0]啊 a[1]的初值之类的
      • 数组不能越界，因为通常会在 i 和 j 上+-，很容易不小心就越界；
    • 计算顺序：记忆化之前我们运算所得到的结果。

案例分析

image-20201122210755238

暴力递归法:

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int fib(int N) {
        if(N == 0) return 0;
        return func(N);
    }
    int func(int N) {
        if(N == 1 || N == 2) return 1;
        return func(N - 1) + func(N - 2);
    }
}

image-20201122211510883

不难发现，这种方法代码简单，但是可以说是十分低效了。

我们画一下递归树：

image-20201122212021418

由递归树我们也不难发现：这个算法的时间复杂度是 O(2^n)，为一个指数级别

观察这颗树，我们发现：f（8）、f（7）….都是重复计算过了的——这就是 DP 问题第一个性质:重叠子问题

带备忘录递归/记忆化

上面我们发现了单纯递归的问题:重复计算

接下来介绍两种记忆化方法

自顶向下

为什么叫自顶向上呢？因为我一开始就想试图求出 N 对应的斐波那契数；

只不过求解该结果需要 F（N-1）和 F（N-2）罢了

那问题就转换成了 求 F（N - 1）和 F（N - 2）…

直到我们遇到了已知的 F（X）(也就是我们常说的 基本状态) ，那就可以往上返回了。

因此叫自顶向上（带备忘录的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int fib(int N) {
        if(N == 0) return 0;
        if(N == 1) return 1;
        int[] memory = new int[N + 1];
        memory[0] = 0;
        memory[1] = 1;
        return func(memory, N);
    }
    private int func(int[] memory, int n) {
        //特判
        if(n == 1 || n == 2) return 1;
        //如果记忆过了 直接return
        if(memory[n] != 0) return memory[n];
        //不然的话就递归寻找
        else memory[n] = func(memory, n -2) + func(memory, n - 1);
        //再返回
        return memory[n];
    }
}

自底向上

为什么叫自底向上呢?因为这种方法是已知了底层的值（这里指的是 F（0）= 0，F（1）= 1）

然后通过迭代的方法，用这两个 basedata 一步步推到 N

换句话说：就是从已知的最底层状态并达到最理想状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fib(int N) {
        if(N == 0) return 0;
        if(N == 1) return 1;
        int current = 0;
        //代替N = 0时的值
        int prev1 = 0;
        //代替N = 1时的值
        int prev2 = 1;
        for(int i = 2; i <= N; i++) {
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
        return current;
    }
}

DP 解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int N) {
        if(N == 0) return 0;
        if(N == 1) return 1;
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= N; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[N];
    }
}

发现了吗，这种解法与带备忘录的自顶向下递归十分类似；

事实上，那种方式就是在填这个 DP 表格。

有人会问，我这个代码哪里体现出了选择？或者说，哪里体现出了状态转移呢？

这就是状态转移方程:

image-20201125222534292

f（n）的状态是由状态 n - 1 与状态 n - 2 相加转移而来的

DP-LeetCode 相关

剑指 Offer 63.股票的最大利润

image-20201007160636576

这种题很容易判断出来用 DP 写，为什么呢，因为只可能在左侧买，右侧卖，那就不用考虑万一右边有更小的买入值怎么办了。

换而言之，只需要一直考虑局部最优解，那么答案肯定是整体的最优解。

这题思路:

用一个 min 去不停更新数组的最小值，让当前遍历到的数字去减去这个值，就是利润，与之前所得到的最大值比大小，更新最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProfit(int[] prices) {
        //注意 这题不能让max = Integer.MIN_VALUE
        //因为如果是这样的话 假如是从大到小排序的话 max值是负数，不符合题目要求，因为自作聪明，Error了一次
        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0 ; i < prices.length; i++) {
            if(prices[i] <= min) {
                //假如当前遍历到的值小于最小值，更新
                min = prices[i];
                //暂时跳出循环
                continue;
            }
            //比较最大值，更新
            max = Math.max(prices[i] - min, max);
        }
        return max;
    }
}

53.最大子序和

image-20201013204245170

用一个 DP 数组来进行动态规划

DP[i] 表示以 nums[i]结尾的连续子数组的最大和

何为连续?意思是中间不能断。如何做到?遇到了数组中每个值，要么加入序列，要么就当序列的头。

  • 确定状态：dp[i] 表示以 nums[i]结尾的连续子数组的最大和

  • 转移方程：

    1
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);

  • 初始值与边界条件：dp[0]为原数组第一个数值，因为我们的遍历是从第二个数开始的

  • 计算顺序：当遍历完整个数组的时候答案就出来了，因此是正序

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxSubArray(int[] nums) {
        //特判1
        if(nums.length == 0) return 0;
        //特判2
        if(nums.length == 1) return nums[0];
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = nums[0];
        for(int i = 1; i < n; i++) {
            //要么就把它纳入序列，要么把它当作开头
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            //比大小
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

70.爬楼梯

image-20201007184400404

这题太经典了，我写的第一道 DP 的题就是这个其实。

当时写到这个题就接触到了这种思想:

要爬上一层楼梯要几步?1 步 对吧；两层楼梯呢？1+1 步，ok，一次走两步 也 ok

那走三层呢?三层其实就是两层基础上又多走一层呗，那就直接用上了两层的走法再加一层走法就好了；后续同理

所以这题最重要的就是设立子问题：走上 n-1 层有多少种解法，走上 n-2 层又有多少种解法，两个之和就是上 n 层可能的组合数

  • 确定状态：dp[i]表示为走到了第 n 阶台阶的组合数

  • 转移方程：

    1
    dp[i] = dp[i - 2] + dp[i - 1];

  • 初始与边界条件：好像没有特别的边界条件

  • 计算顺序：正序

ps：我第一次解出来这个用的是迭代 那我顺便写一下迭代写法 8

迭代解法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int climbStairs(int n) {
        if(n == 1)
            return 1;
        else if(n == 2)
            return 2;
        else {
            int first = 1,second = 2,third = 0;
            for(int i = 3;i <= n;i++){
                third = first+second;
                first = second;
                second = third;
            }
            return second;
        }
    }
}

DP 解法代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2 ; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

5.最长回文子串

image-20201008142356074

这道题第一次纯暴力直接超时，后来想到了中心扩散的办法：枚举字符串各位置然后向两边扩散，但这方法感觉不具备一般性，于是虚心学习了 DP 的解法，这道题最优解法应该是线性的马拉车算法，但那个太难了且同样不具备一般性，我以后再学吧…

DP 思路:

用一个二维数据 dp[I] [j]来表示字符串 i….j 是否为回文字符串；

  • 状态转移方程：
1
dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];

什么意思呢？意思就是i...j假如是回文串的话 等价于 两端字符相同且其中间部分也为回文字符串

  • 边界条件：假如 s[i] == s[j]且长度为 2 或者 3 那么一定是回文字符串了 ；

DP 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public String longestPalindrome(String s) {
        //特判1
        if(s.length() == 0 || s == null) return "";
        //特判2 假如是一个字符肯定是回文串
        String ans = s.substring(0,1);
        int len = s.length();
        char[] a = s.toCharArray();
        boolean[][]dp = new boolean[len][len];
        for(int i = 0 ; i < len; i++) {
            dp[i][i] = true;
        }
        //j用于遍历数组 i紧随其后
        for(int j = 1 ; j < len; j++) {
            for(int i = 0 ; i < j; i++) {
                //如果不相等，则为false
                if(a[i] != a[j]) {
                    dp[i][j] = false;
                } else {
                    //j - i < 3是什么意思呢？
                    //其实是当s[i..j]长度为2或3的时候 假如头尾相等那么这段肯定是回文串了
                    if(j - i < 3) {
                        dp[i][j] = true;
                        //否则取决于中间是否为回文串
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                //假如首位相同 且 长度比之前的答案长度要长 则重新截取
                if(dp[i][j] && j-i+1 > ans.length()){
                    ans = s.substring(i,j+1);
                }
            }
        }
        return ans;
    }
}

322.零钱兑换

image-20201008203417632

这题和之前的爬楼梯有异曲同工之妙，为什么呢？

我们爬楼梯爬 n 层；这题需要凑够 n 的数值

我们爬楼梯有爬 1 层，2 层；这题是用 a 元，b 元，c 元去凑；

ok，我们回到这题来，怎么解决呢？

假设有 k 枚硬币：a1,a2…ak 凑成了目标 amount 因此存在最后一枚硬币 ak，那么前面的面值加起来=amount-ak

没错吧？因此我们得到了原问题和子问题关系啦：最少用多少枚硬币拼成 amount→最少用多少枚硬币拼成 amount-ak

  • 确定状态：dp[n]表示当前的目标金额是 n，至少需要 dp[n]个硬币凑出该金额

  • 转移方程：

    image-20201125223125406

    i 为 最少用多少枚硬币拼成 i ；

    coin 为 我们可利用的硬币面值

    1
    dp[i] = Math.min(dp[i], dp[i - coin] + 1);

  • 初始条件与边界：

    • 边界:i - coin < 0 意思是不存在能凑成差值的方法，定义为正无穷
    • 初始条件：基准值，就是不能算出来的值，需要用到这个去推理得到其他的结果的值：dp[0] = 0 为什么呢 不需要硬币肯定是 0

  • 计算顺序：到底是应该直接从最大面值开始还是最小面值开始呢？

    为了算 dp[x] 我们需要用到 dp[x - 1]..d[x - 2] 因此是正序遍历

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int coinChange(int[] coins, int amount) {
        //特判1
        if(amount == 0) return 0;
        //特判2
        if(coins.length == 0) return  -1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);
        //迭代器遍历 直接取出数组每个数值 外层for循环所有选择的最小值
        for (int coin : coins) {
            //判断差值
            for(int i = coin ; i <= amount; i++) {
                //假如存在可以凑成差值的组合的话
                if(dp[i - coin] != Integer.MAX_VALUE) {
                    //状态转移 在已经有的组合 和 拼出i - coin枚硬币数+自己的一枚中选择一个少的
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        //假如有解的话 输出
        if(dp[amount] != Integer.MAX_VALUE) {
            return dp[amount];
        }
        return -1;
    }
}

面试题 08.11. 硬币

image-20201008212810143

为什么把这题放在零钱兑换下面呢 其实这两题大致相同，只不过一个是要在所有组合数中选择硬币数最小的；

而这题是统计所有的组合数

同样的方法:

  • 确定状态:dp[n]为组成总面额为 n 的情况数

  • 转移方程：

    1
    dp[i] = (dp[i] + dp[i - coin]) % 1000000007;

  • 初始条件与边界：dp[0] = 1 组成 0 的方法有 1 种，就是什么都不放，同时这也是边界限制条件 若 i - coin = 0 也就是面值正好时，可以只放一个硬币了 也就是 1

  • 计算顺序：同样是正序遍历

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int waysToChange(int n) {
        int[] coins = new int[]{1, 5, 10, 25};
        if(n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for(int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }
        return dp[n];
    }
}

剑指 Offer 47.礼物的最大价值

image-20201009163618327

这题就是模拟走迷宫，边走边 DP 求最大值就好了

  • 确定状态：dp[i] [j]为走到 i，j 处的最大值；

  • 转移方程：

    1
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

  • 初始条件与边界：这道题我是取了巧方法，并不是在原地图遍历的，而是额外开的一个二维数组模拟，同时我的行列都+了 1，有效保证上下左右都可以走，不然还得多考虑边界问题，很麻烦。

  • 计算顺序，由于起点在左上角，终点右下角，那么正序遍历就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxValue(int[][] grid) {
        //行
        int m = grid.length;
        //列
        int n = grid[0].length;
        //dp数组
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                //到达[i,j]只有两种可能性从[i - 1][j - 1]出发后先向右再向下或先向下再向右
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        //注意这里返回的就是dp[m][n]了 因为相当于把原地图放在了新dp图的左下方
        return dp[m][n];
    }
}

64.最小路径和

image-20201012103255728

这题和上面一题其实非常像，一开始我傻傻的把 Max 改成了 min 然后直接提交，结果错了，答案是 3 而不是 7。

后来我仔细画图走了一遍流程发现了问题。

我们由于不限定最上面一行只能向右走，最左边一行只能向下走（原点除外）；

导致了我们会跳过那些必走的格子，直接空降了。（因为这样肯定是最小的，逃避了必须走的路）

因此这题和上面的最大价值不一样，必须限定边界走法，那上一题为什么不用呢？因为他是取最大值，他巴不得多走一点路。

  • 确定状态：dp[i] [j]为走到 i，j 处的最小值；

  • 转移方程：

    如果是原点，那就是原地图原点

    1
    if(i == 1 && j == 1) dp[i][j] = grid[i - 1][j - 1];

    如果是最上面一行（除原点），那只能是由左边走到右边

    1
    else if(i == 1 && j != 1) dp[i][j] = dp[i][j - 1] +grid[i - 1][j - 1];

    如果是最左边一列（除原点），那只能是由上面走到下面

    1
    else if(i != 1 && j == 1) dp[i][j] = dp[i - 1][j] + grid[i - 1][j - 1];

    其余的话，和之前的没变，把 max 改成 min 即可

    1
    else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

  • 初始条件与边界：初始条件不用说了，dp 二维数组用 0 填充，表示价值为 0，边界条件这题就不能和上一问一样不去考虑了，必须考虑最上面和最左边

  • 计算顺序：左上角是起点，右下角是终点。正序遍历。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minPathSum(int[][] grid) {
        //行
        int m = grid.length;
        //列
        int n = grid[0].length;
        //dp数组
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == 1 && j == 1) {
                    dp[i][j] = grid[i - 1][j - 1];
                    //最左边一列（除了原点） 只能是由上面往下走
                } else if(i != 1 && j == 1) {
                    dp[i][j] = dp[i - 1][j] + grid[i - 1][j - 1];
                    //最上面一行（除了原点） 只能是由左边向右走
                } else if(i == 1 && j != 1) {
                    dp[i][j] = dp[i][j - 1] +grid[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
                }
            }
        }
        //注意这里返回的就是dp[m][n]了 因为相当于把原地图放在了新dp图的左下方
        return dp[m][n];
    }
}

673.最长递增子序列的个数

image-20201009212657392

这题有两个信息需要去记录：

  1. 递增子序列最长可以是多少
  2. 以不同索引结尾的序列的长度是多少

  • 确定状态

    • dp[i]表示以nums[i]结尾的最长递增子序列长度

  • count[i]表示以nums[i]结尾的最长递增子序列个数

  • 转移方程：

    1
    dp[i] = Math.max(dp[i], dp[j] + 1);
    1
    2
    3
     count[i] = count[j];
    or
     count[i] += count[j];

  • 初始条件与边界：dp[i]应该全部被初始化为 1，因为所有单个值可以成为一个长度为 1 的最长递增序列，同理 count[i]也应该被初始化为 1

  • 计算顺序：外层 i 遍历 [0…..n] ，内层 j 遍历 [0….i] 其中 j < i

这题的关键就在于统计 count 这个数组，count 数组更新需要这几个条件:

  1. nums[i] > nums[j] 后面数值要大于前面的

  2. dp[j] >= dp[i] 前面的 dp 数组要比后面的大 怎么可能呢?只有一种情况，那就是第一次遇到以 nums[i]结尾的最长递增子序列。此时的长度就为 dp[j] + 1 ，而count[i]也相应的等于count[j]；

    以nums[i]结尾的最长递增子序列的组合数=以nums[j]结尾的最长递增子序列的组合数

    这个可以这么理解：当 […j] 形成的组合数是值 A 的话，其每一种组合结尾补上 [i] ,即[…j,i]对于组合数本身是没有增加的，还是 A 值，唯独只是递增子序列的长度+1 了。

  3. dp[j] + 1 = dp[i]，假如之前的长度加上现在遍历到的长度=已经存在的 dp[i]长度 那就证明 dp[j]长度找过一次了，现在的组合数+count[j] 即可

LeetCode 一个大佬带图分析的 我觉得真的写的很好：

image-20201009220524667

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int findNumberOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return 1;
        int n = nums.length;
        //dp[i]表示以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[n];
        //count[i] 表示以 nums[i]结尾的最长递增子序列个数 最后加起来用的
        int[] count = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int len = 0, ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++) {
                //因为i先走，如果j < i，那么可以把nums[j]添加到以nums[i]结尾的序列中
                if(nums[j] < nums[i]) {
                    //序列假如比dp[i]的要长
                    if(dp[j]  >= dp[i]) {
                        //那么就有coont[j]个长度为dp[j]的序列
                        count[i] = count[j];
                        //序列长度更新
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                        //假如序列长度相等
                    } else if( dp[j] + 1 == dp[i]) {
                        //就有count[j]个额外序列 +起来
                        count[i] += count[j];
                    }
                }
            }
            //不停更新最长的长度
            len = Math.max(len, dp[i]);
        }

        for(int i = 0; i < n; i++) {
            //假如以nums[i]结尾的序列长度为最长的 答案+上相应的种类数
            if(dp[i] == len) ans += count[i];
        }
        return ans;
    }
}

1143.最长公共子序列（LCS 问题）

image-20201010214127838

这题是找出最长公共子序列，意思是说不一定要在串 1 中找到完整的串 2；而是要让串 2 尽量长的出现在串 1 之中；

那么也就是说，需要分别记录两个字符串不同长度的时候所得到的最长公共子序列，为了方便用一个二维数组记录就好:行代表第一个串长度，列代表第二个串长度；

可以这么去想：两个串从 0 开始逐渐增大，其中父串是一个一个单位增长，而子串在每次嵌套的循环中从 0 一直增长到它自己的长度。然后在嵌套循环中比较，进行 dp，最后在右下角的 dp 值就是答案了，因为父子串都遍历完了。

  • 确定状态：dp[i] [j]，i 表示 text1 的前 i 个字符，j 表示 text2 的前 j 个字符，而 dp[i] [j]表示 S1 前 i 个字符与 S2 前 j 个字符所可以得到的最长公共子序列的长度。

  • 转移方程：

    如果字符相等（S1[i] == S2[j]）的话，就可以把这个字符算进最长公共子序列（LCS）中

    1
    dp[i][j] = dp[i - 1][j - 1] + 1;

    如果字符不相等（S1[i] != S2[j]）的话，只有 2 种可能性，要么是 S[i]的字符不在 lcs 种，要么是 S2[j]的字符不在 lcs 中。

    问题来了 有没有可能 S1[i]和 S2[j]这两个字符都不在 LCS 中呢？当然有这种可能性，但是那样的话就是：

    1
    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);

    但你想想，第三种的情况的长度一定是最小的，他永远不可能被取到。多此一举了。

    1
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

  • 边界与初始条件：dp[i] [j]初始化为 0（java 中可以省略这一步，我们创建数组时默认填充为 0），因为一开始都没遍历。边界条件可以通过行列各增加一列去解决

  • 计算顺序：由于我们的二维数组右下角，也就是两个字符串都遍历完了就是结果，因此是正序遍历。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if(text1.equals(text2)) return text1.length();
        if(text1 == null || text2 == null) return 0;
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        //初始化dp[][]数组
        for(int i = 0; i < m + 1; i++) {
            for(int j = 0; j < n + 1; j++) {
                dp[i][j] = 0;
            }
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                //如果字符相同 纳入LCS
                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //选择选一个能让LCS长度尽量大的
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        //右下角就是答案了
        return dp[m][n];
    }
}

72.编辑距离

image-20201015203222620

这题唯一有意思的点在于 dp 的状态转移由原来常见的 2 个情况变成了 3 个情况，但是大体其实是换汤不换药，按照老路求解就好，不算难

简单说下思路：用一个二维数组 dp[i] [j]表示word1[0..i]到 word2[0…j]转换需要的最小次数，由于 i <= word1 长度， j <= word2 长度

因此最后是返回dp[word1 长度] [word2 长度]；

假如 word1[i ] == word2[j] 表示在该处不需要变化 dp[i] [j] =dp[i - 1] [j - 1];

word1[i] != word2[j]，那么就有三种情况:

  1. 增添法：基于 word1[0….i]与 word2[0…j-1]的编辑距离，让 word1[i + 1] =word2[j]
  2. 删除法：基于 word1[0…i - 1]与 word2[0….j]的编辑距离，让 word[i] = word2[j +1]
  3. 替换法：基于 word1[0….i - i]与 word2[0….j - 1]的编辑距离，让 word1[i] = word2[j]

然后从这些方法得到的 dp 数组中取最小的那个

  • 确定状态：dp[i] [j]表示word1[0..i]到 word2[0…j]转换需要的最小次数

  • 状态转移方程：

    word1[i] == word2[j]

    1
    dp[i][j] = dp[i - 1][j - 1];

    else

    1
    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;

  • 初始值与边界条件：考虑 word1 为空与 word2 为空两种极端情况将第一列第一行分别初始化好：

    1
    2
    3
    4
    5
    6
    7
    8
    //假如word1为空，想转成word2只能通过添加 i+1 个字符
            for(int i = 0; i <= n; i++) {
                dp[0][i] = i;
            }
    //假如word2为空，想转成word2只能通过删除 i+1 个字符
            for(int i = 0; i <= m; i++) {
                dp[i][0] = i;
            }

  • 计算顺序：最终返回 dp[m] [n]，正序遍历即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        if(m == 0) return n;
        if(n == 0) return m;
        //dp[i][j]表示word1[0...i]到word2[0...j]转化需要的次数，因此我们最后返回值是dp[m][n]
        int[][] dp = new int[m + 1][n + 1];
        //假如word1为空，想转成word2只能通过添加 i+1 个字符
        for(int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        //假如word2为空，想转成word2只能通过删除 i+1 个字符
        for(int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        for(int i = 1;i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

42.接雨水

接雨水

假如我们不用任何的算法去解决这道题，那么雨水值可以怎么算呢？

我们可以想象有第三种颜色：红色。

用这个颜色去填补这个由蓝色和黑色组成的数组，怎么填补呢？它不管原来是什么颜色，只要是格子就直接涂成红色。

这样就有了新的数组，我们通过这个数组，减去图中数组中黑色部分（即height数组），留下来的就是蓝色部分，即雨水量。

那么我们现在的问题从怎么计算这个雨水量变成了如何去构建这个红色数组了。

接雨水

通过观察：我们可以得知红色数组是以最大值为分界线，左边依次递增，右边依次递减（如果整个数组单调递增或单调递减，我们视为特殊情况）

而 Red 数组是由两部分组成的：

  1. 左侧部分为：Red[i] = Math.max(原数组[i], Red[i - 1]);
  2. 右侧部分为：Red[i] = Math.max(原数组[i], Red[i + 1];)

举个例子：当 i = 5 的时候，Red[5] = 2，这个 2 是通过 Red[4] = 2 与 现在遍历到的 heigh[5] = 0,进行比较，从而得来的

而当 i = 9 的时候，Red[9] = 2,这个 1 是通过 Red[10] = 2，与 现在遍历到的 height[9] = 1 进行比较，从而得到的

构建完了 Red 数组后，接下来要做的就是简简单单的减法和加法操作了；

  • 确定状态：dp[i]表示 Red 数组中下标为 i 的高度
  • 状态转移方程：
    • 左侧部分：dp[i] = Math.max(height[i], dp[i - 1]);
    • 右侧部分：dp[i] = Math.max(height[i], dp[i + 1]);
  • 初始值与边界条件：
    • 最大值部分：dp[MaxIndex] = Max;
    • 左端点：dp[0] = height[0];
    • 右端点：dp[height.length - 1] = height[height.length - 1];
  • 计算顺序：计算左侧部分，正序遍历；计算右侧部分，逆序遍历；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int trap(int[] height) {
        if(height.length <= 2) return 0;
        int[] dp = new int[height.length + 1];
        int Max = 0;
        int MaxIndex = 0;
        int sum = 0;
        //算最大值和最大值下标 用于区分DP界限
        for(int i = 0; i < height.length; i++) {
            if(height[i] > Max) {
                Max = height[i];
                MaxIndex = i;
            }
        }
        dp[MaxIndex] = Max;
        dp[0] = height[0];
        dp[height.length - 1] = height[height.length - 1];
        //构建左半边DP数组
        for(int i = 1; i < MaxIndex; i++) {
            dp[i] = Math.max(height[i], dp[i - 1]);
        }
        //构建右半边DP数组
        for(int i = height.length - 2; i > MaxIndex; i--) {
            dp[i] = Math.max(height[i], dp[i + 1]);
        }
        //算差值
        for(int i = 0; i < height.length; i++) {
            sum += dp[i] - height[i];
        }
        return sum;
    }
}

32.最长有效括号

最长有效括号

这种括号问题用 DP 思想去解决十分方便。

  • 确定状态：dp[i]表示以下标$i$字符结尾的最长有效括号长度。
  • 状态转移方程：
    • 如果当前字符是(,dp[i] = 0；
    • 如果当前字符是)
      • 如果之前的字符是(，则判断隔了 2 个距离的左侧是不是左侧边界，如果不是则加上之前的长度，即：dp[i] = dp[i -2] + 2，如果该左侧是最左侧边界，则dp[i] = 2;
      • 如果之前字符是)，则需要找出隔了dp[i - 1] - 1距离的左侧字符，判断它是不是(，如果是则可以合并为更大的一个有效括号。同时，如果它不是最左侧的边界，还可以加上这个左字符的左侧的dp[i - dp[i - 1] - 1]，用于合成更大的有效括号。如果已经是最左侧的了，那就放弃合成。
  • 初始值与边界条件：
    • dp 数组一开始全为 0
    • 在计算(i - dp[i - 1] - 1) - 1的时候需要判断其是否大于等于 0，不然数组会越界
  • 计算顺序：根据 dp 数组的含义，需要正序遍历。（针对我的写法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        int[] dp = new int[len];
        int max = 0;
        for(int i = 0; i < len; i++) {

            char ch = s.charAt(i);
            if(i > 0 && ch == ')') {
                if(s.charAt(i - 1) =='(') {
                    dp[i] = i - 2 >=0 ? dp[i - 2] + 2 : 2;
                } else {
                    //找到左侧匹配
                    int left = i - dp[i - 1] - 1;
                    if(left >= 0) {
                        if(s.charAt(left) == '(') {
                            dp[i] = left - 1 >= 0 ?
                                dp[i - 1] + dp[left - 1] + 2 : dp[i - 1] + 2;
                        }
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

贪心（Greedy Algorithm）

贪心思想

  • 基本概念

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

与 DP 不同，DP 考虑的是全局的最优解，贪心只考虑局部的。

  • 什么时候该用贪心？

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是【局部最优解】能决定【全局最优解】。

简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心 - LeetCode 相关

55.跳跃游戏

跳跃游戏

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean canJump(int[] nums) {
        int maxIndex = 0;

        for(int i = 0; i < nums.length - 1; i++) {

            if(i > maxIndex) return false;

            int curIndex = i + nums[i];
            maxIndex = Math.max(maxIndex, curIndex);
        }

        return maxIndex >= nums.length - 1 ? true : false;

    }
}

DFS

DFS 思想

DFS - LeetCode 相关

15.三数之和

三数之和

这种数组中完成某种目标的题，都可以靠 DFS 去做，可以归纳成一定的模板：

  1. 递归终止条件（没完成目标/完成了目标）
  2. 路径选择
  3. 选择的撤销

具体可以参考：https://labuladong.gitbook.io/algo/mu-lu-ye-3/mu-lu-ye/hui-su-suan-fa-xiang-jie-xiu-ding-ban

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<Integer> tmp = new ArrayList<>();

    public List<List<Integer>> threeSum(int[] nums) {

        boolean[] flag = new boolean[nums.length];
        Arrays.sort(nums);
        DFS(0, tmp, nums, 0, flag);
        Set set = new HashSet<>(res);
        res = new ArrayList<>(set);
        return res;

    }

    public void DFS(int start, List<Integer> tmp, int[] nums, int curSum,boolean[] flag) {
        if(curSum > 0) return;
        //递归终止线
        if(tmp.size() == 3) {
            if(curSum == 0) {
                res.add(new ArrayList<>(tmp));
            }
            return;
        }

        for(int i = start; i < nums.length; i++) {
            if(flag[i] == true) {
                continue;
            }

            tmp.add(nums[i]);
            flag[i] = true;
            DFS(i, tmp, nums, curSum + nums[i], flag);
            tmp.remove(tmp.size() - 1);
            flag[i] = false;
        }

    }
}

但在这道题上，DFS 并不是最优解，会超时：

DFS-三数之和-315/318

可以使用双指针解法去代替 DFS.

39.组合总和

组合总和

  • 分析

经典三步曲：

  1. 终止条件：遍历下标越界，或者当前总和大于目标值，终止；如果当前总和等于目标值，加入进结果列表，终止。
  2. 路径选择：当前总和 + 当前遍历下标的元素，当前元素加入结果子数组，由于可以重复选择数组内元素，将当前下标 i 当做 index 传入下一次递归中
  3. 结果撤销：结果子数组去尾，当前总和减去当前遍历下标元素值
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        DFS(new ArrayList<>(), candidates, target, 0, 0);
        return res;

    }

    public void DFS(ArrayList<Integer> subList, int[] candidates, int target, int index, int cur) {
        if(index >= candidates.length || cur > target) return;
        if(cur == target) {
            res.add(new ArrayList<>(subList));
            return;
        }
        for(int i = index; i < candidates.length; i++) {
            cur += candidates[i];
            subList.add(candidates[i]);
            DFS(subList, candidates, target, i, cur);
            subList.remove(subList.size() - 1);
            cur -= candidates[i];
        }

    }
}

17.电话号码的字母组合

思路参考：https://blog.csdn.net/weixin_43314519/article/details/107797559

image-20201114203057671

对于这道题，我们首先需要把敲的数字与字母对应起来 → 用到了 HashMap （当然了，用数组也是可以，用下下标表示嘛）

那么下一个问题，怎么进行组合配对呢？

想一想 假如是数字 2[“abc”]，答案怎么求呢？==注意，下面的所有代码都是伪代码==

1
2
3
4
5
6
7
result = List()
for(i=0;i<len("abc");i++) {
    //这里的i并不是数字，而是i代表的那个字符
    tmp = i
    result.add(tmp)
}
return result

如果是数字 23[“abc”,”def”]，答案又怎么求呢？

1
2
3
4
5
6
7
8
9
result = List()
for(i=0;i<len("abc");i++) {
    for(j=0;j<len("def");j++) {
    //tmp 是 i字符 + j字符的组合
        tmp = i+j
        result.add(tmp)
     }
}
return result

由此 不难发现 我们键盘输入的字符串（数字长度）决定了循环嵌套次数

后面就不写了，简单来说就是下面这个图的解决方式:

在这里插入图片描述

我们上文并没有提到递归，为什么这个图有调用递归的字样呢?

想一想，我们上面提到了 字符串的长度决定了循环嵌套的层数，但我们的层数是变化的，那我们不就确定不了了嘛？

因此，我们使用递归，我们只需要设立一个基准线，到达基准线了，就说明递归完了，就这么简单。

  • 递归终止的条件：

    上面我们说到，如果数字字符串（23，235，2378）遍历到了最后一个了，那就说明该行程的组合都形成了，在这一层只需要把传过来的 letter 放在结果 list 里就好了

    1
    2
    3
    4
    5
    6
    //index记录了遍历到的字符串位置（数字字符串）
    //长度相同 说明遍历完了 该返回了
    if(index == str.length()) {
           res.add(letter);
           return;
     }

  • 每一层递归应该进行什么处理：我们应该进行定位，把当前遍历到了哪个数字 转成相应的字符串，然后把该字符串当成我们需要研究的参数再传进下一层的递归里面

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //获取index位置的字符，假设输入的字符是"234"
            //第一次递归时index为0所以c=2，第二次index为1所以c=3，第三次c=4
            char c = str.charAt(index);
            //我们上面的c是字符，需要 - '0'转成int型 这样才能当hashmap的key用嘛
            int pos = c - '0';
            //通过pos定位，取出map中对应的字符串
            String pos_letter = map.get(pos);
            //把上面一步得到的字符串拿来遍历
            for(int i = 0; i < pos_letter.length(); i++) {
                //要注意 现在的letter是之前的letter加上当前遍历的pos串上各字符
                //同时 index
                DFS(str, letter + pos_letter.charAt(i), index + 1 );
            }

  • 每一层递归返回值：由于是把结果传进一个 list 里，因此硬要说返回值的话 应该是结果 letter 吧。但是这里并没有明显的返回值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    //结果数组
    List<String> res = new ArrayList<>();
    //map 数字和字母行程映射
    Map<Integer, String> map = new HashMap<Integer, String>();
    public List<String> letterCombinations(String digits) {
        //存值
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");

        //特判
        if(digits == null || digits.length() == 0) return new ArrayList<>();
        DFS(digits, "", 0);
        return res;

    }
    private void DFS(String str, String letter, int index) {
        //index记录了遍历到的字符串位置（数字字符串）
        //长度相同 说明遍历完了 该返回了
        if(index == str.length()) {
            res.add(letter);
            return;
        }
        //获取index位置的字符，假设输入的字符是"234"
        //第一次递归时index为0所以c=2，第二次index为1所以c=3，第三次c=4
        char c = str.charAt(index);
        //我们上面的c是字符，需要 - '0'转成int型 这样才能当hashmap的key用嘛
        int pos = c - '0';
        //通过pos定位，取出map中对应的字符串
        String pos_letter = map.get(pos);
        //把上面一步得到的字符串拿来遍历
        for(int i = 0; i < pos_letter.length(); i++) {
            //要注意 现在的letter是之前的letter加上当前遍历的pos串上各字符
            //同时 index
            DFS(str, letter + pos_letter.charAt(i), index + 1 );
        }

    }
}

22.括号生成

image-20210830180009865

括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs("", n, n);
        return res;
    }

    public void dfs(String curStr, int left, int right) {

        if(left == 0 && right == 0) {
            res.add(curStr);
            return;
        }

        if(left > right) return;

        if(left > 0) {
            dfs(curStr + "(", left - 1, right);
        }

        if(left < right) {
            dfs(curStr + ")", left, right - 1);
        }
    }
}

46.全排列 Ⅰ、全排列 Ⅱ

image-20201114215549798

这题其实与上一题有异曲同工之妙，都是排列组合问题，因此我们的终止条件其实也差不多 当遍历的 index == nums 的长度就代表着有一种组合了，把这个组合添加进结果 list 就好了

这道题网上其实也有很多解析了，都用到了下面这个图，那我也贴上来吧：

image.png

是这么说明的：

1、每一个结点表示了“全排列”问题求解的不同阶段，这些阶段通过变量的“不同的值”体现；
2、这些变量的不同的值，也称之为“状态”；
3、使用深度优先遍历有“回头”的过程，在“回头”以后，状态变量需要设置成为和先前一样；
4、因此在回到上一层结点的过程中，需要撤销上一次选择，这个操作也称之为“状态重置”；
5、深度优先遍历，可以直接借助系统栈空间，为我们保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈。
6、深度优先遍历通过“回溯”操作，实现了全局使用一份状态变量的效果。

其实这段话这么多字，关键其实就 2 点：

  1. DFS 有回溯这一说法，因此前面设置的 用于运算的状态变量需要重置掉
  2. 通过回溯操作，整个运算流程其实就用了一个状态变量

ok，回到这道题；

  • 递归终止的条件:

    就像我们上面说的，index == nums.length 的时候 说明子答案产生了 ，把答案存进来就好

    1
    2
    3
    4
    if(index == nums.length) {
        res.add(new ArrayList<>(subnums));
        return;
    }

    但这存在一个坑，res.add(new ArrayList<>(subnums));？为什么不是res.add(subnums);

    通过这里我也学到了新知识：

    subnums 变量指向的对象在递归过程中始终只有一份，而 DFS 每完成一次，都需要撤销之前的所有选择，因此这个变量会重新变为空

    Java 中都是值传递，对象类型变量传参过程中，复制的是变量地址

    地址添加到了 res 里面，而里面的列表对象又是空的，肯定是不对的。

    因此需要进行一次拷贝/重新创建对象，把 sublist 传进去：res.add(new ArrayList<>(subnums));才 OK

  • 每一层递归应该进行什么处理:

    首先判断遍历的数是否用过了 有就跳过，没有就判成 true

    然后遍历到的值传进 subnums 里 进入下一次递归中，同时 index 需要+1

    每当一次 DFS 结束后，别忘了手动撤销状态（包括 visited 数组重置，还有把 subnums 数组重置）；

    这里我当时自作聪明：在每一次结束后自己还把index--了，结果答案出错了

    原因在于：index 会自己消减的- -

    1
    2
    3
    4
    5
    6
    7
    8
    for(int i =0; i < nums.length; i++) {
        if(visited[i] == true) continue;
        visited[i] = true;
        subnums.add(nums[i]);
        DFS(nums, subnums, index + 1, visited);
        visited[i] = false;
        subnums.remove(subnums.size() - 1);
    }

  • 每一层的返回值:

    同样的，好像确实没有什么返回值

画了个非常非常潦草的运算流程，我自己都看不下去：

image-20201114223620257

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    //答案list
    List<List<Integer>> res = new ArrayList<>();
    //存放可能行程的每种组合
    public List<List<Integer>> permute(int[] nums) {
        //判断nums中元素是否用过了的数组
        boolean[] visited = new boolean[nums.length];
        ArrayList<Integer> subnums = new ArrayList<>();
        DFS(nums, subnums, 0 , visited);
        return res;

    }
    private void DFS(int[] nums, ArrayList<Integer> subnums, int index, boolean[] visited) {
        if(index == nums.length) {
            res.add(new ArrayList<>(subnums));
            return;
        }
        for(int i =0; i < nums.length; i++) {
            if(visited[i] == true) continue;
            visited[i] = true;
            subnums.add(nums[i]);
            DFS(nums, subnums, index + 1, visited);
            visited[i] = false;
            subnums.remove(subnums.size() - 1);
        }

    }
}

image-20201119170323122

这个全排列 Ⅱ与全排列 Ⅰ其实并没有多大差别，只是多了个排序以及剪枝叶的步骤；

排序有什么用呢？假如我们不排序，只剪枝：

那么剪枝中的nums[i] == nums[i - 1] && visited[i - 1] == false这一步还有啥意义呢？我挨着的不相同，但是在几个位置外还有个重复的，那不就把它纳入答案中了吗？

因此如果想用nums[i] == nums[i - 1] && visited[i - 1] == false作为判断条件，就必须排序，这样的话，如果挨着相同，就可以轻松派出这种情况了

image-20201119171211465

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        //判断nums中元素是否用过了的数组
        boolean[] visited = new boolean[nums.length];
        ArrayList<Integer> subnums = new ArrayList<>();
        //这里比全排列多了一步排序
        Arrays.sort(nums);
        DFS(nums, subnums, 0 , visited);
        return res;

    }
    private void DFS(int[] nums, ArrayList<Integer> subnums, int index, boolean[] visited) {
        if(index == nums.length) {
            res.add(new ArrayList<>(subnums));
            return;
        }
        for(int i =0; i < nums.length; i++) {
            //与全排列Ⅰ一样，如果数用了就跳过
            if(visited[i] == true) continue;
            //多了一步:就算前面的数是没有用过的，但是与前面的数相同了，我也不能够纳入答案里面，必须跳过
            else if(i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == false) continue;
            visited[i] = true;
            subnums.add(nums[i]);
            DFS(nums, subnums, index + 1, visited);
            visited[i] = false;
            subnums.remove(subnums.size() - 1);
        }

    }
}

78.子集

子集

  • 分析

DFS 三步曲：

  1. 终止条件：当遍历下标大于原数组长度时退出
  2. 路径选择：将当前下标遍历到的元素加入子数组，将该子数组加入答案列表，同时下标向后移动，进入下一层递归
  3. 选择的撤销：将子数组的末位元素删除
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ans.add(new ArrayList<>());
        DFS(nums, new ArrayList<Integer>(), 0);
        return ans;
    }

    public void DFS(int[] nums, ArrayList<Integer> subList, int index) {
        if(index >= nums.length) return;

        for(int i = index; i < nums.length; i++) {
            subList.add(nums[i]);
            ans.add(new ArrayList<Integer>(subList));
            DFS(nums, subList, i + 1);
            subList.remove(subList.size() - 1);
        }
    }
}

200.岛屿数量

岛屿数量

  • 思路

从一个点出发，向四周“蔓延”，如果蔓延到的点的值为1，之前的出发点也为 1，则会被纳入为岛屿，如果之前出发点不为 1，则可以作为新的岛屿的蔓延起始点。

之前写过类似的二维数组遍历问题，为了减少重复的遍历，我们往往需要一个visitd数组用于判断该点有没有走过。

根据 DFS 三步：

  1. 递归终止条件：走出二维数组边界了，或是已经访问过了，或是该点值为0
  2. 路径选择：向四周走
  3. 路径撤销：这道题不需要撤销
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        int ans = 0;
        boolean[][] visited = new boolean[row][column];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < column; j++) {
                if(visited[i][j] == false && grid[i][j] == '1') {
                    ans++;
                    DFS(visited, grid, i, j);
                }
            }
        }
        return ans;
    }

    public void DFS(boolean[][] visited, char[][] grid, int i, int j) {
        if(i >= grid.length || j >= grid[0].length || i < 0 || j < 0 || visited[i][j] == true || grid[i][j] == '0') return;
        visited[i][j] = true;

        DFS(visited, grid, i, j + 1);
        DFS(visited, grid, i + 1, j);
        DFS(visited, grid, i, j - 1);
        DFS(visited, grid, i - 1, j);
    }
}

剑指 Offer 07.重建二叉树

重建二叉树

  • 分析

前序遍历：根 → 左 → 右，中序遍历：左 → 根 → 右

可以得到以下 2 点：

  1. 前序遍历列表：第一个元素永远是 【根节点 (root)】
  2. 中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】
  • 思路
  1. 通过【前序遍历列表】确定【根节点 (root)】
  2. 在【中序遍历列表】中找到 root 所在的索引位置index
  3. 通过 index，将【前序遍历列表】和【中序遍历列表】划分成了左右分支（四个小数组）
  4. 将上述得到的左右分支作为参数，传入下一次递归中
  • 代码

Arrays.copyOfRange(arr, from ,to)

  • arr:要复制的数组
  • from:起始点下标（取得到）
  • to:终止点下标（取不到）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        //记住递归三部曲:
        //1 终止条件
        //2 路径选择
        //3 撤销（有时候不需要）

        TreeNode root = null;
        root = DFS(root, preorder, inorder, 0);
        return root;



    }

    public TreeNode DFS(TreeNode root, int[] preorder, int[] inorder, int index) {
        if(preorder == null || preorder.length == 0) return null;

        root = new TreeNode(preorder[0]);

        for(int i = 0; i < inorder.length; i++) {
            if(inorder[i] == root.val) {
                index = i;
                break;
            }
        }

        root.left = DFS(root, Arrays.copyOfRange(preorder,1, index + 1), Arrays.copyOfRange(inorder, 0, index), index);
        root.right = DFS(root, Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length), index);
        return root;


    }
}

剑指 Offer 34.二叉树中和为某一值的路径

二叉树中和为某值的路径

  • 分析

DFS 三步曲：

  1. 【终止条件】：当前 root 为空时，返回。
  2. 【路径选择】：首先将当前根值加到 cur 值和子列表中。通过判断是否到叶子结点以及与目标值的相同与否进行答案列表的添加。
  3. 【选择的撤销】：分为两个撤销
    1. 如果cur == target，当将当前路径添加入结果列表后，需要将当前结点值删除
    2. 当遍历完一个结点的左右结点后，需要将该节点进行删除
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        DFS(target, 0, root, new ArrayList<Integer>());
        return res;
    }

    public void DFS(int target, int cur, TreeNode root, ArrayList<Integer> subList) {

        if(root == null) return;

        cur += root.val;
        subList.add(root.val);

        if(cur == target && root.left == null && root.right == null) {
            res.add(new ArrayList<Integer>(subList));
            subList.remove(subList.size() - 1);
            return;
        }

        DFS(target, cur, root.left, subList);
        DFS(target, cur, root.right, subList);
        //走到这 说明该结点的左右子树都遍历了，需要剔除掉。
        subList.remove(subList.size() - 1);

    }
}

疑惑点：这里可能有人会奇怪，你前面的 cur 值 + 了 root 的值，为什么在路径撤销时不需要把 root 值从 cur 值中删除掉呢？

原因在于，我们是在进行递归的每一层中进行的 cur 值增加，当该层递归走完了，它从递归栈的栈顶弹出去了，那么下一层递归中的 cur 值还是原来的 cur 值，不需要进行重置动作。

排序

八大排序分别为：直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序

image-20210514225141391

排序中会经常出现一个词稳定：这个词表达的意思是，如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是 稳定 的。反之，则是 非稳定 的。

用一张图来概述：

十大排序算法

冒泡排序

基本思想

  • 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
  • 直观表达，每一趟遍历，将一个最大的数移到序列末尾。即外部循环决定遍历的趟数，内部循环每一趟确定最大数，次最大数，次次最大数…

算法描述

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

img

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void sort(int[] a) {
    //外层循环控制比较的次数
    for (int i = 0; i < a.length - 1; i++) {
      //内层循环控制到达位置
        for (int j = 0; j < a.length - i - 1; j++) {
            //前面的元素比后面大就交换
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

算法分析

  • 复杂度分析
平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n²) O(n) O(n²) O(1) 不稳定

什么时候最快：当输入的数据已经是正序时 O(n)

什么时候最慢：当输入的数据是反序时 O(n²)

平均时间复杂度：O(n²)

空间复杂度：只有缓存的 temp 变量需要内存空间，O(1)

稳定性：稳定

选择排序

基本思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述

  1. 从未排序序列中，找到关键字最小的元素
  2. 如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
  3. 重复 1、2 步，直到排序结束。

img

直观数据例子：

第一趟的排序过程

原始序列：49、38、65、97、76、13、27、49

1）在进行选择排序过程中分成有序和无序两个部分，开始都是无序序列

结果：49、38、65、97、76、13、27、49

2）从无序序列中取出最小的元素 13，将 13 同无序序列第一个元素交换，此时产生仅含一个元素的有序序列，无序序列减一

结果：{13、} {38、65、97、76、49、27、49}

3）从无序序列中取出最小的元素 27，将 27 同无序序列第一个元素交换，此时产生仅两个元素的有序序列，无序序列减一

结果：{13、27、} {65、97、76、49、38、49}

4）从无序序列中取出最小的元素 38，将 38 同无序序列第一个元素交换，此时产生含三个元素的有序序列，无序序列减一

结果：{13、27、38、} {97、76、49、65、49}

5）从无序序列中取出最小的元素 49，将 49 同无序序列第一个元素交换，此时产生含四个个元素的有序序列，无序序列减一

结果：{13、27、38、49、} {76、97、65、49}

6）从无序序列中取出最小的元素 49，将 49 同无序序列第一个元素交换，此时产生含五个元素的有序序列，无序序列减一

结果：{13、27、38、49、49、} {97、65、76}

7）从无序序列中取出最小的元素 65，将 65 同无序序列第一个元素交换，此时产生含六个元素的有序序列，无序序列减一

结果：{13、27、38、49、49、65} {97、76}

8）从无序序列中取出最小的元素 76，将 76 同无序序列第一个元素交换，此时产生含七个元素的有序序列，无序序列减一

结果：{13、27、38、49、49、65、76、} {97}

9）最后一个元素肯定是最大元素，无序排序直接生产一个有序的序列

结果：{13、27、38、49、49、65、76、97}

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void sort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int min = i;
        //选出之后待排序中值最小的位置
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        //最小值不等于当前值时进行交换
        if (min != i) {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

算法分析

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n²) O(n²) O(n²) O(1) 不稳定

什么时候最快：当输入的数据已经是正序时，但每次都得检查一下，因此是： O(n²)

什么时候最慢：当输入的数据是反序时 O(n²)

平均时间复杂度：O(n²)

空间复杂度：只有缓存的 temp 变量需要内存空间，O(1)

稳定性：不稳定

插入排序

算法思想

基本思想：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

img

算法描述

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤 2~5

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 通过交换进行插入排序，借鉴冒泡排序
 *
 * @param a
 */
public static void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
}

/**
 * 通过将较大的元素都向右移动而不总是交换两个元素
 *
 * @param a
 */
public static void sort2(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int num = a[i];
        int j;
        for (j = i; j > 0 && num < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = num;
    }
}

算法分析

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n²) O(n²) O(n²) O(1) 稳定

数学

有一些算法使用的是数学的思想，我们把那些题放在这里进行总结

摩尔投票法

当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。

  • 算法步骤
  1. 候选人(cand_num)初始化为nums[0]，票数count初始化为 1。
  2. 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
  3. 当票数count为 0 时，更换候选人，并将票数count重置为 1。
  4. 遍历完数组后，cand_num即为最终答案。
  • 算法原理

为何这行得通呢？

投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。

且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。

因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。

这就相当于每个“多数元素”和其他元素 两两相互抵消，抵消到最后肯定还剩余至少 1 个“多数元素”。

无论数组是 1 2 1 2 1，亦或是 1 2 2 1 1，总能得到正确的候选人。

可以想象成一堆会影分身的忍者进行打架，忍术最厉害的忍者能召唤出最多的分身，然后一起打群架，不同的分身和分身之间进行一换一，最后剩下的那个就是分身最多的那个忍者，也是忍术最厉害的那个。

169.多数元素

169.多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int majorityElement(int[] nums) {
        int cand_num = nums[0], count = 1;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] == cand_num) count++;
            else count--;

            if(count == 0) {
                 cand_num = nums[i];
                 count = 1;
            }
        }
        return cand_num;

    }
}

技术参考

博客