代码随想录算法训练营第二十五天| leetcode491.递增子序列、leetcode46.全排列、leetcode47.全排列 II

1 leetcode491.递增子序列

题目链接：491. 非递减子序列 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

思路：用之前的方法，结果翻车了，好好看视频学新技能吧

1.1 视频后的思路

真的没想到用set来去重，还是基本功不够扎实呀

class Solution:
    def __init__(self):
        self.result = []
        self.num = []
    
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        self.backtracking(nums,0)
        return self.result
    
    def backtracking(self,nums,startindex):
        if len(self.num[:])>1:
            self.result.append(self.num[:])
        if startindex == len(nums):
            return
        unset = set()
        for i in range(startindex,len(nums)):
            if (self.num and nums[i]<self.num[-1]) or nums[i] in unset:
                continue
            unset.add(nums[i])
            self.num.append(nums[i])
            self.backtracking(nums,i+1)
            self.num.pop()

1.2 本题小结

1. 针对去重的问题，其实感觉自己做的不够多，就会忘了如何去删除重读元素，看来还是多练习多去写呀
2. 真的set函数，前面学后面忘

2 leetcode46.全排列

题目链接：46. 全排列 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

思路：新问题，真不错，不过我写不出来，看来还是前面的方法掌握的不够熟练，其实是用used的方法解决的就行了，，，

2.1 视频后的思路

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def permute(self, nums: List[int]) -> List[List[int]]:
        used = [False]*len(nums)
        self.backtracking(nums,used)
        return self.result
    def backtracking(self,nums,used):
        if len(self.path[:]) == len(nums):
            self.result.append(self.path[:])
            return
        for i in range(len(nums)):
            if used[i] ==True :
                continue
            used[i] = True
            self.path.append(nums[i])
            self.backtracking(nums,used)
            self.path.pop()
            used[i] = False

2.2 本题小结

1. 这道题与之前的题目区别就在于需要重复的，嗯，写的时候就发现其实就很简单，看完视频就会了

3 leetcode47.全排列 II

题目链接：47. 全排列 II - 力扣（LeetCode）

文章链接：代码随想录

视频链接：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

思路：上一题写完，结合之前的那道题的思路，Duang这个答案就写出来啦

3.1自己的思路

真就融汇贯通啦，自己结合之前的方法就水灵灵的写出来咯

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        used = [False]*len(nums)
        self.backtracking(nums,used)
        return self.result
    def backtracking(self,nums,used):
        if len(self.path[:])==len(nums):
            self.result.append(self.path[:])
            return
        unset =set()
        for i in range(len(nums)):
            if used[i]==True or nums[i] in unset:
                continue
            unset.add(nums[i])
            used[i] = True
            self.path.append(nums[i])
            self.backtracking(nums,used)
            self.path.pop()
            used[i]=False

3.2 视频后的方法

就是使用了排列的方法，感觉两者差不多

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        used = [False]*len(nums)
        self.backtracking(nums,used)
        return self.result
    def backtracking(self,nums,used):
        if len(self.path[:])==len(nums):
            self.result.append(self.path[:])
            return
        for i in range(len(nums)):
            if (i>0 and nums[i]==nums[i-1] and used[i-1]==False) or used[i]:
                continue
            used[i] = True
            self.path.append(nums[i])
            self.backtracking(nums,used)
            self.path.pop()
            used[i]=False

3.3 本题小结

1. 哈哈哈哈哈哈，真就是融汇贯通的一道题目，嗯，算是弄懂了吧

4 今日小结

1. 知识的融合其实有待加强，首先式针对第一题，就是不知道如何防止重复，感觉已经忘记了如何使用集合，但是看了以后就觉得，确实有点不太融汇的感觉
2. 对于二的题目，其实就是判断的逻辑真的没想到，使用一个列表来计算，但是看了就觉得自己能立刻写出来
3. 对于三就是之前知识融合而已，终于，回溯也结束啦