深度优先搜索算法-1

Time: 20190809

DFS: 深度优先搜索

本类题型，题目写得越多，就越有把握。

面试或笔试，DFS是必然会考到的类型。

BFS是一分努力十分收获。
DFS是一分努力一分收获。

大纲

DFS主要会涉及到以下几个方面的知识点：

• 递归
• 组合
• 全排列
• 图
• 非递归法

什么时候用DFS?

找所有方案，找最优的方案，但后者大部分用的是动态规划方法解题，前者占90%。

组合搜索问题

问题：求所有满足条件的组合。
判断条件：组合中的元素顺序无关。
时间复杂度：

用递归的方式实现DFS会比较简单，是最常见的方式。

递归实现的三要素：

• 递归的定义
• 递归的拆解
• 递归的出口

案例

Lintcode 135. 数字组合

题目描述

给定一个候选数字的集合 candidates 和一个目标值 target. 找到 candidates 中所有的和为 target 的组合.

在同一个组合中, candidates 中的某个数字不限次数地出现.

样例
样例 1:

输入: candidates = [2, 3, 6, 7], target = 7
输出: [[7], [2, 2, 3]]
样例 2:

输入: candidates = [1], target = 3
输出: [[1, 1, 1]]
注意事项
所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.

思路

碰到找所有方案的题，一定是DFS，90%的DFS的题，要么是排列要么是组合。

时刻与subsets问题做区分，下面是两个主要的区别：

• 每个元素可以选择多次，
• 同时有target做筛选，属于有条件的subset

所以，针对每个元素可以选择多次的问题，我们在递归时，下标不要+1，仍然传递当前的index，在递归出口处做判断。

代码

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    def combinationSum(self, candidates, target):
        # write your code here
        results = []
        if candidates == None:
            return results
        # 排序
        candidates.sort()
        combination = []
        self.recur(candidates, 0, target, combination, results)
        return results
    
    def recur(self, candidates, startIndex, remainTarget, combination, results):
        
       # 1.递归的出口
        if  remainTarget == 0:
            results.append(combination + []) # 添加新的内存对象
            return 
        # 2.递归的拆解
        for i in range(startIndex, len(candidates)):
            if remainTarget < candidates[i]:
                break
            # [2,2,3,3,6,7]
            if i != 0 and candidates[i] == candidates[i-1]:
                continue # 跳过重复的元素
            combination.append(candidates[i])
            self.recur(candidates, i, remainTarget - candidates[i], combination, results)
            # 不重复选取的方式
            # self.recur(candidates, i, remainTarget - candidates[i], combination, results)
            combination.pop()

上面这就是能AC的代码了。

相关问题

屏幕快照 2019-08-09 下午3.36.12.png

Lintcode 153. 数字组合II

题目描述

给定一个数组 num 和一个整数 target. 找到 num 中所有的数字之和为 target 的组合.

样例
样例 1:

输入: num = [7,1,2,5,1,6,10], target = 8
输出: [[1,1,6],[1,2,5],[1,7],[2,6]]
样例 2:

输入: num = [1,1,1], target = 2
输出: [[1,1]]
解释: 解集不能包含重复的组合
注意事项
在同一个组合中, num 中的每一个数字仅能被使用一次.
所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.
解集不能包含重复的组合.

思路

和上面的代码骨架基本相同，可直接阅读代码来看差别。

代码

class Solution:
    """
    @param num: Given the candidate numbers
    @param target: Given the target number
    @return: All the combinations that sum to target
    """
    
    # [1,1,2]
    # [1', 2] 
    # [1'', 2]
    # 上面两个算重复的，所以需要对最后的结果去重
    # subsets II中用到了这种去重的方式
    
    def combinationSum2(self, nums, target):
        # write your code here
        results = []
        if nums == None:
            return results
        # 上来排个序总是要的
        nums.sort()
        combination = []
        self.recur(nums, 0, combination, target, results)
        return results
        
    def recur(self, nums, startIndex, combination, remainTarget, results):
        # 1.递归出口
        if remainTarget == 0:
            results.append(combination + [])
            return
        
        # 2.递归拆解
        for i in range(startIndex, len(nums)):
            if remainTarget < nums[i]:
                break
            # 这个去重的方式和subsets II中用到的是一样的
            if i != 0 and nums[i] == nums[i-1] and i != startIndex:
                continue
            
            combination.append(nums[i])
            self.recur(nums,i + 1, combination, remainTarget - nums[i], results )
            combination.pop()

过程中搜索去重的方法：选代表。

1 1 1 2 ==> target = 4

1' 1'' 2
1' 1''' 2

136. 分割回文串

所有的切割问题都是组合问题。

题目描述

描述
中文
English
给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.

返回所有可能的分割方案.

不同的方案之间的顺序可以是任意的.
一种分割方案中的每个子串都必须是 s 中连续的一段.
您在真实的面试中是否遇到过这个题？
样例
样例 1:

输入: "a"
输出: [["a"]]
解释: 字符串里只有一个字符, 也就只有一种分割方式 (就是它本身)
样例 2:

输入: "aab"
输出: [["aa", "b"], ["a", "a", "b"]]
解释: 有两种分割的方式.
1. 将 "aab" 分割成 "aa" 和 "b", 它们都是回文的.
2. 将 "aab" 分割成 "a", "a" 和 "b", 它们全都是回文的.

思路

所有的分割问题都是组合问题，组合问题属于DFS类问题。

n个字母的切割问题，就是n - 1个数字的组合问题。

"abc"
a1b2c
a b c -> [1,2]
a bc -> [1]
ab c -> [2]
abc -> []

这样转换之后，就可以使用subsets问题的解法了。

代码

class Solution:
    """
    @param: s: A string
    @return: A list of lists of string
    """
    def partition(self, s):
        # write your code here
        results = []
        if s == None or len(s) == 0:
            return results
            
        partition = []
        self.recur(s, 0, partition, results)
        return results
        
    def recur(self, s, startIndex, partition, results):
        # 递归出口
        if startIndex == len(s):
            print("递归出口：", startIndex)
            results.append(partition + [])
            return
        for i in range(startIndex, len(s)):
            subString = s[startIndex: i + 1]
            print("subString: ", subString)
            
            # 如果不是回文串则跳过去
            if not self.isPalindrome(subString):
                continue
            
            partition.append(subString)
            self.recur(s, i + 1, partition, results)
            partition.pop()
    
    def isPalindrome(self, s):
        for i in range(len(s)):
            if s[i] != s[len(s) - i - 1] :
                return False
        return True

END.