Iris S

思考重点:分治法

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

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

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

  • 分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
  • 分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

分治法在二叉树题目上的运用

  • 根据题目,思考左节点与右节点的关系,并推理出解题所需要返回的值 / 改变的变量
  • 分别往左子树和右子树递归
  • 确定base case

二叉树题目里面,常出现的分析场景和应对方案

  1. 询问最大/最小子树
  • 定义全局变量去储存最大/最小子树的和
  • 通过left + right + root.val 来获取当前子树的值,并和全局变量做比较
  • 更新全局变量

2. 通过左右子树的位置来搜索A和B节点的LCA

通过A和B的位置来推算LCA的位置

  • 当A或B 等于根,返回根
  • 当B是A子树的一部分,而A是左子树的一部分,返回左子树;vice versa
  • 当A和B分别在左子树和右子树,返回当前的根

3. 验证当前树是否平衡

从最小子树开始,通过左子树和右子树的关系来推测平衡性

  • 返回三个变量:左右子树的值,左右子树的高度,当前根

--

--

前缀型

划分型

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

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

匹配型

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

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

例2. dp[i][j] = s[0:i]通过多少次能够变成p[0:j]

  • wildcard matching
  • edit distance

区间型

有substring, subarray等字眼

使用二维数组dp[i][j]记录两个区间所代表的最优值/可行性/方案总数

接龙型

  • 使用一维数组dp[i]: 以下标为i的元素结尾的最长长度

--

--

Substring系列

找At least K个数

  • 用for loop移动右指针,左指针只在通过某些条件的情况下移动
  • 每一轮for loop都累加当前count,通过某些条件的情况下给count++
  • Substring With At Least K Distinct Characters — https://www.lintcode.com/problem/1375/description

Replacement系列

滑动窗口 — 利用最大窗口特性

  • 用max, min来记录合法string长度
  • 用k+单个字母最大出现次数来定义最大的窗口长度
  • 移动左指针来缩小窗口

技巧

  • hash table来储存某个字母出现的次数,当次数为0时,进行某些操作
  • 每一轮移动右指针一步,左指针只能在条件允许时移动

--

--

二维坐标型

最短路径

Sliding Puzzle https://www.lintcode.com/problem/794/?_from=collection&fromId=161

查找可行性

  • 从多个点开始,分层向四方搜索

Zombie in matrix — https://www.lintcode.com/problem/598/?_from=collection&fromId=161

--

--

  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: int, k: int) -> List[List[int]]:
res = []
def dfs(idx, s, count):
if count == k:
res.append(s[:])
for i in range(idx, n):
s.append(i+1)
dfs(i+1, s, count+1)
s.pop()

dfs(0,[], 0)
return res

3. Generate no repeating combinations

  • Sorting + Compare current and the previous index
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = [[]]

def dfs(idx, s):
if idx == len(nums):
return
for i in range(idx, len(nums)):
if i>idx and nums[i] == nums[i-1]:
continue
s.append(nums[i])
res.append(s[:])
dfs(i+1, s)
s.pop()

nums.sort()
dfs(0,[])
return res

--

--