设计素材网站的问卷调查,高端品牌网站建设案例,网站做弹窗广告,高埗仿做网站1、 组合和子集问题
组合问题需要满足一定要求才算作一个答案#xff0c;比如数量要求#xff08;k个数#xff09;#xff0c;累加和要求#xff08;target#xff09;。 子集问题是只要构成一个新的子集就算作一个答案。
进阶#xff1a;去重逻辑。
一般都是要对同…1、 组合和子集问题
组合问题需要满足一定要求才算作一个答案比如数量要求k个数累加和要求target。 子集问题是只要构成一个新的子集就算作一个答案。
进阶去重逻辑。
一般都是要对同层去重。比如[1,1,2,2,2] 放置第一个位置的数时如果已经使用过第一个1了那么他的所有组合和子集一定包含第二个1所以去重逻辑就是同层不能出现相同的数。
对于一个顺序数组通常直接与前一个数比较即可。
for i in range(index1, n):if iindex1 or nums[i]!nums[i-1]:dfs(i,[],target)对于一个乱序数组则需要用哈希表存储同层出现过的数。
hash set()
for i in range(index1, n):if iindex1 or (nums[i] not in hash):hash.add(nums[i])dfs(i, [])实际上上面的两段代码还蕴含了另一个去重即不同层不能用同一个下标的数所以这里索引时是从index1开始。
2、分割问题
我们定义[start:end] **左闭右闭**这段区间为分割出来的子串对他进行条件判断。在python中对应的是s[start: end1]end指向某个字符后面表示切割到这个字符。start则为上一步的end1。可以看下面这幅图比较直观。理解了怎么分割字符串剩下的就套回溯的模板就可以了。 def partition(self, s: str) - List[List[str]]:n len(s)res []def ishuiwen(s):return ss[::-1]def dfs(start,end,stack):ss s[start:end1]if not ishuiwen(ss):returnstack.append(ss)if end n-1:res.append(stack.copy())return for i in range(end1,n):dfs(end1, i, stack.copy())for i in range(n):dfs(0, i, [])return res
