[关闭]
@Yano 2015-12-30T03:25:46.000000Z 字数 14623 阅读 6008

LeetCode之Backtracing题目汇总

LeetCode

我的博客:http://blog.csdn.net/yano_nankai
LeetCode题解:https://github.com/LjyYano/LeetCode


LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总


文章目录:


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:

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


参考:LeetCode 039 Combination Sum

使用递归,注意保存结果时,应该新建一个ArrayList:result.add(new ArrayList< Integer>(cur))。否则result会指向一直变化的cur。

  1. public List<List<Integer>> combinationSum(int[] candidates, int target) {
  2. if (candidates == null || candidates.length == 0) {
  3. return new ArrayList<List<Integer>>();
  4. }
  5. List<List<Integer>> result = new ArrayList<List<Integer>>();
  6. ArrayList<Integer> cur = new ArrayList<Integer>();
  7. Arrays.sort(candidates);
  8. dfs(0, target, result, cur, candidates);
  9. return result;
  10. }
  11. private void dfs(int start, int target, List<List<Integer>> result,
  12. ArrayList<Integer> cur, int[] candidates) {
  13. if (target == 0) {
  14. result.add(new ArrayList<Integer>(cur));
  15. return;
  16. }
  17. for (int i = start; i < candidates.length; i++) {
  18. // candidates[i] > target,则递归结束,后面不可能是解
  19. if (candidates[i] > target) {
  20. return;
  21. }
  22. cur.add(candidates[i]);
  23. dfs(i, target - candidates[i], result, cur, candidates);
  24. cur.remove(cur.size() - 1);
  25. }
  26. }

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:

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 040 Combination Sum II

  1. Combination Sum每个元素可以使用多次,所以递归是dfs(i, target - candidates[i], result, cur, candidates);
  2. Combination Sum II每个元素只能使用一次,所以递归是dfs(i + 1, target - candidates[i], rt, cur, candidates);因为解可能重复,所以使用set,最后转成list。
  1. public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  2. if (candidates == null || candidates.length == 0) {
  3. return new ArrayList<List<Integer>>();
  4. }
  5. Set<List<Integer>> rt = new HashSet<List<Integer>>();
  6. ArrayList<Integer> cur = new ArrayList<Integer>();
  7. Arrays.sort(candidates);
  8. dfs(0, target, rt, cur, candidates);
  9. return new ArrayList<List<Integer>>(rt);
  10. }
  11. private void dfs(int start, int target, Set<List<Integer>> rt,
  12. ArrayList<Integer> cur, int[] candidates) {
  13. if (target == 0) {
  14. rt.add(new ArrayList<Integer>(cur));
  15. return;
  16. }
  17. for (int i = start; i < candidates.length; i++) {
  18. // candidates[i] > target,则递归结束,后面不可能是解
  19. if (candidates[i] > target) {
  20. return;
  21. }
  22. cur.add(candidates[i]);
  23. dfs(i + 1, target - candidates[i], rt, cur, candidates);
  24. cur.remove(cur.size() - 1);
  25. }
  26. }

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. [[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

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

Credits: 
Special thanks to @mithmatt for adding this problem and creating all test cases.


参考:LeetCode 216 Combination Sum III

这次是指定了元素的个数,用一个变量记录即可。

  1. public List<List<Integer>> combinationSum3(int k, int n) {
  2. List<List<Integer>> rt = new ArrayList<List<Integer>>();
  3. if (k < 1 || n < 1) {
  4. return rt;
  5. }
  6. List<Integer> cur = new ArrayList<Integer>();
  7. dfs(rt, cur, 0, k, n, 1);
  8. return rt;
  9. }
  10. private void dfs(List<List<Integer>> rt, List<Integer> cur, int sum, int k,
  11. int n, int level) {
  12. if (sum == n && k == 0) {
  13. rt.add(new ArrayList<Integer>(cur));
  14. return;
  15. } else if (sum > n || k <= 0) {
  16. return;
  17. }
  18. for (int i = level; i <= 9; i++) {
  19. cur.add(i);
  20. dfs(rt, cur, sum + i, k - 1, n, i + 1);
  21. cur.remove(cur.size() - 1);
  22. }
  23. }

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],
]

递归,选择数字k次,每次选择的数字都比前一个大。

  1. int target;// 次数
  2. Integer[] stack;// 存储每次排列
  3. Integer[] nums;// 存储1~n
  4. List<List<Integer>> rt;// 存储结果
  5. public void search(int p) {
  6. // 若长度为k,则stack是其中一个结果,保存结果
  7. if (p == target) {
  8. rt.add(new ArrayList<Integer>(Arrays.asList(stack)));
  9. return;
  10. }
  11. // 对于nums(1~n)中的每个元素
  12. for (Integer n : nums) {
  13. // 找到nums中第一个比stack最后元素大的元素
  14. if (p > 0 && n <= stack[p - 1]) {
  15. continue;
  16. }
  17. // 找到下一个元素,递归
  18. stack[p] = n;
  19. search(p + 1);
  20. }
  21. }
  22. public List<List<Integer>> combine(int n, int k) {
  23. target = k;
  24. nums = new Integer[n];
  25. stack = new Integer[k];
  26. for (int i = 0; i < nums.length; i++) {
  27. nums[i] = i + 1;
  28. }
  29. rt = new ArrayList<List<Integer>>();
  30. search(0);
  31. return rt;
  32. }

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:

"((()))", "(()())", "(())()", "()(())", "()()()"


  1. public List<String> generateParenthesis(int n) {
  2. if (n <= 0) {
  3. return new ArrayList<String>();
  4. }
  5. ArrayList<String> rt = new ArrayList<String>();
  6. dfs(rt, "", n, n);
  7. return rt;
  8. }
  9. void dfs(ArrayList<String> rt, String s, int left, int right) {
  10. if (left > right) {
  11. return;
  12. }
  13. if (left == 0 && right == 0) {
  14. rt.add(s);
  15. }
  16. if (left > 0) {
  17. dfs(rt, s + "(", left - 1, right);
  18. }
  19. if (right > 0) {
  20. dfs(rt, s + ")", left, right - 1);
  21. }
  22. }

Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.


将数字i,转换成格雷码的公式是:

  1. public List<Integer> grayCode(int n) {
  2. List<Integer> rt = new ArrayList<Integer>();
  3. if (n < 0) {
  4. return rt;
  5. }
  6. for (int i = 0; i < Math.pow(2, n); i++) {
  7. rt.add((i >> 1) ^ i);
  8. }
  9. return rt;
  10. }

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.

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

Note: 
Although the above answer is in lexicographical order, your answer could be in any order you want.


  1. static final char[][] CHAR_MAP = { {},// 0
  2. {},// 1
  3. { 'a', 'b', 'c' },// 2
  4. { 'd', 'e', 'f' },// 3
  5. { 'g', 'h', 'i' },// 4
  6. { 'j', 'k', 'l' },// 5
  7. { 'm', 'n', 'o' },// 6
  8. { 'p', 'q', 'r', 's' },// 7
  9. { 't', 'u', 'v' },// 8
  10. { 'w', 'x', 'y', 'z' } // 9
  11. };
  12. List<String> result;
  13. char[] stack;
  14. public List<String> letterCombinations(String digits) {
  15. if (digits == null || digits.length() == 0) {
  16. return new ArrayList<String>();
  17. }
  18. result = new ArrayList<String>();
  19. stack = new char[digits.length()];
  20. dfs(digits.toCharArray(), 0);
  21. return result;
  22. }
  23. private void dfs(char[] digits, int p) {
  24. if (p == digits.length) {
  25. result.add(new String(stack));
  26. } else {
  27. int num = digits[p] - '0';
  28. for (char c : CHAR_MAP[num]) {
  29. stack[p] = c;
  30. dfs(digits, p + 1);
  31. }
  32. }
  33. }

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
    ["aa","b"],
    ["a","a","b"]
]

这个问题,明显可以分解成子问题的解。

分别求s[0..i]作为第一个字符串,如果是palindrome,则解为s[0..i] + partition(s[i+1…end])

  1. public List<List<String>> partition(String s) {
  2. List<List<String>> rt = new ArrayList<List<String>>();
  3. if ("".equals(s)) {
  4. return rt;
  5. }
  6. if (s.length() == 1) {
  7. rt.add(Arrays.asList(s));
  8. return rt;
  9. }
  10. for (int i = 0; i < s.length(); i++) {
  11. String x = s.substring(0, i + 1);
  12. List<List<String>> sub = new ArrayList<List<String>>();
  13. if (isPal(x)) {
  14. sub = partition(s.substring(i + 1));
  15. if (sub.isEmpty()) {
  16. rt.add(Arrays.asList(x));
  17. } else {
  18. for (List<String> l : sub) {
  19. List<String> _l = new ArrayList<String>();
  20. _l.add(x);
  21. _l.addAll(l);
  22. rt.add(_l);
  23. }
  24. }
  25. }
  26. }
  27. return rt;
  28. }
  29. static boolean isPal(String s) {
  30. int st = 0, ed = s.length() - 1;
  31. while (st < ed) {
  32. if (s.charAt(st++) != s.charAt(ed--)) {
  33. return false;
  34. }
  35. }
  36. return true;
  37. }

Permutation Sequence

The set [1,2,3,…,_n_] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, 
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.


首先想到的是递归,按照顺序寻找字符串,然后计数,计算到第k个就是所求字符串。但是这样太慢,在n=9,k很大时会超时。

然后根据规律来,我们发现当n=3时排列是3! = 6组,其中以“1”,“2”,“3”开头的分别有2组。

以“1”开头的排列中,第2位是“2”、“3”的分别有1组。

如果n=4呢?会发现以1开头的排列有6组,其中以2为第2位的排列有2组。

总结规律:第一位数字在数组中的序号肯定是:

k1/(n−1)!

k1=k

第二位数字在剩余数组中的序号肯定是:

k2/(n−2)!

k2=k1

  1. public String getPermutation(int n, int k) {
  2. if (n <= 0 || k <= 0) {
  3. return "";
  4. }
  5. String rt = "";
  6. List<Integer> list = new ArrayList<Integer>();
  7. int fact = 1;
  8. for (int i = 1; i <= n; i++) {
  9. list.add(i);
  10. fact *= i;
  11. }
  12. k--;
  13. for (int i = 0; i < n; i++) {
  14. fact /= (n - i);
  15. int index = k / fact;
  16. rt += list.get(index);
  17. list.remove(index);
  18. k %= fact;
  19. }
  20. return rt;
  21. }

Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2], and [3,2,1].


这里写图片描述

  1. public List<List<Integer>> permute(int[] nums) {
  2. if (nums == null || nums.length == 0) {
  3. return new ArrayList<List<Integer>>();
  4. }
  5. ArrayList<List<Integer>> rt = new ArrayList<List<Integer>>();
  6. if (nums.length == 1) {
  7. rt.add(new ArrayList<Integer>(Arrays.asList(nums[0])));
  8. } else {
  9. for (int i = 0; i < nums.length; i++) {
  10. for (List<Integer> l : permute(resetof(nums, i))) {
  11. l.add(nums[i]);
  12. rt.add(l);
  13. }
  14. }
  15. }
  16. return rt;
  17. }
  18. private int[] resetof(int[] nums, int index) {
  19. int[] rt = new int[nums.length - 1];
  20. int s = 0;
  21. for (int i = 0; i < nums.length; i++) {
  22. if (i != index) {
  23. rt[s++] = nums[i];
  24. }
  25. }
  26. return rt;
  27. }

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2][1,2,1], and [2,1,1].


使用LeetCode 046 Permutations的方法,只是把rt变成Set,最后转成List,但是会超时。

参考自:http://leetcode.tgic.me/permutations-ii/index.html

  1. void swap(int x[], int a, int b) {
  2. int t = x[a];
  3. x[a] = x[b];
  4. x[b] = t;
  5. }
  6. public boolean nextPermutation(int[] num) {
  7. if (num.length < 2)
  8. return false;
  9. int p = -1;
  10. for (int i = num.length - 1; i > 0; i--) {
  11. if (num[i] > num[i - 1]) {
  12. p = i - 1;
  13. break;
  14. }
  15. }
  16. if (p == -1) {
  17. Arrays.sort(num);
  18. return false;
  19. }
  20. int c = -1;
  21. for (int i = num.length - 1; i >= 0; i--) {
  22. if (num[i] > num[p]) {
  23. c = i;
  24. break;
  25. }
  26. }
  27. swap(num, p, c);
  28. Arrays.sort(num, p + 1, num.length);
  29. return true;
  30. }
  31. List<Integer> asList(int[] num) {
  32. ArrayList<Integer> l = new ArrayList<Integer>(num.length);
  33. for (int i = 0; i < num.length; i++)
  34. l.add(num[i]);
  35. return l;
  36. }
  37. public List<List<Integer>> permuteUnique(int[] num) {
  38. Arrays.sort(num);
  39. ArrayList<List<Integer>> found = new ArrayList<List<Integer>>();
  40. found.add(asList(num));
  41. while (nextPermutation(num)) {
  42. found.add(asList(num));
  43. }
  44. return found;
  45. }

Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: 
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)


  1. List<String> rt = new ArrayList<String>();
  2. String[] stack = new String[4];
  3. public List<String> restoreIpAddresses(String s) {
  4. if (s == null || s.length() == 0) {
  5. return new ArrayList<String>();
  6. }
  7. dfs(s, 0, 0);
  8. return rt;
  9. }
  10. /**
  11. *
  12. * @param s
  13. * @param p
  14. * :指针
  15. * @param pstack
  16. * :stack的下标
  17. */
  18. public void dfs(String s, int p, int pstack) {
  19. if (pstack == 4) {
  20. // 如果stack长度为4,且s的字符全部用上
  21. // 则stack[0...3]存了一个结果
  22. if (p >= s.length()) {
  23. String ip = String.join(".", stack);
  24. rt.add(ip);
  25. }
  26. return;
  27. }
  28. // 获取1~3个字符
  29. for (int i = 1; i <= 3; i++) {
  30. // 如果超过字符串长度,返回
  31. if (p + i > s.length()) {
  32. return;
  33. }
  34. // 若选取的第一个字符是0,则停止选取
  35. if (i > 1 && s.charAt(p) == '0') {
  36. continue;
  37. }
  38. String number = s.substring(p, p + i);
  39. // 如果number<=255,递归
  40. if (Integer.parseInt(number) <= 255) {
  41. stack[pstack] = number;
  42. dfs(s, p + i, pstack + 1);
  43. }
  44. }
  45. }

Subsets

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

Note:

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

  1. [
  2. [3],
  3. [1],
  4. [2],
  5. [1,2,3],
  6. [1,3],
  7. [2,3],
  8. [1,2],
  9. []
  10. ]

  1. int target;// 次数
  2. Integer[] stack;// 存储每次排列
  3. List<List<Integer>> rt;// 存储结果
  4. public void search(int p, int[] nums) {
  5. // 若长度为k,则stack是其中一个结果,保存结果
  6. if (p == target) {
  7. rt.add(new ArrayList<Integer>(Arrays.asList(stack)));
  8. return;
  9. }
  10. for (int i = 0; i < nums.length; i++) {
  11. if (p > 0 && nums[i] <= stack[p - 1]) {
  12. continue;
  13. }
  14. stack[p] = nums[i];
  15. search(p + 1, nums);
  16. }
  17. }
  18. public List<List<Integer>> subsets(int[] nums) {
  19. Arrays.sort(nums);
  20. rt = new ArrayList<List<Integer>>();
  21. // 分别做0~num.length长度的组合
  22. for (int i = 0; i <= nums.length; i++) {
  23. target = i;
  24. stack = new Integer[i];
  25. search(0, nums);
  26. }
  27. return rt;
  28. }

Subsets II

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

Note:

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

  1. [
  2. [2],
  3. [1],
  4. [1,2,2],
  5. [2,2],
  6. [1,2],
  7. []
  8. ]

使用二进制,不需要递归。对于二进制中的每一位,0表示不选择,1表示选择。则有2^n种情况。

使用HashSet,能够直接过滤重复情况(先对数组排序,题目中也要求每个list非降序排列)。

  1. public List<List<Integer>> subsetsWithDup(int[] nums) {
  2. if (nums == null) {
  3. return null;
  4. }
  5. if (nums.length == 0) {
  6. return new ArrayList<List<Integer>>();
  7. }
  8. Set<List<Integer>> set = new HashSet<List<Integer>>();
  9. // 题目中要求每个list是非降序,所以要先从小到大排序
  10. Arrays.sort(nums);
  11. // 对于n位,有2^n种情况
  12. for (int i = 0; i < Math.pow(2, nums.length); i++) {
  13. List<Integer> list = new ArrayList<Integer>();
  14. int tmp = i;
  15. // 对于每种情况,分别求得二进制中1的个数
  16. // 0代表不选择,1代表选择
  17. for (int j = 0; j < nums.length; j++) {
  18. int bit = tmp & 1;
  19. tmp >>= 1;
  20. if (bit == 1) {
  21. list.add(nums[j]);
  22. }
  23. }
  24. set.add(list);
  25. }
  26. return new ArrayList<List<Integer>>(set);
  27. }

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 =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

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


典型问题,回溯法(深度优先搜索DFS),暴力破解。以每一个字符为起点,分别判断上下左右四个字符是否符合条件。符合条件则一直向下寻找,否则回退。

  1. public boolean exist(char[][] board, String word) {
  2. if (board == null || board[0].length == 0 || board.length == 0
  3. || word == null) {
  4. return false;
  5. }
  6. int rows = board.length;
  7. int cols = board[0].length;
  8. boolean[] visited = new boolean[rows * cols];
  9. int pathLength = 0;
  10. for (int row = 0; row < rows; row++) {
  11. for (int col = 0; col < cols; col++) {
  12. // 以row,col为开始,能够遍历得到结果
  13. if (dfs(board, rows, cols, row, col, word, pathLength, visited)) {
  14. return true;
  15. }
  16. }
  17. }
  18. return false;
  19. }
  20. public boolean dfs(char[][] board, int rows, int cols, int row, int col,
  21. String word, int pathLength, boolean[] visited) {
  22. // 如果pathLength的长度已经是查找字串的长度,则已经找到
  23. if (pathLength == word.length()) {
  24. return true;
  25. }
  26. boolean hasPath = false;
  27. // 符合条件的情况下:
  28. // 1. 行、列均在矩阵范围内
  29. // 2. board[row][col]是所要找的字符
  30. // 3. board[row][col]没有遍历过
  31. if (row >= 0 && row < rows && col >= 0 && col < cols
  32. && board[row][col] == word.charAt(pathLength)
  33. && !visited[row * cols + col]) {
  34. pathLength++;
  35. visited[row * cols + col] = true;
  36. hasPath = dfs(board, rows, cols, row, col - 1, word, pathLength,
  37. visited)
  38. || dfs(board, rows, cols, row - 1, col, word, pathLength,
  39. visited)
  40. || dfs(board, rows, cols, row, col + 1, word, pathLength,
  41. visited)
  42. || dfs(board, rows, cols, row + 1, col, word, pathLength,
  43. visited);
  44. // 若board[row][col]的前后左右没有满足条件的字符,则回退
  45. if (!hasPath) {
  46. pathLength--;
  47. visited[row * cols + col] = false;
  48. }
  49. }
  50. return hasPath;
  51. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注