Discover more content...

Discover more content...

Enter some keywords in the search box above, we will do our best to offer you relevant results.

Results

We're sorry!

Sorry about that!

We couldn't find any results for your search. Please try again with another keywords.

LeetCode 分类刷题 —— Backtracking

Backtracking 的 Tips:

  • 排列问题 Permutations。第 46 题,第 47 题。第 60 题,第 526 题,第 996 题。
  • 组合问题 Combination。第 39 题,第 40 题,第 77 题,第 216 题。
  • 排列和组合杂交问题。第 1079 题。
  • N 皇后终极解法(二进制解法)。第 51 题,第 52 题。
  • 数独问题。第 37 题。
  • 四个方向搜索。第 79 题,第 212 题,第 980 题。
  • 子集合问题。第 78 题,第 90 题。
  • Trie。第 208 题,第 211 题。
  • BFS 优化。第 126 题,第 127 题。
  • DFS 模板。(只是一个例子,不对应任何题)
func combinationSum2(candidates []int, target int) [][]int {
	if len(candidates) == 0 {
		return [][]int{}
	}
	c, res := []int{}, [][]int{}
	sort.Ints(candidates)
	findcombinationSum2(candidates, target, 0, c, &res)
	return res
}

func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) {
	if target == 0 {
		b := make([]int, len(c))
		copy(b, c)
		*res = append(*res, b)
		return
	}
	for i := index; i < len(nums); i++ {
		if i > index && nums[i] == nums[i-1] { // 这里是去重的关键逻辑
			continue
		}
		if target >= nums[i] {
			c = append(c, nums[i])
			findcombinationSum2(nums, target-nums[i], i+1, c, res)
			c = c[:len(c)-1]
		}
	}
}
  • BFS 模板。(只是一个例子,不对应任何题)
func updateMatrix_BFS(matrix [][]int) [][]int {
	res := make([][]int, len(matrix))
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return res
	}
	queue := make([][]int, 0)
	for i, _ := range matrix {
		res[i] = make([]int, len(matrix[0]))
		for j, _ := range res[i] {
			if matrix[i][j] == 0 {
				res[i][j] = -1
				queue = append(queue, []int{i, j})
			}
		}
	}
	level := 1
	for len(queue) > 0 {
		size := len(queue)
		for size > 0 {
			size -= 1
			node := queue[0]
			queue = queue[1:]
			i, j := node[0], node[1]
			for _, direction := range [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}} {
				x := i + direction[0]
				y := j + direction[1]
				if x < 0 || x >= len(matrix) || y < 0 || y >= len(matrix[0]) || res[x][y] < 0 || res[x][y] > 0 {
					continue
				}
				res[x][y] = level
				queue = append(queue, []int{x, y})
			}
		}
		level++
	}
	for i, row := range res {
		for j, cell := range row {
			if cell == -1 {
				res[i][j] = 0
			}
		}
	}
	return res
}
Title Solution Difficulty Time Space 收藏
17. Letter Combinations of a Phone Number Go Medium O(log n) O(1)
22. Generate Parentheses Go Medium O(log n) O(1)
37. Sudoku Solver Go Hard O(n^2) O(n^2) ❤️
39. Combination Sum Go Medium O(n log n) O(n)
40. Combination Sum II Go Medium O(n log n) O(n)
46. Permutations Go Medium O(n) O(n) ❤️
47. Permutations II Go Medium O(n^2) O(n) ❤️
51. N-Queens Go Hard O(n^2) O(n) ❤️
52. N-Queens II Go Hard O(n^2) O(n) ❤️
60. Permutation Sequence Go Medium O(n log n) O(1)
77. Combinations Go Medium O(n) O(n) ❤️
78. Subsets Go Medium O(n^2) O(n) ❤️
79. Word Search Go Medium O(n^2) O(n^2) ❤️
89. Gray Codes Go Medium O(n) O(1)
90. Subsets II Go Medium O(n^2) O(n) ❤️
93. Restore IP Addresses Go Medium O(n) O(n) ❤️
126. Word Ladder II Go Hard O(n) O(n^2) ❤️
131. Palindrome Partitioning Go Medium O(n) O(n^2) ❤️
211. Add and Search Word - Data structure design Go Medium O(n) O(n) ❤️
212. Word Search II Go Hard O(n^2) O(n^2) ❤️
216. Combination Sum III Go Medium O(n) O(1) ❤️
306. Additive Number Go Medium O(n^2) O(1) ❤️
357. Count Numbers with Unique Digits Go Medium O(1) O(1)
401. Binary Watch Go Easy O(1) O(1)
526. Beautiful Arrangement Go Medium O(n^2) O(1) ❤️
784. Letter Case Permutation Go Easy O(n) O(n)
842. Split Array into Fibonacci Sequence Go Medium O(n^2) O(1) ❤️
980. Unique Paths III Go Hard O(n log n) O(n)
996. Number of Squareful Arrays Go Hard O(n log n) O(n)
1079. Letter Tile Possibilities Go Medium O(n^2) O(1) ❤️