声明：本文题解所有代码都是本人编写，但由于本人能力有限，故解题思路大多参考和阅读他人文档，如果本文有侵权行为，请及时联系我删除。
特别感谢labuladong(东哥)，本文很多思路都是参考他的文档，如果想要了解更多，请访问labuladong的算法笔记。
本文汇总了本人刷hot100的所有题解和心得包括源代码。
本文会持续更新，直到刷完hot100。
两数之和
这道题还是很简单的，有多种解法。
解法：
- 暴力解法，两层for循环，时间复杂度O(n^2)，空间复杂度O(1)
- 哈希表，时间复杂度O(n)，空间复杂度O(n)
- 双指针，时间复杂度O(nlogn)，空间复杂度O(1)
针对这道题，我们可以知道，如果答案存在，那么一定会是某两个数的和，于是我们只需要针对每一个数nums[i]，都尝试在整个数组中寻找target-nums[i]，如果找到了，那么就返回这两个数的索引。
于是问题就变成了，如何快速查找target-nums[i]。
最直接的想法就是针对每一个数都遍历一遍数组（注意需要跳过自己），但是这样时间复杂度是O(n^2)，显然不合适。
于是我们想到了哈希表，哈希表的查找时间复杂度是O(1)，所以我们可以将数组中的每一个数都存入哈希表中，然后针对每一个数nums[i]，都查找哈希表中是否存在target-nums[i]，如果存在，那么就返回这两个数的索引。
但是我们如何在哈希表做法中跳过当前已经选择的元素呢？
答案是，我们可以以每个元素为key其索引为value，每次找到了target-nums[i]的时候就检查一下索引是否和当前选择的元素的索引相同即可。这样也方便返回索引。
如果你不想这么麻烦的排除重复使用一个元素的情况，那么就可以使用双指针做法。
双指针做法的思路是，首先将数组排序，然后使用两个指针，一个指向数组的开头，一个指向数组的末尾，然后每次比较两个指针指向的元素的和是否等于target，如果等于，那么就返回这两个元素的索引，如果小于target，那么就移动左指针，如果大于target，那么就移动右指针。
但是这样返回的索引是排序后的索引，而不是原数组的索引，所以需要再遍历一遍数组，找到原数组的索引。
双指针做法的时间复杂度是O(nlogn)，空间复杂度是O(1)。
这里给出哈希表解法的Go代码：
func twoSum(nums []int, target int) []int {
mapIndex := make(map[int]int)
for i, v := range nums {
mapIndex[v] = i
}
ans := make([]int, 2)
for i, num := range nums {
if anst, ok := mapIndex[target-num]; ok {
if anst == i {
continue
}
ans[0] = anst
ans[1] = i
break
}
}
return ans
}
字母异位词分组
首先搞明白什么是字母异位词：字母异位词是指两个字符串，它们包含的字母相同，但是字母的顺序不同。
那么如何判断两个词是字母异味词？很简单，排序！字母异位词排序后是相同的。
于是这道题的思路就很清晰了，我们只需要将每个字符串排序后，然后存入哈希表中，如果哈希表中已经存在这个排序后的字符串，那么就说明这两个字符串是字母异味词，然后将这两个字符串存入同一个列表中。
最后返回哈希表中的所有列表即可。
这里给出Go代码：
import (
"sort"
)
func groupAnagrams(strs []string) [][]string {
var mapp map[string][]string
mapp = make(map[string][]string)
for _, str := range strs {
chars := []rune(str)
sort.Slice(chars, func(i, j int) bool {
return chars[i] < chars[j]
})
strTemp := string(chars)
mapp[strTemp] = append(mapp[strTemp], str)
}
var ans [][]string
for _, val := range mapp {
ans = append(ans, val)
}
return ans
}
最长连续序列
这道题不难，但是它要求在O(n)来实现，所以我就不能简单的排序后遍历一遍，那样时间复杂度是O(nlogn)。
所以思考，如何判断一个数是连续序列的一部分？很简单，如果它-1或者+1在数组中，那么它就是连续序列的一部分。
于是我们可以使用一个哈希表来存储数组中的每一个数，然后遍历数组，对于每一个数，我们都检查它-1和+1是否在哈希表中，如果在，那么就说明这个数是连续序列的一部分。
但是，说到这里，也只说了基础思路，在此基础上如何获得最长序列长度？
想要获得最长序列长度，就要知道有序的序列起始位置在哪，起始位置有什么特点呢？那就是它-1不在数组中。
所以，我们可以遍历数组，对于每一个数，我们都检查它-1是否在哈希表中，如果不在，那么就说明这个数是连续序列的起始位置。
进一步我们可以从起始位置开始，向右遍历，直到遇到一个数+1不在哈希表中，那么就说明这个数是连续序列的结束位置。
然后，我们就可以更新最长序列长度。
这里给出Go代码：
func longestConsecutive(nums []int) int {
set := make(map[int]struct{})
for _, num := range nums {
set[num] = struct{}{}
}
ans := 0
for num := range set {
if _, ok := set[num-1]; ok {
continue
}
ansTmp := 1
for {
if _, ok := set[num+1]; ok {
num++
ansTmp++
} else {
break
}
}
if ansTmp > ans {
ans = ansTmp
}
}
return ans
}
这段代码中有一个需要注意的地方，那就是必须要遍历哈希表，而不是遍历数组，因为数组中可能存在重复的元素，而哈希表中不存在重复的元素，这样就可以避免重复计算，否则你会有一个测试用例过不去。
移动零
这道题也很简单，题目要求将数组中的0移动到数组的末尾，同时保持非零元素的相对顺序。
唯一需要注意的点是要保持顺序，并且不能新开数组。
显而易见的一个思路：遍历数组，直到遇到0，从当前节点向后遍历数组，找到第一个非零元素，然后交换这两个元素。
但是这样的时间复杂度有点高。因为你每次都遍历数组，时间复杂度是O(n^2)。
于是我们可以用双指针来优化。i指向第一个为0的位置，j指向从i开始第一个非零元素的位置。
先移动i，直到遇到0，然后移动j，满足j>i&&nums[j]!=0&&j<len(nums)，然后交换nums[i]和nums[j]。
由于j保存了上次找到的非零元素的位置，所以j不需要每次都从i开始遍历，只需要从j开始寻找即可，所以时间消耗会少。
这里给出Go代码：
func moveZeroes(nums []int) {
i, j := 0, 0
for i < len(nums) {
if nums[i] == 0 {
for j < len(nums) && (j < i || nums[j] == 0) {
j++
}
if j < len(nums) {
nums[i], nums[j] = nums[j], nums[i]
}
}
i++
}
}
盛最多水的容器
这道题的目的是找到两个线段之间可以容纳的最大水量。给定一个长度为n的数组height，height[i]表示第i个线段的高度。我们可以想象成每个线段都是一个容器壁，线段之间可以容纳水。我们的目标是找到两个线段之间可以容纳的最大水量。
这个问题的关键是如何找到这两个线段。我们可以使用双指针的方法，从两端开始向中间移动，计算每次移动时的水量，并记录最大水量。移动的策略是，如果左边的线段高度小于右边的线段高度，则移动左边的指针，反之移动右边的指针。这样可以确保每次移动都有可能找到更大的水量。
你可能会疑惑为什么每次要移动小的那个线段指针？你可以想一下，每次的盛水容量都是由宽度和最小的线段决定的，所以如果移动大的那个线段指针，那么宽度就会减小，而最小线段的高度不会变，也就是说高度不可能变高，只可能变小，而宽度也一定减小，所以如果移动高的线段，结果一定更差。
而如果移动的是较小的那个线段，虽然结果不一定会变大，但是至少有概率变大。
这里给出Go代码：
func maxArea(height []int) int {
i, j := 0, len(height)-1
ans := 0
for i < j {
width := j - i
high := min(height[i], height[j])
if width*high > ans {
ans = width * high
}
if height[i] == high {
i++
} else {
j--
}
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
三数之和
这道题其实是二数之和的拓展。
实际上这道题的做法受东哥(labuladong)启发，其思路其实是先排序，对于每一个数，都尝试在后面的数组中寻找和为0-nums[i]的二数之和，如果找到了，那么就返回这三个数。
思路很简单，但是这道题的难点在于去重。本题有多个答案，并且数组中会有重复元素，所以需要在之前的二数之和的基础上进行更新：由于我们这次返回的是数字而非索引，所以我们可以大胆的使用双指针做法，并且双指针更利于去重。具体思路是，在排序好的数组中左右两个指针向中间移动，如果遇到重复元素，那么就跳过。这样就可以保证在二数和部分不会有重复内容。
但是在三数和中还是会重复，例如这个用例：[-1,0,1,2,-1,-4]，排序后是[-4,-1,-1,0,1,2]。当选择的第一个数是-1的时候，去找和为1的二数和，得到的结果是[2,-1]和[0,1]，最终结果就是[-1,2,-1]和[-1,0,1]，但是如果后面我们选择到了2的话还是会得到[-1,2,-1]这个结果。这就重复了。
如何解决这种重复呢？答案很简单每次找二数和的时候都只考虑当前数字后面的数组，这是因为如果整个流程按照之前的思路考虑剩下的所有数组的话，那么在选择-1的时候会考虑2，在选择2的时候会考虑-1，而2和-1同时出现的情况之前选择-1的时候就考虑过了，这就会导致重复。为了避免这种重复，我们就从当前数字的后面开始找二数和。
这里给出Go代码：
func threeSum(nums []int) [][]int {
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
fmt.Println(nums)
ans := make([][]int, 0)
for i := 0; i < len(nums); {
numstmp := make([]int, len(nums))
copy(numstmp, nums)
anstwo := twoSum(numstmp[i+1:], 0-nums[i])
for _, s := range anstwo {
anstmp := make([]int, 3)
anstmp[0] = nums[i]
anstmp[1] = s[0]
anstmp[2] = s[1]
ans = append(ans, anstmp)
}
numtmp := nums[i]
for i < len(nums) && nums[i] == numtmp {
i++
}
}
return ans
}
func twoSum(nums []int, target int) [][]int {
ans := make([][]int, 0)
i, j := 0, len(nums)-1
for i < j {
tmp := nums[i] + nums[j]
if tmp < target {
tmpi := nums[i]
for i < len(nums) && nums[i] == tmpi {
i++
}
} else if tmp > target {
tmpj := nums[j]
for j > 0 && nums[j] == tmpj {
j--
}
} else {
ansTmp := make([]int, 2)
ansTmp[0] = nums[i]
ansTmp[1] = nums[j]
tmpi := nums[i]
for i < len(nums) && nums[i] == tmpi {
i++
}
tmpj := nums[j]
for j > 0 && nums[j] == tmpj {
j--
}
ans = append(ans, ansTmp)
}
}
return ans
}
接雨水
这道题是经典的接雨水问题，题目要求计算一个数组中可以接到的雨水总量。
首先，如果一个地方能解雨水，是不是意味着其两边有比它高的柱子？那么一个格子能接的最大雨水量是否就是其两边最高柱子中较矮的那个减去它的高度？
答案是肯定的，所以我们暴力搜索，对于每一个格子，我们都计算它两边最高的柱子，然后计算它能够接到的雨水量。
但是这样时间复杂度是O(n^2)，显然不合适。
于是，其实可以用一个备忘录来记录每个格子左右最高的柱子，这样时间复杂度就变成了O(n)。
这里给出Go代码：
func trap(height []int) int {
lMax := make([]int, len(height))
rMax := make([]int, len(height))
lMax[0] = height[0]
rMax[len(height)-1] = height[len(height)-1]
for i := 1; i < len(height); i++ {
lMax[i] = max(height[i], lMax[i-1])
}
for i := len(height) - 2; i >= 0; i-- {
rMax[i] = max(height[i], rMax[i+1])
}
ans := 0
for i := 1; i < len(height)-1; i++ {
ans += min(lMax[i], rMax[i]) - height[i]
}
return ans
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
无重复字符的最长子串
这道题是经典的滑动窗口问题，题目要求找到一个字符串中无重复字符的最长子串。
这道题的思路是，使用一个哈希表来记录每个字符出现的次数，然后使用两个指针，一个指向当前子串的开始，一个指向当前子串的结束。
右指针不断向右移动，将新的字符加入哈希表，每加入一个字符，如果哈希表中该字符的值大于1，那么就说明出现了重复字符，此时需要移动左指针，直到哈希表中该字符的值为1为止。
在移动左右指针的过程中，记录当前子串的长度，并更新最大长度。
这里给出Go代码：
func lengthOfLongestSubstring(s string) int {
var max int
var windows = make(map[byte]int)
var left, right int
for right < len(s) {
c := s[right]
right++
windows[c]++
for windows[c] > 1 {
d := s[left]
left++
windows[d]--
}
if right-left > max {
max = right - left
}
}
return max
}
找到字符串中所有字母异位词
这道题也是滑动窗口问题，题目要求找到一个字符串中所有字母异位词。
这道题的思路是，使用两个哈希表，一个记录目标字符串p中每个字符出现的次数，一个记录当前窗口中每个字符出现的次数。
然后使用两个指针，一个指向当前窗口的开始，一个指向当前窗口的结束。
右指针不断向右移动，将新的字符加入窗口哈希表，如果这个字符在目标字符串p中存在，那么就将其加入窗口哈希表，并且如果窗口哈希表中该字符的值等于目标哈希表中该字符的值，那么就说明这个字符已经满足要求，将val加1。
当窗口大小大于目标字符串p的长度时，需要移动左指针，将左指针指向的字符从窗口哈希表中移除，如果这个字符在目标字符串p中存在，那么就需要将其从窗口哈希表中移除，并且如果窗口哈希表中该字符的值等于目标哈希表中该字符的值，那么就说明这个字符不再满足要求，将val减1。
当窗口大小等于目标字符串p的长度，并且val等于目标哈希表的大小时，说明当前窗口中的字符串是目标字符串p的字母异位词，将左指针加入答案数组。
这里给出Go代码：
func findAnagrams(s string, p string) []int {
if len(s) < len(p) {
return nil
}
var needp = make(map[byte]int)
for i := 0; i < len(p); i++ {
needp[p[i]]++
}
ans := make([]int, 0, len(s))
var window = make(map[byte]int)
var left, right, val int
for right < len(s) {
nowChar := s[right]
right++
if needp[nowChar] > 0 {
window[nowChar]++
if window[nowChar] == needp[nowChar] {
val++
}
}
for right-left > len(p) {
nowChar := s[left]
left++
if needp[nowChar] > 0 {
if window[nowChar] == needp[nowChar] {
val--
}
window[nowChar]--
}
}
if len(p) == right-left && val == len(needp) {
ans = append(ans, left)
}
}
return ans
}
和为k的子数组
这道题在本博客的前缀和详解文章中已经详细讲解过了，这里就不再赘述。有需要的可以访问前缀和详解。
滑动窗口最大值
这道题看似是滑动窗口题目，但是却不能用滑动窗口来做。
原因很简单，在当前最大值被移出窗口的时候，你如何找到下一个最大值？难道用遍历的吗？显然不行。
另外一个让人比较容易想到的解法是大顶堆，也就是优先队列，但是这也是不行的，因为窗口移动的时候被移除的元素无法映射到大顶堆里，大顶堆只能出队最大的那个元素。
所以其实这道题的正确解法是单调队列。
单调队列和单调栈是相对应的数据结构，单调队列的队列是双端队列，要求可以从队尾出队。
单调队列的思路是，每次有新元素入队的时候，如果新元素比队尾元素大，那么就从队尾出队，直到队尾元素比新元素大为止。
这样就可以保证队列是单调递减的。
对应到这道题，每次移动窗口要出队的时候，如果队首元素和窗口左边界相等，那么就出队。否则忽略。入队的时候则按照单调队列的规定入队。
这样就可以保证队首始终是还在窗口内的最大值。
这里给出Go代码：
func maxSlidingWindow(nums []int, k int) []int {
i := 0
j := k
q := make([]int, 0)
for l := i; l < j; l++ {
for len(q) > 0 && q[len(q)-1] < nums[l] {
q = q[:len(q)-1]
}
q = append(q, nums[l])
}
i++
j++
max := make([]int, 0)
max = append(max, q[0])
for j <= len(nums) {
for len(q) > 0 && q[len(q)-1] < nums[j-1] {
q = q[:len(q)-1]
}
q = append(q, nums[j-1])
if q[0] == nums[i-1] {
q = q[1:]
}
max = append(max, q[0])
j++
i++
}
return max
}
最小覆盖子串
这道题是滑动窗口问题，题目要求找到一个字符串中包含另一个字符串所有字符的最小子串。
其实和找到字符串中所有字母异位词思路是一样的，都是使用滑动窗口和哈希表来解决。
用一个哈希表存储目标字符串t中每个字符出现的次数，用另一个哈希表存储当前窗口中每个字符出现的次数。
然后使用两个指针，一个指向当前窗口的开始，一个指向当前窗口的结束。
定义一个val变量来表示需要满足多少个字母的需求，当val==needval的时候说明找到了一个满足条件的子串。
下面我们详细说一下滑动窗口的思路:
何时移动右指针？
如果当前窗口内的值不能满足val==needval，那么就移动右指针，直到满足条件为止。
何时移动左指针？
如果当前窗口内的值满足val==needval，那么就移动左指针，直到不满足条件为止。
何时更新答案？
当val==needval的时候，并且左指针再移动一次就无法满足条件的时候，更新答案。
这里给出Go代码：
func minWindow(s string, t string) string {
needMap := make(map[byte]int)
sb := []byte(s)
tb := []byte(t)
needVal := 0
for _, b := range tb {
if _, ok := needMap[b]; !ok {
needVal++
}
needMap[b]++
}
val := 0
nowMap := make(map[byte]int)
var ans string
isAns := false
i, j := 0, 1
for j <= len(sb) {
nowMap[sb[j-1]]++
if need, ok := needMap[sb[j-1]]; ok && need == nowMap[sb[j-1]] {
val++
}
for val == needVal {
if need, ok := needMap[sb[i]]; ok && need == nowMap[sb[i]] {
val--
if j-i < len(ans) || !isAns {
ans = string(sb[i:j])
isAns = true
}
}
nowMap[sb[i]]--
i++
}
j++
}
return ans
}
最大子数组和
我在前缀和详解中写到子数组问题大部分可以用三种算法解决：
- 双指针
- 前缀和+哈希表
- 动态规划
这道题是经典的动态规划问题，题目要求找到一个数组中最大的子数组和。
解决动态规划问题，首先解决状态是什么。也就是dp数组是什么？
一般的思维会认为dp[i]是前i个元素的最大子数组和，但是对于这道题，这样的解法是错误的，因为子数组必须连续，而"前i个元素的最大子数组和"并不一定包含第i个元素，那么如果此时通过状态转移方程，将第i+1个元素加入到dp[i]中，那么就无法保证子数组是连续的。
那么dp[i]应该是什么呢？
dp[i]应该是以第i个元素结尾的最大子数组和。
那么状态转移方程是什么呢？
dp[i] = max(dp[i-1]+nums[i], nums[i])
这里给出Go代码：
func maxSubArray(nums []int) int {
dp := make([]int, len(nums))
dp[0] = nums[0]
max := dp[0]
for i := 1; i < len(nums); i++ {
if dp[i-1] < 0 {
dp[i] = nums[i]
} else {
dp[i] = nums[i] + dp[i-1]
}
if dp[i] > max {
max = dp[i]
}
}
return max
}
合并区间
这道题没有什么算法，其实就是排序+模拟。
首先将区间按照左节点排序，然后从第一个区间开始，判断当前区间的右节点和下一区间的左右节点的关系。
- 当前右节点>=下一个区间的右节点：答案数组中直接跳过下一个区间即可。
- 当前右节点<下一个区间的右节点&&当前右节点>=下一个区间的左节点：答案数组中将当前区间右节点更新为下一个区间右节点。
- 当前右节点<下一个区间的左节点：答案数组中将当前区间加入答案数组，然后更新当前区间为下一个区间。
这里给出Go代码：
import "sort"
func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
for i := 0; i < len(intervals)-1; {
if intervals[i][1] >= intervals[i+1][1] {
if i+2 < len(intervals) {
intervals = append(intervals[:i+1], intervals[i+2:]...)
} else {
intervals = intervals[:len(intervals)-1]
}
} else if intervals[i][1] < intervals[i+1][1] && intervals[i][1] >= intervals[i+1][0] {
intervals[i][1] = intervals[i+1][1]
if i+2 < len(intervals) {
intervals = append(intervals[:i+1], intervals[i+2:]...)
} else {
intervals = intervals[:len(intervals)-1]
}
} else {
i++
}
}
return intervals
}
熟悉Go语言的读者可以发现，这个代码的效率其实很低，因为大量使用append对切片进行删除，而Go语言中用append删除的时候其实是用后续数组覆盖前一个数组，所以很浪费时间。
想详细了解Go语言特性的请移步GoLang语言大揭秘。
这里用一个简单的示例向不熟悉Go语言的读者验证上述观点：
package main
import (
"fmt"
)
func main() {
nums := []int{-1, -100, 3, 99}
nums2 := append(nums[:1], nums[2:]...)
fmt.Println(nums2)
fmt.Println(nums)
}
输出为：
[-1 3 99]
[-1 3 99 99]
可见append操作是浅拷贝，会和之前的被附加的数组共享同一个底层数组，并且其删除是覆盖删除，所以效率很低。
所以这里给出优化后的代码：
import "sort"
func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res := make([][]int, 0)
res = append(res, intervals[0])
for i := 0; i < len(intervals); i++ {
if res[len(res)-1][1] >= intervals[i][1] {
continue
} else if res[len(res)-1][1] >= intervals[i][0] && res[len(res)-1][1] < intervals[i][1] {
res[len(res)-1][1] = intervals[i][1]
} else {
res = append(res, intervals[i])
}
}
return res
}
这份代码使用了新的数组来存储答案，无需用append多次删除元素。
轮转数组
这道题是经典的数组轮转问题，题目要求将一个数组向右轮转k个位置。
其实这道题一个不考虑空间复杂度的方法很简单，那就是先把k%n，然后用一个新数组存储当前数组，然后从n-k开始遍历，将新数组中的元素赋值到当前数组中。
这里给出Go代码：
func rotate(nums []int, k int) {
k = k % len(nums)
nums2 := make([]int, len(nums))
copy(nums2, nums)
i := len(nums) - k
for j := 0; j < len(nums); j++ {
nums[j] = nums2[i%len(nums)]
i++
}
}
奈何本人能力有限，实在没想出空间复杂度为O(1)的解法，故去查看了官方题解。
实际上官方题解从数学的角度思考，对于当前数组中的nums[i]，其轮转后的位置其实是(i+k)%n，为了防止赋值后丢失位于(i+k)%n的元素，需要先保存这个元素，然后赋值，以此类推，最后总会回到nums[0]。
但是实际上回到nums[0]的时候，整个数组中还可能有没有被遍历到的元素，所以可以用一个count存储已经遍历到的元素个数，当count==n的时候，说明整个数组已经遍历完毕，退出循环。
这里给出Go代码：
func rotate(nums []int, k int) {
k = k % len(nums)
j := 0
count := 0
for {
if count == len(nums) {
break
}
i := j
tmp := nums[i]
for {
nums[(i+k)%len(nums)], tmp = tmp, nums[(i+k)%len(nums)]
i = (i + k) % len(nums)
count++
if i == j {
break
}
}
j++
}
}
除自身以外数组的乘积
这道题其实最直接的思路就是每一个都算一遍，但是这样时间复杂度是O(n^2)，显然不行。
又因为这道题不让用除法，所以我们来想为什么直接的思路会很慢？答案是做了很多重复计算。
那我们把重复的计算都用备忘录存下来不就好了吗？是的，这就前缀和的思想。对于这道题用到的其实是前缀乘和后缀乘。
设pre[i]表示nums[0]到nums[i-1]的乘积，bef[i]表示nums[i+1]到nums[n-1]的乘积。
那么答案数组ans[i]就是pre[i]*suf[i]。
注意这道题无需给出整个数组的乘积，所以pre和bef数组只需要开n个元素。
这里给出Go代码：
func productExceptSelf(nums []int) []int {
pre := make([]int, len(nums))
beh := make([]int, len(nums))
pre[0] = 1
beh[len(beh)-1] = 1
for i := 1; i < len(pre); i++ {
pre[i] = pre[i-1] * nums[i-1]
}
for i := len(beh) - 2; i >= 0; i-- {
beh[i] = beh[i+1] * nums[i+1]
}
ans := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
ans[i] = pre[i] * beh[i]
}
return ans
}
缺失的第一个正整数
这道题其实思路很简单。用一个哈希表存下数组中的所有值就可以了。但是题目却要求我们时间复杂度为1。
题目的关键在于想清楚一件事：最终结果的大小在1到n+1之间。为什么呢？因为如果数组中的元素都是1到n的正整数，那么最终结果就是n+1。如果数组中的元素有0或者负数，那么最终结果就是1到n之间的数。是不是清晰多了？
所以这里需要用到原地哈希。
原地哈希的思路是，将数组中的元素放到其应该在的位置上。例如如果nums[i]==1，那么1应该在nums[0]的位置上。依次类推，遇到非正数或者大于n的数，则放到哪里都可以。按照这个思路排布数组，最后遍历数组，找到第一个不满足nums[i]==i+1的数，就是答案。如果所有数都满足，那么答案就是n+1。
这里给出Go代码：
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < len(nums); i++ {
for j := i; nums[j] <= n && nums[j] >= 1 && nums[nums[j]-1] != nums[j]; {
nums[nums[j]-1], nums[j] = nums[j], nums[nums[j]-1]
}
}
ans := 0
for i := 0; i < len(nums); i++ {
if i+1 != nums[i] {
ans = i + 1
break
}
}
if ans == 0 {
ans = n + 1
}
return ans
}
矩阵置零
很简单的题目，用一个二维切片存下所有的0的位置，然后遍历这个切片，将0所在的行和列全部置零。
这里给出Go代码：
func setZeroes(matrix [][]int) {
zero := make([][]int, 0)
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == 0 {
zero = append(zero, []int{i, j})
}
}
}
for _, tmp := range zero {
row := tmp[0]
col := tmp[1]
for i := 0; i < len(matrix[row]); i++ {
matrix[row][i] = 0
}
for j := 0; j < len(matrix); j++ {
matrix[j][col] = 0
}
}
}
螺旋矩阵
其实是一个模拟题，用四个变量表示上下左右边界，然后按照顺时针方向遍历矩阵，每次遍历完一行或一列，就更新边界。
具体思路就是纯粹的模拟。
这里给出Go代码：
func spiralOrder(matrix [][]int) []int {
i, j := 0, 0
n, m := len(matrix), len(matrix[0])
ans := make([]int, n*m)
p := 0
length := n * m
begin1, end1 := 0, n
begin2, end2 := 0, m
for p < length {
for j := begin2; j < end2 && p < length; j++ {
ans[p] = matrix[i][j]
p++
}
j--
i++
for i < end1 && p < length {
ans[p] = matrix[i][j]
i++
p++
}
i--
j--
for j >= begin2 && p < length {
ans[p] = matrix[i][j]
j--
p++
}
j++
i--
for i >= begin1+1 && p < length {
ans[p] = matrix[i][j]
i--
p++
}
begin1++
begin2++
end1--
end2--
}
return ans
}
旋转图像
这道题是一个很灵活的题，能想到就很简单，想不到就很难。
具体思路就是先转置矩阵，然后反转每一行。
这里给出Go代码：
func rotate(matrix [][]int) {
for i := 0; i < len(matrix); i++ {
for j :=i; j < len(matrix[i]); j++ {
matrix[i][j], matrix[j][i]=matrix[j][i], matrix[i][j]
}
}
for i :=0; i < len(matrix); i++ {
l :=0
r :=len(matrix[i]) - 1
for l < r {
matrix[i][l], matrix[i][r]=matrix[i][r], matrix[i][l]
l++
r--
}
}
}
搜索二维矩阵II
这道题的第一思路其实是二分，但是很明显不行。
所以要设计一个高效的遍历思路，因为矩阵给出了一个很好的性质，那就是从左到右，从上到下都是递增的。
所以我们可以从矩阵的右上角开始遍历，如果当前元素大于target，则向左移动，如果当前元素小于target，则向下移动。
这里给出Go代码：
func searchMatrix(matrix [][]int, target int) bool {
i := 0
j := len(matrix[0]) - 1
for i < len(matrix) && i >= 0 && j < len(matrix[0]) && j >= 0 {
if matrix[i][j] < target {
i++
} else if matrix[i][j] > target {
j--
} else {
return true
}
}
return false
}
相交链表
这是一道技巧性的题目，可以思考一下，如果两个链表相交的话，用两个指针从两个链表的头部开始遍历，遇到nil了就从另一个链表的头部开始遍历，这样两个指针会同时到达相交节点。如果切换过一次了还没有相遇，就说明两个链表不相交。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
var p1 *ListNode = headA
var p2 *ListNode = headB
p1Change := false
p2Change := false
for p1 != p2 {
p1 = p1.Next
p2 = p2.Next
if p1 == nil {
if !p1Change {
p1 = headB
p1Change = true
} else {
break
}
}
if p2 == nil {
if !p2Change {
p2 = headA
p2Change = true
} else {
break
}
}
}
if p1 != nil && p2 != nil {
return p1
}
return nil
}
反转链表
这道题不难，可以用多种方式解决，首先是最容易想到的最简单的思路，就是把链表节点存到数组中，然后从后往前遍历数组，组成新的链表。
需要注意的是，在把链表节点存入数组的时候要断开其和其他节点的连接，否则在组成新链表的时候会报错为出现环状链表。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
list:=make([]*ListNode,0)
p:=head
for p!=nil {
next:=p.Next
p.Next=nil
list=append(list,p)
p=next
}
var ans *ListNode = new(ListNode)
p=ans
for i:=len(list)-1;i>=0;i-- {
p.Next=list[i]
p=p.Next
}
return ans.Next
}
还可以用迭代的思路来做，每次要翻转链表的时候只需要改变链表的连接顺序，把原本是next的节点变为pre即可。所以可以通过保存前后节点的方式来把后节点的next变为当前节点，当前节点的next变为pre。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
p := head
var pre *ListNode
var next *ListNode
if p != nil {
next = p.Next
}
for p != nil {
p.Next = pre
pre = p
p = next
if p != nil {
next = p.Next
}
}
return pre
}
回文链表
这道题的思路是找到链表的中间节点，然后反转后半部分链表，最后比较前半部分和后半部分链表是否相等。但是我选择直接存到数组里，然后判断数组是否是回文。因为其实时间复杂度是一样的，都需要完全遍历一遍链表后才能进行判断。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
s := make([]int, 0)
p := head
for p != nil {
s = append(s, p.Val)
p = p.Next
}
i, j := 0, len(s)-1
for i <= j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
环形链表
这道题的思路是使用快慢指针。我们用两个指针p1和p2，初始都指向head。p1每次走一步，p2每次走两步。如果链表中存在环，那么p2一定会追上p1并相遇。因为p2比p1快，所以p2一定会先进入环，然后在环中不断追赶p1，最终相遇。
需要注意的是，在移动指针时要检查p1、p2以及p2.Next是否为nil。因为如果链表中没有环，那么p2最终会到达链表尾部(nil)。只要遇到nil就说明一定无环，此时应该返回false。
如果p1和p2相遇，说明链表中一定存在环，返回true。如果能够跳出循环，说明遇到了nil，也就是链表中不存在环，返回false。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
p1, p2 := head, head
// 只要有nil就无环，无论是p1、p2还是p2的next。
for p1 != nil && p2 != nil && p2.Next != nil {
p1 = p1.Next
p2 = p2.Next.Next
if p1 == p2 {
return true
}
}
return false
}
环形链表II
这道题是环形链表的进阶版，不仅要判断是否有环，还要找到环的入口节点。
这道题的解法很巧妙，分为两步：
- 第一步和环形链表I一样，使用快慢指针判断是否有环，并让两个指针在环中相遇
- 第二步是找到环的入口。当两个指针相遇时，让p1重新指向head，然后p1和p2每次都只走一步，它们相遇的地方就是环的入口
为什么第二步相遇的地方就是环的入口呢？这涉及到一个数学证明：
假设链表头到环入口的距离为a，环入口到相遇点的距离为b，相遇点到环入口的距离为c。那么：
- p1走过的距离：a + b
- p2走过的距离：a + b + n(b + c)，其中n是p2在环中转的圈数
- 由于p2速度是p1的两倍，所以：2(a + b) = a + b + n(b + c)
- 化简得：a = c + (n-1)(b + c)
这个等式说明：从head到环入口的距离，等于从相遇点到环入口的距离加上n-1圈。所以让p1从head开始，p2从相遇点开始，每次走一步，它们一定会在环入口相遇。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
p1,p2:=head,head
ifCycle:=false
for p1!=nil&&p2!=nil&&p2.Next!=nil {
p1=p1.Next
p2=p2.Next.Next
if p1==p2 {
ifCycle=true
break
}
}
if !ifCycle {
return nil
}
p1=head
for p1!=p2 {
p1=p1.Next
p2=p2.Next
}
return p1
}
合并两个有序链表
这道题的思路很简单，就是用两个指针分别指向两个链表，每次比较两个指针指向的节点的值，将较小的节点接到结果链表后面，然后移动对应的指针。
需要注意的是，在将节点接到结果链表后面时，要先断开该节点与原链表的连接，否则会出现环状链表。
最后，如果其中一个链表已经遍历完了，就把另一个链表剩余的部分直接接到结果链表后面即可。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
ans := new(ListNode)
p := ans
p1 := list1
p2 := list2
for p1 != nil && p2 != nil {
if p1.Val < p2.Val {
tmp := p1.Next
p1.Next = nil
p.Next = p1
p = p.Next
p1 = tmp
} else {
tmp := p2.Next
p2.Next = nil
p.Next = p2
p = p.Next
p2 = tmp
}
}
if p1 != nil {
p.Next = p1
} else if p2 != nil {
p.Next = p2
}
return ans.Next
}
两数相加
这道题是一个高精度加法的题目，两个链表分别代表两个逆序的数字，我们需要将这两个数字相加并返回结果链表。
解题思路如下：
- 创建一个新的链表用于存储结果
- 同时遍历两个链表，将对应位置的数字相加
- 需要考虑进位的情况，用一个布尔变量ifAdd记录是否需要进位
- 当其中一个链表遍历完后，需要特殊处理进位的情况：
- 如果还有进位，且其中一个链表还有剩余节点，需要将剩余节点的值都加1并处理可能的连续进位
- 如果还有进位，但两个链表都遍历完了，需要新建一个值为1的节点
- 如果没有进位，直接将剩余链表接上即可
这个解法的关键在于处理进位的传递。当出现连续的9时(比如999)，进位会导致一系列的数字变化，需要一直向后处理直到不再需要进位为止。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
ans := new(ListNode)
p := ans
p1 := l1
p2 := l2
var ifAdd bool
for p1 != nil && p2 != nil {
anstmp := 0
if ifAdd {
anstmp += 1
ifAdd = false
}
tmp := p1.Val + p2.Val
anstmp += tmp
if anstmp/10 != 0 {
ifAdd = true
anstmp %= 10
}
p.Next = new(ListNode)
p = p.Next
p.Val = anstmp
p1 = p1.Next
p2 = p2.Next
}
if ifAdd {
if p1 != nil {
p11 := p1
p11.Val++
for p11.Val/10 != 0 {
if p11.Next == nil {
p11.Val %= 10
p11.Next = new(ListNode)
p11.Next.Val = 1
break
}
p11.Next.Val++
p11.Val %= 10
p11 = p11.Next
}
p.Next = p1
} else if p2 != nil {
p22 := p2
p22.Val++
for p22.Val/10 != 0 {
if p22.Next == nil {
p22.Val %= 10
p22.Next = new(ListNode)
p22.Next.Val = 1
break
}
p22.Next.Val++
p22.Val %= 10
p22 = p22.Next
}
p.Next = p2
} else {
p.Next = new(ListNode)
p = p.Next
p.Val = 1
}
} else {
if p1 != nil {
p.Next = p1
} else if p2 != nil {
p.Next = p2
}
}
return ans.Next
}
删除链表的倒数第N个节点
这道题的思路是使用快慢指针。首先创建一个虚拟头节点dummy指向head，这样可以统一处理删除头节点的情况。然后用pre指向dummy，p1和p2指向head。让p2先走n步，此时p2和p1的距离就是n。然后pre、p1和p2同时向后移动，当p2到达链表尾部(nil)时，p1正好指向要删除的节点，pre指向其前一个节点。最后让pre.Next指向p1.Next完成删除操作。返回dummy.Next即为结果。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dunny := new(ListNode)
dunny.Next = head
pre := dunny
p1 := head
p2 := head
for i := 0; i < n; i++ {
p2 = p2.Next
}
for p2 != nil {
pre = pre.Next
p1 = p1.Next
p2 = p2.Next
}
pre.Next = p1.Next
return dunny.Next
}
两两交换链表中的节点
这道题的思路是先将链表节点存入一个切片中，方便后续操作。然后创建一个虚拟头节点dummy，pre指向dummy。遍历切片，每次取两个节点进行交换：将pre.Next指向第二个节点，第一个节点的Next指向第二个节点的Next，第二个节点的Next指向第一个节点，pre移动到第一个节点。如果最后只剩一个节点则不需要交换。最后返回dummy.Next即为结果。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
q := make([]*ListNode, 0)
p := head
for p != nil {
q = append(q, p)
p = p.Next
}
dunny := new(ListNode)
dunny.Next = head
pre := dunny
for i := 0; i < len(q); i += 2 {
if i == len(q)-1 {
break
}
pre.Next = q[i+1]
q[i].Next = q[i+1].Next
q[i+1].Next = q[i]
pre = q[i]
}
return dunny.Next
}
K个一组翻转链表
这道题的思路是先将链表节点存入一个切片中，方便后续操作。然后创建一个虚拟头节点dummy，pre指向dummy。遍历切片，每次取k个节点进行翻转：将pre.Next指向第k个节点，保存第k个节点的Next，然后从后往前依次将节点的Next指向前一个节点，最后将第一个节点的Next指向保存的next，pre移动到第一个节点。如果剩余节点数小于k则不需要翻转。最后返回dummy.Next即为结果。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
q := make([]*ListNode, 0)
p := head
for p != nil {
q = append(q, p)
p = p.Next
}
dunny := new(ListNode)
dunny.Next = head
pre := dunny
for i := 0; i < len(q); i += k {
if i > len(q)-k {
break
}
pre.Next = q[i+k-1]
next := q[i+k-1].Next
for j := i+k-1; j > i; j-- {
q[j].Next = q[j-1]
}
q[i].Next = next
pre = q[i]
}
return dunny.Next
}
随机链表的复制
这道题的思路是使用哈希表。首先遍历链表，将每个节点及其对应的随机指针存入哈希表中。然后再次遍历链表，根据哈希表中的随机指针创建新节点，并连接到新链表中。最后返回新链表的头节点。
这里给出Go代码：
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
hMap := make(map[*Node]*Node)
p := head
for p != nil {
hMap[p] = new(Node)
hMap[p].Val = p.Val
p = p.Next
}
p = head
for p != nil {
hMap[p].Next = hMap[p.Next]
hMap[p].Random = hMap[p.Random]
p = p.Next
}
return hMap[head]
}
排序链表
这道题的思路是使用归并排序。首先将链表分成两部分，然后对两部分分别进行排序，最后将两部分合并。（注意不能用快排，会超时！！）
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 使用快慢指针找到中点
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 断开链表
mid := slow.Next
slow.Next = nil
// 递归排序左右两半
left := sortList(head)
right := sortList(mid)
// 合并有序链表
dummy := &ListNode{Val: 0}
curr := dummy
for left != nil && right != nil {
if left.Val < right.Val {
curr.Next = left
left = left.Next
} else {
curr.Next = right
right = right.Next
}
curr = curr.Next
}
if left != nil {
curr.Next = left
}
if right != nil {
curr.Next = right
}
return dummy.Next
}
合并 K 个升序链表
这道题的思路是使用优先队列。首先将所有链表的头节点放入优先队列中，然后依次取出队列中的最小节点，将其加入结果链表中，并将其下一个节点放入队列中。重复这个过程直到队列为空。最后返回结果链表的头节点。
没什么难度，但是对于不同语言可能感受不一样，因为C++有线程的优先队列，但是GO需要自己实现对应的接口。
这里给出Go代码：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
import "container/heap"
type PriorityQueue []*ListNode
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].Val < pq[j].Val
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(*ListNode))
}
func (pq *PriorityQueue) Pop() interface{} {
ans := (*pq)[pq.Len()-1]
*pq = (*pq)[0:pq.Len()-1]
return ans
}
func mergeKLists(lists []*ListNode) *ListNode {
pq := &PriorityQueue{}
heap.Init(pq)
for _, head := range lists {
if head != nil {
heap.Push(pq, head)
}
}
dummy := new(ListNode)
p := dummy
for pq.Len() > 0 {
node := heap.Pop(pq).(*ListNode)
p.Next = node
p = p.Next
if node.Next != nil {
heap.Push(pq, node.Next)
}
}
return dummy.Next
}
LRU缓存
首先明确什么是LRU缓存，LRU是Least Recently Used的缩写，即最近最少使用。
LRU缓存是一种缓存机制，它根据数据项的访问时间来决定哪些数据项应该被保留，哪些应该被淘汰。
LRU缓存的核心思想是：如果一个数据项最近被访问过，那么它在未来的访问频率会更高。因此，LRU缓存会优先保留最近被访问的数据项，而淘汰那些很久没有被访问的数据项。
实现LRU缓存其实有最优方法，那就是双向链表+哈希表。其中双向链表用于维护数据项的顺序，哈希表用于快速查找数据项。
具体实现步骤：
- 定义双向链表节点结构体，包含前驱/后继指针和键值对
- 实现双向链表的基本操作：
- push()：在链表尾部插入新节点（最近使用）
- pop()：移除链表头节点（最久未使用）
- changeLRU()：将某个节点移动到链表尾部（更新为最近使用）
- LRUCache结构体包含：
- capacity：缓存容量限制
- listMap：哈希表用于O(1)时间查找节点
- list：双向链表维护使用顺序
- Get操作：
- 通过哈希表快速定位节点
- 将该节点移动到链表尾部
- 返回节点值
- Put操作：
- 若key不存在：
- 容量满时先移除链表头节点
- 创建新节点并插入链表尾部
- 若key存在：
- 更新节点值
- 将节点移动到链表尾部
- 若key不存在：
这里给出Go代码：
type node struct {
key int
val int
next *node
pre *node
}
func newNode(key,val int) *node {
return &node{
key:key,
val:val,
}
}
type doubleList struct {
head *node
tail *node
}
func newDoubleList() *doubleList {
headDunny:=newNode(0,0)
tailDunny:=newNode(0,0)
headDunny.next=tailDunny
tailDunny.pre=headDunny
return &doubleList{
head: headDunny,
tail: tailDunny,
}
}
func (this *doubleList) push(key,val int)*node{
newnode:=newNode(key,val)
this.tail.pre.next=newnode
newnode.pre=this.tail.pre
newnode.next=this.tail
this.tail.pre=newnode
return newnode
}
func (this *doubleList)pop()*node{
delNode:=this.head.next
this.head.next=this.head.next.next
this.head.next.pre=this.head
return delNode
}
func (this *doubleList)changeLRU(nodeP *node){
nodeP.pre.next=nodeP.next
nodeP.next.pre=nodeP.pre
nodeP.next=this.tail
nodeP.pre=this.tail.pre
this.tail.pre.next=nodeP
this.tail.pre=nodeP
}
type LRUCache struct {
capacity int
listMap map[int]*node
list *doubleList
}
func Constructor(capacity int) LRUCache {
mapTmp:=make(map[int]*node)
listTmp:=newDoubleList()
return LRUCache{
capacity: capacity,
listMap: mapTmp,
list: listTmp,
}
}
func (this *LRUCache) Get(key int) int {
nodeP,ok:=this.listMap[key]
if !ok {
return -1
}
this.list.changeLRU(nodeP)
return nodeP.val
}
func (this *LRUCache) Put(key int, value int) {
nodeP,ok:=this.listMap[key]
if !ok {
if len(this.listMap) == this.capacity {
delnode:=this.list.pop()
delete(this.listMap,delnode.key)
}
addnode:=this.list.push(key,value)
this.listMap[key]=addnode
}else {
nodeP.val=value
this.list.changeLRU(nodeP)
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
二叉树的中序遍历
最基础的题目，无需多言，直接给出代码：
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
if root==nil {
return []int{}
}
ans:=make([]int,0)
ans=append(ans,inorderTraversal(root.Left)...)
ans=append(ans,root.Val)
ans=append(ans,inorderTraversal(root.Right)...)
return ans
}
二叉树最大深度
这道题有多种思路，子问题分解可以做，遍历也可以做，这里用遍历来做，无论是哪种遍历都可以。
具体思路是：定义一个遍历函数，每次向下遍历一次都对depth++，如果超过当前最大深度，则更新最大深度，每次返回的时候都depth--，直到最后遍历完成后，就找到了最大深度。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
ans:=0
depth:=0
var findDepth func(*TreeNode)
findDepth=func(root *TreeNode){
depth++
if root==nil {
return
}
if depth>ans{
ans=depth
}
findDepth(root.Left)
depth--
findDepth(root.Right)
depth--
}
findDepth(root)
return ans
}
翻转二叉树
解题思路：
- 采用递归思想，像照镜子一样交换每个节点的左右子树
- 递归终止条件：当前节点为空时返回nil
- 具体步骤：
- 1. 交换当前节点的左右子节点（root.Left和root.Right互换）
- 2. 递归处理左子树（处理后的左子树其实是原来的右子树）
- 3. 递归处理右子树（处理后的右子树其实是原来的左子树）
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root ==nil {
return nil
}
root.Left,root.Right=root.Right,root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
}
对称二叉树
这道题要求一个二叉树的左右两个子树镜像对称，那么我们可以递归的思考这个问题，只要当前节点的左右子节点对称，并且左右子树的子节点也对称，那么这个二叉树就是对称的。所以可以递归判断整个树。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
var check func(left, right *TreeNode) bool
check = func(left, right *TreeNode) bool {
if left == nil || right == nil {
return left == right
}
if left.Val != right.Val {
return false
}
return check(left.Left, right.Right) && check(left.Right, right.Left)
}
if root == nil {
return true
}
return check(root.Left, root.Right)
}
二叉树的直径
这道题的关键在于理解一个树的直径可能不通过根节点。并且计算通过一个节点的直径，其计算方法为左右子树的最大深度之和。
所以其实可以用递归的思想，每次递归都计算当前节点的左右子树的最大深度，然后更新最大直径。但是这种方法的事件发展度太高了。
所以可以用后序遍历的思想，先遍历左右子树，然后计算当前节点的直径，最后更新最大直径。同时，在遍历左右子树的时候，可以顺便计算左右子树的最大深度。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func diameterOfBinaryTree(root *TreeNode) int {
var findAns func(*TreeNode) int
ans:=0
findAns = func(root *TreeNode) int {
if root ==nil {
return 0
}
l:=findAns(root.Left)
r:=findAns(root.Right)
if ansr {
return l+1
}
return r+1
}
findAns(root)
return ans
}
二叉树的层序遍历
这道题的思路是使用广度优先搜索（BFS）。首先将根节点入队，然后依次将队列中的节点出队，并将出队节点的左右子节点入队。重复这个过程直到队列为空。最后返回结果。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
if root==nil {
return [][]int{}
}
q:=make([]*TreeNode,0)
ans:=make([][]int,0)
q=append(q,root)
for len(q)!=0 {
qTmp:=make([]*TreeNode,len(q))
copy(qTmp,q)
q=q[len(q):]
ansTmp:=make([]int,0)
for _,node:=range qTmp{
ansTmp=append(ansTmp,node.Val)
if node.Left!=nil {
q=append(q,node.Left)
}
if node.Right!=nil {
q=append(q,node.Right)
}
}
ans=append(ans,ansTmp)
}
return ans
}
将有序数组转换为二叉搜索树
思路很简单，对于一个有序数组而言，其最中间的元素一定是根节点，然后递归处理左右两部分。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums)==0 {
return nil
}
root:=new(TreeNode)
root.Val=nums[len(nums)/2]
root.Left=sortedArrayToBST(nums[:len(nums)/2])
root.Right=sortedArrayToBST(nums[len(nums)/2+1:])
return root
}
验证二叉搜索树
很简单，一个二叉搜索树是正确的的充要条件就是其中序遍历是递增序列。所以，只需要得到其中序遍历的结果，判断是否为递增序列即可。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
var midTravser func(root *TreeNode)[]int
midTravser = func(root *TreeNode) []int{
if root== nil {
return []int{}
}
ans:=make([]int,0)
ans=append(ans,midTravser(root.Left)...)
ans=append(ans,root.Val)
ans=append(ans,midTravser(root.Right)...)
return ans
}
nums:=midTravser(root)
i,j:=0,1
for j<len(nums){
if nums[j]<=nums[i] {
return false
}
i++
j++
}
return true
}
二叉搜索树中第K小的元素
BST的最重要的性质是什么呢？那就是中序遍历是递增序列。所以，只需要中序遍历，然后返回第k个元素即可。当然可以在遍历到第K个元素的时候终止遍历，可以节约时间。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
num:=0
res:=0
ifFind:=false
var midTravser func(*TreeNode)[]int
midTravser=func(root *TreeNode)[]int {
if root ==nil {
return []int{}
}
ans:=make([]int,0)
ans=append(ans,midTravser(root.Left)...)
if ifFind {
return ans
}
ans=append(ans,root.Val)
num++
if num==k {
res=root.Val
ifFind=true
return ans
}
ans=append(ans,midTravser(root.Right)...)
if ifFind {
return ans
}
return ans
}
midTravser(root)
return res
}
二叉树的右视图
翻译一下题目，题目的意思是返回二叉树每一层最右边的节点。那不就是每一层最后一个节点吗？所以，只需要层序遍历，然后返回每一层最后一个节点即可。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
res := make([]int, 0)
var BFS func(*TreeNode)
BFS = func(root *TreeNode) {
if root == nil {
return
}
q := make([]*TreeNode, 0)
q = append(q, root)
for len(q) != 0 {
tmpQ := make([]*TreeNode, len(q))
copy(tmpQ, q)
q = q[len(q):]
for i := 0; i < len(tmpQ); i++ {
if i == len(tmpQ)-1 {
res = append(res, tmpQ[i].Val)
}
if tmpQ[i].Left != nil {
q = append(q, tmpQ[i].Left)
}
if tmpQ[i].Right != nil {
q = append(q, tmpQ[i].Right)
}
}
}
}
BFS(root)
return res
}
二叉树展开为链表
题目要求按照前序遍历展开，最后全部放到右子树。二叉树的解法无非遍历和子问题分解。这道题很明显是子问题分解，先处理左右子树，左右子树压缩完后，拼接到当前根节点的右子树即可。你完全无需考虑如何转化左右子树，你只需要考虑转化了左右子树后如何转化当前的整棵树。这就是递归的魅力。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func flatten(root *TreeNode) {
if root ==nil {
return
}
flatten(root.Left)
flatten(root.Right)
left:=root.Left
right:=root.Right
root.Left=nil
root.Right=left
p:=root
for p.Right!=nil {
p=p.Right
}
p.Right=right
}
从前序与中序遍历序列构造二叉树
这道题的关键是搞清楚前中后续遍历得到的结果中每一部分和整棵树的关系。对于前序遍历，根节点是第一个元素，后面是左子树前序遍历结果，最后是右子树前序遍历结果。对于中序遍历，前半部分是左子树的遍历结果，中间是根节点，后半部分是右子树的遍历结果。对于后序遍历，前半部分是左子树的遍历结果，后半部分是右子树的遍历结果，最后是根节点。
所以，前序遍历的第一个元素一定是根节点，然后在中序遍历中找到根节点，根节点左边的就是左子树，右边的就是右子树。然后递归处理左右子树。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder)==0 || len(inorder)==0 {
return nil
}
root:=new(TreeNode)
root.Val=preorder[0]
i:=0
for ;i<len(inorder);i++ {
if inorder[i]==preorder[0] {
break
}
}
root.Left=buildTree(preorder[1:i+1],inorder[:i])
root.Right=buildTree(preorder[i+1:],inorder[i+1:])
return root
}
路径总和III
我们知道需要找到的target长度路径可能出现在任何一个地方，所以这道题的第一个难点就是如何求得这个树中任何一段路径的长度。
针对这个问题，我们可以用前缀和的思想，前缀和的作用就是求得一段区间的和，所以我们可以计算并保存从根节点到当前节点的路径和，并且保存根节点到当前路径上所有祖先节点的路径和。当要求一段路径的长度时就只需要对应的前缀和相减即可。
第二个难点是如何快速判断当前路径中是否有子路径等于target，最简单粗暴的方法就是计算每个子路径的和，然后判断是否等于target。但是这种方法的时间复杂度为O(n^2)，所以我们可以用哈希表来优化。我们求出一个前缀和后就以该前缀和为key存入哈希表中，哈希表的value为该前缀和出现的次数。
那么要知道当前路径中是否有子路径等于target，只需要判断当前路径和减去target是否在哈希表中，如果在，则说明当前路径中存在子路径等于target。并且哈希表对应的value就是当前路径中存在多少个等于target的子路径。
第三个难点就是如何维护哈希表：当每次遍历退出当前节点的时候都要将当前节点的前缀和从哈希表中删除，因为当前节点的前缀和已经不再属于当前路径了。
第四个难点就是边界和细节处理，首先要考虑的是遍历到一个新的节点后，是先将当前前缀和存入哈希表，还是先求当前路径和减去target是否在哈希表中？答案是先求当前路径和减去target是否在哈希表中，原因是如果先将当前前缀和加入哈希表，那么就意味着我们允许出现一条没有节点的路径（用当前前缀和减去刚刚存入哈希表的当前前缀和，得到的结果是0，但这个0是因为这个前缀和的差表示的路径中没有节点导致的），而题目要求一个路径必须至少有一个节点。
其次我们考虑一个前缀和刚好是target的情况，这种情况会去哈希表中查找0，但0并不在哈希表中，所以需要特判这种情况。我们选择加一个虚拟头节点，这个节点的val是0，这样就保证了哈希表中一定有0这个key。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) int {
count:=make(map[int64]int)
// 虚拟头节点，处理前缀和刚好等于target的情况
dunny:=new(TreeNode)
dunny.Val=0
dunny.Left=root
return travser(dunny,0,targetSum,count)
}
func travser(root *TreeNode, pathSum int64, targetSum int,count map[int64]int) int {
if root ==nil {
return 0
}
pathSum+=int64(root.Val)
// 先找结果后加入前缀和，避免出现允许空路径的情况
res:=count[pathSum-int64(targetSum)]
count[pathSum]++
res+=travser(root.Left,pathSum,targetSum,count)
res+=travser(root.Right,pathSum,targetSum,count)
count[pathSum]--
return res
}
二叉树的最近公共祖先
LCA是很经典的题目，我们来思考如果一个节点是p和q的公共祖先节点会表现出什么性质？显然，通过这个节点向左子树和右子树遍历总能找到p和q。
那么我们就可以先遍历左右子树，如果左右子树中都能找到p和q，那么当前节点就是LCA。如果只在左子树中找到p和q，那么LCA就在左子树中，反之亦然。
值得注意的是，我们很容易想到如果在子树找到了p或者q那么就返回该节点，这没错。但是如果在左子树中找到了p或者q，就不去右子树遍历，这样是错误的。因为在左子树找到了p或者q中的一个，却不能保证另外一个是在左子树该节点的下方还是在右子树。如果在左子树该节点的下方，则LCA就是该节点，如果在右子树，则LCA就是根节点。所以无论如何都要完全遍历左右子树。
这里给出Go代码：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root==nil {
return nil
}
if root.Val==p.Val||root.Val==q.Val {
return root
}
left:=lowestCommonAncestor(root.Left,p,q)
right:=lowestCommonAncestor(root.Right,p,q)
if left!=nil && right!=nil {
return root
} else if left !=nil {
return left
} else {
return right
}
}
岛屿数量
其实很容易想到就是一个图论问题，遍历每个节点，如果该节点是陆地，则以该节点为起点进行DFS，将遍历到的陆地节点标记为已访问，最后统计遍历的次数即可。
值得一提的是如何遍历这样一个矩阵，实际上我们可以定义一个方向数组，分别表示上下左右四个方向，通过方向数组来遍历当前节点的上下左右。
这里给出Go代码：
func numIslands(grid [][]byte) int {
dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
ans := 0
var ifAdd bool
var dfs func(x, y int)
dfs = func(x, y int) {
if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) {
return
}
if grid[x][y] == '0' {
return
}
if ifAdd == false {
ans++
ifAdd = true
}
grid[x][y] = '0'
for _, dir := range dirs {
dfs(x+dir[0], y+dir[1])
}
}
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
ifAdd = false
if grid[i][j] == '1' {
dfs(i, j)
}
}
}
return ans
}
腐烂的橘子
看似花里胡哨，其实很简单的一道题目。可以把这个题目想象成疾病扩散，每个有病的橘子都会在一秒内向上下左右四个方向传染疾病。注意每一秒内所有在这一秒开始就染病的橘子会在这一秒结束的时候完成传染，等到传无可传的时候，就是这个过程停止，我们要统计结果的时候。
所以我们需要保存所有腐烂橘子的坐标，并且在一秒一秒的遍历中，将腐烂橘子的上下左右四个方向的橘子染病。这里的一秒对应在我们的程序中就是一次循环。每次循环中都让橘子传染，每次新感染的橘子都保存到队列中，直到队列为空，这个过程就结束了。
聪明的读者已经看出来了，这不就是图的BFS吗！
是的，这道题就是图的BFS+一些特殊情况的特判。
这里给出Go代码：
// 定义一个坐标结构体
type point struct {
x int
y int
}
func orangesRotting(grid [][]int) int {
q := make([]point, 0)
// 行列大小
row := len(grid)
col := len(grid[0])
// 遍历grid，将腐烂的橘子加入队列（队列初始化）
for i := range row {
for j := range col {
if grid[i][j] == 2 {
q = append(q, point{
x: i,
y: j,
})
}
}
}
// 方向数组
dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
second := 0
// 特判，如果一开始就没有腐烂的橘子，则直接返回0，不加特判会返回-1
ifNo := false
if len(q) == 0 {
ifNo = true
}
// 开始传染
for len(q) != 0 {
// 取出所有当前要传播疾病的橘子
qtmp := make([]point, len(q))
copy(qtmp, q)
q = q[len(q):]
// 遍历所有要传播疾病的橘子
for _, nowP := range qtmp {
// 遍历四个方向
for _, dir := range dirs {
// 计算新位置
newX := nowP.x + dir[0]
newY := nowP.y + dir[1]
// 如果新位置越界，则跳过
if newX < 0 || newX >= row || newY < 0 || newY >= col {
continue
}
// 如果新位置是新鲜的橘子，则感染该橘子
if grid[newX][newY] == 1 {
grid[newX][newY] = 2
// 将新感染的橘子加入队列
q = append(q, point{
x: newX,
y: newY,
})
}
}
}
// 时间加一秒
second++
}
// 遍历grid，如果还有新鲜的橘子，则返回-1，否则返回时间
for i := range row {
for j := range col {
if grid[i][j] == 1 {
return -1
}
}
}
if ifNo {
return 0
}
// 之所以要-1，是因为最后一次循环中其实没有感染新的橘子，也就是说在倒数第二次循环中所有该被感染的橘子就都被感染了
return second - 1
}
课程表
很简单的题目，根据题意显然可以将课程之间的依赖关系转化为一个有向图，由一个课程指向其依赖的课程。接下来只需要判断这个图中是否有环即可。
有环的判断很简单，对图DFS遍历，维护一个哈希表来表示保存当前遍历的路径，如果一个节点在哈希表中被保存了，则说明在当前路径中这个节点被访问过，说明有环。
所以初始的Go代码：
func canFinish(numCourses int, prerequisites [][]int) bool {
// 建图，邻接表
graph := make([][]int, numCourses)
for i := 0; i < numCourses; i++ {
graph[i] = make([]int, 0)
}
for _, nums := range prerequisites {
graph[nums[0]] = append(graph[nums[0]], nums[1:]...)
}
ifCycle := false
// 保存当前路径
visited := make(map[int]bool)
var travser func(start int)
travser = func(start int) {
if ifCycle {
return
}
// 如果当前节点已经被访问过，则说明有环
if visited[start] {
ifCycle = true
return
}
visited[start] = true
for _, num := range graph[start] {
travser(num)
}
visited[start] = false
}
for i := range numCourses {
travser(i)
}
return !ifCycle
}
但是不幸的是，这个版本的代码超时了！
分析一下为什么超时？其实是在每次从一个节点进入DFS的时候，都会沿着其能访问的节点遍历个遍，但是显然其再遍历过程中访问的节点有可能是之前在其他路径中遍历过的节点。该节点在之前的遍历中都无环，那么这次再从这个节点继续DFS的时候，显然也无环，自然无需重复遍历。
所以我们再开一个哈希表，保存整个全图的遍历过程中访问过的节点，来进行遍历的剪枝即可。
这里给出优化后的代码：
func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
for i := 0; i < numCourses; i++ {
graph[i] = make([]int, 0)
}
for _, nums := range prerequisites {
graph[nums[0]] = append(graph[nums[0]], nums[1:]...)
}
ifCycle := false
// 保存整个全图的遍历过程中访问过的节点
found := make(map[int]bool)
visited := make(map[int]bool)
var travser func(start int)
travser = func(start int) {
if ifCycle {
return
}
if visited[start] {
ifCycle = true
return
}
// 如果当前节点已经被别的DFS遍历过，则无需再次经过这个节点运行DFS
if found[start] {
return
}
// 这个节点被遍历过了，做标记
found[start] = true
visited[start] = true
for _, num := range graph[start] {
travser(num)
}
visited[start] = false
}
for i := range numCourses {
travser(i)
}
return !ifCycle
}
实现Trie（前缀树）
这道题是最基础的前缀树实现。前缀树其实是应用非常广泛的算法，举个例子，Gin框架的路由就是基于压缩前缀树实现的，比用哈希表等方法实现高效了不少。
首先说说前缀树的结构，不同于其他树结构在节点保存数据，前缀树其实是在边保存数据的，每一条边代表一个字符，从根节点到叶子节点的路径代表一个单词。
对于每个节点，也可以保存一些数据，来实现类似hash的效果，这个hash可比直接用map[string]bool高效多了（有公共前缀，空间小很多，但是查找稍微慢一些），而且也更加灵活，可以支持通配符等骚操作，这也就是为什么Gin这种高效框架纷纷使用前缀和做路由。
回到本题，题目没要求实现通配符、删除等操作，只需要实现插入、查找、前缀判断三个操作，并且字符串只会有小写字母组成，非常之简单。
直接给出Go代码看注释即可。
type Trie struct {
// 使用长度为26的数组存储子节点,对应26个小写字母。数组中非空的位置表示存在该字母作为前缀的单词被插入过。
children [26]*Trie
// 如果为true，则表示该节点是一个单词的结束节点。
ifEnd bool
}
func Constructor() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
if len(word)==0 {
// 如果单词为空，则表示该单词已经插入完毕，将ifEnd设置为true，表示这个字符串在这里结尾，无论后续还会不会有子节点插入，这里都表示有一个以当前节点为结尾的字符串。
this.ifEnd=true
return
}
// 递归的插入每个字符。
// 如果曾经插入过，则递归插入下一个字符，否则创建一个新节点并插入下一个字符
if this.children[word[0]-'a'] != nil {
this.children[word[0]-'a'].Insert(word[1:])
} else {
this.children[word[0]-'a']=new(Trie)
this.children[word[0]-'a'].Insert(word[1:])
}
}
func (this *Trie) Search(word string) bool {
// 如果单词为空，则表示这个单词确实能在前缀树中找到但不一定是一个曾经插入的单词，也可能是某个单词的前缀。
// 如果ifEnd为true，则表示有一个曾今插入的单词以当前节点为结尾
// 二者结合，则表示这个单词表示的字符串存在于前缀树中并且确实是一个曾经插入的单词。
if len(word)==0&&this.ifEnd {
return true
} else if len(word)==0 {
return false
}
// 如果当前节点有子节点，则递归查找下一个字符
if this.children[word[0]-'a']!=nil {
return this.children[word[0]-'a'].Search(word[1:])
} else {
// 如果当前节点没有子节点，并且还没有到word的最后一个字符，则说明这个单词不存在，返回false
return false
}
}
func (this *Trie) StartsWith(prefix string) bool {
// 和查找单词一模一样的逻辑，但这里就无需考虑是否是完整的单词了，只要prefix这个字符串确实存在于前缀树中即可。
if len(prefix)==0{
return true
}
if this.children[prefix[0]-'a']!=nil {
return this.children[prefix[0]-'a'].StartsWith(prefix[1:])
} else {
return false
}
}
/**
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/
全排列
本题需要我们返回数组的所有排列可能。我们可以用回溯来做。
回溯，本质是决策树的DFS+剪枝。
既然用回溯来做，那么我们需要先确定这个题目的决策树：
可以看到决策树的每个枝条都代表站在当前节点可以做的一个选择。每个节点都代表当前的决策结果。
所以，我们只需要从根节点开始DFS这棵树，得到每个叶子节点的值，即为答案。
当然在代码里我们不能真的写一个这个树，并且也要增加额外的内容来保存用过的节点。具体请看代码注释。
这里给出Go代码：
func permute(nums []int) [][]int {
// 答案数组
ans := make([][]int, 0)
// 目前进行的决策，也就是选择的数字
path := make([]int, 0)
// 保存用过的数字
useMap := make(map[int]bool)
var travser func()
travser = func() {
// 如果决策数组的长度等于nums的长度，则说明已经做出了所有决策，将决策结果加入答案数组
if len(path) == len(nums) {
tmp := make([]int, len(path), cap(path))
copy(tmp, path)
ans = append(ans, tmp)
}
// 遍历nums，做出决策
for _, num := range nums {
// 如果当前数字已经被使用过，则跳过，这就是剪枝
if useMap[num] {
continue
}
// 做出决策
path = append(path, num)
useMap[num] = true
// 进入下一层，继续决策
travser()
// 回溯
useMap[num] = false
path = path[:len(path)-1]
}
}
travser()
return ans
}
子集
题目要我们找出所有子集，既然如此也就符合回溯的思维。选择用回溯算法解题。
回溯的决策树如下：
可以看到，于全排列不同，决策树的每个节点都代表一个决策结果，每个枝条都代表一个选择。
所以我们每次决策后都要保存答案，包括最开始的时候也要保存。
我们脑海里的决策树是不能直接写到代码里的。毕竟谁没事还写个树？但是我们可以把其决策过程写进去。这道题是子集问题最简单的模板，子集问题和排列问题不同，子集问题的剪枝是要求只能选择上一个选择的数字后的数字。所以实现选择列表的方式也不同。具体请看代码。
这里给出Go代码：
func subsets(nums []int) [][]int {
// 决策结果
path := make([]int, 0)
ans := make([][]int, 0)
var find func(int)
find = func(s int) {
// 保存决策结果
tmp := make([]int, len(path), cap(path))
copy(tmp, path)
ans = append(ans, tmp)
// 通过s来控制选择列表，s是当前决策的起点，也就是选择列表的起点
for i := s; i < len(nums); i++ {
// 做出决策
path = append(path, nums[i])
// 进入下一层，继续决策
find(i + 1)
// 回溯
path = path[:len(path)-1]
}
}
find(0)
return ans
}
电话号码的字母组合
看过前两个回溯题目的题解后，这道题应该很简单了。我们来分析一下：
回溯问题对于每一个节点都要确定三个内容：
- 决策列表
- 已决策内容
- 何时以及如何回溯
针对这道题，决策树的每一层都按顺序对应着题目给定的字符串中的一个数字，每个节点的决策列表就是当前决策层对应的数字对应的字母，已决策内容就是从之前决策列表中选出的字母，回溯则是在决策树后续层的决策都做完后，进行回溯，并选择下一个决策。
这里给出Go代码：
func letterCombinations(digits string) []string {
ans := make([]string, 0)
// 当前决策结果
sb := make([]byte, 0)
var find func(int)
find = func(s int) {
// 如果决策层数等于digits的长度，则说明已经做出了所有决策，将决策结果加入答案数组
if s >= len(digits) {
if len(sb) > 0 {
ans = append(ans, string(sb))
}
return
}
// 获取当前决策层的决策列表
alphas := getAlpha(digits[s])
for _, b := range alphas {
// 做出决策
sb = append(sb, b)
// 进入下一层，继续决策
find(s + 1)
// 回溯
sb = sb[:len(sb)-1]
}
}
find(0)
return ans
}
func getAlpha(num byte) []byte {
switch num {
case '2':
return []byte{'a', 'b', 'c'}
case '3':
return []byte{'d', 'e', 'f'}
case '4':
return []byte{'g', 'h', 'i'}
case '5':
return []byte{'j', 'k', 'l'}
case '6':
return []byte{'m', 'n', 'o'}
case '7':
return []byte{'p', 'q', 'r', 's'}
case '8':
return []byte{'t', 'u', 'v'}
case '9':
return []byte{'w', 'x', 'y', 'z'}
}
return []byte{}
}
组合总和
我们要找到所有可能的组合，使得组合中的数字之和等于target。并且每个数字可以被使用多次。
先想一下如果一个数字不能被使用多次呢？那和我们子集的那道题就一样了，只不过加一个判断是否等于target的条件。
接着我们想一下我们子集那道题是怎么保证一个数字只选一次的？很简单，我们是用了一个start参数保证我们每次决策的起点都和之前的决策不重合。
那我们这道题就将每次Strat的起点设置为上一次决策的数字即可。这样就可以让一个数字多次利用，因为这次决策用了的数字还会出现在下一次决策的决策列表里。
这里给出Go代码：
func combinationSum(candidates []int, target int) [][]int {
ans := make([][]int, 0)
path := make([]int, 0)
pathSum := 0
var find func(int)
find = func(s int) {
// 如果当前决策结果的和等于target，则将决策结果加入答案数组
if pathSum == target {
tmp := make([]int, len(path), cap(path))
copy(tmp, path)
ans = append(ans, tmp)
return
} else if pathSum > target {
// 如果当前决策结果的和大于target，则直接返回
return
}
for i := s; i < len(candidates); i++ {
// 做出决策
path = append(path, candidates[i])
pathSum += candidates[i]
// 进入下一层，继续决策，注意这里i不加1，因为一个数字可以被使用多次
find(i)
// 回溯
path = path[:len(path)-1]
pathSum -= candidates[i]
}
}
find(0)
return ans
}
括号生成
又是一道经典的回溯问题，每一层的决策都是选择“(”或者“)”，所以选择列表不变，已决策内容是当前的括号字符串。当字符串长度等于2n时，判断是否有效，并返回。
这里给出Go代码：
func generateParenthesis(n int) []string {
ans := make([]string, 0)
path := make([]byte, 0)
nowNum := 0
var find func()
find = func() {
// 当决策层数等于2n时，判断是否有效，并返回
if nowNum == 2*n {
if check(path) {
s := string(path)
ans = append(ans, s)
}
return
}
// 遍历决策列表
for i := range 2 {
if i == 0 {
// 做出决策
path = append(path, '(')
nowNum++
// 进入下一层，继续决策
find()
// 回溯
path = path[:len(path)-1]
nowNum--
} else {
// 做出决策
path = append(path, ')')
nowNum++
// 进入下一层，继续决策
find()
// 回溯
path = path[:len(path)-1]
nowNum--
}
}
}
find()
return ans
}
// 判断括号是否有效
func check(bs []byte) bool {
s := make([]byte, 0)
for _, b := range bs {
if b == ')' && len(s) > 0 && s[len(s)-1] == '(' {
s = s[:len(s)-1]
continue
}
s = append(s, b)
}
return len(s) == 0
}
单词搜索
这道题与其说是回溯，不如说是图的DFS。虽然但是其实回溯就是DFS。。。
思路很简单，从矩阵的每个点开始进行DFS，存储其结果，如果DFS的结果和目标单词相同，则返回true。如果DFS的决策结果长度大小大于目标单词的长度，则返回（剪枝）。
这里给出Go代码：
func exist(board [][]byte, word string) bool {
// 定义一个点结构体，用于存储坐标
type point struct {
x int
y int
}
row := len(board)
col := len(board[0])
dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
ans := false
// 定义一个map，用于存储路径中的点
pathMap := make(map[point]bool)
// 定义一个切片，用于存储路径中的点
path := make([]byte, 0)
var find func(int, int)
find = func(x, y int) {
// 如果决策结果的长度等于目标单词的长度，则判断是否相等，并返回
if len(path) == len(word) {
// 如果决策结果和目标单词相等，则返回true
if word == string(path) {
ans = true
}
return
}
// 如果坐标越界，则返回
if x < 0 || x >= row || y < 0 || y >= col {
return
}
nowP := point{
x: x,
y: y,
}
// 如果当前点已经在路径中，则返回
if pathMap[nowP] {
return
} else {
// 如果当前点不在路径中，则将当前点加入路径
pathMap[nowP] = true
}
// 做出决策
path = append(path, board[x][y])
// 遍历决策列表
for _, dir := range dirs {
// 进入下一层，继续决策
find(x+dir[0], y+dir[1])
// 已经确定有了，则提前结束
if ans == true {
return
}
}
// 回溯
path = path[:len(path)-1]
pathMap[nowP] = false
}
// 从矩阵的每个点开始进行DFS
start := word[0]
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if ans {
return ans
}
if board[i][j] != start {
continue
}
find(i, j)
}
}
return ans
}
分割回文串
题目要求返回所有可能的回文串分割方案。
很明显，从同一个位置开始，我们可以找到多个回文串，这就是我们的决策列表，每次决策后，从剩下的字符串中递归的进行决策与回溯。直到，字符串所有的内容都参与了某一次决策，则返回结果。
这里给出Go代码：
func partition(s string) [][]string {
ans := make([][]string, 0)
tmp := make([]string, 0)
var find func(int)
find = func(start int) {
if start >= len(s) {
tmptmp := make([]string, len(tmp), cap(tmp))
copy(tmptmp, tmp)
ans = append(ans, tmptmp)
return
}
for i := start; i <= len(s); i++ {
// 如果当前字符串是回文串，则将当前字符串加入决策结果
if isBackStr(s[start:i]) {
tmp = append(tmp, s[start:i])
// 进入下一层，继续决策
find(i)
// 回溯
tmp = tmp[:len(tmp)-1]
}
}
}
find(0)
return ans
}
func isBackStr(s string) bool {
if len(s) == 0 {
return false
}
a, b := 0, len(s)-1
for a <= b {
if s[a] != s[b] {
return false
}
a++
b--
}
return true
}
N皇后
这道题是回溯的经典问题，我们需要在N*N的棋盘上放置N个皇后，并且每个皇后不能在同一行、同一列、同一对角线上。
我们直到在一行中不能出现多个皇后对吗，所以我们可以一行一行的进行决策，每次决策一个皇后放在哪一列。
于是决策树的每一层就代表决策一行皇后放在哪里，决策列表就是这一行可以放皇后的列。
所以我们在做决策的时候对于决策列表中的每个元素，我们都要判断是否与之前决策的皇后是否冲突。不冲突则做出决策，进入下一层，并在后续决策做完后回溯。
每次决策前都要判断当前决策的行是否超出了棋盘范围，如果超过了则说明找到了答案，保存答案并返回。
这里给出Go代码：
func solveNQueens(n int) [][]string {
ans := make([][]string, 0)
// 棋盘
board := make([][]byte, n)
for i := 0; i < n; i++ {
board[i] = make([]byte, n)
for j := 0; j < n; j++ {
board[i][j] = '.'
}
}
var find func(int)
find = func(row int) {
// 如果超出了棋盘范围，说明找到答案，则保存答案并返回
if row == n {
stmp := make([]string, 0)
for _, byteArray := range board {
sb := string(byteArray)
stmp = append(stmp, sb)
}
ans = append(ans, stmp)
return
}
for i := 0; i < n; i++ {
// 如果当前位置可以放置皇后，则做出决策
if isValid(&board, row, i, n) {
board[row][i] = 'Q'
// 进入下一层，继续决策
find(row + 1)
// 回溯
board[row][i] = '.'
}
}
}
find(0)
return ans
}
// 判断当前位置是否可以放置皇后
func isValid(boardP *[][]byte, row, col, n int) bool {
board := *boardP
for i := 0; i < n; i++ {
if board[row][i] == 'Q' {
return false
}
}
for i := 0; i < n; i++ {
if board[i][col] == 'Q' {
return false
}
}
for i, j := row, col; i >= 0 && j >= 0; {
if board[i][j] == 'Q' {
return false
}
i--
j--
}
for i, j := row, col; i >= 0 && j < n; {
if board[i][j] == 'Q' {
return false
}
i--
j++
}
return true
}