2001-2100-Easy

2006.差的绝对值为K的数对数目(2)

• 题目

给你一个整数数组nums和一个整数k，请你返回数对(i, j)的数目，满足i < j且|nums[i] - nums[j]| == k。
|x|的值定义为：
如果x >= 0，那么值为x。
如果x < 0，那么值为-x。
示例 1：输入：nums = [1,2,2,1], k = 1 输出：4
解释：差的绝对值为 1 的数对为：
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
示例 2：输入：nums = [1,3], k = 3 输出：0
解释：没有任何数对差的绝对值为 3 。
示例 3：输入：nums = [3,2,1,5,4], k = 2 输出：3
解释：差的绝对值为 2 的数对为：
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]
提示：1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

• 解题思路

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

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

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

2011.执行操作后的变量值(2)

• 题目

存在一种仅支持 4 种操作和 1 个变量 X 的编程语言：
++X 和 X++ 使变量 X 的值 加 1
--X 和 X-- 使变量 X 的值 减 1
最初，X 的值是 0
给你一个字符串数组 operations ，这是由操作组成的一个列表，返回执行所有操作后， X 的 最终值 。
示例 1：输入：operations = ["--X","X++","X++"] 输出：1
解释：操作按下述步骤执行：
最初，X = 0
--X：X 减 1 ，X =  0 - 1 = -1
X++：X 加 1 ，X = -1 + 1 =  0
X++：X 加 1 ，X =  0 + 1 =  1
示例 2：输入：operations = ["++X","++X","X++"] 输出：3
解释：操作按下述步骤执行： 
最初，X = 0
++X：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
X++：X 加 1 ，X = 2 + 1 = 3
示例 3：输入：operations = ["X++","++X","--X","X--"] 输出：0
解释：操作按下述步骤执行：
最初，X = 0
X++：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
--X：X 减 1 ，X = 2 - 1 = 1
X--：X 减 1 ，X = 1 - 1 = 0
提示：1 <= operations.length <= 100
operations[i] 将会是 "++X"、"X++"、"--X" 或 "X--"

• 解题思路

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

func finalValueAfterOperations(operations []string) int {
	res := 0
	for i := 0; i < len(operations); i++ {
		if operations[i][1] == '+' {
			res++
		} else {
			res--
		}
	}
	return res
}

# 2
func finalValueAfterOperations(operations []string) int {
	res := 0
	for i := 0; i < len(operations); i++ {
		if strings.Contains(operations[i], "+") {
			res++
		} else {
			res--
		}
	}
	return res
}

2016.增量元素之间的最大差值(2)

• 题目

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，
请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。
返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1 。
示例 1：输入：nums = [7,1,5,4] 输出：4
解释：最大差值出现在 i = 1 且 j = 2 时，nums[j] - nums[i] = 5 - 1 = 4 。
注意，尽管 i = 1 且 j = 0 时 ，nums[j] - nums[i] = 7 - 1 = 6 > 4 ，但 i > j 不满足题面要求，所以 6 不是有效的答案。
示例 2：输入：nums = [9,4,3,2] 输出：-1
解释：不存在同时满足 i < j 和 nums[i] < nums[j] 这两个条件的 i, j 组合。
示例 3：输入：nums = [1,5,2,10] 输出：9
解释：最大差值出现在 i = 0 且 j = 3 时，nums[j] - nums[i] = 10 - 1 = 9 。
提示：n == nums.length
2 <= n <= 1000
1 <= nums[i] <= 109

• 解题思路

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

func maximumDifference(nums []int) int {
	res := 0
	minValue := nums[0]
	for i := 1; i < len(nums); i++ {
		res = max(res, nums[i]-minValue)
		minValue = min(minValue, nums[i])
	}
	if res == 0 {
		return -1
	}
	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 b
	}
	return a
}

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

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

2022.将一维数组转变成二维数组(2)

• 题目

给你一个下标从 0开始的一维整数数组original和两个整数m和n。
你需要使用original中所有元素创建一个m行n列的二维数组。
original中下标从 0到 n - 1（都 包含 ）的元素构成二维数组的第一行，
下标从 n到 2 * n - 1（都 包含）的元素构成二维数组的第二行，依此类推。
请你根据上述过程返回一个m x n的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。
示例 1：输入：original = [1,2,3,4], m = 2, n = 2 输出：[[1,2],[3,4]]
解释：构造出的二维数组应该包含 2 行 2 列。
original 中第一个 n=2 的部分为 [1,2] ，构成二维数组的第一行。
original 中第二个 n=2 的部分为 [3,4] ，构成二维数组的第二行。
示例 2：输入：original = [1,2,3], m = 1, n = 3 输出：[[1,2,3]]
解释：构造出的二维数组应该包含 1 行 3 列。
将 original 中所有三个元素放入第一行中，构成要求的二维数组。
示例 3：输入：original = [1,2], m = 1, n = 1 输出：[]
解释：original 中有 2 个元素。
无法将 2 个元素放入到一个 1x1 的二维数组中，所以返回一个空的二维数组。
示例 4：输入：original = [3], m = 1, n = 2 输出：[]
解释：original 中只有 1 个元素。
无法将 1 个元素放满一个 1x2 的二维数组，所以返回一个空的二维数组。
提示：1 <= original.length <= 5 * 104
1 <= original[i] <= 105
1 <= m, n <= 4 * 104

• 解题思路

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

func construct2DArray(original []int, m int, n int) [][]int {
	total := len(original)
	if n*m != total {
		return nil
	}
	res := make([][]int, 0)
	index := 0
	for i := 0; i < m; i++ {
		temp := make([]int, 0)
		for j := 0; j < n; j++ {
			temp = append(temp, original[index])
			index++
		}
		res = append(res, temp)
	}
	return res
}

# 2
func construct2DArray(original []int, m int, n int) [][]int {
	total := len(original)
	if n*m != total {
		return nil
	}
	res := make([][]int, 0)
	for i := 0; i < total; i = i + n {
		res = append(res, original[i:i+n])
	}
	return res
}

2027.转换字符串的最少操作次(2)

• 题目

给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。
一次 操作 定义为从 s 中选出 三个连续字符 并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持 不变 。
返回将 s 中所有字符均转换为 'O' 需要执行的最少操作次数。
示例 1：输入：s = "XXX" 输出：1
解释：XXX -> OOO
一次操作，选中全部 3 个字符，并将它们转换为 'O' 。
示例 2：输入：s = "XXOX" 输出：2
解释：XXOX -> OOOX -> OOOO
第一次操作，选择前 3 个字符，并将这些字符转换为 'O' 。
然后，选中后 3 个字符，并执行转换。最终得到的字符串全由字符 'O' 组成。
示例 3：输入：s = "OOOO" 输出：0
解释：s 中不存在需要转换的 'X' 。
提示：3 <= s.length <= 1000
s[i] 为 'X' 或 'O'

• 解题思路

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

func minimumMoves(s string) int {
	arr := []byte(s)
	res := 0
	for i := 0; i < len(s); i++ {
		if arr[i] == 'X' {
			count := 0
			for j := i; j < len(s); j++ {
				arr[j] = 'O'
				count++
				if count == 3 {
					break
				}
			}
			res++
		}
	}
	return res
}

# 2
func minimumMoves(s string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'X' {
			i = i + 2
			res++
		}
	}
	return res
}

2032.至少在两个数组中出现的值(2)

• 题目

给你三个整数数组 nums1、nums2 和 nums3 ，请你构造并返回一个 不同 数组，且由 至少 在 两个 数组中出现的所有值组成。
数组中的元素可以按 任意 顺序排列。
示例 1：输入：nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3] 输出：[3,2]
解释：至少在两个数组中出现的所有值为：
- 3 ，在全部三个数组中都出现过。
- 2 ，在数组 nums1 和 nums2 中出现过。
示例 2：输入：nums1 = [3,1], nums2 = [2,3], nums3 = [1,2] 输出：[2,3,1]
解释：至少在两个数组中出现的所有值为：
- 2 ，在数组 nums2 和 nums3 中出现过。
- 3 ，在数组 nums1 和 nums2 中出现过。
- 1 ，在数组 nums1 和 nums3 中出现过。
示例 3：输入：nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5] 输出：[]
解释：不存在至少在两个数组中出现的值。
提示：1 <= nums1.length, nums2.length, nums3.length <= 100
1 <= nums1[i], nums2[j], nums3[k] <= 100

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	哈希辅助+位运算	O(n)	O(n)

func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) []int {
	m1, m2, m3 := make(map[int]int), make(map[int]int), make(map[int]int)
	for i := 0; i < len(nums1); i++ {
		m1[nums1[i]] = 1
	}
	for i := 0; i < len(nums2); i++ {
		m2[nums2[i]] = 1
	}
	for i := 0; i < len(nums3); i++ {
		m3[nums3[i]] = 1
	}
	res := make([]int, 0)
	for i := 1; i <= 300; i++ {
		a := m1[i] + m2[i] + m3[i]
		if a >= 2 {
			res = append(res, i)
		}
	}
	return res
}

# 2
func twoOutOfThree(nums1 []int, nums2 []int, nums3 []int) []int {
	m := make(map[int]int)
	arr := [][]int{nums1, nums2, nums3}
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr[i]); j++ {
			value := arr[i][j]
			m[value] = m[value] | (1 << i)
		}
	}
	res := make([]int, 0)
	for k, v := range m {
		if bits.OnesCount(uint(v)) >= 2 {
			res = append(res, k)
		}
	}
	return res
}

2037.使每位学生都有座位的最少移动次数(1)

• 题目

一个房间里有 n个座位和 n名学生，房间用一个数轴表示。给你一个长度为 n的数组seats，其中seats[i] 是第 i个座位的位置。
同时给你一个长度为 n的数组students，其中students[j]是第 j位学生的位置。
你可以执行以下操作任意次：
增加或者减少第i位学生的位置，每次变化量为 1（也就是将第 i位学生从位置 x移动到 x + 1或者 x - 1）
请你返回使所有学生都有座位坐的 最少移动次数，并确保没有两位学生的座位相同。
请注意，初始时有可能有多个座位或者多位学生在 同一位置。
示例 1：输入：seats = [3,1,5], students = [2,7,4] 输出：4
解释：学生移动方式如下：
- 第一位学生从位置 2 移动到位置 1 ，移动 1 次。
- 第二位学生从位置 7 移动到位置 5 ，移动 2 次。
- 第三位学生从位置 4 移动到位置 3 ，移动 1 次。
总共 1 + 2 + 1 = 4 次移动。
示例 2：输入：seats = [4,1,5,9], students = [1,3,2,6] 输出：7
解释：学生移动方式如下：
- 第一位学生不移动。
- 第二位学生从位置 3 移动到位置 4 ，移动 1 次。
- 第三位学生从位置 2 移动到位置 5 ，移动 3 次。
- 第四位学生从位置 6 移动到位置 9 ，移动 3 次。
总共 0 + 1 + 3 + 3 = 7 次移动。
示例 3：输入：seats = [2,2,6,6], students = [1,3,2,6] 输出：4
解释：学生移动方式如下：
- 第一位学生从位置 1 移动到位置 2 ，移动 1 次。
- 第二位学生从位置 3 移动到位置 6 ，移动 3 次。
- 第三位学生不移动。
- 第四位学生不移动。
总共 1 + 3 + 0 + 0 = 4 次移动。
提示：n == seats.length == students.length
1 <= n <= 100
1 <= seats[i], students[j] <= 100

• 解题思路

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

func minMovesToSeat(seats []int, students []int) int {
	res := 0
	sort.Ints(seats)
	sort.Ints(students)
	for i := 0; i < len(seats); i++ {
		res = res + abs(students[i]-seats[i])
	}
	return res
}

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

2042.检查句子中的数字是否递增(1)

• 题目

句子是由若干 token 组成的一个列表，token 间用 单个 空格分隔，句子没有前导或尾随空格。
每个 token 要么是一个由数字 0-9 组成的不含前导零的 正整数，要么是一个由小写英文字母组成的 单词 。
示例，"a puppy has 2 eyes 4 legs" 是一个由 7 个 token 组成的句子：
"2" 和 "4" 是数字，其他像"puppy" 这样的 tokens 属于单词。
给你一个表示句子的字符串 s ，你需要检查 s 中的 全部 数字是否从左到右严格递增
（即，除了最后一个数字，s 中的 每个 数字都严格小于它 右侧 的数字）。
如果满足题目要求，返回 true，否则，返回 false 。
示例 1：输入：s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles" 输出：true
解释：句子中的数字是：1, 3, 4, 6, 12 。
这些数字是按从左到右严格递增的 1 < 3 < 4 < 6 < 12 。
示例 2：输入：s = "hello world 5 x 5" 输出：false
解释：句子中的数字是：5, 5 。这些数字不是严格递增的。
示例 3：输入：s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s" 输出：false
解释：s 中的数字是：7, 51, 50, 60 。这些数字不是严格递增的。
示例 4：输入：s = "4 5 11 26" 输出：true
解释：s 中的数字是：4, 5, 11, 26 。
这些数字是按从左到右严格递增的：4 < 5 < 11 < 26 。
提示：3 <= s.length <= 200
s 由小写英文字母、空格和数字 0 到 9 组成（包含 0 和 9）
s 中数字 token 的数目在 2 和 100 之间（包含 2 和 100）
s 中的 token 之间由单个空格分隔
s 中至少有 两个 数字
s 中的每个数字都是一个 小于 100 的 正 数，且不含前导零
s 不含前导或尾随空格

• 解题思路

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

func areNumbersAscending(s string) bool {
	arr := strings.Split(s, " ")
	prev := -1
	for i := 0; i < len(arr); i++ {
		if '0' <= arr[i][0] && arr[i][0] <= '9' {
			value, _ := strconv.Atoi(arr[i])
			if value > prev {
				prev = value
			} else {
				return false
			}
		}
	}
	return true
}

2047.句子中的有效单词数(2)

• 题目

句子仅由小写字母（'a' 到 'z'）、数字（'0' 到 '9'）、连字符（'-'）、标点符号（'!'、'.' 和 ','）以及空格（' '）组成。
每个句子可以根据空格分解成 一个或者多个 token ，这些 token 之间由一个或者多个空格 ' ' 分隔。
如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：
仅由小写字母、连字符和/或标点（不含数字）。
至多一个 连字符 '-' 。如果存在，连字符两侧应当都存在小写字母（"a-b" 是一个有效单词，但 "-ab" 和 "ab-" 不是有效单词）。
至多一个 标点符号。如果存在，标点符号应当位于 token 的 末尾 。
这里给出几个有效单词的例子："a-b."、"afad"、"ba-c"、"a!" 和 "!" 。
给你一个字符串 sentence ，请你找出并返回 sentence 中 有效单词的数目 。
示例 1：输入：sentence = "cat and  dog" 输出：3
解释：句子中的有效单词是 "cat"、"and" 和 "dog"
示例 2：输入：sentence = "!this  1-s b8d!" 输出：0
解释：句子中没有有效单词
"!this" 不是有效单词，因为它以一个标点开头
"1-s" 和 "b8d" 也不是有效单词，因为它们都包含数字
示例 3：输入：sentence = "alice and  bob are playing stone-game10" 输出：5
解释：句子中的有效单词是 "alice"、"and"、"bob"、"are" 和 "playing"
"stone-game10" 不是有效单词，因为它含有数字
示例 4：输入：sentence = "he bought 2 pencils, 3 erasers, and 1  pencil-sharpener." 输出：6
解释：句子中的有效单词是 "he"、"bought"、"pencils,"、"erasers,"、"and" 和 "pencil-sharpener."
提示：1 <= sentence.length <= 1000
sentence 由小写英文字母、数字（0-9）、以及字符（' '、'-'、'!'、'.' 和 ','）组成
句子中至少有 1 个 token

• 解题思路

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

var m map[byte]bool = map[byte]bool{
	'!': true,
	'.': true,
	',': true,
}

func countValidWords(sentence string) int {
	res := 0
	arr := strings.Fields(sentence)
	for i := 0; i < len(arr); i++ {
		flag := true
		countA := 0
		countB := 0
		for j := 0; j < len(arr[i]); j++ {
			if '0' <= arr[i][j] && arr[i][j] <= '9' {
				flag = false
				break
			}
			if m[arr[i][j]] == true {
				countA++
				if j != len(arr[i])-1 {
					flag = false
					break
				}
			}
			if arr[i][j] == '-' {
				countB++
				if j == 0 || j == len(arr[i])-1 {
					flag = false
					break
				}
				if (('a' <= arr[i][j-1] && arr[i][j-1] <= 'z') &&
					('a' <= arr[i][j+1] && arr[i][j+1] <= 'z')) == false {
					flag = false
					break
				}
			}
		}
		if flag == true && countA <= 1 && countB <= 1 {
			res++
		}
	}
	return res
}

# 2
var m map[byte]bool = map[byte]bool{
	'!': true,
	'.': true,
	',': true,
}

func countValidWords(sentence string) int {
	res := 0
	arr := strings.Fields(sentence)
	for i := 0; i < len(arr); i++ {
		temp := arr[i]
		if m[temp[len(temp)-1]] == true {
			temp = temp[:len(temp)-1]
		}
		if strings.ContainsAny(arr[i], "0123456789") ||
			strings.ContainsAny(temp, "!.,") ||
			strings.Count(temp, "-") >= 2 {
			continue
		}
		j := strings.IndexByte(temp, '-')
		// 存在-
		if j >= 0 && (j == 0 || j == len(temp)-1 || unicode.IsLower(rune(temp[j-1])) == false ||
			unicode.IsLower(rune(temp[j+1])) == false) {
			continue
		}
		res++
	}
	return res
}

2053.数组中第K个独一无二的字符串(1)

• 题目

独一无二的字符串指的是在一个数组中只出现过 一次的字符串。
给你一个字符串数组arr和一个整数k，请你返回arr中第k个独一无二的字符串。
如果少于k个独一无二的字符串，那么返回空字符串""。
注意，按照字符串在原数组中的 顺序找到第 k个独一无二字符串。
示例 1:输入：arr = ["d","b","c","b","c","a"], k = 2 输出："a"
解释：arr 中独一无二字符串包括 "d" 和 "a"。
"d" 首先出现，所以它是第 1 个独一无二字符串。
"a" 第二个出现，所以它是 2 个独一无二字符串。
由于 k == 2 ，返回 "a" 。
示例 2:输入：arr = ["aaa","aa","a"], k = 1 输出："aaa"
解释：arr 中所有字符串都是独一无二的，所以返回第 1 个字符串 "aaa" 。
示例 3：输入：arr = ["a","b","a"], k = 3 输出：""
解释：唯一一个独一无二字符串是 "b" 。由于少于 3 个独一无二字符串，我们返回空字符串 "" 。
提示：1 <= k <= arr.length <= 1000
1 <= arr[i].length <= 5
arr[i]只包含小写英文字母。

• 解题思路

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

func kthDistinct(arr []string, k int) string {
	m := make(map[string]int)
	for i := 0; i < len(arr); i++ {
		m[arr[i]]++
	}
	for i := 0; i < len(arr); i++ {
		if m[arr[i]] == 1 {
			k--
			if k == 0 {
				return arr[i]
			}
		}
	}
	return ""
}

2057.值相等的最小索引(1)

• 题目

给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；
如果不存在这样的下标，返回 -1 。
x mod y 表示 x 除以 y 的 余数 。
示例 1：输入：nums = [0,1,2] 输出：0
解释：i=0: 0 mod 10 = 0 == nums[0].
i=1: 1 mod 10 = 1 == nums[1].
i=2: 2 mod 10 = 2 == nums[2].
所有下标都满足 i mod 10 == nums[i] ，所以返回最小下标 0
示例 2：输入：nums = [4,3,2,1] 输出：2
解释：i=0: 0 mod 10 = 0 != nums[0].
i=1: 1 mod 10 = 1 != nums[1].
i=2: 2 mod 10 = 2 == nums[2].
i=3: 3 mod 10 = 3 != nums[3].
2 唯一一个满足 i mod 10 == nums[i] 的下标
示例 3：输入：nums = [1,2,3,4,5,6,7,8,9,0] 输出：-1
解释：不存在满足 i mod 10 == nums[i] 的下标
示例 4：输入：nums = [2,1,3,5,2] 输出：1
解释：1 是唯一一个满足 i mod 10 == nums[i] 的下标
提示：1 <= nums.length <= 100
0 <= nums[i] <= 9

• 解题思路

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

func smallestEqual(nums []int) int {
	for i := 0; i < len(nums); i++ {
		if i%10 == nums[i] {
			return i
		}
	}
	return -1
}

2062.统计字符串中的元音子字符串(2)

• 题目

子字符串 是字符串中的一个连续（非空）的字符序列。
元音子字符串 是 仅 由元音（'a'、'e'、'i'、'o' 和 'u'）组成的一个子字符串，且必须包含 全部五种 元音。
给你一个字符串 word ，统计并返回 word 中 元音子字符串的数目 。
示例 1：输入：word = "aeiouu" 输出：2
解释：下面列出 word 中的元音子字符串（斜体加粗部分）：
- "aeiouu"
- "aeiouu"
示例 2：输入：word = "unicornarihan" 输出：0
解释：word 中不含 5 种元音，所以也不会存在元音子字符串。
示例 3：输入：word = "cuaieuouac" 输出：7
解释：下面列出 word 中的元音子字符串（斜体加粗部分）：
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
示例 4：输入：word = "bbaeixoubb" 输出：0
解释：所有包含全部五种元音的子字符串都含有辅音，所以不存在元音子字符串。
提示：1 <= word.length <= 100
word 仅由小写英文字母组成

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(1)
02	滑动窗口	O(n)	O(1)

var m = map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}

func countVowelSubstrings(word string) int {
	n := len(word)
	res := 0
	for i := 0; i < n; i++ {
		temp := make(map[byte]bool)
		for j := i; j < n; j++ {
			if m[word[j]] == false {
				break
			}
			temp[word[j]] = true
			if len(temp) == 5 {
				res++
			}
		}
	}
	return res
}

# 2
var m = map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}

func countVowelSubstrings(word string) int {
	n := len(word)
	res := 0
	temp := make(map[byte]int)
	count := 1
	start := -1
	for i := 0; i < n; i++ {
		if m[word[i]] == false {
			temp = make(map[byte]int)
			count = 1
			start = i
			continue
		}
		temp[word[i]]++
		for temp[word[start+count]] > 1 { // 左边多余的字母个数
			temp[word[start+count]]--
			count++
		}
		if len(temp) == 5 {
			res = res + count
		}
	}
	return res
}

2068.检查两个字符串是否几乎相等(2)

• 题目

如果两个字符串 word1和 word2中从 'a'到 'z'每一个字母出现频率之差都 不超过3，
那么我们称这两个字符串word1 和word2 几乎相等。
给你两个长度都为n的字符串word1 和word2，如果word1和word2几乎相等，请你返回true，否则返回false。
一个字母 x的出现 频率指的是它在字符串中出现的次数。
示例 1：输入：word1 = "aaaa", word2 = "bccb" 输出：false
解释：字符串 "aaaa" 中有 4 个 'a' ，但是 "bccb" 中有 0 个 'a' 。
两者之差为 4 ，大于上限 3 。
示例 2：输入：word1 = "abcdeef", word2 = "abaaacc" 输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 1 次，在 word2 中出现了 4 次，差为 3 。
- 'b' 在 word1 中出现了 1 次，在 word2 中出现了 1 次，差为 0 。
- 'c' 在 word1 中出现了 1 次，在 word2 中出现了 2 次，差为 1 。
- 'd' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
- 'e' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
- 'f' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
示例 3：输入：word1 = "cccddabba", word2 = "babababab" 输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 2 次，在 word2 中出现了 4 次，差为 2 。
- 'b' 在 word1 中出现了 2 次，在 word2 中出现了 5 次，差为 3 。
- 'c' 在 word1 中出现了 3 次，在 word2 中出现了 0 次，差为 3 。
- 'd' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
提示：n == word1.length == word2.length
1 <= n <= 100
word1 和word2都只包含小写英文字母。

• 解题思路

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

func checkAlmostEquivalent(word1 string, word2 string) bool {
	a, b := [26]int{}, [26]int{}
	for i := 0; i < len(word1); i++ {
		a[int(word1[i]-'a')]++
	}
	for i := 0; i < len(word2); i++ {
		b[int(word2[i]-'a')]++
	}
	for i := 0; i < 26; i++ {
		if a[i]-b[i] > 3 || b[i]-a[i] > 3 {
			return false
		}
	}
	return true
}

# 2
func checkAlmostEquivalent(word1 string, word2 string) bool {
	a := [26]int{}
	for i := 0; i < len(word1); i++ {
		a[int(word1[i]-'a')]++
	}
	for i := 0; i < len(word2); i++ {
		a[int(word2[i]-'a')]--
	}
	for i := 0; i < 26; i++ {
		if a[i] > 3 || a[i] < -3 {
			return false
		}
	}
	return true
}

2073.买票需要的时间(2)

• 题目

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。
给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。
每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，
他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。
返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。
示例 1：输入：tickets = [2,3,2], k = 2 输出：6
解释： - 第一轮，队伍中的每个人都买到一张票，队伍变为 [1, 2, 1] 。
- 第二轮，队伍中的每个都又都买到一张票，队伍变为 [0, 1, 0] 。
位置 2 的人成功买到 2 张票，用掉 3 + 3 = 6 秒。
示例 2：输入：tickets = [5,1,1,1], k = 0 输出：8
解释：- 第一轮，队伍中的每个人都买到一张票，队伍变为 [4, 0, 0, 0] 。
- 接下来的 4 轮，只有位置 0 的人在买票。
位置 0 的人成功买到 5 张票，用掉 4 + 1 + 1 + 1 + 1 = 8 秒。
提示：n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

• 解题思路

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

func timeRequiredToBuy(tickets []int, k int) int {
	res := 1
	for {
		for i := 0; i < len(tickets); i++ {
			if tickets[i] == 0 {
				continue
			}
			tickets[i]--
			if tickets[i] == 0 && i == k {
				return res
			}
			res++
		}
	}
}

# 2
func timeRequiredToBuy(tickets []int, k int) int {
	res := 0
	for i := 0; i < len(tickets); i++ {
		if i <= k {
			res = res + min(tickets[k], tickets[i]) // 前面的人，最多跟第k个人一样多
		} else {
			res = res + min(tickets[k]-1, tickets[i]) // 后面的人，少一次选择
		}
	}
	return res
}

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

2078.两栋颜色不同且距离最远的房子(2)

• 题目

街上有 n 栋房子整齐地排成一列，每栋房子都粉刷上了漂亮的颜色。
给你一个下标从 0 开始且长度为 n 的整数数组 colors ，其中 colors[i] 表示第 i 栋房子的颜色。
返回 两栋 颜色 不同 房子之间的 最大 距离。
第 i 栋房子和第 j 栋房子之间的距离是 abs(i - j) ，其中 abs(x) 是 x 的绝对值。
示例 1：输入：colors = [1,1,1,6,1,1,1] 输出：3
解释：上图中，颜色 1 标识成蓝色，颜色 6 标识成红色。
两栋颜色不同且距离最远的房子是房子 0 和房子 3 。
房子 0 的颜色是颜色 1 ，房子 3 的颜色是颜色 6 。两栋房子之间的距离是 abs(0 - 3) = 3 。
注意，房子 3 和房子 6 也可以产生最佳答案。
示例 2：输入：colors = [1,8,3,8,3] 输出：4
解释：上图中，颜色 1 标识成蓝色，颜色 8 标识成黄色，颜色 3 标识成绿色。
两栋颜色不同且距离最远的房子是房子 0 和房子 4 。
房子 0 的颜色是颜色 1 ，房子 4 的颜色是颜色 3 。两栋房子之间的距离是 abs(0 - 4) = 4 。
示例 3：输入：colors = [0,1] 输出：1
解释：两栋颜色不同且距离最远的房子是房子 0 和房子 1 。
房子 0 的颜色是颜色 0 ，房子 1 的颜色是颜色 1 。两栋房子之间的距离是 abs(0 - 1) = 1 。
提示：n ==colors.length
2 <= n <= 100
0 <= colors[i] <= 100
生成的测试数据满足 至少 存在 2 栋颜色不同的房子

• 解题思路

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

func maxDistance(colors []int) int {
	res := 0
	for i := 0; i < len(colors); i++ {
		for j := i + 1; j < len(colors); j++ {
			if colors[i] != colors[j] {
				res = max(res, j-i)
			}
		}
	}
	return res
}

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

# 2
func maxDistance(colors []int) int {
	n := len(colors)
	if colors[0] != colors[n-1] {
		return n - 1
	}
	left, right := 1, n-2
	for colors[n-1] == colors[left] {
		left++
	}
	for colors[0] == colors[right] {
		right--
	}
	return max(right, n-1-left)
}

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

2085.统计出现过一次的公共字符串(1)

• 题目

给你两个字符串数组words1和words2，请你返回在两个字符串数组中 都恰好出现一次的字符串的数目。
示例 1：输入：words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"] 输出：2
解释：- "leetcode" 在两个数组中都恰好出现一次，计入答案。
- "amazing" 在两个数组中都恰好出现一次，计入答案。
- "is" 在两个数组中都出现过，但在 words1 中出现了 2 次，不计入答案。
- "as" 在 words1 中出现了一次，但是在 words2 中没有出现过，不计入答案。
所以，有 2 个字符串在两个数组中都恰好出现了一次。
示例 2：输入：words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"] 输出：0
解释：没有字符串在两个数组中都恰好出现一次。
示例 3：输入：words1 = ["a","ab"], words2 = ["a","a","a","ab"] 输出：1
解释：唯一在两个数组中都出现一次的字符串是 "ab" 。
提示：1 <= words1.length, words2.length <= 1000
1 <= words1[i].length, words2[j].length <= 30
words1[i] 和words2[j]都只包含小写英文字母。

• 解题思路

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

func countWords(words1 []string, words2 []string) int {
	a, b := make(map[string]int), make(map[string]int)
	for i := 0; i < len(words1); i++ {
		a[words1[i]]++
	}
	for i := 0; i < len(words2); i++ {
		b[words2[i]]++
	}
	res := 0
	for k, v := range a {
		if v == 1 && b[k] == 1 {
			res++
		}
	}
	return res
}

2089.找出数组排序后的目标下标(2)

• 题目

给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。
目标下标 是一个满足nums[i] == target 的下标 i 。
将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。
如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列。
示例 1：输入：nums = [1,2,5,2,3], target = 2 输出：[1,2]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 2 的下标是 1 和 2 。
示例 2：输入：nums = [1,2,5,2,3], target = 3 输出：[3]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 3 的下标是 3 。
示例 3：输入：nums = [1,2,5,2,3], target = 5 输出：[4]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 5 的下标是 4 。
示例 4：输入：nums = [1,2,5,2,3], target = 4 输出：[]
解释：nums 中不含值为 4 的元素。
提示：1 <= nums.length <= 100
1 <= nums[i], target <= 100

• 解题思路

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

func targetIndices(nums []int, target int) []int {
	sort.Ints(nums)
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			res = append(res, i)
		}
	}
	return res
}

# 2
func targetIndices(nums []int, target int) []int {
	res := make([]int, 0)
	start := 0
	count := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			count++
		} else if nums[i] < target {
			start++
		}
	}
	for i := start; i < start+count; i++ {
		res = append(res, i)
	}
	return res
}

2094.找出3位偶数(2)

• 题目

给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。
你需要找出 所有 满足下述条件且 互不相同 的整数：
该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。
该整数不含 前导零
该整数是一个 偶数
例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。
将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。
示例 1：输入：digits = [2,1,3,0] 输出：[102,120,130,132,210,230,302,310,312,320]
解释：所有满足题目条件的整数都在输出数组中列出。 
注意，答案数组中不含有 奇数 或带 前导零 的整数。
示例 2：输入：digits = [2,2,8,8,2] 输出：[222,228,282,288,822,828,882]
解释：同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。 
在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。 
示例 3：输入：digits = [3,7,5] 输出：[]
解释：使用给定的 digits 无法构造偶数。
示例 4：输入：digits = [0,2,0,0] 输出：[200]
解释：唯一一个不含 前导零 且满足全部条件的整数是 200 。
示例 5：输入：digits = [0,0,0] 输出：[]
解释：构造的所有整数都会有 前导零 。因此，不存在满足题目条件的整数。
提示：3 <=digits.length <= 100
0 <= digits[i] <= 9

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^3)	O(n)
02	枚举	O(nlog(n))	O(1)

func findEvenNumbers(digits []int) []int {
	m := make(map[int]bool)
	n := len(digits)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < n; k++ {
				if i == j || j == k || i == k {
					continue
				}
				v := digits[i]*100 + digits[j]*10 + digits[k]
				if 100 <= v && v%2 == 0 {
					m[v] = true
				}
			}
		}
	}
	arr := make([]int, 0)
	for k := range m {
		arr = append(arr, k)
	}
	sort.Ints(arr)
	return arr
}

# 2
func findEvenNumbers(digits []int) []int {
	res := make([]int, 0)
	m := make(map[int]int)
	for i := 0; i < len(digits); i++ {
		m[digits[i]]++
	}
	for i := 100; i < 1000; i = i + 2 {
		temp := make(map[int]int)
		value := i
		flag := true
		for value > 0 {
			temp[value%10]++
			if m[value%10] < temp[value%10] {
				flag = false
				break
			}
			value = value / 10
		}
		if flag == true {
			res = append(res, i)
		}
	}
	return res
}

2099.找到和最大的长度为K的子序列(1)

• 题目

给你一个整数数组nums和一个整数k。你需要找到nums中长度为 k的 子序列，且这个子序列的和最大。
请你返回 任意 一个长度为k的整数子序列。
子序列定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。
示例 1：输入：nums = [2,1,3,3], k = 2 输出：[3,3]
解释：子序列有最大和：3 + 3 = 6 。
示例 2：输入：nums = [-1,-2,3,4], k = 3 输出：[-1,3,4]
解释：子序列有最大和：-1 + 3 + 4 = 6 。
示例 3：输入：nums = [3,4,3,3], k = 2 输出：[3,4]
解释：子序列有最大和：3 + 4 = 7 。
另一个可行的子序列为 [4, 3] 。
提示：1 <= nums.length <= 1000
-105<= nums[i] <= 105
1 <= k <= nums.length

• 解题思路

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

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

2001-2100-Medium

2001.可互换矩形的组数(1)

• 题目

用一个下标从 0 开始的二维整数数组rectangles 来表示 n 个矩形，
其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。
如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。
更规范的说法是，两个矩形满足widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。
计算并返回rectangles 中有多少对 可互换 矩形。
示例 1：输入：rectangles = [[4,8],[3,6],[10,20],[15,30]] 输出：6
解释：下面按下标（从 0 开始）列出可互换矩形的配对情况：
- 矩形 0 和矩形 1 ：4/8 == 3/6
- 矩形 0 和矩形 2 ：4/8 == 10/20
- 矩形 0 和矩形 3 ：4/8 == 15/30
- 矩形 1 和矩形 2 ：3/6 == 10/20
- 矩形 1 和矩形 3 ：3/6 == 15/30
- 矩形 2 和矩形 3 ：10/20 == 15/30
示例 2：输入：rectangles = [[4,5],[7,8]] 输出：0
解释：不存在成对的可互换矩形。
提示：n == rectangles.length
1 <= n <= 105
rectangles[i].length == 2
1 <= widthi, heighti <= 105

• 解题思路

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

func interchangeableRectangles(rectangles [][]int) int64 {
	m := make(map[string]int64)
	res := int64(0)
	for i := 0; i < len(rectangles); i++ {
		a, b := rectangles[i][0], rectangles[i][1]
		c := gcd(a, b)
		m[fmt.Sprintf("%d,%d", a/c, b/c)]++
	}
	for _, v := range m {
		res = res + (v-1)*v/2
	}
	return res
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

2002.两个回文子序列长度的最大乘积(3)

• 题目

给你一个字符串s，请你找到s中两个不相交回文子序列，使得它们长度的乘积最大。
两个子序列在原字符串中如果没有任何相同下标的字符，则它们是不相交的。
请你返回两个回文子序列长度可以达到的最大乘积。
子序列指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。
如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串。
示例 1：输入：s = "leetcodecom" 输出：9
解释：最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。
它们的乘积为 3 * 3 = 9 。
示例 2：输入：s = "bb" 输出：1
解释：最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。
它们的乘积为 1 * 1 = 1 。
示例 3：输入：s = "accbcaxxcxx" 输出：25
解释：最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。
它们的乘积为 5 * 5 = 25 。
提示：2 <= s.length <= 12
s只含有小写英文字母。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(3^n)	O(n)
02	状态压缩+遍历	O(4^n)	O(2^n)
03	状态压缩+枚举子集	O(n*2^n)	O(2^n)

var res int

func maxProduct(s string) int {
	res = 0
	dfs(s, "", "", 0)
	return res
}

func dfs(s string, a, b string, index int) {
	if len(a) > 0 && len(b) > 0 &&
		isPalindrome(a, 0, len(a)-1) && isPalindrome(b, 0, len(b)-1) {
		res = max(res, len(a)*len(b))
	}
	if index == len(s) {
		return
	}
	dfs(s, a, b, index+1)                  // a,b都不选
	dfs(s, a+string(s[index]), b, index+1) // a不选
	dfs(s, a, b+string(s[index]), index+1) // b不选
}

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

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

# 2
func maxProduct(s string) int {
	res := 0
	n := len(s)
	total := 1 << n
	arr := make([]int, 0)
	for i := 1; i < total; i++ {
		if judge(s, i) {
			arr = append(arr, i)
		}
	}
	for i := 0; i < len(arr); i++ { // 枚举回文状态
		for j := i + 1; j < len(arr); j++ {
			if arr[i]&arr[j] == 0 {
				a, b := bits.OnesCount(uint(arr[i])), bits.OnesCount(uint(arr[j]))
				res = max(res, a*b)
			}
		}
	}
	return res
}

func judge(s string, status int) bool {
	left, right := 0, len(s)-1
	for left < right {
		for left < right && (status&(1<<left)) == 0 {
			left++
		}
		for left < right && (status&(1<<right)) == 0 {
			right--
		}
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

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

# 3
func maxProduct(s string) int {
	res := 0
	n := len(s)
	total := 1 << n
	m := make(map[int]int, 0)
	for i := 1; i < total; i++ {
		if judge(s, i) {
			m[i] = bits.OnesCount(uint(i))
		}
	}
	for i := 1; i < total; i++ { // 遍历状态
		for j := i; j > 0; j = (j - 1) & i { // 枚举子集
			res = max(res, m[j]*m[j^i]) // 子集 * 子集的补集
		}
	}
	return res
}

func judge(s string, status int) bool {
	left, right := 0, len(s)-1
	for left < right {
		for left < right && (status&(1<<left)) == 0 {
			left++
		}
		for left < right && (status&(1<<right)) == 0 {
			right--
		}
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

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

2007.从双倍数组中还原原数组(2)

• 题目

一个整数数组original可以转变成一个 双倍数组changed，转变方式为将 original中每个元素 值乘以 2 加入数组中，
然后将所有元素 随机打乱。
给你一个数组changed，如果change是双倍数组，那么请你返回original数组，否则请返回空数组。
original的元素可以以任意顺序返回。
示例 1：输入：changed = [1,3,4,2,6,8] 输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
示例 2：输入：changed = [6,3,0,1] 输出：[]
解释：changed 不是一个双倍数组。
示例 3：输入：changed = [1] 输出：[]
解释：changed 不是一个双倍数组。
提示：1 <= changed.length <= 105
0 <= changed[i] <= 105

• 解题思路

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

func findOriginalArray(changed []int) []int {
	res := make([]int, 0)
	n := len(changed)
	if n%2 == 1 {
		return nil
	}
	sort.Ints(changed)
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		value := changed[i]
		if m[value] == 0 { // 不是双倍的元素
			m[value*2]++ // 标记双倍
			res = append(res, value)
		} else {
			m[value]--
			if m[value] == 0 {
				delete(m, value)
			}
		}
	}
	if len(m) == 0 {
		return res
	}
	return nil
}

# 2
func findOriginalArray(changed []int) []int {
	res := make([]int, 0)
	n := len(changed)
	if n%2 == 1 {
		return nil
	}
	sort.Ints(changed)
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		m[changed[i]]++
	}
	for i := 0; i < n; i++ {
		if m[changed[i]] != 0 {
			res = append(res, changed[i])
			m[changed[i]]--
			m[changed[i]*2]--
		}
	}
	if len(res)*2 != n {
		return nil
	}
	return res
}

2008.出租车的最大盈利(4)

• 题目

你驾驶出租车行驶在一条有 n个地点的路上。这 n个地点从近到远编号为1到n，你想要从 1开到 n，通过接乘客订单盈利。
你只能沿着编号递增的方向前进，不能改变方向。
乘客信息用一个下标从 0开始的二维数组rides表示，
其中rides[i] = [starti, endi, tipi]表示第i位乘客需要从地点starti前往endi，愿意支付tipi元的小费。
每一位 你选择接单的乘客i，你可以 盈利endi - starti + tipi元。你同时最多只能接一个订单。
给你 n和 rides，请你返回在最优接单方案下，你能盈利最多多少元。
注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。
示例 1：输入：n = 5, rides = [[2,5,4],[1,5,1]] 输出：7
解释：我们可以接乘客 0 的订单，获得 5 - 2 + 4 = 7 元。
示例 2：输入：n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]] 输出：20
解释：我们可以接以下乘客的订单：
- 将乘客 1 从地点 3 送往地点 10 ，获得 10 - 3 + 2 = 9 元。
- 将乘客 2 从地点 10 送往地点 12 ，获得 12 - 10 + 3 = 5 元。
- 将乘客 5 从地点 13 送往地点 18 ，获得 18 - 13 + 1 = 6 元。
我们总共获得 9 + 5 + 6 = 20 元。
提示：1 <= n <= 105
1 <= rides.length <= 3 * 104
rides[i].length == 3
1 <= starti < endi <= n
1 <= tipi <= 105

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划+二分查找+内置函数	O(nlog(n))	O(n)
02	动态规划+二分查找	O(nlog(n))	O(n)
03	动态规划	O(n)	O(n)
04	动态规划	O(n)	O(n)

func maxTaxiEarnings(n int, rides [][]int) int64 {
	m := len(rides)
	arr := make([][]int64, 0)
	for i := 0; i < m; i++ {
		a, b, c := rides[i][0], rides[i][1], rides[i][2]
		arr = append(arr, []int64{int64(a), int64(b), int64(b - a + c)})
	}
	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]
	})
	for i := 1; i < m; i++ {
		target := sort.Search(i, func(j int) bool {
			return arr[j][1] > arr[i][0]
		})
		if target == 0 {
			arr[i][2] = max(arr[i][2], arr[i-1][2])
		} else {
			arr[i][2] = max(arr[i][2]+arr[target-1][2], arr[i-1][2])
		}
	}
	return arr[m-1][2]
}

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

# 2
func maxTaxiEarnings(n int, rides [][]int) int64 {
	m := len(rides)
	arr := make([][]int64, 0)
	for i := 0; i < m; i++ {
		a, b, c := rides[i][0], rides[i][1], rides[i][2]
		arr = append(arr, []int64{int64(a), int64(b), int64(b - a + c)})
	}
	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]
	})
	dp := make([]int64, m)
	dp[0] = arr[0][2]
	for i := 1; i < m; i++ {
		left, right := 0, i-1
		for left < right {
			mid := left + (right-left)/2
			if arr[mid+1][1] <= arr[i][0] {
				left = mid + 1
			} else {
				right = mid
			}
		}
		if arr[left][1] <= arr[i][0] {
			dp[i] = max(dp[i-1], dp[left]+arr[i][2])
		} else {
			dp[i] = max(dp[i-1], arr[i][2])
		}
	}
	return dp[m-1]
}

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

# 3
func maxTaxiEarnings(n int, rides [][]int) int64 {
	dp := make([]int, n+1) // dp[i]到达i位置的最大盈利
	arr := make([][][2]int, n+1)
	for i := 0; i < len(rides); i++ {
		a, b, c := rides[i][0], rides[i][1], rides[i][2]
		arr[b] = append(arr[b], [2]int{a, b - a + c})
	}
	for i := 1; i <= n; i++ {
		dp[i] = dp[i-1]
		for j := 0; j < len(arr[i]); j++ {
			a, c := arr[i][j][0], arr[i][j][1]
			dp[i] = max(dp[i], dp[a]+c)
		}
	}
	return int64(dp[n])
}

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

# 4
func maxTaxiEarnings(n int, rides [][]int) int64 {
	dp := make([]int, n+1) // dp[i]到达i位置的最大盈利
	sort.Slice(rides, func(i, j int) bool {
		if rides[i][0] == rides[j][0] {
			return rides[i][1] < rides[j][1]
		}
		return rides[i][0] < rides[j][0]
	})
	j := 1
	for i := 0; i < len(rides); i++ { // 遍历订单
		a, b, c := rides[i][0], rides[i][1], rides[i][2]
		for j < a { // 更新指针
			j++
			dp[j] = max(dp[j], dp[j-1])
		}
		dp[b] = max(dp[b], dp[j]+(b-a+c))
	}
	for ; j <= n; j++ {
		dp[j] = max(dp[j], dp[j-1])
	}
	return int64(dp[n])
}

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

2012.数组美丽值求和(1)

• 题目

给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i（1 <= i <= nums.length - 2），nums[i] 的 美丽值 等于：
2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums[i] < nums[k]
1，如果满足 nums[i - 1] < nums[i] < nums[i + 1] ，且不满足前面的条件
0，如果上述条件全部不满足
返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的 美丽值的总和 。
示例 1：输入：nums = [1,2,3] 输出：2
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 2
示例 2：输入：nums = [2,4,6,4] 输出：1
解释：对于每个符合范围 1 <= i <= 2 的下标 i :
- nums[1] 的美丽值等于 1
- nums[2] 的美丽值等于 0
示例 3：输入：nums = [3,2,1] 输出：0
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 0
提示：3 <= nums.length <= 105
1 <= nums[i] <= 105

• 解题思路

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

func sumOfBeauties(nums []int) int {
	res := 0
	n := len(nums)
	arrA := make([]int, n)
	arrA[0] = nums[0]
	for i := 1; i < n; i++ {
		arrA[i] = max(nums[i], arrA[i-1])
	}
	arrB := make([]int, n)
	arrB[n-1] = nums[n-1]
	for i := n - 2; i >= 0; i-- {
		arrB[i] = min(nums[i], arrB[i+1])
	}
	for i := 1; i <= n-2; i++ {
		if arrA[i-1] < nums[i] && nums[i] < arrB[i+1] {
			res = res + 2
		} else if nums[i-1] < nums[i] && nums[i] < nums[i+1] {
			res = res + 1
		}
	}
	return res
}

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

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

2013.检测正方形(1)

• 题目

给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法：
添加 一个在数据流中的新点到某个数据结构中。可以添加 重复 的点，并会视作不同的点进行处理。
给你一个查询点，请你从数据结构中选出三个点，使这三个点和查询点一同构成一个 面积为正 的 轴对齐正方形 ，统计 满足该要求的方案数目。
轴对齐正方形 是一个正方形，除四条边长度相同外，还满足每条边都与 x-轴 或 y-轴 平行或垂直。
实现 DetectSquares 类：
DetectSquares() 使用空数据结构初始化对象
void add(int[] point) 向数据结构添加一个新的点 point = [x, y]
int count(int[] point) 统计按上述方式与点 point = [x, y] 共同构造 轴对齐正方形 的方案数。
示例：输入：["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
输出：[null, null, null, null, 1, 0, null, 2]
解释：DetectSquares detectSquares = new DetectSquares();
detectSquares.add([3, 10]);
detectSquares.add([11, 2]);
detectSquares.add([3, 2]);
detectSquares.count([11, 10]); // 返回 1 。你可以选择：
                               //   - 第一个，第二个，和第三个点
detectSquares.count([14, 8]);  // 返回 0 。查询点无法与数据结构中的这些点构成正方形。
detectSquares.add([11, 2]);    // 允许添加重复的点。
detectSquares.count([11, 10]); // 返回 2 。你可以选择：
                               //   - 第一个，第二个，和第三个点
                               //   - 第一个，第三个，和第四个点
提示：point.length == 2
0 <= x, y <= 1000
调用add 和 count 的 总次数 最多为 5000

• 解题思路

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

type DetectSquares struct {
	m map[int]map[int]int
}

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

func (this *DetectSquares) Add(point []int) {
	a, b := point[0], point[1]
	if this.m[a] == nil {
		this.m[a] = make(map[int]int)
	}
	this.m[a][b]++
}

func (this *DetectSquares) Count(point []int) int {
	res := 0
	x, y := point[0], point[1]
	for a := range this.m[x] { // 遍历同一列的y坐标
		if a == y {
			continue
		}
		length := abs(a - y) // 获取正方形边长
		b := x + length      // 右边
		if this.m[b] != nil && this.m[b][a] > 0 && this.m[b][y] > 0 {
			res = res + this.m[b][a]*this.m[b][y]*this.m[x][a]
		}
		b = x - length // 左边
		if this.m[b] != nil && this.m[b][a] > 0 && this.m[b][y] > 0 {
			res = res + this.m[b][a]*this.m[b][y]*this.m[x][a]
		}
	}
	return res
}

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

2017.网格游戏(1)

• 题目

给你一个下标从 0 开始的二维数组 grid ，数组大小为 2 x n ，其中 grid[r][c] 表示矩阵中 (r, c) 位置上的点数。
现在有两个机器人正在矩阵上参与一场游戏。
两个机器人初始位置都是 (0, 0) ，目标位置是 (1, n-1) 。
每个机器人只会 向右 ((r, c) 到 (r, c + 1)) 或 向下 ((r, c) 到 (r + 1, c)) 。
游戏开始，第一个 机器人从 (0, 0) 移动到 (1, n-1) ，并收集路径上单元格的全部点数。
对于路径上所有单元格 (r, c) ，途经后 grid[r][c] 会重置为 0 。
然后，第二个 机器人从 (0, 0) 移动到 (1, n-1) ，同样收集路径上单元的全部点数。注意，它们的路径可能会存在相交的部分。
第一个 机器人想要打击竞争对手，使 第二个 机器人收集到的点数 最小化 。
与此相对，第二个 机器人想要 最大化 自己收集到的点数。
两个机器人都发挥出自己的 最佳水平的前提下，返回 第二个 机器人收集到的 点数 。
示例 1：输入：grid = [[2,5,4],[1,5,1]] 输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 0 + 4 + 0 = 4 个点。
示例 2：输入：grid = [[3,3,1],[8,5,2]] 输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。 
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 3 + 1 + 0 = 4 个点。
示例 3：输入：grid = [[1,3,1,15],[1,3,3,1]] 输出：7
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 1 + 3 + 3 + 0 = 7 个点。
提示：grid.length == 2
n == grid[r].length
1 <= n <= 5 * 104
1 <= grid[r][c] <= 105

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+贪心	O(n)	O(n)

func gridGame(grid [][]int) int64 {
	n := len(grid[0])
	a := make([]int, n) // 前缀和：上边：从右到左
	b := make([]int, n) // 前缀和：下边，从左到右
	for i := n - 1; i > 0; i-- {
		a[i-1] = a[i] + grid[0][i]
	}
	for i := 0; i < n-1; i++ {
		b[i+1] = b[i] + grid[1][i]
	}
	res := math.MaxInt64
	// 当第一个机器人选择第i点往下走的时候
	// 第一个机器人不需要选择最大值，只需要考虑让第二个机器人选择最小
	for i := 0; i < n; i++ {
		// 第二个机器人只有2个选择，选其中最大的
		// 1、从第0个点往下走，拿到b[i]值
		// 2、一直往右走，拿到a[i]值
		res = min(res, max(a[i], b[i]))
	}
	return int64(res)
}

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

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

2018.判断单词是否能放入填字游戏内(1)

• 题目

给你一个m x n的矩阵board，它代表一个填字游戏当前的状态。填字游戏格子中包含小写英文字母（已填入的单词），
表示空格的' '和表示障碍格子的'#'。
如果满足以下条件，那么我们可以 水平（从左到右 或者从右到左）或 竖直（从上到下 或者从下到上）填入一个单词：
该单词不占据任何'#'对应的格子。
每个字母对应的格子要么是' '（空格）要么与 board中已有字母 匹配。
如果单词是 水平放置的，那么该单词左边和右边 相邻格子不能为' '或小写英文字母。
如果单词是竖直放置的，那么该单词上边和下边相邻格子不能为' '或小写英文字母。
给你一个字符串word，如果word可以被放入board中，请你返回true，否则请返回false。
示例 1：输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc" 输出：true
解释：单词 "abc" 可以如上图放置（从上往下）。
示例 2：输入：board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac" 输出：false
解释：无法放置单词，因为放置该单词后上方或者下方相邻格会有空格。
示例 3：输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca" 输出：true
解释：单词 "ca" 可以如上图放置（从右到左）。
提示：m == board.length
n == board[i].length
1 <= m * n <= 2 * 105
board[i][j]可能为' '，'#'或者一个小写英文字母。
1 <= word.length <= max(m, n)
word只包含小写英文字母。

• 解题思路

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

func placeWordInCrossword(board [][]byte, word string) bool {
	n, m := len(board), len(board[0])
	arr := make([][]byte, m)
	for i := 0; i < m; i++ {
		arr[i] = make([]byte, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr[j][i] = board[i][j] // 转置后统一按行处理
		}
	}
	return checkBoard(board, word) || checkBoard(arr, word)
}

func checkBoard(board [][]byte, word string) bool {
	for i := 0; i < len(board); i++ {
		arr := strings.Split(string(board[i]), "#") // 按#切割
		for j := 0; j < len(arr); j++ {
			if len(arr[j]) != len(word) { // 长度不等
				continue
			}
			left, right := true, true
			for k := 0; k < len(word); k++ { // 正向：word == arr[j]
				if arr[j][k] != ' ' && arr[j][k] != word[k] {
					left = false
					break
				}
			}
			for k := 0; k < len(word); k++ { // 反向：word == reverse(arr[j])
				if arr[j][k] != ' ' && arr[j][k] != word[len(word)-1-k] {
					right = false
					break
				}
			}
			if left == true || right == true {
				return true
			}
		}
	}
	return false
}

2023.连接后等于目标字符串的字符串对(2)

• 题目

给你一个 数字字符串数组 nums和一个 数字字符串 target，
请你返回 nums[i] + nums[j]（两个字符串连接）结果等于 target的下标 (i, j)（需满足 i != j）的数目。
示例 1：输入：nums = ["777","7","77","77"], target = "7777" 输出：4
解释：符合要求的下标对包括：
- (0, 1)："777" + "7"
- (1, 0)："7" + "777"
- (2, 3)："77" + "77"
- (3, 2)："77" + "77"
示例 2：输入：nums = ["123","4","12","34"], target = "1234" 输出：2
解释：符合要求的下标对包括
- (0, 1)："123" + "4"
- (2, 3)："12" + "34"
示例 3：输入：nums = ["1","1","1"], target = "11" 输出：6
解释：符合要求的下标对包括
- (0, 1)："1" + "1"
- (1, 0)："1" + "1"
- (0, 2)："1" + "1"
- (2, 0)："1" + "1"
- (1, 2)："1" + "1"
- (2, 1)："1" + "1"
提示：2 <= nums.length <= 100
1 <= nums[i].length <= 100
2 <= target.length <= 100
nums[i]和target只包含数字。
nums[i]和target不含有任何前导 0 。

• 解题思路

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

func numOfPairs(nums []string, target string) int {
	res := 0
	n := len(nums)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if nums[i]+nums[j] == target {
				res++
			}
			if nums[j]+nums[i] == target {
				res++
			}
		}
	}
	return res
}

# 2
func numOfPairs(nums []string, target string) int {
	res := 0
	n := len(nums)
	m := make(map[string]int)
	for i := 0; i < n; i++ {
		m[nums[i]]++
	}
	for i := 1; i < len(target); i++ {
		a, b := target[:i], target[i:]
		if a == b {
			res = res + m[a]*(m[a]-1)
		} else {
			res = res + m[a]*m[b]
		}
	}
	return res
}

2024.考试的最大困扰度(3)

• 题目

一位老师正在出一场由 n道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F'表示）。
老师想增加学生对自己做出答案的不确定性，方法是最大化有 连续相同结果的题数。（也就是连续出现 true 或者连续出现 false）。
给你一个字符串answerKey，其中answerKey[i]是第 i个问题的正确结果。
除此以外，还给你一个整数 k，表示你能进行以下操作的最多次数：
每次操作中，将问题的正确答案改为'T' 或者'F'（也就是将 answerKey[i] 改为'T'或者'F'）。
请你返回在不超过 k次操作的情况下，最大连续 'T'或者 'F'的数目。
示例 1：输入：answerKey = "TTFF", k = 2 输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。
示例 2：输入：answerKey = "TFFT", k = 1 输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。
示例 3：输入：answerKey = "TTFTTFTT", k = 1 输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。
提示：n == answerKey.length
1 <= n <= 5 * 104
answerKey[i]要么是'T' ，要么是'F'
1 <= k <= n

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	滑动窗口-双指针	O(n)	O(n)
02	滑动窗口-双指针	O(n)	O(1)
03	滑动窗口-双指针	O(n)	O(n)

func maxConsecutiveAnswers(answerKey string, k int) int {
	n := len(answerKey)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		if answerKey[i] == 'T' {
			arr[i] = 1
		}
	}
	a := longestOnes(arr, k)
	arr = make([]int, n)
	for i := 0; i < n; i++ {
		if answerKey[i] == 'F' {
			arr[i] = 1
		}
	}
	b := longestOnes(arr, k)
	return max(a, b)
}

// leetcode 1004.最大连续1的个数III
func longestOnes(A []int, K int) int {
	res := 0
	left, right := 0, 0
	count := 0
	for right = 0; right < len(A); right++ {
		if A[right] == 0 {
			count++
		}
		for count > K {
			if A[left] == 0 {
				count--
			}
			left++
		}
		res = max(res, right-left+1)
	}
	return res
}

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

# 2
func maxConsecutiveAnswers(answerKey string, k int) int {
	n := len(answerKey)
	res := 0
	left, right := 0, 0
	countA, countB := 0, 0
	for ; right < n; right++ {
		if answerKey[right] == 'T' {
			countA++
		} else {
			countB++
		}
		for countA > k && countB > k { // 都大于k时，滑动窗口才移动
			if answerKey[left] == 'T' {
				countA--
			} else {
				countB--
			}
			left++
		}
		res = max(res, right-left+1)
	}
	return res
}

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

# 3
func maxConsecutiveAnswers(answerKey string, k int) int {
	arr := []byte(answerKey)
	return max(longestOnes(arr, k, 'T'), longestOnes(arr, k, 'F'))
}

func longestOnes(A []byte, K int, target byte) int {
	res := 0
	left, right := 0, 0
	count := 0
	for right = 0; right < len(A); right++ {
		if A[right] == target {
			count++
		}
		for count > K {
			if A[left] == target {
				count--
			}
			left++
		}
		res = max(res, right-left+1)
	}
	return res
}

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

2028.找出缺失的观测数据(2)

• 题目

现有一份 n + m次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。
观测数据中缺失了 n 份，你手上只拿到剩余m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。
给你一个长度为 m 的整数数组 rolls ，其中rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。
返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。
如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。
k个数字的 平均值 为这些数字求和后再除以k 。
注意 mean 是一个整数，所以 n + m 次投掷的总和需要被n + m整除。
示例 1：输入：rolls = [3,2,4,3], mean = 4, n = 2 输出：[6,6]
解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。
示例 2：输入：rolls = [1,5,6], mean = 3, n = 4 输出：[2,3,2,2]
解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。
示例 3：输入：rolls = [1,2,3,4], mean = 6, n = 4 输出：[]
解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。
示例 4：输入：rolls = [1], mean = 3, n = 1 输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。
提示：m == rolls.length
1 <= n, m <= 105
1 <= rolls[i], mean <= 6

• 解题思路

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

func missingRolls(rolls []int, mean int, n int) []int {
	sum := 0
	m := len(rolls)
	for i := 0; i < m; i++ {
		sum = sum + rolls[i]
	}
	total := mean * (n + m)
	left := total - sum
	if left > n*6 || left < n {
		return nil
	}
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = left / n // 平均分配
	}
	for i := 0; i < left%n; i++ {
		res[i] = res[i] + 1
	}
	return res
}

# 2
func missingRolls(rolls []int, mean int, n int) []int {
	sum := 0
	m := len(rolls)
	for i := 0; i < m; i++ {
		sum = sum + rolls[i]
	}
	total := mean * (n + m)
	left := total - sum
	if left > n*6 || left < n {
		return nil
	}
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = 1
	}
	left = left - n
	for i := 0; i < n; i++ {
		if left < 6 {
			res[i] = res[i] + left
			break
		}
		res[i] = res[i] + 5
		left = left - 5
	}
	return res
}

2029.石子游戏IX(1)

• 题目

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。
给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。
Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones中移除任一石子。
如果玩家移除石子后，导致 所有已移除石子 的价值总和 可以被 3 整除，那么该玩家就 输掉游戏 。
如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。
假设两位玩家均采用最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。
示例 1：输入：stones = [2,1] 输出：true
解释：游戏进行如下：
- 回合 1：Alice 可以移除任意一个石子。
- 回合 2：Bob 移除剩下的石子。 
已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。
示例 2：输入：stones = [2] 输出：false
解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。 
由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。
示例 3：输入：stones = [5,1,2,4,3] 输出：false
解释：Bob 总会获胜。其中一种可能的游戏进行方式如下：
- 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
- 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
- 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
- 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
- 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.
Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。
提示：1 <= stones.length <= 105
1 <= stones[i] <= 104

• 解题思路

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

func stoneGameIX(stones []int) bool {
	m := make(map[int]int)
	for i := 0; i < len(stones); i++ {
		m[stones[i]%3]++
	}
	a, b, c := m[0], m[1], m[2] // 0,1,2的个数
	// 以1开头：1、(1、2)、1...
	// 以2开头：2、(2、1)、2...
	if a%2 == 0 { // 0为偶数个，可以抵消
		// 获胜策略：选择较少的1或者2
		// 1、1=2 => Alice赢（以1开始或者2开始都赢）
		// 不等的时候
		// 2.1、1>2 => Alice以2开头=> 2、2、1...(2、1).. 最后Bob没有2可选，只能选择1，Alice就赢了
		// 2.2 2>1 => Alice以1开头=> 1、1、2...(1、2).. 最后Bob没有1可选，只能选择2，Alice就赢了
		return b > 0 && c > 0
	}
	if a%2 == 1 {
		// 奇数个0
		// 获胜策略：选取较多的1或者2
		// 需要差值大于2个Alice才赢
		// 1>2 => Alice以1开头 => 1、(1、0)、2、1、1 / 1、(0、1)、2、1、1
		// 2>1 => Alice以2开头 => 2、(2、0)、1、2、2 / 2、(0、2)、1、2、2
		return b-c > 2 || c-b > 2
	}
	return false
}

2033.获取单值网格的最小操作数(1)

• 题目

给你一个大小为m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。
单值网格 是全部元素都相等的网格。
返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。
示例 1：输入：grid = [[2,4],[6,8]], x = 2 输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 
- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
共计 4 次操作。
示例 2：输入：grid = [[1,5],[2,3]], x = 1 输出：5
解释：可以使所有元素都等于 3 。
示例 3：输入：grid = [[1,2],[3,4]], x = 2 输出：-1
解释：无法使所有元素相等。
提示：m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
1 <= x, grid[i][j] <= 104

• 解题思路

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

func minOperations(grid [][]int, x int) int {
	n, m := len(grid), len(grid[0])
	arr := make([]int, 0)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr = append(arr, grid[i][j])
		}
	}
	sort.Ints(arr)
	target := arr[len(arr)/2]
	res := 0
	for i := 0; i < len(arr); i++ {
		if abs(target-arr[i])%x != 0 {
			return -1
		}
		res = res + abs(target-arr[i])/x
	}
	return res
}

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

2034.股票价格波动(2)

• 题目

给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳和该时间点股票对应的 价格。
不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。
如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正前一条错误的记录。
请你设计一个算法，实现：
更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将更正之前的错误价格。
找到当前记录里 最新股票价格。最新股票价格定义为时间戳最晚的股票价格。
找到当前记录里股票的 最高价格。
找到当前记录里股票的 最低价格。
请你实现StockPrice类：
StockPrice()初始化对象，当前无股票价格记录。
void update(int timestamp, int price)在时间点 timestamp更新股票价格为 price。
int current()返回股票 最新价格。
int maximum()返回股票 最高价格。
int minimum()返回股票 最低价格。
示例 1：输入：["StockPrice", "update", "update", "current", "maximum", "update", 
"maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
输出：[null, null, null, 5, 10, null, 5, null, 2]
解释：StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // 时间戳为 [1] ，对应的股票价格为 [10] 。
stockPrice.update(2, 5);  // 时间戳为 [1,2] ，对应的股票价格为 [10,5] 。
stockPrice.current();     // 返回 5 ，最新时间戳为 2 ，对应价格为 5 。
stockPrice.maximum();     // 返回 10 ，最高价格的时间戳为 1 ，价格为 10 。
stockPrice.update(1, 3);  // 之前时间戳为 1 的价格错误，价格更新为 3 。
                          // 时间戳为 [1,2] ，对应股票价格为 [3,5] 。
stockPrice.maximum();     // 返回 5 ，更正后最高价格为 5 。
stockPrice.update(4, 2);  // 时间戳为 [1,2,4] ，对应价格为 [3,5,2] 。
stockPrice.minimum();     // 返回 2 ，最低价格时间戳为 4 ，价格为 2 。
提示：1 <= timestamp, price <= 109
update，current，maximum和minimum总 调用次数不超过105。
current，maximum和minimum被调用时，update操作 至少已经被调用过 一次。

• 解题思路

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

type StockPrice struct {
	*redblacktree.Tree
	m                 map[int]int
	curTime, curPrice int
}

func Constructor() StockPrice {
	return StockPrice{
		Tree: redblacktree.NewWithIntComparator(),
		m:    make(map[int]int),
	}
}

func (this *StockPrice) Update(timestamp int, price int) {
	if v, ok := this.m[timestamp]; ok {
		this.remove(v) // 删除
	}
	this.put(price) // 添加记录
	this.m[timestamp] = price
	if timestamp >= this.curTime { // 更新
		this.curTime, this.curPrice = timestamp, price
	}
}

func (this *StockPrice) put(price int) {
	count := 0
	if v, ok := this.Get(price); ok {
		count = v.(int)
	}
	this.Put(price, count+1)
}

func (this *StockPrice) remove(price int) {
	if v, ok := this.Get(price); ok && v.(int) > 1 {
		this.Put(price, v.(int)-1)
	} else {
		this.Remove(price)
	}
}

func (this *StockPrice) Current() int {
	return this.curPrice
}

func (this *StockPrice) Maximum() int {
	return this.Right().Key.(int)
}

func (this *StockPrice) Minimum() int {
	return this.Left().Key.(int)
}

# 2
type StockPrice struct {
	maxH, minH        *mixHeap
	curTime, curPrice int
	m                 map[int]int
}

func Constructor() StockPrice {
	return StockPrice{
		maxH: &mixHeap{isBig: true},
		minH: &mixHeap{isBig: false},
		m:    make(map[int]int), // 保存最新的时间戳=>价格数据
	}
}

func (this *StockPrice) Update(timestamp int, price int) {
	if timestamp >= this.curTime { // 更新
		this.curTime, this.curPrice = timestamp, price
	}
	this.maxH.push([]int{timestamp, price})
	this.minH.push([]int{timestamp, price})
	this.m[timestamp] = price // 时间戳=>价格
}

func (this *StockPrice) Current() int {
	return this.curPrice
}

func (this *StockPrice) Maximum() int {
	for this.maxH.Len() > 0 {
		top := this.maxH.Top()
		if top[1] == this.m[top[0]] { // 跟map里面的价格对的上，直接返回
			return top[1]
		}
		this.maxH.pop() // 剔除旧数据
	}
	return 0
}

func (this *StockPrice) Minimum() int {
	for this.minH.Len() > 0 {
		top := this.minH.Top()
		if top[1] == this.m[top[0]] { // 跟map里面的价格对的上，直接返回
			return top[1]
		}
		this.minH.pop() // 剔除旧数据
	}
	return 0
}

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][1] > m.arr[j][1]
	}
	return m.arr[i][1] < m.arr[j][1]
}

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
}

2038.如果相邻两个颜色均相同则删除当前颜色(2)

• 题目

总共有 n个颜色片段排成一列，每个颜色片段要么是'A'要么是'B'。
给你一个长度为n的字符串colors，其中colors[i]表示第i个颜色片段的颜色。
Alice 和 Bob 在玩一个游戏，他们 轮流从这个字符串中删除颜色。Alice 先手。
如果一个颜色片段为 'A'且 相邻两个颜色都是颜色 'A'，那么 Alice 可以删除该颜色片段。
Alice不可以删除任何颜色'B'片段。
如果一个颜色片段为 'B'且 相邻两个颜色都是颜色 'B'，那么 Bob 可以删除该颜色片段。
Bob 不可以删除任何颜色 'A'片段。
Alice 和 Bob 不能从字符串两端删除颜色片段。
如果其中一人无法继续操作，则该玩家 输掉游戏且另一玩家 获胜。
假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回true，否则 Bob 获胜，返回false。
示例 1：输入：colors = "AAABABB" 输出：true
解释：AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 'A' ，这也是唯一一个相邻颜色片段都是 'A' 的 'A' 。
现在轮到 Bob 操作。
Bob 无法执行任何操作，因为没有相邻位置都是 'B' 的颜色片段 'B' 。
因此，Alice 获胜，返回 true 。
示例 2：输入：colors = "AA" 输出：false
解释：Alice 先操作。
只有 2 个 'A' 且它们都在字符串的两端，所以她无法执行任何操作。
因此，Bob 获胜，返回 false 。
示例 3：输入：colors = "ABBBBBBBAAA" 输出：false
解释：ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的选择是删除从右数起第二个 'A' 。
ABBBBBBBAA -> ABBBBBBAA
接下来轮到 Bob 操作。
他有许多选择，他可以选择任何一个 'B' 删除。
然后轮到 Alice 操作，她无法删除任何片段。
所以 Bob 获胜，返回 false 。
提示：1 <=colors.length <= 105
colors只包含字母'A'和'B'

• 解题思路

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

func winnerOfGame(colors string) bool {
	arrA := strings.Split(colors, "B")
	arrB := strings.Split(colors, "A")
	countA, countB := 0, 0
	for i := 0; i < len(arrA); i++ {
		if len(arrA[i]) >= 3 {
			countA = countA + len(arrA[i]) - 2
		}
	}
	for i := 0; i < len(arrB); i++ {
		if len(arrB[i]) >= 3 {
			countB = countB + len(arrB[i]) - 2
		}
	}
	if countA > countB {
		return true
	}
	return false
}

# 2
func winnerOfGame(colors string) bool {
	countA := 0
	countB := 0
	if len(colors) <= 2 {
		return false
	}
	for i := 2; i < len(colors); i++ {
		if colors[i-1] == colors[i-2] && colors[i-1] == colors[i] {
			if colors[i] == 'A' {
				countA++
			} else {
				countB++
			}
		}
	}
	if countA > countB {
		return true
	}
	return false
}

2039.网络空闲的时刻(2)

• 题目

给你一个有 n个服务器的计算机网络，服务器编号为0到n - 1。
同时给你一个二维整数数组edges，其中edges[i] = [ui, vi]表示服务器ui 和vi之间有一条信息线路，
在一秒内它们之间可以传输任意数目的信息。再给你一个长度为 n且下标从0开始的整数数组patience。
题目保证所有服务器都是 相通的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。
编号为 0的服务器是 主服务器，其他服务器为 数据服务器。每个数据服务器都要向主服务器发送信息，并等待回复。
信息在服务器之间按 最优线路传输，也就是说每个信息都会以 最少时间到达主服务器。
主服务器会处理 所有新到达的信息并 立即按照每条信息来时的路线 反方向 发送回复信息。
在 0秒的开始，所有数据服务器都会发送各自需要处理的信息。
从第 1秒开始，每一秒最 开始时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：
如果还没收到任何回复信息，那么该服务器会周期性重发信息。数据服务器i每patience[i]秒都会重发一条信息，
也就是说，数据服务器i在上一次发送信息给主服务器后的 patience[i]秒 后会重发一条信息给主服务器。
否则，该数据服务器不会重发信息。
当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲状态。
请返回计算机网络变为 空闲状态的最早秒数。
示例 1：输入：edges = [[0,1],[1,2]], patience = [0,2,1] 输出：8
解释：0 秒最开始时，
- 数据服务器 1 给主服务器发出信息（用 1A 表示）。
- 数据服务器 2 给主服务器发出信息（用 2A 表示）。
1 秒时，
- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。
2 秒时，
- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
- 服务器 2 重发一条信息（用 2C 表示）。
...
4 秒时，
- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
...
7 秒时，回复信息 2D 到达服务器 2 。
从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
所以第 8 秒是网络变空闲的最早时刻。
示例 2：输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10] 输出：3
解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始，网络变空闲。
提示：n == patience.length
2 <= n <= 105
patience[0] == 0
对于1 <= i < n ，满足1 <= patience[i] <= 105
1 <= edges.length <= min(105, n * (n - 1) / 2)
edges[i].length == 2
0 <= ui, vi < n
ui != vi
不会有重边。
每个服务器都直接或间接与别的服务器相连。

• 解题思路

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

func networkBecomesIdle(edges [][]int, patience []int) int {
	maxValue := math.MaxInt32 / 10
	n := len(patience)
	arr := make([][][2]int, n) // 邻接表：i=>j的集合
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1] // a=>b
		arr[a] = append(arr[a], [2]int{b, 1})
		arr[b] = append(arr[b], [2]int{a, 1})
	}
	dis := make([]int, n) // k到其他点的距离
	for i := 0; i < n; i++ {
		dis[i] = maxValue
	}
	dis[0] = 0
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	heap.Push(&intHeap, [2]int{0, 0})
	for intHeap.Len() > 0 {
		node := heap.Pop(&intHeap).([2]int) // 距离起点最近的点
		a := node[0]
		if dis[a] < node[1] { // 大于最短距离，跳过
			continue
		}
		for i := 0; i < len(arr[a]); i++ {
			b, c := arr[a][i][0], arr[a][i][1]
			if dis[a]+c < dis[b] { // 更新距离
				dis[b] = dis[a] + c
				heap.Push(&intHeap, [2]int{b, dis[b]})
			}
		}
	}
	res := 0
	for i := 1; i < n; i++ {
		total := (2*dis[i]-1)/patience[i]*patience[i] + 2*dis[i]
		res = max(res, total)
	}
	return res + 1
}

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

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
}

# 2
func networkBecomesIdle(edges [][]int, patience []int) int {
	n := len(patience)
	arr := make([][]int, n) // 邻接表：i=>j的集合
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1] // a=>b
		arr[a] = append(arr[a], b)
		arr[b] = append(arr[b], a)
	}
	res := 0
	visited := make([]bool, n)
	visited[0] = true
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		a, dis := node[0], node[1]
		if a != 0 {
			total := (2*dis-1)/patience[a]*patience[a] + 2*dis
			res = max(res, total)
		}
		for i := 0; i < len(arr[a]); i++ {
			b := arr[a][i]
			if visited[b] == false {
				queue = append(queue, [2]int{b, dis + 1})
				visited[b] = true
			}
		}
	}
	return res + 1
}

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

2043.简易银行系统(1)

• 题目

你的任务是为一个很受欢迎的银行设计一款程序，以自动化执行所有传入的交易（转账，存款和取款）。
银行共有 n 个账户，编号从 1 到 n 。
每个账号的初始余额存储在一个下标从 0 开始的整数数组 balance中，其中第 (i + 1) 个账户的初始余额是 balance[i] 。
请你执行所有 有效的 交易。如果满足下面全部条件，则交易 有效 ：
指定的账户数量在 1 和 n 之间，且
取款或者转账需要的钱的总数 小于或者等于 账户余额。
实现 Bank 类：
Bank(long[] balance) 使用下标从 0 开始的整数数组 balance 初始化该对象。
boolean transfer(int account1, int account2, long money) 
从编号为account1 的账户向编号为 account2 的账户转帐 money 美元。如果交易成功，返回 true ，否则，返回 false 。
boolean deposit(int account, long money) 向编号为account 的账户存款 money 美元。
如果交易成功，返回 true ；否则，返回 false 。
boolean withdraw(int account, long money) 从编号为 account 的账户取款 money 美元。
如果交易成功，返回 true ；否则，返回 false 。
示例：输入： ["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
输出：[null, true, true, true, false, false]
解释：Bank bank = new Bank([10, 100, 20, 50, 30]);
bank.withdraw(3, 10);    // 返回 true ，账户 3 的余额是 $20 ，所以可以取款 $10 。
                         // 账户 3 余额为 $20 - $10 = $10 。
bank.transfer(5, 1, 20); // 返回 true ，账户 5 的余额是 $30 ，所以可以转账 $20 。
                         // 账户 5 的余额为 $30 - $20 = $10 ，账户 1 的余额为 $10 + $20 = $30 。
bank.deposit(5, 20);     // 返回 true ，可以向账户 5 存款 $20 。
                         // 账户 5 的余额为 $10 + $20 = $30 。
bank.transfer(3, 4, 15); // 返回 false ，账户 3 的当前余额是 $10 。
                         // 所以无法转账 $15 。
bank.withdraw(10, 50);   // 返回 false ，交易无效，因为账户 10 并不存在。
提示：n == balance.length
1 <= n, account, account1, account2 <= 105
0 <= balance[i], money <= 1012
transfer, deposit, withdraw 三个函数，每个 最多调用 104 次

• 解题思路

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

type Bank struct {
	arr []int64
	n   int
}

func Constructor(balance []int64) Bank {
	return Bank{arr: balance, n: len(balance)}
}

func (this *Bank) Transfer(account1 int, account2 int, money int64) bool {
	if account1 > this.n || account2 > this.n || this.arr[account1-1] < money {
		return false
	}
	this.arr[account1-1] = this.arr[account1-1] - money
	this.arr[account2-1] = this.arr[account2-1] + money
	return true
}

func (this *Bank) Deposit(account int, money int64) bool {
	if account > this.n {
		return false
	}
	this.arr[account-1] = this.arr[account-1] + money
	return true
}

func (this *Bank) Withdraw(account int, money int64) bool {
	if account > this.n || this.arr[account-1] < money {
		return false
	}
	this.arr[account-1] = this.arr[account-1] - money
	return true
}

2044.统计按位或能得到最大值的子集数目(4)

• 题目

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。
如果选中的元素下标位置不一样，则认为两个子集 不同 。
对数组 a 执行 按位或，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。
示例 1：输入：nums = [3,1] 输出：2
解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：
- [3]
- [3,1]
示例 2：输入：nums = [2,2,2] 输出：7
解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。
示例 3：输入：nums = [3,2,1,5] 输出：6
解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]
提示：1 <= nums.length <= 16
1 <= nums[i] <= 105

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	子集	O(3^n)	O(2^n)
02	子集	O(n*2^n)	O(2^n)
03	子集	O(n*2^n)	O(1)
04	递归	O(2^n)	O(1)

func countMaxOrSubsets(nums []int) int {
	n := len(nums)
	total := 1 << n
	sum := make([]int, total)
	for i := 0; i < n; i++ { // 每次添加1个
		count := 1 << i
		for j := 0; j < count; j++ {
			sum[count|j] = sum[j] | nums[i] // 按位或运算：j前面补1=>子集和加上tasks[i]
		}
	}
	maxValue := 0
	for i := 0; i < total; i++ {
		maxValue = max(maxValue, sum[i])
	}
	res := 0
	for i := 0; i < total; i++ {
		if sum[i] == maxValue {
			res++
		}
	}
	return res
}

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

# 2
func countMaxOrSubsets(nums []int) int {
	n := len(nums)
	total := 1 << n
	sum := make([]int, total)
	for i := 0; i < total; i++ { // 枚举状态
		for j := 0; j < n; j++ { // 枚举该位
			if (i & (1 << j)) > 0 {
				sum[i] = sum[i] | nums[j]
			}
		}
	}
	maxValue := 0
	for i := 0; i < total; i++ {
		maxValue = max(maxValue, sum[i])
	}
	res := 0
	for i := 0; i < total; i++ {
		if sum[i] == maxValue {
			res++
		}
	}
	return res
}

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

# 3
func countMaxOrSubsets(nums []int) int {
	n := len(nums)
	total := 1 << n
	maxValue := 0
	res := 0
	for i := 0; i < total; i++ { // 枚举状态
		value := 0
		for j := 0; j < n; j++ { // 枚举该位
			if (i & (1 << j)) > 0 {
				value = value | nums[j]
			}
		}
		if value > maxValue {
			maxValue = value
			res = 1
		} else if value == maxValue {
			res++
		}
	}
	return res
}

# 4
var maxValue int
var res int

func countMaxOrSubsets(nums []int) int {
	n := len(nums)
	maxValue = 0
	res = 0
	for i := 0; i < n; i++ {
		maxValue = maxValue | nums[i]
	}
	dfs(nums, 0, 0)
	return res
}

func dfs(nums []int, index, sum int) {
	if index == len(nums) {
		if sum == maxValue {
			res++
		}
		return
	}
	dfs(nums, index+1, sum)
	dfs(nums, index+1, sum|nums[index])
}

2048.下一个更大的数值平衡数(2)

• 题目

如果整数 x 满足：对于每个数位d ，这个数位恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。
给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。
示例 1：输入：n = 1 输出：22
解释：22 是一个数值平衡数，因为：
- 数字 2 出现 2 次 
这也是严格大于 1 的最小数值平衡数。
示例 2：输入：n = 1000 输出：1333
解释：1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。
示例 3：输入：n = 3000 输出：3133
解释：3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 3000 的最小数值平衡数。
提示：0 <= n <= 106

• 解题思路

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

func nextBeautifulNumber(n int) int {
	for i := n + 1; ; i++ {
		if judge(i) == true {
			return i
		}
	}
}

func judge(a int) bool {
	s := strconv.Itoa(a)
	m := make(map[int]int)
	for i := 0; i < len(s); i++ {
		m[int(s[i]-'0')]++
	}
	for k, v := range m {
		if k != v {
			return false
		}
	}
	return true
}

2049.统计最高分的节点数目(3)

• 题目

给你一棵根节点为 0 的二叉树，它总共有 n个节点，节点编号为0到n - 1。
同时给你一个下标从0开始的整数数组parents表示这棵树，其中parents[i]是节点 i的父节点。
由于节点 0是根，所以parents[0] == -1。
一个子树的 大小为这个子树内节点的数目。每个节点都有一个与之关联的分数。
求出某个节点分数的方法是，将这个节点和与它相连的边全部 删除，剩余部分是若干个 非空子树，
这个节点的 分数为所有这些子树 大小的乘积。
请你返回有 最高得分节点的 数目。
示例1:输入：parents = [-1,2,0,2,0] 输出：3
解释：- 节点 0 的分数为：3 * 1 = 3
- 节点 1 的分数为：4 = 4
- 节点 2 的分数为：1 * 1 * 2 = 2
- 节点 3 的分数为：4 = 4
- 节点 4 的分数为：4 = 4
最高得分为 4 ，有三个节点得分为 4 （分别是节点 1，3 和 4 ）。
示例 2：输入：parents = [-1,2,0]
输出：2
解释：
- 节点 0 的分数为：2 = 2
- 节点 1 的分数为：2 = 2
- 节点 2 的分数为：1 * 1 = 1
最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。
提示：n == parents.length
2 <= n <= 105
parents[0] == -1
对于i != 0，有0 <= parents[i] <= n - 1
parents表示一棵二叉树。

• 解题思路

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

var arr [][]int
var sum []int

func countHighestScoreNodes(parents []int) int {
	res := 0
	maxValue := 0
	n := len(parents)
	sum = make([]int, n)
	arr = make([][]int, n)
	for i := 1; i < n; i++ { // 邻接表
		a, b := i, parents[i] // b=>a
		arr[b] = append(arr[b], a)
	}
	dfs(0)                   // 先统计
	for i := 0; i < n; i++ { // 后计算
		value := 1
		for j := 0; j < len(arr[i]); j++ { // 计算左右子树乘积
			if sum[arr[i][j]] > 0 {
				value = value * sum[arr[i][j]]
			}
		}
		if parents[i] != -1 { // 计算去掉以根节点位i的剩余部分
			if sum[parents[i]]-sum[i] > 0 {
				value = value * (sum[0] - sum[i]) // 根节点总数-节点i总数
			}
		}
		if value > maxValue {
			maxValue = value
			res = 1
		} else if value == maxValue {
			res++
		}
	}
	return res
}

func dfs(root int) int {
	count := 1
	for i := 0; i < len(arr[root]); i++ {
		count = count + dfs(arr[root][i])
	}
	sum[root] = count
	return count
}

# 2
var arr [][]int
var n int
var maxValue int
var res int

func countHighestScoreNodes(parents []int) int {
	res = 0
	maxValue = 1
	n = len(parents)
	arr = make([][]int, n)
	for i := 1; i < n; i++ { // 邻接表
		a, b := i, parents[i] // b=>a
		arr[b] = append(arr[b], a)
	}
	dfs(0)
	return res
}

func dfs(root int) int {
	count := 1
	value := 1
	for i := 0; i < len(arr[root]); i++ { // 计算左右子树乘积
		size := dfs(arr[root][i])
		count = count + size
		value = value * size
	}
	if root > 0 { // 计算去掉以根节点位i的剩余部分
		value = value * (n - count)
	}
	if value > maxValue {
		maxValue = value
		res = 1
	} else if value == maxValue {
		res++
	}
	return count
}

# 3
var n int
var maxValue int
var res int
var left, right []int

func countHighestScoreNodes(parents []int) int {
	res = 0
	maxValue = 1
	n = len(parents)
	left, right = make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		left[i], right[i] = -1, -1
	}
	for i := 1; i < n; i++ { // 建立左右子树关系
		a, b := i, parents[i] // b=>a
		if left[b] == -1 {    // 优先放在左子树
			left[b] = a
		} else {
			right[b] = a
		}
	}
	dfs(0)
	return res
}

func dfs(root int) int {
	if root == -1 {
		return 0
	}
	a, b := dfs(left[root]), dfs(right[root])
	value := max(a, 1) * max(b, 1) * max(n-a-b-1, 1)
	if value > maxValue {
		maxValue = value
		res = 1
	} else if value == maxValue {
		res++
	}
	return a + b + 1 // 左子树+右子树+1
}

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

2054.两个最好的不重叠活动(2)

• 题目

给你一个下标从 0开始的二维整数数组events，其中events[i] = [startTimei, endTimei, valuei]。
第i个活动开始于startTimei，结束于endTimei，如果你参加这个活动，那么你可以得到价值valuei。
你 最多可以参加两个时间不重叠活动，使得它们的价值之和 最大。
请你返回价值之和的 最大值。
注意，活动的开始时间和结束时间是 包括在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。
更具体的，如果你参加一个活动，且结束时间为 t，那么下一个活动必须在t + 1或之后的时间开始。
示例 1:输入：events = [[1,3,2],[4,5,2],[2,4,3]] 输出：4
解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。
示例 2：输入：events = [[1,3,2],[4,5,2],[1,5,5]] 输出：5
解释：选择活动 2 ，价值和为 5 。
示例 3：输入：events = [[1,5,3],[1,5,1],[6,6,5]] 输出：8
解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。
提示：2 <= events.length <= 105
events[i].length == 3
1 <= startTimei <= endTimei <= 109
1 <= valuei <= 106

• 解题思路

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

func maxTwoEvents(events [][]int) int {
	res := 0
	sort.Slice(events, func(i, j int) bool {
		return events[i][0] < events[j][0]
	})
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	prevMaxValue := 0
	for i := 0; i < len(events); i++ {
		a, b, c := events[i][0], events[i][1], events[i][2]
		for intHeap.Len() > 0 && intHeap[0][1] < a { // 之前的结束时间 小于 当前的开始时间
			value := heap.Pop(&intHeap).([3]int)[2] // 小根堆取值：按结束时间从小到大
			prevMaxValue = max(prevMaxValue, value) // 更新之前最大值
		}
		res = max(res, prevMaxValue+c)
		heap.Push(&intHeap, [3]int{a, b, c})
	}
	return res
}

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][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.([3]int)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

# 2
func maxTwoEvents(events [][]int) int {
	arr := make([][3]int, 0)
	for i := 0; i < len(events); i++ {
		a, b, c := events[i][0], events[i][1], events[i][2]
		arr = append(arr, [3]int{a, 0, c})
		arr = append(arr, [3]int{b, 1, c}) // 拆分为2块
	}
	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]
	})
	res := 0
	prevMaxValue := 0
	for i := 0; i < len(arr); i++ {
		if arr[i][1] == 0 { // 为开始时间
			res = max(res, arr[i][2]+prevMaxValue)
		} else {
			prevMaxValue = max(prevMaxValue, arr[i][2]) // 更新之前最大值
		}
	}
	return res
}

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

2055.蜡烛之间的盘子(2)

• 题目

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0开始的字符串s，
它只包含字符'*' 和'|'，其中'*'表示一个 盘子，'|'表示一支蜡烛。
同时给你一个下标从 0开始的二维整数数组queries，
其中queries[i] = [lefti, righti]表示 子字符串s[lefti...righti]（包含左右端点的字符）。
对于每个查询，你需要找到 子字符串中在 两支蜡烛之间的盘子的 数目。
如果一个盘子在 子字符串中左边和右边 都至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间。
比方说，s = "||**||**|*"，查询[3, 8]，表示的是子字符串"*||**|"。
子字符串中在两支蜡烛之间的盘子数目为2，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。
请你返回一个整数数组answer，其中answer[i]是第i个查询的答案。
示例 1:输入：s = "**|**|***|", queries = [[2,5],[5,9]] 输出：[2,3]
解释：- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。
示例 2:输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]] 输出：[9,0,0,0,0]
解释：- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。
提示：3 <= s.length <= 105
s只包含字符'*' 和'|'。
1 <= queries.length <= 105
queries[i].length == 2
0 <= lefti <= righti < s.length

• 解题思路

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

func platesBetweenCandles(s string, queries [][]int) []int {
	n := len(s)
	res := make([]int, len(queries))
	sum := make([]int, n+1)
	left, right := make([]int, n), make([]int, n)
	prev := -1
	for i := 0; i < n; i++ {
		sum[i+1] = sum[i]
		if s[i] == '|' { // 蜡烛
			prev = i
		} else {
			sum[i+1]++
		}
		left[i] = prev
	}
	prev = n
	for i := n - 1; i >= 0; i-- {
		if s[i] == '|' { // 蜡烛
			prev = i
		}
		right[i] = prev
	}
	for i := 0; i < len(queries); i++ {
		a, b := right[queries[i][0]], left[queries[i][1]] // 位子：右边第一个蜡烛，左边第一个蜡烛
		if a < b {                                        // 满足的条件下
			res[i] = sum[b] - sum[a]
		}
	}
	return res
}

# 2
func platesBetweenCandles(s string, queries [][]int) []int {
	n := len(s)
	res := make([]int, len(queries))
	arr := make([]int, 0)
	for i := 0; i < n; i++ {
		if s[i] == '|' { // 盘子
			arr = append(arr, i)
		}
	}
	for i := 0; i < len(queries); i++ {
		a, b := queries[i][0], queries[i][1]
		l := sort.SearchInts(arr, a)
		r := sort.SearchInts(arr, b)
		if r == len(arr) || arr[r] != b { // r超出范围或者找到的下标不是目标数
			r--
		}
		if l < r {
			res[i] = arr[r] - arr[l] - (r - l) // 总个数-盘子个数
		}
	}
	return res
}

2058.找出临界点之间的最小和最大距离(2)

• 题目

链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。
如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。
如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。
注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。
给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，
其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。
如果临界点少于两个，则返回 [-1，-1] 。
示例 1：输入：head = [3,1] 输出：[-1,-1]
解释：链表 [3,1] 中不存在临界点。
示例 2：输入：head = [5,3,1,2,5,1,2] 输出：[1,3]
解释：存在三个临界点：
- [5,3,1,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。
- [5,3,1,2,5,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。
- [5,3,1,2,5,1,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。
第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。
第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。
示例 3：输入：head = [1,3,2,2,3,2,2,2,7] 输出：[3,3]
解释：存在两个临界点：
- [1,3,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。
- [1,3,2,2,3,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。
最小和最大距离都存在于第二个节点和第五个节点之间。
因此，minDistance 和 maxDistance 是 5 - 2 = 3 。
注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。
示例 4：输入：head = [2,3,3,2] 输出：[-1,-1]
解释：链表 [2,3,3,2] 中不存在临界点。
提示：链表中节点的数量在范围 [2, 105] 内
1 <= Node.val <= 105

• 解题思路

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

func nodesBetweenCriticalPoints(head *ListNode) []int {
	a, b, c := head, head.Next, head.Next.Next // 题目保证数量范围>=2
	maxDis, minDis := math.MinInt32, math.MaxInt32
	index := 1
	prev := 0  // 前一个位置
	first := 0 // 第一个位置
	for c != nil {
		if (a.Val < b.Val && b.Val > c.Val) ||
			(a.Val > b.Val && b.Val < c.Val) {
			if first == 0 {
				first = index // 第一次出现
			}
			maxDis = max(maxDis, index-first) // 当前位置减去第一次位置
			if 0 < prev {
				minDis = min(minDis, index-prev) // 当前位置减去前一次位置
			}
			prev = index
		}
		a, b, c = b, c, c.Next
		index++
	}
	if minDis == math.MaxInt32 {
		return []int{-1, -1}
	}
	return []int{minDis, maxDis}
}

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

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

# 2
func nodesBetweenCriticalPoints(head *ListNode) []int {
	a, b, c := head, head.Next, head.Next.Next // 题目保证数量范围>=2
	arr := make([]int, 0)
	index := 1
	for c != nil {
		if (a.Val < b.Val && b.Val > c.Val) ||
			(a.Val > b.Val && b.Val < c.Val) {
			arr = append(arr, index)
		}
		a, b, c = b, c, c.Next
		index++
	}
	if len(arr) < 2 {
		return []int{-1, -1}
	}
	minDis := math.MaxInt32
	for i := 0; i < len(arr)-1; i++ {
		minDis = min(minDis, arr[i+1]-arr[i])
	}
	return []int{minDis, arr[len(arr)-1] - arr[0]}
}

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

2059.转化数字的最小运算数(1)

• 题目

给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。
整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算：
如果 0 <= x <= 1000 ，那么，对于数组中的任一下标 i（0 <= i < nums.length），可以将 x 设为下述任一值：
x + nums[i]
x - nums[i]
x ^ nums[i]（按位异或 XOR）
注意，你可以按任意顺序使用每个 nums[i] 任意次。使 x 越过 0 <= x <= 1000 范围的运算同样可以生效，
但该该运算执行后将不能执行其他运算。
返回将 x = start 转化为 goal 的最小操作数；如果无法完成转化，则返回 -1 。
示例 1：输入：nums = [1,3], start = 6, goal = 4 输出：2
解释：可以按 6 → 7 → 4 的转化路径进行，只需执行下述 2 次运算：
- 6 ^ 1 = 7
- 7 ^ 3 = 4
示例 2：输入：nums = [2,4,12], start = 2, goal = 12 输出：2
解释：可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算：
- 2 + 12 = 14
- 14 - 2 = 12
示例 3：输入：nums = [3,5,7], start = 0, goal = -4 输出：2
解释：可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算：
- 0 + 3 = 3
- 3 - 7 = -4
注意，最后一步运算使 x 超过范围 0 <= x <= 1000 ，但该运算仍然可以生效。
示例 4：输入：nums = [2,8,16], start = 0, goal = 1 输出：-1
解释：无法将 0 转化为 1
示例 5：输入：nums = [1], start = 0, goal = 3 输出：3
解释：可以按 0 → 1 → 2 → 3 的转化路径进行，只需执行下述 3 次运算：
- 0 + 1 = 1 
- 1 + 1 = 2
- 2 + 1 = 3
提示：1 <= nums.length <= 1000
-109 <= nums[i], goal <= 109
0 <= start <= 1000
start != goal
nums 中的所有整数互不相同

• 解题思路

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

func minimumOperations(nums []int, start int, goal int) int {
	m := make(map[int]bool)
	m[start] = true
	queue := make([]int, 0)
	queue = append(queue, start)
	count := 1
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			for j := 0; j < len(nums); j++ {
				temp := []int{queue[i] + nums[j], queue[i] - nums[j], queue[i] ^ nums[j]}
				for k := 0; k < len(temp); k++ {
					if temp[k] == goal {
						return count
					}
					if 0 <= temp[k] && temp[k] <= 1000 && m[temp[k]] == false {
						m[temp[k]] = true
						queue = append(queue, temp[k])
					}
				}
			}
		}
		count++
		queue = queue[length:]
	}
	return -1
}

2063.所有子字符串中的元音(1)

• 题目

给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。
子字符串 是字符串中一个连续（非空）的字符序列。
注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。
示例 1：输入：word = "aba" 输出：6
解释：所有子字符串是："a"、"ab"、"aba"、"b"、"ba" 和 "a" 。
- "b" 中有 0 个元音
- "a"、"ab"、"ba" 和 "a" 每个都有 1 个元音
- "aba" 中有 2 个元音
因此，元音总数 = 0 + 1 + 1 + 1 + 1 + 2 = 6 。
示例 2：输入：word = "abc" 输出：3
解释：所有子字符串是："a"、"ab"、"abc"、"b"、"bc" 和 "c" 。
- "a"、"ab" 和 "abc" 每个都有 1 个元音
- "b"、"bc" 和 "c" 每个都有 0 个元音
因此，元音总数 = 1 + 1 + 1 + 0 + 0 + 0 = 3 。
示例 3：输入：word = "ltcd" 输出：0
解释："ltcd" 的子字符串均不含元音。
示例 4：输入：word = "noosabasboosa" 输出：237
解释：所有子字符串中共有 237 个元音。
提示：1 <= word.length <= 105
word 由小写英文字母组成

• 解题思路

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

var m = map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}

func countVowels(word string) int64 {
	n := len(word)
	res := int64(0)
	for i := 0; i < n; i++ {
		if m[word[i]] == true {
			// 计算当前字符出现在多少种组合里面
			// 总数：left * right
			res = res + int64(i+1)*int64(n-i) // 左边个数（包含当前）*右边个数
		}
	}
	return res
}

2064.分配给商店的最多商品的最小值(2)

• 题目

给你一个整数n，表示有n间零售商店。总共有m种产品，每种产品的数目用一个下标从 0开始的整数数组quantities表示，
其中quantities[i]表示第i种商品的数目。
你需要将 所有商品分配到零售商店，并遵守这些规则：
一间商店 至多只能有 一种商品 ，但一间商店拥有的商品数目可以为任意件。
分配后，每间商店都会被分配一定数目的商品（可能为 0件）。
用x表示所有商店中分配商品数目的最大值，你希望 x越小越好。也就是说，你想 最小化分配给任意商店商品数目的 最大值。
请你返回最小的可能的x。
示例 1：输入：n = 6, quantities = [11,6] 输出：3
解释： 一种最优方案为：
- 11 件种类为 0 的商品被分配到前 4 间商店，分配数目分别为：2，3，3，3 。
- 6 件种类为 1 的商品被分配到另外 2 间商店，分配数目分别为：3，3 。
分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。
示例 2：输入：n = 7, quantities = [15,10,10] 输出：5
解释：一种最优方案为：
- 15 件种类为 0 的商品被分配到前 3 间商店，分配数目为：5，5，5 。
- 10 件种类为 1 的商品被分配到接下来 2 间商店，数目为：5，5 。
- 10 件种类为 2 的商品被分配到最后 2 间商店，数目为：5，5 。
分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) = 5 。
示例 3：输入：n = 1, quantities = [100000] 输出：100000
解释：唯一一种最优方案为：
- 所有 100000 件商品 0 都分配到唯一的商店中。
分配给所有商店的最大商品数目为 max(100000) = 100000 。
提示：m == quantities.length
1 <= m <= n <= 105
1 <= quantities[i] <= 105

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(nlog(n))	O(1)
02	二分查找+内置函数	O(nlog(n))	O(1)

func minimizedMaximum(n int, quantities []int) int {
	left,right := 1, 100000
	for left < right{
		mid := left+(right-left)/2
		if judge(quantities, mid) <=n {
			right = mid
		}else {
			left = mid+1
		}
	}
	return left
}

func judge( quantities []int, per int)int  {
	res := 0
	for i := 0; i < len(quantities); i++{
		res = res + quantities[i]/per
		if quantities[i]%per !=0{
			res++
		}
	}
	return res
}

# 2
func minimizedMaximum(n int, quantities []int) int {
	return sort.Search(100000, func(i int) bool {
		return judge(quantities, i) <= n
	})
}

func judge(quantities []int, per int) int {
	if per == 0 { // 注意除0错误
		return math.MaxInt32
	}
	res := 0
	for i := 0; i < len(quantities); i++ {
		// res = res + (quantities[i]+per-1)/per
		res = res + quantities[i]/per
		if quantities[i]%per != 0 {
			res++
		}
	}
	return res
}

2069.模拟行走机器人II(2)

• 题目

给你一个在 XY 平面上的width x height的网格图，左下角的格子为(0, 0)，右上角的格子为(width - 1, height - 1)。
网格图中相邻格子为四个基本方向之一（"North"，"East"，"South"和"West"）。
一个机器人 初始在格子(0, 0)，方向为"East"。
机器人可以根据指令移动指定的 步数。每一步，它可以执行以下操作。
沿着当前方向尝试 往前一步。
如果机器人下一步将到达的格子 超出了边界，机器人会 逆时针转 90 度，然后再尝试往前一步。
如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。
请你实现Robot类：
Robot(int width, int height)初始化一个width x height的网格图，机器人初始在(0, 0)，方向朝"East"。
void move(int num)给机器人下达前进num步的指令。
int[] getPos()返回机器人当前所处的格子位置，用一个长度为 2 的数组[x, y]表示。
String getDir()返回当前机器人的朝向，为"North"，"East"，"South"或者"West"。
示例 1：输入：["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]
解释：Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.move(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.move(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.move(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.move(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.move(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"
提示：2 <= width, height <= 100
1 <= num <= 105
move，getPos和getDir总共调用次数不超过104次。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	模拟	O(n)	O(1)
02	预处理	O(n)	O(n)

var m = map[int]string{0: "East", 1: "North", 2: "West", 3: "South"}
var dx = []int{1, 0, -1, 0}
var dy = []int{0, 1, 0, -1}

type Robot struct {
	w, h, x, y, dir, total int
}

func Constructor(width int, height int) Robot {
	return Robot{w: width, h: height, total: 2*width + 2*height - 4}
}

func (this *Robot) Step(num int) {
	num = num % this.total
	if num == 0 && this.x == 0 && this.y == 0 && this.dir == 0 {
		this.dir = 3 // 注意特判
	}
	for ; num > 0; num-- {
		newX, newY := this.x+dx[this.dir], this.y+dy[this.dir]
		if 0 <= newX && newX < this.w && 0 <= newY && newY < this.h {
			this.x = newX
			this.y = newY
		} else {
			this.dir = (this.dir + 1) % 4
			this.x = this.x + dx[this.dir]
			this.y = this.y + dy[this.dir]
		}
	}
}

func (this *Robot) GetPos() []int {
	return []int{this.x, this.y}
}

func (this *Robot) GetDir() string {
	return m[this.dir%4]
}

# 2
var m = map[int]string{0: "East", 1: "North", 2: "West", 3: "South"}

type Robot struct {
	arr    [][2]int
	dir    []int
	isMove bool
	index  int
}

func Constructor(width int, height int) Robot {
	arr := make([][2]int, 0)
	dir := make([]int, 0)
	for i := 0; i < width; i++ {
		arr = append(arr, [2]int{i, 0})
		dir = append(dir, 0)
	}
	for i := 1; i < height; i++ {
		arr = append(arr, [2]int{width - 1, i})
		dir = append(dir, 1)
	}
	for i := width - 2; i >= 0; i-- {
		arr = append(arr, [2]int{i, height - 1})
		dir = append(dir, 2)
	}
	for i := height - 2; i > 0; i-- {
		arr = append(arr, [2]int{0, i})
		dir = append(dir, 3)
	}
	dir[0] = 3 // 第0个朝南
	return Robot{arr: arr, dir: dir, isMove: false}
}

func (this *Robot) Step(num int) {
	this.isMove = true
	this.index = (this.index + num) % len(this.arr)
}

func (this *Robot) GetPos() []int {
	return []int{this.arr[this.index][0], this.arr[this.index][1]}
}

func (this *Robot) GetDir() string {
	if this.isMove == false {
		return "East"
	}
	return m[this.dir[this.index]]
}

2070.每一个查询的最大美丽值(2)

• 题目

给你一个二维整数数组items，其中items[i] = [pricei, beautyi]分别表示每一个物品的 价格和 美丽值。
同时给你一个下标从 0开始的整数数组queries。对于每个查询queries[j]，
你想求出价格小于等于queries[j]的物品中，最大的美丽值是多少。如果不存在符合条件的物品，那么查询的结果为0。
请你返回一个长度与 queries相同的数组answer，其中answer[j]是第j个查询的答案。
示例 1：输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6] 输出：[2,4,5,5,6,6]
解释：
- queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。
- queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。
  它们中的最大美丽值为 4 。
- queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。
  它们中的最大美丽值为 5 。
- queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。
  所以，答案为所有物品中的最大美丽值，为 6 。
示例 2：输入：items = [[1,2],[1,2],[1,3],[1,4]], queries = [1] 输出：[4]
解释：每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。
注意，多个物品可能有相同的价格和美丽值。
示例 3：输入：items = [[10,1000]], queries = [5] 输出：[0]
解释：没有物品的价格小于等于 5 ，所以没有物品可以选择。
因此，查询的结果为 0 。
提示：1 <= items.length, queries.length <= 105
items[i].length == 2
1 <= pricei, beautyi, queries[j] <= 109

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+二分查找	O(nlog(n))	O(1)
02	排序+双指针	O(nlog(n))	O(n)

func maximumBeauty(items [][]int, queries []int) []int {
	n := len(queries)
	m := len(items)
	res := make([]int, n)
	sort.Slice(items, func(i, j int) bool {
		return items[i][0] < items[j][0]
	})
	for i := 1; i < m; i++ {
		items[i][1] = max(items[i][1], items[i-1][1]) // 更新最大美丽值
	}
	for i := 0; i < n; i++ {
		if queries[i] >= items[m-1][0] {
			res[i] = items[m-1][1]
			continue
		}
		if queries[i] < items[0][0] {
			continue
		}
		index := binSearch(items, queries[i]) // 二分查找
		res[i] = items[index][1]
	}
	return res
}

func binSearch(arr [][]int, target int) int {
	left := 0
	right := len(arr)
	for left < right {
		mid := left + (right-left)/2
		if arr[mid][0] == target {
			left = mid + 1
		} else if arr[mid][0] < target {
			left = mid + 1
		} else if arr[mid][0] > target {
			right = mid
		}
	}
	return left - 1
}

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

# 2
func maximumBeauty(items [][]int, queries []int) []int {
	n := len(queries)
	m := len(items)
	res := make([]int, n)
	sort.Slice(items, func(i, j int) bool {
		return items[i][0] < items[j][0]
	})
	arr := make([][2]int, n)
	for i := 0; i < n; i++ {
		arr[i] = [2]int{i, queries[i]}
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][1] < arr[j][1]
	})
	j := 0
	maxValue := 0
	for i := 0; i < n; i++ {
		index, target := arr[i][0], arr[i][1]
		for ; j < m && items[j][0] <= target; j++ {
			maxValue = max(maxValue, items[j][1])
		}
		res[index] = maxValue
	}
	return res
}

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

2074.反转偶数长度组的节点(3)

• 题目

给你一个链表的头节点 head 。
链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。
一个组的 长度 就是组中分配到的节点数目。换句话说：
节点 1 分配给第一组
节点 2 和 3 分配给第二组
节点 4、5 和 6 分配给第三组，以此类推
注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。
示例 1：输入：head = [5,2,6,3,9,1,7,3,8,4] 输出：[5,6,2,3,9,1,4,8,3,7]
解释：- 第一组长度为 1 ，奇数，没有发生反转。
- 第二组长度为 2 ，偶数，节点反转。
- 第三组长度为 3 ，奇数，没有发生反转。
- 最后一组长度为 4 ，偶数，节点反转。
示例 2：输入：head = [1,1,0,6] 输出：[1,0,1,6]
解释：- 第一组长度为 1 ，没有发生反转。
- 第二组长度为 2 ，节点反转。
- 最后一组长度为 1 ，没有发生反转。
示例 3：输入：head = [2,1] 输出：[2,1]
解释：- 第一组长度为 1 ，没有发生反转。
- 最后一组长度为 1 ，没有发生反转。
示例 4：输入：head = [8] 输出：[8]
解释：只有一个长度为 1 的组，没有发生反转。
提示：链表中节点数目范围是 [1, 105]
0 <= Node.val <= 105

• 解题思路

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

func reverseEvenLengthGroups(head *ListNode) *ListNode {
	arr := make([]int, 0)
	for head != nil {
		arr = append(arr, head.Val)
		head = head.Next
	}
	start := 1
	count := 2
	for start < len(arr) {
		end := start + count - 1 // 计算结尾下标
		if end >= len(arr) {
			end = len(arr) - 1
		}
		if (start-end+1)%2 == 0 { // 偶数个才反转
			reverse(arr, start, end) // 反转
		}
		start = start + count
		count = count + 1
	}
	temp := &ListNode{}
	node := temp
	for i := 0; i < len(arr); i++ {
		node.Next = &ListNode{Val: arr[i]}
		node = node.Next
	}
	return temp.Next
}

func reverse(arr []int, start, end int) {
	for start < end {
		arr[start], arr[end] = arr[end], arr[start]
		start++
		end--
	}
}

# 2
func reverseEvenLengthGroups(head *ListNode) *ListNode {
	count := 1
	arr := make([]*ListNode, 0)
	for cur := head; cur != nil; cur = cur.Next {
		arr = append(arr, cur)
		if len(arr) == count || cur.Next == nil {
			if len(arr)%2 == 0 {
				for i := 0; i < len(arr)/2; i++ { // 交换值
					arr[i].Val, arr[len(arr)-1-i].Val = arr[len(arr)-1-i].Val, arr[i].Val
				}
			}
			arr = make([]*ListNode, 0)
			count++
		}
	}
	return head
}

# 3
func reverseEvenLengthGroups(head *ListNode) *ListNode {
	count := 1
	cur := head
	prev := &ListNode{}
	for cur != nil {
		c := 0
		temp := cur
		for c < count && temp != nil {
			c++
			temp = temp.Next
		}
		if c%2 == 1 {
			for i := 0; i < c; i++ {
				prev, cur = cur, cur.Next // 指针后移
			}
		} else { // 反转链表
			for i := 0; i < c-1; i++ {
				prev.Next, cur.Next.Next, cur.Next = cur.Next, prev.Next, cur.Next.Next
			}
			prev, cur = cur, cur.Next
		}
		count++
	}
	return head
}

2075.解码斜向换位密码(1)

• 题目

字符串 originalText 使用 斜向换位密码 ，经由 行数固定 为 rows 的矩阵辅助，加密得到一个字符串 encodedText 。
originalText 先按从左上到右下的方式放置到矩阵中。
先填充蓝色单元格，接着是红色单元格，然后是黄色单元格，以此类推，直到到达 originalText 末尾。
箭头指示顺序即为单元格填充顺序。所有空单元格用 ' ' 进行填充。矩阵的列数需满足：用 originalText 填充之后，最右侧列 不为空 。
接着按行将字符附加到矩阵中，构造encodedText 。
先把蓝色单元格中的字符附加到 encodedText 中，接着是红色单元格，最后是黄色单元格。箭头指示单元格访问顺序。
例如，如果 originalText = "cipher" 且 rows = 3 ，那么我们可以按下述方法将其编码：
蓝色箭头标识 originalText 是如何放入矩阵中的，红色箭头标识形成 encodedText 的顺序。
在上述例子中，encodedText = "ch ie pr" 。
给你编码后的字符串 encodedText 和矩阵的行数 rows ，返回源字符串 originalText 。
注意：originalText 不 含任何尾随空格 ' ' 。生成的测试用例满足 仅存在一个 可能的 originalText 。
示例 1：输入：encodedText = "ch   ie   pr", rows = 3 输出："cipher"
解释：此示例与问题描述中的例子相同。
示例 2：输入：encodedText = "iveo    eed   l te   olc", rows = 4 输出："i love leetcode"
解释：上图标识用于编码 originalText 的矩阵。 
蓝色箭头展示如何从 encodedText 找到 originalText 。
示例 3：输入：encodedText = "coding", rows = 1 输出："coding"
解释：由于只有 1 行，所以 originalText 和 encodedText 是相同的。
示例 4：输入：encodedText = " b  ac", rows = 2 输出：" abc"
解释：originalText 不能含尾随空格，但它可能会有一个或者多个前置空格。
提示：0 <= encodedText.length <= 106
encodedText 仅由小写英文字母和 ' ' 组成
encodedText 是对某个 不含 尾随空格的 originalText 的一个有效编码
1 <= rows <= 1000
生成的测试用例满足 仅存在一个 可能的 originalText

• 解题思路

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

func decodeCiphertext(encodedText string, rows int) string {
	a, b := rows, len(encodedText)/rows
	res := make([]byte, 0)
	for i := 0; i < b; i++ {
		x, y := 0, i
		for x < a && y < b {
			res = append(res, encodedText[x*b+y])
			x++
			y++
		}
	}
	return strings.TrimRight(string(res), " ")
}

2079.给植物浇水(1)

• 题目

你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。
其中，第 i 株植物的位置是 x = i 。x = -1处有一条河，你可以在那里重新灌满你的水罐。
每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：
按从左到右的顺序给植物浇水。
在给当前植物浇完水之后，如果你没有足够的水 完全 浇灌下一株植物，那么你就需要返回河边重新装满水罐。
你 不能 提前重新灌满水罐。
最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位都需要 一步 。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。
另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的 步数 。
示例 1：输入：plants = [2,2,3,3], capacity = 5 输出：14
解释：从河边开始，此时水罐是装满的：
- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。
- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。
- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。
- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。
- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。
需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。
示例 2：输入：plants = [1,1,1,4,2,3], capacity = 4 输出：30
解释：从河边开始，此时水罐是装满的：
- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。
- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。
- 走到植物 5 (6 步) ，浇水。
需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。
示例 3：输入：plants = [7,7,7,7,7,7,7], capacity = 8 输出：49
解释：每次浇水都需要重新灌满水罐。
需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。
提示：n == plants.length
1 <= n <= 1000
1 <= plants[i] <= 106
max(plants[i]) <= capacity <= 109

• 解题思路

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

func wateringPlants(plants []int, capacity int) int {
	res := 0
	n := len(plants)
	value := capacity
	for i := 0; i < n; i++ {
		if plants[i] <= value {
			res++ // 走1步
			value = value - plants[i]
		} else {
			res = res + i + (i + 1) // 回去i，返回i+1
			value = capacity - plants[i]
		}
	}
	return res
}

2080.区间内查询数字的频率(3)

• 题目

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率。
子数组中一个值的 频率指的是这个子数组中这个值的出现次数。
请你实现RangeFreqQuery类：
RangeFreqQuery(int[] arr)用下标从 0开始的整数数组arr构造一个类的实例。
int query(int left, int right, int value)返回子数组arr[left...right]中value的频率。
一个 子数组 指的是数组中一段连续的元素。arr[left...right]指的是 nums中包含下标 left和 right在内的中间一段连续元素。
示例 1：输入：["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：[null, 1, 2]
解释：RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。
提示：1 <= arr.length <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
调用query不超过105次。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希+二分查找	O(nlog(n))	O(n)
02	内置函数	O(nlog(n))	O(n)
03	内置函数	O(nlog(n))	O(n)

type RangeFreqQuery struct {
	m map[int][]int
}

func Constructor(arr []int) RangeFreqQuery {
	m := make(map[int][]int)
	for i := 0; i < len(arr); i++ {
		m[arr[i]] = append(m[arr[i]], i)
	}
	return RangeFreqQuery{m: m}
}

func (this *RangeFreqQuery) Query(left int, right int, value int) int {
	arr := this.m[value]
	l := lowerBound(arr, left)
	r := upperBound(arr, right)
	return r - l
}

// 返回第一个大于target的位置
func lowerBound(arr []int, target int) int {
	left, right := 0, len(arr)
	for left < right {
		mid := left + (right-left)/2
		if arr[mid] == target {
			right = mid // 收缩左边界
		} else if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

// 返回第一个大于等于target的位置
func upperBound(arr []int, target int) int {
	left, right := 0, len(arr)
	for left < right {
		mid := left + (right-left)/2
		if arr[mid] == target {
			left = mid + 1 // 收缩左边界
		} else if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

# 2
type RangeFreqQuery struct {
	m map[int]sort.IntSlice
}

func Constructor(arr []int) RangeFreqQuery {
	m := make(map[int]sort.IntSlice)
	for i := 0; i < len(arr); i++ {
		m[arr[i]] = append(m[arr[i]], i)
	}
	return RangeFreqQuery{m: m}
}

func (this *RangeFreqQuery) Query(left int, right int, value int) int {
	arr := this.m[value]
	arr = arr[arr.Search(left):]
	return arr.Search(right + 1)
}

# 3
type RangeFreqQuery struct {
	m map[int][]int
}

func Constructor(arr []int) RangeFreqQuery {
	m := make(map[int][]int)
	for i := 0; i < len(arr); i++ {
		m[arr[i]] = append(m[arr[i]], i)
	}
	return RangeFreqQuery{m: m}
}

func (this *RangeFreqQuery) Query(left int, right int, value int) int {
	arr := this.m[value]
	l := sort.SearchInts(arr, left)
	r := sort.SearchInts(arr, right+1)
	return r - l
}

2086.从房屋收集雨水需要的最少水桶数(2)

• 题目

给你一个下标从 0开始的字符串street。street中每个字符要么是表示房屋的'H' ，要么是表示空位的'.'。
你可以在 空位放置水桶，从相邻的房屋收集雨水。位置在 i - 1或者 i + 1的水桶可以收集位置为 i处房屋的雨水。
一个水桶如果相邻两个位置都有房屋，那么它可以收集 两个 房屋的雨水。
在确保 每个房屋旁边都 至少有一个水桶的前提下，请你返回需要的 最少水桶数。如果无解请返回 -1。
示例 1：输入：street = "H..H" 输出：2
解释：我们可以在下标为 1 和 2 处放水桶。
"H..H" -> "HBBH"（'B' 表示放置水桶）。
下标为 0 处的房屋右边有水桶，下标为 3 处的房屋左边有水桶。
所以每个房屋旁边都至少有一个水桶收集雨水。
示例 2：输入：street = ".H.H." 输出：1
解释：我们可以在下标为 2 处放置一个水桶。
".H.H." -> ".HBH."（'B' 表示放置水桶）。
下标为 1 处的房屋右边有水桶，下标为 3 处的房屋左边有水桶。
所以每个房屋旁边都至少有一个水桶收集雨水。
示例 3：输入：street = ".HHH." 输出：-1
解释：没有空位可以放置水桶收集下标为 2 处的雨水。
所以没有办法收集所有房屋的雨水。
示例 4：输入：street = "H" 输出：-1
解释：没有空位放置水桶。
所以没有办法收集所有房屋的雨水。
示例 5：输入：street = "." 输出：0
解释：没有房屋需要收集雨水。
所以需要 0 个水桶。
提示：1 <= street.length <= 105
street[i]要么是'H'，要么是'.' 。

• 解题思路

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

func minimumBuckets(street string) int {
	res := 0
	n := len(street)
	for i := 0; i < n; i++ {
		if street[i] == 'H' {
			if i+1 < n && street[i+1] == '.' { // (H.A)BC的情况，往后数3(+2再+1)位到B，+1
				res++
				i = i + 2
			} else if i >= 1 && street[i-1] == '.' { // (.HH)ABC的情况，+1
				res++
			} else {
				return -1
			}
		}
	}
	return res
}

# 2
func minimumBuckets(street string) int {
	if street == "H" || strings.Contains(street, "HHH") ||
		strings.HasSuffix(street, "HH") || strings.HasPrefix(street, "HH") {
		return -1
	}
	return strings.Count(street, "H") - strings.Count(street, "H.H")
}

2087.网格图中机器人回家的最小代价(2)

• 题目

给你一个m x n的网格图，其中(0, 0)是最左上角的格子，(m - 1, n - 1)是最右下角的格子。
给你一个整数数组startPos，startPos = [startrow, startcol]表示 初始有一个 机器人在格子(startrow, startcol)处。
同时给你一个整数数组homePos，homePos = [homerow, homecol]表示机器人的 家在格子(homerow, homecol)处。
机器人需要回家。每一步它可以往四个方向移动：上，下，左，右，同时机器人不能移出边界。
每一步移动都有一定代价。再给你两个下标从0开始的额整数数组：长度为m的数组rowCosts 和长度为 n的数组colCosts。
如果机器人往 上或者往 下移动到第 r行的格子，那么代价为rowCosts[r]。
如果机器人往 左或者往 右移动到第 c列 的格子，那么代价为colCosts[c]。
请你返回机器人回家需要的 最小总代价。
示例 1：输入：startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7] 输出：18
解释：一个最优路径为：
从 (1, 0) 开始
-> 往下走到 (2, 0) 。代价为 rowCosts[2] = 3 。
-> 往右走到 (2, 1) 。代价为 colCosts[1] = 2 。
-> 往右走到 (2, 2) 。代价为 colCosts[2] = 6 。
-> 往右走到 (2, 3) 。代价为 colCosts[3] = 7 。
总代价为 3 + 2 + 6 + 7 = 18
示例 2：输入：startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26] 输出：0
解释：机器人已经在家了，所以不需要移动。总代价为 0 。
提示：m == rowCosts.length
n == colCosts.length
1 <= m, n <= 105
0 <= rowCosts[r], colCosts[c] <= 104
startPos.length == 2
homePos.length == 2
0 <= startrow, homerow < m
0 <= startcol, homecol < n

• 解题思路

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

func minCost(startPos []int, homePos []int, rowCosts []int, colCosts []int) int {
	res := 0
	a, b, c, d := startPos[0], startPos[1], homePos[0], homePos[1]
	res = res - rowCosts[a] - colCosts[b]
	if a > c {
		a, c = c, a
	}
	if b > d {
		b, d = d, b
	}
	for i := a; i <= c; i++ {
		res = res + rowCosts[i]
	}
	for i := b; i <= d; i++ {
		res = res + colCosts[i]
	}
	return res
}

# 2
func minCost(startPos []int, homePos []int, rowCosts []int, colCosts []int) int {
	res := 0
	a, b, c, d := startPos[0], startPos[1], homePos[0], homePos[1]
	if a > c {
		for i := a - 1; i >= c; i-- {
			res = res + rowCosts[i]
		}
	} else if a < c {
		for i := a + 1; i <= c; i++ {
			res = res + rowCosts[i]
		}
	}
	if b > d {
		for i := b - 1; i >= d; i-- {
			res = res + colCosts[i]
		}
	} else if b < d {
		for i := b + 1; i <= d; i++ {
			res = res + colCosts[i]
		}
	}
	return res
}

2090.半径为k的子数组平均值(2)

• 题目

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。
半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，
即下标在i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。
如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。
例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 3.75，截断后得到 3 。
示例 1：输入：nums = [7,4,3,9,1,8,5,2,6], k = 3 输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：- avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。
- 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。
  使用截断式 整数除法，avg[3] = 37 / 7 = 5 。
- 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
- 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。
示例 2：输入：nums = [100000], k = 0 输出：[100000]
解释：- 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。
  avg[0] = 100000 / 1 = 100000 。
示例 3：输入：nums = [8], k = 100000 输出：[-1]
解释：- avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。
提示：n == nums.length
1 <= n <= 105
0 <= nums[i], k <= 105

• 解题思路

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

func getAverages(nums []int, k int) []int {
	n := len(nums)
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = -1
	}
	if 2*k+1 <= n {
		sum := 0
		for i := 0; i < 2*k+1; i++ {
			sum = sum + nums[i]
		}
		for i := k; i < n-k; i++ {
			if i != k {
				sum = sum + nums[i+k] - nums[i-k-1]
			}
			res[i] = sum / (2*k + 1)
		}
	}
	return res
}

# 2
func getAverages(nums []int, k int) []int {
	n := len(nums)
	res := make([]int, n)
	left := 0
	sum := 0
	for right := 0; right < n; right++ {
		res[right] = -1
		sum = sum + nums[right]
		if right >= 2*k {
			res[right-k] = sum / (2*k + 1)
			sum = sum - nums[left]
			left++
		}
	}
	return res
}

2091.从数组中移除最大值和最小值(1)

• 题目

给你一个下标从 0 开始的数组 nums ，数组由若干 互不相同 的整数组成。
nums 中有一个值最小的元素和一个值最大的元素。分别称为 最小值 和 最大值 。你的目标是从数组中移除这两个元素。
一次 删除 操作定义为从数组的 前面 移除一个元素或从数组的 后面 移除一个元素。
返回将数组中最小值和最大值 都 移除需要的最小删除次数。
示例 1：输入：nums = [2,10,7,5,4,1,8,6] 输出：5
解释：数组中的最小元素是 nums[5] ，值为 1 。
数组中的最大元素是 nums[1] ，值为 10 。
将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。
结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。
示例 2：输入：nums = [0,-4,19,1,8,-2,-3,5] 输出：3
解释：数组中的最小元素是 nums[1] ，值为 -4 。
数组中的最大元素是 nums[2] ，值为 19 。
将最大值和最小值都移除需要从数组前面移除 3 个元素。
结果是 3 ，这是所有可能情况中的最小删除次数。 
示例 3：输入：nums = [101] 输出：1
解释：数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。
移除它只需要 1 次删除操作。
提示：1 <= nums.length <= 105
-105 <= nums[i] <= 105
nums 中的整数 互不相同

• 解题思路

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

func minimumDeletions(nums []int) int {
	minIndex, maxIndex := 0, 0
	for i := 0; i < len(nums); i++ {
		if nums[i] > nums[maxIndex] {
			maxIndex = i
		}
		if nums[i] < nums[minIndex] {
			minIndex = i
		}
	}
	if minIndex > maxIndex { // 保证minIndex <= maxIndex
		minIndex, maxIndex = maxIndex, minIndex
	}
	a := maxIndex + 1                        // 第1种情况：全往左移
	b := len(nums) - minIndex                // 第2种情况：全往右移
	c := minIndex + 1 + len(nums) - maxIndex // 第3种情况：往2边移动
	return min(min(a, b), c)
}

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

2095.删除链表的中间节点(2)

• 题目

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
示例 1：输入：head = [1,3,4,7,1,2,6] 输出：[1,3,4,1,2,6]
解释：上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。 
示例 2：输入：head = [1,2,3,4] 输出：[1,2,4]
解释：上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。
示例 3：输入：head = [2,1] 输出：[2]
解释：上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。
提示：链表中节点的数目在范围 [1, 105] 内
1 <= Node.val <= 105

• 解题思路

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

func deleteMiddle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}
	slow := head
	fast := head
	prev := &ListNode{}
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		prev = slow
		slow = slow.Next
	}
	prev.Next = prev.Next.Next
	return head
}

# 2
func deleteMiddle(head *ListNode) *ListNode {
	prev := &ListNode{Next: head}
	slow := prev
	fast := prev
	for fast.Next != nil && fast.Next.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return prev.Next
}

2096.从二叉树一个节点到另一个节点每一步的方向(2)

• 题目

给你一棵 二叉树的根节点root，这棵二叉树总共有n个节点。每个节点的值为1到n中的一个整数，且互不相同。
给你一个整数startValue，表示起点节点 s的值，和另一个不同的整数destValue，表示终点节点t的值。
请找到从节点s到节点 t的 最短路径，并以字符串的形式返回每一步的方向。
每一步用 大写字母'L'，'R'和'U'分别表示一种方向：
'L'表示从一个节点前往它的 左孩子节点。
'R'表示从一个节点前往它的 右孩子节点。
'U'表示从一个节点前往它的 父节点。
请你返回从 s到 t最短路径每一步的方向。
示例 1：输入：root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6 输出："UURL"
解释：最短路径为：3 → 1 → 5 → 2 → 6 。
示例 2：输入：root = [2,1], startValue = 2, destValue = 1 输出："L"
解释：最短路径为：2 → 1 。
提示：树中节点数目为n。
2 <= n <= 105
1 <= Node.val <= n
树中所有节点的值 互不相同。
1 <= startValue, destValue <= n
startValue != destValue

• 解题思路

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

var m map[*TreeNode]*TreeNode // 父节点
var start, dest *TreeNode

func getDirections(root *TreeNode, startValue int, destValue int) string {
	m = make(map[*TreeNode]*TreeNode)
	start, dest = &TreeNode{}, &TreeNode{}
	dfs(root, startValue, destValue)            // 构建父节点关系
	a, b := path(start, root), path(dest, root) // 生成根节点到目标节点的路径
	i := 0
	for i = 0; i < len(a) && i < len(b); i++ {
		if a[i] != b[i] {
			break
		}
	}
	return strings.Repeat("U", len(a)-i) + strings.Join(b[i:], "")
}

func path(cur *TreeNode, root *TreeNode) []string {
	res := make([]string, 0)
	for cur != root {
		prev := m[cur]
		if cur == prev.Left {
			res = append(res, "L")
		} else {
			res = append(res, "R")
		}
		cur = prev
	}
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	return res
}

func dfs(root *TreeNode, startValue, destValue int) {
	if root.Val == startValue {
		start = root
	}
	if root.Val == destValue {
		dest = root
	}
	if root.Left != nil {
		m[root.Left] = root
		dfs(root.Left, startValue, destValue)
	}
	if root.Right != nil {
		m[root.Right] = root
		dfs(root.Right, startValue, destValue)
	}
}

# 2
var a, b []string

func getDirections(root *TreeNode, startValue int, destValue int) string {
	a, b = make([]string, 0), make([]string, 0)
	dfs(root, startValue, destValue, make([]string, 0)) // 构建父节点关系

	i := 0
	for i = 0; i < len(a) && i < len(b); i++ {
		if a[i] != b[i] {
			break
		}
	}
	return strings.Repeat("U", len(a)-i) + strings.Join(b[i:], "")
}

func dfs(root *TreeNode, startValue, destValue int, path []string) {
	if root.Val == startValue {
		a = make([]string, len(path))
		copy(a, path)
	}
	if root.Val == destValue {
		b = make([]string, len(path))
		copy(b, path)
	}
	if root.Left != nil {
		path = append(path, "L")
		dfs(root.Left, startValue, destValue, path)
		path = path[:len(path)-1]
	}
	if root.Right != nil {
		path = append(path, "R")
		dfs(root.Right, startValue, destValue, path)
		path = path[:len(path)-1]
	}
}

2100.适合打劫银行的日子(1)

• 题目

你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组security，其中security[i]是第 i天执勤警卫的数量。
日子从 0开始编号。同时给你一个整数time。
如果第 i天满足以下所有条件，我们称它为一个适合打劫银行的日子：
第 i天前和后都分别至少有 time天。
第 i天前连续 time天警卫数目都是非递增的。
第 i天后连续 time天警卫数目都是非递减的。
更正式的，第 i 天是一个合适打劫银行的日子当且仅当：
security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... 
<= security[i + time - 1] <= security[i + time].
请你返回一个数组，包含 所有 适合打劫银行的日子（下标从 0开始）。返回的日子可以 任意顺序排列。
示例 1：输入：security = [5,3,3,3,5,6,2], time = 2 输出：[2,3]
解释：第 2 天，我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。
第 3 天，我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。
没有其他日子符合这个条件，所以日子 2 和 3 是适合打劫银行的日子。
示例 2：输入：security = [1,1,1,1,1], time = 0 输出：[0,1,2,3,4]
解释：因为 time 等于 0 ，所以每一天都是适合打劫银行的日子，所以返回每一天。
示例 3：输入：security = [1,2,3,4,5,6], time = 2输出：[]
解释：没有任何一天的前 2 天警卫数目是非递增的。
所以没有适合打劫银行的日子，返回空数组。
示例 4：输入：security = [1], time = 5 输出：[]
解释：没有日子前面和后面有 5 天时间。
所以没有适合打劫银行的日子，返回空数组。
提示：1 <= security.length <= 105
0 <= security[i], time <= 105

• 解题思路

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

func goodDaysToRobBank(security []int, time int) []int {
	n := len(security)
	if 2*time >= n {
		return nil
	}
	left, right := make([]int, n), make([]int, n)
	for i := 1; i < n; i++ {
		if security[i-1] >= security[i] {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if security[i] <= security[i+1] {
			right[i] = right[i+1] + 1
		}
	}
	res := make([]int, 0)
	for i := time; i < n-time; i++ {
		if left[i] >= time && right[i] >= time {
			res = append(res, i)
		}
	}
	return res
}

2001-2100-Hard

2009.使数组连续的最少操作数(2)

• 题目

给你一个整数数组nums。每一次操作中，你可以将nums中任意一个元素替换成 任意整数。
如果nums满足以下条件，那么它是 连续的：
nums中所有元素都是 互不相同的。
nums中 最大元素与最小元素的差等于nums.length - 1。
比方说，nums = [4, 2, 5, 3]是 连续的，但是nums = [1, 2, 3, 5, 6] 不是连续的。
请你返回使 nums连续的 最少操作次数。
示例 1：输入：nums = [4,2,5,3] 输出：0
解释：nums 已经是连续的了。
示例 2：输入：nums = [1,2,3,5,6] 输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。
示例 3：输入：nums = [1,10,100,1000] 输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。
提示：1 <= nums.length <= 105
1 <= nums[i] <= 109

• 解题思路

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

func minOperations(nums []int) int {
	n := len(nums)
	sort.Ints(nums)
	// 去重
	index := 0
	for i := 1; i < n; i++ {
		if nums[index] != nums[i] {
			index++
			nums[index] = nums[i]
		}
	}
	nums = nums[:index+1]
	// 二分查找
	res := 0
	for right := 0; right < len(nums); right++ {
		// 计算区间[nums[i]-n+1, nums[i]]的长度
		left := sort.SearchInts(nums[:right], nums[right]-n+1)
		res = max(res, right-left+1) // 取最长的长度
	}
	return n - res
}

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

# 2
func minOperations(nums []int) int {
	n := len(nums)
	sort.Ints(nums)
	// 去重
	index := 0
	for i := 1; i < n; i++ {
		if nums[index] != nums[i] {
			index++
			nums[index] = nums[i]
		}
	}
	nums = nums[:index+1]
	// 滑动窗口
	res := 0
	left := 0
	for right := 0; right < len(nums); right++ {
		for nums[right]-nums[left] > n-1 {
			left++
		}
		res = max(res, right-left+1)
	}
	return n - res
}

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

2025.分割数组的最多方案数(2)

• 题目

给你一个下标从 0开始且长度为 n的整数数组nums。分割数组 nums的方案数定义为符合以下两个条件的 pivot数目：
1 <= pivot < n
nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
同时给你一个整数k。你可以将nums中一个元素变为k或不改变数组。
请你返回在 至多改变一个元素的前提下，最多有多少种方法 分割nums使得上述两个条件都满足。
示例 1：输入：nums = [2,-1,2], k = 3 输出：1
解释：一个最优的方案是将 nums[0] 改为 k。数组变为 [3,-1,2] 。
有一种方法分割数组：
- pivot = 2 ，我们有分割 [3,-1 | 2]：3 + -1 == 2 。
示例 2：输入：nums = [0,0,0], k = 1 输出：2
解释：一个最优的方案是不改动数组。
有两种方法分割数组：
- pivot = 1 ，我们有分割 [0 | 0,0]：0 == 0 + 0 。
- pivot = 2 ，我们有分割 [0,0 | 0]: 0 + 0 == 0 。
示例 3：输入：nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33 输出：4
解释：一个最优的方案是将 nums[2] 改为 k 。数组变为 [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14] 。
有四种方法分割数组。
提示：n == nums.length
2 <= n <= 105
-105 <= k, nums[i] <= 105

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	前缀和+哈希	O(n)	O(n)
02	前缀和	O(n)	O(n)

func waysToPartition(nums []int, k int) int {
	res := 0
	n := len(nums)
	sum := 0
	prev := make(map[int]int) // 前缀和
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + nums[i]
		sum = sum + nums[i]
		if i != n-1 {
			prev[sum]++
		}
	}
	if sum%2 == 0 {
		res = prev[sum/2] // 不改变的结果
	}
	suf := make(map[int]int) // 后缀和
	sufSum := 0
	temp := sum
	for i := n - 1; i >= 0; i-- { // 枚举每一位修改后的结果
		target := sum - nums[i] + k // 替换后的总和
		temp = temp - nums[i]
		prev[temp]-- // 前缀和 减一
		sufSum = sufSum + k
		suf[sufSum]++
		if target%2 == 0 {
			res = max(res, prev[target/2]+suf[target/2])
		}
		suf[sufSum]--
		sufSum = sufSum - k + nums[i]
		suf[sufSum]++
	}
	return res
}

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

# 2
func waysToPartition(nums []int, k int) int {
	res := 0
	n := len(nums)
	prev := make(map[int]int) // 前缀和
	arr := make([]int, n)
	arr[0] = nums[0]
	for i := 1; i < n; i++ {
		arr[i] = arr[i-1] + nums[i]
		prev[arr[i-1]]++
	}
	sum := arr[n-1]
	if sum%2 == 0 {
		res = prev[sum/2] // 不改变的结果
	}
	m := make(map[int]int)
	for i := 0; i < len(arr); i++ {
		diff := k - nums[i]
		if (sum+diff)%2 == 0 {
			res = max(res, prev[(sum-diff)/2]+m[(sum+diff)/2])
		}
		m[arr[i]]++    // 左侧+1
		prev[arr[i]]-- // 右侧-1
	}
	return res
}

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

2050.并行课程III(2)

• 题目

给你一个整数n，表示有n节课，课程编号从1到n。同时给你一个二维整数数组relations，
其中relations[j] = [prevCoursej, nextCoursej]，
表示课程prevCoursej必须在课程nextCoursej之前完成（先修课的关系）。
同时给你一个下标从 0开始的整数数组time，其中time[i]表示完成第(i+1)门课程需要花费的 月份数。
请你根据以下规则算出完成所有课程所需要的 最少月份数：
如果一门课的所有先修课都已经完成，你可以在 任意时间开始这门课程。
你可以同时上任意门课程。
请你返回完成所有课程所需要的 最少月份数。
注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。
示例1:输入：n = 3, relations = [[1,3],[2,3]], time = [3,2,5] 输出：8
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 和 2 。
课程 1 花费 3 个月，课程 2 花费 2 个月。
所以，最早开始课程 3 的时间是月份 3 ，完成所有课程所需时间为 3 + 5 = 8 个月。
示例 2：输入：n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5] 输出：12
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 ，2 和 3 。
在月份 1，2 和 3 分别完成这三门课程。
课程 4 需在课程 3 之后开始，也就是 3 个月后。课程 4 在 3 + 4 = 7 月完成。
课程 5 需在课程 1，2，3 和 4 之后开始，也就是在 max(1,2,3,7) = 7 月开始。
所以完成所有课程所需的最少时间为 7 + 5 = 12 个月。
提示：1 <= n <= 5 * 104
0 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)
relations[j].length == 2
1 <= prevCoursej, nextCoursej <= n
prevCoursej != nextCoursej
所有的先修课程对[prevCoursej, nextCoursej]都是 互不相同的。
time.length == n
1 <= time[i] <= 104
先修课程图是一个有向无环图。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	拓扑排序	O(n)	O(n)
02	递归	O(n)	O(n)

func minimumTime(n int, relations [][]int, time []int) int {
	res := 0
	degree := make([]int, n+1)
	dis := make([]int, n+1)   // 计算入度
	arr := make([][]int, n+1) // 邻接表
	for i := 0; i < len(relations); i++ {
		a, b := relations[i][0], relations[i][1] // a => b
		arr[a] = append(arr[a], b)
		degree[b]++ // 入度+1
	}
	queue := make([]int, 0)
	for i := 1; i <= n; i++ {
		if degree[i] == 0 { // 入度为0：起点
			queue = append(queue, i)
			dis[i] = time[i-1]
			res = max(res, dis[i])
		}
	}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for i := 0; i < len(arr[cur]); i++ {
			next := arr[cur][i]
			dis[next] = max(dis[next], dis[cur]+time[next-1]) // 更新为较大的结果
			degree[next]--                                    // next节点入度-1
			if degree[next] == 0 {                            // 入度=0
				queue = append(queue, next)
			}
			res = max(res, dis[next])
		}
	}
	return res
}

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

# 2
var m map[int]int
var arr [][]int
var temp []int

func minimumTime(n int, relations [][]int, time []int) int {
	arr = make([][]int, n+1)
	degree := make([]int, n+1) // 出度
	temp = make([]int, n+1)
	m = make(map[int]int)
	copy(temp, time)
	for i := 0; i < len(relations); i++ {
		a, b := relations[i][0], relations[i][1] // a => b
		arr[b] = append(arr[b], a)
		degree[a]++
	}
	res := 0
	for i := 1; i <= n; i++ {
		if degree[i] == 0 { // 从出度为0的节点往前递归
			res = max(res, dfs(i))
		}
	}
	return res
}

func dfs(root int) int {
	if _, ok := m[root]; ok {
		return m[root]
	}
	sum := 0
	for i := 0; i < len(arr[root]); i++ {
		sum = max(sum, dfs(arr[root][i]))
	}
	sum = sum + temp[root-1]
	m[root] = sum
	return sum
}

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

2065.最大化一张图中的路径价值(2)

• 题目

给你一张 无向图，图中有 n个节点，节点编号从 0到 n - 1（都包括）。同时给你一个下标从 0开始的整数数组values，
其中values[i]是第 i个节点的 价值。同时给你一个下标从 0开始的二维整数数组edges，
其中edges[j] = [uj, vj, timej]表示节点uj 和vj之间有一条需要timej秒才能通过的无向边。
最后，给你一个整数maxTime。
合法路径指的是图中任意一条从节点0开始，最终回到节点 0，且花费的总时间 不超过maxTime 秒的一条路径。
你可以访问一个节点任意次。
一条合法路径的 价值定义为路径中 不同节点的价值 之和（每个节点的价值 至多算入价值总和中一次）。
请你返回一条合法路径的 最大价值。
注意：每个节点 至多有 四条边与之相连。
示例 1：输入：values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49 输出：75
解释：一条可能的路径为：0 -> 1 -> 0 -> 3 -> 0 。总花费时间为 10 + 10 + 10 + 10 = 40 <= 49 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 0 + 32 + 43 = 75 。
示例 2：输入：values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30 输出：25
解释：一条可能的路径为：0 -> 3 -> 0 。总花费时间为 10 + 10 = 20 <= 30 。
访问过的节点为 0 和 3 ，最大路径价值为 5 + 20 = 25 。
示例 3：输入：values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50 输出：7
解释：一条可能的路径为：0 -> 1 -> 3 -> 1 -> 0 。总花费时间为 10 + 13 + 13 + 10 = 46 <= 50 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。
示例 4：输入：values = [0,1,2], edges = [[1,2,10]], maxTime = 10 输出：0
解释：唯一一条路径为 0 。总花费时间为 0 。
唯一访问过的节点为 0 ，最大路径价值为 0 。
提示：n == values.length
1 <= n <= 1000
0 <= values[i] <= 108
0 <= edges.length <= 2000
edges[j].length == 3
0 <= uj < vj <= n - 1
10 <= timej, maxTime <= 100
[uj, vj]所有节点对 互不相同。
每个节点 至多有四条边。
图可能不连通。

• 解题思路

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

var res int
var arr [][][2]int
var visited []bool

func maximalPathQuality(values []int, edges [][]int, maxTime int) int {
	n := len(values)
	arr = make([][][2]int, n) // 邻接表
	for i := 0; i < len(edges); i++ {
		a, b, c := edges[i][0], edges[i][1], edges[i][2]
		arr[a] = append(arr[a], [2]int{b, c})
		arr[b] = append(arr[b], [2]int{a, c})
	}
	visited = make([]bool, n)
	visited[0] = true
	res = 0
	dfs(values, maxTime, 0, 0, values[0]) // 初始带着0点的价值
	return res
}

func dfs(values []int, maxTime int, start int, t int, sum int) {
	if start == 0 {
		res = max(res, sum)
	}
	for i := 0; i < len(arr[start]); i++ {
		next, c := arr[start][i][0], arr[start][i][1]
		if t+c <= maxTime { // 时间在范围内
			if visited[next] == false { // 该点没有出现过，加上该点的价值
				visited[next] = true
				dfs(values, maxTime, next, t+c, sum+values[next])
				visited[next] = false
			} else { // 该点出现过，不加价值，只加时间
				dfs(values, maxTime, next, t+c, sum)
			}
		}
	}
}

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

# 2
var res int
var arr [][][2]int
var visited []int

func maximalPathQuality(values []int, edges [][]int, maxTime int) int {
	n := len(values)
	arr = make([][][2]int, n) // 邻接表
	for i := 0; i < len(edges); i++ {
		a, b, c := edges[i][0], edges[i][1], edges[i][2]
		arr[a] = append(arr[a], [2]int{b, c})
		arr[b] = append(arr[b], [2]int{a, c})
	}
	res = 0
	visited = make([]int, n)
	dfs(values, maxTime, 0, 0, 0)
	return res
}

func dfs(values []int, maxTime int, start int, t int, sum int) {
	if t > maxTime {
		return
	}

	if visited[start] == 0 {
		sum = sum + values[start]
	}
	visited[start]++
	if start == 0 {
		res = max(res, sum)
	}
	for i := 0; i < len(arr[start]); i++ {
		next, c := arr[start][i][0], arr[start][i][1]
		dfs(values, maxTime, next, t+c, sum)
	}
	visited[start]--
}

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

2076.处理含限制条件的好友请求(2)

• 题目

给你一个整数 n ，表示网络上的用户数目。每个用户按从 0 到 n - 1 进行编号。
给你一个下标从 0 开始的二维整数数组 restrictions ，
其中 restrictions[i] = [xi, yi] 意味着用户 xi 和用户 yi 不能 成为 朋友 ，不管是 直接 还是通过其他用户 间接 。
最初，用户里没有人是其他用户的朋友。给你一个下标从 0 开始的二维整数数组 requests 表示好友请求的列表，
其中 requests[j] = [uj, vj] 是用户 uj 和用户 vj 之间的一条好友请求。
如果 uj 和 vj 可以成为 朋友 ，那么好友请求将会 成功 。
每个好友请求都会按列表中给出的顺序进行处理（即，requests[j] 会在 requests[j + 1] 前）。
一旦请求成功，那么对所有未来的好友请求而言， uj 和 vj 将会 成为直接朋友 。
返回一个 布尔数组 result ，其中元素遵循此规则：如果第 j 个好友请求 成功 ，那么 result[j] 就是 true ；否则，为 false 。
注意：如果 uj 和 vj 已经是直接朋友，那么他们之间的请求将仍然成功 。
示例 1：输入：n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]] 输出：[true,false]
解释：请求 0 ：用户 0 和 用户 2 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 2 和 用户 1 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (1--2--0) 。
示例 2：输入：n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]] 输出：[true,false]
解释：请求 0 ：用户 1 和 用户 2 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 0 和 用户 2 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--2--1) 。
示例 3：输入：n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
输出：[true,false,true,false]
解释：请求 0 ：用户 0 和 用户 4 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 1 和 用户 2 不能成为朋友，因为他们之间存在限制。
请求 2 ：用户 3 和 用户 1 可以成为朋友，所以他们成为直接朋友。 
请求 3 ：用户 3 和 用户 4 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--4--3--1) 。
提示：2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= xi, yi <= n - 1
xi != yi
1 <= requests.length <= 1000
requests[j].length == 2
0 <= uj, vj <= n - 1
uj != vj

• 解题思路

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

func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
	fa = Init(n)
	res := make([]bool, len(requests))
	for i := 0; i < len(requests); i++ {
		a, b := requests[i][0], requests[i][1]
		x, y := find(a), find(b)
		if x == y {
			res[i] = true
		} else {
			flag := true
			for j := 0; j < len(restrictions); j++ { // 尝试每个限制条件
				c, d := restrictions[j][0], restrictions[j][1]
				u, v := find(c), find(d)
				if (x == u && y == v) || (x == v && y == u) { // 有限制
					flag = false
					break
				}
			}
			if flag == true {
				res[i] = true
				union(x, y)
			}
		}
	}
	return res
}

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)
}

# 2
func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
	fa = Init(n)
	res := make([]bool, len(requests))
	for i := 0; i < len(requests); i++ {
		a, b := requests[i][0], requests[i][1]
		temp := make([]int, n)
		copy(temp, fa) // 备份当前的结果
		union(a, b)    // 尝试连接
		flag := true
		for j := 0; j < len(restrictions); j++ {
			c, d := restrictions[j][0], restrictions[j][1]
			if query(c, d) == true { // 查看是否有限制
				flag = false
				break
			}
		}
		if flag == true {
			res[i] = true
		} else {
			fa = make([]int, n) // 不满足条件，恢复回去
			copy(fa, temp)
		}
	}
	return res
}

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)
}

2092.找出知晓秘密的所有专家

题目

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，
其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。
一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。
专家 0 有一个 秘密 ，最初，他在时间0 将这个秘密分享给了专家 firstPerson 。
接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。
更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。
秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。
在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。
示例 1：输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1 输出：[0,1,2,3,5]
解释：时间 0 ，专家 0 将秘密与专家 1 共享。
时间 5 ，专家 1 将秘密与专家 2 共享。
时间 8 ，专家 2 将秘密与专家 3 共享。
时间 10 ，专家 1 将秘密与专家 5 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。
示例 2：输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3 输出：[0,1,3]
解释：时间 0 ，专家 0 将秘密与专家 3 共享。
时间 2 ，专家 1 与专家 2 都不知晓这个秘密。
时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。
因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。
示例 3：输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1 输出：[0,1,2,3,4]
解释：时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。
注意，专家 2 可以在收到秘密的同一时间分享此秘密。
时间 2 ，专家 3 将秘密与专家 4 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。
示例 4：输入：n = 6, meetings = [[0,2,1],[1,3,1],[4,5,1]], firstPerson = 1 输出：[0,1,2,3]
解释：时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 0 将秘密与专家 2 共享，专家 1 将秘密与专家 3 共享。
因此，在所有会议结束后，专家 0、1、2 和 3 都将知晓这个秘密。
提示：2 <= n <= 105
1 <= meetings.length <= 105
meetings[i].length == 3
0 <= xi, yi <= n - 1
xi != yi
1 <= timei <= 105
1 <= firstPerson <= n - 1

解题思路

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

2097.合法重新排列数对(2)

• 题目

给你一个下标从 0开始的二维整数数组pairs，其中pairs[i] = [starti, endi]。
如果 pairs的一个重新排列，满足对每一个下标 i （1 <= i < pairs.length）都有endi-1 == starti ，
那么我们就认为这个重新排列是pairs 的一个 合法重新排列 。
请你返回 任意一个pairs 的合法重新排列。
注意：数据保证至少存在一个 pairs的合法重新排列。
示例 1：输入：pairs = [[5,1],[4,5],[11,9],[9,4]] 输出：[[11,9],[9,4],[4,5],[5,1]]
解释：输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti。
end0 = 9 == 9 = start1 
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3
示例 2：输入：pairs = [[1,3],[3,2],[2,1]] 输出：[[1,3],[3,2],[2,1]]
解释：输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。
示例 3：输入：pairs = [[1,2],[1,3],[2,1]] 输出：[[1,2],[2,1],[1,3]]
解释：输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2
提示：1 <= pairs.length <= 105
pairs[i].length == 2
0 <= starti, endi <= 109
starti != endi
pairs中不存在一模一样的数对。
至少 存在 一个合法的pairs重新排列。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	欧拉回路	O(n)	O(n)
02	欧拉回路	O(n)	O(n)

var arr map[int][]int
var res [][]int

func validArrangement(pairs [][]int) [][]int {
	res = make([][]int, 0)
	arr = make(map[int][]int) // 有向图邻接表
	m := make(map[int]int)
	for i := 0; i < len(pairs); i++ {
		a, b := pairs[i][0], pairs[i][1]
		arr[a] = append(arr[a], b)
		m[b]++ // 入度+1
		m[a]-- // 出度-1
	}
	start := pairs[0][0] // 寻找起始节点
	for k, v := range m {
		if v == -1 {
			start = k
			break
		}
	}
	dfs(start)
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	return res
}

func dfs(start int) {
	for len(arr[start]) > 0 {
		next := arr[start][0]
		arr[start] = arr[start][1:]
		dfs(next)
		res = append(res, []int{start, next})
	}
}

# 2
var arr map[int][]int
var path []int

func validArrangement(pairs [][]int) [][]int {
	path = make([]int, 0)
	arr = make(map[int][]int) // 有向图邻接表
	m := make(map[int]int)
	for i := 0; i < len(pairs); i++ {
		a, b := pairs[i][0], pairs[i][1]
		arr[a] = append(arr[a], b)
		m[b]++ // 入度+1
		m[a]-- // 出度-1
	}
	start := pairs[0][0] // 寻找起始节点
	for k, v := range m {
		if v == -1 {
			start = k
			break
		}
	}
	dfs(start)
	res := make([][]int, 0)
	for i := len(path) - 1; i > 0; i-- {
		res = append(res, []int{path[i], path[i-1]})
	}
	return res
}

func dfs(start int) {
	for len(arr[start]) > 0 {
		next := arr[start][0]
		arr[start] = arr[start][1:]
		dfs(next)
	}
	path = append(path, start)
}