细语呢喃

技术改变生活

0%

『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.

1
2
**Input:**Digit string "23"
**Output:** ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

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

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

思路：

方法一: 直接dfs搜索

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if(digits.empty()) return ans;
        static const vector<string> button = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        dfs(0, "", ans, button, digits);
        return ans;
    }
    
    void dfs(int start, string cur, vector<string> &ans, const vector<string> button, const string &digits){
        if(cur.size() == digits.size()){
            ans.push_back(cur);
            return;
        }
        for(char c: button[digits[start] - '0'])
            dfs(start + 1, cur + c, ans, button, digits);
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits: return []
        button = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        ans = []
        self.dfs(0, '', ans, button, digits)
        return ans
    
    def dfs(self, i, cur, ans, button, digits):
        if len(cur) == len(digits):
            ans.append(cur)
            return
        
        for c in button[int(digits[i])]:
            self.dfs(i + 1, cur + c, ans, button, digits)

方法二:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if(digits.empty()) return ans;
        static const vector<string> button = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ans.push_back("");
        for(int i = 0; i < digits.size(); i++){
            vector<string> temp;
            for(char c: button[digits[i] - '0']){
                for(string cur: ans){
                    temp.push_back(cur + c);
                }
            }
            ans = temp;
        }
        return ans;
    }
};

 

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    void dfs(int n, int left, string cur, vector<string> & ans){
        if(!n && !left){
            ans.push_back(cur);
            return;
        }
        if(n > 0) dfs(n - 1, left + 1, cur + '(', ans);
        if(left > 0) dfs(n, left - 1, cur + ')', ans);
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        dfs(n, 0, "", ans);
        return ans;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ans = []
        self.dfs(n, 0, "", ans)
        return ans

    def dfs(self, n, left, cur, ans):
        if not n and not left:
            ans.append(cur)
            return
        if n > 0: self.dfs(n - 1, left + 1, cur + '(', ans)
        if left > 0: self.dfs(n, left - 1, cur + ')', ans)

 

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 (_a_1, _a_2, … , _a_k) must be in non-descending order. (ie, _a_1 ≤ _a_2 ≤ … ≤ _a_k).
  • 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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
	void dfs(int cur,int curSum,vector<int> &path, vector<vector<int>> &ans,const vector<int> &candidates, const int target) {
		if (curSum == target) {
			ans.push_back(path);
			return;
		}
		for (int i = cur; i < candidates.size(); i++) {
			if (curSum + candidates[i] <= target) {
				path.push_back(candidates[i]);
				dfs(i, curSum + candidates[i], path, ans, candidates, target);
				path.pop_back();
			}
			while (i + 1 < candidates.size() && candidates[i] == candidates[i + 1]) i++;
		}
	}

public:
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> path;
		sort(candidates.begin(), candidates.end());
		dfs(0, 0, path, ans, candidates, target);
		return ans;
	}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0,target,path,ans,candidates);
        return ans;
    }

    private void dfs(int cur, int target, List<Integer> path, List<List<Integer>> ans, final int[] candidates) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = cur; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                path.add(candidates[i]);
                dfs(i, target - candidates[i], path, ans, candidates);
                path.remove(path.size() - 1);
            }
            while(i + 1 < candidates.length && candidates[i] == candidates[i+1]) i++;
        }
    }
}


Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        ans, _path = [], []
        self.solve(0, target, _path, ans, candidates)
        return ans

    def solve(self, cur, target, _path, ans, candidates):
        if target == 0:
            ans.append(_path[:])  # use _path will be wrong.
            return

        while cur < len(candidates):
            if candidates[cur] <= target:
                _path.append(candidates[cur])
                self.solve(cur, target - candidates[cur], _path, ans, candidates)
                _path.pop()
            while cur + 1 < len(candidates) and candidates[cur] == candidates[cur + 1]: cur += 1
            cur += 1


 

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 (_a_1, _a_2, … , _a_k) must be in non-descending order. (ie, _a_1 ≤ _a_2 ≤ … ≤ _a_k).
  • 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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private:
	void dfs(int cur,int target,vector<int> &path, vector<vector<int>> &ans,const vector<int> &candidates) {
		if (target == 0) {
			ans.push_back(path);
			return;
		}
		for (int i = cur; i < candidates.size(); i++) {
            if(i > cur && candidates[i] == candidates[i - 1])
                continue;
			if (candidates[i] <= target) {
				path.push_back(candidates[i]);
				dfs(i + 1, target - candidates[i], path, ans, candidates);
				path.pop_back();
			}
		}
	}
 
public:
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> path;
		sort(candidates.begin(), candidates.end());
		dfs(0, target, path, ans, candidates);
		return ans;
	}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0,target,path,ans,candidates);
        return ans;
    }

    private void dfs(int cur, int target, List<Integer> path, List<List<Integer>> ans, final int[] candidates) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = cur; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                path.add(candidates[i]);
                dfs(i + 1, target - candidates[i], path, ans, candidates);
                path.remove(path.size() - 1);
            }
            while(i + 1 < candidates.length && candidates[i] == candidates[i+1]) i++;
        }
    }
}

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        ans, _path = [], []
        self.solve(0, target, _path, ans, candidates)
        return ans

    def solve(self, cur, target, _path, ans, candidates):
        if target == 0:
            ans.append(_path[:])  # use _path will be wrong.
            return

        while cur < len(candidates):
            if candidates[cur] <= target:
                _path.append(candidates[cur])
                self.solve(cur + 1, target - candidates[cur], _path, ans, candidates)
                _path.pop()
            while cur + 1 < len(candidates) and candidates[cur] == candidates[cur + 1]: cur += 1
            cur += 1

 

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:

1
2
3
4
5
6
7
8
9
10
11
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

题目地址：leetcode N-Queens

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

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

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

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
	inline bool check(vector<int> &place, int cur){
		for (int j = 0; j < cur; j++)
			if (place[cur] == place[j] || abs(place[cur] - place[j]) == cur - j)
				return false;
		return true;
	}

	void solve(int cur, int n, vector<int> &place, vector<vector<string>> &ans){
		if (cur == n){
			vector<string> res;
			for (int k = 0; k < n;k++)
				for (int i = 0; i < n;i++)
					if (place[i] == k){
						string temp(n, '.');
                        temp[i] = 'Q';
						res.push_back(temp);
					}
			ans.push_back(res);
			return;
		}
		for (int i = 0; i < n; i++)	{
			place[cur] = i;
			if (check(place, cur))
				solve(cur + 1, n, place, ans);
		}
	}

	vector<vector<string>> solveNQueens(int n) {
		vector<vector<string>>ans;
		vector<int> place(n, 0);
		solve(0, n, place, ans);
		return ans;
	}
};

 

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    # @return a list of lists of string
    def solveNQueens(self, n):
        self.ans=[]
        place=[0]*n
        self.solve(0, n,place)    
        return self.ans  
        
    def check(self,cur,place):
        for i in range(0,cur):
            if place[i]==place[cur] or abs(place[i]-place[cur])==cur-i:
                return False
        return True
    
    def solve(self,cur,n,place):
        if cur==n:
            temp=[]
            for k in range(0,n):
                for i in range(0,n):
                    if place[i]==k:
                        L='.'*i+'Q'+'.'*(n-i-1)
                        temp.append(L)
            self.ans.append(temp)                                 
            return
        for i in range(0,n):
            place[cur]=i
            if(self.check(cur,place)):
                self.solve(cur + 1, n, place)

 

另一种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
	bool check(int x, int y, vector<string> &board) {
		for (int i = 0; i < x; ++i)
			if (board[i][y] == 'Q')
				return false;

		for (int i = x - 1, j = y - 1; 0 <= i && 0 <= j; --i, --j)
			if (board[i][j] == 'Q')
				return false;

		for (int i = x - 1, j = y + 1; j < board.size() && i >= 0; --i, ++j)
			if (board[i][j] == 'Q')
				return false;

		return true;
	}

	void dfs(int x, const int n, vector<string> &board, vector<vector<string>> &ans) {
        if (x >= n) {
			ans.push_back(board);
			return;
		}
        
        for(int y = 0; y < n; ++y){
            if (check(x, y, board)) {
                board[x][y] = 'Q';
                dfs(x + 1, n, board, ans);
                board[x][y] = '.';
		    }
        }
	}

public:
	vector<vector<string>> solveNQueens(int n) {
		vector<string> board(n, string(n, '.'));
		vector<vector<string>> ans;
		dfs(0, n, board, ans);
		return ans;
	}
};

 

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    inline bool check(int row, vector<int> &place){
        for(int i = 0; i < row; ++i)
            if(place[i] == place[row]  row - i == abs(place[row] - place[i]))
                return false;
        return true;
    }
    
    void dfs(int row, vector<int> &place, int &ans){
        if(row == place.size()){
            ++ans;
            return;
        }
        for(int i = 0; i < place.size(); ++i){
            place[row] = i;
            if(check(row, place))
                dfs(row + 1, place, ans);
        }
    }
    
public:
    int totalNQueens(int n) {
        vector<int> place(n, 0);
        int ans = 0;
        dfs(0, place, ans);
        return ans;
    }
};

 

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:        
    # @return an integer
    def totalNQueens(self, n):
        self._cnt=0
        place=[0]*n
        self.solve(0, n,place)    
        return self._cnt   
        
    def check(self,cur,place):
        for i in range(0,cur):
            if place[i]==place[cur] or abs(place[i]-place[cur])==cur-i:
                return False
        return True
    
    def solve(self,cur,n,place):
        if cur==n:
            self._cnt += 1
            return
        for i in range(0,n):
            place[cur]=i
            if(self.check(cur,place)):
                self.solve(cur + 1, n, place)

 

另一种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
	bool check(int x, int y, vector<string> &board) {
		for (int i = 0; i < x; ++i)
			if (board[i][y] == 'Q')
				return false;

		for (int i = x - 1, j = y - 1; 0 <= i && 0 <= j; --i, --j)
			if (board[i][j] == 'Q')
				return false;

		for (int i = x - 1, j = y + 1; j < board.size() && i >= 0; --i, ++j)
			if (board[i][j] == 'Q')
				return false;

		return true;
	}

	void dfs(int x, const int n, vector<string> &board, int &ans) {
        if (x >= n) {
			++ans;
			return;
		}
        
        for(int y = 0; y < n; ++y){
            if (check(x, y, board)) {
                board[x][y] = 'Q';
                dfs(x + 1, n, board, ans);
                board[x][y] = '.';
		    }
        }
	}

public:
	int totalNQueens(int n) {
		vector<string> board(n, string(n, '.'));
		int ans = 0;
		dfs(0, n, board, ans);
		return ans;
	}
};

 

 

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	void solve( int cnt, int cur, int n, int k, vector<int>& vis, vector<vector<int> > & ans){
		if (cnt == k){
			ans.push_back(vis);
			return;
		}
		for (int i = cur; i < n; i++){
			vis.push_back(i+1);
			solve(cnt+1,i+1, n, k,vis, ans);
			vis.pop_back();
		}
	}
	vector<vector<int> > combine(int n, int k) {
		vector<vector<int> > ans;
		vector<int> vis;
		solve(0,0, n, k,vis, ans); 
		return ans;
	}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private void dfs(int cur, List<Integer> res, final int n, final int k, List<List<Integer>> ans) {
        if (res.size() == k) {
            ans.add(new ArrayList<>(res));
            return;
        }
        for (int i = cur; i <= n; i++) {
            res.add(i);
            dfs(i + 1, res, n, k, ans);
            res.remove(res.size() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<Integer> res = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs(1, res, n, k, ans);
        return ans;
    }
}


Python

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    # @return a list of lists of integers
    def combine(self, n, k):
        ans,res=[],[]
        self.solve(res, 0, 0, n, k, ans)
        return ans
        
    def solve(self,res,cnt,cur,n,k,ans):   
        if cnt==k:
            ans.append(res[:])
            return
        
        for i in range(cur,n):
            res.append(i+1)
            self.solve(res, cnt+1, i+1, n, k, ans)
            res.pop()

 

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	void solve(int cur, int n, vector<int> &nums, vector<int> &res,vector<vector<int>> & ans){	
		ans.push_back(res);
		for (int i = cur; i < n; i++){
			res.push_back(nums[i]);
			solve(i+1, n, nums, res, ans);
			res.pop_back();
		}
	}

	vector<vector<int>> subsets(vector<int> &nums) {
		vector<vector<int>> ans;
		vector<int> res;
		solve(0, nums.size(), nums, res, ans);
		return ans;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private void dfs(int cur, List<Integer> res, int[] nums, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(res));
        for (int i = cur; i < nums.length; i++) {
            res.add(nums[i]);
            dfs(i + 1, res, nums, ans);
            res.remove(res.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> res = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs(0, res, nums, ans);
        return ans;
    }
}


Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans,res=[],[]
        self.solve(0, len(nums), nums, res, ans)
        return ans
                      
    def solve(self,cur,n,nums,res,ans):           
        ans.append(res[:])
        for i in range(cur,n):
            res.append(nums[i])
            self.solve(i+1, len(nums), nums, res, ans)
            res.pop()

 

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 =

1
2
3
4
5
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

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

题目地址：leetcode Word Search

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

思路：DFS，注意剪枝。

PS:进阶篇：Word Search II

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int dx[4] = {1, -1, 0, 0 };
const int dy[4] = {0, 0, 1, -1 };
class Solution {
 public:	 
	 bool ok(int nx,int ny,int m,int n){
		 if (nx < 0 || nx >= m || ny < 0 || ny >= n) return false;
		 return true;
	 }
	 bool dfs(int x, int y, int cur, vector<vector<bool> >& vis,vector<vector<char> > &board, string &word){		
		 if (cur == word.length() ) return true;
		 if (cur > word.length())   return false;
		 for (int k = 0; k < 4; k++){
			 int nx = x + dx[k], ny = y + dy[k];
			 if (ok(nx,ny,board.size(),board[0].size()) &&!vis[nx][ny]&&board[nx][ny]==word[cur]){
				 vis[nx][ny] = true;			
				 if (dfs(nx, ny, cur+1, vis, board, word)) return true;				
				 vis[nx][ny] = false;
			 }
		 }
		 return false;
	 }

	 bool exist(vector<vector<char> > &board, string word) {
		 vector<vector<bool> > vis(board.size(), vector<bool>(board[0].size(), 0));
		 
		 for (int i = 0; i < board.size(); i++){
			 for (int j = 0; j < board[0].size(); j++){
				 if (board[i][j] != word[0]) continue;
				 vis[i][j] = true;
				 if (dfs(i, j, 1, vis, board, word)) return true;
				 vis[i][j] = false;
			 }
		 }			 			 
		 return false;
	 }
 };

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    # @param board, a list of lists of 1 length string
    # @param word, a string
    # @return a boolean
    def exist(self, board, word):
        vis = [[0 for i in range(len(board[0]))]for j in range(len(board))]
        m , n = len(board) , len(board[0])
        self.dx , self.dy= [1,-1,0,0], [0,0,1,-1]
        
        for i in range(m):
            for j in range(n):
                if board[i][j]==word[0]:
                    vis[i][j]=True
                    if(self.dfs(i,j,1,vis,board,word)): return True
                    vis[i][j]=False
        return False
        
    def dfs(self,x,y,cur,vis,board,word):
        if cur==len(word):  return True
        if cur > len(word): return False
        for k in range(4):
            nx,ny=x+self.dx[k] , y + self.dy[k]
            if nx < 0 or nx >= len(board) or ny <0 or ny >= len(board[0]):
                continue
            if board[nx][ny]==word[cur] and not vis[nx][ny]:
                vis[nx][ny]=True
                if(self.dfs(nx, ny, cur+1, vis, board, word)): return True
                vis[nx][ny]=False
        
        return False

另一种写法：

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
	const vector<int> dx = { 0, 0, 1, -1 };
	const vector<int> dy = { 1, -1, 0, 0 };

	bool dfs(int cur, int x, int y, vector<vector<bool>> &vis, const vector<vector<char>>& board, const string &word) {
		if (cur == word.size()) return true;
		if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size()
			|| vis[x][y] || word[cur] != board[x][y])
			return false;

		vis[x][y] = true;
		for (int i = 0; i < 4; ++i)
			if (dfs(cur + 1, x + dx[i], y + dy[i], vis, board, word))
				return true;

		vis[x][y] = false;
		return false;
	}

public:
	bool exist(vector<vector<char>>& board, string word) {
		if (board.empty() || board[0].empty()) return false;

		vector<vector<bool>> vis(board.size(), vector<bool>(board[0].size(), false));
		for (int i = 0; i < board.size(); ++i)
			for (int j = 0; j < board[i].size(); ++j)
				if (word[0] == board[i][j] && dfs(0, i, j, vis, board, word))
					return true;
		return false;
	}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def dfs(self, cur, x, y, vis, board, word):
        if cur == len(word):
            return True
        
        if x < 0 or y < 0 or x >= len(board) or y >= len(board[0]):
            return False
        if vis[x][y] or word[cur] != board[x][y]:
            return False
        
        vis[x][y] = True
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            if self.dfs(cur + 1, x + dx, y + dy, vis, board, word):
                return True
        vis[x][y] = False
        return False
        
        
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board or not board[0]:
            return False
        vis = [[False] * len(board[0]) for _ in range(len(board))] 
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == word[0] and self.dfs(0, i, j, vis, board, word):
                    return True
        return False

 

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	void solve(int cur, int n, vector<int> &nums, vector<int> &res,vector<vector<int>> & ans){	
		ans.push_back(res);
		for (int i = cur; i < n; i++){
			res.push_back(nums[i]);
			solve(i+1, n, nums, res, ans);
			res.pop_back();
            while (i + 1 < n && nums[i] == nums[i + 1]) i++;
		}
	}

	vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		vector<int> res;
		solve(0, nums.size(), nums, res, ans);
		return ans;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private void dfs(int cur, List<Integer> res, int[] nums, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(res));
        for (int i = cur; i < nums.length; i++) {
            res.add(nums[i]);
            dfs(i + 1, res, nums, ans);
            res.remove(res.size() - 1);
            while (i + 1 < nums.length && nums[i] == nums[i + 1]) i++;
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<Integer> res = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs(0, res, nums, ans);
        return ans;
    }
}


Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        ans, res = [], []
        self.solve(0, len(nums), nums, res, ans)
        return ans

    def solve(self, cur, n, nums, res, ans):
        ans.append(res[:])
        i = cur
        while i < n:
            res.append(nums[i])
            self.solve(i + 1, len(nums), nums, res, ans)
            while i + 1 < n and nums[i] == nums[i + 1]: i += 1
            res.pop()
            i += 1


 

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:

1
2
3
4
11110
11010
11000
00000

Answer: 1

Example 2:

1
2
3
4
11000
11000
00100
00011

Answer: 3

传送门

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

思路：dfs/bfs均可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    # @param grid, a list of list of characters
    # @return an integer
    def numIslands(self, grid):
        if not grid or not grid[0]:return 0
        m,n=len(grid),len(grid[0])
        vis = [[False for j in xrange(n)]for i in xrange(m)]
        self.dx,self.dy=[1,-1,0,0],[0,0,1,-1]
        ans = 0 
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j]=='1' and not vis[i][j]:
                    vis[i][j]=True
                    self.dfs(i,j,grid,vis)
                    ans+=1
        return ans

    def dfs(self,x,y,grid,vis):
        for k in xrange(4):
            nx,ny=x+self.dx[k],y+self.dy[k]
            if nx<0 or ny<0 or nx >=len(grid) or ny>=len(grid[0])\
            or grid[nx][ny]=='0' or vis[nx][ny]: continue
            vis[nx][ny]=True
            self.dfs(nx,ny,grid,vis)

 

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
	vector<vector<int> >ans;
    vector<vector<int> > combinationSum3(int k, int n) {
    	vector<int> res;
        dfs(0,res,k,n);
        return ans;
    }
    
    void dfs(int cur,vector<int> &res,const int k,const int n){
    	if(res.size() >k) return;
		if(res.size() ==k){
			int sum = 0;
			for(int i=0;i<k;i++) sum += res[i];
			if(sum == n) ans.push_back(res);
			return;
		}
		
		for(int i = cur+1;i<=9;i++){
			res.push_back(i);
			dfs(i,res,k,n);
			res.pop_back();
		}	
	}
};

 

 

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".

1
2
((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2] Example 2

Input: "2*3-4*5"

1
2
3
4
5
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

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

题目地址：leetcode  Different Ways to Add Parentheses

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def diffWaysToCompute(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        dp = {}
        return self.dfs(s, dp)

    def dfs(self, s, dp):
        if s in dp: return dp[s]
        ans = []
        n = len(s)
        for i in xrange(n):
            if s[i] not in ["+", "-", "*"]: continue
            res1, res2 = self.dfs(s[:i], dp), self.dfs(s[i + 1:], dp)
            for x in res1:
                for y in res2:
                    if s[i] == '+':   ans.append(x + y)
                    elif s[i] == '-': ans.append(x - y)
                    elif s[i] == '*': ans.append(x * y)
        if not ans: ans.append(int(s))
        dp[s] = ans
        return ans


 

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:

1
2
3
4
5
"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

题目地址：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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef long long int LL;
class Solution {
public:
	vector<string> addOperators(string num, int target) {
		vector<string> ans;
		dfs(0, "", 0, 0, ans, num.length(), num, target);
		return ans;
	}

	void dfs(int cur, string path, LL pre, LL val, vector<string> & ans, const int n, const string &num, const int target) {
		if (cur == n && pre + val == target) {
			ans.push_back(path);
			return;
		}
		LL x = 0;
		for (int i = cur; i < n; i++) {
			x = x * 10 + (num[i] - 48); // - '0' it is 48
			string str_x = to_string(x);
			if (cur != 0) {
				dfs(i + 1, path + "+" + str_x, pre + val, x, ans, n, num, target);
				dfs(i + 1, path + "-" + str_x, pre + val, -x, ans, n, num, target);
				dfs(i + 1, path + "*" + str_x, pre, val * x, ans, n, num, target);
			}
			else
				dfs(i + 1, str_x, 0, x, ans, n, num, target);
			if (num[cur] == '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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def dfs(self, cur, cur_path, vis, g, ans):
        if cur == len(g) - 1:
            ans.append(cur_path)
            return

        for nx in g[cur]:
            if vis[nx]: continue
            vis[nx] = True
            self.dfs(nx, cur_path + [nx], vis, g, ans)
            vis[nx] = False

    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        vis = [False] * len(graph)
        ans = []
        cur_path = [0]
        self.dfs(0, cur_path, vis, graph, ans)
        return ans

 

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

请我喝杯咖啡吧~