Iris S

思考重点:分治法

  • 二叉树题目几乎全部都要利用分治和递归的思想

简单地解释一下分治法(Divide and Conqueror)

以下解释来自https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html

  • 分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便 …

--

--

前缀型

划分型

使用一维数组dp[i]: 记录在下标为i的元素前砍一刀所得到的方案数/可行性

  • decode ways 在i砍一刀,求组合,累加全部方案总数
  • word break 在i砍一刀,看看能不能划分成单词

匹配型

使用二维数组dp[i][j]记录两个string之间的关系:

例1. dp[i][j] = s[0:i] 能够和 p[0:j]匹配的最长s …

--

--

--

--

  1. Generate permutations
  • DFS + loop with increasing index
def dfs(self, count, nums, s, v):
if count == len(nums):
self.res.append(s[:])
return
for i in range(len(nums)):
if v[i]==1:
continue
v[i]=1
s.append(nums[i])

self.dfs(count+1,nums,s,v)
s.pop()
v[i] = 0

2. Generate combinations

  • DFS + loop with increasing
class Solution:
def combine(self, n…

--

--