mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 09:23:19 +08:00
7.9 KiB
7.9 KiB
| title | type | weight |
|---|---|---|
| 2.08 ✅ Backtracking | docs | 8 |
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. | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity | Favorite | Acceptance |
|---|---|---|---|---|---|---|---|
| 0017 | Letter Combinations of a Phone Number | [Go]({{< relref "/ChapterFour/0001~0099/0017.Letter-Combinations-of-a-Phone-Number.md" >}}) | Medium | O(log n) | O(1) | 52.0% | |
| 0022 | Generate Parentheses | [Go]({{< relref "/ChapterFour/0001~0099/0022.Generate-Parentheses.md" >}}) | Medium | O(log n) | O(1) | 68.4% | |
| 0037 | Sudoku Solver | [Go]({{< relref "/ChapterFour/0001~0099/0037.Sudoku-Solver.md" >}}) | Hard | O(n^2) | O(n^2) | ❤️ | 51.6% |
| 0039 | Combination Sum | [Go]({{< relref "/ChapterFour/0001~0099/0039.Combination-Sum.md" >}}) | Medium | O(n log n) | O(n) | 62.6% | |
| 0040 | Combination Sum II | [Go]({{< relref "/ChapterFour/0001~0099/0040.Combination-Sum-II.md" >}}) | Medium | O(n log n) | O(n) | 51.6% | |
| 0046 | Permutations | [Go]({{< relref "/ChapterFour/0001~0099/0046.Permutations.md" >}}) | Medium | O(n) | O(n) | ❤️ | 70.0% |
| 0047 | Permutations II | [Go]({{< relref "/ChapterFour/0001~0099/0047.Permutations-II.md" >}}) | Medium | O(n^2) | O(n) | ❤️ | 52.2% |
| 0051 | N-Queens | [Go]({{< relref "/ChapterFour/0001~0099/0051.N-Queens.md" >}}) | Hard | O(n!) | O(n) | ❤️ | 54.6% |
| 0052 | N-Queens II | [Go]({{< relref "/ChapterFour/0001~0099/0052.N-Queens-II.md" >}}) | Hard | O(n!) | O(n) | ❤️ | 64.3% |
| 0077 | Combinations | [Go]({{< relref "/ChapterFour/0001~0099/0077.Combinations.md" >}}) | Medium | O(n) | O(n) | ❤️ | 61.1% |
| 0078 | Subsets | [Go]({{< relref "/ChapterFour/0001~0099/0078.Subsets.md" >}}) | Medium | O(n^2) | O(n) | ❤️ | 68.5% |
| 0079 | Word Search | [Go]({{< relref "/ChapterFour/0001~0099/0079.Word-Search.md" >}}) | Medium | O(n^2) | O(n^2) | ❤️ | 38.9% |
| 0089 | Gray Code | [Go]({{< relref "/ChapterFour/0001~0099/0089.Gray-Code.md" >}}) | Medium | O(n) | O(1) | 54.2% | |
| 0090 | Subsets II | [Go]({{< relref "/ChapterFour/0001~0099/0090.Subsets-II.md" >}}) | Medium | O(n^2) | O(n) | ❤️ | 51.5% |
| 0093 | Restore IP Addresses | [Go]({{< relref "/ChapterFour/0001~0099/0093.Restore-IP-Addresses.md" >}}) | Medium | O(n) | O(n) | ❤️ | 40.0% |
| 0095 | Unique Binary Search Trees II | [Go]({{< relref "/ChapterFour/0001~0099/0095.Unique-Binary-Search-Trees-II.md" >}}) | Medium | 47.4% | |||
| 0113 | Path Sum II | [Go]({{< relref "/ChapterFour/0100~0199/0113.Path-Sum-II.md" >}}) | Medium | 52.4% | |||
| 0126 | Word Ladder II | [Go]({{< relref "/ChapterFour/0100~0199/0126.Word-Ladder-II.md" >}}) | Hard | O(n) | O(n^2) | ❤️ | 25.9% |
| 0131 | Palindrome Partitioning | [Go]({{< relref "/ChapterFour/0100~0199/0131.Palindrome-Partitioning.md" >}}) | Medium | O(n) | O(n^2) | ❤️ | 55.9% |
| 0212 | Word Search II | [Go]({{< relref "/ChapterFour/0200~0299/0212.Word-Search-II.md" >}}) | Hard | O(n^2) | O(n^2) | ❤️ | 38.4% |
| 0216 | Combination Sum III | [Go]({{< relref "/ChapterFour/0200~0299/0216.Combination-Sum-III.md" >}}) | Medium | O(n) | O(1) | ❤️ | 62.6% |
| 0301 | Remove Invalid Parentheses | [Go]({{< relref "/ChapterFour/0300~0399/0301.Remove-Invalid-Parentheses.md" >}}) | Hard | 46.0% | |||
| 0306 | Additive Number | [Go]({{< relref "/ChapterFour/0300~0399/0306.Additive-Number.md" >}}) | Medium | O(n^2) | O(1) | ❤️ | 30.1% |
| 0357 | Count Numbers with Unique Digits | [Go]({{< relref "/ChapterFour/0300~0399/0357.Count-Numbers-with-Unique-Digits.md" >}}) | Medium | O(1) | O(1) | 49.9% | |
| 0401 | Binary Watch | [Go]({{< relref "/ChapterFour/0400~0499/0401.Binary-Watch.md" >}}) | Easy | O(1) | O(1) | 49.7% | |
| 0473 | Matchsticks to Square | [Go]({{< relref "/ChapterFour/0400~0499/0473.Matchsticks-to-Square.md" >}}) | Medium | 40.2% | |||
| 0491 | Increasing Subsequences | [Go]({{< relref "/ChapterFour/0400~0499/0491.Increasing-Subsequences.md" >}}) | Medium | 49.6% | |||
| 0494 | Target Sum | [Go]({{< relref "/ChapterFour/0400~0499/0494.Target-Sum.md" >}}) | Medium | 45.3% | |||
| 0526 | Beautiful Arrangement | [Go]({{< relref "/ChapterFour/0500~0599/0526.Beautiful-Arrangement.md" >}}) | Medium | O(n^2) | O(1) | ❤️ | 63.4% |
| 0638 | Shopping Offers | [Go]({{< relref "/ChapterFour/0600~0699/0638.Shopping-Offers.md" >}}) | Medium | 54.1% | |||
| 0784 | Letter Case Permutation | [Go]({{< relref "/ChapterFour/0700~0799/0784.Letter-Case-Permutation.md" >}}) | Medium | O(n) | O(n) | 70.5% | |
| 0816 | Ambiguous Coordinates | [Go]({{< relref "/ChapterFour/0800~0899/0816.Ambiguous-Coordinates.md" >}}) | Medium | 55.7% | |||
| 0842 | Split Array into Fibonacci Sequence | [Go]({{< relref "/ChapterFour/0800~0899/0842.Split-Array-into-Fibonacci-Sequence.md" >}}) | Medium | O(n^2) | O(1) | ❤️ | 37.4% |
| 0980 | Unique Paths III | [Go]({{< relref "/ChapterFour/0900~0999/0980.Unique-Paths-III.md" >}}) | Hard | O(n log n) | O(n) | 79.2% | |
| 0996 | Number of Squareful Arrays | [Go]({{< relref "/ChapterFour/0900~0999/0996.Number-of-Squareful-Arrays.md" >}}) | Hard | O(n log n) | O(n) | 49.0% | |
| 1079 | Letter Tile Possibilities | [Go]({{< relref "/ChapterFour/1000~1099/1079.Letter-Tile-Possibilities.md" >}}) | Medium | O(n^2) | O(1) | ❤️ | 76.2% |
| 1239 | Maximum Length of a Concatenated String with Unique Characters | [Go]({{< relref "/ChapterFour/1200~1299/1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters.md" >}}) | Medium | 50.6% | |||
| 1655 | Distribute Repeating Integers | [Go]({{< relref "/ChapterFour/1600~1699/1655.Distribute-Repeating-Integers.md" >}}) | Hard | 40.5% | |||
| ------------ | ------------------------------------------------------- | ------- | ---------------- | --------------- | ------------- | ------------- | ------------- |