Leetcode 【216、769】

题目描述：【DFS】216. Combination Sum III

解题思路：

这道题一看要求输出所有满足题意的组合，很明显 DFS 回溯法进行求解，属于模板题。不过这倒题需要注意几个剪枝情况：

• 因为是组合数，所以保证后一个数比前一个数大即可；
• 当深度小于 k 时才进行深搜，深度大于 k 没必要深搜。

Python3 实现：

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
          
        def search(r, tar):  # tar为目标值
            for i in range(1, 10):
                if self.b[i] == False and i > self.a[r-1]:
                    self.a[r] = i
                    self.b[i] = True
                    tar -= i  # 目标值减小
                    if r == k and tar == 0:  # 找到一组解
                        self.ans.append([])
                        for j in range(1, k+1):
                            self.ans[-1].append(self.a[j])
                    elif r < k:  # 深度小于k才进行深搜
                        search(r+1, tar)
                    self.b[i] = False  # 恢复b[i]为False
                    tar += i  # 恢复目标值tar                  
                
        self.ans = []  # 保存所有答案
        self.a = [0] * 10  # 保存一组答案
        self.b = [False] * 10  # 标记数字i是否被使用过
        search(1, n)  # 调用深搜算法
        return self.ans

---

题目描述：【Array】769. Max Chunks To Make Sorted

解题思路：

方法1（普通的方法）：

• 因为要保证有序，所以简单想法就是先找 0 的位置，判断 0 左右两边的序列排序后是否满足升序。如果不满足，就找 1、2, ... 的位置，满足的话就划分出一个块，然后标记当前划分的位置。
• 当前划分的位置能保证左侧是一个块，但是右侧还可以继续划分。
• 所以，继续找下一个在划分位置右侧的数字，然后按照第一步相同的思路做，直到所有数字找完为止。

举例：arr = [2,0,3,1,5,4,6]，刚开始找到 0 的位置，发现 [2,0] 和 [3,1,5,4,6] 不满足；找 1 的位置，发现 [2,0,3,1] 和 [5,4,6] 满足，块数加 1；找 2、3，由于都在划分处（1 的位置）的左侧，不用管；找 4 的位置，在划分位置的右侧，[5 4] 和 [6] 满足，块数加 1；找 5，由于都在划分处（4 的位置）的左侧，不用管；找 6，在划分位置的右侧，[6] 和 [] 满足，块数加 1；最后得到结果为 3。

Python3 实现：

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        N = len(arr)
        sort = [i for i in range(N)]
        chunks = sort_len = i = 0
        split = -1  # 划分处
        while i < N:  # 找每个数字
            ind = arr.index(i)  # 每个数字的位置
            if ind < split:  # 在划分处左侧的数字，不用管
                i += 1
                continue
            left, right = arr[split+1:ind+1], arr[ind+1:]  # 划分成左右两个序列
            left.sort()
            right.sort()
            if left + right == sort[sort_len:]:
                chunks += 1
                sort_len += len(left)
                split = ind  # 更新划分处的位置
            i += 1
        return chunks

方法2（巧妙的方法）：

其实有一种巧妙的方法。假设原序列进行了一种划分，不管如何分，第一组排序完都为 0,1, 2, ..., k ，不难发现，原序列切割的那个点的前面必须要出现 0,1,2, ..., k。

因为数组的排序后正确顺序应该是 arr[i] 处的数是 i。所以，从头遍历数组，每次更新最大值 max_，即 max_ = max(max_, arr[i])，max_ 必须在 i 处才能满足对 0～i 数字排序后能够恰好是正确的位置。因为 max_ 是第 0～i 个数字中的最大值，遍历的过程中如果 max_ == i，就保证了前面 i-1 个数字必然都比 max_ 小（因为 max_ 是 0～i 中的最大值），则第 0～i 个数字必然能排列成正确顺序，就能划分成一个块。继续遍历，找到下一个满足 max_ == i 的地方（记为 j），则 i+1～j 又能分为一个块。以此类推，直到遍历到最后一个数为止得到答案。

简单一句话来说，当前最大值与下标 i 相等时，前面就可以划分成一个块。

举例：arr = [2,0,3,1,5,4,6]，刚开始 max_ = 2，说明至少需要遍历到 i == 2 才可能划分成一个块（因为要包括 0 ~2）。遍历到 3 时，max_ 就要改写成 3，说明至少需要遍历到 i == 3 才可能划分成一个块（因为要包括 0~3）。到了 i == 3，发现刚好满足条件，则块数加 1。继续遍历，max_ = 5，并且能到 i == 5，块数加 1。最后，max_ = 6，并且 i == 6，块数加 1，最后得到结果 3。

Python3 实现：

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        cnt = max_ = 0
        for i in range(len(arr)):
            max_ = max(max_, arr[i])  # 每次都更新最大值
            if max_ == i:  # 最大值与下标相等，说明可以划分成一个块
                cnt += 1
        return cnt