知识点

LeetCode算法题

1. LeetCode算法题

   1. 学习

      1. 区间问题系列

         1. 区间调度

            解题思路：

            常见问题有【用最少的箭头射爆气球】、【不重复区间个数】等。

            解题思路都是，先按照end排序，让问题具备贪心性质，然后使用贪心算法解决。

         2. 区间合并

            解题思路：

            按照start排序，然后遍历排序后的区间数组进行合并。

         3. 区间交集

            解题思路：

            先按照start排序

            假设有两个区间[a1, a2]和[b1, b2]，分析两个区间如果不相交的条件，它的否定就是区间相交。至此，得到了区间相交的判定。

            然后，根据两个区间[a1, a2]和[b1, b2]相交的4种情况，分析交集的共有特性，从而得到交集区间的规律。

            遍历排序后的区间数组，然后利用区间相交判定和交集区间的规律得到所有交集区间。

      2. nSum问题

         解题思路：

         一般会问【3数之和】、【4数之和】等等，解题方法都是通过【2数之和】为基础得到的。

         【2数之和】，先排序，然后利用双指针法解题。

         【3数之和】，先排序数组，然后遍历数组得到第一个固定的数，然后让target减去固定的数得到target2，然后使用两数之和的方法计算target2，这样3个数都找到了。

      3. 698.【划分为k个相等的子集】

         解题思路：

         之前的固定大小子集问题，我们可以转化为背包问题然后用动态规划解决。但是，对于该问题，因为相等子集个数可能会有很多个，一般只能通过暴力穷举。要暴力穷举，一般使用的是dfs。

         使用dfs，要求明确路径、选择、结束条件。

         划分为k个相等子集，可以想象将n个数字分配到k个「桶」里，最后这k个「桶」里的数字之和要相同。我们可以用int[] bucket = new int[k]定义k个桶，第k个索引元素就是第k个桶中的数字和；对于数组中的数字，选择就是进入哪个桶中；结束条件为遍历完所有的数字，如果每个桶的数字和都为sum(nums) / k则返回true，否则返回false。

   2. 复习

      1. 子集问题

         1. 78.【子集】

            解题思路：

            dfs。

         2. 90.【子集 II】

            解题思路：

            因为数组有重复元素，因此要考虑子集去重问题。

            去重问题：

            去重，必须要先排序，因此我们升序排序数组。然后定义一个辅助boolean数组used，大小和nums一样。通过used数组来做去重。

            因为dfs是决策树的遍历，因此去重有两个层面即同一个树枝的去重和同一个树层的去重。该题目要求不能 包含重复的子集，明显就是同一个树层的去重问题。

            同一个树层去重，逻辑写在for循环里面，当i > 0 && nums[i] == nums[i - 1] && !used[i - 1]说明同一个树层有重复，continue这个回溯分支。