网站开发树形图,电子商务网站建设 名词解释,安徽优化开发区,高校网站建设前言心路历程#xff1a;
一开始看到有点懵#xff0c;后来发现有点像按照一定规则穷举所有可能情况#xff0c;想到了排列组合问题#xff0c;再结合问题长度不固定#xff0c;无法用已知个for循环表示#xff0c;从而想到了回溯。这个题相当于需要在一定规则下枚举。 按照…
心路历程
一开始看到有点懵后来发现有点像按照一定规则穷举所有可能情况想到了排列组合问题再结合问题长度不固定无法用已知个for循环表示从而想到了回溯。这个题相当于需要在一定规则下枚举。 按照回溯的模板递归循环是整个字符串sfor循环是候选集合。候选集合为第i个元素 “选” 或者 “不选” 按照这个思路其实就已经可以把所有可能组成的情况给遍历到然后再从所有结果里搜集满足条件的即可。
这道题在回溯问题里很有代表性考察了很多点包括怎么对排列问题进行建模选or不选、如何判断满足括号条件栈、如何剪枝。一开始把问题想简单了导致写完之后花了很长时间解决未通过的案例这里面还是有一些细节需要考虑的比如任何回溯都得在递归函数调用结束后“恢复现场”。
注意的点
1、回溯算法在记录path时一定要记得copy 2、回溯函数中任何递归调用后都得恢复路径比如这个问题里遇到字母时虽然形成的树只有一个分支但是返回后也得恢复path才行当时第一次想这个问题以为单分支不用恢复路径导致de了半天bug。还是需要理解回溯是遍历边这个概念。 3、剪枝的判断直接返回就行把剪枝的部分当作不需要记录path的终止条件即可。 4、每个节点候选集合都有空字符串和括号两个选择需要遍历没法贪婪地认为有括号选括号因为需要考虑所有的组合。 5、注意题目中找的是删除最少括号后的所有可能组合也就是最长的合法解并且不能包含重复元素。
感悟
1、算法题主要考察两类能力一是对问题进行建模的能力二是逻辑条件的想全能力。很多时候知道问题大概怎么做但是具体想各种情况时还是会漏掉一些情况或者想错一些情况。 2、回溯问题debug可以从打印路径和候选集合的角度寻找错误。 3、很多算法中循环的建模思路都可以按照’选‘or’不选‘ 或者 ’选哪个‘的思路考虑尤其在回溯、递归、动态规划等问题上可以建模为决策问题。这一点其实和DRL在求解组合优化问题时的两类动作建模思路是一致的。
解法
这道题有两个思路思路一剪枝选择后序有可能形成最长路径解法二剪枝找到所有的判断满足条件的最长的。第二个可能更清晰不过由于刚做完括号的题所以按照第一个思路写的AC解
class Solution:def removeInvalidParentheses(self, s: str) - List[str]:from collections import Counterpath []res []n len(s)kuohaos [(, )]mystack Mystack()maxlen 0def dfs(i): # i代表遍历字符串的第i个元素# nonlocal s, n, res, path, mystack # 这一行可有可无nonlocal maxlen # 这一行必须有# 剪枝把一些不可能更长的去掉;if (n - len(path)) len(.join(path)) maxlen:returnif i n:string .join(path.copy())maxlen max(maxlen, len(string))res.append(string)returnif s[i] not in kuohaos:path.append(s[i])dfs(i1)path.pop() # 这块也得回溯else:candidate []# 看第i个括号能不能选即可if s[i] (: # 后面的数量大于等于栈长1就可以选c Counter(s[i1:] )) # 1防止为空# print(mystack.sk, c[)], mystack.len())if c[)] - 1 mystack.len() 1: candidate.append(()elif s[i] ): # 栈里有左括号if mystack.len() 0:candidate.append())else:assert False, s[i]for each in candidate:# print(each, path, i)path.append(each) # path 怎么会这么长# 维护一下栈if each ! :mystack.append(each)dfs(i1)path.pop()if each ! :mystack.pop(each)dfs(0)# 返回res里最长的lengths [len(eve) for eve in res]res [eve for eve in res if len(eve) max(lengths)]return list(set(res)) # 需要去重class Mystack:def __init__(self):from collections import dequeself.sk deque()def pop(self, ele):if ele (:self.sk.pop()elif ele ):self.sk.append(()else:assert False, eledef append(self, ele):if ele (:self.sk.append(()elif ele ):assert len(self.sk) ! 0self.sk.pop()else:assert False, eledef len(self):return len(self.sk)
