39. 组合总和
- 一开始写的时候没注意到可以重复,注意到可以重复之后就去掉了start_index,但是出现了类似[2,2,3][2,3,2]这种重复。看了题解之后,发现加上start_index,但是进for循环的时候start_index还是i,这样就是既可以重复也不会重新取之前的数。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
self.backtracking(candidates, target, [], 0)
return self.res
def backtracking(self, candidates, target, path, start_index):
if target == 0:
# print(path)
self.res.append(path[:])
return
if target 0: return
for i in range(start_index, len(candidates)):
if target-candidates[i] 0:
continue
path.append(candidates[i])
self.backtracking(candidates, target-candidates[i], path, i)
path.pop()
40.组合总和II
- 相比于之前这个题的区别,就是这个在candidates里可以重复,但是最后res里不能有重复的list。想要去重还挺难想的,不过题解里给了一个思路,就是在树的同一层进行操作,即可进行去重操作。递归的时候不在树的同一层,因此不需要有去重操作。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
candidates.sort()
self.backtracking(candidates, target, 0, [])
return self.res
def backtracking(self, candidates, target, start_index, path):
if target == 0:
self.res.append(path[:])
return
for i in range(start_index, len(candidates)):
if target-candidates[i] 0: continue # 剪枝
# 树的同一层,如果有重复的,跳过
if candidates[i] == candidates[i-1] and i > start_index: continue
path.append(candidates[i])
self.backtracking(candidates, target-candidates[i], i+1, path)
path.pop()
131.分割回文串
- 这题好难。。没有思路。。根本想不到分割和回溯又什么关系。所以直接看的题解。可能需要复习复习。
- 题解给的解释:
– 递归用于纵向遍历
– for循环用于横向遍历
– 当切割线迭代至字符串末尾,说明找到一种方法
– 类似组合问题,为了不重复切割同一位置,需要start_index来做标记下一轮递归的起始位置(切割线)
– 关于模拟切割线,其实就是index是上一层已经确定了的分割线,i是这一层试图寻找的新分割线
class Solution:
def partition(self, s: str) -> List[List[str]]:
self.res = []
self.backtracking(s, 0, [])
return self.res
def backtracking(self, s, start_index, path):
if start_index == len(s):
self.res.append(path[:])
服务器托管网 return
for i in range(start_index, len(s)): # 用start_index作为分割点
if self.is_palindrome(s, start_index, i):
path.append(s[start_index:i+1])
self.bac服务器托管网ktracking(s, i+1, path)
path.pop()
def is_palindrome(self, s, start, end):
i = start
j = end
while(i j):
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
# 若反序和正序相同,意味着这是回文串
if s[start_index: i + 1] == s[start_index: i + 1][::-1]:
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
一、前言 继2014年的R-CNN、2015年的Fast R-CNN后,2016年目标检测领域再次迎来Ross Girshick大佬的神作Faster R-CNN,一举解决了目标检测的实时性问题。相较于Fast R-CNN而言,Faster R-CNN主要改进…