1601-1700-Easy¶

1603.设计停车系统(2)¶

题目

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类：
    ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类，
    三个参数分别对应每种停车位的数目。
    bool addCar(int carType) 检车是否有 carType 对应的停车位。 
    carType 有三种类型：大，中，小，分别用数字 1， 2 和 3 表示。
    一辆车只能停在  carType 对应尺寸的停车位中。
    如果没有空车位，请返回 false ，否则将该车停入车位并返回 true 。
示例 1：输入：["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
输出：[null, true, true, false, false]
解释：ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ，因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ，因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ，因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ，因为没有空的大车位，唯一一个大车位已经被占据了
提示： 0 <= big, medium, small <= 1000
    carType 取值为 1， 2 或 3
    最多会调用 addCar 函数 1000 次

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组	O(1)	O(1)
02	数组	O(1)	O(1)

type ParkingSystem struct {
	arr   [3]int
	total [3]int
}

func Constructor(big int, medium int, small int) ParkingSystem {
	return ParkingSystem{
		arr:   [3]int{big, medium, small},
		total: [3]int{0, 0, 0},
	}
}

func (this *ParkingSystem) AddCar(carType int) bool {
	index := carType - 1
	if this.total[index] < this.arr[index] {
		this.total[index]++
		return true
	}
	return false
}

# 2
type ParkingSystem struct {
	arr [3]int
}

func Constructor(big int, medium int, small int) ParkingSystem {
	return ParkingSystem{
		arr: [3]int{big, medium, small},
	}
}

func (this *ParkingSystem) AddCar(carType int) bool {
	if this.arr[carType-1] > 0 {
		this.arr[carType-1]--
		return true
	}
	return false
}

1608.特殊数组的特征值(3)¶

题目

给你一个非负整数数组 nums 。
如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，
那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。
否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
示例 1：输入：nums = [3,5] 输出：2
解释：有 2 个元素（3 和 5）大于或等于 2 。
示例 2：输入：nums = [0,0] 输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。
示例 3：输入：nums = [0,4,3,0,4] 输出：3
解释：有 3 个元素大于或等于 3 。
示例 4：输入：nums = [3,6,7,7,0] 输出：-1
提示：1 <= nums.length <= 100
    0 <= nums[i] <= 1000

解题思路

No.	思路	时间复杂度	空间复杂度
01	计数排序	O(n)	O(n)
02	暴力法	O(n^2)	O(1)
03	排序	O(nlog(n))	O(1)

func specialArray(nums []int) int {
	arr := make([]int, 1001)
	for i := 0; i < len(nums); i++ {
		arr[nums[i]]++
	}
	for i := len(arr) - 2; i >= 0; i-- {
		arr[i] = arr[i] + arr[i+1]
	}
	for i := 0; i <= len(nums); i++ {
		if arr[i] == i {
			return i
		}
	}
	return -1
}

# 2
func specialArray(nums []int) int {
	for i := 0; i <= len(nums); i++ {
		count := 0
		for j := 0; j < len(nums); j++ {
			if nums[j] >= i {
				count++
			}
		}
		if count == i {
			return i
		}
	}
	return -1
}

# 3
func specialArray(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	if nums[0] >= n {
		return n
	}
	for i := 1; i < n; i++ {
		target := n - i
		if nums[i] >= target && target > nums[i-1] {
			return target
		}
	}
	return -1
}

1614.括号的最大嵌套深度(2)¶

题目

如果字符串满足一下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
    字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
    字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
    字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。
类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
    depth("") = 0
    depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
    depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串
例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），
而 ")(" 、"(()" 都不是 有效括号字符串 。
给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
示例 1：输入：s = "(1+(2*3)+((8)/4))+1" 输出：3
解释：数字 8 在嵌套的 3 层括号中。
示例 2：输入：s = "(1)+((2))+(((3)))" 输出：3
示例 3：输入：s = "1+(2*3)/(2-1)" 输出：1
示例 4：输入：s = "1" 输出：0
提示： 1 <= s.length <= 100
    s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
    题目数据保证括号表达式 s 是 有效的括号表达式

解题思路

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

func maxDepth(s string) int {
	res := 0
	count := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			count++
		} else if s[i] == ')' {
			if count > res {
				res = count
			}
			count--
		}
	}
	return res
}

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

1619.删除某些元素后的数组均值(2)¶

题目

给你一个整数数组arr，请你删除最小5%的数字和最大 5%的数字后，剩余数字的平均值。
与 标准答案误差在10-5的结果都被视为正确结果。
示例 1：输入：arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3] 输出：2.00000
解释：删除数组中最大和最小的元素后，所有元素都等于 2，所以平均值为 2 。
示例 2：输入：arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0] 输出：4.00000
示例 3：输入：arr =[6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,
3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
输出：4.77778
示例 4：输入：arr =[9,7,8,7,7,8,4,4,6,8,8,7,6,8,8,9,2,6,0,0,1,10,8,6,3,3,5,1,10,9,0,
7,10,0,10,4,1,10,6,9,3,6,0,0,2,7,0,6,7,2,9,7,7,3,0,1,6,1,10,3]
输出：5.27778
示例 5：输入：arr = [4,8,4,10,0,7,1,3,7,8,8,3,4,1,6,2,1,1,8,0,9,8,0,3,9,10,3,10,1,10,7,3,2,1,4,
9,10,7,6,4,0,8,5,1,2,1,6,2,5,0,7,10,9,10,3,7,10,5,8,5,7,6,7,6,10,9,5,10,5,5,
7,2,10,7,7,8,2,0,1,1]
输出：5.29167
提示：20 <= arr.length <= 1000
arr.length是20的倍数
0 <= arr[i] <= 105

解题思路

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

func trimMean(arr []int) float64 {
	temp := make([]float64, 0)
	for i := 0; i < len(arr); i++ {
		temp = append(temp, float64(arr[i]))
	}
	sort.Float64s(temp)
	var sum float64
	count := int(float64(len(arr)) * 0.05)
	for i := count; i < len(temp)-count; i++ {
		sum = sum + temp[i]
	}
	return sum / float64(len(arr)-2*count)
}

# 2
func trimMean(arr []int) float64 {
	n := len(arr)
	count := n / 20
	sort.Ints(arr)
	sum := 0
	for i := count; i < n-count; i++ {
		sum += arr[i]
	}
	return float64(sum) / float64(n-2*count)
}

1624.两个相同字符之间的最长子字符串(2)¶

题目

给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。
如果不存在这样的子字符串，返回 -1 。
子字符串 是字符串中的一个连续字符序列。
示例 1：输入：s = "aa" 输出：0
解释：最优的子字符串是两个 'a' 之间的空子字符串。
示例 2：输入：s = "abca" 输出：2
解释：最优的子字符串是 "bc" 。
示例 3：输入：s = "cbzxy" 输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。
示例 4：输入：s = "cabbac" 输出：4
解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。
提示：1 <= s.length <= 300  s 只含小写英文字母

解题思路

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

func maxLengthBetweenEqualCharacters(s string) int {
	m := make(map[byte]int)
	res := -1
	for i := 0; i < len(s); i++ {
		if value, ok := m[s[i]]; ok {
			res = max(res, i-value-1)
		} else {
			m[s[i]] = i
		}
	}
	return res
}

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

# 2
func maxLengthBetweenEqualCharacters(s string) int {
	res := -1
	for i := 0; i < len(s); i++ {
		for j := i + 1; j < len(s); j++ {
			if s[i] == s[j] {
				res = max(res, j-i-1)
			}
		}
	}
	return res
}

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

1629.按键持续时间最长的键(1)¶

题目

LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 n 个），每次一个。
给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。
releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。
字符串和数组的 下标都从 0 开始 。
第 0 个键在时间为 0 时被按下，接下来每个键都 恰好 在前一个键松开时被按下。
测试人员想要找出按键 持续时间最长 的键。
第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，
第 0 次按键的持续时间为 releaseTimes[0] 。
注意，测试期间，同一个键可以在不同时刻被多次按下，而每次的持续时间都可能不同。
请返回按键 持续时间最长 的键，如果有多个这样的键，则返回 按字母顺序排列最大 的那个键。
示例 1：输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd" 输出："c"
解释：按键顺序和持续时间如下：
按下 'c' ，持续时间 9（时间 0 按下，时间 9 松开）
按下 'b' ，持续时间 29 - 9 = 20（松开上一个键的时间 9 按下，时间 29 松开）
按下 'c' ，持续时间 49 - 29 = 20（松开上一个键的时间 29 按下，时间 49 松开）
按下 'd' ，持续时间 50 - 49 = 1（松开上一个键的时间 49 按下，时间 50 松开）
按键持续时间最长的键是 'b' 和 'c'（第二次按下时），持续时间都是 20
'c' 按字母顺序排列比 'b' 大，所以答案是 'c'
示例 2：输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda" 输出："a"
解释：按键顺序和持续时间如下：
按下 's' ，持续时间 12
按下 'p' ，持续时间 23 - 12 = 11
按下 'u' ，持续时间 36 - 23 = 13
按下 'd' ，持续时间 46 - 36 = 10
按下 'a' ，持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ，持续时间 16
提示： releaseTimes.length == n
    keysPressed.length == n
    2 <= n <= 1000
    0 <= releaseTimes[i] <= 109
    releaseTimes[i] < releaseTimes[i+1]
    keysPressed 仅由小写英文字母组成

解题思路

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

func slowestKey(releaseTimes []int, keysPressed string) byte {
	res := 0
	maxValue := releaseTimes[0]
	for i := 1; i < len(releaseTimes); i++ {
		if releaseTimes[i]-releaseTimes[i-1] > maxValue {
			maxValue = releaseTimes[i] - releaseTimes[i-1]
			res = i
		} else if releaseTimes[i]-releaseTimes[i-1] == maxValue &&
			keysPressed[i] > keysPressed[res] {
			res = i
		}
	}
	return keysPressed[res]
}

1636.按照频率将数组升序排序(1)¶

题目

给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。
如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。 
请你返回排序后的数组。
示例 1：输入：nums = [1,1,2,2,2,3] 输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。
示例 2：输入：nums = [2,3,1,3,2] 输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。
示例 3：输入：nums = [-1,1,-6,4,5,-6,1,4,1] 输出：[5,-1,4,4,-6,-6,1,1,1]
提示：1 <= nums.length <= 100
    -100 <= nums[i] <= 100

解题思路

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

func frequencySort(nums []int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	arr := make([][2]int, 0)
	for k, v := range m {
		arr = append(arr, [2]int{k, v})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i][1] == arr[j][1] {
			return arr[i][0] > arr[j][0]
		}
		return arr[i][1] < arr[j][1]
	})
	res := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		for j := 0; j < arr[i][1]; j++ {
			res = append(res, arr[i][0])
		}
	}
	return res
}

1640.能否连接形成数组(2)¶

题目

给你一个整数数组 arr ，数组中的每个整数 互不相同 。
另有一个由整数数组构成的数组 pieces，其中的整数也 互不相同 。
请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。
如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。
示例 1：输入：arr = [85], pieces = [[85]]输出：true
示例 2：输入：arr = [15,88], pieces = [[88],[15]] 输出：true
解释：依次连接 [15] 和 [88]
示例 3：输入：arr = [49,18,16], pieces = [[16,18,49]] 输出：false
解释：即便数字相符，也不能重新排列 pieces[0]
示例 4：输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]] 输出：true
解释：依次连接 [91]、[4,64] 和 [78]
示例 5：输入：arr = [1,3,5,7], pieces = [[2,4,6,8]] 输出：false
提示：1 <= pieces.length <= arr.length <= 100
    sum(pieces[i].length) == arr.length
    1 <= pieces[i].length <= arr.length
    1 <= arr[i], pieces[i][j] <= 100
    arr 中的整数 互不相同
    pieces 中的整数 互不相同（也就是说，如果将 pieces 扁平化成一维数组，数组中的所有整数互不相同）

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历标记	O(n^2)	O(1)
02	哈希辅助	O(n)	O(n)

func canFormArray(arr []int, pieces [][]int) bool {
	for i := 0; i < len(pieces); i++ {
		value := pieces[i]
		length := len(value)
		flag := false
		for j := 0; j < len(arr); j++ {
			if arr[j] == value[0] {
				flag = true
				for k := j; k < j+length && k < len(arr); k++ {
					if arr[k] != value[k-j] {
						return false
					} else {
						arr[k] = 0
					}
				}
				break
			}
		}
		if flag == false {
			return false
		}
	}
	for i := 0; i < len(arr); i++ {
		if arr[i] != 0 {
			return false
		}
	}
	return true
}

# 2
func canFormArray(arr []int, pieces [][]int) bool {
	m := make(map[int]int)
	for i := 0; i < len(arr); i++ {
		m[arr[i]] = i
	}
	for i := 0; i < len(pieces); i++ {
		if _, ok := m[pieces[i][0]]; !ok {
			return false
		}
		for k := 0; k < len(pieces[i])-1; k++ {
			if m[pieces[i][k+1]]-m[pieces[i][k]] != 1 {
				return false
			}
		}
	}
	return true
}

1646.获取生成数组中的最大值(1)¶

题目

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
nums[0] = 0
nums[1] = 1
当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
返回生成数组 nums 中的 最大 值。
示例 1：输入：n = 7 输出：3
解释：根据规则：
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此，nums = [0,1,1,2,1,3,2,3]，最大值 3
示例 2：输入：n = 2 输出：1
解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1
示例 3：输入：n = 3 输出：2
解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2
提示：0 <= n <= 100

解题思路

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

func getMaximumGenerated(n int) int {
	arr := make([]int, n+3)
	arr[0] = 0
	arr[1] = 1
	res := 0
	for i := 0; i <= n; i++ {
		if i%2 == 0 {
			arr[i] = arr[i/2]
		} else {
			arr[i] = arr[i/2] + arr[(i+1)/2]
		}
		if arr[i] > res {
			res = arr[i]
		}
	}
	return res
}

1652.拆炸弹(1)¶

题目

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为n的循环数组code以及一个密钥k。
为了获得正确的密码，你需要替换掉每一个数字。所有数字会同时被替换。
如果k > 0，将第i个数字用 接下来k个数字之和替换。
如果k < 0，将第i个数字用 之前k个数字之和替换。
如果k == 0，将第i个数字用0替换。
由于code是循环的，code[n-1]下一个元素是code[0]，且code[0]前一个元素是code[n-1]。
给你 循环数组code和整数密钥k，请你返回解密后的结果来拆除炸弹！
示例 1：输入：code = [5,7,1,4], k = 3 输出：[12,10,16,13]
解释：每个数字都被接下来 3 个数字之和替换。
解密后的密码为 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到数组是循环连接的。
示例 2：输入：code = [1,2,3,4], k = 0 输出：[0,0,0,0]
解释：当 k 为 0 时，所有数字都被 0 替换。
示例 3：输入：code = [2,4,9,3], k = -2 输出：[12,5,6,13]
解释：解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。
如果 k 是负数，那么和为 之前 的数字。
提示：n == code.length
1 <= n<= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1

解题思路

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

func decrypt(code []int, k int) []int {
	n := len(code)
	res := make([]int, n)
	if k == 0 {
		return res
	}
	for i := 0; i < n; i++ {
		sum := 0
		for j := 1; j <= abs(k); j++ {
			if k > 0 {
				sum = sum + code[(i+j+n)%n]
			} else {
				sum = sum + code[(i-j+n)%n]
			}
		}
		res[i] = sum
	}
	return res
}

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

1656.设计有序流(1)¶

题目

有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。
不存在 id 相同的两个(id, value) 对。
设计一个流，以 任意 顺序获取 n个(id, value)对，并在多次调用时 按 id 递增的顺序 返回一些值。
实现 OrderedStream 类：
OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，
并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1。
否则，返回一个空列表。
示例：输入["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
输出[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
解释: OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]
提示：1 <= n <= 1000
1 <= id <= n
value.length == 5
value 仅由小写字母组成
每次调用 insert 都会使用一个唯一的 id
恰好调用 n 次 insert

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组	O(n)	O(n)

type OrderedStream struct {
	arr []string
	ptr int
}

func Constructor(n int) OrderedStream {
	return OrderedStream{
		arr: make([]string, n+1),
		ptr: 1,
	}
}

func (this *OrderedStream) Insert(id int, value string) []string {
	res := make([]string, 0)
	this.arr[id] = value
	if this.ptr < id-1 {
		return res
	}
	for i := this.ptr; i < len(this.arr); i++ {
		if this.arr[i] == "" {
			break
		}
		res = append(res, this.arr[i])
		this.ptr++
	}
	return res
}

1662.检查两个字符串数组是否相等(2)¶

题目

给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。
数组表示的字符串是由数组中的所有元素 按顺序 连接形成的字符串。
示例 1：输入：word1 = ["ab", "c"], word2 = ["a", "bc"] 输出：true
解释：word1 表示的字符串为 "ab" + "c" -> "abc"
word2 表示的字符串为 "a" + "bc" -> "abc"
两个字符串相同，返回 true
示例 2：输入：word1 = ["a", "cb"], word2 = ["ab", "c"] 输出：false
示例 3：输入：word1  = ["abc", "d", "defg"], word2 = ["abcddefg"] 输出：true
提示：1 <= word1.length, word2.length <= 103
1 <= word1[i].length, word2[i].length <= 103
1 <= sum(word1[i].length), sum(word2[i].length) <= 103
word1[i] 和 word2[i] 由小写字母组成

解题思路

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

func arrayStringsAreEqual(word1 []string, word2 []string) bool {
	return strings.Join(word1,"") == strings.Join(word2,"")
}

# 2
func arrayStringsAreEqual(word1 []string, word2 []string) bool {
	str1 := ""
	str2 := ""
	for i := 0; i < len(word1); i++ {
		str1 = str1 + word1[i]
	}
	for i := 0; i < len(word2); i++ {
		str2 = str2 + word2[i]
	}
	return str1 == str2
}

1668.最大重复子字符串(1)¶

题目

给你一个字符串sequence，如果字符串 word连续重复k次形成的字符串是sequence的一个子字符串，
那么单词word 的 重复值为 k 。单词 word的 最大重复值是单词word在sequence中最大的重复值。
如果word不是sequence的子串，那么重复值k为 0 。
给你一个字符串 sequence和 word，请你返回 最大重复值k 。
示例 1：输入：sequence = "ababc", word = "ab" 输出：2
解释："abab" 是 "ababc" 的子字符串。
示例 2：输入：sequence = "ababc", word = "ba" 输出：1
解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。
示例 3：输入：sequence = "ababc", word = "ac" 输出：0
解释："ac" 不是 "ababc" 的子字符串。
提示：1 <= sequence.length <= 100
1 <= word.length <= 100
sequence 和word都只包含小写英文字母。

解题思路

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

func maxRepeating(sequence string, word string) int {
	res := 0
	for i := 1; ; i++ {
		if strings.Contains(sequence, strings.Repeat(word, i)) == false {
			break
		} else {
			res = i
		}
	}
	return res
}

1672.最富有客户的资产总量(1)¶

题目

给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i位客户在第 j 家银行托管的资产数量。
返回最富有客户所拥有的 资产总量 。
客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
示例 1：输入：accounts = [[1,2,3],[3,2,1]] 输出：6
解释：第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。
示例 2：输入：accounts = [[1,5],[7,3],[3,5]] 输出：10
解释：第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10 
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的，资产总量是 10
示例 3：输入：accounts = [[2,8,7],[7,1,3],[1,9,5]] 输出：17
提示：m ==accounts.length
n ==accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100

解题思路

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

func maximumWealth(accounts [][]int) int {
	res := 0
	for i := 0; i < len(accounts); i++ {
		sum := 0
		for j := 0; j < len(accounts[i]); j++ {
			sum = sum + accounts[i][j]
		}
		if sum > res {
			res = sum
		}
	}
	return res
}

1678.设计Goal解析器(2)¶

题目

请你设计一个可以解释字符串 command 的 Goal 解析器 。
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。
Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al" 。
然后，按原顺序将经解释得到的字符串连接成一个字符串。
给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。
示例 1：输入：command = "G()(al)" 输出："Goal"
解释：Goal 解析器解释命令的步骤如下所示：
G -> G
() -> o
(al) -> al
最后连接得到的结果是 "Goal"
示例 2：输入：command = "G()()()()(al)" 输出："Gooooal"
示例 3：输入：command = "(al)G(al)()()G" 输出："alGalooG"
提示：1 <= command.length <= 100
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成

解题思路

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

func interpret(command string) string {
	command = strings.ReplaceAll(command, "(al)", "al")
	command = strings.ReplaceAll(command, "()", "o")
	return command
}

# 2
func interpret(command string) string {
	res := ""
	for i := 0; i < len(command); {
		if command[i] == 'G' {
			res = res + "G"
			i = i + 1
		} else if command[i] == '(' {
			if command[i+1] == ')' {
				res = res + "o"
				i = i + 2
			} else {
				res = res + "al"
				i = i + 4
			}
		}
	}
	return res
}

1684.统计一致字符串的数目(1)¶

题目

给你一个由不同字符组成的字符串allowed和一个字符串数组words。
如果一个字符串的每一个字符都在 allowed中，就称这个字符串是 一致字符串。
请你返回words数组中一致字符串的数目。
示例 1：输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"] 输出：2
解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。
示例 2：输入：allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"] 输出：7
解释：所有字符串都是一致的。
示例 3：输入：allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"] 输出：4
解释：字符串 "cc"，"acd"，"ac" 和 "d" 是一致字符串。
提示：1 <= words.length <= 104
1 <= allowed.length <= 26
1 <= words[i].length <= 10
allowed中的字符 互不相同。
words[i] 和allowed只包含小写英文字母。

解题思路

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

func countConsistentStrings(allowed string, words []string) int {
	res := 0
	m := make(map[byte]bool)
	for i := 0; i < len(allowed); i++ {
		m[allowed[i]] = true
	}

	for _, word := range words {
		flag := true
		for i := 0; i < len(word); i++ {
			if _, ok := m[word[i]]; !ok {
				flag = false
				break
			}
		}
		if flag == true {
			res++
		}
	}
	return res
}

1688.比赛中的配对次数(2)¶

题目

给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：
如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。
总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。
总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数，直到决出获胜队伍为止。
示例 1：输入：n = 7 输出：6
解释：比赛详情：
- 第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
- 第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6
示例 2：输入：n = 14 输出：13
解释：比赛详情：
- 第 1 轮：队伍数 = 14 ，配对次数 = 7 ，7 支队伍晋级。
- 第 2 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。 
- 第 3 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 4 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 7 + 3 + 2 + 1 = 13
提示：1 <= n <= 200

解题思路

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

func numberOfMatches(n int) int {
	res := 0
	for n > 1 {
		res = res + n/2
		n = n/2 + n%2
	}
	return res
}

# 2
func numberOfMatches(n int) int {
	// 共有n个队伍,一个冠军,需要淘汰n-1个 队伍。
	// 每一场比赛淘汰一个队伍,因此进行了n-1场比赛。
	return n - 1
}

1694.重新格式化电话号码(1)¶

题目

给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。
请你按下述方式重新格式化电话号码。
首先，删除 所有的空格和破折号。
其次，将数组从左到右 每 3 个一组 分块，直到 剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
2 个数字：单个含 2 个数字的块。
3 个数字：单个含 3 个数字的块。
4 个数字：两个分别含 2 个数字的块。
最后用破折号将这些块连接起来。
注意，重新格式化过程中 不应该 生成仅含 1 个数字的块，并且 最多 生成两个含 2 个数字的块。
返回格式化后的电话号码。
示例 1：输入：number = "1-23-45 6" 输出："123-456"
解释：数字是 "123456"
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 3 个数字，将它们放入单个含 3 个数字的块。第 2 个块是 "456" 。
连接这些块后得到 "123-456" 。
示例 2：输入：number = "123 4-567" 输出："123-45-67"
解释：数字是 "1234567".
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 4 个数字，所以将它们分成两个含 2 个数字的块。这 2 块分别是 "45" 和 "67" 。
连接这些块后得到 "123-45-67" 。
示例 3：输入：number = "123 4-5678" 输出："123-456-78"
解释：数字是 "12345678" 。
步骤 1：第 1 个块 "123" 。
步骤 2：第 2 个块 "456" 。
步骤 3：剩下 2 个数字，将它们放入单个含 2 个数字的块。第 3 个块是 "78" 。
连接这些块后得到 "123-456-78" 。
示例 4：输入：number = "12" 输出："12"
示例 5：输入：number = "--17-5 229 35-39475 " 输出："175-229-353-94-75"
提示：2 <= number.length <= 100
number 由数字和字符 '-' 及 ' ' 组成。
number 中至少含 2 个数字。

解题思路

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

func reformatNumber(number string) string {
	str := strings.ReplaceAll(number, "-", "")
	str = strings.ReplaceAll(str, " ", "")
	res := ""
	for len(str) > 4 {
		res = res + str[:3] + "-"
		str = str[3:]
	}
	if len(str) == 4 {
		res = res + str[:2] + "-" + str[2:]
	} else {
		res = res + str
	}
	return res
}

1700.无法吃午餐的学生数量(1)¶

题目

学校的自助午餐提供圆形和方形的三明治，分别用数字0和1表示。
所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个栈里，每一轮：
如果队列最前面的学生喜欢栈顶的三明治，那么会拿走它并离开队列。
否则，这名学生会放弃这个三明治并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组students 和sandwiches，
其中sandwiches[i]是栈里面第i个三明治的类型（i = 0是栈的顶部），
students[j]是初始队列里第j名学生对三明治的喜好（j = 0是队列的最开始位置）。
请你返回无法吃午餐的学生数量。
示例 1：输入：students = [1,1,0,0], sandwiches = [0,1,0,1] 输出：0 
解释：- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，
三明治栈为 sandwiches = [1,0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
所以所有学生都有三明治吃。
示例 2：输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] 输出：3
提示：1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i]要么是0，要么是1。
students[i]要么是0，要么是1。

解题思路

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

func countStudents(students []int, sandwiches []int) int {
	a, b := 0, 0
	for i := 0; i < len(students); i++ {
		if students[i] == 0 {
			a++
		} else {
			b++
		}
	}
	for i := 0; i < len(sandwiches); i++ {
		if sandwiches[i] == 0 && a > 0 {
			a--
		} else if sandwiches[i] == 1 && b > 0 {
			b--
		} else {
			break
		}
	}
	return a + b
}

1601-1700-Medium¶

1604.警告一小时内使用相同员工卡大于等于三次的人(2)¶

题目

力扣公司的员工都使用员工卡来开办公室的门。
每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。
如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。
给你字符串数组 keyName 和 keyTime ，
其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。
使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。
请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。
请注意 "10:00" - "11:00" 视为一个小时时间范围内，
而 "23:51" - "00:10" 不被视为一小时内，因为系统记录的是某一天内的使用情况。
示例 1：输入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], 
keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
输出：["daniel"]
解释："daniel" 在一小时内使用了 3 次员工卡（"10:00"，"10:40"，"11:00"）。
示例 2：输入：keyName = ["alice","alice","alice","bob","bob","bob","bob"], 
keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
输出：["bob"]
解释："bob" 在一小时内使用了 3 次员工卡（"21:00"，"21:20"，"21:30"）。
示例 3：输入：keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
输出：[]
示例 4：输入：keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], 
keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
输出：["clare","leslie"]
提示：1 <= keyName.length, keyTime.length <= 105
    keyName.length == keyTime.length
    keyTime 格式为 "HH:MM" 。
    保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
    1 <= keyName[i].length <= 10
    keyName[i] 只包含小写英文字母。

解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希+排序+遍历	O(nlog(n))	O(n)
02	哈希+排序+滑动窗口	O(nlog(n))	O(n)

func alertNames(keyName []string, keyTime []string) []string {
	m := make(map[string][]int)
	for i := 0; i < len(keyName); i++ {
		m[keyName[i]] = append(m[keyName[i]], strToInt(keyTime[i]))
	}
	res := make([]string, 0)
	for k, v := range m {
		sort.Ints(v)
		first := v[0]
		second := v[0]
		count := 1
		for i := 1; i < len(v); i++ {
			if v[i] > first && v[i]-first <= 60 {
				second = v[i]
				count++
			} else {
				first = second
				second = v[i]
				count = 2
			}
			if count >= 3 {
				res = append(res, k)
				break
			}
		}
	}
	sort.Strings(res)
	return res
}

func strToInt(str string) int {
	arr := strings.Split(str, ":")
	hour, _ := strconv.Atoi(arr[0])
	minute, _ := strconv.Atoi(arr[1])
	return hour*60 + minute
}

# 2
func alertNames(keyName []string, keyTime []string) []string {
	m := make(map[string][]int)
	for i := 0; i < len(keyName); i++ {
		m[keyName[i]] = append(m[keyName[i]], strToInt(keyTime[i]))
	}
	res := make([]string, 0)
	for k, v := range m {
		sort.Ints(v)
		for i := 0; i < len(v)-2; i++ {
			if v[i+2]-v[i] <= 60 {
				res = append(res, k)
				break
			}
		}
	}
	sort.Strings(res)
	return res
}

func strToInt(str string) int {
	arr := strings.Split(str, ":")
	hour, _ := strconv.Atoi(arr[0])
	minute, _ := strconv.Atoi(arr[1])
	return hour*60 + minute
}

1605.给定行和列的和求可行矩阵(1)¶

题目

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， 
colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。
请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，
且该矩阵满足 rowSum 和 colSum 的要求。
请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。
示例 1：输入：rowSum = [3,8], colSum = [4,7] 输出：[[3,0],
      [1,7]]
解释：第 0 行：3 + 0 = 0 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
                  [3,5]]
示例 2：输入：rowSum = [5,7,10], colSum = [8,6,8] 
输出：[[0,5,0],
      [6,1,0],
      [2,0,8]]
示例 3：输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
      [6,0,3]]
示例 4：输入：rowSum = [1,0], colSum = [1]
输出：[[1],
      [0]]
示例 5：输入：rowSum = [0], colSum = [0]
输出：[[0]]
提示：1 <= rowSum.length, colSum.length <= 500
    0 <= rowSum[i], colSum[i] <= 108
    sum(rows) == sum(columns)

解题思路

No.	思路	时间复杂度	空间复杂度
01	贪心	O(n^2)	O(n^2)

func restoreMatrix(rowSum []int, colSum []int) [][]int {
	n := len(rowSum)
	m := len(colSum)
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			value := min(rowSum[i], colSum[j])
			res[i][j] = value
			rowSum[i] = rowSum[i] - value
			colSum[j] = colSum[j] - value
		}
	}
	return res
}

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

1609.奇偶树(1)¶

题目

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
    二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
    偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
    奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
示例 1：输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，
因此这是一棵奇偶树。
示例 2：输入：root = [5,4,2,3,3,7] 输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
示例 3：输入：root = [5,9,1,3,5,7] 输出：false
解释：1 层上的节点值应为偶数。
示例 4：输入：root = [1]输出：true
示例 5：输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17] 输出：true
提示：树中节点数在范围 [1, 105] 内
    1 <= Node.val <= 106

解题思路

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

func isEvenOddTree(root *TreeNode) bool {
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	level := 1
	for len(queue) > 0 {
		length := len(queue)
		temp := make([]int, 0)
		for i := 0; i < length; i++ {
			temp = append(temp, queue[i].Val)
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		if level%2 == 0 {
			for j := 0; j < len(temp)/2; j++ {
				temp[j], temp[len(temp)-1-j] = temp[len(temp)-1-j], temp[j]
			}
		}
		for i := 0; i < len(temp); i++ {
			if i < len(temp)-1 && temp[i] >= temp[i+1] {
				return false
			}
			if temp[i]%2 != level%2 {
				return false
			}
		}
		queue = queue[length:]
		level++
	}
	return true
}

1615.最大网络秩(1)¶

题目

n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。
每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。
如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。
示例 1：输入：n = 4, roads = [[0,1],[0,3],[1,2],[1,3]] 输出：4
解释：城市 0 和 1 的网络秩是 4，因为共有 4 条道路与城市 0 或 1 相连。
位于 0 和 1 之间的道路只计算一次。
示例 2：输入：n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]] 输出：5
解释：共有 5 条道路与城市 1 或 2 相连。
示例 3：输入：n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]] 输出：5
解释：2 和 5 的网络秩为 5，注意并非所有的城市都需要连接起来。
提示：2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= ai, bi<= n-1
ai!=bi
每对城市之间 最多只有一条道路相连

解题思路

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

func maximalNetworkRank(n int, roads [][]int) int {
	arr := make([]int, n)
	m := make(map[int]int)
	for i := 0; i < len(roads); i++ {
		a, b := roads[i][0], roads[i][1]
		arr[a]++
		arr[b]++
		m[a*100+b]++
		m[b*100+a]++
	}
	res := 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			value := arr[i] + arr[j] - m[i*100+j]
			if value > res {
				res = value
			}
		}
	}
	return res
}

1616.分割两个字符串得到回文串(2)¶

题目

给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。
由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，
同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。
请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。
比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
请注意， x + y 表示连接字符串 x 和 y 。
示例 1：输入：a = "x", b = "y" 输出：true
解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
那么 aprefix + bsuffix = "" + "y" = "y" 是回文串。
示例 2：输入：a = "ulacfd", b = "jizalu" 输出：true
解释：在下标为 3 处分割：
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
那么 aprefix + bsuffix = "ula" + "alu" = "ulaalu" 是回文串。
提示：1 <= a.length, b.length <= 105
    a.length == b.length
    a 和 b 都只包含小写英文字母

解题思路

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

func checkPalindromeFormation(a string, b string) bool {
	if judge(a, b) == true || judge(b, a) == true {
		return true
	}
	return false
}

// 判断prefixA+suffixB是否是回文
func judge(a, b string) bool {
	left, right := 0, len(a)-1
	for left < right {
		if a[left] == b[right] {
			left++
			right--
		} else {
			break
		}
	}
	var i, j int
	// 2种判断
	// A1+A2+A3
	// B1+B2+B3
	// 1.reverse(A1)=B3，判断B2是否回文
	i, j = left, right
	for i < j {
		if b[i] == b[j] {
			i++
			j--
		} else {
			break
		}
	}
	if i >= j {
		return true
	}
	// 2.reverse(A1)=B3，判断A2是否回文
	i, j = left, right
	for i < j {
		if a[i] == a[j] {
			i++
			j--
		} else {
			break
		}
	}
	if i >= j {
		return true
	}
	return false
}

# 2
func checkPalindromeFormation(a string, b string) bool {
	start := len(a)/2 - 1 // 中间靠左坐标
	c := check(a, a, start)
	if check(a, b, c) == -1 || check(b, a, c) == -1 {
		return true
	}
	c = check(b, b, start)
	if check(a, b, c) == -1 || check(b, a, c) == -1 {
		return true
	}
	return false
}

// 从start往左边走，从n-1-start往右边走
func check(a, b string, start int) int {
	left := start
	right := len(a) - 1 - start
	for left >= 0 {
		if a[left] != b[right] {
			break
		}
		left--
		right++
	}
	return left
}

1620.网络信号最好的坐标(1)¶

题目

给你一个数组 towers和一个整数 radius，数组中包含一些网络信号塔，
其中towers[i] = [xi, yi, qi]表示第i个网络信号塔的坐标是(xi, yi)且信号强度参数为qi。
所有坐标都是在 X-Y 坐标系内的整数坐标。两个坐标之间的距离用 欧几里得距离计算。
整数radius表示一个塔 能到达的 最远距离。
如果一个坐标跟塔的距离在 radius以内，那么该塔的信号可以到达该坐标。
在这个范围以外信号会很微弱，所以 radius以外的距离该塔是 不能到达的。
如果第 i个塔能到达 (x, y)，那么该塔在此处的信号为⌊qi / (1 + d)⌋，其中d是塔跟此坐标的距离。
一个坐标的 网络信号是所有 能到达该坐标的塔的信号强度之和。
请你返回 网络信号最大的整数坐标点。如果有多个坐标网络信号一样大，请你返回字典序最小的一个坐标。
注意：坐标(x1, y1)字典序比另一个坐标(x2, y2)小：要么x1 < x2，要么x1 == x2 且y1 < y2。
⌊val⌋表示小于等于val的最大整数（向下取整函数）。
示例 1：输入：towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2 输出：[2,1]
解释：坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。
示例 2：输入：towers = [[23,11,21]], radius = 9 输出：[23,11]
示例 3：输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2 输出：[1,2]
示例 4：输入：towers = [[2,1,9],[0,1,9]], radius = 2 输出：[0,1]
解释：坐标 (0, 1) 和坐标 (2, 1) 都是强度最大的位置，但是 (0, 1) 字典序更小。
提示：1 <= towers.length <= 50
towers[i].length == 3
0 <= xi, yi, qi <= 50
1 <= radius <= 50

解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n)	O(1)

func bestCoordinate(towers [][]int, radius int) []int {
	res := []int{0, 0}
	maxValue := 0
	for i := 0; i <= 50; i++ {
		for j := 0; j <= 50; j++ {
			sum := 0
			for k := 0; k < len(towers); k++ {
				a, b, c := towers[k][0], towers[k][1], towers[k][2]
				d := (a-i)*(a-i) + (b-j)*(b-j)
				if d <= radius*radius {
					value := float64(c) / (1 + math.Sqrt(float64(d)))
					sum = sum + int(math.Floor(value))
				}
			}
			if sum > maxValue {
				maxValue = sum
				res = []int{i, j}
			}
		}
	}
	return res
}

1621.大小为K的不重叠线段的数目(2)¶

题目

给你一维空间的n个点，其中第i个点（编号从0 到n-1）位于x = i处，
请你找到恰好k个不重叠线段且每个线段至少覆盖两个点的方案数。
线段的两个端点必须都是整数坐标。
这k个线段不需要全部覆盖全部n个点，且它们的端点可以重合。
请你返回 k个不重叠线段的方案数。由于答案可能很大，请将结果对109 + 7取余 后返回。
示例 1：输入：n = 4, k = 2 输出：5
解释：如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，
{(1,2),(2,3)}，{(0,1),(1,2)} 。
示例 2：输入：n = 3, k = 1 输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。
示例 3：输入：n = 30, k = 7 输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。
示例 4：输入：n = 5, k = 3 输出：7
示例 5：输入：n = 3, k = 2 输出：1
提示：2 <= n <= 1000
1 <= k <= n-1

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n^2)
02	数学-组合	O(n)	O(1)

var mod = 1000000007

func numberOfSets(n int, k int) int {
	dp := make([][][2]int, n)
	// dp[i][j][0] =>0到i的点，构造成j条线段的方案数, 第j条线段的右端点没有使用i
	// dp[i][j][1] =>0到i的点，构造成j条线段的方案数, 第j条线段的右端点使用i
	for i := 0; i < n; i++ {
		dp[i] = make([][2]int, n)
	}
	dp[0][0][0] = 1
	for i := 1; i < n; i++ {
		for j := 0; j <= k; j++ {
			dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % mod // 没有使用i
			dp[i][j][1] = dp[i-1][j][1]                         // 使用i：扩展右侧
			if j > 0 {
				dp[i][j][1] = (dp[i][j][1] + dp[i-1][j-1][0] + dp[i-1][j-1][1]) % mod // 使用i：新开一个
			}
		}
	}
	return (dp[n-1][k][0] + dp[n-1][k][1]) % mod
}

# 2

# 2
var mod = 1000000007

func numberOfSets(n int, k int) int {
	// 共享k-1个点+n个点 => n+k-1个点
	// 共 n+k−1 个数中选择 2k 个
	return C(n+k-1, 2*k)
}

func C(n, m int) int {
	a := multiMod(n, n-m+1)
	b := multiMod(m, 1)
	return a * powMod(b, mod-2) % mod
}

func multiMod(n, m int) int {
	res := 1
	for i := m; i <= n; i++ {
		res = (res * i) % mod
	}
	return res
}

func powMod(a, b int) int {
	res := 1
	for b > 0 {
		if b%2 == 1 {
			res = (res * a) % mod
		}
		a = a * a % mod
		b = b / 2
	}
	return res
}

1625.执行操作后字典序最小的字符串(2)¶

题目

给你一个字符串 s 以及两个整数 a 和 b 。其中，字符串 s 的长度为偶数，且仅由数字 0 到 9 组成。
你可以在 s 上按任意顺序多次执行下面两个操作之一：
累加：将 a 加到 s 中所有下标为奇数的元素上（下标从 0 开始）。数字一旦超过 9 就会变成 0，如此循环往复。
例如，s = "3456" 且 a = 5，则执行此操作后 s 变成 "3951"。
轮转：将 s 向右轮转 b 位。例如，s = "3456" 且 b = 1，则执行此操作后 s 变成 "6345"。
请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。
如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：
在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。
例如，"0158” 字典序比 "0190" 小，因为不同的第一个位置是在第三个字符，显然 '5' 出现在 '9' 之前。
示例 1：输入：s = "5525", a = 9, b = 2 输出："2050"
解释：执行操作如下：
初态："5525"
轮转："2555"
累加："2454"
累加："2353"
轮转："5323"
累加："5222"
累加："5121"
轮转："2151"
累加："2050"
无法获得字典序小于 "2050" 的字符串。
示例 2：输入：s = "74", a = 5, b = 1 输出："24"
解释：执行操作如下：
初态："74"
轮转："47"
累加："42"
轮转："24"
无法获得字典序小于 "24" 的字符串。
示例 3：输入：s = "0011", a = 4, b = 2 输出："0011"
解释：无法获得字典序小于 "0011" 的字符串。
示例 4：输入：s = "43987654", a = 7, b = 3 输出："00553311"
提示：2 <= s.length <= 100
s.length 是偶数
s 仅由数字 0 到 9 组成
1 <= a <= 9
1 <= b <= s.length - 1

解题思路

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

var m map[string]bool
var res string

func findLexSmallestString(s string, a int, b int) string {
	res = s
	m = make(map[string]bool)
	dfs(s, a, b)
	return res
}

func dfs(s string, a, b int) {
	if m[s] == true {
		return
	}
	m[s] = true
	if s < res {
		res = s
	}
	dfs(add(s, a), a, b)
	dfs(s[b:]+s[:b], a, b)
}

func add(s string, a int) string {
	res := []byte(s)
	for i := 1; i < len(s); i = i + 2 {
		res[i] = byte('0' + (int(s[i]-'0')+a)%10)
	}
	return string(res)
}

# 2
func findLexSmallestString(s string, a int, b int) string {
	res := s
	m := make(map[string]bool)
	queue := make([]string, 0)
	queue = append(queue, s)
	for len(queue) > 0 {
		str := queue[0]
		queue = queue[1:]
		if m[str] == true {
			continue
		}
		m[str] = true
		if str < res {
			res = str
		}
		queue = append(queue, str[b:]+str[:b])
		queue = append(queue, add(str, a))
	}
	return res
}

func add(s string, a int) string {
	res := []byte(s)
	for i := 1; i < len(s); i = i + 2 {
		res[i] = byte('0' + (int(s[i]-'0')+a)%10)
	}
	return string(res)
}

1626.无矛盾的最佳球队(1)¶

题目

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。
球队的得分是球队中所有球员的分数 总和 。
然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。
如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。
请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
示例 1：输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5] 输出：34
解释：你可以选中所有球员。
示例 2：输入：scores = [4,5,6,5], ages = [2,1,2,1] 输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。
示例 3：输入：scores = [1,2,3,5], ages = [8,9,10,1] 输出：6
解释：最佳的选择是前 3 名球员。
提示： 1 <= scores.length, ages.length <= 1000
    scores.length == ages.length
    1 <= scores[i] <= 10^6
    1 <= ages[i] <= 1000

解题思路

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

func bestTeamScore(scores []int, ages []int) int {
	arr := make([][2]int, 0)
	for i := 0; i < len(ages); i++ {
		arr = append(arr, [2]int{ages[i], scores[i]})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i][0] == arr[j][0] {
			return arr[i][1] < arr[j][1]
		}
		return arr[i][0] < arr[j][0]
	})
	dp := make([]int, len(arr))
	res := 0
	for i := 0; i < len(arr); i++ {
		dp[i] = arr[i][1]
		for j := 0; j < i; j++ {
			if arr[j][1] <= arr[i][1] {
				dp[i] = max(dp[i], dp[j]+arr[i][1])
			}
		}
		res = max(res, dp[i])
	}
	return res
}

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

1630.等差子数组(1)¶

题目

如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。
更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。
例如，下面这些都是 等差数列 ：
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
下面的数列 不是等差数列 ：
1, 1, 2, 5, 7
给你一个由 n 个整数组成的数组 nums，和两个由 m 个整数组成的数组 l 和 r，后两个数组表示 m 组范围查询，
其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。
返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , 
nums[r[i]] 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。
示例 1：输入：nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5] 输出：[true,false,true]
解释：第 0 个查询，对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。
第 1 个查询，对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。
第 2 个查询，对应子数组 [5,9,3,7] 。可以重新排列为等差数列 [3,5,7,9] 。
示例 2：输入：nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], 
l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
输出：[false,true,false,false,true,true]
提示：n == nums.length
    m == l.length
    m == r.length
    2 <= n <= 500
    1 <= m <= 500
    0 <= l[i] < r[i] < n
    -105 <= nums[i] <= 105

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(n^2*log(n))	O(n)

func checkArithmeticSubarrays(nums []int, l []int, r []int) []bool {
	res := make([]bool, 0)
	for i := 0; i < len(l); i++ {
		flag := true
		arr := make([]int, 0)
		arr = append(arr, nums[l[i]:r[i]+1]...)
		sort.Ints(arr)
		for j := 2; j < len(arr); j++ {
			if arr[j]-arr[j-1] != arr[1]-arr[0] {
				flag = false
				break
			}
		}
		res = append(res, flag)
	}
	return res
}

1631.最小体力消耗路径(4)¶

题目

你准备参加一场远足活动。给你一个二维rows x columns的地图heights，
其中heights[row][col]表示格子(row, col)的高度。
一开始你在最左上角的格子(0, 0)，且你希望去最右下角的格子(rows-1, columns-1)（注意下标从 0 开始编号）。
你每次可以往 上，下，左，右四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值是路径上相邻格子之间 高度差绝对值的 最大值决定的。
请你返回从左上角走到右下角的最小体力消耗值。
示例 1：输入：heights = [[1,2,2],[3,8,2],[5,3,5]] 输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
示例 2：输入：heights = [[1,2,3],[3,8,4],[5,3,5]] 输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
示例 3：输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] 输出：0
解释：上图所示路径不需要消耗任何体力。
提示：rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106

解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找+广度优先搜索	O(n^2log(n))	O(n^2)
02	并查集	O(n^2log(n))	O(n^2)
03	Dijkstra	O(n^2log(n))	O(n^2)
04	二分查找+广度优先搜索+内置函数	O(n^2log(n))	O(n^2)

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

func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	left, right := 0, 1000000
	res := 0
	for left <= right {
		mid := left + (right-left)/2 // 二分枚举最大值
		queue := make([][2]int, 0)
		queue = append(queue, [2]int{0, 0})
		visited := make([][]bool, n)
		for i := 0; i < n; i++ {
			visited[i] = make([]bool, m)
		}
		for len(queue) > 0 {
			a, b := queue[0][0], queue[0][1]
			queue = queue[1:]
			for i := 0; i < 4; i++ {
				x, y := a+dx[i], b+dy[i]
				if 0 <= x && x < n && 0 <= y && y < m &&
					visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= mid {
					queue = append(queue, [2]int{x, y})
					visited[x][y] = true
				}
			}
		}
		if visited[n-1][m-1] == true { // 缩小范围
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

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

# 2
func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	arr := make([][3]int, 0) // 相邻格子可以连一条边，高度差绝对值最为边的权值
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			index := i*m + j // 转化为一维坐标
			if i > 0 {
				value := abs(heights[i][j] - heights[i-1][j])      // 上到下
				arr = append(arr, [3]int{index - m, index, value}) // 之前坐标，当前坐标，绝对值
			}
			if j > 0 {
				value := abs(heights[i][j] - heights[i][j-1])      // 左到右
				arr = append(arr, [3]int{index - 1, index, value}) // 之前坐标，当前坐标，绝对值
			}
		}
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][2] < arr[j][2]
	})
	fa = Init(n * m)
	for i := 0; i < len(arr); i++ { // 从小到大枚举高度差绝对值
		a, b, c := arr[i][0], arr[i][1], arr[i][2]
		union(a, b)
		if query(0, n*m-1) == true {
			return c
		}
	}
	return 0
}

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

var fa []int

// 初始化
func Init(n int) []int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = i
	}
	return arr
}

// 查询
func find(x int) int {
	if fa[x] != x {
		fa[x] = find(fa[x])
	}
	return fa[x]
}

// 合并
func union(i, j int) {
	fa[find(i)] = find(j)
}

func query(i, j int) bool {
	return find(i) == find(j)
}

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

func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	arr := make([][]int, n) //  高度差绝对值的最大值
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
		for j := 0; j < m; j++ {
			arr[i][j] = math.MaxInt32 // 初始化为最大值
		}
	}
	arr[0][0] = 0
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	heap.Push(&intHeap, [3]int{0, 0, 0})
	for {
		node := heap.Pop(&intHeap).([3]int)
		a, b, c := node[0], node[1], node[2]
		if a == n-1 && b == m-1 { // 返回结果
			return c
		}
		if arr[a][b] < c { // 大于 高度差绝对值的最大值，跳过
			continue
		}
		for i := 0; i < 4; i++ {
			x, y := a+dx[i], b+dy[i]
			if 0 <= x && x < n && 0 <= y && y < m {
				diff := max(c, abs(heights[x][y]-heights[a][b])) // 更新：去 高度差绝对值的最大值 的较大值
				if diff < arr[x][y] {                            // 更新：加入堆，点会重复，通过更新arr[x][y]来过滤
					arr[x][y] = diff
					heap.Push(&intHeap, [3]int{x, y, diff})
				}
			}
		}
	}
	return 0
}

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

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

type IntHeap [][3]int

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

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

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.([3]int))
}

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

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

func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	return sort.Search(1000000, func(target int) bool {
		queue := make([][2]int, 0)
		queue = append(queue, [2]int{0, 0})
		visited := make([][]bool, n)
		for i := 0; i < n; i++ {
			visited[i] = make([]bool, m)
		}
		for len(queue) > 0 {
			a, b := queue[0][0], queue[0][1]
			queue = queue[1:]
			if a == n-1 && b == m-1 {
				return true
			}
			for i := 0; i < 4; i++ {
				x, y := a+dx[i], b+dy[i]
				if 0 <= x && x < n && 0 <= y && y < m &&
					visited[x][y] == false && abs(heights[a][b]-heights[x][y]) <= target {
					queue = append(queue, [2]int{x, y})
					visited[x][y] = true
				}
			}
		}
		return false
	})
	return 0
}

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

1637.两点之间不包含任何点的最宽垂直面积(1)¶

题目

给你 n 个二维平面上的点 points ，其中 points[i] = [xi, yi] ，
请你返回两点之间内部不包含任何点的 最宽垂直面积 的宽度。
垂直面积 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。
最宽垂直面积 为宽度最大的一个垂直面积。
请注意，垂直区域 边上 的点 不在 区域内。
示例 1：输入：points = [[8,7],[9,9],[7,4],[9,7]] 输出：1
解释：红色区域和蓝色区域都是最优区域。
示例 2：输入：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]] 输出：3
提示： n == points.length
    2 <= n <= 105
    points[i].length == 2
    0 <= xi, yi <= 109

解题思路

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

func maxWidthOfVerticalArea(points [][]int) int {
	sort.Slice(points, func(i, j int) bool {
		return points[i][0] < points[j][0]
	})
	res := 0
	for i := 1; i < len(points); i++ {
		res = max(res, points[i][0]-points[i-1][0])
	}
	return res
}

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

1638.统计只差一个字符的子串数目(3)¶

题目

给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，
是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。
比方说， "computer" 和 "computation" 加粗部分只有一个字符不同： 
'e'/'a' ，所以这一对子字符串会给答案加 1 。
请你返回满足上述条件的不同子字符串对数目。
一个 子字符串 是一个字符串中连续的字符。
示例 1：输入：s = "aba", t = "baba" 输出：6
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 2：输入：s = "ab", t = "bb" 输出：3
解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。
示例 3：输入：s = "a", t = "a" 输出：0
示例 4：输入：s = "abe", t = "bbc" 输出：10
提示：1 <= s.length, t.length <= 100
    s 和 t 都只包含小写英文字母。

解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^3)	O(1)
02	暴力法	O(n^4)	O(n)
03	动态规划	O(n^2)	O(n^2)

func countSubstrings(s string, t string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		for j := 0; j < len(t); j++ {
			diff := 0
			for k := 0; i+k < len(s) && j+k < len(t); k++ {
				if s[i+k] != t[j+k] {
					diff++
				}
				if diff > 1 {
					break
				}
				if diff == 1 {
					res++
				}
			}
		}
	}
	return res
}

# 2
func countSubstrings(s string, t string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		for j := i + 1; j <= len(s); j++ {
			length := j - i
			newStr := s[i:j]
			for k := 0; k <= len(t)-length; k++ {
				b := t[k : k+length]
				if compare(newStr, b) {
					res++
				}
			}
		}
	}
	return res
}

func compare(a, b string) bool {
	count := 0
	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			count++
		}
		if count >= 2 {
			return false
		}
	}
	if count == 0 {
		return false
	}
	return true
}

# 3
func countSubstrings(s, t string) int {
	res := 0
	m, n := len(s), len(t)
	// dp以s[i]和t[j]结尾的所有子串对中，满足恰好只有一个字符不同的字符串对的数目
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	// 以s[i]和t[j]为结尾的子串，最多有多少个连续相同的字符
	same := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		same[i] = make([]int, n+1)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if s[i] == t[j] {
				dp[i+1][j+1] = dp[i+1][j+1] + dp[i][j]
				same[i+1][j+1] = same[i][j] + 1
			} else {
				dp[i+1][j+1] = same[i][j] + 1
			}
			res = res + dp[i+1][j+1]
		}
	}
	return res
}

1641.统计字典序元音字符串的数目(3)¶

题目

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，
s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
示例 1：输入：n = 1 输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
示例 2：输入：n = 2 输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后
示例 3：输入：n = 33 输出：66045
提示：1 <= n <= 50

解题思路

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

func countVowelStrings(n int) int {
	dp := make([][5]int, n+1)
	dp[0][0], dp[0][1], dp[0][2], dp[0][3], dp[0][4] = 1, 1, 1, 1, 1
	for i := 1; i <= n; i++ {
		for j := 0; j < 5; j++ {
			for k := 0; k <= j; k++ {
				dp[i][j] = dp[i][j] + dp[i-1][k]
			}
		}
	}
	res := 0
	for i := 0; i < 5; i++ {
		res = res + dp[n-1][i]
	}
	return res
}

# 2
func countVowelStrings(n int) int {
	dp := make([]int, 5)
	dp[0] = 1
	for i := 0; i < n; i++ {
		for j := 1; j < 5; j++ {
			dp[j] = dp[j] + dp[j-1]
		}
	}
	res := 0
	for i := 0; i < 5; i++ {
		res = res + dp[i]
	}
	return res
}

# 3
// 将n个小球放到m个盒子里，盒子可以空：C(n+m-1, m-1) m=5 => C(n+4,4)
// 在n+4中选择4个整数(4*3*2)
func countVowelStrings(n int) int {
	return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24
}

1642.可以到达的最远建筑(2)¶

题目

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
示例 1：输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：
- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。
示例 2：输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 输出：7
示例 3：输入：heights = [14,3,19,3], bricks = 17, ladders = 0 输出：3
提示：1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length

解题思路

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

func furthestBuilding(heights []int, bricks int, ladders int) int {
	if len(heights) <= 1 {
		return 0
	}
	intHeap := &IntHeap{}
	heap.Init(intHeap)
	need := 0
	for i := 1; i < len(heights); i++ {
		need = heights[i] - heights[i-1]
		if need <= 0 {
			continue
		}
		heap.Push(intHeap, need)
		if intHeap.Len() > ladders {
			need = heap.Pop(intHeap).(int)
			if need > bricks {
				return i - 1
			}
			bricks = bricks - need
		}
	}
	return len(heights) - 1
}

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 furthestBuilding(heights []int, bricks int, ladders int) int {
	left, right := 0, len(heights)
	res := 0
	for left <= right {
		mid := left + (right-left)/2
		if check(heights[0:mid], bricks, ladders) {
			left = mid + 1
			res = mid
		} else {
			right = mid - 1
		}
	}
	return res - 1
}

func check(heights []int, bricks int, ladders int) bool {
	arr := make([]int, 0)
	for i := 1; i < len(heights); i++ {
		need := heights[i] - heights[i-1]
		if need > 0 {
			arr = append(arr, need)
		}
	}
	sort.Ints(arr)
	i := 0
	for ; i < len(arr); i++ {
		if bricks-arr[i] >= 0 {
			bricks = bricks - arr[i]
			continue
		}
		if ladders > 0 {
			ladders--
			continue
		}
		break
	}
	return i == len(arr)
}

1647.字符频次唯一的最小删除次数(1)¶

题目

如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
字符串中字符的 频次 是该字符在字符串中的出现次数。
例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。
示例 1：输入：s = "aab" 输出：0
解释：s 已经是优质字符串。
示例 2：输入：s = "aaabbbcc" 输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。
示例 3：输入：s = "ceabaacb" 输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
提示：1 <= s.length <= 10^5  s 仅含小写英文字母

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+贪心	O(n)	O(1)

func minDeletions(s string) int {
	m := make(map[int]int)
	for i := 0; i < len(s); i++ {
		m[int(s[i])]++
	}
	arr := make([]int, 0)
	for _, v := range m {
		arr = append(arr, v)
	}
	sort.Ints(arr)
	M := make(map[int]bool)
	res := 0
	for i := len(arr) - 1; i >= 0; i-- {
		if M[arr[i]] == false {
			M[arr[i]] = true
			continue
		}
		j := arr[i]
		for j >= 0 {
			if M[j] == false {
				M[j] = true
				res = res + arr[i] - j
				break
			}
			j--
		}
		if j == -1 {
			res = res + arr[i]
		}
	}
	return res
}

1648.销售价值减少的颜色球(2)¶

题目

你有一些球的库存inventory，里面包含着不同颜色的球。一个顾客想要任意颜色 总数为orders的球。
这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的同色球的数目。
比方说还剩下6个黄球，那么顾客买第一个黄球的时候该黄球的价值为6。
这笔交易以后，只剩下5个黄球了，所以下一个黄球的价值为5（也就是球的价值随着顾客购买同色球是递减的）
给你整数数组inventory，其中inventory[i]表示第i种颜色球一开始的数目。
同时给你整数orders，表示顾客总共想买的球数目。你可以按照 任意顺序卖球。
请你返回卖了 orders个球以后 最大总价值之和。
由于答案可能会很大，请你返回答案对 109+ 7取余数的结果。
示例 1：输入：inventory = [2,5], orders = 4 输出：14
解释：卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。
最大总和为 2 + 5 + 4 + 3 = 14 。
示例 2：输入：inventory = [3,5], orders = 6 输出：19
解释：卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。
最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。
示例 3：输入：inventory = [2,8,4,10,6], orders = 20 输出：110
示例 4：输入：inventory = [1000000000], orders = 1000000000 输出：21
解释：卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。 
500000000500000000 对 109 + 7 取余为 21 。
提示：1 <= inventory.length <= 105
1 <= inventory[i] <= 109
1 <= orders <= min(sum(inventory[i]), 109)

解题思路

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

func maxProfit(inventory []int, orders int) int {
	inventory = append(inventory, 0) // 避免第一个数特判
	sort.Ints(inventory)
	n := len(inventory)
	res := 0
	// 每次把当前数减到前一个数
	for i := n - 1; i >= 1; i-- {
		if orders <= 0 {
			break
		}
		total := (n - i) * (inventory[i] - inventory[i-1])
		if total <= orders { // 够用
			sum := (inventory[i-1] + 1 + inventory[i]) * (inventory[i] - inventory[i-1]) / 2 * (n - i)
			res = (res + sum) % 1000000007
			orders = orders - total
		} else { // 不够用
			a, b := orders/(n-i), orders%(n-i)
			start := inventory[i] - a + 1
			sum := (start+inventory[i])*a/2*(n-i) + b*(start-1)
			res = (res + sum) % 1000000007
			orders = 0
		}
	}
	return res
}

# 2
func maxProfit(inventory []int, orders int) int {
	left, right := 0, math.MaxInt32
	target := 0
	for left <= right {
		target = left + (right-left)/2
		sum := 0
		count := 0
		for i := 0; i < len(inventory); i++ {
			if inventory[i] >= target {
				count++
				sum = sum + (inventory[i] - target)
			}
		}
		if sum > orders { // 过小
			left = target + 1
		} else if sum+count <= orders { // 过小
			right = target - 1
		} else {
			break
		}
	}
	res := 0
	temp := 0
	for i := 0; i < len(inventory); i++ {
		if inventory[i] > target {
			res = (res + getCount(target+1, inventory[i])) % 1000000007
			temp = temp + inventory[i] - target
		}
	}
	return (res + (orders-temp)*target) % 1000000007
}

func getCount(a, b int) int {
	return (a + b) * (b - a + 1) / 2
}

1653.使字符串平衡的最少删除次数(4)¶

题目

给你一个字符串s，它仅包含字符'a' 和'b'。
你可以删除s中任意数目的字符，使得s 平衡。
我们称s平衡的当不存在下标对(i,j)满足i < j 且s[i] = 'b'同时s[j]= 'a'。
请你返回使 s平衡的 最少删除次数。
示例 1：输入：s = "aababbab" 输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
示例 2：输入：s = "bbaaaaabb" 输出：2
解释：唯一的最优解是删除最前面两个字符。
提示：1 <= s.length <= 105
s[i]要么是'a' 要么是'b'。

解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+后缀和	O(n)	O(n)
02	栈	O(n)	O(n)
03	遍历	O(n)	O(1)
04	动态规划	O(n)	O(n)

func minimumDeletions(s string) int {
	n := len(s)
	dpA := make([]int, n)
	dpB := make([]int, n)
	if s[0] == 'a' {
		dpA[0] = 1
	}
	for i := 1; i < n; i++ {
		if s[i] == 'a' {
			dpA[i] = dpA[i-1] + 1
		} else {
			dpA[i] = dpA[i-1]
		}
	}
	if s[n-1] == 'b' {
		dpB[n-1] = 1
	}
	for i := n - 2; i >= 0; i-- {
		if s[i] == 'b' {
			dpB[i] = dpB[i+1] + 1
		} else {
			dpB[i] = dpB[i+1]
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		res = max(res, dpA[i]+dpB[i])
	}
	return n - res
}

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

# 2
func minimumDeletions(s string) int {
	res := 0
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		if s[i] == 'b' {
			stack = append(stack, 'b')
		} else {
			// 遇到'ba'则删掉，并次数+1
			if len(stack) > 0 {
				res++
				stack = stack[:len(stack)-1]
			}
		}
	}
	return res
}

# 3
func minimumDeletions(s string) int {
	aCount := 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'a' {
			aCount = aCount + 1
		}
	}
	res := aCount
	bCount := 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'a' {
			aCount--
		} else {
			bCount++
		}
		// 要删除：前面b的个数+后面a的个数
		res = min(res, aCount+bCount)
	}
	return res
}

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

# 4
func minimumDeletions(s string) int {
	n := len(s)
	dp := make([][2]int, n+1)
	// dp[n][0]以a结尾需要删除的次数
	// dp[n][1]以b结尾需要删除的次数
	for i := 0; i < n; i++ {
		if s[i] == 'a' {
			dp[i+1][0] = dp[i][0]
			dp[i+1][1] = dp[i][1] + 1
		} else {
			dp[i+1][0] = dp[i][0] + 1
			dp[i+1][1] = min(dp[i][0], dp[i][1])
		}
	}
	return min(dp[n][0], dp[n][1])
}

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

1654.到家的最少跳跃次数(2)¶

题目

有一只跳蚤的家在数轴上的位置x处。请你帮助它从位置0出发，到达它的家。
跳蚤跳跃的规则如下：
它可以 往前 跳恰好 a个位置（即往右跳）。
它可以 往后跳恰好 b个位置（即往左跳）。
它不能 连续 往后跳 2 次。
它不能跳到任何forbidden数组中的位置。
跳蚤可以往前跳 超过它的家的位置，但是它 不能跳到负整数的位置。
给你一个整数数组forbidden，其中forbidden[i]是跳蚤不能跳到的位置，同时给你整数a，b和x，
请你返回跳蚤到家的最少跳跃次数。
如果没有恰好到达 x的可行方案，请你返回 -1 。
示例 1：输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9 输出：3
解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
示例 2：输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11 输出：-1
示例 3：输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7 输出：2
解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
提示：1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden中所有位置互不相同。
位置x不在 forbidden中。

解题思路

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

func minimumJumps(forbidden []int, a int, b int, x int) int {
	m := make([]bool, 6001)
	for i := 0; i < len(forbidden); i++ {
		m[forbidden[i]] = true
	}
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	res := -1
	for len(queue) > 0 {
		length := len(queue)
		res++
		for i := 0; i < length; i++ {
			index, dir := queue[i][0], queue[i][1]
			if index == x {
				return res
			}
			if dir == 0 && index-b > 0 && m[index-b] == false { // 向后跳-b
				m[index-b] = true
				queue = append(queue, [2]int{index - b, 1})
			}
			if index+a < len(m) && m[index+a] == false { // 向前跳+a
				m[index+a] = true
				queue = append(queue, [2]int{index + a, 0})
			}
		}
		queue = queue[length:]
	}
	return -1
}

# 2
var m []bool

func minimumJumps(forbidden []int, a int, b int, x int) int {
	m = make([]bool, 6001)
	for i := 0; i < len(forbidden); i++ {
		m[forbidden[i]] = true
	}
	return dfs(0, 0, a, b, x)
}

func dfs(index int, dir int, a int, b int, x int) int {
	if index == x {
		return 0
	}
	res := -1
	if index+a < len(m) && m[index+a] == false { // 向前跳+a
		m[index+a] = true
		res = dfs(index+a, 0, a, b, x)
		if res != -1 {
			return res + 1
		}
	}
	if dir == 0 && index-b > 0 && m[index-b] == false { // 向后跳-b
		res = dfs(index-b, 1, a, b, x)
		if res != -1 {
			return res + 1
		}
	}
	return res
}

1657.确定两个字符串是否接近(1)¶

题目

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
操作 1：交换任意两个 现有 字符。
例如，abcde -> aecdb
操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
示例 1：输入：word1 = "abc", word2 = "bca" 输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"
示例 2：输入：word1 = "a", word2 = "aa" 输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
示例 3：输入：word1 = "cabbba", word2 = "abbccc" 输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"
示例 4：输入：word1 = "cabbba", word2 = "aabbss" 输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
提示：1 <= word1.length, word2.length <= 105
word1 和 word2 仅包含小写英文字母

解题思路

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

func closeStrings(word1 string, word2 string) bool {
	if len(word1) != len(word2) {
		return false
	}
	arr1 := make([]int, 26)
	arr2 := make([]int, 26)
	m1 := make(map[uint8]bool)
	m2 := make(map[uint8]bool)
	for i := 0; i < len(word1); i++ {
		arr1[word1[i]-'a']++
		arr2[word2[i]-'a']++
		m1[word1[i]-'a'] = true
		m2[word2[i]-'a'] = true
	}
	for key := range m1 {
		if m2[key] != true {
			return false
		}
	}
	sort.Ints(arr1)
	sort.Ints(arr2)
	for i := 0; i < 26; i++ {
		if arr1[i] != arr2[i] {
			return false
		}
	}
	return true
}

1658.将x减到0的最小操作数(2)¶

题目

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，
然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x恰好 减到0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：输入：nums = [1,1,4,2,3], x = 5 输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：输入：nums = [5,6,7,8,9], x = 4 输出：-1
示例 3：输入：nums = [3,2,20,1,1,3], x = 10 输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109

解题思路

No.	思路	时间复杂度	空间复杂度
01	前后缀和	O(n)	O(n)
02	滑动窗口	O(n)	O(1)

func minOperations(nums []int, x int) int {
	n := len(nums)
	res := n + 1
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + nums[i]
	}
	if sum < x {
		return -1
	}
	if sum == x {
		return n
	}
	left := make([]int, n)
	right := make([]int, n)
	mLeft := make(map[int]int)
	mRight := make(map[int]int)
	left[0] = nums[0]
	mLeft[nums[0]] = 0
	right[n-1] = nums[n-1]
	mRight[nums[n-1]] = n - 1
	if left[0] == x || right[n-1] == x {
		return 1
	}
	for i := 1; i < n; i++ {
		left[i] = left[i-1] + nums[i]
		mLeft[left[i]] = i
		if left[i] == x {
			res = min(res, i+1)
		}
	}
	for i := n - 2; i >= 0; i-- {
		right[i] = right[i+1] + nums[i]
		mRight[right[i]] = i
		if right[i] == x {
			res = min(res, n-i)
		}
	}
	for i := 1; i < n; i++ {
		left := left[i]
		if index, ok := mRight[x-left]; ok && i < index {
			target := n - (index - i - 1)
			res = min(res, target)
		}
	}
	if res == n+1 {
		return -1
	}
	return res
}

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

# 2
func minOperations(nums []int, x int) int {
	n := len(nums)
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + nums[i]
	}
	target := sum - x
	left := 0
	right := 0
	res := -1
	cur := 0
	// 和为sum-x的最长连续子数组
	for left < n {
		if right < n {
			cur = cur + nums[right]
			right++
		}
		for cur > target && left < n {
			cur = cur - nums[left]
			left++
		}
		if cur == target {
			res = max(res, right-left)
		}
		if right == n {
			left++
		}
	}
	if res == -1 {
		return -1
	}
	return n - res
}

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

1663.具有给定数值的最小字符串(2)¶

题目

小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，
c 的数值为 3 ，以此类推。
字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。
例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：
x 是 y 的一个前缀；
如果 i 是x[i] != y[i] 的第一个位置，且 x[i]在字母表中的位置比y[i]靠前。
示例 1：输入：n = 3, k = 27 输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。
示例 2：输入：n = 5, k = 73 输出："aaszz"
提示：1 <= n <= 105
n <= k <= 26 * n

解题思路

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

func getSmallestString(n int, k int) string {
	res := ""
	k = k - n
	a := k / 25
	b := k % 25
	right := a
	var left, middle int
	if b == 0 {
		left = n - right
		middle = 0
	} else {
		left = n - right - 1
		middle = b
	}
	res = res + strings.Repeat("a", left)
	if middle > 0 {
		res = res + string('a'+middle)
	}
	res = res + strings.Repeat("z", right)
	return res
}

# 2
func getSmallestString(n int, k int) string {
	arr := make([]byte, n)
	k = k - n
	for i := n - 1; i >= 0; i-- {
		if k > 25 {
			arr[i] = 'z'
			k = k - 25
		} else {
			arr[i] = byte('a' + k)
			k = 0
		}
	}
	return string(arr)
}

1664.生成平衡数组的方案数(2)¶

题目

给你一个整数数组nums。你需要选择 恰好一个下标（下标从 0开始）并删除对应的元素。
请注意剩下元素的下标可能会因为删除操作而发生改变。
比方说，如果nums = [6,1,7,4,1]，那么：
选择删除下标 1 ，剩下的数组为nums = [6,7,4,1]。
选择删除下标2，剩下的数组为nums = [6,1,4,1]。
选择删除下标4，剩下的数组为nums = [6,1,7,4]。
如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。
请你返回删除操作后，剩下的数组nums是平衡数组 的方案数。
示例 1：输入：nums = [2,1,6,4] 输出：1
解释：删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。
示例 2：输入：nums = [1,1,1] 输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。
示例 3：输入：nums = [1,2,3] 输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 104

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	前缀和	O(n)	O(n)

func waysToMakeFair(nums []int) int {
	res := 0
	a := 0
	b := 0
	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			a = a + nums[i]
		} else {
			b = b + nums[i]
		}
	}
	x, y := 0, 0
	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			a = a - nums[i]
		} else {
			b = b - nums[i]
		}
		even := x + b
		odd := y + a
		if even == odd {
			res++
		}
		if i%2 == 0 {
			x = x + nums[i]
		} else {
			y = y + nums[i]
		}
	}
	return res
}

# 2
func waysToMakeFair(nums []int) int {
	n := len(nums)
	dp := make([]int, n+1)
	for i := 0; i < n; i++ {
		if i%2 == 0 {
			dp[i+1] = dp[i] + nums[i]
		} else {
			dp[i+1] = dp[i] - nums[i]
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		// dp[i]表示索引i左边部分奇偶元素差值，
		// dp[n] - dp[i+1]表示索引i右边部分奇偶元素差值
		if dp[i] == dp[n]-dp[i+1] {
			res++
		}
	}
	return res
}

1669.合并两个链表(2)¶

题目

给你两个链表list1 和list2，它们包含的元素分别为n 个和m 个。
请你将list1中第a个节点到第b个节点删除，并将list2接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
请你返回结果链表的头指针。
示例 1：输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2：输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。
提示：3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104

解题思路

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

func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
	res := &ListNode{}
	temp := res
	for i := 0; i < a; i++{
		temp.Next = list1
		temp = temp.Next
		list1 = list1.Next
	}
	for list2 != nil{
		temp.Next = list2
		temp = temp.Next
		list2 = list2.Next
	}
	for i := a; i <= b; i++{
		list1 = list1.Next
	}
	for list1 != nil{
		temp.Next = list1
		temp = temp.Next
		list1 = list1.Next
	}
	return  res.Next
}

# 2
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
	cur := list1
	for i := 0; i < a-1; i++ {
		cur = cur.Next
	}
	temp := cur.Next
	for i := 0; i < (b - a + 1); i++ {
		temp = temp.Next
	}
	cur.Next = list2
	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = temp
	return list1
}

1670.设计前中后队列(1)¶

题目

请你设计一个队列，支持在前，中，后三个位置的 push和 pop操作。
请你完成FrontMiddleBack类：
FrontMiddleBack()初始化队列。
void pushFront(int val) 将val添加到队列的 最前面。
void pushMiddle(int val) 将val添加到队列的 正中间。
void pushBack(int val)将val添加到队里的 最后面。
int popFront()将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
int popMiddle() 将 正中间的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
请注意当有两个中间位置的时候，选择靠前面的位置进行操作。比方说：
将 6添加到[1, 2, 3, 4, 5]的中间位置，结果数组为[1, 2, 6, 3, 4, 5]。
从[1, 2, 3, 4, 5, 6]的中间位置弹出元素，返回3，数组变为[1, 2, 4, 5, 6]。
示例 1：输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", 
"pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：[null, null, null, null, null, 1, 3, 4, 2, -1]
解释：FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] （队列为空）
提示：1 <= val <= 109
最多调用1000次pushFront，pushMiddle，pushBack，popFront，popMiddle和popBack 。

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组	O(n^2)	O(n)

type FrontMiddleBackQueue struct {
	arr []int
}

func Constructor() FrontMiddleBackQueue {
	return FrontMiddleBackQueue{}
}

func (this *FrontMiddleBackQueue) PushFront(val int) {
	this.arr = append([]int{val}, this.arr...)
}

func (this *FrontMiddleBackQueue) PushMiddle(val int) {
	mid := len(this.arr) / 2
	this.arr = append(this.arr[:mid], append([]int{val}, this.arr[mid:]...)...)
}

func (this *FrontMiddleBackQueue) PushBack(val int) {
	this.arr = append(this.arr, val)
}

func (this *FrontMiddleBackQueue) PopFront() int {
	var res int
	if len(this.arr) == 0 {
		return -1
	}
	res = this.arr[0]
	this.arr = this.arr[1:]
	return res
}

func (this *FrontMiddleBackQueue) PopMiddle() int {
	var res, mid int
	if len(this.arr) == 0 {
		return -1
	}
	if len(this.arr)%2 == 1 {
		mid = len(this.arr) / 2
	} else {
		mid = len(this.arr)/2 - 1
	}
	res = this.arr[mid]
	this.arr = append(this.arr[:mid], this.arr[mid+1:]...)
	return res
}

func (this *FrontMiddleBackQueue) PopBack() int {
	var res int
	if len(this.arr) == 0 {
		return -1
	}
	res = this.arr[len(this.arr)-1]
	this.arr = this.arr[:len(this.arr)-1]
	return res
}

1673.找出最具竞争力的子序列(1)¶

题目

给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。
数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
在子序列a 和子序列b 第一个不相同的位置上，如果a中的数字小于 b 中对应的数字，
那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 
例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上，4 小于 5 。
示例 1：输入：nums = [3,5,2,6], k = 2 输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，
[2,6] 最具竞争力。
示例 2：输入：nums = [2,4,3,3,5,4,9,6], k = 4 输出：[2,3,3,4]
提示：1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length

解题思路

No.	思路	时间复杂度	空间复杂度
01	单调栈	O(n)	O(n)

func mostCompetitive(nums []int, k int) []int {
	stack := make([]int, 0)
	k = len(nums) - k
	for i := 0; i < len(nums); i++ {
		value := nums[i]
		// 栈顶元素打大于后面的元素，摘除栈顶元素（因为前面的更大，需要删除了才能变的最小）
		for len(stack) > 0 && stack[len(stack)-1] > value && k > 0 {
			stack = stack[:len(stack)-1]
			k--
		}
		stack = append(stack, value)
	}
	stack = stack[:len(stack)-k]
	return stack
}

1674.使数组互补的最少操作次数(1)¶

题目

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。
每一次操作，你可以将 nums 中的任何整数替换为1到limit 之间的另一个整数。
如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i]都等于同一个数，
则数组 nums 是 互补的 。
例如，数组 [1,2,3,4] 是互补的，因为对于所有下标i ，nums[i] + nums[n - 1 - i] = 5 。
返回使数组 互补 的 最少操作次数。
示例 1：输入：nums = [1,2,4,3], limit = 4 输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。
示例 2：输入：nums = [1,2,2,1], limit = 2 输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。
示例 3：输入：nums = [1,2,1,2], limit = 2 输出：0
解释：nums 已经是互补的。
提示：n == nums.length
2 <= n<=105
1 <= nums[i]<= limit <=105
n 是偶数。

解题思路

No.	思路	时间复杂度	空间复杂度
01	差分数组	O(n)	O(n)

func minMoves(nums []int, limit int) int {
	n := len(nums)
	arr := make([]int, 2*limit+2)
	for i := 0; i < n/2; i++ {
		a, b := nums[i], nums[n-1-i]
		// 1、首先[2,2*limit]都加2=>操作2次
		arr[2] = arr[2] + 2
		arr[2*limit+1] = arr[2*limit+1] - 2
		// 2、将[1+min(a,b),limit+max(a,b)] 减1=>操作1次
		arr[1+min(a, b)] = arr[1+min(a, b)] - 1
		arr[limit+max(a, b)+1] = arr[limit+max(a, b)+1] + 1
		// 3、将[a+b]减1，目标值=>操作0次
		arr[a+b] = arr[a+b] - 1
		arr[a+b+1] = arr[a+b+1] + 1
	}
	res := n
	sum := 0
	for i := 2; i <= 2*limit; i++ {
		sum = sum + arr[i]
		if res > sum {
			res = sum
		}
	}
	return res
}

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

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

1679.K和数对的最大数目(3)¶

题目

给你一个整数数组 nums 和一个整数 k 。
每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
返回你可以对数组执行的最大操作数。
示例 1：输入：nums = [1,2,3,4], k = 5 输出：2
解释：开始时 nums = [1,2,3,4]：
- 移出 1 和 4 ，之后 nums = [2,3]
- 移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。
示例 2：输入：nums = [3,1,3,4,3], k = 6 输出：1
解释：开始时 nums = [3,1,3,4,3]：
- 移出前两个 3 ，之后nums = [1,4,3]
不再有和为 6 的数对，因此最多执行 1 次操作。
提示：1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9

解题思路

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

func maxOperations(nums []int, k int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		if m[k-nums[i]] > 0 {
			res++
			m[k-nums[i]]--
		} else {
			m[nums[i]]++
		}
	}
	return res
}

# 2
func maxOperations(nums []int, k int) int {
	sort.Ints(nums)
	res := 0
	left := 0
	right := len(nums) - 1
	for left < right {
		sum := nums[left] + nums[right]
		if sum == k {
			res++
			left++
			right--
		} else if sum > k {
			right--
		} else {
			left++
		}
	}
	return res
}

# 3
func maxOperations(nums []int, k int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	for key := range m {
		res = res + min(m[key], m[k-key])
	}
	return res / 2
}

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

1680.连接连续二进制数字(2)¶

题目

给你一个整数n，请你将1到 n的二进制表示连接起来，
并返回连接结果对应的 十进制数字对 109+ 7取余的结果。
示例 1：输入：n = 1 输出：1
解释：二进制的 "1" 对应着十进制的 1 。
示例 2：输入：n = 3 输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。
示例 3：输入：n = 12 输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 10^9 + 7 取余后，结果为 505379714 。
提示：1 <= n <= 10^5

解题思路

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

package main

import "math/bits"

func main() {

}

func concatenatedBinary(n int) int {
	res := 0
	for i := 1; i <= n; i++ {
		length := bits.Len(uint(i))
		res = (res<<length + i) % 1000000007
	}
	return res
}

# 2
func concatenatedBinary(n int) int {
	res := 0
	length := 0
	for i := 1; i <= n; i++ {
		if i&(i-1) == 0 {
			length++
		}
		res = (res<<length + i) % 1000000007
	}
	return res
}

1685.有序数组中差绝对值之和(2)¶

题目

给你一个 非递减有序整数数组nums。
请你建立并返回一个整数数组result，它跟nums长度相同，
且result[i]等于nums[i]与数组中所有其他元素差的绝对值之和。
换句话说，result[i]等于sum(|nums[i]-nums[j]|) ，
其中0 <= j < nums.length 且j != i（下标从 0 开始）。
示例 1：输入：nums = [2,3,5] 输出：[4,3,5]
解释：假设数组下标从 0 开始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
示例 2：输入：nums = [1,4,6,8,10] 输出：[24,15,13,15,21]
提示：2 <= nums.length <= 105
1 <= nums[i] <= nums[i + 1] <= 104

解题思路

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

func getSumAbsoluteDifferences(nums []int) []int {
	n := len(nums)
	res := make([]int, 0)
	right := 0 // 右边和
	left := 0  // 左边和
	for i := 1; i < n; i++ {
		right = right + (nums[i] - nums[0])
	}
	res = append(res, right)
	for i := 1; i < n; i++ {
		diff := nums[i] - nums[i-1]
		left = left + diff*i
		right = right - diff*(n-i)
		res = append(res, left+right)
	}
	return res
}

# 2
func getSumAbsoluteDifferences(nums []int) []int {
	n := len(nums)
	res := make([]int, 0)
	arr := make([]int, 0)
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + nums[i]
		arr = append(arr, sum)
	}
	res = append(res, sum-n*nums[0])
	for i := 1; i < n; i++ {
		left := nums[i]*i - arr[i-1]              // 左边和
		right := (sum - arr[i]) - nums[i]*(n-1-i) // 右边和
		res = append(res, left+right)
	}
	return res
}

1686.石子游戏VI(1)¶

题目

Alice 和Bob 轮流玩一个游戏，Alice 先手。
一堆石子里总共有n个石子，轮到某个玩家时，他可以移出一个石子并得到这个石子的价值。
Alice 和 Bob 对石子价值有不一样的的评判标准。双方都知道对方的评判标准。
给你两个长度为 n的整数数组aliceValues 和bobValues。
aliceValues[i] 和bobValues[i]分别表示 Alice 和 Bob 认为第i个石子的价值。
所有石子都被取完后，得分较高的人为胜者。
如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略进行游戏。
请你推断游戏的结果，用如下的方式表示：
如果 Alice 赢，返回1。
如果 Bob 赢，返回-1。
如果游戏平局，返回0。
示例 1：输入：aliceValues = [1,3], bobValues = [2,1] 输出：1
解释：如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。
示例 2：输入：aliceValues = [1,2], bobValues = [3,1] 输出：0
解释：Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。
示例 3：输入：aliceValues = [2,4,3], bobValues = [1,6,7] 输出：-1
解释：不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。
提示：n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100

解题思路

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

func stoneGameVI(aliceValues []int, bobValues []int) int {
	arr := make([][2]int, len(aliceValues))
	for i := 0; i < len(arr); i++ {
		arr[i] = [2]int{i, aliceValues[i] + bobValues[i]}
	}
	// 贪心策略：将两组石头的价值相加，每次取价值最大的那一组
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][1] > arr[j][1]
	})
	a, b := 0, 0
	for i := 0; i < len(arr); i++ {
		if i%2 == 0 {
			a = a + aliceValues[arr[i][0]]
		} else {
			b = b + bobValues[arr[i][0]]
		}
	}
	if a == b {
		return 0
	} else if a > b {
		return 1
	}
	return -1
}

1689.十-二进制数的最少数目(1)¶

题目

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。
例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。
给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。
示例 1：输入：n = "32" 输出：3
解释：10 + 11 + 11 = 32
示例 2：输入：n = "82734" 输出：8
示例 3：输入：n = "27346209830709182346" 输出：9
提示：1 <= n.length <= 105
n 仅由数字组成
n 不含任何前导零并总是表示正整数

解题思路

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

func minPartitions(n string) int {
	res := 0
	for i := 0; i < len(n); i++ {
		value := int(n[i] - '0')
		if value > res {
			res = value
		}
	}
	return res
}

1690.石子游戏VII(4)¶

题目

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，
并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。
爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，
如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。
示例 1：输入：stones = [5,3,1,4,2] 输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。
示例 2：输入：stones = [7,90,5,1,100,10,10,2] 输出：122
提示：n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

解题思路

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

func stoneGameVII(stones []int) int {
	n := len(stones)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + stones[i]
	}
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	for j := 2; j <= n; j++ {
		for i := 0; i+j <= n; i++ {
			left := arr[i+j] - arr[i+1] - dp[i+1][i+j-1] // 左边得分-得分
			right := arr[i+j-1] - arr[i] - dp[i][i+j-2]  // 右边得分-得分
			dp[i][i+j-1] = max(left, right)
		}
	}
	return dp[0][n-1]
}

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

# 2
var dp [][]int
var arr []int

func stoneGameVII(stones []int) int {
	n := len(stones)
	arr = make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + stones[i]
	}
	dp = make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if i == j {
				continue
			}
			dp[i][j] = -1
		}
	}
	dfs(0, n-1)
	return dp[0][n-1]
}

func dfs(i, j int) int {
	if dp[i][j] != -1 {
		return dp[i][j]
	}
	left := arr[j+1] - arr[i+1] - dfs(i+1, j)
	right := arr[j] - arr[i] - dfs(i, j-1)
	dp[i][j] = max(left, right)
	return dp[i][j]
}

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

# 3
func stoneGameVII(stones []int) int {
	n := len(stones)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + stones[i]
	}
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			left := arr[j+1] - arr[i+1] - dp[i+1][j] // 左边得分-得分
			right := arr[j] - arr[i] - dp[i][j-1]    // 右边得分-得分
			dp[i][j] = max(left, right)
		}
	}
	return dp[0][n-1]
}

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

# 4
func stoneGameVII(stones []int) int {
	n := len(stones)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + stones[i]
	}
	dp := make([]int, n)
	for i := n - 2; i >= 0; i-- {
		sum := stones[i]
		for j := i + 1; j < n; j++ {
			sum = sum + stones[j]
			left := sum - stones[i] - dp[j]    // 左边得分-得分
			right := sum - stones[j] - dp[j-1] // 右边得分-得分
			dp[j] = max(left, right)
		}
	}
	return dp[n-1]
}

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

1695.删除子数组的最大得分(1)¶

题目

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。
删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是a 的一个子数组。
示例 1：输入：nums = [4,2,4,5,6] 输出：17
解释：最优子数组是 [2,4,5,6]
示例 2：输入：nums = [5,2,1,2,5,2,1,2,5] 输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
提示：1 <= nums.length <= 105
1 <= nums[i] <= 104

解题思路

No.	思路	时间复杂度	空间复杂度
01	滑动窗口	O(n)	O(n)

func maximumUniqueSubarray(nums []int) int {
	res := 0
	sum := 0
	m := make(map[int]int)
	left := 0
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
		sum = sum + nums[i]
		for m[nums[i]] > 1 {
			m[nums[left]]--
			sum = sum - nums[left]
			left++
		}
		if sum > res {
			res = sum
		}
	}
	return res
}

1696.跳跃游戏VI(4)¶

题目

给你一个下标从 0 开始的整数数组 nums和一个整数 k。
一开始你在下标0处。每一步，你最多可以往前跳k步，但你不能跳出数组的边界。
也就是说，你可以从下标i跳到[i + 1， min(n - 1, i + k)]包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1），你的 得分为经过的所有数字之和。
请你返回你能得到的 最大得分。
示例 1：输入：nums = [1,-1,-2,4,-7,3], k = 2 输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
示例 2：输入：nums = [10,-5,-2,4,0,3], k = 3 输出：17
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 输出：0
提示：1 <= nums.length, k <= 105
-104<= nums[i]<= 104

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n)
02	动态规划	O(n)	O(n)
03	栈辅助	O(n)	O(n)
04	堆	O(nlog(n))	O(n)

func maxResult(nums []int, k int) int {
	n := len(nums)
	dp := make([]int, n)
	if k > n {
		k = n
	}
	dp[0] = nums[0]
	maxValue := nums[0]
	for i := 1; i < len(nums); i++ {
		if i <= k { // 在前k个，dp[i] = maxValue + nums[i]
			dp[i] = maxValue + nums[i]
			maxValue = max(maxValue, dp[i])
		} else {
			if maxValue == dp[i-1-k] { // 需要重新找maxValue
				maxValue = getMaxValue(dp[i-k : i])
			}
			dp[i] = maxValue + nums[i]
			maxValue = max(maxValue, dp[i])
		}
	}
	return dp[n-1]
}

func getMaxValue(arr []int) int {
	maxValue := arr[0]
	for i := 0; i < len(arr); i++ {
		if arr[i] > maxValue {
			maxValue = arr[i]
		}
	}
	return maxValue
}

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

# 2
func maxResult(nums []int, k int) int {
	n := len(nums)
	dp := make([]int, n)
	if k > n {
		k = n
	}
	dp[0] = nums[0]
	maxValue := nums[0]
	maxIndex := 0
	for i := 1; i < len(nums); i++ {
		if i <= k { // 在前k个，dp[i] = maxValue + nums[i]
			dp[i] = maxValue + nums[i]
			if dp[i] >= maxValue {
				maxValue = dp[i]
				maxIndex = i
			}
		} else {
			if i-k > maxIndex {
				maxValue = dp[maxIndex+1]
				for j := maxIndex + 1; j < i; j++ {
					if dp[j] >= maxValue {
						maxValue = dp[j]
						maxIndex = j
					}
				}
			}
			dp[i] = maxValue + nums[i]
			if dp[i] >= maxValue {
				maxValue = dp[i]
				maxIndex = i
			}
		}
	}
	return dp[n-1]
}

# 3
func maxResult(nums []int, k int) int {
	n := len(nums)
	if k > n {
		k = n
	}
	res := nums[0]
	stack := make([][2]int, 0)
	stack = append(stack, [2]int{0, nums[0]})
	for i := 1; i < len(nums); i++ {
		if stack[0][0] < i-k {
			stack = stack[1:]
		}
		res = stack[0][1] + nums[i]
		for len(stack) > 0 && stack[len(stack)-1][1] < res {
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, [2]int{i, res})
	}
	return res
}

# 4
func maxResult(nums []int, k int) int {
	n := len(nums)
	if k > n {
		k = n
	}
	res := nums[0]
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	heap.Push(&intHeap, [2]int{0, nums[0]})
	for i := 1; i < len(nums); i++ {
		for i-intHeap[0][0] > k { // 不满足删除
			heap.Pop(&intHeap)
		}
		res = intHeap[0][1] + nums[i]
		heap.Push(&intHeap, [2]int{i, res})
	}
	return res
}

type IntHeap [][2]int

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

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

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.([2]int))
}

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

1601-1700-Hard¶

1606.找到处理最多请求的服务器(2)¶

题目

你有 k个服务器，编号为 0到 k-1，它们可以同时处理多个请求组。
每个服务器有无穷的计算能力但是 不能同时处理超过一个请求。请求分配到服务器的规则如下：
第i（序号从 0 开始）个请求到达。
如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。
如果第(i % k)个服务器空闲，那么对应服务器会处理该请求。
否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器）。
比方说，如果第 i个服务器在忙，那么会查看第 (i+1)个服务器，第 (i+2)个服务器等等。
给你一个 严格递增的正整数数组arrival，表示第i个任务的到达时间，和另一个数组load，
其中load[i]表示第i个请求的工作量（也就是服务器完成它所需要的时间）。
你的任务是找到 最繁忙的服务器。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。
请你返回包含所有最繁忙服务器序号的列表，你可以以任意顺序返回这个列表。
示例 1：输入：k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]  输出：[1] 
解释：所有服务器一开始都是空闲的。
前 3 个请求分别由前 3 台服务器依次处理。
请求 3 进来的时候，服务器 0 被占据，所以它呗安排到下一台空闲的服务器，也就是服务器 1 。
请求 4 进来的时候，由于所有服务器都被占据，该请求被舍弃。
服务器 0 和 2 分别都处理了一个请求，服务器 1 处理了两个请求。所以服务器 1 是最忙的服务器。
示例 2：输入：k = 3, arrival = [1,2,3,4], load = [1,2,1,2] 输出：[0]
解释：前 3 个请求分别被前 3 个服务器处理。
请求 3 进来，由于服务器 0 空闲，它被服务器 0 处理。
服务器 0 处理了两个请求，服务器 1 和 2 分别处理了一个请求。所以服务器 0 是最忙的服务器。
示例 3：输入：k = 3, arrival = [1,2,3], load = [10,12,11] 输出：[0,1,2]
解释：每个服务器分别处理了一个请求，所以它们都是最忙的服务器。
示例 4：输入：k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2] 输出：[1]
示例 5：输入：k = 1, arrival = [1], load = [1] 输出：[0]
提示：1 <= k <= 105
1 <= arrival.length, load.length <= 105
arrival.length == load.length
1 <= arrival[i], load[i] <= 109
arrival保证 严格递增。

解题思路

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

func busiestServers(k int, arrival []int, load []int) []int {
	n := len(arrival)
	res := make([]int, 0)
	freeHeap := &mixHeap{isBig: false} // 小根堆：下标小的优先处理
	busyHeap := &mixHeap{isBig: false} // 小根堆： 空闲时间小，早结束
	for i := 0; i < k; i++ {
		freeHeap.push([]int{i})
	}
	arr := make([]int, k)
	for i := 0; i < n; i++ {
		start := arrival[i]
		// busy堆执行完出队列
		for busyHeap.Len() > 0 && busyHeap.Top()[0] <= start {
			id := busyHeap.pop()[1]
			// i+((id-i)%k+k)%k 表示下一个循环的编号
			freeHeap.push([]int{i + ((id-i)%k+k)%k}) // 入free堆：注意时间处理，负数取模后要取正
		}
		// 选择一个执行，如果为空舍弃：条件2
		if freeHeap.Len() > 0 {
			id := freeHeap.pop()[0] % k
			busyHeap.push([]int{start + load[i], id}) // 结束时间+id
			arr[id]++
		}
	}
	var maxValue int
	for i := 0; i < len(arr); i++ {
		if arr[i] > maxValue {
			maxValue = arr[i]
			res = []int{i}
		} else if arr[i] == maxValue {
			res = append(res, i)
		}
	}
	return res
}

type mixHeap struct {
	arr   [][]int
	isBig bool
}

func (m *mixHeap) Len() int {
	return len(m.arr)
}

func (m *mixHeap) Swap(i, j int) {
	m.arr[i], m.arr[j] = m.arr[j], m.arr[i]
}

func (m *mixHeap) Less(i, j int) bool {
	if m.isBig {
		return m.arr[i][0] > m.arr[j][0] // 大根堆
	}
	return m.arr[i][0] < m.arr[j][0] // 小根堆
}

func (m *mixHeap) Push(x interface{}) {
	m.arr = append(m.arr, x.([]int))
}

func (m *mixHeap) Pop() interface{} {
	value := (m.arr)[len(m.arr)-1]
	m.arr = (m.arr)[:len(m.arr)-1]
	return value
}

func (m *mixHeap) push(x []int) {
	heap.Push(m, x)
}

func (m *mixHeap) pop() []int {
	return heap.Pop(m).([]int)
}

func (m *mixHeap) Top() []int {
	if m.Len() > 0 {
		return m.arr[0]
	}
	return nil
}

# 2
func busiestServers(k int, arrival []int, load []int) []int {
	n := len(arrival)
	res := make([]int, 0)
	arr := make([]int, k)
	free := make([]int, k)
	for i := 0; i < k; i++ {
		free[i] = i
	}
	busyHeap := make(IntHeap, 0)
	heap.Init(&busyHeap)
	for i := 0; i < n; i++ {
		start := arrival[i]
		// busy堆执行完出队列
		for busyHeap.Len() > 0 && busyHeap[0][0] <= start {
			// free插入该下标：插入有序数组后有序
			id := busyHeap[0][1]
			index := sort.SearchInts(free, id)
			free = append(free[:index], append([]int{id}, free[index:]...)...)
			heap.Pop(&busyHeap)
		}
		if len(free) == 0 {
			continue
		}
		id := sort.SearchInts(free, i%k)
		if id == len(free) {
			id = 0
		}
		arr[free[id]]++
		heap.Push(&busyHeap, []int{start + load[i], free[id]})
		free = append(free[:id], free[id+1:]...) // 删除该下标
	}
	var maxValue int
	for i := 0; i < len(arr); i++ {
		if arr[i] > maxValue {
			maxValue = arr[i]
			res = []int{i}
		} else if arr[i] == maxValue {
			res = append(res, i)
		}
	}
	return res
}

type IntHeap [][]int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
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
}

1611.使整数变为0的最少操作次数(3)¶

题目

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。
示例 1：输入：n = 0 输出：0
示例 2：输入：n = 3 输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。
示例 3：输入：n = 6 输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。
示例 4：输入：n = 9 输出：14
示例 5：输入：n = 333 输出：393
提示：0 <= n <= 109

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(log(n))	O(1)
02	格雷码	O(log(n))	O(1)
03	遍历	O(log(n))	O(1)

func minimumOneBitOperations(n int) int {
	// 依次将高位的1翻转为0
	// 操作2：00..110000..00 => 00..010000..00
	// 操作2+操作1：00..010000..00 => 00..011000..00
	// 操作2：00..011000..00 => 00..001000..00
	res := 0
	if n == 0 {
		return 0
	}
	for i := 0; (1 << i) <= n; i++ {
		if (1<<i)&n > 0 { // 第i位>0
			total := 1<<(1+i) - 1 // 把(1+i)位数变为100..00的次数
			res = total - res     // 交替加减
		}
	}
	return res
}

# 2
func minimumOneBitOperations(n int) int {
	// 在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同
	// 则称这种编码为格雷码（Gray Code）
	res := 0
	for n > 0 {
		res = res ^ n
		n = n / 2
	}
	return res
}

# 3
func minimumOneBitOperations(n int) int {
	// 依次将高位的1翻转为0
	// 操作2：00..110000..00 => 00..010000..00
	// 操作2+操作1：00..010000..00 => 00..011000..00
	// 操作2：00..011000..00 => 00..001000..00
	res := 0
	if n == 0 {
		return 0
	}
	length := bits.Len(uint(n))
	flag := 1
	for i := 0; (1 << i) <= n; i++ {
		if (1<<(length-1-i))&n > 0 { // 第length-1-i位>0{
			total := 1<<(length-i) - 1
			res = res + total*flag
			flag = -1 * flag
		}
	}
	return res
}

1649.通过指令创建有序数组(2)¶

题目

给你一个整数数组instructions，你需要根据instructions中的元素创建一个有序数组。
一开始你有一个空的数组nums，你需要从左到右遍历instructions中的元素，将它们依次插入nums数组中。
每一次插入操作的代价是以下两者的 较小值：
nums中 严格小于instructions[i]的数字数目。
nums中 严格大于instructions[i]的数字数目。
比方说，如果要将3 插入到nums = [1,2,3,5]，
那么插入操作的代价为min(2, 1) (元素1和2小于3，元素5大于3），插入后nums 变成[1,2,3,3,5]。
请你返回将instructions中所有元素依次插入nums后的 总最小代价。由于答案会很大，请将它对109 + 7取余后返回。
示例 1：输入：instructions = [1,5,6,2] 输出：1
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 5 ，代价为 min(1, 0) = 0 ，现在 nums = [1,5] 。
插入 6 ，代价为 min(2, 0) = 0 ，现在 nums = [1,5,6] 。
插入 2 ，代价为 min(1, 2) = 1 ，现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。
示例 2:输入：instructions = [1,2,3,6,5,4] 输出：3
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。
插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。
插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。
插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。
插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。
示例 3：输入：instructions = [1,3,3,3,2,4,2,1,2] 输出：4
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。
插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。
插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。
插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。
提示：1 <= instructions.length <= 105
1 <= instructions[i] <= 105

解题思路

No.	思路	时间复杂度	空间复杂度
01	树状数组	O(nlog(n))	O(n)
02	线段树	O(nlog(n))	O(n)

var mod = 1000000007

func createSortedArray(instructions []int) int {
	res := 0
	c = make([]int, 100002)
	length = 100001
	for i := 0; i < len(instructions); i++ {
		value := instructions[i]
		upData(value, 1) // 次数+1
		left := getSum(value - 1)
		right := getSum(100000) - getSum(value)
		res = (res + min(left, right)) % mod
	}
	return res
}

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

var length int
var c []int // 树状数组

func lowBit(x int) int {
	return x & (-x)
}

// 单点修改
func upData(i, k int) { // 在i位置加上k
	for i <= length {
		c[i] = c[i] + k
		i = i + lowBit(i) // i = i + 2^k
	}
}

// 区间查询
func getSum(i int) int {
	res := 0
	for i > 0 {
		res = res + c[i]
		i = i - lowBit(i)
	}
	return res
}

# 2
var mod = 1000000007

func createSortedArray(instructions []int) int {
	res := 0
	n := 100001
	arr = make([]int, n*4+1)
	for i := 0; i < len(instructions); i++ {
		x := instructions[i]
		left := query(0, 1, n, 1, x-1)  // 查询1~x-1
		right := query(0, 1, n, x+1, n) // 查询 x+1~n
		res = (res + min(left, right)) % mod
		update(0, 1, n, x) // 添加x
	}
	return res
}

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

var arr []int // 线段树

func update(id int, left, right, x int) {
	if left > x || right < x {
		return
	}
	arr[id]++
	if left == right {
		return
	}
	mid := left + (right-left)/2
	update(2*id+1, left, mid, x)    // 左节点
	update(2*id+2, mid+1, right, x) // 右节点
}

func query(id int, left, right, queryLeft, queryRight int) int {
	if left > queryRight || right < queryLeft {
		return 0
	}
	if queryLeft <= left && right <= queryRight {
		return arr[id]
	}
	mid := left + (right-left)/2
	return query(id*2+1, left, mid, queryLeft, queryRight) +
		query(id*2+2, mid+1, right, queryLeft, queryRight)
}

1655.分配重复整数¶

题目¶

给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值。
同时你有 m个顾客的订单 quantity，其中，整数quantity[i]是第i位顾客订单的数目。
请你判断是否能将 nums中的整数分配给这些顾客，且满足：
第i位顾客 恰好有quantity[i]个整数。
第i位顾客拿到的整数都是 相同的。
每位顾客都满足上述两个要求。
如果你可以分配 nums中的整数满足上面的要求，那么请返回true，否则返回 false。
示例 1：输入：nums = [1,2,3,4], quantity = [2] 输出：false
解释：第 0 位顾客没办法得到两个相同的整数。
示例 2：输入：nums = [1,2,3,3], quantity = [2] 输出：true
解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。
示例 3：输入：nums = [1,1,2,2], quantity = [2,2] 输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。
示例 4：输入：nums = [1,1,2,3], quantity = [2,2] 输出：false
解释：尽管第 0 位顾客可以得到 [1,1] ，第 1 位顾客没法得到 2 个一样的整数。
示例 5：输入：nums = [1,1,1,1,1], quantity = [2,3] 输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [1,1,1] 。
提示：n == nums.length
1 <= n <= 105
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 105
nums中至多有50个不同的数字。

解题思路¶

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

1665.完成所有任务的最少初始能量(1)¶

题目

给你一个任务数组tasks ，其中tasks[i] = [actuali, minimumi]：
actuali是完成第 i个任务 需要耗费的实际能量。
minimumi是开始第 i个任务前需要达到的最低能量。
比方说，如果任务为[10, 12]且你当前的能量为11，那么你不能开始这个任务。
如果你当前的能量为13，你可以完成这个任务，且完成它后剩余能量为 3。
你可以按照 任意顺序完成任务。
请你返回完成所有任务的 最少初始能量。
示例 1：输入：tasks = [[1,2],[2,4],[4,8]] 输出：8
解释：一开始有 8 能量，我们按照如下顺序完成任务：
    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。
示例 2：输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]] 输出：32
解释：一开始有 32 能量，我们按照如下顺序完成任务：
    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。
示例 3：输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]] 输出：27
解释：一开始有 27 能量，我们按照如下顺序完成任务：
    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。
提示：1 <= tasks.length <= 105
1 <= actuali<= minimumi<= 104

解题思路

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

func minimumEffort(tasks [][]int) int {
	sort.Slice(tasks, func(i, j int) bool {
		return tasks[i][1]-tasks[i][0] > tasks[j][1]-tasks[j][0]
	})
	total := 0
	res := 0
	for i := 0; i < len(tasks); i++ {
		res = max(res, total+tasks[i][1])
		total = total + tasks[i][0]
	}
	return res
}

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

1671.得到山形数组的最少删除次数(1)¶

题目

我们定义arr是 山形数组当且仅当它满足：
arr.length >= 3
存在某个下标i（从 0 开始）满足0 < i < arr.length - 1且：
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给你整数数组nums，请你返回将 nums变成 山形状数组的最少删除次数。
示例 1：输入：nums = [1,3,1] 输出：0
解释：数组本身就是山形数组，所以我们不需要删除任何元素。
示例 2：输入：nums = [2,1,1,5,6,2,3,1]输出：3
解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。
示例 3：输入：nums = [4,3,2,1,1,2,3,1]输出：4
提示：输入：nums = [1,2,3,4,4,3,2,1]输出：1
提示：3 <= nums.length <= 1000
1 <= nums[i] <= 109
题目保证nums 删除一些元素后一定能得到山形数组。

解题思路

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

func minimumMountainRemovals(nums []int) int {
	n := len(nums)
	res := 0
	left := make([]int, n)
	right := make([]int, n)
	for i := 0; i < n; i++ {
		left[i] = 0
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				left[i] = max(left[j]+1, left[i])
			}
		}
	}
	for i := n - 1; i >= 0; i-- {
		right[i] = 0
		for j := n - 1; j > i; j-- {
			if nums[j] < nums[i] {
				right[i] = max(right[j]+1, right[i])
			}
		}
	}
	for i := 1; i < n-1; i++ {
		res = max(res, left[i]+right[i]+1)
	}
	return n - res
}

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

1675.数组的最小偏移量(1)¶

题目

给你一个由 n 个正整数组成的数组 nums 。
你可以对数组的任意元素执行任意次数的两类操作：
如果元素是 偶数 ，除以 2
例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
如果元素是 奇数 ，乘上 2
例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]
数组的 偏移量 是数组中任意两个元素之间的 最大差值 。
返回数组在执行某些操作之后可以拥有的 最小偏移量 。
示例 1：输入：nums = [1,2,3,4] 输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1
示例 2：输入：nums = [4,1,5,20,3] 输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3
示例 3：输入：nums = [2,10,8] 输出：3
提示：n == nums.length
2 <= n <= 105
1 <= nums[i] <= 109

解题思路

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

func minimumDeviation(nums []int) int {
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	minValue := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		if nums[i]%2 == 1 { // 奇数x2=>变为偶数放入堆， 统一处理为偶数
			nums[i] = nums[i] * 2
		}
		heap.Push(&intHeap, nums[i])
		minValue = min(minValue, nums[i]) // 记录最小值
	}
	res := intHeap[0] - minValue
	for intHeap.Len() > 0 && intHeap[0]%2 == 0 { //  把最大偶数处理/2
		node := heap.Pop(&intHeap).(int)
		minValue = min(minValue, node/2)
		heap.Push(&intHeap, node/2)
		res = min(res, intHeap[0]-minValue) // 目标结果：将最大值除以2，用最大值减去最小值
	}
	return res
}

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

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
}

1691.堆叠长方体的最大高度(1)¶

题目

给你 n 个长方体 cuboids ，
其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。
请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，
你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
返回 堆叠长方体cuboids 可以得到的 最大高度 。
示例 1：输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]] 输出：190
解释：第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
总高度是 95 + 50 + 45 = 190 。
示例 2：输入：cuboids = [[38,25,45],[76,35,3]] 输出：76
解释：无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。
示例 3：输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出：102
解释：重新排列长方体后，可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下，这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。
提示：n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100

解题思路

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

func maxHeight(cuboids [][]int) int {
	for i := 0; i < len(cuboids); i++ {
		arr := cuboids[i]
		sort.Ints(arr)
		cuboids[i] = arr
	}
	sort.Slice(cuboids, func(i, j int) bool {
		if cuboids[i][0] == cuboids[j][0] {
			if cuboids[i][1] == cuboids[j][1] {
				return cuboids[i][2] < cuboids[j][2]
			}
			return cuboids[i][1] < cuboids[j][1]
		}
		return cuboids[i][0] < cuboids[j][0]
	})
	n := len(cuboids)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = cuboids[i][2]
	}
	res := dp[0]
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if cuboids[i][0] >= cuboids[j][0] &&
				cuboids[i][1] >= cuboids[j][1] &&
				cuboids[i][2] >= cuboids[j][2] {
				dp[i] = max(dp[i], dp[j]+cuboids[i][2])
			}
		}
		res = max(res, dp[i])
	}
	return res
}

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