Se7en的架构笔记Hot 100 算法题
二分查找
二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
go
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2:
go
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1题解
经典的二分查找算法，用于在一个升序排列的整数数组 nums 中查找目标值 target 的索引。
- 初始化：设置 left 和 right 指针，分别指向数组的起始和结束位置。
- 循环查找：通过循环不断缩小查找范围，直到找到目标值或者确定目标值不存在。
- 计算中间索引 mid，并与 target 比较。
- 如果 nums[mid] == target，直接返回 mid，表示找到了目标值。
- 如果 nums[mid] > target，说明目标值在左侧，将 right 更新为 mid - 1。
- 否则，目标值在右侧，将 left 更新为 mid + 1。
- 返回结果：如果循环结束时没有找到目标值，返回 -1，表示目标值不在数组中。
go
func search(nums []int, target int) int {
left, right := 0, len(nums) - 1
for left <= right {
mid := left + (right - left) / 2
if nums[mid] == target {
return mid
}
if nums[mid] > target {
right = mid - 1
} else {
left++
}
}
return -1
}搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
go
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4示例 2：
go
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1示例 3：
go
输入：nums = [1], target = 0
输出：-1题解
确定旋转点：
- 数组被旋转后，可能存在两个有序部分。我们可以利用二分查找来找出哪一部分是有序的。
- 在每一步中，我们需要确定当前的 mid 指针所指向的元素，然后判断左半部分和右半部分的有序性。
查找目标值：
- 如果左半部分有序，判断目标值是否在左半部分的范围内（即 nums[left] <= target < nums[mid]）。如果在，缩小搜索范围到左半部分；否则，转向右半部分。
- 如果右半部分有序，判断目标值是否在右半部分的范围内（即 nums[mid] < target <= nums[right]）。如果在，缩小搜索范围到右半部分；否则，转向左半部分。
终止条件：
- 当 left 超过 right 时，表示数组中没有目标值，返回 -1。
go
func search(nums []int, target int) int {
// 初始化左右指针
left, right := 0, len(nums)-1
// 开始二分查找
for left <= right {
// 计算中间位置的索引
mid := left + (right-left)/2
// 如果找到目标值，直接返回其索引
if nums[mid] == target {
return mid
}
// 判断左半部分是否有序
if nums[left] <= nums[mid] {
// 左半部分有序
// 检查目标值是否在左半部分的范围内
if nums[left] <= target && target <= nums[mid] {
// 目标值在左半部分，移动右指针，缩小范围至左半部分
right = mid - 1
} else {
// 目标值不在左半部分，缩小范围至右半部分
left = mid + 1
}
} else {
// 右半部分有序
// 检查目标值是否在右半部分的范围内
if nums[mid] <= target && target <= nums[right] {
// 目标值在右半部分，移动左指针，缩小范围至右半部分
left = mid + 1
} else {
// 目标值不在右半部分，缩小范围至左半部分
right = mid - 1
}
}
}
// 如果遍历完数组仍未找到目标值，返回 -1
return -1
}寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
go
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2示例 2：
go
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5题解
核心思想
递归查找第
k小元素： 我们通过递归的方式，逐步在两个已排序的数组中查找第k小的元素。每次递归时，我们从nums1和nums2中各自选取一部分，比较这部分元素的大小，排除不可能包含第k小元素的部分。如何选择前
i个元素：- 每次递归时，我们需要决定从
nums1中选取多少个元素。我们选择i = min(k / 2, len(nums1))，即从nums1中选取前k / 2个元素（或nums1能提供的最多元素）。 - 然后，从
nums2中选取剩余的k - i个元素。这种划分方式可以有效地平衡两个数组的大小，并通过比较选定的元素来决定接下来递归的搜索范围。
- 每次递归时，我们需要决定从
判断舍弃哪部分：
- 比较
nums1[i-1]和nums2[j-1]（当前划分点的元素）。如果nums1[i-1] < nums2[j-1]，说明nums1[0]到nums1[i-1]这部分元素都比nums2[j-1]小，第 k 个小的元素肯定不在 nums1 中，因此可以舍弃nums1[0]到nums1[i-1]，继续在nums1[i:]和nums2中寻找第k-i小的元素。 - 否则，舍弃
nums2[0]到nums2[j-1]，继续在nums1和nums2[j:]中寻找第k-j小的元素。
- 比较
终止条件
- 当
nums1为空时：如果nums1为空，那么直接返回nums2[k-1]。 - 当
k = 1时：当k = 1时，返回nums1[0]和nums2[0]中较小的那个元素，因为它们是最小的两个元素。
例子解释
假设有两个已排序数组：
go
nums1 = [1, 3, 8]
nums2 = [7, 9, 10, 11]
k = 4初始递归：
i = min(k / 2, len(nums1)) = min(4 / 2, 3) = 2，从nums1中选取前 2 个元素1, 3。- 从
nums2中选取剩下的 2 个元素7, 9。 - 比较
nums1[1] = 3和nums2[1] = 9，因为3 < 9，第 4 小的元素肯定不在 nums1 中，因此我们可以舍弃nums1[0]和nums1[1]，继续在nums1[2:] = [8]和nums2 = [7, 9, 10, 11]中查找第 2 小的元素（因为已经排除了一半，所以接下来是找第 2 小）。
递归查找第 2 小的元素：
- 现在我们要找第 2 小的元素，剩下的部分是：
nums1 = [8]和nums2 = [7, 9, 10, 11]。 - 比较
nums1[0] = 8和nums2[0] = 7，因为7 < 8，舍弃nums2[0] = 7，继续在nums1 = [8]和nums2[1:] = [9, 10, 11]中查找第 1 小的元素。
- 现在我们要找第 2 小的元素，剩下的部分是：
返回结果：
- 现在我们要找第 1 小的元素，直接返回
nums1[0] = 8，即第 4 小的元素。
- 现在我们要找第 1 小的元素，直接返回
go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
total := m + n
if total%2 == 1 {
// 奇数：返回第 (total/2 + 1) 小的数
return float64(findKth(nums1, nums2, total/2+1))
}
// 偶数：返回第 (total/2) 和 (total/2 + 1) 小数的平均值
return float64(findKth(nums1, nums2, total/2)+findKth(nums1, nums2, total/2+1)) / 2
}
// findKth 找到两个排序数组中第 k 小的数
func findKth(nums1, nums2 []int, k int) int {
len1, len2 := len(nums1), len(nums2)
// 确保 nums1 是较短的数组
if len1 > len2 {
return findKth(nums2, nums1, k)
}
// 边界条件
if len1 == 0 {
return nums2[k-1] // 如果 nums1 为空，第 k 小就是 nums2[k-1]
}
if k == 1 {
return min(nums1[0], nums2[0]) // 如果 k 为 1，返回两个数组中最小的数
}
// 划分点
i := min(len1, k/2) // nums1 的划分位置
j := k - i // nums2 的划分位置
if nums1[i-1] < nums2[j-1] {
// nums1[i-1] 比较小，舍弃 nums1[:i]
return findKth(nums1[i:], nums2, k-i)
} else {
// nums2[j-1] 比较小，舍弃 nums2[:j]
return findKth(nums1, nums2[j:], k-j)
}
}
// 辅助函数
func min(a, b int) int {
if a < b {
return a
}
return b
}寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
go
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
go
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。题解
这个问题可以通过二分查找来解决：
- 设当前区间的中间元素为 mid。
- 如果 nums[mid] < nums[mid + 1]，说明在右边可能有一个峰值，因此我们可以在右半部分继续查找。
- 如果 nums[mid] > nums[mid + 1]，说明在左边可能有一个峰值，因此我们可以在左半部分继续查找。
- 这个过程会持续进行，直到 left == right，即搜索区间缩小为一个元素，这个元素就是我们所要找的峰值。
go
func findPeakElement(nums []int) int {
left, right := 0, len(nums)-1
// 使用二分查找
for left < right {
mid := left + (right - left) / 2
// 如果中间元素小于右边的元素，说明峰值在右半部分
if nums[mid] < nums[mid+1] {
left = mid + 1
} else {
// 如果中间元素大于右边的元素，说明峰值在左半部分
right = mid
}
}
return left // left == right 时，已找到峰值的位置
}在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
go
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]示例 2：
go
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]示例 3：
go
输入：nums = [], target = 0
输出：[-1,-1]题解
nums 数组是有序的，只不过可能有连续的数字是相同的。要求设计时间复杂度为 O(log n) 的算法来查找一个目标值 target 在一个已排序的数组 nums 中的开始位置和结束位置，可以利用二分查找来实现。二分查找的时间复杂度是 O(log n)，可以通过两次二分查找来分别找到目标值的起始位置和结束位置。
- 使用二分查找查找 target 的起始位置。通过比较中间元素与目标值的关系，可以决定是向左还是向右搜索。
- 使用二分查找查找 target 的结束位置。方法类似，只是当找到目标值时，我们需要继续往右搜索，直到找到最后一个目标值。
- 如果在两次二分查找中都找到了目标值，那么返回它们的位置；如果没有找到目标值，返回 [-1, -1]。
go
// 查找目标值在数组中的开始和结束位置
func searchRange(nums []int, target int) []int {
first := findFirst(nums, target)
if first == -1 {
return []int{-1, -1} // 如果目标值不存在，返回 [-1, -1]
}
last := findLast(nums, target)
return []int{first, last}
}
// 查找目标值第一次出现的下标
func findFirst(nums []int, target int) int {
left, right := 0, len(nums)-1
result := -1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
result = mid
right = mid - 1 // 继续在左半部分查找
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return result
}
// 查找目标值最后一次出现的下标
func findLast(nums []int, target int) int {
left, right := 0, len(nums)-1
result := -1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
result = mid
left = mid + 1 // 继续在右半部分查找
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return result
}搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。
示例 1：
go
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true示例 2：
go
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false题解
解法一：二维矩阵视为一维数组
go
func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
left, right := 0, m*n-1
for left <= right {
mid := (left + right) / 2
midValue := matrix[mid/n][mid%n] // 转换为二维索引
if midValue == target {
return true
} else if midValue < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}解法二：两层二分查找
外层二分查找确定 target 在哪一行，内层二分查找确定 target 在该行的位置。
go
func searchMatrix(matrix [][]int, target int) bool {
left, right := 0, len(matrix)-1
for left <= right {
mid := left + (right-left)/2
// 检查 target 是否可能存在于第 mid 行
if target < matrix[mid][0] {
right = mid - 1
} else if target > matrix[mid][len(matrix[0])-1] {
left = mid + 1
} else {
// 在第 mid 行中进行二分查找
l, r := 0, len(matrix[0])-1
for l <= r {
m := l + (r-l)/2
if target == matrix[mid][m] {
return true
} else if target < matrix[mid][m] {
r = m - 1
} else {
l = m + 1
}
}
return false
}
}
return false
}搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
go
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true题解
对于这样一个具有双重排序性质的矩阵，可以通过从矩阵的右上角或左下角出发来高效搜索目标值。
比如从矩阵的右上角开始：当前元素是该列的最小值，同时是该行的最大值，便于通过比较缩小搜索范围。
- 如果当前元素等于目标值，返回 true。
- 如果当前元素大于目标值，则向左移动一列。
- 如果当前元素小于目标值，则向下移动一行。
不断重复上述步骤，直到超出矩阵边界，返回 false。
go
func searchMatrix(matrix [][]int, target int) bool {
// 从右上角开始
row, col := 0, len(matrix[0])-1
for row < len(matrix) && col >= 0 {
if matrix[row][col] == target {
return true
} else if matrix[row][col] > target {
col-- // 向左移动
} else {
row++ // 向下移动
}
}
return false
}双指针
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
go
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]示例 2：
go
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]题解
使用两个指针：一个从头开始，另一个从尾部开始，逐步交换这两个指针所指向的字符，直到两个指针相遇。
go
func reverseString(s []byte) {
n := len(s) - 1
for i := 0; i <= n / 2; i++ {
s[i], s[n-i] = s[n-i], s[i]
}
}无重复字符的最长子串
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。题解（滑动窗口 + 哈希表）
- 哈希表
dic统计：指针j遍历字符s，哈希表统计字符s[j]最后一次出现的索引 。 - 更新左指针
i： 根据上轮左指针i和dic[s[j]]，每轮更新左边界i，保证区间[i+1,j]内无重复字符且最大。
go
i=max(dic[s[j]],i)- 更新结果
res： 取上轮res和本轮双指针区间[i+1,j]的宽度（即 j−i）中的最大值。
go
res=max(res,j−i)
go
func lengthOfLongestSubstring(s string) int {
dic := make(map[byte]int)
n := len(s)
res := 0
i := -1
for j := 0; j < n; j++ {
if v, ok := dic[s[j]]; ok {
// 更新滑动窗口的左边界，保证区间 [i+1,j] 内无重复字符
i = max(v, i)
}
dic[s[j]] = j
res = max(res, j-i)
}
return res
}
func max(x, y int) int {
if x > y {
return x
}
return y
}三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
go
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
go
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
go
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。题解（排序 + 双指针）
先对数组排序，设一非递减的数组示例和初始三指针位置及名字如下所示。固定 i，即可转换为寻找满足 nums[l]+nums[r]=−nums[i] 的三元组。
总共 3 个循环，第 1 个循环枚举 i，第 2 个循环枚举 l，l 每次从 i + 1 开始从左往右遍历数组，第 3 个循环枚举 r，r 每次从 n - 1 开始从右往左遍历数组，寻找满足 nums[l]+nums[r]=−nums[i] 的三元组。 第二重循环和第三重循环实际上是并列的关系，因此最终的时间复杂度是 O(n^2)。
还要注意因为不能包含重复的三元组，所以在移动指针的时候，需要规避连续的重复元素。
go
func threeSum(nums []int) [][]int {
n := len(nums)
// 先将数组排序
sort.Ints(nums)
ans := make([][]int, 0)
// 枚举 i
for i := 0; i < n; i++ {
// 需要和上一次枚举的数不相同
if i > 0 && nums[i] == nums[i-1] {
continue
}
// r 对应的指针初始指向数组的最右端
r := n - 1
target := -1 * nums[i]
// 枚举 b
for l := i + 1; l < n; l++ {
// 需要和上一次枚举的数不相同
if l > i+1 && nums[l] == nums[l-1] {
continue
}
// 需要保证 l 的指针在 r 的指针的左侧
for l < r && nums[l]+nums[r] > target {
r--
}
// 如果指针重合，随着 l 后续的增加
// 就不会有满足 i+l+r=0 并且 l<r，可以退出循环
if l == r {
break
}
if nums[l]+nums[r] == target {
ans = append(ans, []int{nums[i], nums[l], nums[r]})
}
}
}
return ans
}合并两个有序数组
给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
go
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。示例 2：
go
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。示例 3：
go
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。题解
原地替换 nums1 数组，初始指针如下图所示，一直向 tail 初赋值，i1 和 i2 指针不断左移。当 nums1[i1] > nums2[i2] 时，令 nums1[tail] = nums1[i1]，i1 左移，反之亦然。
go
func merge(nums1 []int, m int, nums2 []int, n int) {
i1 := m - 1
i2 := n - 1
tail := m + n - 1
for i1 >= 0 || i2 >= 0 {
// nums1 数组已经遍历完成，直接将 nums2 数组的值进行追加
if i1 == -1 {
nums1[tail] = nums2[i2]
i2--
} else if i2 == -1 { // nums2 数组已经遍历完成，直接将 nums1 数组的值进行追加
nums1[tail] = nums1[i1]
i1--
} else if nums1[i1] >= nums2[i2] {
nums1[tail] = nums1[i1]
i1--
} else {
nums1[tail] = nums2[i2]
i2--
}
tail--
}
}接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
go
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：
go
输入：height = [4,2,0,3,2,5]
输出：9题解
左右指针从两端向中间移动，想要正确计算储水量需要知道本端的最高点高度，以及确保对方有一个不低于本端最高点的柱子。 左右两端轮流占领目前遍历到的最高点，当一方占据着全局最高点时。另一方前进，直到遇到了一个比全局最高点更高的点，换另一方前进，循环往复直到 left, right 碰面。可移动的一方每步更新自己这侧的最高点，由于另一方此时占据着全局最高点，所以可以保证另一方有一个不低于本方最高点的柱子，也就确保了当前对储水量的计算是正确的。
go
func trap(height []int) int {
// 如果数组为空，直接返回 0
if len(height) == 0 {
return 0
}
// 初始化左右指针，以及左右两侧的最大高度
left, right := 0, len(height)-1
leftMax, rightMax := 0, 0
// 用于记录总的接水量
totalWater := 0
// 当左右指针没有交错时，继续循环
for left < right {
// 如果左边柱子的高度小于右边柱子的高度
if height[left] < height[right] {
// 如果当前柱子的高度大于等于左侧最大高度，更新左侧最大高度
if height[left] >= leftMax {
leftMax = height[left]
} else {
// 否则，计算当前柱子上方可以接到的雨水
totalWater += leftMax - height[left]
}
// 左指针右移
left++
} else {
// 如果右边柱子的高度小于或等于左边柱子的高度
// 如果当前柱子的高度大于等于右侧最大高度，更新右侧最大高度
if height[right] >= rightMax {
rightMax = height[right]
} else {
// 否则，计算当前柱子上方可以接到的雨水
totalWater += rightMax - height[right]
}
// 右指针左移
right--
}
}
// 返回总的接水量
return totalWater
}移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
go
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
go
输入: nums = [0]
输出: [0]题解
双指针的定义：
- left 指针：指向当前数组中应该填入非零元素的位置。
- right 指针：用于遍历整个数组。
算法步骤：
- 初始化 left 为 0，表示当前第一个有效非零元素应该放的位置。
- 使用 right 遍历数组：
- 如果 nums[right] 是非零值，交换 nums[left] 和 nums[right] 的值，同时 left 向右移动一位。
- 如果是 0，right 向右移动，left 不动。
- 遍历结束后，left 之前的所有元素均为非零元素，且保持原有顺序；left 及其后的元素为 0。
go
func moveZeroes(nums []int) {
left := 0
for right := 0; right < len(nums); right++ {
if nums[right] != 0 {
nums[left], nums[right] = nums[right], nums[left]
left++
}
}
}链表
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
go
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]示例 2：
go
输入：l1 = [], l2 = []
输出：[]示例 3：
go
输入：l1 = [], l2 = [0]
输出：[0]题解
创建一个哨兵节点，作为合并后的新链表头节点的前一个节点。这样可以避免单独处理头节点，也无需特判链表为空的情况，从而简化代码。
比较 list1 和 list2 的节点值，如果 list1 的节点值小，则把 list1 加到新链表的末尾，然后把 list1 替换成它的下一个节点。如果 list2 的节点值小则同理。
循环结束后，其中一个链表可能还有剩余的节点，将剩余部分加到新链表的末尾。
go
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
// 用哨兵节点简化代码逻辑
newHead := &ListNode{}
cur := newHead
for list1 != nil && list2 != nil {
// 把 list1 加到新链表中
if list1.Val <= list2.Val {
cur.Next = list1
list1 = list1.Next
// 把 list2 加到新链表中
} else {
cur.Next = list2
list2 = list2.Next
}
cur = cur.Next
}
// 拼接剩余链表
if list1 == nil {
cur.Next = list2
} else {
cur.Next = list1
}
return newHead.Next
}反转链表
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
示例 1：
go
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
go
输入：head = [1,2]
输出：[2,1]示例 3：
go
输入：head = []
输出：[]题解
在遍历链表时，将当前节点的 Next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点 pre。在更改引用之前，还需要临时存储后一个节点 tmp。最后返回新的头引用。
go
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。
示例 1：
go
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]示例 2：
go
输入：head = [5], left = 1, right = 1
输出：[5]题解
引入虚拟头节点：为了方便处理边界情况（如 left 在链表头部），我们设置一个 dummy 节点，并让 dummy.Next 指向 head。这样，即使 left = 1 也可以统一处理。
定位到反转区间的前一个节点：定义一个指针 pre，并将其移动到 left 前一个节点的位置。这一步确保我们可以在反转链表时方便地进行节点拼接操作。
反转指定区间的节点：
- 定义 start 为 left 位置的第一个节点，nex 为 start.Next。
- 通过一个循环，将 nex 节点逐步插入到 pre 后面，从而实现反转。
- 每次循环操作，将 nex 从链表中“取出”，然后插入到 pre 后面，使反转区间逐步形成最终结果。
返回结果：返回 dummy.Next，即反转后的链表头。
go
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if head == nil || left == right {
return head
}
// 设置虚拟头节点，方便处理边界情况
dummy := &ListNode{Next: head}
pre := dummy
// 移动 pre 到 left 前一个节点的位置
for i := 1; i < left; i++ {
pre = pre.Next
}
// start 将是要反转的第一个节点（按上图的例子，start 始终指向 2 这个节点）
start := pre.Next
// nex 是将要反转的节点
nex := start.Next
// 开始反转从 left 到 right 的节点
for i := 0; i < right-left; i++ {
start.Next = nex.Next
nex.Next = pre.Next
pre.Next = nex
nex = start.Next
}
return dummy.Next
}相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
go
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。示例 2：
go
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
go
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。题解
如果两个链表相交，那么两链表的公共尾部节点总数一定相等。
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB，当走到 node 时，共走步数为：
go
a+(b−c)指针 B 先遍历完链表 headB，再开始遍历链表 headA，当走到 node 时，共走步数为：
go
b+(a−c)如下式所示，此时指针 A , B 重合，并有两种情况：
go
a+(b−c)=b+(a−c)- 若两链表有公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node。
- 若两链表无公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null。
go
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
curA, curB := headA, headB
// 当 curA 和 curB 不相等时，继续遍历
for curA != curB {
// 如果 curA 走到了末尾，就切换到 headB；否则继续往下走
if curA == nil {
curA = headB
} else {
curA = curA.Next
}
// 如果 curB 走到了末尾，就切换到 headA；否则继续往下走
if curB == nil {
curB = headA
} else {
curB = curB.Next
}
}
// 当 curA == curB 时返回交点，或者返回 nil
return curA
}环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环 ，则返回 true。 否则，返回 false。
示例 1：
go
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。题解
定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。 初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
go
func hasCycle(head *ListNode) bool {
// 如果链表为空或只有一个节点，没有环
if head == nil || head.Next == nil {
return false
}
slow, fast := head, head
// 快慢指针移动，直到相遇或快指针到达链表尾部
for fast != nil && fast.Next != nil {
slow = slow.Next // 慢指针每次走一步
fast = fast.Next.Next // 快指针每次走两步
if slow == fast { // 快慢指针相遇，链表有环
return true
}
}
// 快指针到达链表尾部，链表没有环
return false
}环形链表 II
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
示例 1：
go
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。题解
快慢指针法：使用两个指针，一个是“慢指针”（slow），每次走一步；另一个是“快指针”（fast），每次走两步。如果链表有环，快指针一定会和慢指针相遇。
相遇后：快慢指针相遇后，我们将其中一个指针（比如慢指针）移到链表头，然后让两个指针同时每次走一步，再次相遇的位置就是环的入口节点。
当 fast == slow 时，两指针在环中第一次相遇。下面分析此时 fast 与 slow 走过的步数关系：
- 设链表共有 a+b 个节点，其中 链表头部到链表入口有 a 个节点（不计链表入口节点），链表环有 b 个节点（这里需要注意，a 和 b 是未知数，例如图解上链表 a=4 , b=5）；设两指针分别走了 f，s 步，则有：
- fast 走的步数是 slow 步数的 2 倍，即 f=2s；（解析：fast 每轮走 2 步）
- fast 比 slow 多走了 n 个环的长度，即 f=s+nb；（解析：双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走环的长度整数倍）。
将以上两式相减得到 f=2nb，s=nb，即 fast 和 slow 指针分别走了 2n，n 个环的周长。
如果从 head 节点走到入环点需要走：a + nb，即先走 a 步到入口节点，之后绕 nb 步会再次到入口节点。 而在相遇的时候 slow 已经走了 nb，那么 slow 再走 a 步就是入环点了。
如何知道 slow 刚好走了 a 步？让 fast 从 head 节点开始，和 slow 指针一起走，相遇时刚好就是 a 步，也就是入口点。
go
func detectCycle(head *ListNode) *ListNode {
// 如果链表为空或者只有一个节点，直接返回 nil
if head == nil || head.Next == nil {
return nil
}
slow, fast := head, head // 都从头节点开始
// 第一步：快慢指针相遇，判断是否有环
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast { // 快慢指针相遇，表示链表有环
// 第二步：找环的入口节点
fast = head
// 从头节点开始，快慢指针一起走，直到相遇
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow // 或者 return fast，返回环的入口节点
}
}
// 如果没有环，返回 nil
return nil
}K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
go
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]示例 2：
go
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]题解
pre 节点指向待翻转的一组子链表的头节点，tail 节点用于找到当前 k 个节点的尾节点。找到当前 k 个节点的尾节点后，调用 myReverse 函数翻转当前 k 个节点，并返回新的头尾节点。将翻转后的头节点接到上一组，更新 pre 为当前组的尾节点，移动 head 到下一组的头节点。
完整动图参考：力扣官方题解
go
func reverseKGroup(head *ListNode, k int) *ListNode {
// 创建一个虚拟节点 hair，并将其 Next 指向 head。这样可以方便处理头节点的特殊情况，最后返回 hair.Next 即可
hair := &ListNode{Next: head}
// pre 指向待翻转的一组子链表的头节点
pre := hair
for head != nil {
// tail 用于找到当前 k 个节点的尾节点
tail := pre
// 循环处理链表，每次处理 k 个节点
for i := 0; i < k; i++ {
tail = tail.Next
// 如果剩余节点数不足 k 个，不翻转直接返回
if tail == nil {
return hair.Next
}
}
// 保存下一组的头节点
nex := tail.Next
// 翻转当前 k 个节点，并返回新的头尾节点
head, tail = myReverse(head, tail)
// 将翻转后的头节点接到上一组
pre.Next = head
// 更新 pre 为当前组的尾节点
pre = tail
// 移动 head 到下一组的头节点
head = nex
}
return hair.Next
}
func myReverse(head, tail *ListNode) (*ListNode, *ListNode) {
// pre 初始指向下一组的头节点
pre := tail.Next
// p 指向当前要处理的节点
p := head
// 循环翻转节点，直到处理完 tail
for pre != tail {
// 保存下一个要处理的节点
nex := p.Next
// 翻转当前节点的指针
p.Next = pre
// 更新 pre 为当前节点
pre = p
// 移动 p 到下一个节点，继续反转
p = nex
}
// 返回翻转后的新头尾节点
return tail, head
}两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
go
输入：head = [1,2,3,4]
输出：[2,1,4,3]题解
和 K 个一组翻转链表 类似，只是 k 固定为 2。
go
func swapPairs(head *ListNode) *ListNode {
// 创建一个虚拟节点 hair，并将其 Next 指向 head。这样可以方便处理头节点的特殊情况，最后返回 hair.Next 即可
hair := &ListNode{Next: head}
// pre 指向待翻转的一组子链表的头节点
pre := hair
// 和K 个一组翻转链表一题类似，只是 k 固定为 2
k := 2
for head != nil {
// tail 用于找到当前 k 个节点的尾节点
tail := pre
// 循环处理链表，每次处理 k 个节点
for i := 0; i < k; i++ {
tail = tail.Next
// 如果剩余节点数不足 k 个，不翻转直接返回
if tail == nil {
return hair.Next
}
}
// 保存下一组的头节点
nex := tail.Next
// 翻转当前 k 个节点，并返回新的头尾节点
head, tail = myReverse(head, tail)
// 将翻转后的头节点接到上一组
pre.Next = head
// 更新 pre 为当前组的尾节点
pre = tail
// 移动 head 到下一组的头节点
head = nex
}
return hair.Next
}
func myReverse(head, tail *ListNode) (*ListNode, *ListNode) {
// pre 初始指向下一组的头节点
pre := tail.Next
// p 指向当前要处理的节点
p := head
// 循环翻转节点，直到处理完 tail
for pre != tail {
// 保存下一个要处理的节点
nex := p.Next
// 翻转当前节点的指针
p.Next = pre
// 更新 pre 为当前节点
pre = p
// 移动 p 到下一个节点，继续反转
p = nex
}
// 返回翻转后的新头尾节点
return tail, head
}重排链表
给定一个单链表 L 的头节点 head，单链表 L 表示为：
go
L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为：
go
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
go
输入：head = [1,2,3,4]
输出：[1,4,2,3]示例 2：
go
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]题解
- 找到链表的中间节点：使用快慢指针来找到链表的中间节点。快指针每次走两步，慢指针每次走一步，最终慢指针会指向中间节点。
- 将后半部分反转：从中间节点开始，将链表的后半部分进行反转。这样就能方便地交替连接前半部分和后半部分。
- 交替合并两个链表：将前半部分和反转后的后半部分交替合并。
go
func reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
// 步骤 1: 找到链表的中间节点
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 步骤 2: 反转链表的后半部分
second := slow.Next
slow.Next = nil // 断开前半部分与后半部分的连接
second = reverseList(second)
// 步骤 3: 交替合并两个链表
first := head
for second != nil {
tmp1 := first.Next
tmp2 := second.Next
first.Next = second
second.Next = tmp1
first = tmp1
second = tmp2
}
}
// 反转链表
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}删除排序链表中的重复元素
给定一个已排序的链表的头 head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。
示例 1：
go
输入：head = [1,1,2]
输出：[1,2]示例 2：
go
输入：head = [1,1,2,3,3]
输出：[1,2,3]题解
利用链表已经排序的特点：如果链表是排序好的，那么重复的元素一定是连续出现的。因此，可以通过遍历链表，只需要检查当前节点和下一个节点的值是否相同，若相同就删除下一个节点。
go
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
cur := head
for cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}删除排序链表中的重复元素 II
给定一个已排序的链表的头 head， 删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。
示例 1：
go
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]示例 2：
go
输入：head = [1,1,1,2,3]
输出：[2,3]题解
遍历链表：遍历链表时，检查当前节点的值和下一个节点的值：
- 如果当前节点的值与下一个节点的值相同，说明出现了重复节点。我们需要跳过所有这些重复节点。
- 如果当前节点的值与下一个节点的值不同，保留当前节点，继续处理下一个节点。
调整指针：在删除节点时，调整当前节点的 Next 指针，跳过所有重复的节点。
go
func deleteDuplicates(head *ListNode) *ListNode {
// 创建一个虚拟头节点，方便处理头节点的删除情况
dummy := &ListNode{Next: head}
prev := dummy // prev 始终指向去重后的链表的最后一个节点
// 遍历链表
for head != nil {
// 如果当前节点与下一个节点的值相同，跳过所有重复的节点
if head.Next != nil && head.Val == head.Next.Val {
// 跳过重复节点
for head.Next != nil && head.Val == head.Next.Val {
head = head.Next
}
// 跳过所有重复的节点，连接到下一个不重复的节点
prev.Next = head.Next
// 有可能这个节点和后面节点会重复，比如 1 -> 2 -> 2 -> 3 -> 3
// 所以没有移动 prev = prev.Next
} else {
// 当前节点没有重复，保留当前节点
prev = prev.Next
}
// 继续向下遍历
head = head.Next
}
return dummy.Next // 返回去重后的链表头
}删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
go
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]题解
快慢指针法：
- 我们使用两个指针：一个快指针 fast 和一个慢指针 slow。
- 先将快指针向前移动 n 步，这样快指针和慢指针之间的距离就固定了 n 个节点。
- 然后同时移动快指针和慢指针，直到快指针到达链表的末尾。此时，慢指针就正好指向倒数第 n 个节点的前一个节点。
- 删除倒数第 n 个节点，只需要将慢指针的 Next 指针指向 slow.Next.Next 即可。
go
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// 创建一个虚拟头节点，简化头节点删除的处理
dummy := &ListNode{Next: head}
fast := dummy
slow := dummy
// 让快指针先走 n 步
for i := 0; i <= n; i++ {
fast = fast.Next
}
// 快指针和慢指针一起走，直到快指针到达链表末尾
// 此时慢指针的 next 就是要删除的节点
for fast != nil {
slow = slow.Next
fast = fast.Next
}
// 删除倒数第 n 个节点
slow.Next = slow.Next.Next
// 返回头节点
return dummy.Next
}合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
go
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6题解
优先队列：使用一个最小堆来保存所有链表的头节点。每次从堆中弹出值最小的节点，然后将它的下一个节点加入堆。Go 语言中可以通过实现 heap.Interface 来构建整数小顶堆。
合并过程：
- 将每个链表的头节点加入堆。
- 从堆中取出当前最小值的节点，加入结果链表。
- 如果该节点有后续节点，则将后续节点加入堆。
go
type MinHeap []*ListNode
// Go 语言中可以通过实现 heap.Interface 来构建整数小顶堆
// 实现 heap.Interface 需要同时实现 sort.Interface
// Len sort.Interface 的方法
func (h MinHeap) Len() int { return len(h) }
// 如果实现大顶堆，则需要调整为 >
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
// Push heap.Interface 的方法，实现推入元素到堆
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(*ListNode))
}
// Pop heap.Interface 的方法，实现弹出堆顶元素
func (h *MinHeap) Pop() interface{} {
last := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return last
}
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
h := &MinHeap{}
heap.Init(h)
// 将每个链表的头节点加入堆
for _, list := range lists {
if list != nil {
heap.Push(h, list)
}
}
// 使用一个哑节点简化操作
dummy := &ListNode{}
curr := dummy
// 合并链表
for h.Len() > 0 {
// 弹出堆中最小值
smallest := heap.Pop(h).(*ListNode)
curr.Next = smallest
curr = curr.Next
// 如果该节点有下一个节点，将其加入堆
if smallest.Next != nil {
heap.Push(h, smallest.Next)
}
}
return dummy.Next
}图书整理 I
书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。
示例 1：
bash
输入：head = [3,6,4,1]
输出：[1,4,6,3]方法一：递归
利用递归，先递推至链表末端；回溯时，依次将节点值加入列表，即可实现链表值的倒序输出。
- 终止条件： 当 head == None 时，代表越过了链表尾节点，则返回空列表；
- 递推工作： 访问下一节点 head.next ；
go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBookList(head *ListNode) []int {
var data []int
recur(head, &data)
return data
}
func recur(head *ListNode, data *[]int) {
if head == nil {
return
}
recur(head.Next, data)
*data = append(*data, head.Val)
}方法二：辅助栈法
- 入栈： 遍历链表，将各节点值 push 入栈。
- 出栈： 将各节点值 pop 出栈，存储于数组并返回。
go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBookList(head *ListNode) []int {
stack := list.New()
for head != nil {
stack.PushBack(head.Val)
head = head.Next
}
data := make([]int, 0)
for stack.Len() > 0 {
data = append(data, stack.Back().Value.(int))
stack.Remove(stack.Back())
}
return data
}方法三：反转链表
先将原链表反转，然后再遍历反转后的链表，将值依次存入数组中。
go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBookList(head *ListNode) []int {
var data []int
reverseHead := reverseList(head)
for reverseHead != nil {
data = append(data, reverseHead.Val)
reverseHead = reverseHead.Next
}
return data
}
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
for head != nil {
next := head.Next
head.Next = pre
pre = head
head = next
}
return pre
}排序链表
给你链表的头结点 head，请将其按升序排列并返回排序后的链表。
示例 1：
go
输入：head = [4,2,1,3]
输出：[1,2,3,4]题解
要按升序排序链表，常见的方法是归并排序（Merge Sort），因为它对于链表具有良好的时间复杂度 O(n log n)，并且不需要额外的空间（因为链表是可以原地修改的）。归并排序的基本思路是：
- 分割链表：将链表从中间分割成两部分。
- 排序子链表：递归地排序每个子链表。
- 合并排序后的子链表：将两个已排序的子链表合并成一个排序链表。
go
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 使用快慢指针找到链表的中点
mid := findMiddle(head)
left := sortList(head) // 递归排序左半部分
right := sortList(mid) // 递归排序右半部分
// 合并两个已排序的链表
return merge(left, right)
}
// findMiddle 使用快慢指针找到链表的中点
func findMiddle(head *ListNode) *ListNode {
slow, fast := head, head
var prev *ListNode
// 快指针一次走两步，慢指针一次走一步
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
// 断开链表，返回链表的后半部分
if prev != nil {
prev.Next = nil
}
return slow
}
// merge 合并两个已排序的链表
func merge(left, right *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
// 合并两个链表，直到其中一个链表为空
for left != nil && right != nil {
if left.Val < right.Val {
tail.Next = left
left = left.Next
} else {
tail.Next = right
right = right.Next
}
tail = tail.Next
}
// 如果有剩余的节点，直接接到结果链表的末尾
if left != nil {
tail.Next = left
} else {
tail.Next = right
}
return dummy.Next
}训练计划 II
给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。
示例 1：
go
输入：head = [2,4,7,8], cnt = 1
输出：8题解
快慢指针法：
- 我们使用两个指针：一个快指针 fast 和一个慢指针 slow。
- 先将快指针向前移动 n 步，这样快指针和慢指针之间的距离就固定了 n 个节点。
- 然后同时移动快指针和慢指针，直到快指针到达链表的末尾。此时，慢指针就正好指向倒数第 n 个节点的前一个节点。
go
func trainingPlan(head *ListNode, cnt int) *ListNode {
fast, slow := head, head
for i := 0; i < cnt; i++ {
fast = fast.Next
}
for fast != nil {
slow = slow.Next
fast = fast.Next
}
return slow
}两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
go
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.题解
- 使用一个虚拟头节点 dummy 来简化结果链表的构造，cur 指向当前链表的末尾。
- 每次取出两个链表当前节点的值相加，并处理进位。直到两个链表都为空且没有进位为止。
go
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
carry := 0
for l1 != nil || l2 != nil || carry > 0 {
n1, n2 := 0,0
if l1 != nil {
n1 = l1.Val
l1 = l1.Next
}
if l2 != nil {
n2 = l2.Val
l2 = l2.Next
}
sum := n1 + n2 + carry
carry = sum / 10
cur.Next = &ListNode{Val: sum % 10}
cur = cur.Next
}
return dummy.Next
}回文链表
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
示例 1：
go
输入：head = [1,2,2,1]
输出：true示例 2：
go
输入：head = [1,2]
输出：false题解
- 使用快慢指针找到链表的中间节点。
- 将链表后半部分反转。
- 比较链表前半部分和反转后的后半部分是否相同。
go
func isPalindrome(head *ListNode) bool {
slow, fast := head, head
for fast != nil &&fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
secondHalf := reverseList(slow)
firstHalf := head
for secondHalf != nil {
if firstHalf.Val != secondHalf.Val {
return false
}
firstHalf = firstHalf.Next
secondHalf = secondHalf.Next
}
return true
}
func reverseList(node *ListNode) *ListNode {
var prev *ListNode
for node != nil {
next := node.Next
node.Next = prev
prev = node
node = next
}
return prev
}哈希表
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
go
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
go
输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
go
输入：nums = [3,3], target = 6
输出：[0,1]题解
我们可以通过哈希表来优化问题的求解，使其时间复杂度降低到 O(n)。具体思路如下：
- 创建一个哈希表，键是数组中的数字，值是该数字的下标。
- 在遍历数组时，针对每个数字 v，我们检查哈希表中是否存在 target - v，即目标值减去当前数字的差值。如果存在，那么这两个数的和正好等于 target，返回它们的下标即可。
- 如果没有找到合适的数字，则将当前数字和它的下标存入哈希表，供后续元素查找使用，并进入下一次循环。
go
func twoSum(nums []int, target int) []int {
// 键是数字，值是 nums 数组的下标
hashTable := make(map[int]int)
for i, v := range nums {
// 在哈希表中查找的数字，target 减去当前的数字
if p, ok := hashTable[target-v]; ok {
return []int{p, i}
}
// 没有找到就把当前数字存入哈希表
hashTable[v] = i
}
return nil
}最长连续序列
给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
go
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：
go
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9题解
- 将数组中的所有元素存入 HashMap（去重）。
- 遍历数组中的每个元素，如果它是一个连续序列的起点（即 num - 1 不在 HashMap 中），就开始向后查找连续的元素。
- 维护一个变量记录当前找到的最长连续序列的长度。
go
// 寻找最长连续序列的函数
func longestConsecutive(nums []int) int {
if len(nums) == 0 {
return 0
}
// 用 HashSet 存储所有元素，去除重复
numSet := make(map[int]bool)
for _, num := range nums {
numSet[num] = true
}
longest := 0
// 遍历每个元素
for num := range numSet {
// 只有当 num 是一个连续序列的起点时才进行查找
if !numSet[num-1] {
currentNum := num
currentStreak := 1
// 向后查找连续序列
for numSet[currentNum+1] {
currentNum++
currentStreak++
}
// 更新最长连续序列的长度
if currentStreak > longest {
longest = currentStreak
}
}
}
return longest
}前缀和
和为 K 的子数组
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。
示例 1：
go
输入：nums = [1,1,1], k = 2
输出：2示例 2：
go
输入：nums = [1,2,3], k = 3
输出：2题解
方法一：哈希表
- 前缀和是从数组起点到当前元素的累积和。用 prefixSum 表示当前的前缀和。
- 维护一个哈希表 countMap，其中键为前缀和，值为该前缀和出现的次数。
- 遍历数组时，通过 prefixSum - k 判断是否存在之前的前缀和满足条件。
go
func subarraySum(nums []int, k int) int {
countMap := make(map[int]int)
countMap[0] = 1 // 初始前缀和为 0 的情况
prefixSum := 0
count := 0
for _, num := range nums {
prefixSum += num
// 检查是否存在前缀和使得当前子数组和为 k
if val, exists := countMap[prefixSum-k]; exists {
count += val
}
// 更新当前前缀和的出现次数
countMap[prefixSum]++
}
return count
}方法二：暴力枚举法
- 使用双层循环遍历数组：
- 外层循环：从每个元素 nums[i] 开始，枚举所有可能的起点。
- 内层循环：从当前起点 i 开始，逐一向右扩展子数组 nums[i...j]，计算当前子数组的和 currentSum。
- 对于每个子数组：
- 累加当前元素到 currentSum。
- 如果 currentSum == k，说明找到一个符合条件的子数组，结果计数器 res 增加 1。
go
func subarraySum(nums []int, k int) int {
n := len(nums)
res := 0
for i := 0; i < n; i++ {
currentSum := 0
for j := i; j < n; j++ {
currentSum += nums[j]
if currentSum == k {
res++
}
}
}
return res
}参考资料：算法面试实录-和为 k 的子数组
栈与队列
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
go
输入：s = "()"
输出：true示例 2：
go
输入：s = "()[]{}"
输出：true示例 3：
go
输入：s = "(]"
输出：false示例 4：
go
输入：s = "([])"
输出：true题解
栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
为了避免在检查和弹出栈顶元素时需要额外的边界检查，可以在栈中插入一个任意初始值（如 'x'）。例如，使用这个初始值时，可以在后续逻辑中直接执行 stack[len(stack)-1]，而不需要担心栈是否为空。
go
func isValid(s string) bool {
dic := map[rune]rune {
'(': ')',
'{': '}',
'[': ']',
}
// 通过在栈中插入一个任意初始值（如 'x'），可以避免在检查和弹出栈顶元素时需要额外的边界检查。
// 例如，使用这个初始值时，可以在后续逻辑中直接执行 stack[len(stack)-1]，而不需要担心栈是否为空。
stack := []rune{'x'}
for _, c := range s {
// 左侧括号直接压入栈
if _, ok := dic[c]; ok {
stack = append(stack, c)
// 当遇到右侧括号时，和栈顶元素进行比较
} else {
if dic[stack[len(stack)-1]] != c {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 1
}最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
go
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"示例 2：
go
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"示例 3：
go
输入：s = ""
输出：0题解
初始化栈和变量：
- 栈中存储的是索引，用于计算有效括号长度。
- 首先将 -1 压入栈，作为基准点，帮助处理一开始可能就有匹配的括号。
遍历字符串：
- 遇到 '(' 时，将其索引压入栈。
- 遇到 ')' 时，弹出栈顶元素，表示当前右括号找到了一个匹配的左括号：
- 如果栈不为空，用当前索引减去栈顶索引，得到一个有效括号长度，并更新最大长度。
- 如果栈为空，将当前索引压入栈，作为新的基准点。
基准点的作用是确保栈在无法匹配时能够正确记录“当前无效括号的起点”，以便后续长度计算依然正确。
go
func longestValidParentheses(s string) int {
stack := []int{}
// 初始化基准点
stack = append(stack, -1)
maxLen := 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
// 左括号，压入索引
stack = append(stack, i)
} else {
// 右括号，弹出栈顶
stack = stack[:len(stack)-1]
if len(stack) == 0 {
// 如果栈为空，记录当前索引作为新的基准点
stack = append(stack, i)
} else {
// 栈不为空，计算有效括号长度
maxLen = max(maxLen, i-stack[len(stack)-1])
}
}
}
return maxLen
}
func max(a, b int) int {
if a > b {
return a
}
return b
}用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回 true ；否则，返回 false
题解
将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。
每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
go
type MyQueue struct {
inStack, outStack []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (q *MyQueue) Push(x int) {
q.inStack = append(q.inStack, x)
}
func (q *MyQueue) in2out() {
for len(q.inStack) > 0 {
q.outStack = append(q.outStack, q.inStack[len(q.inStack)-1])
q.inStack = q.inStack[:len(q.inStack)-1]
}
}
func (q *MyQueue) Pop() int {
if len(q.outStack) == 0 {
q.in2out()
}
x := q.outStack[len(q.outStack)-1]
q.outStack = q.outStack[:len(q.outStack)-1]
return x
}
func (q *MyQueue) Peek() int {
if len(q.outStack) == 0 {
q.in2out()
}
return q.outStack[len(q.outStack)-1]
}
func (q *MyQueue) Empty() bool {
return len(q.inStack) == 0 && len(q.outStack) == 0
}最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素 val 推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例 1:
go
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.题解
借用一个辅助栈 minStack，用于存获取 stack 中最小值。
算法流程：
- push() 方法： 每当 push() 新值进来时，如果小于等于 minStack 栈顶值，则一起 push() 到 minStack，即更新了栈顶最小值；
- pop() 方法： 判断将 pop() 出去的元素值是否是 minStack 栈顶元素值（即最小值），如果是则将 minStack 栈顶元素一起 pop()，这样可以保证 minStack 栈顶元素始终是 stack 中的最小值。
- getMin()方法： 返回 minStack 栈顶即可。
go
type MinStack struct {
stack, minStack []int
}
func Constructor() MinStack {
return MinStack{}
}
func (q *MinStack) Push(val int) {
q.stack = append(q.stack, val)
// 当 minStack 为空或者 minStack 的栈顶元素小于 val 时，将 val 压入 minStack
if len(q.minStack) == 0 || val <= q.minStack[len(q.minStack)-1] {
q.minStack = append(q.minStack, val)
}
}
func (q *MinStack) Pop() {
val := q.stack[len(q.stack)-1]
q.stack = q.stack[:len(q.stack)-1]
if len(q.minStack) > 0 && val == q.minStack[len(q.minStack)-1] {
q.minStack = q.minStack[:len(q.minStack)-1]
}
}
func (q *MinStack) Top() int {
return q.stack[len(q.stack)-1]
}
func (q *MinStack) GetMin() int {
if len(q.minStack) > 0 {
return q.minStack[len(q.minStack)-1]
}
return 0
}字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
go
输入：s = "3[a]2[bc]"
输出："aaabcbc"示例 2：
go
输入：s = "3[a2[c]]"
输出："accaccacc"示例 3：
go
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"示例 4：
go
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"题解
- 遍历字符串 s，用栈来辅助解析嵌套的结构。
- 当遇到一个数字时，解析数字并开始记录后续的方括号内容。
- 当遇到 ] 时，将当前括号内的内容出栈，按照数字重复解码。
- 最后，栈中累积的字符串就是解码后的结果。
go
func decodeString(s string) string {
stack := []string{}
numStack := []int{}
currentStr := ""
currentNum := 0
for _, ch := range s {
if ch >= '0' && ch <= '9' { // 如果是数字，解析为 currentNum
currentNum = currentNum*10 + int(ch-'0')
} else if ch == '[' { // 如果是 '['，把当前的数字和字符串推入栈
numStack = append(numStack, currentNum)
stack = append(stack, currentStr)
currentStr = ""
currentNum = 0
} else if ch == ']' { // 如果是 ']'，弹出数字并重复字符串
repeatNum := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
lastStr := stack[len(stack)-1]
stack = stack[:len(stack)-1]
currentStr = lastStr + strings.Repeat(currentStr, repeatNum)
} else { // 普通字符，累积到 currentStr
currentStr += string(ch)
}
}
return currentStr
}排序
快速排序
- 首先，对原数组执行一次“哨兵划分”，选取数组最左端元素作为基准数，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧，得到未排序的左子数组和右子数组。
- 然后，对左子数组和右子数组分别递归执行“哨兵划分”。
- 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。
go
/* 哨兵划分 */
func partition(nums []int, left, right int) int {
// 以 nums[left] 为基准数
i, j := left, right
for i < j {
for i < j && nums[j] >= nums[left] {
j-- // 从右向左找首个小于基准数的元素
}
for i < j && nums[i] <= nums[left] {
i++ // 从左向右找首个大于基准数的元素
}
// 元素交换
nums[i], nums[j] = nums[j], nums[i]
}
// 将基准数交换至两子数组的分界线
nums[i], nums[left] = nums[left], nums[i]
return i // 返回基准数的索引
}
/* 快速排序 */
func quickSort(nums []int, left, right int) {
// 子数组长度为 1 时终止递归
if left >= right {
return
}
// 哨兵划分
pivot := partition(nums, left, right)
// 递归左子数组、右子数组
quickSort(nums, left, pivot-1)
quickSort(nums, pivot+1, right)
}数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
go
输入: [3,2,1,5,6,4], k = 2
输出: 5示例 2:
go
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4题解
基于快速排序的思想，但是此题并不需要对数组进行完整排序，它在每次递归中只会在需要的那一侧继续划分，而不是像快速排序那样递归处理两侧，当 pivot 等于 k-1 时，即找到了第 k 个最大的元素。
go
func findKthLargest(nums []int, k int) int {
quickSort(nums, 0, len(nums)-1, k)
return nums[k-1]
}
func partition(nums []int, left, right int) int {
i, j := left, right
for i <= j {
for i <= j && nums[i] >= nums[left] {
i++
}
for i <= j && nums[j] <= nums[left] {
j--
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
nums[left], nums[j] = nums[j], nums[left]
return j
}
func quickSort(nums []int, left, right, k int) {
if left <= right {
pivot := partition(nums, left, right)
if pivot == k-1 {
return
} else if pivot > k-1 {
quickSort(nums, left, pivot-1, k)
} else {
quickSort(nums, pivot+1, right, k)
}
}
}归并排序
“划分阶段”从顶至底递归地将数组从中点切分为两个子数组。
- 计算数组中点 mid ，递归划分左子数组（区间 [left, mid] ）和右子数组（区间 [mid + 1, right]）。
- 递归执行步骤 1. ，直至子数组区间长度为 1 时终止。
“合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的。
go
func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
// 分割数组
mid := len(nums) / 2
left := sortArray(nums[:mid]) // 递归排序左半部分
right := sortArray(nums[mid:]) // 递归排序右半部分
// 合并排序后的左右两个部分
return merge(left, right)
}
// merge 合并两个已排序的数组
func merge(left, right []int) []int {
result := []int{}
i, j := 0, 0
// 合并两个有序数组
for i < len(left) && j < len(right) {
if left[i] < right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
// 将剩余的元素添加到结果中
for i < len(left) {
result = append(result, left[i])
i++
}
for j < len(right) {
result = append(result, right[j])
j++
}
return result
}二叉树
二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的层序遍历。即逐层地，从左到右访问所有节点）。
示例 1：
go
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
go
输入：root = [1]
输出：[[1]]示例 3：
go
输入：root = []
输出：[]题解
- BFS 算法，通过一个 while 循环控制从上向下一层层遍历，for 循环控制每一层从左向右遍历。
- 在处理每层节点的时候将下一层的节点加入 queue，然后在下一轮 for 循环的时候根据当前层的节点数进行处理。
go
func levelOrder(root *TreeNode) [][]int {
// 存放最后的结果
var ans [][]int
// 特殊情况
if root == nil {
return ans
}
// 队列存放每层节点
var queue []*TreeNode
// 先将根节点加入队列
queue = append(queue, root)
// 外层循环控制从上向下一层层遍历
for len(queue) != 0 {
// 存放每层结果
var levelAns []int
// 该层的节点数
curLevelNum := len(queue)
// 内层循环控制每一层从左向右遍历
for i := 0; i < curLevelNum; i++ {
node := queue[0]
levelAns = append(levelAns, node.Val)
queue = queue[1:]
// 将该层的子节点加入队列，在下一次层序遍历时使用
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
ans = append(ans, levelAns)
}
return ans
}二叉树的前序、中序、后序遍历
相应地，前序、中序和后序遍历都属于深度优先遍历（depth-first traversal），也称深度优先搜索（depth-first search, DFS），它体现了一种“先走到尽头，再回溯继续”的遍历方式。
下图展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。
深度优先搜索通常基于递归实现：
go
/* 前序遍历 */
func preOrder(node *TreeNode) {
if node == nil {
return
}
// 访问优先级：根节点 -> 左子树 -> 右子树
nums = append(nums, node.Val)
preOrder(node.Left)
preOrder(node.Right)
}
/* 中序遍历 */
func inOrder(node *TreeNode) {
if node == nil {
return
}
// 访问优先级：左子树 -> 根节点 -> 右子树
inOrder(node.Left)
nums = append(nums, node.Val)
inOrder(node.Right)
}
/* 后序遍历 */
func postOrder(node *TreeNode) {
if node == nil {
return
}
// 访问优先级：左子树 -> 右子树 -> 根节点
postOrder(node.Left)
postOrder(node.Right)
nums = append(nums, node.Val)
}以二叉树的中序遍历 为例，下面是完整代码：
go
func inorderTraversal(root *TreeNode) []int {
res := make([]int, 0)
inOrder(&res, root)
return res
}
func inOrder(res *[]int, root *TreeNode) {
if root == nil {
return
}
inOrder(res, root.Left)
*res = append(*res, root.Val)
inOrder(res, root.Right)
}从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
go
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]题解
- 前序遍历的第一个元素就是根节点的值。
- 在中序遍历中找到根节点的值，该值左边的元素就是左子树的元素，右边的元素就是右子树的元素。
- 递归构建左右子树，每次递归中先根据前序遍历确定子树的根节点，再根据中序遍历确定这个子树的左右子树。
go
func buildTree(preorder []int, inorder []int) *TreeNode {
inorderIndex = make(map[int]int)
// 构建哈希表，存储中序遍历的值和索引的对应关系
for i := 0; i < len(inorder); i++ {
inorderIndex[inorder[i]] = i
}
return build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}
func build(preorder []int, preStart int, preEnd int, inorder []int, inStart int, inEnd int) *TreeNode {
if preStart > preEnd {
return nil
}
// 前序遍历数组的第一个元素就是 root
rootVal := preorder[preStart]
// 获取 root 节点在中序遍历数组中的索引
index, _ := inorderIndex[rootVal]
leftSize := index - inStart
// 先构建 root 节点
root := &TreeNode{Val: rootVal}
// 递归构建左右子树
root.Left = build(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1)
root.Right = build(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd)
return root
}从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
示例 1:
go
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]题解
- 后序遍历的最后一个元素就是根节点的值。
- 在中序遍历中找到根节点的值，该值左边的元素就是左子树的元素，右边的元素就是右子树的元素。
- 递归构建左右子树，每次递归中先根据后序遍历确定子树的根节点，再根据中序遍历确定这个子树的左右子树。
go
var inorderIndex map[int]int
func buildTree(inorder []int, postorder []int) *TreeNode {
inorderIndex = make(map[int]int)
// 根据中序遍历数组构建哈希表
for i := 0; i < len(inorder); i++ {
inorderIndex[inorder[i]] = i
}
return build(postorder, 0, len(postorder)-1, inorder, 0, len(inorder)-1)
}
func build(postorder []int, postStart int, postEnd int, inorder []int, inStart int, inEnd int) *TreeNode {
if postStart > postEnd {
return nil
}
// 构建根节点
rootVal := postorder[postEnd]
root := &TreeNode{Val: rootVal}
// 计算左子树的长度
index, _ := inorderIndex[rootVal]
leftSize := index - inStart
// 递归构建左右子树
root.Left = build(postorder, postStart, postStart+leftSize-1, inorder, inStart, index-1)
root.Right = build(postorder, postStart+leftSize, postEnd-1, inorder, index+1, inEnd)
return root
}根据前序和后序遍历构造二叉树
给定两个整数数组，preorder 和 postorder，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中任何一个。
示例 1：
go
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]题解
通过前序中序，或者后序中序遍历结果可以确定唯一一棵原始二叉树，但是通过前序后序遍历结果无法确定唯一的原始二叉树。
- 1.首先把前序遍历结果的第一个元素（或者后序遍历结果的最后一个元素确定为根节点的值）。
- 2.然后把前序遍历结果的第二个元素作为左子树的根节点的值。
- 3.在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。
go
var postorderIndex map[int]int
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
postorderIndex = make(map[int]int)
// 根据后序遍历数组构建哈希表
for i := 0; i < len(postorder); i++ {
postorderIndex[postorder[i]] = i
}
return build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder)-1)
}
func build(preorder []int, preStart int, preEnd int, postorder []int, postStart int, postEnd int) *TreeNode {
if preStart > preEnd {
return nil
}
if preStart == preEnd {
return &TreeNode{Val: preorder[preStart]}
}
// 构建根节点
rootVal := preorder[preStart]
root := &TreeNode{Val: rootVal}
// 获取子树长度
leftRootVal := preorder[preStart+1]
index, _ := postorderIndex[leftRootVal]
leftSize := index - postStart + 1
// 递归构建左右子树
root.Left = build(preorder, preStart+1, preStart+leftSize, postorder, postStart, index)
root.Right = build(preorder, preStart+leftSize+1, preEnd, postorder, index+1, postEnd)
return root
}二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
go
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]示例 2：
go
输入：root = [1]
输出：[[1]]示例 3：
go
输入：root = []
输出：[]题解
和 二叉树的层序遍历 一题类似，也是采用 BFS 遍历，唯一的区别是如果层数是偶数时，翻转当前层的结果。
go
func zigzagLevelOrder(root *TreeNode) [][]int {
var ans [][]int
if root == nil {
return ans
}
queue := []*TreeNode{root}
level := 1
for len(queue) != 0 {
var levelAns []int
levelNum := len(queue)
for i := 0; i < levelNum; i++ {
node := queue[0]
levelAns = append(levelAns, node.Val)
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
// 偶数层将本层的结果翻转一下
if level % 2 == 0 {
n := len(levelAns)
for i := 0; i < n/2; i++ {
levelAns[i], levelAns[n-1-i] = levelAns[n-1-i], levelAns[i]
}
}
ans = append(ans, levelAns)
level++
}
return ans
}二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
go
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2：
go
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：
go
输入：root = [1,2], p = 1, q = 2
输出：1题解
考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。
根据 left 和 right ，可展开为四种情况：
- 当 left 和 right 同时不为空 ：说明 p,q 分列在 root 的 异侧 （分别在左/右子树），因此 root 为最近公共祖先，返回 root ；
- 当 left 和 right 同时为空 ：说明 root 的左/右子树中都不包含 p,q ，返回 null ；
- 当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
- p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p）；
- p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
- 当 left 不为空 ， right 为空 ：与情况 3. 同理；
go
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
if root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
// 情况 1：p 和 q 都在以 root 为根的树中，找到最近公共祖先
if left != nil && right != nil {
return root
}
// 情况 2：p 和 q 都不在以 root 为根的树中
if left == nil && right == nil {
return nil
}
// 情况 3：p 和 q 其中一个在 root 为根的树中，或者 p,q 两节点都在 root 为根的树中
if left == nil {
return right
}
return left
}二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
go
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]题解
- 我们使用一个队列来进行层次遍历，每次遍历二叉树的每一层。
- 对于每一层，记录这一层的最后一个节点，因为这个节点是从右侧能看到的。
- 将所有这些最后一个节点收集起来，返回结果。
go
func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}
var result []int
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
var lastNode *TreeNode
// 遍历当前层
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
lastNode = node // 记录这一层的最后一个节点
// 将左右子节点加入队列
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
// 把这一层的最后一个节点的值加入结果
result = append(result, lastNode.Val)
}
return result
}二叉树中的最大路径和
二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root，返回其最大路径和。
示例 1：
go
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6示例 2：
go
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42题解
我们可以采用递归方法，从每个节点出发计算路径的最大贡献值。具体思路如下：
- 递归计算最大贡献值：定义递归函数 maxGain，对于每个节点，分别递归计算左右子树的最大贡献值（即左右子树路径和的最大值）。当左右子树的贡献值为负数时，舍弃该路径，将贡献值记为 0。
- 更新全局最大路径和：对于每个节点，计算它作为路径顶点时的路径和，即节点值加上左右子树的贡献值，并用这个和更新全局最大路径和 maxSum。
- 返回最大贡献值：为上层节点计算贡献值时，返回当前节点的最大单边贡献值（即
节点值 + max(左子树贡献, 右子树贡献)），用于父节点路径和的计算。
go
// maxPathSum 计算二叉树的最大路径和
func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt32 // 初始化为最小整数
maxGain(root, &maxSum) // 计算最大路径和
return maxSum
}
// maxGain 计算从当前节点向下的最大路径和，并更新全局最大路径和
func maxGain(node *TreeNode, maxSum *int) int {
if node == nil {
return 0
}
// 递归计算左右子树的最大贡献值，若为负则取0
leftGain := max(0, maxGain(node.Left, maxSum))
rightGain := max(0, maxGain(node.Right, maxSum))
// 当前节点的最大路径和
priceNewPath := node.Val + leftGain + rightGain
// 更新全局最大路径和
*maxSum = max(*maxSum, priceNewPath)
// 返回最大贡献值，用于父节点的路径计算
return node.Val + max(leftGain, rightGain)
}
// max 函数返回两者中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}求根节点到叶节点数字之和
给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。计算从根节点到叶节点生成的所有数字之和。叶节点是指没有子节点的节点。
示例 1：
go
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25示例 2：
go
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026题解
方法一：深度优先搜索
从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。
go
func dfs(root *TreeNode, prevSum int) int {
if root == nil {
return 0
}
sum := prevSum*10 + root.Val
if root.Left == nil && root.Right == nil {
return sum
}
return dfs(root.Left, sum) + dfs(root.Right, sum)
}
func sumNumbers(root *TreeNode) int {
return dfs(root, 0)
}方法一：广度优先搜索
使用广度优先搜索，需要维护两个队列，分别存储节点和节点对应的数字。
初始时，将根节点和根节点的值分别加入两个队列。每次从两个队列分别取出一个节点和一个数字，进行如下操作：
- 如果当前节点是叶子节点，则将该节点对应的数字加到数字之和；
- 如果当前节点不是叶子节点，则获得当前节点的非空子节点，并根据当前节点对应的数字和子节点的值计算子节点对应的数字，然后将子节点和子节点对应的数字分别加入两个队列。
搜索结束后，即可得到所有叶子节点对应的数字之和。
go
type pair struct {
node *TreeNode
num int
}
func sumNumbers(root *TreeNode) (sum int) {
if root == nil {
return
}
queue := []pair{{root, root.Val}}
for len(queue) > 0 {
p := queue[0]
queue = queue[1:]
left, right, num := p.node.Left, p.node.Right, p.num
if left == nil && right == nil {
sum += num
} else {
if left != nil {
queue = append(queue, pair{left, num*10 + left.Val})
}
if right != nil {
queue = append(queue, pair{right, num*10 + right.Val})
}
}
}
return
}路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。如果存在，返回 true；否则，返回 false。
示例 1：
go
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
go
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
go
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。题解
- 递归分解问题：每次递归将 targetSum 减去当前节点的值，继续判断左右子树是否存在满足条件的路径。
- 终止条件：
- 如果节点为空，直接返回 false。
- 如果是叶子节点，判断路径和是否等于 targetSum。
- 组合结果：递归判断左右子树，只要有一条路径满足条件即返回 true。
go
func hasPathSum(root *TreeNode, targetSum int) bool {
// 如果节点为空，则直接返回 false
if root == nil {
return false
}
// 如果是叶子节点，并且路径和等于 targetSum，则返回 true
if root.Left == nil && root.Right == nil {
return root.Val == targetSum
}
// 递归判断左子树或右子树是否有满足条件的路径
return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
叶子节点是指没有子节点的节点。
示例 1：
go
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]题解
- 使用深度优先搜索 (DFS) 遍历二叉树。
- 在递归中维护当前路径 path 和目标和 targetSum。
- 如果当前节点是叶子节点，并且路径和等于目标和，则将当前路径加入结果集。
- 确保每次递归对路径的操作不会相互影响，可以使用切片的副本。
go
func pathSum(root *TreeNode, targetSum int) [][]int {
var res [][]int
var path []int
helper(root, targetSum, path, &res)
return res
}
func helper(node *TreeNode, targetSum int, path []int, res *[][]int) {
if node == nil {
return
}
// 创建当前路径的副本
newPath := make([]int, len(path)+1)
copy(newPath, path)
newPath[len(path)] = node.Val
// 如果是叶子节点且路径和等于目标和
if node.Left == nil && node.Right == nil && targetSum == node.Val {
*res = append(*res, newPath)
return
}
// 递归搜索左右子树
helper(node.Left, targetSum-node.Val, newPath, res)
helper(node.Right, targetSum-node.Val, newPath, res)
}平衡二叉树
给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树是指该树所有节点的左右子树的高度相差不超过 1。
示例 1：
go
输入：root = [3,9,20,null,null,15,7]
输出：true示例 2：
go
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false题解
通过递归的方式进行判断：
- 对每个节点，递归计算左子树和右子树的高度。
- 判断左右子树的高度差是否小于等于 1。
- 如果任一节点不符合平衡的条件，则该树不是平衡二叉树。
go
// 判断二叉树是否是平衡二叉树
func isBalanced(root *TreeNode) bool {
// 递归计算树的高度并判断是否平衡
_, isBalanced := checkHeight(root)
return isBalanced
}
// 检查二叉树的高度，同时判断是否平衡
func checkHeight(node *TreeNode) (int, bool) {
// 如果节点为空，表示高度为 0，且平衡
if node == nil {
return 0, true
}
// 递归获取左子树的高度和是否平衡
leftHeight, leftBalanced := checkHeight(node.Left)
if !leftBalanced {
return 0, false // 左子树不平衡，直接返回
}
// 递归获取右子树的高度和是否平衡
rightHeight, rightBalanced := checkHeight(node.Right)
if !rightBalanced {
return 0, false // 右子树不平衡，直接返回
}
// 当前节点的左右子树高度差是否超过 1
if abs(leftHeight-rightHeight) > 1 {
return 0, false // 当前树不平衡
}
// 返回当前树的高度，和是否平衡
return 1 + max(leftHeight, rightHeight), true
}
// 计算两个整数中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 计算绝对值
func abs(a int) int {
if a < 0 {
return -a
}
return a
}验证二叉搜索树
给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
go
输入：root = [2,1,3]
输出：true示例 2：
go
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。题解
- 对于每个节点，我们检查其值是否在其父节点的有效范围内。
- 对于左子树，当前节点的值应该大于父节点的下界（最小值）。
- 对于右子树，当前节点的值应该小于父节点的上界（最大值）。
- 对左右子树递归判断其是否满足以上条件。
go
func isValidBST(root *TreeNode) bool {
return isValidBSTHelper(root, math.MinInt64, math.MaxInt64)
}
// isValidBSTHelper 是递归判断节点是否在有效范围内
func isValidBSTHelper(node *TreeNode, min, max int) bool {
if node == nil {
return true // 空树是有效的二叉搜索树
}
// 当前节点的值必须在 (min, max) 范围内
if node.Val <= min || node.Val >= max {
return false
}
// 递归检查左子树和右子树
return isValidBSTHelper(node.Left, min, node.Val) &&
isValidBSTHelper(node.Right, node.Val, max)
}二叉树的最大深度
给定一个二叉树 root，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
go
输入：root = [3,9,20,null,null,15,7]
输出：3题解
- 对于每一个节点，递归地计算左子树和右子树的深度。
- 当前节点的深度是 1 + max(左子树深度, 右子树深度)。
go
func maxDepth(root *TreeNode) int {
// 如果节点为空，深度为 0
if root == nil {
return 0
}
// 递归计算左子树和右子树的深度
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
// 当前节点的深度是 1 + max(左子树深度, 右子树深度)
return 1 + max(leftDepth, rightDepth)
}
// 计算两个整数中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}二叉树最大宽度
给你一棵二叉树的根节点 root，返回树的最大宽度。
树的最大宽度是所有层中最大的宽度。
每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
示例 1：
go
输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。题解
- 层序遍历：使用队列来遍历每一层节点，同时记录每个节点的索引。
- 完全二叉树中，左子节点的索引为 2 × 当前节点索引。右子节点的索引为 2 × 当前节点索引 + 1。
- 计算每层宽度：每层宽度为最后一个节点索引减去第一个节点索引再加 1。
go
type NodeIndex struct {
Node *TreeNode
Index int
}
func widthOfBinaryTree(root *TreeNode) int {
if root == nil {
return 0
}
// 使用队列保存节点和其索引，初始索引为 0
queue := []NodeIndex{{Node: root, Index: 0}}
maxWidth := 0
for len(queue) > 0 {
size := len(queue)
// 计算每层的宽度，并与最大宽度进行比较
levelStart, levelEnd := queue[0].Index, queue[len(queue)-1].Index
maxWidth = max(maxWidth, levelEnd-levelStart+1)
// 遍历当前层
for i := 0; i < size; i++ {
current := queue[0]
queue = queue[1:]
if current.Node.Left != nil {
queue = append(queue, NodeIndex{Node: current.Node.Left, Index: 2 * current.Index})
}
if current.Node.Right != nil {
queue = append(queue, NodeIndex{Node: current.Node.Right, Index: 2*current.Index + 1})
}
}
}
return maxWidth
}
func max(a, b int) int {
if a > b {
return a
}
return b
}二叉树的直径
给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root。
两节点之间路径的长度由它们之间边数表示。
示例 1：
go
输入：root = [1,2,3,4,5]
输出：3
解释：3，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。题解
为了计算二叉树的直径，我们可以利用深度优先搜索（DFS）的思想，通过递归地计算每个节点的最大深度，并在计算过程中更新最大直径。具体来说，对于每一个节点，我们计算其左右子树的高度，然后用这两个高度之和来更新全局变量 maxDiameter。最后返回的是从该节点出发的最大深度，即左右子树高度的最大值加1（包括当前节点本身）。
go
// 用来存储最大直径的全局变量
var maxDiameter int
// 计算二叉树的直径
func diameterOfBinaryTree(root *TreeNode) int {
maxDiameter = 0
// 计算深度并更新直径
depth(root)
return maxDiameter
}
// 计算节点的深度，同时更新最大直径
func depth(node *TreeNode) int {
if node == nil {
return 0
}
// 递归计算左子树和右子树的深度
leftDepth := depth(node.Left)
rightDepth := depth(node.Right)
// 更新最大直径
maxDiameter = max(maxDiameter, leftDepth + rightDepth)
// 返回当前节点的深度
return 1 + max(leftDepth, rightDepth)
}
// 计算两个整数中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}对称二叉树
给你一个二叉树的根节点 root，检查它是否轴对称。
示例 1：
go
输入：root = [1,2,2,3,4,4,3]
输出：true示例 2：
go
输入：root = [1,2,2,null,3,null,3]
输出：false题解
- 递归比较树的左子树和右子树。
- 对于每一对节点，检查它们的值是否相等，并且它们的左子树和右子树应该互为镜像，右子树和左子树也要互为镜像
go
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return isMirror(root.Left, root.Right)
}
// 判断两棵树是否互为镜像
func isMirror(t1, t2 *TreeNode) bool {
// 如果两个节点都为空，说明是镜像
if t1 == nil && t2 == nil {
return true
}
// 如果一个为空，另一个不为空，说明不是镜像
if t1 == nil || t2 == nil {
return false
}
// 判断节点值是否相等，并且左右子树是否互为镜像
return t1.Val == t2.Val && isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}翻转二叉树
给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。
示例 1：
go
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]题解
- 对于每一个节点，将其左右子节点互换。
- 然后递归地对左右子节点分别执行翻转操作。
go
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
// 递归交换左右子树
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}二叉树展开为链表
给你二叉树的根结点 root，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。 展开后的单链表应该与二叉树先序遍历顺序相同。
示例 1：
go
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]对于一个节点 x，可以执行以下流程：
- 1.先利用 flatten(x.left) 和 flatten(x.right) 将 x 的左右子树拉平。
- 2.将 x 的右子树接到左子树下方，然后将整个左子树作为右子树。
go
// 定义：将以 root 为根的树拉平为链表
func flatten(root *TreeNode) {
// base case
if root == nil {
return
}
// 利用定义，把左右子树拉平
flatten(root.Left)
flatten(root.Right)
// *** 后序遍历位置 ***
// 1. 左右子树已经被拉平成一条链表
left := root.Left
right := root.Right
// 2. 将左子树作为右子树
root.Left = nil
root.Right = left
// 3. 将原先的右子树接到当前右子树的末端
p := root
for p.Right != nil {
p = p.Right
}
p.Right = right
}贪心
最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
go
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
go
输入：nums = [1]
输出：1示例 3：
go
输入：nums = [5,4,-1,7,8]
输出：23题解
- maxSum 记录最大和，curSum 记录当前指针元素之前的和。
- 每次循环时，判断当前元素 nums[i] 加上之前的和 curSum 是否比仅仅取当前元素 nums[i] 更大。
- 如果 nums[i] + curSum > nums[i]，说明之前的和是有利的，继续累加当前元素，更新 curSum。
- 如果 nums[i] + curSum <= nums[i]，则丢弃之前的和，从当前元素重新开始，即 curSum = nums[i]。
go
func maxSubArray(nums []int) int {
maxSum := nums[0]
curSum := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i]+curSum > nums[i] {
curSum += nums[i]
} else {
curSum = nums[i]
}
if maxSum < curSum {
maxSum = curSum
}
}
return maxSum
}深度优先遍历（DFS）
岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
go
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1示例 2：
go
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3题解
- 使用双层循环遍历每个格子 (i, j)。
- 当遇到陆地格子（'1'）时，说明发现了一个新岛屿，将 islandCount 增加 1。
- 通过调用 dfs 函数，从该陆地格子出发，将与其相邻的所有陆地格子标记为已访问的状态（即设置为 '0'），以避免重复计算。
go
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
row, col := len(grid), len(grid[0])
islandCount := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == '1' {
// 连在一起的陆地只记录一次
islandCount++
dfs(grid, i, j, row, col)
}
}
}
return islandCount
}
// DFS 从指定位置开始标记相邻的陆地
func dfs(grid [][]byte, i, j, row, col int) {
if i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == '0' {
return
}
// 将当前陆地标记为水，避免重复访问
grid[i][j] = '0'
// 递归访问上下左右相邻的格子
dfs(grid, i-1, j, row, col)
dfs(grid, i+1, j, row, col)
dfs(grid, i, j-1, row, col)
dfs(grid, i, j+1, row, col)
}岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0。
示例 1：
go
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。题解
和 岛屿数量 一题类似，只是需要记录最大的岛屿面积。
go
func maxAreaOfIsland(grid [][]int) int {
if len(grid) == 0 {
return 0
}
maxIsland := 0
row, col := len(grid), len(grid[0])
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == 1 {
num := 0
dfs(grid, i, j, row, col, &num)
if num > maxIsland {
maxIsland = num
}
}
}
}
return maxIsland
}
func dfs(grid [][]int, i, j, row, col int, num *int) {
if i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == 0 {
return
}
// 将遍历过的岛屿置为 0
grid[i][j] = 0
// 增加面积
*num++
dfs(grid, i-1, j, row, col, num)
dfs(grid, i+1, j, row, col, num)
dfs(grid, i, j-1, row, col, num)
dfs(grid, i, j+1, row, col, num)
}被围绕的区域
给你一个 m x n 的矩阵 board，由若干字符 'X' 和 'O' 组成，捕获所有被围绕的区域：
- 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
- 区域：连接所有 'O' 的单元格来形成一个区域。
- 围绕：如果您可以用 'X' 单元格连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来捕获被围绕的区域。
示例 1：
go
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]解释：
在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。
题解
- 标记边缘的 'O'：对于矩阵边缘上的 'O' 及其相连的 'O' 区域，先用 DFS 将它们标记为一个特殊的字符（比如 '#'），以表示这些 'O' 不会被包围。
- 转换字符：
- 在 DFS 完成后，将剩余的未标记的 'O'（即被包围的区域）转换为 'X'。
- 将标记为 '#' 的字符还原回 'O'，因为这些区域不应该被包围。
go
func solve(board [][]byte) {
if len(board) == 0 {
return
}
rows, cols := len(board), len(board[0])
// 边缘上的所有 'O' 及其相连的 'O' 标记为 '#'
// 左右边
for i := 0; i < rows; i++ {
if board[i][0] == 'O' {
dfs(board, i, 0, rows, cols)
}
if board[i][cols-1] == 'O' {
dfs(board, i, cols-1, rows, cols)
}
}
// 上下边
for j := 0; j < cols; j++ {
if board[0][j] == 'O' {
dfs(board, 0, j, rows, cols)
}
if board[rows-1][j] == 'O' {
dfs(board, rows-1, j, rows, cols)
}
}
// 遍历整个矩阵
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if board[i][j] == 'O' {
board[i][j] = 'X' // 被包围的区域变为 'X'
} else if board[i][j] == '#' {
board[i][j] = 'O' // 恢复未包围的区域
}
}
}
}
// DFS 将相连的 'O' 标记为 '#'
func dfs(board [][]byte, i, j, rows, cols int) {
if i < 0 || j < 0 || i >= rows || j >= cols || board[i][j] != 'O' {
return
}
board[i][j] = '#' // 标记为 '#'
// 向四个方向扩展
dfs(board, i+1, j, rows, cols) // 下
dfs(board, i-1, j, rows, cols) // 上
dfs(board, i, j+1, rows, cols) // 右
dfs(board, i, j-1, rows, cols) // 左
}岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地，grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 1：
go
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边题解
- 遍历网格，找到第一个陆地格子（1），然后调用外部的 dfs 函数从该格子开始计算岛屿的周长。
- 检查边界或水域情况，如果当前格子在网格边界之外或是水域（0），则周长加 1。
- 如果访问的是陆地，标记为 -1，避免重复访问。
go
func islandPerimeter(grid [][]int) int {
row, col := len(grid), len(grid[0])
perimeter := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == 1 {
dfs(grid, i, j, row, col, &perimeter)
return perimeter // 找到一个岛屿的起点后，计算完成直接返回
}
}
}
return perimeter
}
func dfs(grid [][]int, i, j, row, col int, perimeter *int) {
// 边界情况和水域的处理
if i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == 0 {
*perimeter += 1
return
}
// 如果格子已经访问过，直接返回
if grid[i][j] == -1 {
return
}
// 标记当前格子为已访问
grid[i][j] = -1
// 递归计算四个方向的周长
dfs(grid, i-1, j, row, col, perimeter) // 上
dfs(grid, i+1, j, row, col, perimeter) // 下
dfs(grid, i, j-1, row, col, perimeter) // 左
dfs(grid, i, j+1, row, col, perimeter) // 右
}广度优先遍历（BFS）
岛屿数量
题解
BFS 遍历相邻陆地：对于每个新发现的陆地，我们用 BFS 来访问所有与它相连的陆地格子。将初始的“1”放入 queue，然后逐层将相邻的“1”格子加入队列，同时标记为已访问（即改成“0”）。
go
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
islandCount := 0
// 遍历每个格子
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
// 如果遇到一个岛屿（陆地“1”），执行 BFS
if grid[i][j] == '1' {
islandCount++
bfs(grid, i, j, rows, cols)
}
}
}
return islandCount
}
// BFS 从给定的起始位置开始遍历相连的陆地格子
func bfs(grid [][]byte, i, j, rows, cols int) {
// 定义四个方向：上、下、左、右
directions := [][]int{
{-1, 0}, {1, 0}, {0, -1}, {0, 1},
}
queue := [][]int{{i, j}}
grid[i][j] = '0' // 将起始位置标记为已访问
for len(queue) > 0 {
// 取出队列中的第一个位置
curr := queue[0]
queue = queue[1:]
currRow, currCol := curr[0], curr[1]
// 遍历四个方向
for _, direction := range directions {
newRow, newCol := currRow+direction[0], currCol+direction[1]
// 检查新位置是否在网格内，且是否为陆地（“1”）
if newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1' {
grid[newRow][newCol] = '0' // 标记为已访问
queue = append(queue, []int{newRow, newCol}) // 将新位置加入队列
}
}
}
}动态规划
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
go
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
go
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶题解
动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。
由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。在以下代码中，我们初始化一个数组 dp 来存储子问题的解，它起到了与记忆化搜索中数组 mem 相同的记录作用。
go
func climbStairs(n int) int {
if n == 1 || n == 2 {
return n
}
// 初始化 dp 表，用于存储子问题的解
dp := make([]int, n+1)
// 初始状态：预设最小子问题的解
dp[1] = 1
dp[2] = 2
// 状态转移：从较小子问题逐步求解较大子问题
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
go
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
go
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。题解
状态定义：dp[i] 表示偷窃到第 i 间房屋时，能够获取的最高金额。 状态转移方程：对于每间房屋，我们可以选择偷窃它或不偷窃：
- 不偷窃第 i 间房屋：那么最高金额就是 dp[i-1]。
- 偷窃第 i 间房屋：那么最高金额就是 dp[i-2] + nums[i]（即第 i-2 间房屋的最高金额加上当前房屋的金额）。 综上，状态转移方程为：
dp[i]=max(dp[i−1],dp[i−2]+nums[i])
go
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
if n == 1 {
return nums[0]
}
dp := make([]int, n)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < n; i++ {
// 不偷/偷
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
}
return dp[n-1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下，今晚能够偷窃到的最高金额。
示例 1：
go
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：
go
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。示例 3：
go
输入：nums = [1,2,3]
输出：3题解
由于房屋是环形排列的，偷窃第一个房屋会影响最后一个房屋的选择。因此，我们可以将此问题拆分成两个线性问题：
- 情况 1：不偷窃第一个房屋（从 nums[1] 到 nums[n-1]）。
- 情况 2：不偷窃最后一个房屋（从 nums[0] 到 nums[n-2]）。
根据两种情况分别通过 dp 算法计算最高金额，最后取两种情况的最大值。
go
func rob(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
if n == 2 {
return max(nums[0], nums[1])
}
// 不偷窃第一个房屋和偷窃第一个房屋
return max(_rob(nums[1:]), _rob(nums[:n-1]))
}
func _rob(nums []int) int {
n := len(nums)
dp := make([]int, n)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < n; i++ {
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
}
return dp[n-1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root。
除了 root 之外，每栋房子有且只有一个“父”房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
给定二叉树的 root。返回在不触动警报的情况下，小偷能够盗取的最高金额。
示例 1:
go
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7示例 2:
go
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9题解
定义状态：对于每个节点，用两个值表示该节点的最大收益：
- rob(root): 表示偷当前节点的最大收益。
- notRob(root): 表示不偷当前节点的最大收益。
状态转移：
- 如果偷当前节点，那么不能偷它的左右子节点，所以收益为当前节点的值 root.Val + notRob(left) + notRob(right)。
- 如果不偷当前节点，可以选择偷或不偷左右子节点，所以收益为 max(rob(left), notRob(left)) + max(rob(right), notRob(right))。
go
func rob(root *TreeNode) int {
res := dfs(root)
return max(res[0], res[1])
}
// dfs 函数返回一个数组：
// res[0] 表示不偷当前节点的最大收益，res[1] 表示偷当前节点的最大收益
func dfs(root *TreeNode) [2]int {
if root == nil {
return [2]int{0, 0}
}
// 递归计算左右子树
left := dfs(root.Left)
right := dfs(root.Right)
// 不偷当前节点的最大收益
notRob := max(left[0], left[1]) + max(right[0], right[1])
// 偷当前节点的最大收益
rob := root.Val + left[0] + right[0]
return [2]int{notRob, rob}
}
// 辅助函数：计算最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}零钱兑换
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
go
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1示例 2：
go
输入：coins = [2], amount = 3
输出：-1示例 3：
go
输入：coins = [1], amount = 0
输出：0题解
定义状态：
- 设 dp[i][a] 为前 i 个硬币能够组成金额 a 所需的最少硬币数。
- dp[0][a] 表示不使用任何硬币时，组成金额 a 是不可能的，因此初始化为一个很大的值 max，表示无法组成该金额。
状态转移方程： 对于每个 i 和每个金额 a，我们可以选择是否使用第 i 个硬币 coins[i-1]：
- 如果不选择硬币 i，则 dp[i][a] = dp[i-1][a]。
- 如果选择硬币 i，则 dp[i][a] = dp[i][a - coins[i-1]] + 1，a - coins[i-1] 表示扣除当前选择的硬币后还所需的最小硬币数，加 1 是因为我们选择了当前硬币。
结果判断：
- 最终在 dp[n][amount] 中得到结果。如果值为 max，表示无法组成该金额，返回 -1；否则返回 dp[n][amount] 的值。
go
func coinChange(coins []int, amount int) int {
n := len(coins)
max := amount + 1
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amount+1)
}
// 状态转移：首行首列
for a := 1; a <= amount; a++ {
dp[0][a] = max
}
// 状态转移：其余行和列
for i := 1; i <= n; i++ {
for a := 1; a <= amount; a++ {
// 若超过目标金额，则不选硬币 i
if coins[i-1] > a {
dp[i][a] = dp[i-1][a]
} else {
// 不选和选硬币 i 这两种方案的较小值
dp[i][a] = min(dp[i-1][a], dp[i][a-coins[i-1]] + 1)
}
}
}
if dp[n][amount] != max {
return dp[n][amount]
}
return -1
}
func min(x, y int) int {
if x < y {
return x
}
return y
}零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
go
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1示例 2：
go
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。示例 3：
go
输入：amount = 10, coins = [10]
输出：1题解
相比于零钱兑换，本题目标是求组合数量，因此子问题变为：前 i 种硬币能够凑出金额 a 的组合数量。
当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为：dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]]。
当目标金额为 0 时，无须选择任何硬币即可凑出目标金额，因此应将首列所有 dp[i][0] 都初始化为 1。 当无硬币时，无法凑出任何 > 0 的目标金额，因此首行所有 dp[0][a] 都等于 0（默认值）。
go
func change(amount int, coins []int) int {
n := len(coins)
// 初始化 dp 表
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, amount + 1)
}
// 初始化首列
// 当目标金额为 0 时，无须选择任何硬币即可凑出目标金额
for i := 0; i <= n; i++ {
dp[i][0] = 1
}
// 状态转移：其余行和列
for i := 1; i <= n; i++ {
for a := 1; a <= amount; a++ {
if coins[i-1] > a {
// 若超过目标金额，则不选硬币 i
dp[i][a] = dp[i-1][a]
} else {
// 不选和选硬币 i 这两种方案之和
dp[i][a] = dp[i-1][a] + dp[i][a-coins[i-1]]
}
}
}
return dp[n][amount]
}买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例 1：
go
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
go
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。题解
如果第 i 天卖出股票，则最大利润为该天的股价-前面天数中最小的股价，然后与已知的最大利润比较，如果大于则更新当前最大利润的值。
go
func maxProfit(prices []int) int {
// 初始化为正无穷大
minPrice := math.MaxInt32
// 初始化最大利润为0
maxProfit := 0
for i := 0; i < len(prices); i++ {
// 更新到目前为止的最低价格
if prices[i] < minPrice {
minPrice = prices[i]
}
profit := prices[i] - minPrice
// 更新最大利润
if profit > maxProfit {
maxProfit = profit
}
}
return maxProfit
}上面的解法中我们没有使用到动态规划的典型结构，比如状态转移方程等。为了更好地展示如何用动态规划的思想来分析这个问题，我们可以描述成状态转移的方式，尽管在实现上和简单的遍历类似。
状态定义：
- dp[i]：表示在第 i 天卖出股票所能获得的最大利润。
状态转移方程：
- 对于每一天 i，我们可以选择在之前的任何一天 j（j<i）买入股票，然后在第 i 天卖出：
- dp[i]=max(dp[i−1],prices[i]−min(prices[0]...prices[i−1]))
- 其中，dp[i-1] 表示不进行交易的利润。
最终结果：
- 最大利润即为所有 dp[i] 中的最大值。
go
func maxProfit(prices []int) int {
n := len(prices)
if n == 0 {
return 0
}
dp := make([]int, n)
minPrice := prices[0]
for i := 1; i < n; i++ {
// 更新到目前为止的最低价格
if prices[i] < minPrice {
minPrice = prices[i]
}
dp[i] = max(dp[i-1], prices[i] - minPrice)
}
return dp[n-1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}买卖股票的最佳时机 II
给你一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回你能获得的最大利润。
示例 1：
go
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。示例 2：
go
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。示例 3：
go
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。题解
这题和 买卖股票的最佳时机 题类似，区别是允许在同一天买入和卖出，并且可以多次买卖股票。
方法一：贪心
- 为了获得最大利润，只需要抓住每一次价格上升的机会，即当天的价格高于前一天时，就把这段差值（利润）加入到总利润中。如果当前价格低于或等于前一天，则跳过（即当天不买卖）。
- 只要价格上升，就即时获利，而不必考虑复杂的买卖时机。因为所有连续上升段的利润都会被加到总利润中，等价于计算整个上升区间的总差值。
go
func maxProfit(prices []int) int {
totalProfit := 0
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
totalProfit += prices[i] - prices[i-1]
}
}
return totalProfit
}方法二：动态规划
定义两个状态：
dp[i][0]: 第i天交易完后 不持有股票 的最大利润。dp[i][1]: 第i天交易完后 持有股票 的最大利润。
不持有股票的状态：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
- 要么继承前一天不持有股票的状态利润。
- 要么在今天卖出股票，将昨天持有股票的利润加上今天的价格。
持有股票的状态：dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
- 要么继承前一天持有股票的状态利润。
- 要么在今天买入股票，将昨天不持有股票的利润减去今天的价格。
初始状态：
- 第 0 天不持有股票的利润为 0，即：
dp[0][0] = 0 - 第 0 天持有股票的利润为负数，即：
dp[0][1] = -prices[0]
最终答案：最后一天不持有股票的状态值 dp[n-1][0] 即为最大利润。
go
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
n := len(prices)
dp := make([][2]int, n) // dp[i][0] 表示第 i 天不持有股票的最大利润，dp[i][1] 表示第 i 天持有股票的最大利润
// 初始状态
dp[0][0] = 0 // 第 0 天不持有股票的利润是 0
dp[0][1] = -prices[0] // 第 0 天持有股票的利润是 -prices[0]
// 状态转移
for i := 1; i < n; i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) // 不持有股票的最大利润
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) // 持有股票的最大利润
}
return dp[n-1][0] // 最终返回不持有股票的最大利润
}
// 辅助函数：返回两个整数中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
示例 1：
go
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3。示例 2：
go
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3。示例 3：
go
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。题解
在这个问题中，我们使用的是动态规划来计算最长公共子序列。我们的目标是构建一个状态表 dp[i][j]，其中 dp[i][j] 表示字符串 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列的长度。
- 如果 text1[i-1] == text2[j-1]，那么这两个字符可以一起加入到公共子序列中。此时，dp[i][j] = dp[i-1][j-1] + 1，表示从 dp[i-1][j-1] 的公共子序列长度基础上，加上当前匹配的字符。
- 如果 text1[i-1] != text2[j-1]，说明当前字符不相等，我们不能同时包含这两个字符，所以我们有两个选择：
- 忽略 text1[i-1]，然后去计算 text1[0...i-2] 和 text2[0...j-1] 的最长公共子序列，这个值就是 dp[i-1][j]。
- 忽略 text2[j-1]，然后去计算 text1[0...i-1] 和 text2[0...j-2] 的最长公共子序列，这个值就是 dp[i][j-1]。
选择 较大的值，就是在这两种选择中选出最大的一种，因为我们在寻找最长的公共子序列长度。
为什么选择较大的值？
- 我们通过选择 dp[i-1][j] 或 dp[i][j-1] 中的较大值，表示在当前两个字符不匹配时，我们选择忽略一个字符，从而保持计算最长公共子序列时的递推关系。选择较大的值保证了我们能在忽略某个字符后，得到可能的最长公共子序列。
- 具体说明：假设我们正在处理 text1[i-1] 和 text2[j-1] 这两个字符，并且这两个字符不相等。我们必须决定是否：
- 忽略 text1[i-1]，继续寻找 text1[0...i-2] 和 text2[0...j-1] 的公共子序列。
- 忽略 text2[j-1]，继续寻找 text1[0...i-1] 和 text2[0...j-2] 的公共子序列。
我们选择较大的一方，因为公共子序列的长度不会因为忽略一个字符而减少，而是会继续从之前的子序列中扩展。所以，选择 dp[i-1][j] 或 dp[i][j-1] 中的较大值，能保证我们能够得到一个更长的公共子序列。
go
func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
// 创建一个二维 DP 数组
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 填充 DP 表
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1 // 字符相同，LCS长度加1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // 字符不同，取最大值
}
}
}
// 返回 LCS 的长度
return dp[m][n]
}
// 辅助函数：返回两个整数中的最大值
func max(a, b int) int {
if a > b {
return a
}
return b
}编辑距离
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
go
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例 2：
go
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')题解
我们可以使用动态规划来解决这个问题。我们构建一个二维数组 dp，其中 dp[i][j] 表示将 word1[0...i-1] 转换成 word2[0...j-1] 所需要的最少操作数。
状态转移方程
如果 word1[i-1] == word2[j-1]，那么这两个字符已经匹配，不需要任何操作。因此：
go
dp[i][j]=dp[i−1][j−1]如果 word1[i-1] != word2[j-1]，我们需要做出一个操作，考虑三种可能的操作：
dp[i-1][j-1]（替换操作）：
- 这个状态表示将
word1的第 ( i ) 个字符替换为word2的第 ( j ) 个字符的操作次数。 - 如果
word1的第 ( i ) 个字符与word2的第 ( j ) 个字符相同，那么实际上不需要替换操作，因此直接继承dp[i-1][j-1]的值。 - 如果字符不同，则需要执行一次替换操作，结果为
dp[i-1][j-1] + 1。
dp[i-1][j]（删除操作）：
- 这个状态表示删除
word1的第 ( i ) 个字符的操作次数。 - 删除后，只需考虑将
word1的前 ( i-1 ) 个字符转换为word2的前 ( j ) 个字符，因此结果为dp[i-1][j] + 1。
dp[i][j-1]（插入操作）：
- 这个状态表示在
word1中插入word2的第 ( j ) 个字符的操作次数。 - 插入后，需要将
word1的前 ( i ) 个字符转换为word2的前 ( j-1 ) 个字符，因此结果为dp[i][j-1] + 1。
此时状态转移方程为：
go
dp[i][j]=min(dp[i−1][j−1]+1,dp[i−1][j]+1,dp[i][j−1]+1)具体的代码如下：
go
func minDistance(word1 string, word2 string) int {
// 获取两个字符串的长度
m, n := len(word1), len(word2)
// 创建二维 DP 数组
// dp[i][j] 表示 word1 的前 i 个字符转换到 word2 的前 j 个字符需要的最少操作数
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 初始化第一行和第一列
// 第一行表示 word1 为空，转换到 word2 需要的操作数（即插入操作）
for j := 0; j <= n; j++ {
dp[0][j] = j
}
// 第一列表示 word2 为空，word1 转换到空串需要的操作数（即删除操作）
for i := 0; i <= m; i++ {
dp[i][0] = i
}
// 填充 DP 数组
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if word1[i-1] == word2[j-1] {
// 如果字符相同，不需要操作
dp[i][j] = dp[i-1][j-1]
} else {
// 否则取三种操作的最小值
dp[i][j] = min(
dp[i-1][j-1] + 1, // 替换
min(
dp[i-1][j] + 1, // 删除
dp[i][j-1] + 1, // 插入
),
)
}
}
}
return dp[m][n]
}
// 辅助函数：返回两个数中的较小值
func min(a, b int) int {
if a < b {
return a
}
return b
}最长递增子序列
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
go
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。示例 2：
go
输入：nums = [0,1,0,3,2,3]
输出：4示例 3：
go
输入：nums = [7,7,7,7,7,7,7]
输出：1题解
- 定义状态：定义一个 dp 数组，其中 dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。
- 状态转移方程：对于每个 i，我们遍历从 0 到 i-1 的所有元素 j，如果 nums[i] > nums[j]，则说明 nums[i] 可以接在 nums[j] 之后形成更长的递增子序列，此时更新 dp[i] 为 dp[i] = max(dp[i], dp[j] + 1)。
- 初始化：每个元素至少可以单独成为一个子序列，所以 dp[i] 初始化为 1。
- 结果：dp 数组中最大值即为最长严格递增子序列的长度。
go
func lengthOfLIS(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
dp := make([]int, n)
// 初始化：每个数字本身就是长度为1的递增子序列
for i := 0; i < n; i++ {
dp[i] = 1
}
maxLen := 1
// 对于每个位置，检查前面的所有数字
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
// 如果当前数字大于之前的数字，可以接在其后形成更长的递增子序列
if nums[i] > nums[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
maxLen = max(maxLen, dp[i])
}
return maxLen
}
func max(a, b int) int {
if a > b {
return a
}
return b
}最长重复子数组
给两个整数数组 nums1 和 nums2，返回 两个数组中公共的、长度最长的子数组的长度。
示例 1：
go
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。示例 2：
go
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5题解
动态规划思路：
- 使用二维数组 dp[i][j] 表示以下含义：nums1[0:i] 和 nums2[0:j] 的公共子数组的最大长度。
- 转移方程：如果 nums1[i-1] == nums2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
go
func findLength(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
// 定义一个二维 dp 数组
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
maxLength := 0
// 填充 dp 数组
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > maxLength {
maxLength = dp[i][j]
}
}
}
}
return maxLength
}单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
go
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
go
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。示例 3：
go
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false题解
- 定义一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以由字典中的单词拼接而成。
- 状态转移方程：如果存在一个单词 word，它属于 wordDict，并且 s[j:i] == word，同时 dp[j] 为 true，则 dp[i] 为 true。
- 初始状态：dp[0] = true，表示空字符串总是可以被拼接。
- 最终答案：dp[len(s)] 表示字符串 s 是否可以完全被拼接。
go
// 字符串是否可以由字典中的单词拼接而成
func wordBreak(s string, wordDict []string) bool {
// 将 wordDict 转换为哈希集合以加速查找
wordSet := make(map[string]bool)
for _, word := range wordDict {
wordSet[word] = true
}
// 定义 dp 数组
dp := make([]bool, len(s)+1)
dp[0] = true // 空字符串可以被拼接
// 动态规划
for i := 1; i <= len(s); i++ {
for j := 0; j < i; j++ {
if dp[j] && wordSet[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[len(s)]
}不同路径
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start”）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
问总共有多少条不同的路径？
示例 1：
go
输入：m = 3, n = 7
输出：28题解
- 定义状态：用 dp[i][j] 表示从起点到达位置 (i, j) 的路径数。
- 状态转移方程：从 (i, j) 到达 (i, j) 的路径数等于从 (i-1, j) 和 (i, j-1) 到达的路径数之和。因此 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
- 初始化：第一行和第一列的路径数都是 1，因为机器人只能一直向右或一直向下。
- 最终答案：dp[m-1][n-1] 表示从起点到达终点的路径数。
go
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
// 初始化第一行和第一列
for i := 0; i < m; i++ {
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
// 计算其他位置的路径数
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
go
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。示例 2:
go
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。题解
由于存在负数和零，子数组的最大乘积会受到符号的影响，因此需要同时跟踪当前子数组的最大值和最小值。
状态定义：
- maxProd：以当前元素结尾的子数组的最大乘积。
- minProd：以当前元素结尾的子数组的最小乘积。
状态转移方程：
- 当 nums[i] >= 0 时：
- maxProd = max(nums[i], maxProd * nums[i])
- minProd = min(nums[i], minProd * nums[i])
- 当 nums[i] < 0 时：
- maxProd = max(nums[i], minProd * nums[i])
- minProd = min(nums[i], maxProd * nums[i])
- 当 nums[i] >= 0 时：
全局最大值更新：result = max(result, maxProd)
go
func maxProduct(nums []int) int {
if len(nums) == 0 {
return 0
}
maxProd, minProd := nums[0], nums[0]
result := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] < 0 {
maxProd, minProd = minProd, maxProd // 交换
}
maxProd = max(nums[i], maxProd*nums[i])
minProd = min(nums[i], minProd*nums[i])
result = max(result, maxProd)
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
go
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4题解
- 状态定义：dp[i][j] 表示以位置 (i, j) 为右下角的最大正方形的边长。
- 状态转移方程：
- 如果 matrix[i][j] == '1'：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- 如果 matrix[i][j] == '0'：dp[i][j] = 0
- 具体解释：
- 一个以 (i, j) 为右下角的正方形，其边长受到以下条件的约束：
- (i-1, j) 的正方形是否存在（上方）。
- (i, j-1) 的正方形是否存在（左方）。
- (i-1, j-1) 的正方形是否存在（左上方）。
- 只有当这三个位置都能形成相应的正方形时，以 (i, j) 为右下角的正方形才能继续扩大，否则只能是 1x1 的正方形。
- 如果 (i, j) 是 '0'：当前位置无法构成正方形，因此 dp[i][j] = 0。
- 一个以 (i, j) 为右下角的正方形，其边长受到以下条件的约束：
go
func maximalSquare(matrix [][]byte) int {
rows, cols := len(matrix), len(matrix[0])
dp := make([][]int, rows)
for i := range dp {
dp[i] = make([]int, cols)
}
maxSide := 0
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if matrix[i][j] == '1' {
if i == 0 || j == 0 {
dp[i][j] = 1
} else {
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
}
maxSide = max(maxSide, dp[i][j])
}
}
}
return maxSide * maxSide
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}最小路径和
给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
go
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。题解
- 定义状态：dp[i][j] 表示从左上角到达位置 (i,j) 的最小路径和。
- 状态转移方程：
- 如果从左边到达 (i,j)，路径和为 dp[i][j-1] + grid[i][j]。
- 如果从上边到达 (i,j)，路径和为 dp[i-1][j] + grid[i][j]。
- 综合两者，状态转移方程为：dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]。
- 初始化：
- 第一行只能从左到右移动，dp[0][j] = dp[0][j-1] + grid[0][j]。
- 第一列只能从上到下移动，dp[i][0] = dp[i-1][0] + grid[i][0]。
- 最终结果：dp[m-1][n-1] 表示从左上角到达右下角的最小路径和。
go
func minPathSum(grid [][]int) int {
rows, cols := len(grid), len(grid[0])
dp := make([][]int, rows)
for i := range dp {
dp[i] = make([]int, cols)
}
dp[0][0] = grid[0][0]
// 初始化第一列
for i := 1; i < rows; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
// 初始化第一行
for j := 1; j < cols; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
// 填充 dp 表
for i := 1; i < rows; i++ {
for j := 1; j < cols; j++ {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
return dp[rows-1][cols-1]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}回溯
全排列
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1：
go
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
go
输入：nums = [0,1]
输出：[[0,1],[1,0]]示例 3：
go
输入：nums = [1]
输出：[[1]]题解
初始化状态与数据结构：
- 创建一个空的二维切片 res 用于存储最终结果。
- 定义一个切片 state 用来表示当前排列状态。
- 定义一个布尔切片 selected，用于记录某个元素是否被选择，以防止重复选择。
回溯函数 backtrace：回溯的核心逻辑是递归地尝试每个可能的元素组合。
- 终止条件：当 state 的长度等于 nums 的长度时，说明已生成一个完整的排列，将 state 的副本 newState 加入 res 中。
- 选择与剪枝：
- 遍历 nums 中的每个元素 choice，查看它是否已被选择（selected[i]）。
- 如果 choice 未被选择，将其加入 state，并将 selected[i] 标记为 true 表示选择了该元素。
- 递归调用 backtrace 以继续下一层排列选择。
- 回退：递归返回后，将 state 恢复到之前状态（删除最后一个选择的元素），并将 selected[i] 恢复为 false，以便后续尝试不同的排列。
go
func permute(nums []int) [][]int {
res := make([][]int, 0)
state := make([]int, 0)
selected := make([]bool, len(nums))
backtrace(nums, &state, &selected, &res)
return res
}
func backtrace(nums []int, state *[]int, selected *[]bool, res *[][]int) {
// 当状态长度等于元素数量时，记录解
if len(*state) == len(nums) {
newState := append([]int{}, *state...)
*res = append(*res, newState)
}
// 遍历所有选择
for i :=0; i < len(nums); i++ {
choice := nums[i]
// 剪枝：不允许重复选择元素
if !(*selected)[i] {
// 尝试：做出选择，更新状态
(*selected)[i] = true
*state = append(*state, choice)
// 进行下一轮选择
backtrace(nums, state, selected, res)
// 回退：撤销选择，恢复到之前的状态
(*selected)[i] = false
*state = (*state)[:len(*state)-1]
}
}
}- nums：在递归中并未修改 nums，所以可以直接按值传递。
- state 和 selected：递归过程中会对 state 和 selected 进行修改，因此仍需要按引用传递，以保证每层递归共享同一份数据。
- res：res 是用于记录结果的切片，它需要通过指针传递，以确保修改会影响到最终的结果。
全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
示例 1：
go
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]示例 2：
go
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]题解
在全排列的基础上，在每一轮选择中开启一个哈希集合 duplicated ，用于记录该轮中已经尝试过的元素。
go
func permuteUnique(nums []int) [][]int {
state := make([]int, 0)
res := make([][]int, 0)
selected := make([]bool, len(nums))
backtrace(nums, &state, &selected, &res)
return res
}
func backtrace(nums []int, state *[]int, selected *[]bool, res *[][]int) {
// 当状态长度等于元素数量时，记录解
if len(*state) == len(nums) {
newState := append([]int{}, *state...)
*res = append(*res, newState)
}
// 记录该轮中已经尝试过的元素
duplicated := make(map[int]struct{})
// 遍历所有选择
for i := 0; i < len(nums); i++ {
choice := nums[i]
// 剪枝：不允许重复选择元素且不允许重复选择相等元素
if _, ok := duplicated[choice]; !ok && !(*selected)[i] {
// 尝试：做出选择，更新状态
// 记录选择过的元素值
(*selected)[i] = true
duplicated[choice] = struct{}{}
*state = append(*state, choice)
// 进行下一轮选择
backtrace(nums, state, selected, res)
// 回退：撤销选择，恢复到之前的状态
(*selected)[i] = false
*state = (*state)[:len(*state)-1]
}
}
}复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。
示例 1：
go
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]示例 2：
go
输入：s = "0000"
输出：["0.0.0.0"]示例 3：
go
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]题解
这个题目可以使用回溯算法来解决。具体的思路是将字符串 s 划分为四段，每段代表一个有效的 IP 地址段（即一个整数，范围在 0 到 255 之间，且不允许前导 0）。如果找到一个合法的划分，就将其加入结果集。代码的步骤如下：
- 定义一个递归函数来构建 IP 地址的每一段。
- 如果已经构建了 4 段并且遍历完字符串，就将当前 IP 地址加入结果集。
- 如果剩余的字符太多或太少，直接返回。
- 对每一段，尝试选择 1 到 3 个字符作为当前段，并判断是否有效。
- 继续递归构建下一段。
go
func restoreIpAddresses(s string) []string {
var result []string
backtrack(s, 0, []string{}, &result)
return result
}
// backtrack 函数用于递归构建 IP 地址的每一段
func backtrack(s string, start int, path []string, result *[]string) {
// 如果已经有 4 段，并且已经用完了字符串的所有字符
if len(path) == 4 {
if start == len(s) {
*result = append(*result, fmt.Sprintf("%s.%s.%s.%s", path[0], path[1], path[2], path[3]))
}
return
}
// 剩下的字符长度不合适
if len(s)-start < 4-len(path) || len(s)-start > 3*(4-len(path)) {
return
}
// 尝试从 start 开始，取 1 到 3 位字符
for i := 1; i <= 3; i++ {
// 如果剩余字符不足 i 位，直接跳出
if start+i > len(s) {
break
}
segment := s[start : start+i]
// 检查 segment 是否是合法的 IP 地址段
if isValid(segment) {
backtrack(s, start+i, append(path, segment), result)
}
}
}
// isValid 函数用于检查一个字符串是否是合法的 IP 地址段
func isValid(segment string) bool {
if len(segment) > 1 && segment[0] == '0' { // 不能有前导零
return false
}
num, err := strconv.Atoi(segment)
if err != nil || num < 0 || num > 255 { // 必须在 0 到 255 之间
return false
}
return true
}子集
给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例 1：
go
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2：
go
输入：nums = [0]
输出：[[],[0]]题解
在回溯的过程中，每次递归时，我们都通过 append(current, nums[i]) 来选择当前元素 nums[i] 并进入下一层递归，生成包含当前元素的子集。而一旦递归结束，回到当前层时，我们需要撤销当前的选择，即从 current 中移除最后添加的元素。
由于 current 切片是引用类型，每次在回溯时都可能被修改，因此我们需要通过 append([]int{}, current...) 生成当前子集的一个独立副本，而不是直接将引用添加到结果中。
go
func subsets(nums []int) [][]int {
var result [][]int
var current []int
backtrack(nums, 0, current, &result)
return result
}
func backtrack(nums []int, start int, current []int, result *[][]int) {
// 先把当前的子集加入到结果中
subset := append([]int{}, current...) // 拷贝当前子集
*result = append(*result, subset)
// 从 start 开始，逐个尝试包含下一个元素
for i := start; i < len(nums); i++ {
current = append(current, nums[i]) // 包含当前元素
backtrack(nums, i+1, current, result) // 继续搜索下一个元素
current = current[:len(current)-1] // 回溯，移除当前元素，也就是不选择当前元素
}
}括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 1：
go
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
go
输入：n = 1
输出：["()"]题解
这个可以通过回溯来解决，在构建括号组合时，每次都有两种选择：
- 添加左括号 (，前提是当前左括号的数量小于 n。
- 添加右括号 )，前提是当前右括号的数量小于当前的左括号数量（这保证了括号的有效性）。
我们可以通过回溯算法不断尝试并生成合法的括号组合，直到达到 n 对括号为止。
go
func generateParenthesis(n int) []string {
var result []string
var current string
backtrack(n, n, current, &result)
return result
}
func backtrack(left int, right int, current string, result *[]string) {
// 如果当前组合已经是一个有效的括号组合，且左括号和右括号都已用完
if left == 0 && right == 0 {
*result = append(*result, current)
return
}
// 选择添加左括号 '('，前提是左括号数量还没有用完
if left > 0 {
backtrack(left-1, right, current+"(", result)
}
// 选择添加右括号 ')'，前提是右括号数量还没有用完，且右括号数量不小于左括号数量
if right > left {
backtrack(left, right-1, current+")", result)
}
}组合总和
给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
示例 1：
go
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。题解
- backtrack 是回溯算法的核心函数：
- start 控制从哪个位置开始选择数字（避免重复组合）。
- target 表示当前还需要凑齐的目标值。
- 每次递归中，遍历从 start 开始的 candidates 数组元素，选择一个数字，并递归减去目标值。如果目标值变成 0，说明找到一个有效的组合，将它添加到结果中。
- 最后通过复制 combination 数组来避免引用问题，并返回所有符合条件的组合。
go
func combinationSum(candidates []int, target int) [][]int {
var res [][]int
var combination []int
// 调用回溯函数
backtrack(candidates, target, 0, combination, &res)
return res
}
// 回溯函数
func backtrack(candidates []int, target int, start int, combination []int, res *[][]int) {
// 如果目标为 0，则说明找到一个有效组合
if target == 0 {
// 需要复制一份 combination，因为它是引用类型
combinationCopy := make([]int, len(combination))
copy(combinationCopy, combination)
*res = append(*res, combinationCopy)
return
}
// 遍历 candidates 数组
for i := start; i < len(candidates); i++ {
// 如果当前数字大于目标值，就不需要再继续往下找了
if candidates[i] > target {
continue
}
// 选择当前数字并继续递归
combination = append(combination, candidates[i])
backtrack(candidates, target-candidates[i], i, combination, res) // 允许重复选择同一个数字
combination = combination[:len(combination)-1] // 回溯
}
}滑动窗口
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
go
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7题解
- 使用一个双端队列 q 来存储当前窗口内的元素索引，保持队列中的索引对应的值按递减顺序排列。
- 当新元素进入时，从队尾移除所有小于新元素的索引，以确保队列中只保留可能成为最大值的元素。
- 每当窗口移动时，检查队首索引是否已经离开窗口。如果离开，则从队列中移除。
- 队首元素即为当前窗口的最大值。
go
func maxSlidingWindow(nums []int, k int) []int {
ans := make([]int, 0, len(nums)-k+1) // 预先分配好空间
q := []int{}
for i, x := range nums {
// 1. 入
// 从队尾移除所有小于新元素的索引
for len(q) > 0 && nums[q[len(q)-1]] <= x {
q = q[:len(q)-1] // 维护 q 的单调性
}
q = append(q, i) // 入队
// 2. 出
if i-q[0] >= k { // 队首已经离开窗口了
q = q[1:] // Go 的切片是 O(1) 的
}
// 3. 记录答案
// 例如 k = 3，则从第 3 个往后才开始记录答案
if i >= k-1 {
// 由于队首到队尾单调递减，所以窗口最大值就是队首
ans = append(ans, nums[q[0]])
}
}
return ans
}参考资料：
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例 1：
go
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
go
输入：target = 4, nums = [1,4,4]
输出：1示例 3：
go
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0题解
- 双指针滑动窗口：
- 用 left 和 right 表示当前窗口的左右边界。
- sum 用来计算当前窗口中元素的总和。
- 扩大窗口：每次将 nums[right] 加入到 sum 中，并检查总和是否大于等于 target。
- 收缩窗口：当 sum >= target 时，记录当前窗口长度，并尝试通过移动 left 来缩小窗口，同时更新最小长度。
go
func minSubArrayLen(target int, nums []int) int {
left, sum := 0, 0
minLength := math.MaxInt32
for right := 0; right < len(nums); right++ {
sum += nums[right]
// 收缩窗口，直到当前窗口的总和小于 target
for sum >= target {
minLength = min(minLength, right-left+1)
sum -= nums[left]
left++
}
}
if minLength == math.MaxInt32 {
return 0
}
return minLength
}
func min(a, b int) int {
if a < b {
return a
}
return b
}最小覆盖子串
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。
注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
go
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。题解
定义数据结构：
- 用两个哈希表：target 和 window。
- target：记录字符串 t 中每个字符的需求次数。
- window：记录滑动窗口中各字符的出现次数。
- 定义两个指针 left 和 right，表示窗口的左右边界，初始都为 0。
- 滑动窗口逻辑：
- 移动 right 指针，扩展窗口，增加 window 中的字符计数。
- 检查 window 是否满足 target 的条件：如果满足，记录当前窗口长度，并尝试移动 left 收缩窗口，尽量找到更小的窗口。
- 判断满足条件：
- 使用变量 valid 记录当前窗口中满足 target 的字符种类数量。
- 当 valid 等于 target 的键数时，说明当前窗口包含了 t 所有字符。
- 返回结果：
- 在所有满足条件的窗口中，返回长度最小的窗口。
- 如果找不到，返回空字符串。
go
func minWindow(s string, t string) string {
if len(s) < len(t) {
return ""
}
// 记录目标字符出现的次数
target := make(map[byte]int)
for i := 0; i < len(t); i++ {
target[t[i]]++
}
// 滑动窗口中字符的频率
window := make(map[byte]int)
// 用于滑动窗口
left, right := 0, 0
valid := 0 // 记录窗口中满足条件的字符个数
start := 0 // 最小窗口的起始位置
minLen := len(s) + 1 // 初始化为不可能的最大值，表示尚未找到窗口
for right < len(s) {
// 扩大窗口，加入右侧字符
c := s[right]
right++
// 如果当前字符在目标字符中，更新窗口中的字符频率
if _, ok := target[c]; ok {
window[c]++
if window[c] == target[c] {
valid++
}
}
// 当窗口包含了所有目标字符时，尝试缩小窗口
for valid == len(target) {
// 更新最小窗口
if right-left < minLen {
start = left // 记录当前最小窗口的起始位置
minLen = right - left // 更新最小窗口长度
}
// 缩小窗口，移除左侧字符
d := s[left]
left++
// 如果移除的字符是目标字符，更新窗口频率
if _, ok := target[d]; ok {
if window[d] == target[d] {
valid--
}
window[d]--
}
}
}
// 如果没有找到有效的窗口，返回空字符串
if minLen == len(s)+1 {
return ""
}
// 根据记录的起始位置和最小长度提取结果
return s[start : start+minLen]
}字符串
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
go
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
go
输入：s = "cbbd"
输出："bb"题解
使用中心扩展法，从字符串的每个字符出发，向两侧扩展，检查是否构成回文。每个字符可以有两种情况：
- 以该字符为中心（奇回文子串）。
- 以该字符与其后一个字符之间的空隙为中心（偶回文子串）。
go
// 辅助函数，从指定的中心扩展找到最长的回文子串
func expandAroundCenter(s string, left, right int) string {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
// 返回扩展后的回文子串
// 当扩展结束时，left 和 right 的值表示的是扩展后的超出范围的索引。
// 因此，正确的回文子串应从 left + 1（回文串的起始位置）到 right（回文串的结束位置）之间。
return s[left+1 : right]
}
// 主函数，找到最长的回文子串
func longestPalindrome(s string) string {
if len(s) == 0 {
return ""
}
longest := ""
for i := 0; i < len(s); i++ {
// 以 s[i] 为中心的回文子串
oddPalindrome := expandAroundCenter(s, i, i)
// 以 s[i] 和 s[i+1] 为中心的回文子串
evenPalindrome := expandAroundCenter(s, i, i+1)
// 更新最长回文子串
if len(oddPalindrome) > len(longest) {
longest = oddPalindrome
}
if len(evenPalindrome) > len(longest) {
longest = evenPalindrome
}
}
return longest
}字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下：
- 空格：读入字符串并丢弃无用的前导空格（
" "）。 - 符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
- 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
- 舍入：如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1 。
返回整数作为最终结果。
示例 1：
go
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
带下划线线的字符是所读的内容，插入符号是当前读入位置。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："42"（读入 "42"）
^示例 2：
go
输入：s = " -042"
输出：-42
解释：
第 1 步：" -042"（读入前导空格，但忽视掉）
^
第 2 步：" -042"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步：" -042"（读入 "042"，在结果中忽略前导零）
^示例 3：
go
输入：s = "1337c0d3"
输出：1337
解释：
第 1 步："1337c0d3"（当前没有读入字符，因为没有前导空格）
^
第 2 步："1337c0d3"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："1337c0d3"（读入 "1337"；由于下一个字符不是一个数字，所以读入停止）
^示例 4：
go
输入：s = "0-1"
输出：0
解释：
第 1 步："0-1" (当前没有读入字符，因为没有前导空格)
^
第 2 步："0-1" (当前没有读入字符，因为这里不存在 '-' 或者 '+')
^
第 3 步："0-1" (读入 "0"；由于下一个字符不是一个数字，所以读入停止)
^示例 5：
go
输入：s = "words and 987"
输出：0
解释：
读取在第一个非数字字符“w”处停止。题解
go
func myAtoi(s string) int {
// Step 1: 去掉前导空格
i := 0
for i < len(s) && s[i] == ' ' {
i++
}
// Step 2: 处理符号
sign := 1
if i < len(s) && s[i] == '-' {
sign = -1
i++
} else if i < len(s) && s[i] == '+' {
i++
}
// Step 3: 转换数字并跳过前置零
result := 0
for i < len(s) && s[i] >= '0' && s[i] <= '9' {
digit := int(s[i] - '0')
// 检查是否会溢出
// 2147483647 是 32 位有符号整数的最大值（math.MaxInt32），因此需要确保最后一位数字不大于 7
if result > math.MaxInt32/10 || (result == math.MaxInt32/10 && digit > 7) {
if sign == 1 {
return math.MaxInt32
} else {
return math.MinInt32
}
}
result = result*10 + digit
i++
}
// Step 4: 返回最终结果
return result * sign
}字符串相加
给定两个字符串形式的非负整数 num1 和 num2，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。
示例 1：
go
输入：num1 = "11", num2 = "123"
输出："134"示例 2：
go
输入：num1 = "456", num2 = "77"
输出："533"示例 3：
go
输入：num1 = "0", num2 = "0"
输出："0"题解
可以通过模拟加法运算的方式逐位相加两个字符串表示的数字，从最低位（即字符串末尾）开始相加，并维护一个进位。
go
func addStrings(num1 string, num2 string) string {
i, j := len(num1)-1, len(num2)-1 // 从末尾开始
carry := 0 // 初始化进位
result := "" // 结果字符串
for i >= 0 || j >= 0 || carry > 0 { // 遍历 num1 和 num2 直到所有位数都处理完，并处理最后的进位
n1, n2 := 0, 0
if i >= 0 { // 取 num1 当前位的数字
n1 = int(num1[i] - '0')
i--
}
if j >= 0 { // 取 num2 当前位的数字
n2 = int(num2[j] - '0')
j--
}
sum := n1 + n2 + carry // 当前位的和
carry = sum / 10 // 更新进位
result = string(sum%10+'0') + result // 将当前位的结果加入结果字符串
}
return result
}字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
go
输入: num1 = "2", num2 = "3"
输出: "6"示例 2:
go
输入: num1 = "123", num2 = "456"
输出: "56088"题解
- 乘法规则：我们可以通过模拟竖式乘法的方式来计算两个数的乘积。每一位相乘，然后根据位数位置将结果加到最终结果中。
- 位置管理：由于每一位相乘的结果需要根据其位数偏移，我们使用一个数组来保存每一位的乘积结果。
- 进位处理：处理完每一位后，我们需要处理进位情况。
- 结果转换：最后将数组中的结果拼接成一个字符串。
go
func multiply(num1 string, num2 string) string {
// 如果其中一个数字是"0"，直接返回"0"
if num1 == "0" || num2 == "0" {
return "0"
}
// 结果最大长度不超过 num1 和 num2 长度之和
result := make([]int, len(num1) + len(num2))
// 逆序遍历 num1 和 num2，进行逐位相乘
for i := len(num1) - 1; i >= 0; i-- {
for j := len(num2) - 1; j >= 0; j-- {
// 计算当前位相乘的结果
mul := int(num1[i]-'0') * int(num2[j]-'0')
// 存储相乘结果到正确的位置
p1, p2 := i + j, i + j + 1
sum := mul + result[p2]
result[p2] = sum % 10
result[p1] += sum / 10
}
}
// 处理结果数组中的进位，转换成字符串
// 这里我们直接拼接结果
res := ""
for _, num := range result {
if !(len(res) == 0 && num == 0) { // 跳过前导零
res += fmt.Sprintf("%d", num)
}
}
return res
}比较版本号
给你两个版本号字符串 version1 和 version2，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值是它转换为整数并忽略前导零。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。
返回规则如下：
- 如果 version1 < version2 返回 -1，
- 如果 version1 > version2 返回 1，
- 除此之外返回 0。
示例 1：
go
输入：version1 = "1.2", version2 = "1.10"
输出：-1
解释：
version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2 < 10，所以 version1 < version2。示例 2：
go
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：
忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。示例 3：
go
输入：version1 = "1.0", version2 = "1.0.0.0"
输出：0
解释：
version1 有更少的修订号，每个缺失的修订号按 "0" 处理。题解
我们可以将版本号按照点号分割成修订号，然后从左到右比较两个版本号的相同下标的修订号。在比较修订号时，需要将字符串转换成整数进行比较。注意根据题目要求，如果版本号不存在某个下标处的修订号，则该修订号视为 0。
go
func compareVersion(version1, version2 string) int {
v1 := strings.Split(version1, ".")
v2 := strings.Split(version2, ".")
for i := 0; i < len(v1) || i < len(v2); i++ {
x, y := 0, 0
if i < len(v1) {
x, _ = strconv.Atoi(v1[i])
}
if i < len(v2) {
y, _ = strconv.Atoi(v2[i])
}
if x > y {
return 1
}
if x < y {
return -1
}
}
return 0
}反转字符串中的单词
给你一个字符串 s，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
go
输入：s = "the sky is blue"
输出："blue is sky the"示例 2：
go
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。示例 3：
go
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。题解
使用 strings.Fields 函数分割字符串为单词切片，自动处理多个空格，以及前导和尾随空格。然后反转切片，再将切片合并成字符串。
go
func reverseWords(s string) string {
// 分割字符串为单词切片，自动处理多个空格，以及前导和尾随空格
words := strings.Fields(s)
n := len(words)
for i :=0 ; i < n / 2;i++ {
words[i], words[n-1-i] = words[n-1-i],words[i]
}
return strings.Join(words, " ")
}最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
go
输入：strs = ["flower","flow","flight"]
输出："fl"示例 2：
go
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。题解
- 假设第一个字符串是公共前缀的候选前缀，然后逐一与数组中的其他字符串进行比较。
- 如果当前字符串的长度小于第一个字符串，或者当前字符不匹配，返回已匹配的公共前缀。
go
func longestCommonPrefix(strs []string) string {
ans := ""
pivot := strs[0]
// 遍历 pivot 字符串的每个字符
for i := 0; i < len(pivot); i++ {
v := pivot[i]
// 遍历 strs 中的其他字符串
for j := 1; j < len(strs); j++ {
// 如果当前字符串的长度小于或等于 i，或者当前字符不匹配，返回已匹配的 ans
if len(strs[j]) <= i || strs[j][i] != v {
return ans
}
}
// 如果匹配，继续拼接结果
ans += string(v)
}
return ans
}最大数
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
go
输入：nums = [10,2]
输出："210"示例 2：
go
输入：nums = [3,30,34,5,9]
输出："9534330"题解
- 字符串比较规则：自定义排序时，将 a 和 b 组合成 ab 和 ba，选择较大的组合来决定顺序。
- 首位为 0 的特殊处理：如果排序后第一个字符是 0，意味着所有数字均为 0，直接返回 "0"。
go
func largestNumber(nums []int) string {
// 将整数数组转换为字符串数组
strs := make([]string, len(nums))
for i, num := range nums {
strs[i] = strconv.Itoa(num)
}
// 自定义排序规则
sort.Slice(strs, func(i, j int) bool {
return strs[i]+strs[j] > strs[j]+strs[i]
})
// 排序后检查首位是否为“0”，如果是，直接返回“0”
if strs[0] == "0" {
return "0"
}
// 拼接字符串
result := ""
for _, str := range strs {
result += str
}
return result
}基本计算器 II
给你一个字符串表达式 s，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
go
输入：s = "3+2*2"
输出：7示例 2：
go
输入：s = " 3/2 "
输出：1示例 3：
go
输入：s = " 3+5 / 2 "
输出：5题解
初始化和预处理：
- 去掉字符串中的空格。
- 定义一个栈
stack来存储运算符和操作数。 - 定义一个变量
currentNum来记录当前的数字。 - 定义一个变量
sign来记录当前的符号，初始为'+'。
遍历字符串：
- 如果遇到数字，更新
currentNum，处理多位数字。 - 如果遇到运算符（
+，-，*，/）或到达字符串末尾：- 根据前一个符号和
currentNum的值，执行对应操作：'+'：将currentNum入栈。'-'：将-currentNum入栈。'*'：将栈顶元素与currentNum相乘后更新栈顶。'/'：将栈顶元素与currentNum整除后更新栈顶。
- 更新符号为当前符号，并将
currentNum置为 0。
- 根据前一个符号和
- 如果遇到括号：
- 遇到
'('，递归调用计算子表达式，直到遇到对应的')'。 - 将子表达式结果作为一个整体处理。
- 遇到
- 如果遇到数字，更新
计算结果：
- 遍历栈，累加所有元素，得到最终结果。
go
func calculate(s string) int {
var stack []int
currentNum := 0
sign := '+'
n := len(s)
for i := 0; i < n; i++ {
ch := s[i]
// 如果是数字，更新 currentNum
if ch >= '0' && ch <= '9' {
currentNum = currentNum*10 + int(ch-'0')
}
// 如果是操作符或到达末尾，执行当前运算
if ch == '+' || ch == '-' || ch == '*' || ch == '/' || i == n-1 {
if sign == '+' {
stack = append(stack, currentNum)
} else if sign == '-' {
stack = append(stack, -currentNum)
} else if sign == '*' {
stack[len(stack)-1] *= currentNum
} else if sign == '/' {
stack[len(stack)-1] /= currentNum
}
sign = rune(ch) // 更新符号
currentNum = 0
}
}
// 计算栈中的结果
result := 0
for _, num := range stack {
result += num
}
return result
}基本计算器
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval()。
示例 1：
go
输入：s = "1 + 1"
输出：2示例 2：
go
输入：s = " 2-1 + 2 "
输出：3示例 3：
go
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23题解
初始化：
- 用栈
stack来存储之前的运算结果和符号。 - 使用变量
currentNum表示当前的数字。 - 使用变量
sign表示当前的符号，初始为1（表示正号）。 - 使用变量
result来保存当前计算结果。
- 用栈
遍历字符串：
- 如果遇到数字：累积到
currentNum中，处理多位数字。 - 如果遇到符号（
+或-）：- 根据
sign将currentNum加入到result中。 - 更新
sign为1或-1，分别对应正号或负号。 - 将
currentNum重置为 0。
- 根据
- 如果遇到左括号
(：- 将当前的
result和sign压入栈中，并重置result为 0 和sign为 1，开始新的子表达式计算。
- 将当前的
- 如果遇到右括号
)：- 将当前的
result更新为stack.pop()的结果乘以stack.pop()的符号（对应最近的子表达式结果）。
- 将当前的
- 忽略空格。
- 如果遇到数字：累积到
处理结束：
- 遍历结束后，将最后一个
currentNum根据sign加入到result中。
- 遍历结束后，将最后一个
go
func calculate(s string) int {
stack := []int{}
result := 0
currentNum := 0
sign := 1 // 初始为正号
for i := 0; i < len(s); i++ {
ch := s[i]
if ch >= '0' && ch <= '9' { // 处理数字
currentNum = currentNum*10 + int(ch-'0')
} else if ch == '+' { // 遇到 '+'
result += sign * currentNum
sign = 1
currentNum = 0
} else if ch == '-' { // 遇到 '-'
result += sign * currentNum
sign = -1
currentNum = 0
} else if ch == '(' { // 遇到 '('
stack = append(stack, result)
stack = append(stack, sign)
result = 0
sign = 1
} else if ch == ')' { // 遇到 ')'
result += sign * currentNum
currentNum = 0
result *= stack[len(stack)-1] // 恢复符号
stack = stack[:len(stack)-1]
result += stack[len(stack)-1] // 恢复结果
stack = stack[:len(stack)-1]
}
}
// 将最后一个数字加到结果中
result += sign * currentNum
return result
}数学
最小面积矩形
给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。
示例 1：
go
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4示例 2：
go
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2解法：哈希表（Set） + 枚举
- 使用哈希集合存储所有点，以便快速查找是否存在某个坐标点。
- 枚举任意两个不同的点
(x1, y1)和(x2, y2)：- 如果这两个点具有 不同的 x 坐标，则它们可以成为矩形的 对角线上的两个点。
- 计算 另两个点 是否在集合中
(x1, y2)和(x2, y1)。 - 如果这四个点都存在，则计算矩形面积
(|x1 - x2| * |y1 - y2|)并更新最小值。
go
func minAreaRect(points [][]int) int {
// 1. 用 map 作为 Set 存储所有点，方便快速查找
pointSet := make(map[[2]int]bool)
for _, p := range points {
pointSet[[2]int{p[0], p[1]}] = true
}
minArea := math.MaxInt32
n := len(points)
// 2. 枚举所有点对 (x1, y1) 和 (x2, y2)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
x1, y1 := points[i][0], points[i][1]
x2, y2 := points[j][0], points[j][1]
// 3. 确保它们的 x 坐标不同，否则不能构成矩形的对角线
if x1 != x2 && y1 != y2 {
// 4. 检查剩下的两个点是否存在
if pointSet[[2]int{x1, y2}] && pointSet[[2]int{x2, y1}] {
// 5. 计算面积并更新最小值
area := abs(x1-x2) * abs(y1-y2)
if area < minArea {
minArea = area
}
}
}
}
}
// 6. 如果 minArea 仍是初始值，说明没有矩形，返回 0
if minArea == math.MaxInt32 {
return 0
}
return minArea
}
// 计算绝对值
func abs(a int) int {
if a < 0 {
return -a
}
return a
}2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true；否则，返回 false。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
go
输入：n = 1
输出：true
解释：20 = 1示例 2：
go
输入：n = 16
输出：true
解释：24 = 16示例 3：
go
输入：n = 3
输出：false理解 (n & (n - 1)) == 0 的原理
这个表达式用于 判断 n 是否是 2 的幂，因为 2 的幂的二进制表示中只有一个 1，其余都是 0。
位运算 n & (n - 1)
n - 1会把n的最低位的1变成0，并把后面的0变成1。n & (n - 1)则会清除n最低位的1，如果结果是0，说明n只有 一个1，即n是2的幂。
go
func isPowerOfTwo(n int) bool {
if n <= 0 {
return false
}
return (n & (n - 1)) == 0
}示例分析示例 1：n = 8（1000）
go
n = 1000 (8)
n - 1 = 0111 (7)
----------------
n & (n - 1) = 0000 (0) ✅→ 0 说明 8 是 2 的幂。
### [223.矩形面积](https://leetcode.cn/problems/rectangle-area/description/)
给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直的矩形，请你计算并返回两个矩形覆盖的总面积。
每个矩形由其左下顶点和右上顶点坐标表示：
- 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
- 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。
示例 1：
```go
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45核心思路：总面积 - 重叠面积
go
func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
// 计算两个矩形的面积
area1 := (ax2 - ax1) * (ay2 - ay1)
area2 := (bx2 - bx1) * (by2 - by1)
// 计算重叠区域
width := max(0, min(ax2, bx2) - max(ax1, bx1))
height := max(0, min(ay2, by2) - max(ay1, by1))
overlapArea := width * height
return area1 + area2 - overlapArea
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}整数反转
给你一个 32 位的有符号整数 x，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
go
输入：x = 123
输出：321示例 2：
go
输入：x = -123
输出：-321示例 3：
go
输入：x = 120
输出：21示例 4：
go
输入：x = 0
输出：0题解
循环处理每一位数字：
- x % 10 获取 x 的最低位。
- ans = ans*10 + x%10 将 ans 向左移动一位并加上最低位的数字（实现反转效果）。
- x /= 10 将 x 去掉最低位。
go
func reverse(x int) int {
ans := 0
for x != 0 {
// 提前判断，避免下一次计算 * 10，整数溢出
if ans < math.MinInt32/10 || ans > math.MaxInt32/10 {
return 0
}
ans = ans*10 + x%10
x /= 10
}
return ans
}回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true；否则，返回 false。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
示例 1：
go
输入：x = 121
输出：true示例 2：
go
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3：
go
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。题解
将整数反转一半，然后与原始数字进行比较是否相等。
go
func isPalindrome(x int) bool {
// 负数或者个位数为 0 时，不是回文数
if x < 0 || x != 0 && x%10 == 0 {
return false
}
// 当原始数字小于或等于反转后的数字时，表示已经反转了一半的数字
reverseNum := 0
for reverseNum < x {
reverseNum = reverseNum*10 + x%10
x /= 10
}
// 偶数位数和奇数位数
return reverseNum == x || reverseNum/10 == x
}x 的平方根
给你一个非负整数 x，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5)。
示例 1：
go
输入：x = 4
输出：2示例 2：
go
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。题解
要实现一个非负整数的平方根计算，并返回整数部分，可以使用二分查找法。这种方法基于以下观察：
- 如果
且 ，那么 就是 的整数平方根。 - 二分查找法通过缩小范围快速找到满足条件的
。
- 定义搜索范围：
- 如果
是 或 ，直接返回 。 - 否则，搜索范围为
。
- 如果
- 进行二分查找：
- 取中点
。 - 如果
且 ，返回 。 - 如果
，调整右边界。 - 如果
，调整左边界。
- 取中点
- 返回结果：
- 最终搜索完成时，左边界指向的就是整数平方根。
go
func mySqrt(x int) int {
if x == 0 || x == 1 {
return x
}
// 二分查找范围
left, right := 1, x
var result int
for left <= right {
mid := left + (right-left)/2
// 检查 mid 是否是平方根
if mid*mid == x {
return mid
} else if mid*mid < x {
// 如果 mid 的平方小于 x，可能是解
result = mid
left = mid + 1
} else {
// 如果 mid 的平方大于 x，调整右边界
right = mid - 1
}
}
return result
}用 Rand7() 实现 Rand10()
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
示例 1:
go
输入: 1
输出: [2]示例 2:
go
输入: 2
输出: [2,8]示例 3:
go
输入: 3
输出: [3,8,10]题解
我们可以通过构建一个 新的均匀分布 来实现 rand10()。为了实现这一点，我们首先可以利用 rand7() 来生成一个更大的数字范围。然后，我们可以通过映射和重采样的方式使结果均匀地落在 [1, 10] 范围内。
go
func rand10() int {
for {
// 使用 rand7 两次生成一个范围为 [0, 48] 的随机数
num := (rand7() - 1) * 7 + (rand7() - 1)
// 仅当 num 在 [0, 39] 范围内时，我们可以均匀映射到 [1, 10]
if num < 40 {
return num%10 + 1 // 映射到 [1, 10]
}
// 否则重新生成
}
}数组
螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1：
go
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]示例 2：
go
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]题解
我们可以定义四个边界 top、bottom、left 和 right 来限定当前遍历的区域，并按顺时针依次遍历上、右、下、左四条边，每遍历完一条边就收缩相应边界，逐层向内移动。
在收缩边界时，需检查是否还有未遍历的行或列，以防重复遍历或数组越界。
go
func spiralOrder(matrix [][]int) []int {
if len(matrix) == 0 {
return []int{}
}
var result []int
top, bottom := 0, len(matrix)-1
left, right := 0, len(matrix[0])-1
for top <= bottom && left <= right {
// 从左到右遍历上边
for i := left; i <= right; i++ {
result = append(result, matrix[top][i])
}
top++
// 从上到下遍历右边
for i := top; i <= bottom; i++ {
result = append(result, matrix[i][right])
}
right--
// 确保还有行或列需要遍历
if top <= bottom {
// 从右到左遍历下边
for i := right; i >= left; i-- {
result = append(result, matrix[bottom][i])
}
bottom--
}
if left <= right {
// 从下到上遍历左边
for i := bottom; i >= top; i-- {
result = append(result, matrix[i][left])
}
left++
}
}
return result
}合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
go
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2：
go
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。题解
如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的：
我们用数组 merged 存储最终的答案。
首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
- 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
- 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
go
func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return [][]int{}
}
// 1. 按照区间起始位置排序
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
// 2. 初始化结果数组
merged := [][]int{intervals[0]}
// 3. 遍历区间
for i := 1; i < len(intervals); i++ {
last := merged[len(merged)-1]
current := intervals[i]
// 检查是否有重叠
if current[0] <= last[1] {
// 合并区间
last[1] = max(last[1], current[1])
merged[len(merged)-1] = last
} else {
// 没有重叠，直接添加到结果数组
merged = append(merged, current)
}
}
return merged
}
func max(a, b int) int {
if a > b {
return a
}
return b
}下一个排列
整数数组的一个排列就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。
如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2]。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须原地修改，只允许使用额外常数空间。
示例 1：
go
输入：nums = [1,2,3]
输出：[1,3,2]示例 2：
go
输入：nums = [3,2,1]
输出：[1,2,3]示例 3：
go
输入：nums = [1,1,5]
输出：[1,5,1]题解
1. 从后往前找到第一个递减的位置
从右到左遍历数组，找到第一个满足
nums[i] < nums[i+1]的位置i。为什么这样做？
如果nums[i] >= nums[i+1]，说明nums[i+1:]是递减的，递减部分是当前字典序最大的排列。因此，我们需要调整nums[i]，使其更大一些，才能找到下一个排列。如果遍历完整个数组，都没有找到这样的
i，说明整个数组是递减的（如[3, 2, 1]），此时没有更大的排列了，直接将数组反转为升序（最小字典序排列）。
2. 从后往前找到第一个比 nums[i] 大的数字
- 在找到的
i后，从右向左遍历数组，找到第一个满足nums[j] > nums[i]的位置j。 - 为什么这样做？
为了尽量保持新的排列“接近”当前排列，我们需要将nums[i]换成nums[j]，使得调整后的数组稍微大一点点。
3. 交换 nums[i] 和 nums[j]
- 交换后，前面的部分已经是“更大的排列”了，但后面的部分仍然是递减的，因此需要处理后面的部分。
4. 将 nums[i+1:] 反转
- 因为
nums[i+1:]是递减的，把它反转后就会变成升序，即最小字典序排列。 - 这样就保证了调整后的数组是“下一个排列”。
go
func nextPermutation(nums []int) {
n := len(nums)
i := n - 2
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i >= 0 {
j := n - 1
for j >= 0 && nums[i] >= nums[j] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
}
reverse(nums[i+1:])
}
func reverse(a []int) {
for i, n := 0, len(a); i < n/2; i++ {
a[i], a[n-1-i] = a[n-1-i], a[i]
}
}缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
go
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。示例 2：
go
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。示例 3：
go
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。题解
重新排列数组：
- 我们希望将数字 1 放到 nums[0]，数字 2 放到 nums[1]，依此类推。
- 遍历数组，如果当前数字 nums[i] 满足以下条件：
- nums[i] > 0：必须是正数。
- nums[i] <= n：值在数组长度范围内。
- nums[i] != nums[nums[i]-1]：当前数字没有在正确的位置上。
- 则将 nums[i] 和其目标位置 nums[nums[i]-1] 的值交换，直到当前数字在正确位置或条件不满足。
检查排列结果：
- 遍历数组，找到第一个 nums[i] != i+1 的位置，说明缺失的正整数是 i+1。
返回结果：
- 如果所有数字都在正确位置，则返回 n+1。
go
func firstMissingPositive(nums []int) int {
n := len(nums)
// 将每个数放到其正确的位置上，比如 1 放到 nums[0]，2 放到 nums[1]
for i := 0; i < n; i++ {
for nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
}
}
// 找到第一个 nums[i] != i+1 的位置，返回 i+1
for i := 0; i < n; i++ {
if nums[i] != i+1 {
return i + 1
}
}
// 如果所有位置都正确，返回 n+1
return n + 1
}矩阵
旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1：
go
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]示例 2：
go
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]题解
可以通过分步处理来实现矩阵的原地顺时针旋转90度：
- 转置矩阵：将矩阵的行变为列。
- 翻转每一行：将矩阵的每一行进行反转。
go
func rotate(matrix [][]int) {
n := len(matrix)
// 先转置矩阵
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
}
// 然后翻转每一行
for i := 0; i < n; i++ {
for j := 0; j < n/2; j++ {
matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
}
}
}计数
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 n/2 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
go
输入：nums = [3,2,3]
输出：3示例 2：
go
输入：nums = [2,2,1,1,1,2,2]
输出：2题解
方法一
- 1.使用哈希表统计每个元素的出现次数。
- 2.遍历哈希表，找到出现次数大于 n/2 的元素。
go
func majorityElement(nums []int) int {
count := make(map[int]int)
for _, num := range nums {
count[num]++
if count[num] > len(nums)/2 {
return num
}
}
return 0
}方法二
摩尔投票法：
- 遍历数组时，使用一个计数器记录当前候选元素的支持度。
- 当计数器为 0 时，更新候选元素为当前元素。
- 如果当前元素与候选元素相同，计数器加 1，否则减 1。
go
func majorityElement(nums []int) int {
candidate := 0
count := 0
// 摩尔投票法找出候选人
for _, num := range nums {
if count == 0 {
candidate = num
}
if num == candidate {
count++
} else {
count--
}
}
// 因为题目保证一定存在多数元素，无需进一步验证
return candidate
}