代码随想录27期|Python|Day29|回溯算法|491.递增子序列|46.全排列|47.全排列 II

2023-12-27 20:26:01

491.?非递减子序列

本题不是单纯的去重题目,而是需要保持数字在原数组的顺序。

比如:[4,5,6,7]和[4,6,5,7]相比,后者就不能选择[5,6,7]这个排列,因为违反了设置的顺序。所以去重的方法就只有哈希表

需要在每一层设置一个哈希表,也就是进入for循环前,来查询是否之前出现过这个数字。由于数字范围是-100~100所以数组就够了。

1、参数和返回值:参数和一般的回溯模版一致,返回值不需要(因为是找到全遍历)

2、终止条件:path长度大于2即可

3、中间处理逻辑:除了回溯的3行以外,需要加两个并列的判断条件,满足一个说明重复了:

(1)当前nums里i指向的数字小于path的最后一个

(2)used数组储存过该数字

此外在添加每个数字的时候还需要设置used == 1,但是不需要在回溯的时候消除,因为是在树的每一层进行标记,而不是进入了递归的树枝。

class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.backtracking(0, [], res, nums)
        return res
        
    def backtracking(self, start_idx, path, res, nums):
        if len(path) > 1:
            res.append(path[:])
        # 每一层开始初始化used数组
        used = [0] * 201
        for i in range(start_idx, len(nums)):
            if (path and nums[i] < path[-1]) or used[nums[i]+100] == 1:
                continue
            path.append(nums[i])
            used[nums[i]+100] = 1
            self.backtracking(i+1, path, res, nums)
            path.pop()

46.?全排列

本题需要明确“层间”还是“树枝”上去重,对于组合问题,前面的数字不能再取,所以是层间去重,回溯的时候不用修改当前层的used数组,但是在树枝上去重的时候,需要在used数组上同样进行回溯,used就是一个用来标记的“伴随”数组。保证回溯之后,这个数字依然可以取到。

1、参数和返回值:除了模版的参数以外,还需要used作为一个数组参数跟着回溯;返回值不需要,因为是全遍历

2、终止条件:全排列,每一个数字都要用到,所以是path和nums数组长度相等的时候

3、中间处理:和上面used设置在for层遍历之前并且不做回溯修改不同,本题used需要在for内(树枝)上修改,并且在回溯之后要消除操作

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        # used数组作为一个参数进入回溯
        used = [0] * 21
        self.backtracking(nums, [], res, used)
        return res
    
    def backtracking(self, nums, path, res, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[nums[i]+10] == 1:
                continue

            used[nums[i]+10] = 1
            path.append(nums[i])
            self.backtracking(nums, path, res, used)
            path.pop()
            # used需要回溯
            used[nums[i]+10] = 0

47.?全排列 II

本题是去重+排列的杂交题。

难点在于如何在去重的同时不排除第一次遍历这个排列的情况。

1、参数和返回值:和上一题的排列一致,也是全局的used数组加入到模版写法里,返回值为空

2、终止条件:全排列path长度等于nums长度

3、中间处理:两个判断,分别用于去重和进入递归:

(1)去重:当且仅当前一个数字已经被遍历and现在的数字和之前的是一样的时候,需要continue

(2)进入递归:当前数字未被遍历(注意不是上一个逻辑的else,不然很多不满足三个跳过条件之一的情况也会被加入)

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        used = [0] * 9
        self.backtracking(nums, [], res, used)
        return res

    def backtracking(self, nums, path, res, used):
        if len(path) == len(nums):
            res.append(path[:])
            return

        for i in range(len(nums)):
            # 跳过的判断条件:和前面一个重复,并且前一个已经遍历了(防止第一次被剔除)
            if i > 0 and nums[i] == nums[i-1] and used[i-1] == 1:
                continue
            # 进入下一级的条件:在不重复的前提下,当前节点没有被遍历到
            if used[i] == 0:
                used[i] = 1
                path.append(nums[i])
                self.backtracking(nums, path, res, used)
                path.pop()
                used[i] = 0

?第29天完结我的天呐!!!我完全就是一整个我的天呐!

要注意细节和对于模版的裁剪依照的是题目的特殊条件和树的裁剪。

文章来源:https://blog.csdn.net/m0_57527624/article/details/135249138
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。