0601-0700-Easy¶

605.种花问题(3)¶

题目

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。
可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。
能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:输入: flowerbed = [1,0,0,0,1], n = 1 输出: True
示例 2:输入: flowerbed = [1,0,0,0,1], n = 2 输出: False

注意:
    数组内已种好的花不会违反种植规则。
    输入的数组长度范围为 [1, 20000]。
    n 是非负整数，且不会超过输入数组的大小。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	遍历统计	O(n)	O(1)
03	补数+遍历统计	O(n)	O(1)

func canPlaceFlowers(flowerbed []int, n int) bool {
	length := len(flowerbed)
	// 判断条件
	// 1:当前元素是0
	// 2.前一个元素是0，或者当前是第一个元素
	// 3.后一个元素是0，或者当前是最后一个元素
	for i := 0; i < length; i++ {
		if flowerbed[i] == 0 &&
			(i == 0 || flowerbed[i-1] == 0) &&
			(i == length-1 || flowerbed[i+1] == 0) {
			flowerbed[i] = 1
			n--
			if n <= 0 {
				return true
			}
		}
	}
	return n <= 0
}

#
func canPlaceFlowers(flowerbed []int, n int) bool {
	length := len(flowerbed)
	count := 0
	temp := 1
	// 以0开头，计算情况同以0结束，为向中间情况靠齐，可以特殊处理把temp初始化为1
	// 中间计算可以种花，value = (temp-1)/2
	// 最后结束如果为偶数, value=temp/2
	for i := 0; i < length; i++ {
		if flowerbed[i] == 1 {
			count = count + (temp-1)/2
			temp = 0
		} else {
			temp++
		}
	}
	count = count + temp/2
	return n <= count
}

#
func canPlaceFlowers(flowerbed []int, n int) bool {
	flowerbed = append([]int{0}, flowerbed...)
	flowerbed = append(flowerbed, []int{0, 1}...)
	count := 0
	temp := 0
	// 首补0，尾补0，1，统一一种情况
	for i := 0; i < len(flowerbed); i++ {
		if flowerbed[i] == 1 {
			count = count + (temp-1)/2
			temp = 0
		} else {
			temp++
		}
	}
	return n <= count
}

606.根据二叉树创建字符串(2)¶

题目

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1:
输入: 二叉树: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     
输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。
示例 2:
输入: 二叉树: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 
输出: "1(2()(4))(3)"
解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	迭代	O(n)	O(n)

func tree2str(t *TreeNode) string {
	if t == nil {
		return ""
	}
	res := strconv.Itoa(t.Val)
	if t.Left == nil && t.Right == nil {
		return res
	}
	res += "(" + tree2str(t.Left) + ")"
	if t.Right != nil{
		res += "(" + tree2str(t.Right) + ")"
	}
	return res
}

#
func tree2str(t *TreeNode) string {
	if t == nil {
		return ""
	}
	stack := make([]*TreeNode, 0)
	m := make(map[*TreeNode]bool)
	stack = append(stack, t)
	res := ""
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		if _, ok := m[node]; ok {
			stack = stack[:len(stack)-1]
			res = res + ")"
		} else {
			m[node] = true
			res = res + "(" + strconv.Itoa(node.Val)
			if node.Left == nil && node.Right != nil {
				res = res + "()"
			}
			if node.Right != nil {
				stack = append(stack, node.Right)
			}
			if node.Left != nil {
				stack = append(stack, node.Left)
			}
		}
	}
	return res[1 : len(res)-1]
}

617.合并二叉树(2)¶

题目

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，
否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:
输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
注意: 合并必须从两个树的根节点开始。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	迭代	O(n)	O(n)

func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
	if t1 == nil {
		return t2
	}
	if t2 == nil {
		return t1
	}
	t1.Val = t1.Val + t2.Val
	t1.Left = mergeTrees(t1.Left, t2.Left)
	t1.Right = mergeTrees(t1.Right, t2.Right)
	return t1
}

#
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
	if t1 == nil {
		return t2
	}
	if t2 == nil {
		return t1
	}
	list := make([]*TreeNode, 0)
	list = append(list, t1)
	list = append(list, t2)
	for len(list) > 0 {
		node1 := list[0]
		node2 := list[1]
		node1.Val = node1.Val + node2.Val
		if node1.Left != nil && node2.Left != nil {
			list = append(list, node1.Left)
			list = append(list, node2.Left)
		} else if node1.Left == nil && node2.Left != nil {
			node1.Left = node2.Left
		}
		if node1.Right != nil && node2.Right != nil {
			list = append(list, node1.Right)
			list = append(list, node2.Right)
		} else if node1.Right == nil && node2.Right != nil {
			node1.Right = node2.Right
		}
		list = list[2:]
	}
	return t1
}

628.三个数的最大乘积(2)¶

题目

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1:输入: [1,2,3]输出: 6
示例 2:输入: [1,2,3,4]输出: 24
注意:
    给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
    输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(nlog(n))	O(1)
02	遍历	O(n)	O(1)

func maximumProduct(nums []int) int {
	sort.Ints(nums)
	return max(nums[0]*nums[1]*nums[len(nums)-1],
		nums[len(nums)-3]*nums[len(nums)-2]*nums[len(nums)-1])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

#
func maximumProduct(nums []int) int {
	max1, max2, max3 := math.MinInt32, math.MinInt32, math.MinInt32
	min1, min2 := math.MaxInt32, math.MaxInt32
	for i := 0; i < len(nums); i++ {
		if nums[i] <= min1 {
			min2 = min1
			min1 = nums[i]
		} else if nums[i] <= min2 {
			min2 = nums[i]
		}
		if nums[i] >= max1 {
			max3 = max2
			max2 = max1
			max1 = nums[i]
		} else if nums[i] >= max2 {
			max3 = max2
			max2 = nums[i]
		} else if nums[i] >= max3 {
			max3 = nums[i]
		}
	}
	return max(min1*min2*max1, max1*max2*max3)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

633.平方数之和(2)¶

题目

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
示例1:输入: 5 输出: True 解释: 1 * 1 + 2 * 2 = 5
示例2:输入: 3 输出: False

解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(log(n))	O(1)
02	遍历	O(log(n))	O(1)

func judgeSquareSum(c int) bool {
	if c < 0 {
		return false
	}
	i, j := 0, int(math.Sqrt(float64(c)))
	for i <= j {
		current := i*i + j*j
		if current < c {
			i++
		} else if current > c {
			j--
		} else {
			return true
		}
	}
	return false
}

#
func judgeSquareSum(c int) bool {
	for i := 0; i <= int(math.Sqrt(float64(c))); i++ {
		b := c - i*i
		s := int(math.Sqrt(float64(b)))
		if s*s == b {
			return true
		}
	}
	return false
}

637.二叉树的层平均值(2)¶

题目

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入:
    3
   / \
  9  20
    /  \
   15   7
输出: [3, 14.5, 11]
解释:第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
注意：
    节点值的范围在32位有符号整数范围内。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	迭代	O(n)	O(n)

func averageOfLevels(root *TreeNode) []float64 {
	var sum, node []int
	res := make([]float64, 0)
	sum = append(sum, root.Val)
	node = append(node, 1)
	sum, node = dfs(root, sum, node, 1)
	for i := 0; i < len(sum); i++ {
		res = append(res, float64(sum[i])/float64(node[i]))
	}
	return res
}

func dfs(root *TreeNode, sum, node []int, level int) ([]int, []int) {
	if root == nil || (root.Left == nil && root.Right == nil) {
		return sum, node
	}
	if level >= len(sum) {
		sum = append(sum, 0)
		node = append(node, 0)
	}
	if root.Left != nil {
		sum[level] += root.Left.Val
		node[level]++
	}
	if root.Right != nil {
		sum[level] += root.Right.Val
		node[level]++
	}
	sum, node = dfs(root.Left, sum, node, level+1)
	sum, node = dfs(root.Right, sum, node, level+1)
	return sum, node
}

#
func averageOfLevels(root *TreeNode) []float64 {
	res := make([]float64, 0)
	list := make([]*TreeNode, 0)
	list = append(list, root)
	for len(list) > 0 {
		length := len(list)
		sum := 0
		for i := 0; i < length; i++ {
			sum = sum + list[i].Val
			if list[i].Left != nil {
				list = append(list, list[i].Left)
			}
			if list[i].Right != nil {
				list = append(list, list[i].Right)
			}
		}
		res = append(res, float64(sum)/float64(length))
		list = list[length:]
	}
	return res
}

643.子数组最大平均数 I(3)¶

题目

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例 1:输入: [1,12,-5,-6,50,3], k = 4 输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
注意:
    1 <= k <= n <= 30,000。
    所给数据范围 [-10,000，10,000]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历+滑动窗口	O(n)	O(1)
02	遍历+暴力法	O(n^2)	O(1)
03	遍历+累计求和	O(n)	O(n)

func findMaxAverage(nums []int, k int) float64 {
	temp := 0
	for i := 0; i < k; i++ {
		temp = temp + nums[i]
	}
	max := temp
	for i := k; i < len(nums); i++ {
		temp = temp + nums[i] - nums[i-k]
		if max < temp {
			max = temp
		}
	}
	return float64(max) / float64(k)
}

#
func findMaxAverage(nums []int, k int) float64 {
	max := math.MinInt32
	for i := 0; i < len(nums); i++ {
		if i + k > len(nums){
			break
		}
		sum := 0
		for j := i; j < i+k; j++{
			sum = sum+nums[j]
		}
		if sum > max{
			max = sum
		}
	}
	return float64(max) / float64(k)
}

#
func findMaxAverage(nums []int, k int) float64 {
	sum := make([]int, len(nums))
	sum[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		sum[i] = sum[i-1] + nums[i]
	}
	max := sum[k-1]
	for i := k; i < len(nums); i++ {
		if sum[i]-sum[i-k] > max {
			max = sum[i] - sum[i-k]
		}
	}
	return float64(max) / float64(k)
}

645.错误的集合(5)¶

题目

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，
导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:输入: nums = [1,2,2,4]输出: [2,3]
注意:
	给定数组的长度范围是 [2, 10000]。
    给定的数组是无序的。

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组辅助	O(n)	O(n)
02	置反	O(n)	O(1)
03	位运算	O(n)	O(1)
04	哈希辅助	O(n)	O(n)
05	排序	O(nlog(n))	O(1)

func findErrorNums(nums []int) []int {
	newNums := make([]int, len(nums))
	var repeatNum int
	for _, v := range nums {
		if newNums[v-1] != 0 {
			repeatNum = v
		}
		newNums[v-1] = v
	}
	for i, v := range newNums {
		if v == 0 {
			return []int{repeatNum, i + 1}
		}
	}
	return []int{0, 0}
}

#
func findErrorNums(nums []int) []int {
	repeatNum := 0
	for i := 0; i < len(nums); i++ {
		n := abs(nums[i])
		if nums[n-1] < 0 {
			repeatNum = n
		} else {
			nums[n-1] = -nums[n-1]
		}
	}
	misNum := 0
	for i, v := range nums {
		if v > 0 {
			misNum = i + 1
			break
		}
	}
	return []int{repeatNum, misNum}
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

#
func findErrorNums(nums []int) []int {
	res := 0
	// 异或得到repeatedNum^misNum
	for i := 0; i < len(nums); i++ {
		res = res ^ (i + 1) ^ (nums[i])
	}
	// 找到第一位不是0的
	h := 1
	for res&h == 0 {
		h = h << 1
	}
	a := 0
	b := 0
	for i := range nums {
		if h&nums[i] == 0 {
			a ^= nums[i]
		} else {
			b ^= nums[i]
		}
		if h&(i+1) == 0 {
			a ^= i + 1
		} else {
			b ^= i + 1
		}
	}
	for i := range nums {
		if nums[i] == b {
			return []int{b, a}
		}
	}
	return []int{a, b}
}

#
func findErrorNums(nums []int) []int {
	m := make(map[int]int)
	n := len(nums)
	sum := 0
	repeatNum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
		if _, ok := m[nums[i]]; ok {
			repeatNum = nums[i]
		}
		m[nums[i]] = 1
	}
	return []int{repeatNum, n*(n+1)/2 - sum + repeatNum}
}

#
func findErrorNums(nums []int) []int {
	sort.Ints(nums)
	n := len(nums)
	sum := 0
	repeatNum := nums[0]
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
		if i < len(nums)-1 && nums[i] == nums[i+1] {
			repeatNum = nums[i]
		}
	}
	return []int{repeatNum, n*(n+1)/2 - sum + repeatNum}
}

653.两数之和IV输入BST(4)¶

题目

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入: 
    5
   / \
  3   6
 / \   \
2   4   7
Target = 9
输出: True
案例 2:
输入: 
    5
   / \
  3   6
 / \   \
2   4   7
Target = 28 输出: False

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归+哈希辅助	O(n)	O(n)
02	递归	O(nlog(n))	O(log(n))
03	迭代	O(n)	O(n)
04	递归+二分查找	O(n)	O(n)

func findTarget(root *TreeNode, k int) bool {
	if root == nil {
		return false
	}
	m := map[int]int{}
	return dfs(root, k, m)
}

func dfs(node *TreeNode, k int, m map[int]int) bool {
	if node == nil {
		return false
	}
	if _, ok := m[k-node.Val]; ok {
		return true
	}
	m[node.Val] = node.Val
	return dfs(node.Left, k, m) || dfs(node.Right, k, m)
}

#
func dfs(root, searchRoot *TreeNode, k int) bool {
	if root == nil {
		return false
	}
	found := findNode(searchRoot, k-root.Val)
	if found != nil && found != root {
		return true
	}
	return dfs(root.Left, searchRoot, k) ||
		dfs(root.Right, searchRoot, k)
}

func findNode(root *TreeNode, target int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == target {
		return root
	}
	if root.Val < target {
		return findNode(root.Right, target)
	}
	return findNode(root.Left, target)
}

#
func findTarget(root *TreeNode, k int) bool {
	if root == nil {
		return false
	}
	m := make(map[int]int)
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		node := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		if _, ok := m[k-node.Val]; ok {
			return true
		}
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
		m[node.Val] = 1
	}
	return false
}

#
var arr []int

func findTarget(root *TreeNode, k int) bool {
	if root == nil {
		return false
	}
	arr = make([]int, 0)
	dfs(root)
	i := 0
	j := len(arr) - 1
	for i < j {
		if arr[i]+arr[j] == k {
			return true
		} else if arr[i]+arr[j] > k {
			j--
		} else {
			i++
		}
	}
	return false
}

func dfs(node *TreeNode) {
	if node == nil {
		return
	}
	dfs(node.Left)
	arr = append(arr, node.Val)
	dfs(node.Right)
}

657.机器人能否返回原点(2)¶

题目

在二维平面上，有一个机器人从原点 (0, 0) 开始。
给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。
机器人的有效动作有 R（右），L（左），U（上）和 D（下）。
如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。
此外，假设每次移动机器人的移动幅度相同。

示例 1:输入: "UD" 出: true
解释：机器人向上移动一次，然后向下移动一次。
所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:输入: "LL"输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。
我们返回 false，因为它在移动结束时没有返回原点。

解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数-字符统计	O(n)	O(1)
02	模拟	O(n)	O(1)

func judgeCircle(moves string) bool {
	return strings.Count(moves, "U") == strings.Count(moves, "D") &&
		strings.Count(moves, "L") == strings.Count(moves, "R")
}

#
func judgeCircle(moves string) bool {
	x, y := 0, 0
	for i := range moves {
		switch i {
		case 'U':
			y = y + 1
		case 'D':
			y = y - 1
		case 'L':
			x = x - 1
		case 'R':
			x = x + 1
		}
	}
	return x == 0 && y == 0
}

661.图片平滑器(2)¶

题目

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，
平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

示例 1:
输入:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
输出:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
注意:
    给定矩阵中的整数范围为 [0, 255]。
    矩阵的长和宽的范围均为 [1, 150]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n^2)	O(n^2)
02	遍历	O(n^2)	O(n^2)

func imageSmoother(M [][]int) [][]int {
	res := make([][]int, len(M))
	for i := range res {
		res[i] = make([]int, len(M[0]))
		for j := range res[i] {
			res[i][j] = getValue(M, i, j)
		}
	}
	return res
}

func getValue(M [][]int, r, c int) int {
	value, count := 0, 0
	for i := r - 1; i < r+2; i++ {
		for j := c - 1; j < c+2; j++ {
			if 0 <= i && i < len(M) && 0 <= j && j < len(M[0]) {
				value = value + M[i][j]
				count++
			}
		}
	}
	return value / count
}

#
func imageSmoother(M [][]int) [][]int {
	res := make([][]int, len(M))
	for i := range res {
		res[i] = make([]int, len(M[0]))
		for j := range res[i] {
			value, count := 0, 0
			for r := i - 1; r <= i+1; r++ {
				for c := j - 1; c <= j+1; c++ {
					if 0 <= r && r < len(M) && 0 <= c && c < len(M[0]) {
						value = value + M[r][c]
						count++
					}
				}
			}
			res[i][j] = value / count
		}
	}
	return res
}

665.非递减数列(3)¶

题目

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，总满足 array[i] <= array[i + 1]。

示例 1:输入: nums = [4,2,3] 输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:输入: nums = [4,2,1] 输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明：
    1 <= n <= 10 ^ 4
    - 10 ^ 5 <= nums[i] <= 10 ^ 5

解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(n)
02	遍历修改前后	O(n)	O(n)
03	遍历	O(n)	)

func checkPossibility(nums []int) bool {
	for i := 0; i < len(nums); i++ {
		res := make([]int,0)
		res = append(res, nums[0:i]...)
		res = append(res, nums[i+1:]...)
		if isSort(res) {
			return true
		}
	}
	return false
}

func isSort(nums []int) bool {
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] > nums[i+1] {
			return false
		}
	}
	return true
}

#
func checkPossibility(nums []int) bool {
	for i := 1; i < len(nums); i++{
		if nums[i-1] > nums[i]{
			pre := deepCopy(nums)
			pre[i-1] = pre[i]
			next := deepCopy(nums)
			next[i] = next[i-1]
			return sort.IsSorted(sort.IntSlice(pre)) || sort.IsSorted(sort.IntSlice(next))
		}
	}
	return true
}

func deepCopy(nums []int) []int  {
	res := make([]int, len(nums))
	copy(res,nums)
	return res
}

#
func checkPossibility(nums []int) bool {
	count := 0
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] > nums[i+1] {
			if count == 1 {
				return false
			} else if i == 0 {
				// 4 2 3 => 2 2 3
				nums[i] = nums[i+1]
				count++
			} else if nums[i-1] > nums[i+1] {
				// 3 4 2 => 3 4 4
				nums[i+1] = nums[i]
				count++
			} else {
				// 1 4 2 =>  1 2 2
				nums[i] = nums[i+1]
				count++
			}
		}
	}
	return true
}

669.修剪二叉搜索树(2)¶

题目

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。
通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。
你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例 1:
输入: 
    1
   / \
  0   2

  L = 1
  R = 2
输出: 
    1
      \
       2

示例 2:
输入: 
    3
   / \
  0   4
   \
    2
   /
  1
  L = 1
  R = 3
输出: 
      3
     / 
   2   
  /
 1

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	迭代	O(n)	O(n)

func trimBST(root *TreeNode, L int, R int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val < L {
		return trimBST(root.Right, L, R)
	}
	if R < root.Val {
		return trimBST(root.Left, L, R)
	}
	root.Left = trimBST(root.Left, L, R)
	root.Right = trimBST(root.Right, L, R)
	return root
}

#
func trimBST(root *TreeNode, L int, R int) *TreeNode {
	if root == nil {
		return nil
	}
	// 找到根节点
	for root.Val < L || root.Val > R {
		if root.Val < L {
			root = root.Right
		} else {
			root = root.Left
		}
	}

	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	cur := root
	temp := root
	for len(stack) > 0 {
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if cur.Left != nil {
			if cur.Left.Val >= L {
				// 左节点>=L，继续向左
				stack = append(stack, cur.Left)
			} else {
				// 在当前左节点，向它的右节点找到满足<L的值，
				// 并把当前左指针指向找到的值
				// 如示例2里面的，3的Left指向找到的2
				// 然后入栈继续在2找
				temp = cur.Left
				for temp != nil && temp.Val < L {
					temp = temp.Right
				}
				cur.Left = temp
				if temp != nil {
					stack = append(stack, temp)
				}
			}
		}
		if cur.Right != nil {
			if cur.Right.Val <= R {
				stack = append(stack, cur.Right)
			} else {
				temp = cur.Right
				for temp != nil && temp.Val > R {
					temp = temp.Left
				}
				cur.Right = temp
				if temp != nil {
					stack = append(stack, temp)
				}
			}
		}
	}
	return root
}

671.二叉树中第二小的节点(3)¶

题目

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。
如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
示例 1:
输入: 
    2
   / \
  2   5
     / \
    5   7

输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。
示例 2:
输入: 
    2
   / \
  2   2
输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归+数组辅助	O(n)	O(n)
02	递归	O(n)	O(log(n))
03	迭代	O(n)	O(n)

var arr []int

func findSecondMinimumValue(root *TreeNode) int {
	arr = make([]int, 0)
	dfs(root)
	min, second := math.MaxInt32, math.MaxInt32
	flag := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] < min {
			second = min
			min = arr[i]
		} else if min < arr[i] && arr[i] <= second {
			flag = 1
			second = arr[i]
		}
	}
	if second == math.MaxInt32 && flag == 0 {
		return -1
	}
	return second
}

func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	arr = append(arr, root.Val)
	dfs(root.Left)
	dfs(root.Right)
}

#
func dfs(root *TreeNode, val int) int {
	if root == nil {
		return -1
	}
	if root.Val > val {
		return root.Val
	}
	left := dfs(root.Left, val)
	right := dfs(root.Right, val)
	if left == -1 {
		return right
	}
	if right == -1 {
		return left
	}
	return min(left, right)
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}


#
func findSecondMinimumValue(root *TreeNode) int {
	min, second := root.Val, math.MaxInt32
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	flag := 0
	for len(queue) > 0 {
		node := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		if node.Val < min {
			second = min
			min = node.Val
		} else if min < node.Val && node.Val <= second {
			flag = 1
			second = node.Val
		}
		if node.Left != nil {
			// 有0个或2节点
			queue = append(queue, node.Left)
			queue = append(queue, node.Right)
		}
	}
	if second == math.MaxInt32 && flag == 0 {
		return -1
	}
	return second
}

674.最长连续递增序列(3)¶

题目

给定一个未经排序的整数数组，找到最长且连续的的递增序列。
示例 1:输入: [1,3,5,4,7] 输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。 
示例 2:输入: [2,2,2,2,2] 输出: 1
解释: 最长连续递增序列是 [2], 长度为1。

解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	动态规划	O(n)	O(n)
03	遍历	O(n)	O(1)

func findLengthOfLCIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	res := 1
	i, j := 0, 1
	for j < len(nums) {
		for j < len(nums) && nums[j-1] < nums[j] {
			j++
		}
		if res < j-i {
			res = j - i
		}
		i = j
		j++
	}
	return res
}

#
// 状态转移方程
// 若nums[i-1]<nums[i]，则dp[i]=dp[i-1]+1；否则dp[i]=1
func findLengthOfLCIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	res := 1
	dp := make([]int,len(nums))
	for i := 0; i < len(nums); i++{
		dp[i] = 1
	}
	for i := 1; i < len(nums); i++{
		if nums[i-1] < nums[i]{
			dp[i] = dp[i-1]+1
		}
		if dp[i] > res{
			res = dp[i]
		}
	}
	return res
}

680.验证回文字符串 Ⅱ(2)¶

题目

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:输入: "aba" 输出: True
示例 2:输入: "abca"输出: True 解释: 你可以删除c字符。
注意:
    字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	递归	O(n)	O(n)

func validPalindrome(s string) bool {
	i := 0
	j := len(s) - 1
	for i < j {
		if s[i] != s[j] {
			return isPalindrome(s, i, j-1) || isPalindrome(s, i+1, j)
		}
		i++
		j--
	}
	return true
}

func isPalindrome(s string, i, j int) bool {
	for i < j {
		if s[i] != s[j] {
			return false
		}
		i++
		j--
	}
	return true
}

#
func validPalindrome(s string) bool {
	length := len(s)
	if length < 2 {
		return true
	}
	if s[0] == s[length-1] {
		return validPalindrome(s[1 : length-1])
	}
	return isPalindrome(s[0:length-1]) || isPalindrome(s[1:length])
}

func isPalindrome(s string) bool {
	i := 0
	j := len(s) - 1
	for i < j {
		if s[i] != s[j] {
			return false
		}
		i++
		j--
	}
	return true
}

682.棒球比赛(1)¶

题目

你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。

每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:输入: ["5","2","C","D","+"] 输出: 30
解释: 
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。

示例 2:输入: ["5","-2","4","C","D","9","+","+"] 输出: 27
解释: 
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到-2分。总数是：3。
第3轮：你可以得到4分。总和是：7。
操作1：第3轮的数据无效。总数是：3。
第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
第5轮：你可以得到9分。总数是：8。
第6轮：你可以得到-4 + 9 = 5分。总数是13。
第7轮：你可以得到9 + 5 = 14分。总数是27。

注意：
    输入列表的大小将介于1和1000之间。
    列表中的每个整数都将介于-30000和30000之间。

解题思路

No.	思路	时间复杂度	空间复杂度
01	模拟-栈辅助	O(n)	O(n)

func calPoints(ops []string) int {
	stacks := make([]int, 0)
	for i := range ops {
		switch ops[i] {
		case "+":
			r1 := stacks[len(stacks)-1]
			r2 := stacks[len(stacks)-2]
			stacks = append(stacks, r1+r2)
		case "D":
			r1 := stacks[len(stacks)-1]
			stacks = append(stacks, 2*r1)
		case "C":
			stacks = stacks[:len(stacks)-1]
		default:
			tempInt, _ := strconv.Atoi(ops[i])
			stacks = append(stacks, tempInt)
		}
	}
	res := 0
	for _, value := range stacks {
		res = res + value
	}
	return res
}

686.重复叠加字符串匹配(2)¶

题目

给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，
使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。

举个例子，A = "abcd"，B = "cdabcdab"。
答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，
此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。

注意:
A 与 B 字符串的长度在1和10000区间范围内。

解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数	O(n)	O(n)
02	遍历	O(n)	O(n)

func repeatedStringMatch(A string, B string) int {
	times := len(B) / len(A)
	// 要确保B是A的子串，就要最少重复len(B)/len(A)次A次，最多len(B)/len(A)+2次
	// 如长度为 len(B) = 6, len(A) = 3,至少重复2次
	// 长度为len(B) = 7, len(A) = 3, 至少重复3次
	// 另外如B="cabcabca", A="abc",需要重复4次
	for i := times; i <= times+2; i++ {
		if strings.Contains(strings.Repeat(A, i), B) {
			return i
		}
	}
	return -1
}

#
func repeatedStringMatch(A string, B string) int {
	temp := A
	count := 1
	for len(temp) < len(B) {
		temp = temp + A
		count++
	}
	if strings.Contains(temp, B) {
		return count
	}
	temp = temp + A
	if strings.Contains(temp, B) {
		return count + 1
	}
	return -1
}

687.最长同值路径(3)¶

题目

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
              5
             / \
            4   5
           / \   \
          1   1   5

输出:2
示例 2:
输入:
              1
             / \
            4   5
           / \   \
          4   4   5
输出:2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	递归	O(n)	O(log(n))
03	迭代+栈辅助	O(n)	O(n)

var maxLen int

func longestUnivaluePath(root *TreeNode) int {
	maxLen = 0
	dfs(root)
	return maxLen
}

func dfs(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := dfs(root.Left)
	right := dfs(root.Right)
	l, r := 0, 0
	if root.Left != nil && root.Val == root.Left.Val {
		l = left + 1
	}
	if root.Right != nil && root.Val == root.Right.Val {
		r = right + 1
	}
	if l+r > maxLen {
		maxLen = l + r
	}
	return max(l, r)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

#
var maxLen int

func longestUnivaluePath(root *TreeNode) int {
	maxLen = 0
	if root == nil {
		return 0
	}
	dfs(root, root.Val)
	return maxLen
}

func dfs(root *TreeNode, val int) int {
	if root == nil {
		return 0
	}
	left := dfs(root.Left, root.Val)
	right := dfs(root.Right, root.Val)
	if left+right > maxLen {
		maxLen = left + right
	}
	if root.Val == val {
		return max(left, right) + 1
	}
	return 0
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

# 参考543.二叉树的直径做法
func longestUnivaluePath(root *TreeNode) int {
	res := 0
	stack := make([]*TreeNode, 0)
	m := make(map[*TreeNode]int)

	cur := root
	var prev *TreeNode
	for cur != nil || len(stack) != 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		if cur.Right == nil || cur.Right == prev {
			cur = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			leftLen := 0
			rightLen := 0
			if v, ok := m[cur.Left]; ok {
				leftLen = v
			}
			if v, ok := m[cur.Right]; ok {
				rightLen = v
			}
			var left, right int
			if cur.Left != nil && cur.Val == cur.Left.Val {
				left = leftLen + 1
			}
			if cur.Right != nil && cur.Val == cur.Right.Val {
				right = rightLen + 1
			}

			if left+right > res {
				res = left + right
			}
			if left > right {
				m[cur] = left
			} else {
				m[cur] = right
			}
			prev = cur
			cur = nil
		} else {
			cur = cur.Right
		}
	}
	return res
}

690.员工的重要性(2)¶

题目

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。
比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。
那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。
注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。
现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

示例 1:输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
注意:
    一个员工最多有一个直系领导，但是可以有多个直系下属
    员工数量不超过2000。

解题思路

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索-递归	O(n)	O(log(n))
02	广度优先搜索-迭代	O(n)	O(n)

func getImportance(employees []*Employee, id int) int {
	if len(employees) == 0 {
		return 0
	}
	var root *Employee
	for i := 0; i < len(employees); i++ {
		if employees[i].Id == id {
			root = employees[i]
		}
	}
	if root == nil {
		return 0
	}
	res := root.Importance
	for i := range root.Subordinates {
		res = res + getImportance(employees, root.Subordinates[i])
	}
	return res
}

#
func getImportance(employees []*Employee, id int) int {
	if len(employees) == 0 {
		return 0
	}
	m := make(map[int]*Employee)
	for i := 0; i < len(employees); i++ {
		m[employees[i].Id] = employees[i]
	}
	root := m[id]
	if root == nil {
		return 0
	}
	res := 0
	list := make([]*Employee, 0)
	list = append(list, root)
	for len(list) > 0 {
		node := list[0]
		list = list[1:]
		res = res + node.Importance
		for i := range node.Subordinates {
			if value, ok := m[node.Subordinates[i]]; ok {
				list = append(list, value)
			}
		}
	}
	return res
}

693.交替位二进制数(4)¶

题目

给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
示例 1: 输入: 5 输出: True 
解释:5的二进制数是: 101
示例 2:输入: 7 输出: False
解释: 7的二进制数是: 111
示例 3:输入: 11 输出: False
解释: 11的二进制数是: 1011
示例 4:输入: 10 输出: True
解释: 10的二进制数是: 1010

解题思路

No.	思路	时间复杂度	空间复杂度
01	转字符串+遍历	O(1)	O(1)
02	位运算	O(1)	O(1)
03	位运算	O(1)	O(1)
04	遍历	O(1)	O(1)

func hasAlternatingBits(n int) bool {
	str := strconv.FormatInt(int64(n), 2)
	for i := 1; i < len(str); i++ {
		if str[i] == str[i-1] {
			return false
		}
	}
	return true
}

#
/*
示例1：
1. n=1010
2. n>>1=101
3. n=n^(n>>1)=1010^101=1111
4. n&(n+1)=1111&(10000)=0

示例2:
1. n=101
2. n>>1=10
3. n=n^(n>>1)=101^10=111
4. n&(n+1)=111&(1000)=0
*/
func hasAlternatingBits(n int) bool {
	n = n ^ (n >> 1)
	return n&(n+1) == 0
}

#
// n (10|01)&3(11)=10|01
func hasAlternatingBits(n int) bool {
	temp := n & 3
	if temp != 1 && temp != 2 {
		return false
	}
	for n > 0 {
		if n&3 != temp {
			return false
		}
		n = n >> 2
	}
	return true
}

#
// n (10|01)&3(11)=10|01
func hasAlternatingBits(n int) bool {
	temp := n & 3
	if temp != 1 && temp != 2 {
		return false
	}
	for n > 0 {
		if n&3 != temp {
			return false
		}
		n = n >> 2
	}
	return true
}

#
func hasAlternatingBits(n int) bool {
	pre := n & 1
	n = n >> 1
	for n > 0 {
		if n&1 == pre {
			return false
		}
		pre = n & 1
		n = n >> 1
	}
	return true
}

696.计数二进制子串(3)¶

题目

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，
并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。

示例 1 :输入: "00110011" 输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2 :输入: "10101"输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
注意：
    s.length 在1到50,000之间。
    s 只包含“0”或“1”字符。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	遍历	O(n)	O(n)
03	暴力法	O(n^2)	O(1)

func countBinarySubstrings(s string) int {
	res := 0
	cur := 1
	pre := 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] == s[i+1] {
			cur++
		} else {
			if pre > cur {
				res = res + cur
			} else {
				res = res + pre
			}
			pre = cur
			cur = 1
		}
	}
	if pre > cur {
		return res + cur
	}
	return res + pre
}

#
func countBinarySubstrings(s string) int {
	res := 0
	arr := make([]int, 0)
	arr = append(arr, 1)
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			arr[len(arr)-1]++
		} else {
			arr = append(arr, 1)
		}
	}
	for i := 0; i < len(arr)-1; i++ {
		if arr[i] > arr[i+1] {
			res = res + arr[i+1]
		} else {
			res = res + arr[i]
		}
	}
	return res
}

#
var count int

func countBinarySubstrings(s string) int {
	count = 0
	for i := 1; i < len(s); i++ {
		if s[i-1] == '0' && s[i] == '1' {
			CountString(s, i-1, i)
		}
		if s[i-1] == '1' && s[i] == '0' {
			CountString(s, i-1, i)
		}
	}
	return count
}

func CountString(s string, left, right int) {
	leftStr := s[left]
	rightStr := s[right]
	for left >= 0 && right < len(s) && s[left] == leftStr && s[right] == rightStr {
		left--
		right++
		count++
	}
}

697.数组的度(3)¶

题目

给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1:输入: [1, 2, 2, 3, 1]输出: 2
解释: 输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

示例 2:输入: [1,2,2,3,1,4,2] 输出: 6

注意:
    nums.length 在1到50,000区间范围内。
    nums[i] 是一个在0到49,999范围内的整数。

解题思路

No.	思路	时间复杂度	空间复杂度
01	自定义结构体+遍历	O(n)	O(n)
02	哈希辅助	O(n)	O(n)
03	哈希辅助	O(n)	O(n)

type node struct {
	count int
	left  int
	right int
}

func findShortestSubArray(nums []int) int {
	m := make(map[int]*node, 0)
	for k, v := range nums {
		if nd, ok := m[v]; ok {
			nd.count = nd.count + 1
			nd.right = k
		} else {
			m[v] = &node{
				count: 1,
				left:  k,
				right: k,
			}
		}
	}
	maxNode := new(node)
	for _, v := range m {
		if v.count > maxNode.count {
			maxNode = v
		} else if v.count == maxNode.count && 
			v.right-v.left < maxNode.right-maxNode.left {
			maxNode = v
		}
	}
	return maxNode.right - maxNode.left + 1
}

#
func findShortestSubArray(nums []int) int {
	size := len(nums)
	if size < 2 {
		return size
	}
	first := make(map[int]int)
	count := make(map[int]int)
	maxCount := 1
	minLen := size
	for i, n := range nums {
		count[n]++
		if count[n] == 1 {
			first[n] = i
		} else {
			length := i - first[n] + 1
			if maxCount < count[n] ||
				(maxCount == count[n] && minLen > length) {
				maxCount = count[n]
				minLen = length
			}
		}
	}
	if len(count) == size {
		return 1
	}
	return minLen
}

#
func findShortestSubArray(nums []int) int {
	size := len(nums)
	if size < 2 {
		return size
	}
	res := 0
	maxLen := 0
	m := make(map[int][]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]] = append(m[nums[i]], i)
	}
	for _, v := range m{
		if len(v) > maxLen {
			maxLen = len(v)
			res = v[len(v)-1] - v[0] + 1
		} else if len(v) == maxLen && v[len(v)-1]-v[0]+1 < res {
			res = v[len(v)-1] - v[0] + 1
		}
	}
	return res
}

700.二叉搜索树中的搜索(2)¶

题目

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 
返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树:
        4
       / \
      2   7
     / \
    1   3
和值: 2
你应该返回如下子树:
      2     
     / \   
    1   3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	迭代	O(n)	O(n)

func searchBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val < val {
		return searchBST(root.Right, val)
	} else if root.Val > val {
		return searchBST(root.Left, val)
	}
	return root
}

#
func searchBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return nil
	}
	stack := make([]*TreeNode, 0)
	if root.Val == val {
		return root
	} else if root.Val > val && root.Left != nil {
		stack = append(stack, root.Left)
	} else if root.Val < val && root.Right != nil {
		stack = append(stack, root.Right)
	}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if node.Val == val {
			return node
		} else if node.Val > val && node.Left != nil {
			stack = append(stack, node.Left)
		} else if node.Val < val && node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	return nil
}

0601-0700-Medium¶

609.在系统中查找重复文件(1)¶

题目

给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，
您需要找到文件系统中的所有重复文件组的路径。
一组重复的文件至少包括二个具有完全相同内容的文件。
输入列表中的单个目录信息字符串的格式如下：
"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"
这意味着有 n 个文件（f1.txt,f2.txt...fn.txt 的内容分别是
f1_content,f2_content...fn_content）在目录root/d1/d2/.../dm下。
注意：n>=1 且 m>=0。如果 m=0，则表示该目录是根目录。
该输出是重复文件路径组的列表。对于每个组，它包含具有相同内容的文件的所有文件路径。
文件路径是具有下列格式的字符串：
"directory_path/file_name.txt"
示例 1：输入：
["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)",
"root 4.txt(efgh)"]
输出：[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
注：最终输出不需要顺序。
您可以假设目录名、文件名和文件内容只有字母和数字，并且文件内容的长度在 [1，50] 的范围内。
给定的文件数量在 [1，20000] 个范围内。
您可以假设在同一目录中没有任何文件或目录共享相同的名称。
您可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用一个空格分隔。
超越竞赛的后续行动：
假设您有一个真正的文件系统，您将如何搜索文件？广度搜索还是宽度搜索？
如果文件内容非常大（GB级别），您将如何修改您的解决方案？
如果每次只能读取 1 kb 的文件，您将如何修改解决方案？
修改后的解决方案的时间复杂度是多少？其中最耗时的部分和消耗内存的部分是什么？如何优化？
如何确保您发现的重复文件不是误报？

解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)

func findDuplicate(paths []string) [][]string {
	res := make([][]string, 0)
	m := make(map[string][]string)
	for i := 0; i < len(paths); i++ {
		arr := strings.Split(paths[i], " ")
		for j := 1; j < len(arr); j++ {
			index := strings.LastIndexByte(arr[j], '(')
			content := arr[j][index+1 : len(arr[j])-1]
			m[content] = append(m[content], arr[0]+"/"+arr[j][:index])
		}
	}
	for _, v := range m {
		if len(v) > 1 {
			res = append(res, v)
		}
	}
	return res
}

611.有效三角形的个数(3)¶

题目

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:输入: [2,2,3,4] 输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意: 数组长度不超过1000。
    数组里整数的范围为 [0, 1000]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^3)	O(1)
02	暴力法	O(n^3)	O(1)
03	排序双指针	O(n^2)	O(1)

func triangleNumber(nums []int) int {
	res := 0
	n := len(nums)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for k := j + 1; k < n; k++ {
				if nums[i]+nums[j] > nums[k] &&
					nums[i]+nums[k] > nums[j] &&
					nums[j]+nums[k] > nums[i] {
					res++
				}
			}
		}
	}
	return res
}

# 2
func triangleNumber(nums []int) int {
	sort.Ints(nums)
	res := 0
	n := len(nums)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for k := j + 1; k < n; k++ {
				if nums[i]+nums[j] > nums[k] {
					res++
				} else {
					break
				}
			}
		}
	}
	return res
}

# 3
func triangleNumber(nums []int) int {
	sort.Ints(nums)
	res := 0
	n := len(nums)
	for i := 0; i < n; i++ {
		if nums[i] == 0 {
			continue
		}
		left, right := i+1, i+2
		for left < n-1 && nums[left] != 0 {
			for right < n && nums[i]+nums[left] > nums[right] {
				right++
			}
			res = res + right - left - 1
			left++
		}
	}
	return res
}

621.任务调度器(2)¶

题目

给定一个用字符数组表示的 CPU 需要执行的任务列表。
其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。
任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。
CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，
因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 ：输入：tasks = ["A","A","A","B","B","B"], n = 2 输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，
     而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 
提示：
    任务的总个数为 [1, 10000]。
    n 的取值范围为 [0, 100]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	贪心-数组辅助	O(n)	O(1)
02	排序模拟	O(n)	O(1)

func leastInterval(tasks []byte, n int) int {
	arr := [26]int{}
	maxValue := 0
	for i := 0; i < len(tasks); i++ {
		arr[tasks[i]-'A']++
		if arr[tasks[i]-'A'] > maxValue {
			maxValue = arr[tasks[i]-'A']
		}
	}
	res := (maxValue - 1) * (n + 1) // 完成所有任务至少需要(max-1)*(n+1)+1
	for i := 0; i < len(arr); i++ {
		if arr[i] == maxValue {
			res++
		}
	}
	return max(res, len(tasks))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

# 2
func leastInterval(tasks []byte, n int) int {
	arr := make([]int, 26)
	for i := 0; i < len(tasks); i++ {
		arr[tasks[i]-'A']++
	}
	sort.Ints(arr)
	res := 0
	for arr[25] > 0 {
		i := 0
		for i <= n { // 每次安排n+1个
			if arr[25] == 0 {
				break
			}
			if i < 26 && arr[25-i] > 0 {
				arr[25-i]--
			}
			res++
			i++
		}
		sort.Ints(arr)
	}
	return res
}

622.设计循环队列(2)¶

题目

设计你的循环队列实现。 
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。
它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。
在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。
但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
    MyCircularQueue(k): 构造器，设置队列长度为 k 。
    Front: 从队首获取元素。如果队列为空，返回 -1 。
    Rear: 获取队尾元素。如果队列为空，返回 -1 。
    enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
    deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
    isEmpty(): 检查循环队列是否为空。
    isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4
提示：
    所有的值都在 0 至 1000 的范围内；
    操作数将在 1 至 1000 的范围内；
    请不要使用内置的队列库。

解题思路

No.	思路	时间复杂度	空间复杂度
01	切片	O(1)	O(n)
02	循环队列	O(1)	O(n)

type MyCircularQueue struct {
	queue []int
	k     int
}

func Constructor(k int) MyCircularQueue {
	return MyCircularQueue{
		queue: make([]int, 0),
		k:     k,
	}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
	if len(this.queue) == this.k {
		return false
	}
	this.queue = append(this.queue, value)
	return true
}

func (this *MyCircularQueue) DeQueue() bool {
	if len(this.queue) == 0 {
		return false
	}
	this.queue = this.queue[1:]
	return true
}

func (this *MyCircularQueue) Front() int {
	if len(this.queue) == 0 {
		return -1
	}
	return this.queue[0]
}

func (this *MyCircularQueue) Rear() int {
	if len(this.queue) == 0 {
		return -1
	}
	return this.queue[len(this.queue)-1]
}

func (this *MyCircularQueue) IsEmpty() bool {
	return len(this.queue) == 0
}

func (this *MyCircularQueue) IsFull() bool {
	return len(this.queue) == this.k
}

# 2
type MyCircularQueue struct {
	queue []int
	k     int
	front int // 队首
	rear  int // 队尾
}

func Constructor(k int) MyCircularQueue {
	return MyCircularQueue{
		queue: make([]int, k+1),
		k:     k + 1,
		front: 0,
		rear:  0,
	}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
	if this.IsFull() {
		return false
	}
	// 队尾入队
	this.queue[this.rear] = value
	this.rear++
	if this.rear == this.k {
		this.rear = 0
	}
	return true
}

func (this *MyCircularQueue) DeQueue() bool {
	if this.IsEmpty() {
		return false
	}
	// 队尾出队
	this.front++
	if this.front == this.k {
		this.front = 0
	}
	return true
}

func (this *MyCircularQueue) Front() int {
	if this.IsEmpty() {
		return -1
	}
	return this.queue[this.front]
}

func (this *MyCircularQueue) Rear() int {
	if this.IsEmpty() {
		return -1
	}
	prev := this.rear - 1
	if prev < 0 {
		prev = this.k - 1
	}
	return this.queue[prev]
}

func (this *MyCircularQueue) IsEmpty() bool {
	return this.front == this.rear
}

func (this *MyCircularQueue) IsFull() bool {
	next := this.rear + 1
	if next == this.k {
		next = 0
	}
	return next == this.front
}

623.在二叉树中增加一行(2)¶

题目

给定一个二叉树，根节点为第1层，深度为 1。在其第d层追加一行值为v的节点。
添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，
为 N 创建两个值为v的左子树和右子树。
将N 原先的左子树，连接为新节点v 的左子树；将N 原先的右子树，连接为新节点v 的右子树。
如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
示例 1:输入: 二叉树如下所示:
       4
     /   \
    2     6
   / \   / 
  3   1 5   
v = 1
d = 2
输出: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5   
示例 2:输入: 二叉树如下所示:
      4
     /   
    2    
   / \   
  3   1    
v = 1
d = 3
输出: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1
注意:输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
输入的二叉树至少有一个节点。

解题思路

No.	思路	时间复杂度	空间复杂度
01	层序遍历	O(n)	O(n)
02	递归	O(n)	O(log(n))

func addOneRow(root *TreeNode, v int, d int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: v}
	}
	if d == 1 {
		return &TreeNode{Val: v, Left: root}
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	var level = 1
	for len(queue) > 0 {
		level++
		length := len(queue)
		if level == d {
			for i := 0; i < length; i++ {
				queue[i].Left = &TreeNode{
					Left: queue[i].Left,
					Val:  v,
				}
				queue[i].Right = &TreeNode{
					Right: queue[i].Right,
					Val:   v,
				}
			}
		}
		for i := 0; i < length; i++ {
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		queue = queue[length:]
	}
	return root
}

# 2
func addOneRow(root *TreeNode, v int, d int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: v}
	}
	if d == 1 {
		return &TreeNode{Val: v, Left: root}
	}
	dfs(root, v, d)
	return root
}

func dfs(root *TreeNode, v int, d int) {
	if root == nil {
		return
	}
	if d == 2 {
		root.Left = &TreeNode{
			Val:  v,
			Left: root.Left,
		}
		root.Right = &TreeNode{
			Val:   v,
			Right: root.Right,
		}
		return
	}
	dfs(root.Left, v, d-1)
	dfs(root.Right, v, d-1)
}

636.函数的独占时间(2)¶

题目

给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。
每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。
日志是具有以下格式的字符串：function_id：start_or_end：timestamp。
例如："0:start:0"表示函数 0 从 0 时刻开始运行。"0:end:0"表示函数 0 在 0 时刻结束。
函数的独占时间定义是在该方法中花费的时间，调用其他函数花费的时间不算该函数的独占时间。
你需要根据函数的 Id 有序地返回每个函数的独占时间。
示例 1:输入: n = 2
logs = 
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
输出:[3, 4]
说明：函数 0 在时刻 0 开始，在执行了  2个时间单位结束于时刻 1。
现在函数 0 调用函数 1，函数 1 在时刻 2 开始，执行 4 个时间单位后结束于时刻 5。
函数 0 再次在时刻 6 开始执行，并在时刻 6 结束运行，从而执行了 1 个时间单位。
所以函数 0 总共的执行了 2 +1 =3 个时间单位，函数 1 总共执行了 4 个时间单位。
说明：输入的日志会根据时间戳排序，而不是根据日志Id排序。
你的输出会根据函数Id排序，也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。
两个函数不会在同时开始或结束。
函数允许被递归调用，直到运行结束。
1 <= n <= 100

解题思路

No.	思路	时间复杂度	空间复杂度
01	栈辅助	O(n)	O(n)
02	栈辅助	O(n)	O(n)

type Node struct {
	Id        int
	StartTime int
	Wait      int
}

func exclusiveTime(n int, logs []string) []int {
	res := make([]int, n)
	stack := make([]Node, 0)
	for i := 0; i < len(logs); i++ {
		arr := strings.Split(logs[i], ":")
		id, _ := strconv.Atoi(arr[0])
		if arr[1] == "start" {
			start, _ := strconv.Atoi(arr[2])
			stack = append(stack, Node{
				Id:        id,
				StartTime: start,
				Wait:      0,
			})
		} else {
			end, _ := strconv.Atoi(arr[2])
			node := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			total := end - node.StartTime + 1 - node.Wait
			res[node.Id] = res[node.Id] + total
			if len(stack) > 0 {
				wait := end - node.StartTime + 1
				stack[len(stack)-1].Wait = stack[len(stack)-1].Wait + wait
			}
		}
	}
	return res
}

# 2
func exclusiveTime(n int, logs []string) []int {
	res := make([]int, n)
	stack := make([]int, 0)
	var prev int
	for i := 0; i < len(logs); i++ {
		arr := strings.Split(logs[i], ":")
		id, _ := strconv.Atoi(arr[0])
		if arr[1] == "start" {
			start, _ := strconv.Atoi(arr[2])
			if len(stack) > 0 {
				lastId := stack[len(stack)-1]
				res[lastId] = res[lastId] + start - prev
			}
			stack = append(stack, id)
			prev = start
		} else {
			end, _ := strconv.Atoi(arr[2])
			lastId := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[lastId] = res[lastId] + end - prev + 1
			prev = end + 1
		}
	}
	return res
}

638.大礼包(4)¶

题目

在LeetCode商店中， 有许多在售的物品。
然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，
其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。
示例 1:输入: [2,5], [[3,0,5],[1,2,10]], [3,2] 输出: 14
解释: 有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。
示例 2:输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] 输出: 11
解释: A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
说明:最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。
提示：n == price.length
n == needs.length
1 <= n <= 6
0 <= price[i] <= 10
0 <= needs[i] <= 10
1 <= special.length <= 100
special[i].length == n + 1
0 <= special[i][j] <= 50

解题思路

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^n)	O(n)
02	回溯	O(n^n)	O(n)
03	回溯+缓存	O(n^n)	O(n)
04	递归	O(n^n)	O(n)

func shoppingOffers(price []int, special [][]int, needs []int) int {
	return dfs(price, special, needs)
}

func dfs(price []int, special [][]int, needs []int) int {
	res := 0
	for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
		res = res + needs[i]*price[i]
	}
	for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
		temp := make([]int, len(needs))
		copy(temp, needs) // 复制，避免还原
		j := 0
		for j = 0; j < len(temp); j++ {
			if temp[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
				break
			}
			temp[j] = temp[j] - special[i][j]
		}
		if j == len(temp) { // 可以取该礼包，继续递归
			res = min(res, dfs(price, special, temp)+special[i][j]) // 递归，取最小
		}
	}
	return res
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

# 2
func shoppingOffers(price []int, special [][]int, needs []int) int {
	return dfs(price, special, needs)
}

func dfs(price []int, special [][]int, needs []int) int {
	res := 0
	for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
		res = res + needs[i]*price[i]
	}
	for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
		j := 0
		for j = 0; j < len(needs); j++ {
			if needs[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
				break
			}
		}
		if j == len(needs) { // 可以取该礼包，继续递归
			for k := 0; k < len(needs); k++ {
				needs[k] = needs[k] - special[i][k]
			}
			res = min(res, dfs(price, special, needs)+special[i][j]) // 递归，取最小
			for k := 0; k < len(needs); k++ {
				needs[k] = needs[k] + special[i][k]
			}
		}
	}
	return res
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

# 3
var m map[string]int

func shoppingOffers(price []int, special [][]int, needs []int) int {
	m = make(map[string]int)
	return dfs(price, special, needs)
}

func dfs(price []int, special [][]int, needs []int) int {
	if v, ok := m[getString(needs)]; ok {
		return v
	}
	res := 0
	for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
		res = res + needs[i]*price[i]
	}
	for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
		j := 0
		for j = 0; j < len(needs); j++ {
			if needs[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
				break
			}
		}
		if j == len(needs) { // 可以取该礼包，继续递归
			for k := 0; k < len(needs); k++ {
				needs[k] = needs[k] - special[i][k]
			}
			res = min(res, dfs(price, special, needs)+special[i][j]) // 递归，取最小
			for k := 0; k < len(needs); k++ {
				needs[k] = needs[k] + special[i][k]
			}
		}
	}
	m[getString(needs)] = res
	return res
}

func getString(arr []int) string {
	res := ""
	for i := 0; i < len(arr); i++ {
		res = res + fmt.Sprintf("%d,", arr[i])
	}
	return strings.TrimRight(res, ",")
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

# 4
func shoppingOffers(price []int, special [][]int, needs []int) int {
	res := 0
	for i := 0; i < len(needs); i++ { // 默认：走单品所需要的总价格
		res = res + needs[i]*price[i]
	}
	for i := 0; i < len(special); i++ { // 遍历每个礼包，每次取1份尝试
		temp := make([]int, len(needs))
		copy(temp, needs) // 复制，避免还原
		j := 0
		for j = 0; j < len(temp); j++ {
			if temp[j] < special[i][j] { // 剪枝：不满足当前礼包要求，提前退出
				break
			}
			temp[j] = temp[j] - special[i][j]
		}
		if j == len(temp) { // 可以取该礼包，继续递归
			res = min(res, shoppingOffers(price, special, temp)+special[i][j]) // 递归，取最小
		}
	}
	return res
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

640.求解方程(1)¶

题目

求解一个给定的方程，将x以字符串"x=#value"的形式返回。该方程仅包含'+'，' - '操作，变量x和其对应系数。
如果方程没有解，请返回“No solution”。
如果方程有无限解，则返回“Infinite solutions”。
如果方程中只有一个解，要保证返回值x是一个整数。
示例 1：输入: "x+5-3+x=6+x-2" 输出: "x=2"
示例 2:输入: "x=x" 输出: "Infinite solutions"
示例 3:输入: "2x=x" 输出: "x=0"
示例 4:输入: "2x+3x-6x=x+2" 输出: "x=-1"
示例 5:输入: "x=x+2" 输出: "No solution"

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(n)

func solveEquation(equation string) string {
	arr := strings.Split(equation, "=")
	left, right := split(arr[0]), split(arr[1])
	l, r := getValue(left) // l左边x的系数，r右边值
	a, b := getValue(right)
	l, r = l-a, r-b
	if l == r && l == 0 {
		return "Infinite solutions"
	} else if l == 0 && r != 0 {
		return "No solution"
	}
	return "x=" + fmt.Sprintf("%d", r/l)
}

func getValue(arr []string) (l, r int) {
	for i := 0; i < len(arr); i++ {
		s := arr[i]
		if strings.Contains(s, "x") == true {
			s = strings.ReplaceAll(s, "x", "")
			if s == "" || s == "+" || s == "-" {
				s = s + "1"
			}
			value, _ := strconv.Atoi(s)
			l = l + value
		} else {
			value, _ := strconv.Atoi(s)
			r = r - value
		}
	}
	return l, r
}

func split(str string) (res []string) {
	prev := ""
	for i := 0; i < len(str); i++ {
		if str[i] == '+' || str[i] == '-' {
			if len(prev) > 0 {
				res = append(res, prev)
				prev = ""
			}
		}
		prev = prev + string(str[i])
	}
	res = append(res, prev)
	return res
}

641.设计循环双端队列(3)¶

题目

设计实现双端队列。
你的实现需要支持以下操作：
MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。
示例：MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了，返回 false
circularDeque.getRear();  				// 返回 2
circularDeque.isFull();				        // 返回 true
circularDeque.deleteLast();			        // 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();				// 返回 4
提示：所有值的范围为 [1, 1000]
操作次数的范围为 [1, 1000]
请不要使用内置的双端队列库。

解题思路

No.	思路	时间复杂度	空间复杂度
01	循环队列	O(1)	O(n)
02	双向链表	O(1)	O(1)
03	数组模拟	O(n)	O(n)

type MyCircularDeque struct {
	arr    []int
	head   int
	tail   int
	length int
}

// leetcode 622.设计循环队列
func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		arr:    make([]int, k+1),
		head:   0,
		tail:   0,
		length: k + 1,
	}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull() {
		return false
	}
	this.head = (this.head - 1 + this.length) % this.length // 入队：队头-1
	this.arr[this.head] = value
	return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull() {
		return false
	}
	this.arr[this.tail] = value
	this.tail = (this.tail + 1 + this.length) % this.length // 入队：队尾+1
	return true
}

func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty() {
		return false
	}
	this.head = (this.head + 1) % this.length // 出队：队头+1
	return true
}

func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty() {
		return false
	}
	this.tail = (this.tail - 1 + this.length) % this.length // 出队：队尾-1
	return true
}

func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty() {
		return -1
	}
	return this.arr[this.head]
}

func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty() {
		return -1
	}
	index := (this.tail - 1 + this.length) % this.length
	return this.arr[index]
}

func (this *MyCircularDeque) IsEmpty() bool {
	return this.head == this.tail
}

func (this *MyCircularDeque) IsFull() bool {
	return (this.tail+1)%this.length == this.head
}

# 2
type MyCircularDeque struct {
	head   *Node
	tail   *Node
	length int
	cap    int
}

type Node struct {
	value int
	pre   *Node
	next  *Node
}

func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		cap: k,
	}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.length == this.cap {
		return false
	}
	node := &Node{
		value: value,
	}
	if this.length == 0 {
		this.head = node
		this.tail = node
	} else {
		node.next = this.head
		this.head.pre = node
		this.head = node
	}
	this.length++
	return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.length == this.cap {
		return false
	}
	node := &Node{
		value: value,
	}
	if this.length == 0 {
		this.head = node
		this.tail = node
	} else {
		node.pre = this.tail
		this.tail.next = node
		this.tail = node
	}
	this.length++
	return true
}

func (this *MyCircularDeque) DeleteFront() bool {
	if this.length == 0 {
		return false
	}
	if this.length == 1 {
		this.head, this.tail = nil, nil
	} else {
		this.head = this.head.next
		this.head.pre = nil
	}
	this.length--
	return true
}

func (this *MyCircularDeque) DeleteLast() bool {
	if this.length == 0 {
		return false
	}
	if this.length == 1 {
		this.head, this.tail = nil, nil
	} else {
		this.tail = this.tail.pre
		this.tail.next = nil
	}
	this.length--
	return true
}

func (this *MyCircularDeque) GetFront() int {
	if this.length == 0 {
		return -1
	}
	return this.head.value
}

func (this *MyCircularDeque) GetRear() int {
	if this.length == 0 {
		return -1
	}
	return this.tail.value
}

func (this *MyCircularDeque) IsEmpty() bool {
	return this.length == 0
}

func (this *MyCircularDeque) IsFull() bool {
	return this.length == this.cap
}

# 3
type MyCircularDeque struct {
	arr    []int
	length int
	cap    int
}

func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		arr:    make([]int, 0),
		length: 0,
		cap:    k,
	}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull() {
		return false
	}
	this.arr = append([]int{value}, this.arr...)
	this.length++
	return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull() {
		return false
	}
	this.arr = append(this.arr, value)
	this.length++
	return true
}

func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty() {
		return false
	}
	this.arr = this.arr[1:]
	this.length--
	return true
}

func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty() {
		return false
	}
	this.arr = this.arr[:this.length-1]
	this.length--
	return true
}

func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty() {
		return -1
	}
	return this.arr[0]
}

func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty() {
		return -1
	}
	return this.arr[this.length-1]
}

func (this *MyCircularDeque) IsEmpty() bool {
	return this.length == 0
}

func (this *MyCircularDeque) IsFull() bool {
	return this.length == this.cap
}

646.最长数对链(2)¶

题目

给出n个数对。在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当b < c时，数对(c, d)才可以跟在(a, b)后面。
我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：输入：[[1,2], [2,3], [3,4]] 输出：2
解释：最长的数对链是 [1,2] -> [3,4]
提示：给出数对的个数在[1, 1000] 范围内。

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(nlog(n))	O(1)
02	动态规划	O(n^2)	O(n)

func findLongestChain(pairs [][]int) int {
	sort.Slice(pairs, func(i, j int) bool {
		if pairs[i][1] == pairs[j][1] {
			return pairs[i][0] < pairs[j][0]
		}
		return pairs[i][1] < pairs[j][1]
	})
	res := 0
	cur := math.MinInt32
	for i := 0; i < len(pairs); i++ {
		if cur < pairs[i][0] {
			cur = pairs[i][1]
			res++
		}
	}
	return res
}

# 2
func findLongestChain(pairs [][]int) int {
	sort.Slice(pairs, func(i, j int) bool {
		if pairs[i][1] == pairs[j][1] {
			return pairs[i][0] < pairs[j][0]
		}
		return pairs[i][1] < pairs[j][1]
	})
	dp := make([]int, len(pairs))
	for i := 0; i < len(pairs); i++ {
		dp[i] = 1
	}
	res := 0
	for i := 0; i < len(pairs); i++ {
		for j := 0; j < i; j++ {
			if pairs[j][1] < pairs[i][0] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		res = max(res, dp[i])
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

647.回文子串(5)¶

题目

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：输入："abc" 输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：输入："aaa" 输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：输入的字符串长度不会超过 1000 。

解题思路

No.	思路	时间复杂度	空间复杂度
01	中心扩展	O(n^2)	O(1)
02	Manacher算法	O(n^2)	O(1)
03	Manacher算法	O(n)	O(n)
04	动态规划	O(n^2)	O(n^2)
05	暴力法	O(n^3)	O(1)

func countSubstrings(s string) int {
	n := len(s)
	res := 0
	for i := 0; i < 2*n-1; i++ {
		left, right := i/2, i/2+i%2
		for ; 0 <= left && right < n && s[left] == s[right]; left, right = left-1, right+1 {
			res++
		}
	}
	return res
}

# 2
func countSubstrings(s string) int {
	if len(s) <= 1 {
		return len(s)
	}
	str := add(s)
	length := len(str)
	res := 0
	for i := 0; i < length; i++ {
		curLength := search(str, i)
		res = res + curLength/2 + curLength%2
	}
	return res
}

func add(s string) string {
	var res []rune
	for _, v := range s {
		res = append(res, '#')
		res = append(res, v)
	}
	res = append(res, '#')
	return string(res)
}

func search(s string, center int) int {
	i := center - 1
	j := center + 1
	step := 0
	for ; i >= 0 && j < len(s) && s[i] == s[j]; i, j = i-1, j+1 {
		step++
	}
	return step
}

# 3
func countSubstrings(s string) int {
	var res []rune
	res = append(res, '$')
	for _, v := range s {
		res = append(res, '#')
		res = append(res, v)
	}
	res = append(res, '#')
	res = append(res, '!')
	str := string(res)
	n := len(str) - 1
	arr := make([]int, n)
	leftMax, rightMax, result := 0, 0, 0
	for i := 1; i < n; i++ {
		if i <= rightMax {
			arr[i] = min(rightMax-i+1, arr[2*leftMax-i])
		} else {
			arr[i] = 1
		}
		for str[i+arr[i]] == str[i-arr[i]] {
			arr[i]++
		}
		if i+arr[i]-1 > rightMax {
			leftMax = i
			rightMax = i + arr[i] - 1
		}
		result = result + arr[i]/2
	}
	return result
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

# 4
func countSubstrings(s string) int {
	if len(s) <= 1 {
		return len(s)
	}
	dp := make([][]bool, len(s))
	res := 0
	for r := 0; r < len(s); r++ {
		dp[r] = make([]bool, len(s))
		dp[r][r] = true
		res++
		for l := 0; l < r; l++ {
			if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1] == true) {
				dp[l][r] = true
			} else {
				dp[l][r] = false
			}
			if dp[l][r] == true {
				res++
			}
		}
	}
	return res
}

# 5
func countSubstrings(s string) int {
	if len(s) <= 1 {
		return len(s)
	}
	res := len(s)
	for i := 0; i < len(s)-1; i++ {
		for j := i + 1; j < len(s); j++ {
			if s[i] == s[j] && judge(s, i, j) == true {
				res++
			}
		}
	}
	return res
}

func judge(s string, i, j int) bool {
	for i <= j {
		if s[i] != s[j] {
			return false
		}
		i++
		j--
	}
	return true
}

648.单词替换(2)¶

题目

在英语中，我们有一个叫做词根(root)的概念，
它可以跟着其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)。
例如，词根an，跟随着单词other(其他)，可以形成新的单词another(另一个)。
现在，给定一个由许多词根组成的词典和一个句子。
你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子。
示例 1：输入：dictionary = ["cat","bat","rat"], 
sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
示例 2：输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"
示例 3：输入：dictionary = ["a", "aa", "aaa", "aaaa"], 
sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
输出："a a a a a a a a bbb baba a"
示例 4：输入：dictionary = ["catt","cat","bat","rat"], 
sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
示例 5：输入：dictionary = ["ac","ab"], 
sentence = "it is abnormal that this solution is accepted"
输出："it is ab that this solution is ac"
提示：1 <= dictionary.length<= 1000
1 <= dictionary[i].length <= 100
dictionary[i]仅由小写字母组成。
1 <= sentence.length <= 10^6
sentence仅由小写字母和空格组成。
sentence 中单词的总量在范围 [1, 1000] 内。
sentence 中每个单词的长度在范围 [1, 1000] 内。
sentence 中单词之间由一个空格隔开。
sentence没有前导或尾随空格。

解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数	O(n^2)	O(n)
02	字典树	O(n)	O(n)

func replaceWords(dictionary []string, sentence string) string {
	sort.Strings(dictionary)
	arr := strings.Split(sentence, " ")
	for i := 0; i < len(arr); i++ {
		for _, v := range dictionary {
			if strings.HasPrefix(arr[i], v) {
				arr[i] = v
				break
			}
		}
	}
	return strings.Join(arr, " ")
}

# 2
func replaceWords(dictionary []string, sentence string) string {
	trie := Constructor()
	for i := 0; i < len(dictionary); i++ {
		trie.Insert(dictionary[i])
	}
	arr := strings.Split(sentence, " ")
	for i := 0; i < len(arr); i++ {
		result := trie.Search(arr[i])
		if result != "" {
			arr[i] = result
		}
	}
	return strings.Join(arr, " ")
}

type Trie struct {
	next   [26]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
	ending int       // 次数（可以改为bool）
}

func Constructor() Trie {
	return Trie{
		next:   [26]*Trie{},
		ending: 0,
	}
}

// 插入word
func (this *Trie) Insert(word string) {
	temp := this
	for _, v := range word {
		value := v - 'a'
		if temp.next[value] == nil {
			temp.next[value] = &Trie{
				next:   [26]*Trie{},
				ending: 0,
			}
		}
		temp = temp.next[value]
	}
	temp.ending++
}

// 查找
func (this *Trie) Search(word string) string {
	temp := this
	res := ""
	for _, v := range word {
		res = res + string(v)
		value := v - 'a'
		if temp = temp.next[value]; temp == nil {
			return ""
		}
		if temp.ending > 0 {
			return res
		}
	}
	return ""
}

649.Dota2参议院(1)¶

题目

Dota2 的世界里有两个阵营：Radiant(天辉)和Dire(夜魇)
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。
他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：
禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
宣布胜利：如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。
给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了Radiant（天辉）和Dire（夜魇）。
然后，如果有 n 个参议员，给定字符串的大小将是n。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。
这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，
你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是Radiant或Dire。
示例 1：输入："RD" 输出："Radiant"
解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，
因此第二个参议员将被跳过因为他没有任何权利。
然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人
示例 2：输入："RDD" 输出："Dire"
解释：第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
提示：给定字符串的长度在 [1, 10,000] 之间.

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历模拟	O(n)	O(n)

func predictPartyVictory(senate string) string {
	r, d := make([]int, 0), make([]int, 0)
	for i := 0; i < len(senate); i++ {
		if senate[i] == 'R' {
			r = append(r, i)
		} else {
			d = append(d, i)
		}
	}
	for len(r) > 0 && len(d) > 0 {
		if r[0] < d[0] {
			r = append(r, r[0]+len(senate))
		} else {
			d = append(d, d[0]+len(senate))
		}
		r = r[1:]
		d = d[1:]
	}
	if len(r) > 0 {
		return "Radiant"
	}
	return "Dire"
}

650.只有两个键的键盘(2)¶

题目

最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：
    Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
    Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。
输出能够打印出 n 个 'A' 的最少操作次数。
示例 1:输入: 3 输出: 3
解释:最初, 我们只有一个字符 'A'。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 'AA'。
第 3 步, 我们使用 Paste 操作来获得 'AAA'。
说明: n 的取值范围是 [1, 1000] 。

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n)
02	质数分解	O(n^1/2)	O(1)

func minSteps(n int) int {
	dp := make([]int, n+3)
	if n <= 1 {
		return 0
	}
	dp[0] = 0
	dp[1] = 0
	dp[2] = 2
	for i := 3; i <= n; i++ {
		minValue := i
		for j := i / 2; j >= 2; j-- {
			if i%j == 0 {
				minValue = dp[j] + i/j
				break
			}
		}
		dp[i] = minValue
	}
	return dp[n]
}

# 2
func minSteps(n int) int {
	res := 0
	for i := 2; i <= n; i++ {
		for n%i == 0 {
			res = res + i
			n = n / i
		}
	}
	return res
}

652.寻找重复的子树(1)¶

题目

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
下面是两个重复的子树：
      2
     /
    4
和 4
因此，你需要以列表的形式返回上述重复子树的根结点。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(n)

var m map[string]int
var res []*TreeNode

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	m = make(map[string]int)
	res = make([]*TreeNode, 0)

	dfs(root)
	return res
}

func dfs(root *TreeNode) string {
	if root == nil {
		return "#"
	}
	value := strconv.Itoa(root.Val) + "," + dfs(root.Left) + "," + dfs(root.Right)
	m[value]++
	if m[value] == 2 {
		res = append(res, root)
	}
	return value
}

654.最大二叉树(2)¶

题目

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
    二叉树的根是数组中的最大元素。
    左子树是通过数组中最大值左边部分构造出的最大二叉树。
    右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
示例 ：输入：[3,2,1,6,0,5] 输出：
返回下面这棵树的根节点：
      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1
提示：给定的数组的大小在 [1, 1000] 之间。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n^2)	O(n)
02	迭代	O(n)	O(n)

func constructMaximumBinaryTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	index := 0
	maxValue := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] > maxValue {
			maxValue = nums[i]
			index = i
		}
	}
	return &TreeNode{
		Val:   maxValue,
		Left:  constructMaximumBinaryTree(nums[:index]),
		Right: constructMaximumBinaryTree(nums[index+1:]),
	}
}

# 2
func constructMaximumBinaryTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	stack := make([]*TreeNode, 0)
	var cur *TreeNode
	for i := 0; i < len(nums); i++ {
		cur = &TreeNode{
			Val: nums[i],
		}
		// 递减栈
		for len(stack) > 0 && stack[len(stack)-1].Val < cur.Val {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			// top选择cur或者栈顶数据作为父节点
			if len(stack) > 0 && stack[len(stack)-1].Val < cur.Val {
				stack[len(stack)-1].Right = top
			} else {
				cur.Left = top
			}
		}
		stack = append(stack, cur)
	}
	// 没有右边节点，栈顶元素作为第二个栈顶元素的右节点
	for len(stack) > 0 {
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if len(stack) > 0 {
			stack[len(stack)-1].Right = cur
		}
	}
	return cur
}

655.输出二叉树(1)¶

题目

在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
行数m应当等于给定二叉树的高度。
列数n应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。
根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。
左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。
然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串""。
使用相同的规则输出子树。
示例 1:输入:
     1
    /
   2
输出:
[["", "1", ""],
 ["2", "", ""]]
示例 2:输入:
     1
    / \
   2   3
    \
     4
输出:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]
示例 3:输入:
      1
     / \
    2   5
   / 
  3 
 / 
4 
输出:
[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]
注意: 二叉树的高度在范围 [1, 10] 中。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n*2^n)	O(n*2^n)

var res [][]string

func printTree(root *TreeNode) [][]string {
	h := getHeightDFS(root)
	w := (1 << h) - 1
	res = make([][]string, h)
	for i := 0; i < h; i++ {
		res[i] = make([]string, w)
	}
	dfs(root, 0, 0, w-1)
	return res
}

func dfs(root *TreeNode, h, left, right int) {
	if root == nil {
		return
	}
	mid := left + (right-left)/2
	res[h][mid] = strconv.Itoa(root.Val)
	dfs(root.Left, h+1, left, mid-1)
	dfs(root.Right, h+1, mid+1, right)
}

func getHeightDFS(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + max(getHeightDFS(root.Left), getHeightDFS(root.Right))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

658.找到K个最接近的元素(3)¶

题目

给定一个排序好的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
示例 1：输入：arr = [1,2,3,4,5], k = 4, x = 3 输出：[1,2,3,4]
示例 2：输入：arr = [1,2,3,4,5], k = 4, x = -1 输出：[1,2,3,4]
提示：1 <= k <= arr.length
1 <= arr.length<= 104
数组里的每个元素与x 的绝对值不超过 104

解题思路

No.	思路	时间复杂度	空间复杂度
01	自定义排序	O(nlog(n))	O(n)
02	二分查找	O(log(n))	O(1)
03	遍历	O(n)	O(1)

func findClosestElements(arr []int, k int, x int) []int {
	sort.Slice(arr, func(i, j int) bool { // 按差值的绝对值排序，相同按照值大小排序
		if abs(arr[i]-x) == abs(arr[j]-x) {
			return arr[i] < arr[j]
		}
		return abs(arr[i]-x) < abs(arr[j]-x)
	})
	res := arr[:k]
	sort.Ints(res)
	return res
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

# 2
func findClosestElements(arr []int, k int, x int) []int {
	left, right := 0, len(arr)-k
	for left < right {
		mid := left + (right-left)/2   // 枚举左边
		if x-arr[mid] > arr[mid+k]-x { // 看x离left和right哪个远
			left = mid + 1
		} else {
			right = mid
		}
	}
	return arr[left : left+k]
}

# 3
func findClosestElements(arr []int, k int, x int) []int {
	left, right := 0, len(arr)-1
	for i := 1; i <= len(arr)-k; i++ {
		if x-arr[left] <= arr[right]-x { // 看x离left和right哪个远，远的就移动 相等就right-1
			right--
		} else {
			left++
		}
	}
	return arr[left : right+1]
}

659.分割数组为连续子序列(2)¶

题目

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，
其中每个子序列都由连续整数组成。
如果可以完成上述分割，则返回 true ；否则，返回 false 。
示例 1：输入: [1,2,3,3,4,5] 输出: True
解释:你可以分割出这样两个连续子序列 : 
1, 2, 3
3, 4, 5
示例 2：输入: [1,2,3,3,4,4,5,5] 输出: True
解释: 你可以分割出这样两个连续子序列 : 
1, 2, 3, 4, 5
3, 4, 5
示例 3：输入: [1,2,3,4,4,5] 输出: False
提示：1 <= nums.length <= 10000

解题思路

No.	思路	时间复杂度	空间复杂度
01	堆	O(nlog(n))	O(n)
02	贪心	O(n)	O(n)

func isPossible(nums []int) bool {
	m := make(map[int]*IntHeap)
	for i := 0; i < len(nums); i++ {
		v := nums[i]
		if m[v] == nil {
			intHeap := make(IntHeap, 0)
			heap.Init(&intHeap)
			m[v] = &intHeap
		}
		length := 0
		if h := m[v-1]; h != nil {
			length = heap.Pop(h).(int) // 找到最短的以v-1结尾的长度
			if m[v-1].Len() == 0 {
				delete(m, v-1)
			}
		}
		temp := m[v]
		heap.Push(temp, length+1)
	}
	for _, v := range m {
		if (*v)[0] < 3 {
			return false
		}
	}
	return true
}

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

# 2
func isPossible(nums []int) bool {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	count := make(map[int]int) // 以某个数字结尾的连续子序列的个数
	for i := 0; i < len(nums); i++ {
		v := nums[i]
		if m[v] == 0 {
			continue
		}
		if count[v-1] > 0 { // 添加到前一个数之后
			m[v]--
			count[v-1]--
			count[v]++
		} else if m[v+1] > 0 && m[v+2] > 0 { // 没有，生成1个新的
			m[v]--
			m[v+1]--
			m[v+2]--
			count[v+2]++
		} else {
			return false
		}
	}
	return true
}

662.二叉树最大宽度(2)¶

题目

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。
这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:输入: 
           1
         /   \
        3     2
       / \     \  
      5   3     9 
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:输入: 
          1
         /  
        3    
       / \       
      5   3     
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:输入: 
          1
         / \
        3   2 
       /        
      5      
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:输入: 
          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。

解题思路

No.	思路	时间复杂度	空间复杂度
01	迭代	O(n)	O(n)
02	递归	O(n)	O(n)

func widthOfBinaryTree(root *TreeNode) int {
	res := 1
	if root == nil {
		return 0
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	arr := make([]int, 0)
	arr = append(arr, 1)
	for len(queue) > 0 {
		if arr[len(arr)-1]-arr[0]+1 > res {
			res = arr[len(arr)-1] - arr[0] + 1
		}
		length := len(queue)
		for i := 0; i < length; i++ {
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
				arr = append(arr, arr[i]*2)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
				arr = append(arr, arr[i]*2+1)
			}
		}
		queue = queue[length:]
		arr = arr[length:]
	}
	return res
}

# 2
var res int
var m map[int]int

func widthOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	res = 0
	m = make(map[int]int)
	dfs(root, 0, 1)
	return res
}

func dfs(root *TreeNode, level int, id int) {
	if root == nil {
		return
	}
	if _, ok := m[level]; !ok {
		m[level] = id
	}
	if id-m[level]+1 > res {
		res = id - m[level] + 1
	}
	dfs(root.Left, level+1, id*2)
	dfs(root.Right, level+1, id*2+1)
}

667.优美的排列II(1)¶

题目

给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：
假设该列表是 answer =[a1, a2, a3, ... , an] ，
那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。
返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。
示例 1：输入：n = 3, k = 1
输出：[1, 2, 3]
解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1
示例 2：输入：n = 3, k = 2 输出：[1, 3, 2]
解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2
提示：1 <= k < n <= 104

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(n)

func constructArray(n int, k int) []int {
	if n == k {
		return nil
	}
	res := make([]int, n)
	// 构建等差数列为1：共n-k个数=>1
	for i := 1; i <= n-k; i++ {
		res[i-1] = i
	}
	// 构建交错队列：最大值和最小值交错出现，这样差值各不相同
	// n=10, k=7 => [1 2 3 4 5 6 7 10 8 9]
	// 剩下k个数（与等差数列相连）：共k个差值，依次1、2、3、...，去除1后共k-1个差值
	left := n - k + 1
	right := n
	count := 0
	for i := n - k + 1; i <= n; i++ {
		if count%2 == 1 {
			res[i-1] = left
			left++
		} else {
			res[i-1] = right
			right--
		}
		count++
	}
	return res
}

670.最大交换(3)¶

题目

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :输入: 2736 输出: 7236
解释: 交换数字2和数字7。
示例 2 :输入: 9973 输出: 9973
解释: 不需要交换。
注意:给定数字的范围是 [0, 10^8]

解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(1)	O(1)
02	贪心遍历	O(1)	O(1)
03	排序遍历	O(1)	O(1)

func maximumSwap(num int) int {
	if num <= 11 {
		return num
	}
	res := num
	arr := []byte(strconv.Itoa(num))
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			tempArr := make([]byte, len(arr))
			copy(tempArr, arr)
			tempArr[i], tempArr[j] = tempArr[j], tempArr[i]
			newValue, _ := strconv.Atoi(string(tempArr))
			if newValue > res {
				res = newValue
			}
		}
	}
	return res
}

# 2
func maximumSwap(num int) int {
	if num <= 11 {
		return num
	}
	res := num
	arr := []byte(strconv.Itoa(num))
	temp := [10]int{}
	for i := 0; i < len(arr); i++ {
		temp[arr[i]-'0'] = i // 每个数字最后一次出现的位置
	}
	for i := 0; i < len(arr); i++ {
		// 寻找最后面比当前数字大并且最大数字并进行交换
		for j := 9; j > int(arr[i]-'0'); j-- {
			if temp[j] > i {
				arr[i], arr[temp[j]] = arr[temp[j]], arr[i]
				res, _ = strconv.Atoi(string(arr))
				return res
			}
		}
	}
	return res
}

# 3
func maximumSwap(num int) int {
	if num <= 11 {
		return num
	}
	res := num
	arr := []byte(strconv.Itoa(num))
	temp := [10]int{}
	for i := 0; i < len(arr); i++ {
		temp[arr[i]-'0'] = i // 每个数字最后一次出现的位置
	}
	tempArr := []byte(strconv.Itoa(num))
	sort.Slice(tempArr, func(i, j int) bool {
		return tempArr[i] > tempArr[j]
	})

	for i := 0; i < len(arr); i++ {
		if arr[i] != tempArr[i] {
			arr[i], arr[temp[int(tempArr[i]-'0')]] = arr[temp[int(tempArr[i]-'0')]], arr[i]
			res, _ = strconv.Atoi(string(arr))
			return res
		}
	}
	return res
}

672.灯泡开关Ⅱ(2)¶

题目

现有一个房间，墙上挂有n只已经打开的灯泡和 4 个按钮。在进行了m次未知操作后，你需要返回这n只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 [1, 2, 3 ..., n]，这 4 个按钮的功能如下：
将所有灯泡的状态反转（即开变为关，关变为开）
将编号为偶数的灯泡的状态反转
将编号为奇数的灯泡的状态反转
将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, ...)
示例 1:输入: n = 1, m = 1. 输出: 2
说明: 状态为: [开], [关]
示例 2:输入: n = 2, m = 1. 输出: 3
说明: 状态为: [开, 关], [关, 开], [关, 关]
示例 3:输入: n = 3, m = 1. 输出: 4
说明: 状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].
注意：n和m 都属于 [0, 1000].

解题思路

No.	思路	时间复杂度	空间复杂度
01	找规律	O(1)	O(1)

func flipLights(n int, presses int) int {
	// 找规律：
	// 同一按钮操作2次，结果不变
	// 操作状态有16种；m > 4 后，状态在m=3或者m=4之间切换
	// m = 0： 0000
	// m = 1: 1000、0100、0010、0001
	// m = 2:
	//	还原：0000
	//  新增：1100、1010、1001，0110、0101、0011
	// m = 3:
	// 还原：1000、0100、0010、0001
	// 新增: 1110、0111、1011、1101
	// m = 4:
	// 还原：0000、1100、1010、1001，0110、0101、0011
	// 新增：1111
	if presses == 0 {
		return 1
	}
	if n == 1 {
		return 2
	}
	if n == 2 {
		if presses == 1 {
			return 3
		}
		return 4
	}
	if presses == 1 {
		return 4
	} else if presses == 2 {
		return 7
	}
	return 8
}

673.最长递增子序列的个数(1)¶

题目

给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:输入: [1,3,5,4,7] 输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:输入: [2,2,2,2,2] 输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n)

func findNumberOfLIS(nums []int) int {
	n := len(nums)
	if n == 0 || nums == nil {
		return 0
	}
	dp := make([]int, n)
	count := make([]int, n)
	maxValue := 0
	for i := 0; i < n; i++ {
		dp[i] = 1
		count[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				if dp[i] < dp[j]+1 {
					count[i] = count[j]
				} else if dp[i] == dp[j]+1 {
					count[i] = count[i] + count[j]
				}
				dp[i] = max(dp[j]+1, dp[i])
			}
		}
		maxValue = max(maxValue, dp[i])
	}
	res := 0
	for i := 0; i < n; i++ {
		if dp[i] == maxValue {
			res = res + count[i]
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

676.实现一个魔法字典(3)¶

题目

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 
如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 MagicDictionary 类：
MagicDictionary() 初始化对象
void buildDict(String[]dictionary) 使用字符串数组dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，
判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。
如果可以，返回 true ；否则，返回 false 。
示例：输入["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出[null, null, false, true, false, false]
解释 MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False
提示：1 <=dictionary.length <= 100
1 <=dictionary[i].length <= 100
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串 互不相同
1 <=searchWord.length <= 100
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 100 次 search

解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n^2)	O(n)
02	暴力法	O(n^2)	O(n)
03	trie树	O(n^2)	O(n)

type MagicDictionary struct {
	m map[int][]string
}

func Constructor() MagicDictionary {
	return MagicDictionary{m: map[int][]string{}}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	for i := 0; i < len(dictionary); i++ {
		this.m[len(dictionary[i])] = append(this.m[len(dictionary[i])], dictionary[i])
	}
}

func (this *MagicDictionary) Search(searchWord string) bool {
	if len(this.m[len(searchWord)]) == 0 {
		return false
	}
	for i := 0; i < len(this.m[len(searchWord)]); i++ {
		word := this.m[len(searchWord)][i]
		count := 0
		for j := 0; j < len(searchWord); j++ {
			if word[j] != searchWord[j] {
				count++
				if count > 1 {
					break
				}
			}
		}
		if count == 1 {
			return true
		}
	}
	return false
}

# 2
type MagicDictionary struct {
	arr []string
}

func Constructor() MagicDictionary {
	return MagicDictionary{arr: make([]string, 0)}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	this.arr = dictionary
}

func (this *MagicDictionary) Search(searchWord string) bool {
	for i := 0; i < len(this.arr); i++ {
		word := this.arr[i]
		if len(word) != len(searchWord) {
			continue
		}
		count := 0
		for j := 0; j < len(searchWord); j++ {
			if word[j] != searchWord[j] {
				count++
				if count > 1 {
					break
				}
			}
		}
		if count == 1 {
			return true
		}
	}
	return false
}

# 3
type MagicDictionary struct {
	next   [26]*MagicDictionary // 下一级指针，如不限于小写字母，[26]=>[256]
	ending int                  // 次数（可以改为bool）
}

func Constructor() MagicDictionary {
	return MagicDictionary{
		next:   [26]*MagicDictionary{},
		ending: 0,
	}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	for i := 0; i < len(dictionary); i++ {
		word := dictionary[i]
		temp := this
		for _, v := range word {
			value := v - 'a'
			if temp.next[value] == nil {
				temp.next[value] = &MagicDictionary{
					next:   [26]*MagicDictionary{},
					ending: 0,
				}
			}
			temp = temp.next[value]
		}
		temp.ending++
	}
}

func (this *MagicDictionary) Search(searchWord string) bool {
	cur := this
	arr := []byte(searchWord)
	for i := 0; i < len(searchWord); i++ {
		b := searchWord[i]
		for j := 0; j < 26; j++ {
			if j+'a' == int(b) {
				continue
			}
			arr[i] = byte('a' + j)
			if cur.SearchWord(string(arr[i:])) == true {
				return true
			}
		}
		arr[i] = b
		if cur.next[int(b-'a')] == nil {
			return false
		}
		cur = cur.next[int(b-'a')]
	}
	return false
}

func (this *MagicDictionary) SearchWord(word string) bool {
	temp := this
	for _, v := range word {
		value := v - 'a'
		if temp = temp.next[value]; temp == nil {
			return false
		}
	}
	if temp.ending > 0 {
		return true
	}
	return false
}

677.键值映射(3)¶

题目

实现一个 MapSum 类，支持两个方法，insert和sum：
MapSum() 初始化 MapSum 对象
void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。
如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
示例：输入： ["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：[null, null, 3, null, 5]
解释： MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)
提示：1 <= key.length, prefix.length <= 50
key 和 prefix 仅由小写英文字母组成
1 <= val <= 1000
最多调用 50 次 insert 和 sum

解题思路

No.	思路	时间复杂度	空间复杂度
01	trie树	O(n)	O(n)
02	哈希辅助	O(n)	O(n)
03	哈希辅助	O(n)	O(n)

type MapSum struct {
	val  int
	next map[int32]*MapSum
}

func Constructor() MapSum {
	return MapSum{
		val:  0,
		next: make(map[int32]*MapSum),
	}
}

func (this *MapSum) Insert(key string, val int) {
	node := this
	for _, v := range key {
		if _, ok := node.next[v]; ok == false {
			temp := Constructor()
			node.next[v] = &temp
		}
		node = node.next[v]
	}
	node.val = val
}

func (this *MapSum) Sum(prefix string) int {
	node := this
	for _, v := range prefix {
		if _, ok := node.next[v]; ok == false {
			return 0
		}
		node = node.next[v]
	}
	res := 0
	queue := make([]*MapSum, 0)
	queue = append(queue, node)
	for len(queue) > 0 {
		temp := queue[0]
		queue = queue[1:]
		res = res + temp.val
		for _, v := range temp.next {
			queue = append(queue, v)
		}
	}
	return res
}

# 2
type MapSum struct {
	m    map[string]int
	data map[string]map[string]bool
}

func Constructor() MapSum {
	return MapSum{
		m:    make(map[string]int),
		data: make(map[string]map[string]bool),
	}
}

func (this *MapSum) Insert(key string, val int) {
	this.m[key] = val
	for i := 1; i <= len(key); i++ {
		str := key[:i]
		if _, ok := this.data[str]; ok == false {
			this.data[str] = make(map[string]bool)
		}
		this.data[str][key] = true
	}
}

func (this *MapSum) Sum(prefix string) int {
	res := 0
	for key := range this.data[prefix] {
		res = res + this.m[key]
	}
	return res
}

# 3
type MapSum struct {
	m map[string]int
}

func Constructor() MapSum {
	return MapSum{
		m: make(map[string]int),
	}
}

func (this *MapSum) Insert(key string, val int) {
	this.m[key] = val
}

func (this *MapSum) Sum(prefix string) int {
	res := 0
	for key, value := range this.m {
		if strings.HasPrefix(key, prefix) {
			res = res + value
		}
	}
	return res
}

678.有效的括号字符串(4)¶

题目

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。
有效字符串具有如下规则：
    任何左括号 ( 必须有相应的右括号 )。
    任何右括号 ) 必须有相应的左括号 ( 。
    左括号 ( 必须在对应的右括号之前 )。
    * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
    一个空字符串也被视为有效字符串。
示例 1:输入: "()" 输出: True
示例 2:输入: "(*)" 输出: True
示例 3:输入: "(*))" 输出: True
注意:字符串大小将在 [1，100] 范围内。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	双栈	O(n)	O(n)
03	递归	O(n!)	O(n)
04	遍历	O(n)	O(1)

func checkValidString(s string) bool {
	// 第1次把星号当左括号看
	left, right := 0, 0
	for i := 0; i < len(s); i++ {
		if s[i] == ')' {
			right++
		} else {
			left++
		}
		if right > left {
			return false
		}
	}
	// 第2次把星号当右括号看
	left, right = 0, 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left > right {
			return false
		}
	}
	return true
}

# 2
func checkValidString(s string) bool {
	stackL := make([]int, 0)
	stackS := make([]int, 0)
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stackL = append(stackL, i)
		} else if s[i] == '*' {
			stackS = append(stackS, i)
		} else {
			if len(stackL) > 0 {
				stackL = stackL[:len(stackL)-1]
			} else if len(stackS) > 0 {
				stackS = stackS[:len(stackS)-1]
			} else {
				return false
			}
		}
	}
	if len(stackL) > len(stackS) {
		return false
	}
	for len(stackL) > 0 && len(stackS) > 0 {
		a, b := stackL[len(stackL)-1], stackS[len(stackS)-1]
		if a > b {
			return false
		}
		stackL = stackL[:len(stackL)-1]
		stackS = stackS[:len(stackS)-1]
	}
	if len(stackL) == 0 {
		return true
	}
	return false
}

# 3
func checkValidString(s string) bool {
	return dfs(s, 0, 0)
}

func dfs(s string, index, count int) bool {
	if count < 0 {
		return false
	}
	for i := index; i < len(s); i++ {
		if s[i] == '(' {
			count++
		} else if s[i] == ')' {
			if count == 0 {
				return false
			}
			count--
		} else if s[i] == '*' {
			return dfs(s, i+1, count+1) || dfs(s, i+1, count-1) || dfs(s, i+1, count)
		}
	}
	return count == 0
}

# 4
func checkValidString(s string) bool {
	maxLeft, minLeft := 0, 0 // 可以有最多left和最少left的数量
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			maxLeft++
			minLeft++
		} else if s[i] == '*' {
			maxLeft++        // *当(用
			if minLeft > 0 { // *当)用
				minLeft--
			}
		} else if s[i] == ')' {
			maxLeft--
			if maxLeft < 0 {
				return false
			}
			if minLeft > 0 {
				minLeft--
			}
		}
	}
	return minLeft == 0
}

684.冗余连接(1)¶

题目

在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。
附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v]，满足u < v，表示连接顶点u和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。
如果有多个答案，则返回二维数组中最后出现的边。答案边[u, v] 应满足相同的格式u < v
示例 1：输入: [[1,2], [1,3], [2,3]] 输出: [2,3]
解释: 给定的无向图为:
  1
 / \
2 - 3
示例 2：输入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
    |   |
    4 - 3
注意:输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。

解题思路

No.	思路	时间复杂度	空间复杂度
01	并查集	O(n)	O(n)

func findRedundantConnection(edges [][]int) []int {
	n := len(edges) + 1
	fa := make([]int, n)
	for i := 0; i < n; i++ {
		fa[i] = i
	}
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		if find(fa, a) == find(fa, b) {
			return edges[i]
		}
		union(fa, a, b)
	}
	return nil
}

func union(fa []int, a, b int) {
	fa[find(fa, a)] = find(fa, b)
}

func find(fa []int, a int) int {
	for fa[a] != a {
		fa[a] = fa[fa[a]]
		a = fa[a]
	}
	return a
}

688.“马”在棋盘上的概率(2)¶

题目

已知一个NxN的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为(0, 0)，最右下角的记为(N-1, N-1)。
现有一个 “马”（也译作 “骑士”）位于(r, c)，并打算进行K 次移动。
如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。
现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了K次或跳到了棋盘外面。
求移动结束后，“马” 仍留在棋盘上的概率。
示例：输入: 3, 2, 0, 0 输出: 0.0625
解释: 输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。
对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。
注意：N 的取值范围为 [1, 25]
K的取值范围为 [0, 100]
开始时，“马” 总是位于棋盘上

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^3)	O(n^3)
02	动态规划	O(n^3)	O(n^2)

var dx = []int{2, 2, 1, 1, -1, -1, -2, -2}
var dy = []int{1, -1, 2, -2, 2, -2, 1, -1}

func knightProbability(n int, k int, row int, column int) float64 {
	dp := make([][][]float64, n) // dp[i][j][k]在位置[i,j]移动k步
	for i := 0; i < n; i++ {
		dp[i] = make([][]float64, n)
		for j := 0; j < n; j++ {
			dp[i][j] = make([]float64, k+1)
		}
	}
	dp[row][column][0] = float64(1)
	for a := 1; a <= k; a++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				for b := 0; b < 8; b++ {
					x := i + dx[b]
					y := j + dy[b]
					if 0 <= x && x < n && 0 <= y && y < n {
						dp[i][j][a] = dp[i][j][a] + dp[x][y][a-1]/8.0
					}
				}
			}
		}
	}
	res := float64(0)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			res = res + dp[i][j][k]
		}
	}
	return res
}

# 2
var dx = []int{2, 2, 1, 1, -1, -1, -2, -2}
var dy = []int{1, -1, 2, -2, 2, -2, 1, -1}

func knightProbability(n int, k int, row int, column int) float64 {
	dp := make([][]float64, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]float64, n)
	}
	dp[row][column] = float64(1)
	for a := 1; a <= k; a++ {
		temp := make([][]float64, n)
		for i := 0; i < n; i++ {
			temp[i] = make([]float64, n)
		}
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				for b := 0; b < 8; b++ {
					x := i + dx[b]
					y := j + dy[b]
					if 0 <= x && x < n && 0 <= y && y < n {
						temp[i][j] = temp[i][j] + dp[x][y]/8.0
					}
				}
			}
		}
		dp = temp
	}
	res := float64(0)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			res = res + dp[i][j]
		}
	}
	return res
}

692.前K个高频单词(2)¶

题目

给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
示例 1：输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。
示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，出现次数依次为 4, 3, 2 和 1 次。
注意：假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
    输入的单词均由小写字母组成。
扩展练习： 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

解题思路

No.	思路	时间复杂度	空间复杂度
01	堆	O(nlog(n))	O(n)
02	自定义排序	O(nlog(n))	O(n)

func topKFrequent(words []string, k int) []string {
	m := make(map[string]int)
	for _, v := range words {
		m[v]++
	}
	nodeHeap := &Heap{}
	heap.Init(nodeHeap)
	for key, value := range m {
		heap.Push(nodeHeap, Node{
			str: key,
			num: value,
		})
	}
	fmt.Println(nodeHeap)
	var res []string
	for i := 0; i < k; i++ {
		value := heap.Pop(nodeHeap).(Node)
		res = append(res, value.str)
	}
	return res
}

type Node struct {
	str string
	num int
}

type Heap []Node

func (h Heap) Len() int {
	return len(h)
}

func (h Heap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h Heap) Less(i, j int) bool {
	if h[i].num == h[j].num {
		return h[i].str < h[j].str
	}
	return h[i].num > h[j].num
}

func (h *Heap) Pop() interface{} {
	value := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return value
}

func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

# 2
func topKFrequent(words []string, k int) []string {
	var res []string
	m := make(map[string]int)
	for _, v := range words {
		m[v]++
	}
	var arr []Node
	for k, v := range m {
		arr = append(arr, Node{
			str: k,
			num: v,
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i].num == arr[j].num {
			return arr[i].str < arr[j].str
		}
		return arr[i].num > arr[j].num
	})
	for i := 0; i < k; i++ {
		res = append(res, arr[i].str)
	}
	return res
}

type Node struct {
	str string
	num int
}

695.岛屿的最大面积(2)¶

题目

给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 1:
[[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 。
示例 2:[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解题思路

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^2)	O(n)
02	深度优先搜索	O(n^2)	O(n)

func maxAreaOfIsland(grid [][]int) int {
	maxArea := 0
	for i := range grid {
		for j := range grid[i] {
			maxArea = max(maxArea, getArea(grid, i, j))
		}
	}
	return maxArea
}

func getArea(grid [][]int, i, j int) int {
	if grid[i][j] == 0 {
		return 0
	}
	grid[i][j] = 0
	area := 1
	if i != 0 {
		area = area + getArea(grid, i-1, j)
	}
	if j != 0 {
		area = area + getArea(grid, i, j-1)
	}
	if i != len(grid)-1 {
		area = area + getArea(grid, i+1, j)
	}
	if j != len(grid[0])-1 {
		area = area + getArea(grid, i, j+1)
	}
	return area
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

# 2
func maxAreaOfIsland(grid [][]int) int {
	res := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 1 {
				value := dfs(grid, i, j)
				if value > res {
					res = value
				}
			}
		}
	}
	return res
}

func dfs(grid [][]int, i, j int) int {
	if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) ||
		grid[i][j] == 0 {
		return 0
	}
	grid[i][j] = 0
	res := 1
	res = res + dfs(grid, i+1, j)
	res = res + dfs(grid, i-1, j)
	res = res + dfs(grid, i, j+1)
	res = res + dfs(grid, i, j-1)
	return res
}

698.划分为k个相等的子集(3)¶

题目

给定一个整数数组nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
提示：1 <= k <= len(nums) <= 16
0 < nums[i] < 10000

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划+状态压缩	O(n*2^n)	O(2^n)
02	回溯	O(2^n)	O(2^n)
03	回溯	O(2^n)	O(2^n)

func canPartitionKSubsets(nums []int, k int) bool {
	if k == 1 {
		return true
	}
	n := len(nums)
	sort.Ints(nums)
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + nums[i]
	}
	if sum%k != 0 { // 分不开：false
		return false
	}
	target := sum / k
	if nums[n-1] > target { // 有1个大于平均值：false
		return false
	}
	total := 1 << n
	arr := make([]int, total)
	dp := make([]bool, total)
	dp[0] = true
	for i := 0; i < total; i++ { // 枚举状态
		if dp[i] == false {
			continue
		}
		for j := 0; j < n; j++ { // 基于当前状态，添加1个数
			if i&(1<<j) > 0 { // 第j位为1，跳过
				continue
			}
			next := i | (1 << j) // 添加完后的值
			if dp[next] == true {
				continue
			}
			if arr[i]+nums[j] <= target {
				arr[next] = (arr[i] + nums[j])%target
				dp[next] = true
			} else {
				break // 已经排好序，后面会更大
			}
		}
	}
	return dp[total-1]
}

# 2
func canPartitionKSubsets(nums []int, k int) bool {
	if k == 1 {
		return true
	}
	n := len(nums)
	sort.Ints(nums)
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + nums[i]
	}
	if sum%k != 0 { // 分不开：false
		return false
	}
	target := sum / k
	if nums[n-1] > target { // 有1个大于平均值：false
		return false
	}
	return dfs(nums, k, target, 0, 0, make([]bool, n))
}

func dfs(nums []int, k int, target int, index int, count int, visited []bool) bool {
	if k == 0 {
		return true
	}
	if count == target {
		return dfs(nums, k-1, target, 0, 0, visited) // k减少一个，从头开始
	}
	for i := index; i < len(nums); i++ {
		if visited[i] == true { // nums[i]使用过
			continue
		}
		if count+nums[i] > target { // 大于目标值
			continue
		}
		visited[i] = true
		count = count + nums[i]
		if dfs(nums, k, target, i+1, count, visited) == true {
			return true
		}
		count = count - nums[i]
		visited[i] = false
	}
	return false
}

# 3
func canPartitionKSubsets(nums []int, k int) bool {
	if k == 1 {
		return true
	}
	n := len(nums)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + nums[i]
	}
	if sum%k != 0 { // 分不开：false
		return false
	}
	target := sum / k
	if nums[0] > target { // 有1个大于平均值：false
		return false
	}
	return dfs(nums, k, target, 0, make([]int, k))
}

// 不做剪枝，需要排序从大到小
func dfs(nums []int, k int, target int, index int, sum []int) bool {
	if index == len(nums) {
		return true
	}
	for i := 0; i < k; i++ {
		if sum[i] < target && sum[i]+nums[index] <= target {
			sum[i] = sum[i] + nums[index]
			if dfs(nums, k, target, index+1, sum) == true {
				return true
			}
			sum[i] = sum[i] - nums[index]
		}
	}
	return false
}

0601-0700-Hard¶

629.K个逆序对数组(2)¶

题目

给出两个整数n和k，找出所有包含从1到n的数字，且恰好拥有k个逆序对的不同的数组的个数。
逆序对的定义如下：对于数组的第i个和第j个元素，如果满i<j且a[i]>a[j]，则其为一个逆序对；否则不是。
由于答案可能很大，只需要返回 答案 mod 109+ 7 的值。
示例 1:输入: n = 3, k = 0输出: 1
解释: 只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。
示例 2:输入: n = 3, k = 1输出: 2
解释: 数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。
说明:n的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划-超时	O(n^3)	O(n^2)
01	动态规划	O(n^2)	O(n^2)
02	动态规划+前缀和	O(n^2)	O(n)

var mod = 1000000007

func kInversePairs(n int, k int) int {
	dp := make([][]int, n+1) // dp[n][k]表示1-n的排列中，包含k个逆序对
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, k+1)
		dp[i][0] = 1
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= k; j++ {
			// 前面i-1个数，i个插入位
			// 插入到最后，不增加： f(i,j) = f(i,j) + f(i-1,j)
			// 插入到倒数第2个，增加：f(i,j) = f(i,j) + f(i-1,j-1)
			// ...
			// 插入到倒数第i个，增加：f(i,j) = f(i,j) + f(i-1,j-i+1)
			// f(i,j) = f(i-1,j) + f(i-1,j-1) + ... + f(i-1,j-i+1)
			for l := max(0, j-i+1); l <= j; l++ {
				dp[i][j] = (dp[i][j] + dp[i-1][l]) % mod
			}
		}
	}
	return dp[n][k]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

# 1
var mod = 1000000007

func kInversePairs(n int, k int) int {
	dp := make([][]int, n+1) // dp[n][k]表示1-n的排列中，包含k个逆序对
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, k+1)
	}
	for i := 1; i <= n; i++ {
		dp[i][0] = 1
		// 最多i*(i-1)/2
		for j := 1; j <= k && j <= i*(i-1)/2; j++ {
			// 前面i-1个数，i个插入位
			// 插入到最后，不增加： f(i,j) = f(i,j) + f(i-1,j)
			// 插入到倒数第2个，增加：f(i,j) = f(i,j) + f(i-1,j-1)
			// ...
			// 插入到倒数第i个，增加：f(i,j) = f(i,j) + f(i-1,j-i+1)
			// => f(i,j) = f(i-1,j) + f(i-1,j-1) + ... + f(i-1,j-i+1)
			// f(i,j-1) = f(i-1, j-1)+ ...+f(i-1, j-i)
			// f(i,j) - f(i,j-1) = f(i-1,j)-f(i-1, j-i)
			// => f(i, j) = f(i,j-1)+f(i-1,j)-f(i-1,j-i)
			if j >= i {
				dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i]
			} else {
				dp[i][j] = dp[i][j-1] + dp[i-1][j]
			}
			if dp[i][j] >= 0 {
				dp[i][j] = dp[i][j] % mod
			} else {
				dp[i][j] = (dp[i][j] + mod) % mod
			}
		}
	}
	return dp[n][k]
}

# 2
var mod = 1000000007

func kInversePairs(n int, k int) int {
	dp := make([]int, k+1) // dp[k]包含k个逆序对的方案数
	dp[0] = 1
	sum := make([]int, k+2)
	sum[1] = 1
	for i := 1; i <= n; i++ {
		// 最多i*(i-1)/2
		for j := 1; j <= k && j <= i*(i-1)/2; j++ {
			// 前面i-1个数，i个插入位
			// 插入到最后，不增加： f(i,j) = f(i,j) + f(i-1,j)
			// 插入到倒数第2个，增加：f(i,j) = f(i,j) + f(i-1,j-1)
			// ...
			// 插入到倒数第i个，增加：f(i,j) = f(i,j) + f(i-1,j-i+1)
			// => f(i,j) = f(i-1,j) + f(i-1,j-1) + ... + f(i-1,j-i+1)
			// => f(j) = sum[j+1] - sum[j-i+1]
			dp[j] = (sum[j+1] - sum[max(0, j-i+1)]) % mod
		}
		for j := 1; j <= k; j++ {
			sum[j+1] = sum[j] + dp[j]
		}
	}
	return dp[k]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

630.课程表III(2)¶

题目

这里有 n 门不同的在线课程，他们按从 1 到 n编号。
每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d天。
一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。
给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。
示例：输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出: 3
解释: 这里一共有 4 门课程, 但是你最多可以修 3 门:
首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。
第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。
第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。
第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。
提示:整数 1 <= d, t, n <= 10,000 。
你不能同时修两门课程。

解题思路

No.	思路	时间复杂度	空间复杂度
01	堆	O(nlog(n))	O(n)
02	堆	O(nlog(n))	O(n)

func scheduleCourse(courses [][]int) int {
	sort.Slice(courses, func(i, j int) bool {
		return courses[i][1] < courses[j][1]
	})
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	sum := 0
	for i := 0; i < len(courses); i++ {
		count, endTime := courses[i][0], courses[i][1]
		if sum+count <= endTime { // 时间充足，学习
			sum = sum + count
			heap.Push(&intHeap, count)
		} else if intHeap.Len() > 0 && count < intHeap[0] {
			// 当前花费时间比之前时间最大耗时少，放弃之前最大耗时的课程
			top := heap.Pop(&intHeap).(int) // 最大放弃
			sum = sum - top                 // 减去最大
			sum = sum + count               // 添加当前
			heap.Push(&intHeap, count)
		}
	}
	return intHeap.Len()
}

type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	value := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return value
}

# 2
func scheduleCourse(courses [][]int) int {
	sort.Slice(courses, func(i, j int) bool {
		return courses[i][1] < courses[j][1]
	})
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	sum := 0
	res := 0
	for i := 0; i < len(courses); i++ {
		count, endTime := courses[i][0], courses[i][1]
		if sum+count <= endTime { // 时间充足，学习
			sum = sum + count
			res++
			heap.Push(&intHeap, count)
		} else if intHeap.Len() > 0 && count < intHeap[0] {
			// 当前花费时间比之前时间最大耗时少，放弃之前最大耗时的课程
			top := heap.Pop(&intHeap).(int) // 最大放弃
			sum = sum - top                 // 减去最大
			sum = sum + count               // 添加当前
			heap.Push(&intHeap, count)
		}
	}
	return res
}

type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	value := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return value
}

632.最小区间(2)¶

题目

你有k个 非递减排列 的整数列表。找到一个 最小 区间，使得k个列表中的每个列表至少有一个数包含在其中。
我们定义如果b-a < d-c或者在b-a == d-c时a < c，则区间 [a,b] 比 [c,d] 小。
示例 1：输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 输出：[20,24]
解释： 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
示例 2：输入：nums = [[1,2,3],[1,2,3],[1,2,3]] 输出：[1,1]
示例 3：输入：nums = [[10,10],[11,11]] 输出：[10,11]
示例 4：输入：nums = [[10],[11]] 输出：[10,11]
示例 5：输入：nums = [[1],[2],[3],[4],[5],[6],[7]] 输出：[1,7]
提示：nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i] 按非递减顺序排列

解题思路

No.	思路	时间复杂度	空间复杂度
01	堆	O(n^2log(n))	O(n)
02	滑动窗口	O(n^2)	O(n^2)

func smallestRange(nums [][]int) []int {
	nodeHeap := make(NodeHeap, 0) // 堆的大小为n
	heap.Init(&nodeHeap)
	maxValue, n := math.MinInt32, len(nums)
	// 问题可以转化为，从n个列表中各取1个数，使得这n个数中的最大值与最小值的差最小
	for i := 0; i < n; i++ {
		maxValue = max(maxValue, nums[i][0]) // 获取n个数的最大值
		heap.Push(&nodeHeap, Node{Id: i, Value: nums[i][0]})
		nums[i] = nums[i][1:] // 数组缩小，也可以使用下标标记
	}
	res := []int{math.MinInt32 / 10, math.MaxInt32 / 10}
	for { // 从小到大，每从堆取出一个最小值，再从所在组取出下一个较大的数放回去
		node := heap.Pop(&nodeHeap).(Node)       // 小根堆，取最小值
		if maxValue-node.Value < res[1]-res[0] { // 更新范围：最大值-最小值
			res = []int{node.Value, maxValue}
		}
		if len(nums[node.Id]) == 0 { // 退出条件：某一个数组首先访问完
			break
		}
		heap.Push(&nodeHeap, Node{Id: node.Id, Value: nums[node.Id][0]})
		maxValue = max(maxValue, nums[node.Id][0]) // 更新最大值
		nums[node.Id] = nums[node.Id][1:]
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type Node struct {
	Id    int
	Value int
}

type NodeHeap []Node

func (h NodeHeap) Len() int {
	return len(h)
}

// 小根堆<,大根堆变换方向>
func (h NodeHeap) Less(i, j int) bool {
	return h[i].Value < h[j].Value
}

func (h NodeHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}

func (h *NodeHeap) Pop() interface{} {
	value := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return value
}

# 2
func smallestRange(nums [][]int) []int {
	n := len(nums)
	m := make(map[int][]int)
	minValue, maxValue := math.MaxInt32, math.MinInt32
	for i := 0; i < n; i++ {
		for j := 0; j < len(nums[i]); j++ {
			minValue = min(minValue, nums[i][j])
			maxValue = max(maxValue, nums[i][j])
			m[nums[i][j]] = append(m[nums[i][j]], i) // 存的是值对应的下标
		}
	}
	res := []int{minValue, maxValue}
	left, right := minValue, minValue // 双指针
	window := make(map[int]int)       // 滑动窗口：包含n个列的时候，更新范围
	for ; right <= maxValue; right++ {
		if len(m[right]) > 0 {
			for i := 0; i < len(m[right]); i++ {
				window[m[right][i]]++ // 添加进窗口
			}
			for len(window) == n {
				if right-left < res[1]-res[0] {
					res = []int{left, right}
				}
				for i := 0; i < len(m[left]); i++ {
					window[m[left][i]]--
					if window[m[left][i]] == 0 {
						delete(window, m[left][i])
					}
				}
				left++
			}
		}
	}
	return res
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

664.奇怪的打印机(3)¶

题目

有台奇怪的打印机有以下两个特殊要求：
打印机每次只能打印同一个字符序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。
示例 1:输入: "aaabbb" 输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。
示例 2:输入: "aba" 输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划-递归	O(n^3)	O(n^2)
02	动态规划	O(n^3)	O(n^2)
03	动态规划	O(n^3)	O(n^2)

var dp [][]int

func strangePrinter(s string) int {
	n := len(s)
	dp = make([][]int, n) // dp[i][j] => 打印S[i], S[i+1], ..., S[j]所需的次数
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	return dfs(s, 0, n-1)
}

func dfs(s string, i, j int) int {
	if i > j {
		return 0
	}
	if dp[i][j] > 0 {
		return dp[i][j]
	}
	res := dfs(s, i+1, j) + 1 // 单独打印i
	for k := i + 1; k <= j; k++ {
		if s[i] == s[k] { // 相同的时候，打印i-k
			res = min(res, dfs(s, i, k-1)+dfs(s, k+1, j))
		}
	}
	dp[i][j] = res
	return res
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

# 2
func strangePrinter(s string) int {
	n := len(s)
	dp := make([][]int, n) // dp[i][j] => 打印S[i], S[i+1], ..., S[j]所需的次数
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}
	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			dp[i][j] = dp[i+1][j] + 1     // 单独打印i
			for k := i + 1; k <= j; k++ { // 相同的时候，打印i-k
				if s[i] == s[k] {
					dp[i][j] = min(dp[i][j], dp[i+1][k-1]+dp[k][j])
				}
			}
		}
	}
	return dp[0][n-1]
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

# 3
func strangePrinter(s string) int {
	n := len(s)
	dp := make([][]int, n+1) // dp[i][j] => 打印S[i], S[i+1], ..., S[j]所需的次数
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
		dp[i][i] = 1
	}
	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			dp[i][j] = dp[i+1][j] + 1
			for k := i + 1; k <= j; k++ {
				if s[i] == s[k] {
					dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])
				}
			}
		}
	}
	return dp[0][n-1]
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

668.乘法表中第k小的数(1)¶

题目

几乎每一个人都用乘法表。但是你能在乘法表中快速找到第k小的数字吗？
给定高度m、宽度n 的一张m * n的乘法表，以及正整数k，你需要返回表中第k小的数字。
例1：输入: m = 3, n = 3, k = 5 输出: 3
解释: 乘法表:
1	2	3
2	4	6
3	6	9
第5小的数字是 3 (1, 2, 2, 3, 3).
例 2：输入: m = 2, n = 3, k = 6 输出: 6
解释: 乘法表:
1	2	3
2	4	6
第6小的数字是 6 (1, 2, 2, 3, 4, 6).
注意：m 和n的范围在 [1, 30000] 之间。
k 的范围在 [1, m * n] 之间。

解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(nlog(n))	O(1)

func findKthNumber(m int, n int, k int) int {
	left := 1
	right := m * n
	for left < right {
		mid := left + (right-left)/2
		total := judge(m, n, k, mid)
		if total == true { // 满足条件，继续找
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func judge(m int, n int, k int, target int) bool {
	count := 0
	for i := 1; i <= m; i++ {
		count = count + min(target/i, n) // 当前行全部满足+n，部分满足+target/i
	}
	return count >= k
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

675.为高尔夫比赛砍树¶

题目¶

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个m x n 的矩阵表示， 在这个矩阵中：
0 表示障碍，无法触碰
1表示地面，可以行走
比 1 大的数表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
示例 1：输入：forest = [[1,2,3],[0,0,4],[7,6,5]] 输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。
示例 2：输入：forest = [[1,2,3],[0,0,0],[7,6,5]] 输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。
示例 3：输入：forest = [[2,3,4],[0,0,5],[8,7,6]] 输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。
提示：m == forest.length
n == forest[i].length
1 <= m, n <= 50
0 <= forest[i][j] <= 109

解题思路¶

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^2)	O(n)

679.24点游戏¶

题目¶

解题思路¶

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^2)	O(n)

685.冗余连接II¶

题目¶

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。
每一个节点只有一个父节点，除了根节点没有父节点。
输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。
附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。 
每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。
返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
示例1:输入: [[1,2], [1,3], [2,3]] 输出: [2,3]
解释: 给定的有向图如下:
  1
 / \
v   v
2-->3
示例 2:输入: [[1,2], [2,3], [3,4], [4,1], [1,5]] 输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3
注意:二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。

解题思路¶

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^2)	O(n)

689.三个无重叠子数组的最大和¶

题目¶

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组，并返回这三个子数组。
以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。
示例 1：输入：nums = [1,2,1,2,6,7,5,1], k = 2 输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
示例 2：输入：nums = [1,2,1,2,1,2,1,2,1], k = 2 输出：[0,2,4]
提示：1 <= nums.length <= 2 * 104
1 <= nums[i] <216
1 <= k <= floor(nums.length / 3)

解题思路¶

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^2)	O(n)