本文主要是介绍2024.8.28 Python，复习，全排列的dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如果问我如何克服编程学习的挫折感，我的评价是，感觉挫折的时候不如回头看看，之前学过的东西是否完全掌握了，那么这节复习课就来了。
1.无重复
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串
这个题在2024.8.13的文章中出现，但是我发现这个题并没有写足够详细的解答，我将通过复习这个题重写这道题的思路
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:occ=set()rk,ans=0,0for i in range(len(s)):if i!=0: #目的是为了不让第一个排除掉，不让i-1超出范围，保证s[0]进去了以后能进while循环occ.discard(s[i-1]) #在i进入的时候去掉i-1while s[i] not in occ:rk+=1occ.add(s[i])ans=max(rk-i,ans)return ans
这个代码的基本逻辑是检查右指针的数在set里有没有，如果没有就加进去，在for循环中循环while，然后不断右移指针，同时是for循环中更新ans，不是while中更新。chat同时给出了另外一个答案，也是可以的。
def lengthOfLongestSubstring(s:str)->int:char_set=set()left=0ans=0for right in range(len(s)):while s[right] in char_set:char_set.remove(s[left])left+=1char_set.add(s[right])ans=max(ans,right-left+1)return ans
他是移右边的指针，不重复的话就算ans，然后出现重复的，就先删左边的再右移左指针，别忘了加一，直到没有重复的，再算ans
2.电话号码的字母组合
class Solution:def letterCombinations(self,digits:str)->List[str]:if not digits:return []phone={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'} res=[]digits=list(digits)def backtrack(digits,ans):if not digits:res.append(ans) return j=digits.pop(0)for letter in phone[j]:backtrack(digits[:],ans+letter)backtrack(digits,'')return res
这是我写的一个版本，我最开始写的版本一直对不了，chat给我修改以后把digits改成了[:]，把ans+=letter改成了代入函数的ans+letter。我的理解是，因为是函数内的函数，所以这些参数会在参数传递的时候修改，而使用[]这样的方法就能避免在参数传递的时候修改了原来的值，我现在也不是特别能理解为什么有时候参数需要修改，有时候不要，我先放在这里。等我再做几个回溯算法的题可能就学会了。
3.全排列的dfs版本复习
普通用remain的版本已经尝试过了，已经完成了， 主要关注点在于，记得传进下一层函数的时候，尽量不要改变这一层的函数值，如果改变了，记得在这一层的之后复原，而不是在下一层复原，在下面的代码中将很好的体现这个思路
#这是个错误代码
class Solution:def permute(self,nums:List[int])->List[List[int]]:ans,res=[],[]n=len(nums)on_path=[False]*ndef dfs():if len(ans)==len(nums):res.append(ans[:])returnfor i in range(len(nums)):if on_path[i]==False:ans+=[nums[i]]on_path[i]=Truedfs()on_path[i]=Falseans.pop()dfs()return res
上面这个代码是错的，代码报错了，原因是我没有传递ans，很奇怪，在函数里定义函数本来应该是不需要传递这样的ans的，下面的是对的代码
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:ans, path = [], []on_path = [False] * len(nums)def dfs():if len(path) == len(nums):ans.append(path.copy())returnfor i, x in enumerate(nums):if not on_path[i]:path.append(x)on_path[i] = Truedfs()on_path[i] = Falsepath.pop()dfs()return ans
没啥区别对吧，问题就出在+=这里了append和+=功能是一样的，但是处理是不一样的，ans+=是重新建立一个新的列表，如果你使用append，那么只是在加东西，但是你用+=就是删了重来，这就使得在递归调用时，ans 可能无法正确保留状态，因此你需要显式传递它。也就是说此ans已经不是彼ans了，有或者说换了个地址。
解决办法就是，要么在第一个dfs里把ans带进函数，要么就是把+=换成append，很奇怪，但是这种问题如果以后出现的话，也就知道不是代码的问题了，是背后机制的问题。
这篇关于2024.8.28 Python，复习，全排列的dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
