2.08 ✅ Backtracking

Backtracking #

  • 排列问题 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
}
No.TitleSolutionDifficultyTimeComplexitySpaceComplexityFavoriteAcceptance
0017Letter Combinations of a Phone NumberGoMediumO(log n)O(1)56.6%
0022Generate ParenthesesGoMediumO(log n)O(1)72.5%
0037Sudoku SolverGoHardO(n^2)O(n^2)❤️57.7%
0039Combination SumGoMediumO(n log n)O(n)68.6%
0040Combination Sum IIGoMediumO(n log n)O(n)53.4%
0046PermutationsGoMediumO(n)O(n)❤️75.7%
0047Permutations IIGoMediumO(n^2)O(n)❤️57.4%
0051N-QueensGoHardO(n!)O(n)❤️64.2%
0052N-Queens IIGoHardO(n!)O(n)❤️71.6%
0077CombinationsGoMediumO(n)O(n)❤️67.0%
0078SubsetsGoMediumO(n^2)O(n)❤️74.9%
0079Word SearchGoMediumO(n^2)O(n^2)❤️40.2%
0089Gray CodeGoMediumO(n)O(1)57.2%
0090Subsets IIGoMediumO(n^2)O(n)❤️55.9%
0093Restore IP AddressesGoMediumO(n)O(n)❤️47.4%
0095Unique Binary Search Trees IIGoMedium52.4%
0113Path Sum IIGoMedium57.1%
0126Word Ladder IIGoHardO(n)O(n^2)❤️27.5%
0131Palindrome PartitioningGoMediumO(n)O(n^2)❤️64.9%
0212Word Search IIGoHardO(n^2)O(n^2)❤️36.4%
0216Combination Sum IIIGoMediumO(n)O(1)❤️67.6%
0257Binary Tree PathsGoEasy61.4%
0301Remove Invalid ParenthesesGoHard47.2%
0306Additive NumberGoMediumO(n^2)O(1)❤️31.1%
0357Count Numbers with Unique DigitsGoMediumO(1)O(1)51.9%
0401Binary WatchGoEasyO(1)O(1)52.3%
0473Matchsticks to SquareGoMedium40.2%
0491Non-decreasing SubsequencesGoMedium60.2%
0494Target SumGoMedium45.7%
0526Beautiful ArrangementGoMediumO(n^2)O(1)❤️64.4%
0638Shopping OffersGoMedium53.3%
0784Letter Case PermutationGoMediumO(n)O(n)73.8%
0816Ambiguous CoordinatesGoMedium56.4%
0842Split Array into Fibonacci SequenceGoMediumO(n^2)O(1)❤️38.4%
0980Unique Paths IIIGoHardO(n log n)O(n)81.7%
0996Number of Squareful ArraysGoHardO(n log n)O(n)49.2%
1079Letter Tile PossibilitiesGoMediumO(n^2)O(1)❤️76.0%
1239Maximum Length of a Concatenated String with Unique CharactersGoMedium52.2%
1655Distribute Repeating IntegersGoHard39.3%
——————————————————————-——-—————-—————————-————-————-

⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者