『leetcode』递归/DFS

leetcode dfs 归纳整理 包括:

  • 17. Letter Combinations of a Phone Number
  • 22. Generate Parentheses
  • 39 Combination Sum
  • 40 Combination Sum II
  • 51 N-Queens
  • 52 N-Queens II
  • 77 Combinations
  • 78 Subsets
  • 79 Word Search
  • 90 Subsets II
  • 200 Number of Islands
  • 216 Combination Sum III
  • 241 Different Ways to Add Parentheses
  • 282 Expression Add Operators
  • 797. All Paths From Source to Target

17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

题目地址:leetcode Letter Combinations of a Phone Number

题目大意: 给定一串由数字组成的字符串,求9宫格的手机键盘能打出的字母组合。

思路:

方法一: 直接dfs搜索

C++

Python

 方法二:

BFS的思想。 解相当于一颗多叉树上的遍历。 digits[i – 1] 遍历完答案为ans,则下一次就是枚举ans和当前数字digits[i] 能打出的字母的组合起来。

假设ans有9种了,现在digits[i]对应的有4种,那就是9 * 4=36种。

 

 


 

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

题目地址:leetcode Generate Parentheses

题目大意:给定数字n,求所有可能的合法括号。

思路:递归搜索即可。。记录左边有多少个括号,总共还有个左括号没有用即可。

C++

Python

 

39. Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

题目地址:leetcode Combination Sum

题意:给定一串序列和一个target.要求求出序列中的所有子集,使得子集和为target(元素可以重复使用)

思路:

排序然后DFS进行枚举。

结果什么时候会重复?当candidates有重复元素的时候。(虽然这题感觉没有重复的数据。。)

但是比如[2,2,3,6,7] 结果应该还是[7]、[2,2,3]

C++

Java

Python

 

40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

题目地址:leetcode Combination Sum II

题意:和上面一题差不多,都是求子集和为target的所有子集。

不同的地方在于,这一题的元素只能使用一次。

思路:

也是排序后进行DFS,不过不同的地方在于下一次枚举的元素应该为当前元素位置+1,还有就是如果当前元素有解,那么下一次从下一个不同于这个元素的位置开始。

详见代码高亮行

C++

Java

 

Python

 

 

 

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

题目地址:leetcode N-Queens

题目大意: 给定N,求出N皇后的解

思路: DFS搜索解即可。先尝试防止第row行,然后枚举第row行的所有col看是否不冲突

代码和52题几乎一样。只是改成具体结果而已。(建议先做52题)

C++

 

python

 

另一种写法:

 

 

52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

题目地址:leetcode N-Queens II

题目大意:给定数字n,求n皇后的解有多少个

思路: 大一就做过的玩意~ 水。。

C++

 

python

 

另一种写法:

 

 

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

题目地址:leetcode Combinations

题意:给定1~n中由k个数组成的组合。

思路:dfs

C++

Java

Python

现在的貌似TLE了,原来AC的

 

 

 

78. Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

题目地址:leetcode Subsets

题意:给定集合S(元素唯一),求S的所有子集(包括空集)

思路:和上面的组合不同在于,组合那题当cnt==k时候为解,这一题每一次递归都是一次解。

C++

Java

Python

 

 


 

 

79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

题目地址:leetcode Word Search

题目大意:给定一个矩阵和一个字符串,求该字符串是否能在矩阵中找到。(通过上下、左右相邻拼接,但是每个字符只能使用一次)

思路:DFS,注意剪枝。

 

PS:进阶篇:Word Search II

C++

 

Python

另一种写法:

C++

Python

 

 

 

 

90. Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

题目地址:leetcode Subsets II

题意:给定集合S(元素不唯一),求S的所有子集(包括空集)

思路:和上面的subset一样,只不过需要去重。

C++

Java

Python

 

 

200. Number of Islands

 

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

Example 2:

Answer: 3

传送门

题意: 给定由0和1组成的二维数组,求1的连通块

思路:dfs/bfs均可。

 

 

216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

传送门

题意:给定n,要求用1到9的k个数来使得这k个数的和为n

思路:DFS。。。

C++

 

 

 

241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1

Input: "2-1-1".

Output: [0, 2]
Example 2

Input: "2*3-4*5"

Output: [-34, -14, -10, -10, 10]

题目地址:leetcode  Different Ways to Add Parentheses

题意:给定一个字符串表达式,要求你添加若干个括号,得到所有可能的结果。

思路:分治法,若s[i] 为+-*三个符号,把它分为左右两部分即可。此外,可以用记忆化搜索加快速度。

 

 

 

 

282. Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

题目地址:leetcode Expression Add Operators

题意:给定0~9数字组成的字符串和一个数target,要求你输出能用+ – * 三种运算符计算得到target的所有解。

思路:。。还以为有啥高深的解法。想了半天。。。。就是直接DFS就可以了。。。O(4^n) ,n为字符串长度

注意点有:

  • 由于运算符的优先级,因此,分为两半,一个是pre为计算的值,一个为val为pre右方还未计算的值,对于当前的数x,进行如下的操作可以保证优先级
    • 加法:pre = pre + val   val = x
    • 减法: pre =  pre – val   val = -x
    • 乘法:pre = pre      val = val *x
  • 当前的第一个数为’0’的情况   计算完后Break

 


 

797. All Paths From Source to Target

Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows:  the nodes are 0, 1, …, graph.length – 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0—>1
| |
v v
2—>3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

题目地址:leetcode All Paths From Source to Target

题目大意:给定一个y哦那个邻接表表示的有向无环图,要你输出从0节点到n-1节点的所有路径

思路:直接dfs大水题啊。(PS: 有向无环图其实都不用判断是不是重复走过了。。vis不需要也行)

Python

 

 

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > 『leetcode』递归/DFS
本文地址:https://www.hrwhisper.me/leetcode-recursive-or-dfs/

听说长得好看的已经打赏了

Leetcode . permalink.

9 thoughts on “『leetcode』递归/DFS

  1. 麻烦请教一个问题哈。为什么在subset这道题里,要ans.append(res[:])而不是ans.append(res)呢?我记得看到你解释过但是忘记在哪道题里了。。。。谢谢。

    • 不用res[:]的话,添加进去的只是个类似指针的东西。 然后如果res被修改,在ans里面的也会被修改。

  2. combination sum2 这里代码第二处高亮看不懂啊^-^大概思路是一样的,不过我多加了一处判定条件: bool check(vector& res,vector >&ans) { for(int i=0;i

Leave a Reply

Your email address will not be published. Required fields are marked *