0301-0400-Easy¶

303.区域和检索-数组不可变(2)¶

题目

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:
    你可以假设数组不可变。
    会多次调用 sumRange 方法。

解题思路

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

type NumArray struct {
	arr []int
}

func Constructor(nums []int) NumArray {
	size := len(nums)
	arr := make([]int, size+1)
	for i := 1; i <= size; i++ {
		arr[i] = arr[i-1] + nums[i-1]
	}
	return NumArray{arr: arr}
}

func (n *NumArray) SumRange(i int, j int) int {
	return n.arr[j+1] - n.arr[i]
}

#
type NumArray struct {
	arr []int
}

func Constructor(nums []int) NumArray {
	return NumArray{nums}
}

func (n *NumArray) SumRange(i int, j int) int {
	sum := 0
	for ; i <= j; i++ {
		sum = sum + n.arr[i]
	}
	return sum
}

326.3的幂(3)¶

题目

给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1: 输入: 27 输出: true
示例 2: 输入: 0 输出: false
示例 3: 输入: 9 输出: true
示例 4: 输入: 45 输出: false
进阶：你能不使用循环或者递归来完成本题吗？

解题思路

No.	思路	时间复杂度	空间复杂度
01	迭代	I	O(1)
02	转3进制判断	O(log(n))	O(1)
03	递归	O(log(n))	O(log(n))

func isPowerOfThree(n int) bool {
	if n <= 0 {
		return false
	}
	for n > 1 {
		if n % 3 != 0{
			return false
		}
		n = n / 3
	}
	return n == 1
}

#
func isPowerOfThree(n int) bool {
	if n <= 0 {
		return false
	}
	str := strconv.FormatInt(int64(n), 3)
	return str[0:1] == "1" && strings.Count(str, "0") == len(str)-1
}


#
func isPowerOfThree(n int) bool {
	if n <= 0 {
		return false
	}
	if n == 1 {
		return true
	}
	if n%3 != 0 {
		return false
	}
	return isPowerOfThree(n / 3)
}

342.4的幂(4)¶

题目

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
示例 1: 输入: 16 输出: true
示例 2: 输入: 5 输出: false
进阶：你能不使用循环或者递归来完成本题吗？

解题思路

No.	思路	时间复杂度	空间复杂度
01	迭代	O(log(n))	O(1)
02	递归	O(log(n))	O(log(n))
03	位运算	O(1)	O(1)
04	转4进制	O(log(n))	O(1)

func isPowerOfFour(num int) bool {
	if num <= 0 {
		return false
	}

	for num > 1 {
		if num%4 != 0 {
			return false
		}
		num = num / 4
	}
	return num == 1
}

#
func isPowerOfFour(num int) bool {
	if num <= 0 {
		return false
	}
	if num == 1{
		return true
	}
	if num % 4 != 0{
		return false
	}

	return isPowerOfFour(num/4)
}

#
func isPowerOfFour(num int) bool {
	if num <= 0 {
		return false
	}
	// return (num & (num-1) == 0) && (num-1)%3 == 0
	return (num&(num-1) == 0) && (num&0xaaaaaaaa == 0)
}

#
func isPowerOfFour(num int) bool {
	if num <= 0 {
		return false
	}
	str := strconv.FormatInt(int64(num), 4)
	return str[0:1] == "1" && strings.Count(str, "0") == len(str)-1
}

344.反转字符串(3)¶

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1： 输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2： 输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

解题思路

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

func reverseString(s []byte) {
	i, j := 0, len(s)-1
	for i < j {
		s[i], s[j] = s[j], s[i]
		i++
		j--
	}
}

#
func reverseString(s []byte) {
	var reverse func(int, int)
	reverse = func(left, right int) {
		if left < right {
			s[left], s[right] = s[right], s[left]
			reverse(left+1, right-1)
		}
	}
	reverse(0, len(s)-1)
}

#
func reverseString(s []byte) {
	for i := 0; i < len(s)/2; i++ {
		s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i]
	}
}

345.反转字符串中的元音字母(2)¶

题目

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1:输入: "hello"输出: "holle"
示例 2:输入: "leetcode"输出: "leotcede"
说明:元音字母不包含字母"y"。

解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	数组辅助替换	O(n)	O(n)

func reverseVowels(s string) string {
	bytes := []byte(s)
	length := len(s)
	i, j := 0, length-1
	for i < j {
		if !isvowels(bytes[i]) {
			i++
			continue
		}
		if !isvowels(bytes[j]) {
			j--
			continue
		}
		bytes[i], bytes[j] = bytes[j], bytes[i]
		i++
		j--
	}
	return string(bytes)
}

func isvowels(b byte) bool {
	return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' ||
		b == 'A' || b == 'E' || b == 'I' || b == 'O' || b == 'U'
}

#
func reverseVowels(s string) string {
	bytes := []byte(s)
	length := len(s)
	temp := make([]byte, 0)
	for i := 0; i < length; i++ {
		if isvowels(bytes[i]) {
			temp = append(temp, bytes[i])
		}
	}
	count := 0
	for i := 0; i < length; i++ {
		if isvowels(bytes[i]) {
			bytes[i] = temp[len(temp)-1-count]
			count++
		}
	}
	return string(bytes)
}

func isvowels(b byte) bool {
	return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' ||
		b == 'A' || b == 'E' || b == 'I' || b == 'O' || b == 'U'
}

349.两个数组的交集(3)¶

题目

给定两个数组，编写一个函数来计算它们的交集。
示例 1:输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2]
示例 2:输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [9,4]
说明:
    输出结果中的每个元素一定是唯一的。
    我们可以不考虑输出结果的顺序。

解题思路

No.	思路	时间复杂度	空间复杂度
01	单哈希辅助	O(n)	O(n)
02	双哈希辅助	O(n)	O(n)
03	排序双指针	O(nlog(n))	O(n)

func intersection(nums1 []int, nums2 []int) []int {
	res := make([]int, 0)
	m := make(map[int]int)
	for _, v := range nums1 {
		m[v] = 1
	}
	for _, v := range nums2 {
		if m[v] == 1 {
			res = append(res, v)
			m[v] += 1
		}
	}
	return res
}

#
func intersection(nums1 []int, nums2 []int) []int {
	m1 := make(map[int]bool)
	m2 := make(map[int]bool)
	res := make([]int, 0)
	for _, v := range nums1 {
		m1[v] = true
	}

	for _, v := range nums2 {
		if m1[v] != false {
			m2[v] = true
		}
	}

	for k := range m2 {
		res = append(res, k)
	}
	return res
}

#
func intersection(nums1 []int, nums2 []int) []int {
	sort.Ints(nums1)
	sort.Ints(nums2)
	res := make([]int, 0)
	i := 0
	j := 0
	for i < len(nums1) && j < len(nums2) {
		if nums1[i] < nums2[j] {
			i++
		} else if nums1[i] > nums2[j] {
			j++
		} else {
			if len(res) == 0 || res[len(res)-1] != nums1[i] {
				res = append(res, nums1[i])
			}
			i++
			j++
		}
	}
	return res
}

350.两个数组的交集 II(3)¶

题目

给定两个数组，编写一个函数来计算它们的交集。
示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2]  输出: [2,2]
示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [4,9]
说明：输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
     我们可以不考虑输出结果的顺序。
进阶:
    如果给定的数组已经排好序呢？你将如何优化你的算法？
    如果 nums1 的大小比 nums2 小很多，哪种方法更优？
    如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解题思路

No.	思路	时间复杂度	空间复杂度
01	单哈希辅助	O(n)	O(n)
02	双哈希辅助	O(n)	O(n)
03	排序双指针	O(nlog(n))	O(n)

func intersect(nums1 []int, nums2 []int) []int {
	m1 := make(map[int]int)
	res := make([]int, 0)
	for _, v := range nums1 {
		m1[v] += 1
	}

	for _, v := range nums2 {
		if m1[v] > 0 {
			res = append(res, v)
			m1[v]--
		}
	}
	return res
}

#
func intersect(nums1 []int, nums2 []int) []int {
	m1 := make(map[int]int)
	m2 := make(map[int]int)
	res := make([]int, 0)
	for _, v := range nums1 {
		m1[v]++
	}

	for _, v := range nums2 {
		if m1[v] != 0 && m1[v] > m2[v] {
			m2[v]++
		}
	}

	for k := range m2 {
		for i := 0; i < m2[k]; i++ {
			res = append(res, k)
		}
	}
	return res
}

#
func intersect(nums1 []int, nums2 []int) []int {
	sort.Ints(nums1)
	sort.Ints(nums2)
	res := make([]int, 0)
	i := 0
	j := 0
	for i < len(nums1) && j < len(nums2) {
		if nums1[i] < nums2[j] {
			i++
		} else if nums1[i] > nums2[j] {
			j++
		} else {
			res = append(res, nums1[i])
			i++
			j++
		}
	}
	return res
}

367.有效的完全平方数(4)¶

题目

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如  sqrt。
示例 1：输入：16 输出：True
示例 2：输入：14 输出：False

解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(log(n))	O(1)
02	牛顿迭代法	O(log(n))	O(1)
03	数学法	O(n^1/2)	O(1)
04	暴力法	O(n^1/2)	O(1)

func isPerfectSquare(num int) bool {
	if num < 2 {
		return true
	}
	left := 2
	right := num / 2
	for left <= right {
		mid := left + (right-left)/2
		if mid*mid == num {
			return true
		} else if mid*mid > num {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return false
}

#
func isPerfectSquare(num int) bool {
	if num < 2 {
		return true
	}
	x := num / 2
	for x*x > num {
		x = (x + num/x) / 2
	}
	return x*x == num
}

#
func isPerfectSquare(num int) bool {
	i := 1
	for num > 0 {
		num = num - i
		i = i + 2
	}
	return num == 0
}

#
func isPerfectSquare(num int) bool {
	i := 1
	for i * i < num{
		i++
	}
	return i * i == num
}

371.两整数之和(2)¶

题目

不使用运算符 + 和 - ，计算两整数a,b之和。
示例 1:输入: a = 1, b = 2 输出: 3
示例 2:输入: a = -2, b = 3 输出: 1

解题思路

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

func getSum(a int, b int) int {
	for b != 0 {
		a, b = a^b, (a&b)<<1
	}
	return a
}


#
func getSum(a int, b int) int {
	if b == 0 {
		return a
	}
	return getSum(a^b, (a&b)<<1)
}

374.猜数字大小(2)¶

题目

我们正在玩一个猜数字游戏。 游戏规则如下：
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。
每次你猜错了，我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：
-1 : 我的数字比较小
 1 : 我的数字比较大
 0 : 恭喜！你猜对了！
 
示例 :输入: n = 10, pick = 6 输出: 6

解题思路

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

func guessNumber(n int) int {
	low := 1
	high := n
	for low < high{
		mid := low + (high-low)/2
		if guess(mid) == 0{
			return mid
		}else if guess(mid) == 1{
			low = mid + 1
		}else {
			high = mid - 1
		}
	}
	return low
}

#
func guessNumber(n int) int {
	return binary(1, n)
}

func binary(left, right int) int {
	mid := left + (right-left)/2
	if guess(mid) == 1 {
		return binary(mid+1, right)
	} else if guess(mid) == -1 {
		return binary(left, mid-1)
	} else {
		return mid
	}
}

383.赎金信(3)¶

题目

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，
判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。
如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。
杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组辅助	O(n)	O(1)
02	哈希辅助	O(n)	O(1)
03	排序双指针	O(nlog(n))	O(n)

func canConstruct(ransomNote string, magazine string) bool {
	index := [26]int{}
	for i := 0; i < len(magazine); i++ {
		index[magazine[i]-'a']++
	}

	for i := 0; i < len(ransomNote); i++ {
		index[ransomNote[i]-'a']--
		if index[ransomNote[i]-'a'] < 0 {
			return false
		}
	}
	return true
}

#
func canConstruct(ransomNote string, magazine string) bool {
	index := make(map[uint8]int)
	for i := 0; i < len(magazine); i++ {
		index[magazine[i]-'a']++
	}

	for i := 0; i < len(ransomNote); i++ {
		index[ransomNote[i]-'a']--
		if index[ransomNote[i]-'a'] < 0 {
			return false
		}
	}
	return true
}

#
func canConstruct(ransomNote string, magazine string) bool {
	ransomNoteArr := strings.Split(ransomNote, "")
	magazineArr := strings.Split(magazine, "")
	sort.Strings(ransomNoteArr)
	sort.Strings(magazineArr)

	i := 0
	j := 0
	for i < len(ransomNoteArr) && j < len(magazineArr) {
		if ransomNoteArr[i] > magazineArr[j] {
			j++
		} else if ransomNoteArr[i] < magazineArr[j] {
			return false
		} else {
			i++
			j++
		}
	}
	return i == len(ransomNote)
}

387.字符串中的第一个唯一字符(3)¶

题目

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode"返回 0.
s = "loveleetcode",返回 2.
注意事项：您可以假定该字符串只包含小写字母。

解题思路

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

func firstUniqChar(s string) int {
	m := [26]int{}
	for i := 0; i < len(s); i++ {
		m[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if m[s[i]-'a'] == 1 {
			return i
		}
	}
	return -1
}

#
func firstUniqChar(s string) int {
	m := make(map[uint8]int)
	for i := 0; i < len(s); i++ {
		m[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if m[s[i]-'a'] == 1 {
			return i
		}
	}
	return -1
}

#
func firstUniqChar(s string) int {
	for i := 0; i < len(s); i++ {
		flag := true
		for j := 0; j < len(s); j++ {
			if s[i] == s[j] && i != j {
				flag = false
				break
			}
		}
		if flag {
			return i
		}
	}
	return -1
}

389.找不同(5)¶

题目

给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。 
示例:输入：s = "abcd"t = "abcde"输出：e
解释：'e' 是那个被添加的字母。

解题思路

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

func findTheDifference(s string, t string) byte {
	m := [26]int{}
	bytest := []byte(t)
	bytess := []byte(s)
	for _, v := range bytest {
		m[v-'a']++
	}
	for _, v := range bytess {
		m[v-'a']--
	}
	for k := range m {
		if m[k] == 1 {
			return byte(k + 'a')
		}
	}
	return 0
}

#
func findTheDifference(s string, t string) byte {
	m := make(map[byte]int)
	bytest := []byte(t)
	bytess := []byte(s)
	for _, v := range bytest {
		m[v]++
	}
	for _, v := range bytess {
		m[v]--
	}
	for k := range m {
		if m[k] == 1 {
			return k
		}
	}
	return 0
}

#
func findTheDifference(s string, t string) byte {
	ch := byte(0)
	for _, value := range s {
		ch ^= byte(value)
	}
	for _, value := range t {
		ch ^= byte(value)
	}
	return ch
}

#
func findTheDifference(s string, t string) byte {
	ch := byte(0)
	for _, value := range t {
		ch += byte(value)
	}
	for _, value := range s {
		ch -= byte(value)
	}
	return ch
}

#
func findTheDifference(s string, t string) byte {
	sArr := strings.Split(s, "")
	tArr := strings.Split(t, "")
	sort.Strings(sArr)
	sort.Strings(tArr)
	for i := 0; i < len(sArr); i++{
		if sArr[i] != tArr[i]{
			return []byte(tArr[i])[0]
		}
	}
	return []byte(tArr[len(tArr)-1])[0]
}

392.判断子序列(4)¶

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。
字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:s = "abc", t = "ahbgdc"返回 true.
示例 2:s = "axc", t = "ahbgdc"返回 false.
后续挑战 :
如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，
你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	单指针遍历	O(n^2)	O(1)
03	二分查找	O(nlog(n))	o
04	动态规划	O(n^2)	O(n^2)

func isSubsequence(s string, t string) bool {
	if len(s) > len(t){
		return false
	}
	i := 0
	j := 0
	for i < len(s) && j < len(t){
		if s[i] == t[j]{
			i++
		}
		j++
	}
	return i == len(s)
}

#
func isSubsequence(s string, t string) bool {
	for _, v := range s{
		idx := strings.IndexRune(t, v)
		if idx == -1{
			return false
		}
		t = t[idx+1:]
	}
	return true
}

#
func isSubsequence(s string, t string) bool {
	m := make(map[uint8][]int)
	for i := 0; i < len(t); i++ {
		value := t[i] - 'a'
		if m[value] == nil {
			m[value] = make([]int, 0)
		}
		m[value] = append(m[value], i)
	}
	prev := -1
	for i := 0; i < len(s); i++ {
		value := s[i] - 'a'
		left := 0
		right := len(m[value]) - 1
		if len(m[value]) == 0 {
			return false
		}
		for left < right {
			mid := left + (right-left)/2
			if m[value][mid] > prev {
				right = mid
			} else {
				left = mid + 1
			}
		}
		if left > right || m[value][left] <= prev {
			return false
		}
		prev = m[value][left]
	}
	return true
}

#
/*
状态定义: dp[i][j] 表示长度为i的字符串s是否为长度为j的字符串t的子序列
状态转移方程: 如果s[i] == t[j]， 则dp[i][j] = dp[i-1][j-1]
如果s[i] != t[j]，则dp[i][j] = dp[i][j-1]
初始: dp[0][j] = true 表示空串s 是任意长度串t的子串
dp[i][0] = false 表示任意长度非空串s 不是空串t的字串
dp[i][0] = false 表示任意长度非空串s 不是空串t的字串
*/
func isSubsequence(s string, t string) bool {
	if len(s) == 0 {
		return true
	} else if len(s) > len(t) {
		return false
	}

	dp := make([][]bool, len(s)+1)
	for i := 0; i < len(s)+1; i++ {
		dp[i] = make([]bool, len(t)+1)
		dp[i][0] = false
	}
	for i := 0; i <= len(t); i++ {
		dp[0][i] = true
	}

	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(t); j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = dp[i][j-1]
			}
		}
	}
	return dp[len(s)][len(t)]
}

0301-0400-Medium¶

304.二维区域和检索-矩阵不可变(1)¶

题目

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，
右下角为 (row2, col2)。
Range Sum Query 2D
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，
该子矩形内元素的总和为 8。
示例: 给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
说明:你可以假设矩阵不可变。
    会多次调用 sumRegion 方法。
    你可以假设 row1 ≤ row2 且 col1 ≤ col2。

解题思路

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

type NumMatrix struct {
	arr [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	if matrix == nil || len(matrix) == 0 || matrix[0] == nil || len(matrix[0]) == 0 {
		arr := make([][]int, 1)
		for i := 0; i < 1; i++ {
			arr[i] = make([]int, 1)
		}
		return NumMatrix{arr: arr}
	}
	n, m := len(matrix), len(matrix[0])
	arr := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			arr[i][j] = arr[i][j-1] + arr[i-1][j] - arr[i-1][j-1] + matrix[i-1][j-1]
		}
	}
	return NumMatrix{arr: arr}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	return this.arr[row2+1][col2+1] - this.arr[row2+1][col1] - this.arr[row1][col2+1] + this.arr[row1][col1]
}

306.累加数(1)¶

题目

累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1:输入: "112358" 输出: true 
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:输入: "199100199" 输出: true 
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
进阶:你如何处理一个溢出的过大的整数输入?

解题思路

No.	思路	时间复杂度	空间复杂度
01	回溯	O(n(log(n))^2)	O(n)

var res []int

func isAdditiveNumber(num string) bool {
	if len(num) < 3 {
		return false
	}
	res = make([]int, 0)
	dfs(num, 0, 0, 0, make([]int, 0))
	return len(res) >= 3
}

func dfs(s string, index, sum, prev int, path []int) bool {
	if index == len(s) {
		if len(path) >= 3 {
			res = path
		}
		return len(path) >= 3
	}
	value := 0
	for i := index; i < len(s); i++ {
		// 0开头不满足要求(当前i=index的时候，可以为0， 避免错过1+0=1的情况)
		if s[index] == '0' && i > index {
			break
		}
		value = value*10 + int(s[i]-'0')
		if len(path) >= 2 {
			if value < sum {
				continue
			}
			if value > sum {
				break
			}
		}
		if dfs(s, i+1, prev+value, value, append(path, value)) == true {
			return true
		}
	}
	return false
}

307.区域和检索-数组可修改(3)¶

题目

给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。
实现 NumArray 类：
NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和
（即，nums[left] + nums[left + 1], ..., nums[right]）
示例：输入： ["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出： [null, 9, null, 8]
解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 9 ，sum([1,3,5]) = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5]) = 8
提示：1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
最多调用 3 * 104 次 update 和 sumRange 方法

解题思路

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

type NumArray struct {
	arr    []int // 原数组
	b      []int // 分块和
	length int   // 分块长度
}

func Constructor(nums []int) NumArray {
	n := len(nums)
	per := int(math.Sqrt(float64(n)))
	length := int(math.Ceil(float64(n) / float64(per)))
	b := make([]int, length)
	for i := 0; i < n; i++ {
		b[i/length] = b[i/length] + nums[i]
	}
	return NumArray{
		arr:    nums,
		b:      b,
		length: length,
	}
}

func (this *NumArray) Update(i int, val int) {
	index := i / this.length
	this.b[index] = this.b[index] - this.arr[i] + val
	this.arr[i] = val
}

func (this *NumArray) SumRange(i int, j int) int {
	res := 0
	a, b := i/this.length, j/this.length
	if a == b {
		for k := i; k <= j; k++ {
			res = res + this.arr[k]
		}
	} else {
		// 分3段
		for k := i; k <= (a+1)*this.length-1; k++ {
			res = res + this.arr[k]
		}
		for k := a + 1; k <= b-1; k++ {
			res = res + this.b[k]
		}
		for k := b * this.length; k <= j; k++ {
			res = res + this.arr[k]
		}
	}
	return res
}

# 2
type NumArray struct {
	origin []int // 原数组
	arr    []int // 线段树
	length int   // 长度
}

func Constructor(nums []int) NumArray {
	n := len(nums)
	arr := make([]int, 4*n+1)
	res := NumArray{
		origin: nums,
		arr:    arr,
		length: n,
	}
	for i := 0; i < n; i++ {
		res.UpdateArr(0, 1, res.length, i+1, nums[i]) // 从1开始，添加nums[i]
	}
	return res
}

func (this *NumArray) Update(index int, val int) {
	val, this.origin[index] = val-this.origin[index], val // 需要变更的大小
	this.UpdateArr(0, 1, this.length, index+1, val)       // 从1开始
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.Query(0, 1, this.length, left+1, right+1) // 范围+1
}

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

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

# 3
type NumArray struct {
	origin []int // 原数组
	c      []int // 树状数组
	length int   // 长度
}

func Constructor(nums []int) NumArray {
	n := len(nums)
	arr := make([]int, n+1)
	res := NumArray{
		origin: nums,
		c:      arr,
		length: n,
	}
	// 单点修改
	for i := 0; i < n; i++ {
		res.UpData(i+1, nums[i]) // 注意下标，默认数组是从1开始
	}
	return res
}

func (this *NumArray) Update(index int, val int) {
	if index < 0 || index > this.length-1 {
		return
	}
	val, this.origin[index] = val-this.origin[index], val // 需要变更的大小
	this.UpData(index+1, val)
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.GetSum(right+1) - this.GetSum(left)
}

func (this *NumArray) LowBit(x int) int {
	return x & (-x)
}

// 单点修改
func (this *NumArray) UpData(i, k int) { // 在i位置加上k
	for i <= this.length {
		this.c[i] = this.c[i] + k
		i = i + this.LowBit(i) // i = i + 2^k
	}
}

// 区间查询
func (this *NumArray) GetSum(i int) int {
	res := 0
	for i > 0 {
		res = res + this.c[i]
		i = i - this.LowBit(i)
	}
	return res
}

309.最佳买卖股票时机含冷冻期(2)¶

题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
    你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:输入: [1,2,3,0,2] 输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划-二维	O(n)	O(n)
02	动态规划	O(n)	O(1)

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	n := len(prices)
	dp := make([][3]int, n)
	// 0 => 持有
	// 1 => 不持有，本日卖出，下一日冷冻期
	// 2 => 不持有，本日无卖出，下一日不是冷冻期
	dp[0][0] = -prices[0] // 第0天买入，亏损-price[0]
	for i := 1; i < n; i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i]) // 继续持有 or 可以操作，继续买入，导致今天持有股票
		dp[i][1] = dp[i-1][0] + prices[i]                // 卖出操作
		dp[i][2] = max(dp[i-1][1], dp[i-1][2])           // 昨天卖出，无股票，今天是冷冻期 or 昨天没股票，也不操作
	}
	return max(dp[n-1][1], dp[n-1][2]) // 最后一天操作，会导致利润变少，可以忽略
	// return max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]))
}

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

# 2
func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	n := len(prices)
	// a => 持有
	// b => 不持有，本日卖出，下一日冷冻期
	// c => 不持有，本日无卖出，下一日不是冷冻期
	var a, b, c int
	a = -prices[0] // 第0天买入，亏损-price[0]
	for i := 1; i < n; i++ {
		A := max(a, c-prices[i]) // 继续持有 or 可以操作，继续买入，导致今天持有股票
		B := a + prices[i]       // 卖出操作
		C := max(b, c)           // 昨天卖出，无股票，今天是冷冻期 or 昨天没股票，也不操作
		a, b, c = A, B, C
	}
	return max(b, c)
}

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

310.最小高度树(1)¶

题目

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
给你一棵包含n个节点的数，标记为0到n - 1 。
给定数字n和一个有 n - 1 条无向边的 edges列表（每一个边都是一对标签），
其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。
在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
示例 1：输入：n = 4, edges = [[1,0],[1,2],[1,3]] 输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
示例 2：输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] 输出：[3,4]
示例 3：输入：n = 1, edges = [] 输出：[0]
示例 4：输入：n = 2, edges = [[0,1]] 输出：[0,1]
提示：1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
所有 (ai, bi) 互不相同
给定的输入 保证 是一棵树，并且 不会有重复的边

解题思路

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

func findMinHeightTrees(n int, edges [][]int) []int {
	if n == 1 {
		return []int{0}
	}
	if n == 2 {
		return []int{0, 1}
	}
	m := make(map[int][]int)
	degree := make([]int, n)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		m[a] = append(m[a], b)
		m[b] = append(m[b], a)
		degree[a]++
		degree[b]++
	}
	// 从叶子节点开始遍历
	queue := make([]int, 0)
	for i := 0; i < n; i++ {
		if degree[i] == 1 {
			queue = append(queue, i)
		}
	}

	for n > 2 {
		total := len(queue)
		n = n - total
		for i := 0; i < total; i++ {
			node := queue[i]
			degree[node] = 0
			for j := 0; j < len(m[node]); j++ {
				temp := m[node][j]
				if degree[temp] > 0 {
					degree[temp]--
					if degree[temp] == 1 {
						queue = append(queue, temp)
					}
				}
			}
		}
		queue = queue[total:]
	}
	res := make([]int, 0)
	for i := 0; i < len(queue); i++ {
		res = append(res, queue[i])
	}
	return res
}

313.超级丑数(2)¶

题目

编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为k的质数列表primes中的正整数。
示例:输入: n = 12, primes = [2,7,13,19] 输出: 32 
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
说明:1是任何给定primes的超级丑数。
给定primes中的数字以升序排列。
0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
第n个超级丑数确保在 32 位有符整数范围内。

解题思路

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

func nthSuperUglyNumber(n int, primes []int) int {
	if n == 0 || n == 1 {
		return n
	}
	intHeap := &IntHeap{}
	heap.Init(intHeap)
	heap.Push(intHeap, 1)
	n--
	for n > 0 {
		x := heap.Pop(intHeap).(int)
		for intHeap.Len() > 0 && x == (*intHeap)[0] {
			heap.Pop(intHeap)
		}
		for i := 0; i < len(primes); i++ {
			heap.Push(intHeap, x*primes[i])
		}
		n--
	}
	return heap.Pop(intHeap).(int)
}

type IntHeap []int

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

func (h IntHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

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

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

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

# 2
func nthSuperUglyNumber(n int, primes []int) int {
	arr := make([]int, n)
	arr[0] = 1
	times := make([]int, len(primes))
	for i := 1; i < n; i++ {
		next := math.MaxInt32
		for j, value := range times {
			next = min(next, primes[j]*arr[value])
		}
		for j, value := range times {
			if primes[j]*arr[value] == next {
				times[j]++
			}
		}
		arr[i] = next
	}
	return arr[n-1]
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

318.最大单词长度乘积(2)¶

题目

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，
并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1:输入: ["abcw","baz","foo","bar","xtfn","abcdef"] 输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。
示例 2:输入: ["a","ab","abc","d","cd","bcd","abcd"] 输出: 4 
解释: 这两个单词为 "ab", "cd"。
示例 3:输入: ["a","aa","aaa","aaaa"] 输出: 0 
解释: 不存在这样的两个单词。

解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数	O(n^3)	O(1)
02	位运算	O(n^2)	O(n)

func maxProduct(words []string) int {
	res := 0
	for i := 0; i < len(words); i++ {
		for j := i + 1; j < len(words); j++ {
			if strings.ContainsAny(words[i], words[j]) == false && 
				res < len(words[i])*len(words[j]) {
				res = len(words[i]) * len(words[j])
			}
		}
	}
	return res
}

# 2
func maxProduct(words []string) int {
	res := 0
	arr := make([]int, len(words))
	for i := 0; i < len(words); i++ {
		for _, char := range words[i] {
			// 位或 只要有1，那么就是1
			arr[i] = arr[i] | 1<<uint(char-'a')
		}
	}
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			if arr[i]&arr[j] == 0 && res < len(words[i])*len(words[j]) {
				res = len(words[i]) * len(words[j])
			}
		}
	}
	return res
}

319.灯泡开关(1)¶

题目

初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 
第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。
第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 
找出 n 轮后有多少个亮着的灯泡。
示例:输入: 3输出: 1 
解释: 初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 
你应该返回 1，因为只有一个灯泡还亮着。

解题思路

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

func bulbSwitch(n int) int {
	// 第i个灯泡的反转次数等于它所有因子（包括1和i）的个数
	// 反转奇数次=>变成亮
	// 只有平方数才有奇数个因子
	return int(math.Sqrt(float64(n)))
}

322.零钱兑换(4)¶

题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:输入: coins = [1, 2, 5], amount = 11 输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:输入: coins = [2], amount = 3 输出: -1
说明:你可以认为每种硬币的数量是无限的。

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n)
02	动态规划	O(n^2)	O(n)
03	深度优先搜索	O(n^k)	O(n)
04	广度优先搜索	O(n)	O(n)

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = -1
		for j := 0; j < len(coins); j++ {
			prev := i - coins[j]
			if i < coins[j] || dp[prev] == -1 {
				continue
			}
			if dp[i] == -1 || dp[i] > dp[prev]+1 {
				dp[i] = dp[prev] + 1
			}
		}
	}
	return dp[amount]
}

# 2
func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := 0; i <= amount; i++ {
		dp[i] = amount + 1
	}
	dp[0] = 0
	for i := 0; i < len(coins); i++ {
		for j := coins[i]; j < amount+1; j++ {
			dp[j] = min(dp[j], dp[j-coins[i]]+1)
		}
	}
	if dp[amount] == amount+1 {
		return -1
	}
	return dp[amount]
}

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

# 3
var res int

func coinChange(coins []int, amount int) int {
	for i := 0; i < len(coins); i++ {
		for j := 0; j < len(coins)-1-i; j++ {
			if coins[j] < coins[j+1] {
				coins[j], coins[j+1] = coins[j+1], coins[j]
			}
		}
	}
	res = math.MaxInt32
	dfs(coins, amount, 0, 0)
	if res == math.MaxInt32 {
		return -1
	}
	return res
}

func dfs(coins []int, amount int, count int, level int) {
	if amount == 0 {
		res = min(res, count)
		return
	}
	if level == len(coins) {
		return
	}
	for i := amount / coins[level]; i >= 0 && i+count < res; i-- {
		dfs(coins, amount-i*coins[level], count+i, level+1)
	}
}

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

# 4
func coinChange(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}
	res := 1
	sort.Ints(coins)
	list := make([]int, 0)
	list = append(list, amount)
	arr := make([]bool, amount+1)
	arr[amount] = true
	for len(list) > 0 {
		length := len(list)
		for i := 0; i < length; i++ {
			value := list[i]
			for j := 0; j < len(coins); j++ {
				next := value - coins[j]
				if next == 0 {
					return res
				}
				if next < 0 {
					break
				}
				if arr[next] == false {
					list = append(list, next)
					arr[next] = true
				}
			}
		}
		list = list[length:]
		res++
	}
	return -1
}

324.摆动排序II(2)¶

题目

给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 1:输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:输入: nums = [1, 3, 2, 2, 3, 1] 输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明: 你可以假设所有输入都会得到有效的结果。
进阶:你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

解题思路

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

func wiggleSort(nums []int) {
	arr := make([]int, len(nums))
	copy(arr, nums)
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] > arr[j]
	})
	a := 1
	for i := 0; i < len(arr)/2; i++ {
		nums[a] = arr[i]
		a = a + 2
	}
	a = 0
	for i := len(arr) / 2; i < len(arr); i++ {
		nums[a] = arr[i]
		a = a + 2
	}
}

# 2
func wiggleSort(nums []int) {
	arr := make([]int, len(nums))
	copy(arr, nums)
	sort.Ints(arr)
	j := len(nums)
	k := (len(nums) + 1) / 2
	for i := 0; i < len(nums); i++ {
		if i%2 == 1 {
			j--
			nums[i] = arr[j]
		} else {
			k--
			nums[i] = arr[k]
		}
	}
}

328.奇偶链表(3)¶

题目

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL
示例 2:输入: 2->1->3->5->6->4->7->NULL  输出: 2->3->6->7->1->5->4->NULL
说明:应当保持奇数节点和偶数节点的相对顺序。
    链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

解题思路

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

func oddEvenList(head *ListNode) *ListNode {
	odd := &ListNode{}
	even := &ListNode{}
	a := odd
	b := even
	count := 1
	for head != nil {
		if count%2 == 1 {
			a.Next = head
			a = head
		} else {
			b.Next = head
			b = head
		}
		count++
		head = head.Next
	}
	b.Next = nil
	a.Next = even.Next
	return odd.Next
}

# 2
func oddEvenList(head *ListNode) *ListNode {
	odd := make([]*ListNode, 0)
	even := make([]*ListNode, 0)
	count := 1
	for head != nil {
		if count%2 == 1 {
			odd = append(odd, head)
		} else {
			even = append(even, head)
		}
		count++
		head = head.Next
	}
	temp := &ListNode{}
	node := temp
	for i := 0; i < len(odd); i++ {
		node.Next = odd[i]
		node = node.Next
	}
	for i := 0; i < len(even); i++ {
		node.Next = even[i]
		node = node.Next
	}
	node.Next = nil
	return temp.Next
}

# 3
func oddEvenList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	temp := head.Next // 第一个偶数
	odd, even := head, temp
	for odd.Next != nil && even.Next != nil {
		odd.Next = even.Next
		odd = odd.Next
		even.Next = odd.Next
		even = even.Next
	}
	odd.Next = temp // 第一个偶数接入奇数尾部
	return head
}

331.验证二叉树的前序序列化(2)¶

题目

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。
如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例 1:输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true
示例 2:输入: "1,#" 输出: false
示例 3:输入: "9,#,#,1" 输出: false

解题思路

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

func isValidSerialization(preorder string) bool {
	arr := strings.Split(preorder, ",")
	slot := 1
	for i := 0; i < len(arr); i++ {
		slot--
		if slot < 0 {
			return false
		}
		if arr[i] != "#" {
			slot = slot + 2
		}
	}
	return slot == 0
}

# 2
func isValidSerialization(preorder string) bool {
	arr := strings.Split(preorder, ",")
	stack := make([]string, 0)
	for i := 0; i < len(arr); i++ {
		for len(stack) > 0 && stack[len(stack)-1] == "#" && arr[i] == "#" {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				return false
			}
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, arr[i])
	}
	return len(stack) == 1 && stack[0] == "#"
}

332.重新安排行程(1)¶

题目

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，
对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，
所以该行程必须从 JFK 开始。
提示：如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。
例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
所有的机票必须都用一次 且 只能用一次。
示例 1：输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出：["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2：输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

解题思路

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

var m map[string][]string
var res []string

func findItinerary(tickets [][]string) []string {
	res = make([]string, 0)
	m = make(map[string][]string)
	for i := 0; i < len(tickets); i++ {
		a, b := tickets[i][0], tickets[i][1]
		m[a] = append(m[a], b)
	}
	for _, v := range m {
		sort.Strings(v)
	}
	dfs("JFK")
	left, right := 0, len(res)-1
	for left < right {
		res[left], res[right] = res[right], res[left]
		left++
		right--
	}
	return res
}

func dfs(start string) {
	for len(m[start]) > 0 {
		node := m[start][0]
		m[start] = m[start][1:]
		dfs(node)
	}
	res = append(res, start)
}

334.递增的三元子序列(4)¶

题目

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
    如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1，
    使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。
示例 1:输入: [1,2,3,4,5] 输出: true
示例 2:输入: [5,4,3,2,1] 输出: false

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	数组辅助	O(n)	O(n)
03	动态规划	O(n)	O(n)
04	暴力法	O(n^3)	O(1)

func increasingTriplet(nums []int) bool {
	a, b := math.MaxInt32, math.MaxInt32
	for i := 0; i < len(nums); i++ {
		if a >= nums[i] {
			a = nums[i]
		} else if b >= nums[i] {
			b = nums[i]
		} else {
			return true
		}
	}
	return false
}

# 2
func increasingTriplet(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	a := make([]int, len(nums))
	b := make([]int, len(nums))
	a[0] = nums[0]
	b[len(b)-1] = nums[len(nums)-1]
	for i := 1; i < len(nums); i++ {
		a[i] = min(a[i-1], nums[i])
	}
	for i := len(nums) - 2; i >= 0; i-- {
		b[i] = max(b[i+1], nums[i])
	}
	for i := 0; i < len(nums); i++ {
		if a[i] < nums[i] && nums[i] < b[i] {
			return true
		}
	}
	return false
}

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
}

# 3
func increasingTriplet(nums []int) bool {
	dp := make([]int, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		if dp[i] >= 2 {
			return true
		}
	}
	return false
}

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

# 4
func increasingTriplet(nums []int) bool {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] >= nums[j] {
				continue
			}
			for k := j + 1; k < len(nums); k++ {
				if nums[j] < nums[k] {
					return true
				}
			}
		}
	}
	return false
}

337.打家劫舍III(1)¶

题目

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
这个地区只有一个入口，我们称之为“根”。 
除了“根”之外，每栋房子有且只有一个“父“房子与之相连。
一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 
如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:输入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:输入: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
输出: 9解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解题思路

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

func rob(root *TreeNode) int {
	a, b := dfs(root)
	return max(a, b)
}

func dfs(root *TreeNode) (int, int) {
	if root == nil {
		return 0, 0
	}
	leftA, leftB := dfs(root.Left)
	rightA, rightB := dfs(root.Right)
	a := root.Val + leftB + rightB               // A=>偷
	b := max(leftA, leftB) + max(rightA, rightB) // B=>不偷
	return a, b
}

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

338.比特位计数(4)¶

题目

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，
计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:输入: 2 输出: [0,1,1]
示例 2:输入: 5 输出: [0,1,1,2,1,2]
进阶:给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数
（如 C++ 中的 __builtin_popcount）来执行此操作。

解题思路

No.	思路	时间复杂度	空间复杂度
01	位运算	O(n)	O(n)
02	动态规划	O(n)	O(n)
03	暴力法	O(n)	O(n)
04	内置函数	O(n)	O(n)

func countBits(num int) []int {
	res := make([]int, num+1)
	for i := 1; i <= num; i++ {
		res[i] = res[i&(i-1)] + 1
	}
	return res
}

# 2
func countBits(num int) []int {
	res := make([]int, num+1)
	for i := 1; i <= num; i++ {
		if i%2 == 0 {
			res[i] = res[i/2]
		} else {
			res[i] = res[i-1] + 1
		}
	}
	return res
}

# 3
func countBits(num int) []int {
	res := make([]int, 0)
	for i := 0; i <= num; i++ {
		count := 0
		value := i
		for value != 0 {
			if value%2 == 1 {
				count++
			}
			value = value / 2
		}
		res = append(res, count)
	}
	return res
}

# 4
func countBits(num int) []int {
	res := make([]int, 0)
	for i := 0; i <= num; i++ {
		count := bits.OnesCount(uint(i))
		res = append(res, count)
	}
	return res
}

341.扁平化嵌套列表迭代器(2)¶

题目

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
示例 1:输入: [[1,1],2,[1,1]] 输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:输入: [1,[4,[6]]] 输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

解题思路

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

type NestedIterator struct {
	arr []*NestedInteger
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	return &NestedIterator{arr: nestedList}
}

func (this *NestedIterator) Next() int {
	value := this.arr[0]
	this.arr = this.arr[1:]
	return value.GetInteger()
}

func (this *NestedIterator) HasNext() bool {
	if len(this.arr) == 0 {
		return false
	}
	if this.arr[0].IsInteger() {
		return true
	}
	this.arr = append(this.arr[0].GetList(), this.arr[1:]...)
	return this.HasNext()
}

# 2
type NestedIterator struct {
	arr []int
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	arr := getList(nestedList)
	return &NestedIterator{arr: arr}
}

func getList(nestedList []*NestedInteger) []int {
	res := make([]int, 0)
	for i := 0; i < len(nestedList); i++ {
		if nestedList[i].IsInteger() == true {
			res = append(res, nestedList[i].GetInteger())
		} else {
			res = append(res, getList(nestedList[i].GetList())...)
		}
	}
	return res
}
func (this *NestedIterator) Next() int {
	value := this.arr[0]
	this.arr = this.arr[1:]
	return value
}

func (this *NestedIterator) HasNext() bool {
	return len(this.arr) > 0
}

343.整数拆分(2)¶

题目

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:输入: 2 输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:输入: 10 输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

解题思路

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

func integerBreak(n int) int {
	if n < 2 {
		return 0
	}
	if n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	dp[2] = 2
	dp[3] = 3
	for i := 4; i <= n; i++ {
		max := 0
		for j := 1; j <= i/2; j++ {
			length := dp[j] * dp[i-j]
			if length > max {
				max = length
			}
			dp[i] = max
		}
	}
	return dp[n]
}

#
func integerBreak(n int) int {
	if n < 2 {
		return 0
	}
	if n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}
	timesOf3 := n / 3
	if n-timesOf3*3 == 1 {
		timesOf3 = timesOf3 - 1
	}
	timesOf2 := (n - timesOf3*3) / 2
	return int(math.Pow(float64(2), float64(timesOf2))) *
		int(math.Pow(float64(3), float64(timesOf3)))
}

347.前K个高频元素(3)¶

题目

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:输入: nums = [1], k = 1 输出: [1]
提示：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
    你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
    题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
    你可以按任意顺序返回答案。

解题思路

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

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

# 2
func topKFrequent(nums []int, k int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	var h IntHeap
	heap.Init(&h)
	for k, v := range m {
		heap.Push(&h, [2]int{k, v})
	}
	res := make([]int, 0)
	for h.Len() > 0 && k > 0 {
		k--
		node := heap.Pop(&h).([2]int)
		res = append(res, node[0])
	}
	return res
}

type IntHeap [][2]int

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

# 3
func topKFrequent(nums []int, k int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	arr := make([][]int, len(nums)+1)
	temp := make(map[int][]int)
	for key, value := range m {
		temp[value] = append(temp[value], key)
		arr[value] = append(arr[value], key)
	}
	res := make([]int, 0)
	for i := len(arr) - 1; i >= 0; i-- {
		// 避免出现0=>x次的情况
		if _, ok := temp[i]; ok {
			for j := 0; j < len(arr[i]); j++ {
				k--
				if k < 0 {
					break
				}
				res = append(res, arr[i][j])
			}
		}
	}
	return res
}

355.设计推特(2)¶

题目

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，
能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：
postTweet(userId, tweetId): 创建一条新的推文
getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。
推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId): 关注一个用户
unfollow(followerId, followeeId): 取消关注一个用户
示例:Twitter twitter = new Twitter();
// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
twitter.postTweet(1, 5);
// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
twitter.getNewsFeed(1);
// 用户1关注了用户2.
twitter.follow(1, 2);
// 用户2发送了一个新推文 (推文id = 6).
twitter.postTweet(2, 6);
// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
// 推文id6应当在推文id5之前，因为它是在5之后发送的.
twitter.getNewsFeed(1);
// 用户1取消关注了用户2.
twitter.unfollow(1, 2);
// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
// 因为用户1已经不再关注用户2.
twitter.getNewsFeed(1);

解题思路

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

type Twitter struct {
	data [][2]int
	m    map[int]map[int]int
}

func Constructor() Twitter {
	return Twitter{
		data: make([][2]int, 0),
		m:    make(map[int]map[int]int),
	}
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
	this.data = append(this.data, [2]int{userId, tweetId})
}

func (this *Twitter) GetNewsFeed(userId int) []int {
	res := make([]int, 0)
	for i := len(this.data) - 1; i >= 0; i-- { // 遍历发表的列表
		id, tid := this.data[i][0], this.data[i][1]
		if id == userId || this.m[userId][id] > 0 {
			res = append(res, tid)
		}
		if len(res) == 10 {
			return res
		}
	}
	return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
	if this.m[followerId] == nil {
		this.m[followerId] = make(map[int]int)
	}
	this.m[followerId][followeeId] = 1
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
	if this.m[followerId] != nil {
		this.m[followerId][followeeId] = 0
	}
}

# 2
type Twitter struct {
	data  map[int][][2]int
	m     map[int]map[int]int
	count int
}

func Constructor() Twitter {
	return Twitter{
		data:  make(map[int][][2]int),
		m:     make(map[int]map[int]int),
		count: 0,
	}
}

func (this *Twitter) PostTweet(userId int, tweetId int) {
	this.data[userId] = append(this.data[userId], [2]int{this.count, tweetId})
	this.count++
}

func (this *Twitter) GetNewsFeed(userId int) []int {
	res := make([]int, 0)
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := len(this.data[userId]) - 1; i >= 0; i-- {
		a, b := this.data[userId][i][0], this.data[userId][i][1]
		if intHeap.Len() == 10 && intHeap[0][0] > a {
			break
		}
		heap.Push(&intHeap, [2]int{a, b})
		if intHeap.Len() > 10 {
			heap.Pop(&intHeap)
		}
	}
	for k, v := range this.m[userId] {
		if k == userId || v == 0 {
			continue
		}
		for i := len(this.data[k]) - 1; i >= 0; i-- {
			a, b := this.data[k][i][0], this.data[k][i][1]
			if intHeap.Len() == 10 && intHeap[0][0] > a {
				break
			}
			heap.Push(&intHeap, [2]int{a, b})
			if intHeap.Len() > 10 {
				heap.Pop(&intHeap)
			}
		}
	}
	for intHeap.Len() > 0 {
		node := heap.Pop(&intHeap).([2]int)
		res = append([]int{node[1]}, res...)
	}
	return res
}

func (this *Twitter) Follow(followerId int, followeeId int) {
	if this.m[followerId] == nil {
		this.m[followerId] = make(map[int]int)
	}
	this.m[followerId][followeeId] = 1
}

func (this *Twitter) Unfollow(followerId int, followeeId int) {
	if this.m[followerId] != nil {
		this.m[followerId][followeeId] = 0
	}
}

type IntHeap [][2]int

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

357.计算各个位数不同的数字个数(3)¶

题目

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n。
示例:输入: 2 输出: 91 
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

解题思路

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

func countNumbersWithUniqueDigits(n int) int {
	if n == 0 {
		return 1
	}
	dp := make([]int, n+10)
	dp[1] = 10
	prev := 9
	/*
		n = 1, 1+9
		n = 2, 1+9+9*9
		n = 3, 1+9+9*9+9*9*8
		n = 4, 1+9+9*9+9*9*8+9*9*8*7
	*/
	for i := 2; i <= 10; i++ {
		dp[i] = dp[i-1] + 9*prev
		prev = prev * (10 - i)
	}
	if n >= 10 {
		return dp[10]
	}
	return dp[n]
}

# 2
func countNumbersWithUniqueDigits(n int) int {
	if n == 0 {
		return 1
	}
	res := 1
	prev := 1
	for i := 1; i <= 10 && i <= n; i++ {
		res = res + 9*prev
		prev = prev * (10 - i)
	}
	return res
}

# 3
func countNumbersWithUniqueDigits(n int) int {
	if n == 0 {
		return 1
	}
	return dfs(n, 0, make([]bool, 10))
}

func dfs(n, index int, visited []bool) int {
	if index == n {
		return 0
	}
	res := 0
	for i := 0; i < 10; i++ {
		if n >= 2 && index == 1 && i == 0 {
			continue
		}
		if visited[i] == true {
			continue
		}
		visited[i] = true
		res = res + dfs(n, index+1, visited) + 1
		visited[i] = false
	}
	return res
}

365.水壶问题(3)¶

题目

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。
请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
    装满任意一个水壶
    清空任意一个水壶
    从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4  输出: True
示例 2:输入: x = 2, y = 6, z = 5 输出: False

解题思路

No.	思路	时间复杂度	空间复杂度
01	数学	O(log(n))	O(1)
02	递归	O(log(n))	O(log(n))
03	广度优先搜索	O(n^2)	O(n^2)

// ax+by=z
func canMeasureWater(x int, y int, z int) bool {
	if x > y {
		x, y = y, x
	}
	if x+y < z {
		return false
	}
	if x == 0 || y == 0 {
		return z == 0 || x+y == z
	}
	return z%gcd(x, y) == 0
}

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

# 2
func canMeasureWater(x int, y int, z int) bool {
	if z == 0 || z == x+y {
		return true
	} else if z > x+y || y == 0 {
		return false
	}
	return canMeasureWater(y, x%y, z%y)
}

# 3
func canMeasureWater(x int, y int, z int) bool {
	if x+y < z {
		return false
	}
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	m := make(map[[2]int]bool)
	for len(queue) > 0 {
		a, b := queue[0][0], queue[0][1]
		queue = queue[1:]
		if m[[2]int{a, b}] == true {
			continue
		}
		m[[2]int{a, b}] = true
		if a == z || b == z || a+b == z {
			return true
		}
		// +x
		c, d := x, b
		queue = append(queue, [2]int{c, d})
		// +y
		c, d = a, y
		queue = append(queue, [2]int{c, d})
		// -x
		c, d = 0, b
		queue = append(queue, [2]int{c, d})
		// -y
		c, d = a, 0
		queue = append(queue, [2]int{c, d})
		// x->y
		if a > y-b {
			c, d = a+b-y, y
			queue = append(queue, [2]int{c, d})
		} else {
			c, d = 0, a+b
			queue = append(queue, [2]int{c, d})
		}
		// y->x
		if b > x-a {
			c, d = x, a+b-x
			queue = append(queue, [2]int{c, d})
		} else {
			c, d = a+b, 0
			queue = append(queue, [2]int{c, d})
		}
	}
	return false
}

368.最大整除子集(1)¶

题目

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：
Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:输入: [1,2,3] 输出: [1,2] (当然, [1,3] 也正确)
示例 2:输入: [1,2,4,8] 输出: [1,2,4,8]

解题思路

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

func largestDivisibleSubset(nums []int) []int {
	n := len(nums)
	if n < 2 {
		return nums
	}
	sort.Ints(nums)
	dp := make([][]int, n)
	dp[0] = append(dp[0], nums[0])
	resLength := 0
	index := 0
	for i := 1; i < n; i++ {
		maxLength := 0
		arr := make([]int, 0)
		for j := 0; j < i; j++ {
			// 可除以整除集合中的最大值=>属于该集合
			if nums[i]%nums[j] == 0 && len(dp[j]) >= maxLength {
				maxLength = len(dp[j])
				arr = dp[j]
			}
		}
		dp[i] = append(dp[i], append(arr, nums[i])...)
		if len(dp[i]) > resLength {
			resLength = len(dp[i])
			index = i
		}
	}
	return dp[index]
}

372.超级次方(2)¶

题目

你的任务是计算ab对1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例 1：输入：a = 2, b = [3] 输出：8
示例 2：输入：a = 2, b = [1,0] 输出：1024
示例 3：输入：a = 1, b = [4,3,3,8,5,2] 输出：1
示例 4：输入：a = 2147483647, b = [2,0,0] 输出：1198
提示：1 <= a <= 231 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

解题思路

No.	思路	时间复杂度	空间复杂度
01	快速幂	O(nlog(n))	O(n)
02	快速幂	O(nlog(n))	O(1)

var mod int = 1337

func superPow(a int, b []int) int {
	a = a % mod
	if len(b) == 0 {
		return 1
	}
	x := mypow(a, b[len(b)-1])
	y := mypow(superPow(a, b[:len(b)-1]), 10)
	return x * y % mod
}

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

# 2
var mod int = 1337

func superPow(a int, b []int) int {
	a = a % mod
	if len(b) == 0 {
		return 1
	}
	res := 1
	for i := 0; i < len(b); i++ {
		res = mypow(res, 10) * mypow(a, b[i]) % mod
	}
	return res
}

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

373.查找和最小的K对数字(2)¶

题目

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自 nums2。
找到和最小的 k 对数字(u1,v1), (u2,v2) ... (uk,vk)。
示例 1:输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
    [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:输入: nums1 = [1,2], nums2 = [3], k = 3  输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

解题思路

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

func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
	Heap := &NodeHeap{}
	heap.Init(Heap)
	for i := 0; i < len(nums1); i++ {
		for j := 0; j < len(nums2); j++ {
			heap.Push(Heap, Node{
				i: nums1[i],
				j: nums2[j],
			})
			if Heap.Len() > k {
				heap.Pop(Heap)
			}
		}
	}
	res := make([][]int, 0)
	for Heap.Len() > 0 {
		node := heap.Pop(Heap).(Node)
		res = append(res, []int{node.i, node.j})
	}
	return res
}

type Node struct {
	i int
	j int
}

type NodeHeap []Node

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

func (h NodeHeap) Less(i, j int) bool {
	return h[i].i+h[i].j > h[j].i+h[j].j
}

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

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

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

# 2
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
	arr := make([][]int, 0)
	for i := 0; i < len(nums1); i++ {
		for j := 0; j < len(nums2); j++ {
			arr = append(arr, []int{nums1[i], nums2[j]})
		}
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][0]+arr[i][1] < arr[j][0]+arr[j][1]
	})
	if len(arr) < k {
		return arr
	}
	return arr[:k]
}

375.猜数字大小II(3)¶

题目

我们正在玩一个猜数游戏，游戏规则如下：
我从1到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。
直到你猜到我选的数字，你才算赢得了这个游戏。
示例:n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

解题思路

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

func getMoneyAmount(n int) int {
	dp := make([][]int, n+1) // 表示从[i,j]之间选择一个数字来猜，你确保获胜所需要的最少现金
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := n; i >= 1; i-- {
		for j := i + 1; j <= n; j++ {
			minValue := math.MaxInt32
			for k := i; k < j; k++ { // 可以选择[i-j]，其中最小值
				minValue = min(minValue, max(dp[i][k-1], dp[k+1][j])+k)
			}
			dp[i][j] = minValue
		}
	}
	return dp[1][n]
}

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 getMoneyAmount(n int) int {
	dp := make([][]int, n+1) // 表示从[i,j]之间选择一个数字来猜，你确保获胜所需要的最少现金
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := 2; i <= n; i++ {
		for j := 1; j+i-1 <= n; j++ {
			minValue := math.MaxInt32
			for k := j; k < i+j-1; k++ { // 可以选择[i-j]，其中最小值
				minValue = min(minValue, max(dp[j][k-1], dp[k+1][i+j-1])+k)
			}
			dp[j][i+j-1] = minValue
		}
	}
	return dp[1][n]
}

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
}

# 3
var dp [][]int

func getMoneyAmount(n int) int {
	dp = make([][]int, n+1) // 表示从[i,j]之间选择一个数字来猜，你确保获胜所需要的最少现金
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	return dfs(1, n)
}

func dfs(start, end int) int {
	if start >= end {
		return 0
	}
	if dp[start][end] > 0 {
		return dp[start][end]
	}
	minValue := math.MaxInt32
	for i := start; i <= end; i++ {
		res := i + max(dfs(i+1, end), dfs(start, i-1))
		minValue = min(minValue, res)
	}
	dp[start][end] = minValue
	return minValue
}

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
}

376.摆动序列(3)¶

题目

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。
第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如，[1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3)是正负交替出现的。
相反, [1,4,7,2,5]和[1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，
第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 
通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:输入: [1,7,4,9,2,5] 输出: 6 
解释: 整个序列均为摆动序列。
示例 2:输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:输入: [1,2,3,4,5,6,7,8,9] 输出: 2
进阶:你能否用O(n) 时间复杂度完成此题?

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n)	O(n)
02	动态规划	O(n)	O(1)
03	贪心	O(n)	O(1)

func wiggleMaxLength(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}
	up := make([]int, n)   // 以前i个元素中的某一个为结尾的最长的上升摆动序列的长度
	down := make([]int, n) // 以前i个元素中的某一个为结尾的最长的下降摆动序列的长度。
	up[0] = 1
	down[0] = 1
	for i := 1; i < n; i++ {
		if nums[i-1] < nums[i] { // 递增
			up[i] = max(up[i-1], down[i-1]+1)
			down[i] = down[i-1]
		} else if nums[i-1] > nums[i] { // 递减
			up[i] = up[i-1]
			down[i] = max(up[i-1]+1, down[i-1])
		} else {
			up[i] = up[i-1]
			down[i] = down[i-1]
		}
	}
	return max(up[n-1], down[n-1])
}

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

# 2
func wiggleMaxLength(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}
	up := 1   // 以前i个元素中的某一个为结尾的最长的上升摆动序列的长度
	down := 1 // 以前i个元素中的某一个为结尾的最长的下降摆动序列的长度。
	for i := 1; i < n; i++ {
		if nums[i-1] < nums[i] { // 递增
			up = down + 1
		} else if nums[i-1] > nums[i] { // 递减

			down = up + 1
		}
	}
	return max(up, down)
}

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

# 3
func wiggleMaxLength(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}
	res := 1
	diff := nums[1] - nums[0]
	if diff != 0 {
		res = 2
	}
	for i := 2; i < n; i++ {
		newDiff := nums[i] - nums[i-1]
		if (diff >= 0 && newDiff < 0) ||
			(diff <= 0 && newDiff > 0) {
			res++
			diff = newDiff
		}
	}
	return res
}

377.组合总和Ⅳ(2)¶

题目

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:nums = [1, 2, 3] target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶：如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？

解题思路

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

func combinationSum4(nums []int, target int) int {
	// 等价于：
	// 假设你正在爬楼梯。需要n阶你才能到达楼顶。
	// 每次你可以爬num(num in nums)级台阶。
	// 你有多少种不同的方法可以爬到楼顶呢？
	dp := make([]int, target+1)
	dp[0] = 1 // 爬0楼1种解法
	for i := 1; i <= target; i++ {
		for j := 0; j < len(nums); j++ {
			if i-nums[j] >= 0 {
				dp[i] = dp[i] + dp[i-nums[j]]
			}
		}
	}
	return dp[target]
}

# 2
var m map[int]int

func combinationSum4(nums []int, target int) int {
	m = make(map[int]int)
	res := dfs(nums, target)
	if res == -1 {
		return 0
	}
	return res
}

func dfs(nums []int, target int) int {
	if target == 0 {
		return 1
	}
	if target < 0 {
		return -1
	}
	if v, ok := m[target]; ok {
		return v
	}
	temp := 0
	for i := 0; i < len(nums); i++ {
		if dfs(nums, target-nums[i]) != -1 {
			temp = temp + dfs(nums, target-nums[i])
		}
	}
	m[target] = temp
	return temp
}

378.有序矩阵中第K小的元素(3)¶

题目

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例：matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
返回 13。
提示：你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组辅助排序	O(n^2log(n))	O(n^2)
02	二分查找	O(nlog(n))	O(1)
03	堆	O(n^2log(n))	O(n^2)

func kthSmallest(matrix [][]int, k int) int {
	res := make([]int, 0)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			res = append(res, matrix[i][j])
		}
	}
	sort.Ints(res)
	return res[k-1]
}

# 2
func kthSmallest(matrix [][]int, k int) int {
	n := len(matrix)
	left, right := matrix[0][0], matrix[n-1][n-1]
	for left < right {
		mid := left + (right-left)/2
		if check(matrix, mid, k, n) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

// 左下角查找
func check(matrix [][]int, mid, k, n int) bool {
	i := n - 1
	j := 0
	num := 0
	for i >= 0 && j < n {
		if matrix[i][j] <= mid {
			// 往右,说明左边一列都小于mid
			num = num + i + 1
			j++
		} else {
			// 往上
			i--
		}
	}
	return num >= k
}

# 3
func kthSmallest(matrix [][]int, k int) int {
	var h IntHeap
	heap.Init(&h)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			heap.Push(&h, matrix[i][j])
		}
	}
	for h.Len() > 0 && k > 0 {
		k--
		res := heap.Pop(&h).(int)
		if k == 0 {
			return res
		}
	}
	return 0
}

type IntHeap []int

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

380.常数时间插入、删除和获取随机元素(2)¶

题目

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
    insert(val)：当元素 val 不存在时，向集合中插入该项。
    remove(val)：元素 val 存在时，从集合中移除该项。
    getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中，所以返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

解题思路

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

type RandomizedSet struct {
	m   map[int]int
	arr []int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		m:   make(map[int]int),
		arr: make([]int, 0),
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.m[val]; ok {
		return false
	}
	this.arr = append(this.arr, val)
	this.m[val] = len(this.arr) - 1
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	if _, ok := this.m[val]; !ok {
		return false
	}
	index := this.m[val]
	this.arr[index], this.arr[len(this.arr)-1] = this.arr[len(this.arr)-1], this.arr[index]
	this.m[this.arr[index]] = index
	this.arr = this.arr[:len(this.arr)-1]
	delete(this.m, val)
	return true
}

func (this *RandomizedSet) GetRandom() int {
	if len(this.arr) == 0 {
		return -1
	}
	index := rand.Intn(len(this.arr))
	return this.arr[index]
}

# 2
type RandomizedSet struct {
	m map[int]bool
}

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

func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.m[val]; ok {
		return false
	}
	this.m[val] = true
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	if _, ok := this.m[val]; !ok {
		return false
	}
	delete(this.m, val)
	return true
}

func (this *RandomizedSet) GetRandom() int {
	if len(this.m) == 0 {
		return -1
	}
	index := rand.Intn(len(this.m))
	res := -1
	for res = range this.m {
		index--
		if index == -1 {
			break
		}
	}
	return res
}

382.链表随机节点(1)¶

题目

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例:// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

解题思路

No.	思路	时间复杂度	空间复杂度
01	蓄水池抽样	O(n)	O(1)

type Solution struct {
	head *ListNode
	r    *rand.Rand
}

func Constructor(head *ListNode) Solution {
	return Solution{
		head: head,
		r:    rand.New(rand.NewSource(time.Now().Unix())),
	}
}

func (this *Solution) GetRandom() int {
	res := this.head.Val
	cur := this.head
	count := 1
	for cur != nil {
		if this.r.Intn(count)+1 == count {
			res = cur.Val
		}
		count++
		cur = cur.Next
	}
	return res
}

384.打乱数组(2)¶

题目

打乱一个没有重复元素的数组。
示例:
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();
// 重设数组到它的初始状态[1,2,3]。
solution.reset();
// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

解题思路

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

type Solution struct {
	nums []int
}

func Constructor(nums []int) Solution {
	return Solution{nums: nums}
}

func (this *Solution) Reset() []int {
	return this.nums
}

func (this *Solution) Shuffle() []int {
	arr := make([]int, len(this.nums))
	copy(arr, this.nums)
	rand.Shuffle(len(arr), func(i, j int) {
		arr[i], arr[j] = arr[j], arr[i]
	})
	return arr
}

#
type Solution struct {
	nums []int
}

func Constructor(nums []int) Solution {
	return Solution{nums: nums}
}

func (this *Solution) Reset() []int {
	return this.nums
}

func (this *Solution) Shuffle() []int {
	arr := make([]int, len(this.nums))
	copy(arr, this.nums)
	res := make([]int, len(this.nums))
	for i := 0; i < len(res); i++{
		j := rand.Intn(len(arr))
		res[i] = arr[j]
		arr = append(arr[:j], arr[j+1:]...)
	}
	return res
}

385.迷你语法分析器(1)¶

题目

给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。
列表中的每个元素只可能是整数或整数嵌套列表
提示：你可以假定这些字符串都是格式良好的：
字符串非空
字符串不包含空格
字符串只包含数字0-9、[、-、,、]
示例 1：给定 s = "324",
你应该返回一个 NestedInteger 对象，其中只包含整数值 324。
示例 2：给定 s = "[123,[456,[789]]]",
返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
    i.  一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789

解题思路

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

func deserialize(s string) *NestedInteger {
	if s[0] != '[' {
		res := &NestedInteger{}
		num, _ := strconv.Atoi(s)
		res.SetInteger(num)
		return res
	}
	stack := make([]NestedInteger, 0)
	str := ""
	for i := 0; i < len(s); i++ {
		if s[i] == '[' {
			stack = append(stack, NestedInteger{})
		} else if s[i] == ']' {
			if len(str) > 0 {
				node := NestedInteger{}
				num, _ := strconv.Atoi(str)
				node.SetInteger(num)
				stack[len(stack)-1].Add(node)
			}
			str = ""
			if len(stack) > 1 { // 出栈
				last := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				stack[len(stack)-1].Add(last)
			}
		} else if s[i] == ',' {
			if len(str) > 0 {
				node := NestedInteger{}
				num, _ := strconv.Atoi(str)
				node.SetInteger(num)
				stack[len(stack)-1].Add(node)
			}
			str = ""
		} else {
			str = str + string(s[i])
		}
	}
	return &stack[len(stack)-1]
}

386.字典序排数(2)¶

题目

给定一个整数n, 返回从1到n的字典顺序。
例如，给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据n小于等于5,000,000。

解题思路

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

func lexicalOrder(n int) []int {
	res := make([]int, 0)
	num := 1
	for {
		if num <= n {
			res = append(res, num)
			num = num * 10
		} else {
			num = num / 10
			for num%10 == 9 {
				num = num / 10
			}
			if num == 0 {
				break
			}
			num++
		}
	}
	return res
}

# 2
var res []int

func lexicalOrder(n int) []int {
	res = make([]int, 0)
	for i := 1; i <= 9; i++ {
		dfs(n, i)
	}
	return res
}

func dfs(n, start int) {
	if start > n {
		return
	}
	// N叉树前序遍历
	res = append(res, start)
	for i := 0; i <= 9; i++ {
		dfs(n, start*10+i)
	}
}

388.文件的最长绝对路径(1)¶

题目

假设文件系统如下图所示：
这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。
subdir1 包含文件 file1.ext 和子目录 subsubdir1；
subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。
在文本格式中，如下所示(⟶表示制表符)：
dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext
如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n
\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。'\n' 和 '\t' 分别是换行符和制表符。
文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，
所有路径用 '/' 连接。上面例子中，
指向 file2.ext 的绝对路径是 "dir/subdir2/subsubdir2/file2.ext" 。
每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，
其中名称和扩展名由字母、数字和/或空格组成。
给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向文件的最长绝对路径 的长度。 
如果系统中没有文件，返回0。
示例 1：输入：input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" 输出：20
解释：只有一个文件，绝对路径为 "dir/subdir2/file.ext" ，路径长度 20
路径 "dir/subdir1" 不含任何文件
示例 2：输入：input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2
\n\t\tsubsubdir2\n\t\t\tfile2.ext"
输出：32
解释：存在两个文件：
"dir/subdir1/file1.ext" ，路径长度 21
"dir/subdir2/subsubdir2/file2.ext" ，路径长度 32
返回 32 ，因为这是最长的路径
示例 3：输入：input = "a" 输出：0
解释：不存在任何文件
示例 4：输入：input = "file1.txt\nfile2.txt\nlongfile.txt" 输出：12
解释：根目录下有 3 个文件。
因为根目录中任何东西的绝对路径只是名称本身，所以答案是 "longfile.txt" ，路径长度为 12
提示：1 <= input.length <= 104
input 可能包含小写或大写的英文字母，一个换行符 '\n'，
一个指表符 '\t'，一个点 '.'，一个空格 ' '，和数字。

解题思路

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

func lengthLongestPath(input string) int {
	res := 0
	arr := strings.Split(input, "\n")
	temp := make([]string, 0)
	for i := 0; i < len(arr); i++ {
		str := arr[i]
		count := strings.Count(arr[i], "\t")
		str = str[count:] // 去除\t后的字符串
		if count < len(temp) { // 多个\t的个数小于当前层级，需要去除
			temp = temp[:count]
		}
		if strings.Contains(str, ".") {
			length := len(str) + getLength(temp) + len(temp) // len(temp)个分隔符
			if length > res {
				res = length
			}
		} else {
			temp = append(temp, str)
		}
	}
	return res
}

func getLength(arr []string) int {
	res := 0
	for i := 0; i < len(arr); i++ {
		res = res + len(arr[i])
	}
	return res
}

390.消除游戏(2)¶

题目

给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。
示例：输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
输出:6

解题思路

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

func lastRemaining(n int) int {
	if n == 1 {
		return 1
	}
	// f(2k)/f(2k+1) = 2(k+1-f(k))，最后奇数2k+1不影响结果
	return 2 * (n/2 + 1 - lastRemaining(n/2))
}

# 2
func lastRemaining(n int) int {
	return dfs(n, 1)
}

func dfs(n int, isLeftToRight int) int {
	if n == 1 {
		return 1
	}
	if n%2 == 1 { // 奇数
		return 2 * dfs(n/2, 1-isLeftToRight)
	}
	if isLeftToRight == 1 { // 偶数从左往右
		return 2 * dfs(n/2, 1-isLeftToRight)
	}
	// 偶数从右往左，如1，2，3，4，5，6，7，8 => 1，3，5，7
	return 2*dfs(n/2, 1-isLeftToRight) - 1
}

393.UTF-8编码验证(2)¶

题目

UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：
对于 1 字节的字符，字节的第一位设为0，后面7位为这个符号的unicode码。
对于 n 字节的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为0，后面字节的前两位一律设为10。
剩下的没有提及的二进制位，全部为这个符号的unicode码。
这是 UTF-8 编码的工作方式：
   Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
给定一个表示数据的整数数组，返回它是否为有效的 utf-8 编码。
注意:输入是整数数组。只有每个整数的最低 8 个有效位用来存储数据。这意味着每个整数只表示 1 字节的数据。
示例 1:data = [197, 130, 1], 表示 8 位的序列: 11000101 10000010 00000001.返回 true 。
这是有效的 utf-8 编码，为一个2字节字符，跟着一个1字节字符。
示例 2:data = [235, 140, 4], 表示 8 位的序列: 11101011 10001100 00000100. 返回 false 。
前 3 位都是 1 ，第 4 位为 0 表示它是一个3字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不以 10 开头，所以是不符合规则的。

解题思路

No.	思路	时间复杂度	空间复杂度
01	位运算	O(n)	O(1)
02	位运算	O(n)	O(1)

func validUtf8(data []int) bool {
	count := 0
	for i := 0; i < len(data); i++ {
		if count == 0 {
			if data[i]&0b11111000 == 0b11110000 {
				count = 3
			} else if data[i]&0b11110000 == 0b11100000 {
				count = 2
			} else if data[i]&0b11100000 == 0b11000000 {
				count = 1
			} else if data[i]&0b10000000 != 0b00000000 { // 其它以1开头的
				return false
			}
		} else {
			if data[i]&0b10000000 != 0b10000000 {
				return false
			}
			count--
		}
	}
	return count == 0
}

# 2
func validUtf8(data []int) bool {
	count := 0
	for i := 0; i < len(data); i++ {
		if count == 0 {
			if data[i]>>3 == 0b11110 {
				count = 3
			} else if data[i]>>4 == 0b1110 {
				count = 2
			} else if data[i]>>5 == 0b110 {
				count = 1
			} else if data[i]>>7 != 0b0 { // 其它以1开头的
				return false
			}
		} else {
			if data[i]>>6 != 0b10 {
				return false
			}
			count--
		}
	}
	return count == 0
}

394.字符串解码(2)¶

题目

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。
注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：输入：s = "3[a]2[bc]" 输出："aaabcbc"
示例 2：输入：s = "3[a2[c]]" 输出："accaccacc"
示例 3：输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"
示例 4：输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"

解题思路

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

func decodeString(s string) string {
	res := make([]byte, 0)
	numStack := make([]int, 0)
	lenStack := make([]int, 0)
	var count int
	for i := 0; i < len(s); i++ {
		if '0' <= s[i] && s[i] <= '9' {
			count = count*10 + int(s[i]-'0')
		} else if s[i] == '[' {
			numStack = append(numStack, count)
			count = 0
			lenStack = append(lenStack, len(res))
		} else if s[i] == ']' {
			c := numStack[len(numStack)-1]
			numStack = numStack[:len(numStack)-1]
			l := lenStack[len(lenStack)-1]
			lenStack = lenStack[:len(lenStack)-1]
			str := res[l:]
			res = res[:l]
			for i := 0; i < c; i++ {
				res = append(res, str...)
			}
		} else {
			res = append(res, s[i])
		}
	}
	return string(res)
}

#
func decodeString(s string) string {
	res := ""
	count := 0
	for i := 0; i < len(s); i++ {
		if '0' <= s[i] && s[i] <= '9' {
			count = count*10 + int(s[i]-'0')
		} else if s[i] == '[' {
			times := 0
			i++
			str := make([]byte, 0)
			for s[i] != ']' || times != 0 {
				if s[i] == '[' {
					times++
				} else if s[i] == ']' {
					times--
				}
				str = append(str, s[i])
				i++
			}
			temp := decodeString(string(str))
			for j := 0; j < count; j++ {
				res = res + (temp)
			}
			count = 0
		} else {
			res = res + string(s[i])
		}
	}
	return res
}

395.至少有K个重复字符的最长子串(2)¶

题目

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:输入: s = "aaabb", k = 3输出: 3
最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2:输入:s = "ababbc", k = 2 输出:5 
最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

解题思路

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

func longestSubstring(s string, k int) int {
	res := 0
	m := make(map[byte]int) // 统计每个字符的个数
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}
	var split byte // 某个字符出现的次数：0<x<k
	for key, value := range m {
		if value < k {
			split = key
			break
		}
	}
	if split == 0 { // 字符出现次数都>=k
		return len(s)
	}
	arr := strings.Split(s, string(split)) // 以该字符切割的子串
	for i := 0; i < len(arr); i++ {
		temp := longestSubstring(arr[i], k)
		if temp > res {
			res = temp
		}
	}
	return res
}

# 2
func longestSubstring(s string, k int) int {
	res := 0
	// 多次滑动窗口
	for i := 1; i < 26; i++ { // 枚举字符种类的个数
		m := make(map[byte]int)
		count := 0
		left := 0
		lessK := 0 // 字符出现次数<k的个数
		for right := 0; right < len(s); right++ {
			if m[s[right]] == 0 {
				count++
				lessK++
			}
			m[s[right]]++
			if m[s[right]] == k {
				lessK--
			}
			for count > i { // 字母出现次数大于枚举的次数
				if m[s[left]] == k {
					lessK++
				}
				m[s[left]]-- // 移动左窗口
				if m[s[left]] == 0 {
					count--
					lessK--
				}
				left++
			}
			if lessK == 0 && right-left+1 > res { // 更新结果
				res = right - left + 1
			}
		}
	}
	return res
}

396.旋转函数(1)¶

题目

给定一个长度为 n 的整数数组A。
假设Bk是数组A顺时针旋转 k 个位置后的数组，我们定义A的“旋转函数”F为：
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。
计算F(0), F(1), ..., F(n-1)中的最大值。
注意:可以认为 n 的值小于 10^5。
示例:A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

解题思路

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

func maxRotateFunction(A []int) int {
	res := 0
	total := 0
	n := len(A)
	for i := 0; i < n; i++ {
		total = total + A[i]
		res = res + i*A[i]
	}
	temp := res
	for i := 0; i < n; i++ {
		// 最后移动到第一位，其他右移一位
		temp = temp + total      // 每一位都加一次
		temp = temp - n*A[n-1-i] // 最后一位删除
		if temp > res {
			res = temp
		}
	}
	return res
}

397.整数替换(2)¶

题目

给定一个正整数 n，你可以做如下操作：
1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少？
示例 1:输入: 8输出: 3
解释:8 -> 4 -> 2 -> 1
示例 2:输入: 7输出: 4
解释:7 -> 8 -> 4 -> 2 -> 1 或7 -> 6 -> 3 -> 2 -> 1

解题思路

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

func integerReplacement(n int) int {
	if n < 3 {
		return n - 1
	}
	if n == math.MinInt32 {
		return 32
	}
	if n%2 == 0 {
		return integerReplacement(n/2) + 1
	}
	a := integerReplacement(n+1) + 1
	b := integerReplacement(n-1) + 1
	if a > b {
		return b
	}
	return a
}

# 2
var m map[int]int

func integerReplacement(n int) int {
	m = make(map[int]int)
	return dfs(n)
}

func dfs(n int) int {
	if m[n] > 0 {
		return m[n]
	}
	if n == 1 {
		return 0
	}
	if n%2 == 0 {
		m[n] = dfs(n/2) + 1
	} else {
		m[n] = min(dfs(n-1), dfs(n+1)) + 1
	}
	return m[n]
}

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

398.随机数索引(2)¶

题目

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
示例:int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

解题思路

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

type Solution struct {
	m map[int][]int
	r *rand.Rand
}

func Constructor(nums []int) Solution {
	res := Solution{
		m: make(map[int][]int),
		r: rand.New(rand.NewSource(time.Now().Unix())),
	}
	for i := 0; i < len(nums); i++ {
		res.m[nums[i]] = append(res.m[nums[i]], i)
	}
	return res
}

func (this *Solution) Pick(target int) int {
	arr := this.m[target]
	index := this.r.Intn(len(arr))
	return arr[index]
}

# 2
type Solution struct {
	nums []int
	r    *rand.Rand
}

func Constructor(nums []int) Solution {
	return Solution{
		nums: nums,
		r:    rand.New(rand.NewSource(time.Now().Unix())),
	}
}

func (this *Solution) Pick(target int) int {
	res := 0
	count := 1
	for i := 0; i < len(this.nums); i++ {
		if this.nums[i] == target {
            // 蓄水池采样法
			if this.r.Intn(count)+1 == count {
				res = i
			}
			count++
		}
	}
	return res
}

399.除法求值(3)¶

题目

给出方程式A / B = k, 其中A 和B 均为用字符串表示的变量，k 是一个浮点型数字。
根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回-1.0。
输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
示例 1：输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], 
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：给定：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回：[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2：输入：equations = [["a","b"],["b","c"],["bc","cd"]], 
values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：输入：equations = [["a","b"]], values = [0.5], 
queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：1 <= equations.length <= 20
equations[i].length == 2
1 <= equations[i][0].length, equations[i][1].length <= 5
values.length ==equations.length
0.0 <values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= queries[i][0].length, queries[i][1].length <= 5
equations[i][0], equations[i][1],queries[i][0], queries[i][1] 由小写英文字母与数字组成

解题思路

No.	思路	时间复杂度	空间复杂度
01	广度优先搜索	O(n^2)	O(n^2)
02	Floyd	O(n^3)	O(n^2)
03	并查集	O(nlog(n))	O(n)

type Node struct {
	to    int
	value float64
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	m := make(map[string]int) // 计算对应的id
	for i := 0; i < len(equations); i++ {
		a, b := equations[i][0], equations[i][1]
		if _, ok := m[a]; ok == false {
			m[a] = len(m)
		}
		if _, ok := m[b]; ok == false {
			m[b] = len(m)
		}
	}
	arr := make([][]Node, len(m)) // 邻接表
	for i := 0; i < len(equations); i++ {
		a, b := m[equations[i][0]], m[equations[i][1]]
		arr[a] = append(arr[a], Node{to: b, value: values[i]})
		arr[b] = append(arr[b], Node{to: a, value: 1 / values[i]}) // 除以
	}
	res := make([]float64, len(queries))
	for i := 0; i < len(queries); i++ {
		a, okA := m[queries[i][0]]
		b, okB := m[queries[i][1]]
		if okA == false || okB == false {
			res[i] = -1
		} else {
			res[i] = bfs(arr, a, b) // 广度优先查找
		}
	}
	return res
}

func bfs(arr [][]Node, start, end int) float64 {
	temp := make([]float64, len(arr)) // 结果的比例
	temp[start] = 1
	queue := make([]int, 0)
	queue = append(queue, start)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == end {
			return temp[node]
		}
		for i := 0; i < len(arr[node]); i++ {
			next := arr[node][i].to
			if temp[next] == 0 {
				temp[next] = temp[node] * arr[node][i].value
				queue = append(queue, next)
			}
		}
	}
	return -1
}

# 2
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	m := make(map[string]int) // 计算对应的id
	for i := 0; i < len(equations); i++ {
		a, b := equations[i][0], equations[i][1]
		if _, ok := m[a]; ok == false {
			m[a] = len(m)
		}
		if _, ok := m[b]; ok == false {
			m[b] = len(m)
		}
	}
	arr := make([][]float64, len(m)) // 邻接矩阵
	for i := 0; i < len(m); i++ {
		arr[i] = make([]float64, len(m))
	}
	for i := 0; i < len(equations); i++ {
		a, b := m[equations[i][0]], m[equations[i][1]]
		arr[a][b] = values[i]
		arr[b][a] = 1 / values[i]
	}
	for k := 0; k < len(arr); k++ { // Floyd
		for i := 0; i < len(arr); i++ {
			for j := 0; j < len(arr); j++ {
				if arr[i][k] > 0 && arr[k][j] > 0 {
					arr[i][j] = arr[i][k] * arr[k][j]
				}
			}
		}
	}
	res := make([]float64, len(queries))
	for i := 0; i < len(queries); i++ {
		a, okA := m[queries[i][0]]
		b, okB := m[queries[i][1]]
		if okA == false || okB == false || arr[a][b] == 0 {
			res[i] = -1
		} else {
			res[i] = arr[a][b]
		}
	}
	return res
}

# 3
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	m := make(map[string]int) // 计算对应的id
	for i := 0; i < len(equations); i++ {
		a, b := equations[i][0], equations[i][1]
		if _, ok := m[a]; ok == false {
			m[a] = len(m)
		}
		if _, ok := m[b]; ok == false {
			m[b] = len(m)
		}
	}
	fa, rank = Init(len(m))
	for i := 0; i < len(equations); i++ {
		a, b := m[equations[i][0]], m[equations[i][1]]
		union(a, b, values[i])
	}
	res := make([]float64, len(queries))
	for i := 0; i < len(queries); i++ {
		a, okA := m[queries[i][0]]
		b, okB := m[queries[i][1]]
		if okA == true && okB == true && find(a) == find(b) {
			res[i] = rank[a] / rank[b]
		} else {
			res[i] = -1
		}
	}
	return res
}

var fa []int
var rank []float64

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

// 查询
func find(x int) int {
	// 彻底路径压缩
	if fa[x] != x {
		origin := fa[x]
		fa[x] = find(fa[x])
		rank[x] = rank[x] * rank[origin] // 秩处理是难点
	}
	return fa[x]
}

// 合并
func union(i, j int, value float64) {
	x, y := find(i), find(j)
	rank[x] = value * rank[j] / rank[i] // 秩处理是难点
	fa[x] = y
}

400.第N个数字(2)¶

题目

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
注意:n 是正数且在32位整数范围内 ( n < 231)。
示例 1:输入:3输出:3
示例 2:输入:11输出:0
说明:第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。

解题思路

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

func findNthDigit(n int) int {
	if n < 0 {
		return -1
	}
	digits := 1
	for {
		numbers := countOfIntegers(digits)
		if n < numbers*digits {
			return digitAtIndex(n, digits)
		}
		n = n - numbers*digits
		digits++
	}
}

func countOfIntegers(n int) int {
	if n == 1 {
		return 10
	}
	count := math.Pow(float64(10), float64(n-1))
	return 9 * int(count)
}

func digitAtIndex(n, digits int) int {
	number := beginNumber(digits) + n/digits
	indexFromRight := digits - n%digits
	for i := 1; i < indexFromRight; i++ {
		number = number / 10
	}
	return number % 10
}

func beginNumber(digits int) int {
	if digits == 1 {
		return 0
	}
	return int(math.Pow(float64(10), float64(digits-1)))
}

# 2
func findNthDigit(n int) int {
	if n < 10 {
		return n
	}
	digits := 1
	count := 9
	number := 1
	for n-digits*count > 0 {
		n = n - digits*count
		digits++
		count = count * 10
		number = number * 10
	}
	number = number + (n-1)/digits
	index := (n - 1) % digits
	str := strconv.Itoa(number)
	return int(str[index] - '0')
}

0301-0400-Hard¶

301.删除无效的括号(2)¶

题目

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 1:输入: "()())()" 输出: ["()()()", "(())()"]
示例 2:输入: "(a)())()" 输出: ["(a)()()", "(a())()"]
示例 3:输入: ")(" 输出: [""]

解题思路

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

func removeInvalidParentheses(s string) []string {
	res := make([]string, 0)
	cur := make(map[string]int)
	cur[s] = 1
	for {
		for k := range cur {
			if isValid(k) {
				res = append(res, k)
			}
		}
		if len(res) > 0 {
			return res
		}
		next := make(map[string]int)
		for k := range cur {
			for i := range k {
				if k[i] == '(' || k[i] == ')' {
					str := k[:i] + k[i+1:]
					next[str] = 1
				}
			}
		}
		cur = next
	}
}

func isValid(s string) bool {
	left := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			left++
		} else if s[i] == ')' {
			left--
		}
		if left < 0 {
			return false
		}
	}
	return left == 0
}

# 2
var m map[string]bool
var max int

func removeInvalidParentheses(s string) []string {
	m = make(map[string]bool)
	res := make([]string, 0)
	max = 0
	dfs(s, 0, 0, "")
	for k := range m {
		res = append(res, k)
	}
	return res
}

func dfs(s string, start, count int, temp string) {
	if count < 0 {
		return
	}
	if start == len(s) {
		if count == 0 {
			if len(temp) > max {
				max = len(temp)
				m = make(map[string]bool)
				m[temp] = true
			} else if max == len(temp) {
				m[temp] = true
			}
		}
		return
	}
	if s[start] == '(' {
		dfs(s, start+1, count+1, temp+"(")
	} else if s[start] == ')' {
		dfs(s, start+1, count-1, temp+")")
	} else {
		dfs(s, start+1, count, temp+string(s[start]))
	}
	if s[start] == '(' || s[start] == ')' {
		dfs(s, start+1, count, temp)
	}
}

312.戳气球(3)¶

题目

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。
这里的 left 和 right 代表和 i 相邻的两个气球的序号。
注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
    0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:输入: [3,1,5,8] 输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

解题思路

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

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

func maxCoins(nums []int) int {
	n := len(nums)
	arr = make([]int, n+2)
	arr[0], arr[len(arr)-1] = 1, 1
	for i := 1; i <= n; i++ {
		arr[i] = nums[i-1]
	}
	res = make([][]int, n+2)
	for i := 0; i < len(res); i++ {
		res[i] = make([]int, n+2)
		for j := 0; j < len(res[i]); j++ {
			res[i][j] = -1
		}
	}
	return dfs(0, n+1)
}

// 将开区间(i,j)内的位置全部填满气球能够得到的最多硬币数
func dfs(left, right int) int {
	// 不满足3个
	if left+1 >= right {
		return 0
	}
	if res[left][right] != -1 {
		return res[left][right]
	}
	for i := left + 1; i < right; i++ {
		// 填充第i位，两边是arr[left],arr[right]
		sum := arr[left] * arr[i] * arr[right]
		sum = sum + dfs(left, i) + dfs(i, right)
		res[left][right] = max(res[left][right], sum)
	}
	return res[left][right]
}

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

# 2
func maxCoins(nums []int) int {
	n := len(nums)
	arr := make([]int, n+2)
	arr[0], arr[len(arr)-1] = 1, 1
	for i := 1; i <= n; i++ {
		arr[i] = nums[i-1]
	}
	dp := make([][]int, n+2)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+2)
	}
	// dp[i][j] 表示填满开区间(i,j)能得到的最多硬币数
	// i => left
	// k => i
	// j => right
	// i不能0->n+1
	for i := n - 1; i >= 0; i-- {
		for j := i + 2; j <= n+1; j++ {
			for k := i + 1; k < j; k++ {
				sum := arr[i] * arr[k] * arr[j]
				sum = sum + dp[i][k] + dp[k][j]
				dp[i][j] = max(dp[i][j], sum)
			}
		}
	}
	return dp[0][n+1]
}

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

# 3
func maxCoins(nums []int) int {
	n := len(nums)
	arr := make([]int, n+2)
	arr[0], arr[len(arr)-1] = 1, 1
	for i := 1; i <= n; i++ {
		arr[i] = nums[i-1]
	}
	dp := make([][]int, n+2)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+2)
	}
	// dp[i][j] 表示填满开区间(i,j)能得到的最多硬币数
	// i => left
	// k => i
	// j => right
	for j := 2; j <= n+1; j++ {
		for i := j - 2; i >= 0; i-- {
			for k := i + 1; k < j; k++ {
				sum := arr[i] * arr[k] * arr[j]
				sum = sum + dp[i][k] + dp[k][j]
				dp[i][j] = max(dp[i][j], sum)
			}
		}
	}
	return dp[0][n+1]
}

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

315.计算右侧小于当前元素的个数(3)¶

题目

给定一个整数数组 nums，按要求返回一个新数组counts。
数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于nums[i] 的元素的数量。
示例：输入：nums = [5,2,6,1] 输出：[2,1,1,0] 
解释：5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
提示：0 <= nums.length <= 10^5
-10^4<= nums[i] <= 10^4

解题思路

No.	思路	时间复杂度	空间复杂度
01	树状数组+离散化	O(nlog(n))	O(n)
02	归并排序	O(nlog(n))	O(n)
03	线段树+离散化	O(nlog(n))	O(n)

func countSmaller(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	arr, _ := getLSH(nums)
	length = n
	c = make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		res[i] = getSum(arr[i] - 1)
		upData(arr[i], 1)
	}
	return res
}

func getLSH(a []int) ([]int, map[int]int) {
	n := len(a)
	arr := make([]int, n)
	copy(arr, a)
	sort.Ints(arr) // 排序
	m := make(map[int]int)
	m[arr[0]] = 1
	index := 1
	for i := 1; i < n; i++ {
		if arr[i] != arr[i-1] {
			index++
			m[arr[i]] = index
		}
	}
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = m[a[i]]
	}
	return res, m
}

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

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

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

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

# 2
type Node struct {
	Value int
	Index int
}

var res []int

func countSmaller(nums []int) []int {
	n := len(nums)
	res = make([]int, n)
	arr := make([]Node, 0)
	for i := 0; i < n; i++ {
		arr = append(arr, Node{
			Value: nums[i],
			Index: i,
		})
	}
	mergeSort(arr)
	return res
}

func mergeSort(nums []Node) {
	n := len(nums)
	if n <= 1 {
		return
	}
	a := append([]Node{}, nums[:n/2]...)
	b := append([]Node{}, nums[n/2:]...)
	mergeSort(a) // a已经有序
	mergeSort(b) // b已经有序
	i, j := 0, 0
	for i = 0; i < len(a); i++ {
		for j < len(b) && a[i].Value > b[j].Value { // 统计比右边多多少个数
			j++
		}
		res[a[i].Index] = res[a[i].Index] + j // 找到下标，然后加上次数
	}
	i, j = 0, 0
	for k := 0; k < len(nums); k++ { // 2个有序数组合并
		if i < len(a) && (j == len(b) || a[i].Value <= b[j].Value) {
			nums[k] = a[i]
			i++
		} else {
			nums[k] = b[j]
			j++
		}
	}
	return
}

# 3
func countSmaller(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	tempArr, m := getLSH(nums)
	total := len(tempArr)
	arr = make([]int, 4*total+1)
	for i := n - 1; i >= 0; i-- {
		index := m[nums[i]]
		res[i] = query(0, 1, total, 1, index-1)
		update(0, 1, total, index, 1)
	}
	return res
}

func getLSH(a []int) ([]int, map[int]int) {
	n := len(a)
	arr := make([]int, n)
	copy(arr, a)
	sort.Ints(arr) // 排序
	m := make(map[int]int)
	m[arr[0]] = 1
	index := 1
	for i := 1; i < n; i++ {
		if arr[i] != arr[i-1] {
			index++
			m[arr[i]] = index
		}
	}
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = m[a[i]]
	}
	return res, m
}

var arr []int // 线段树

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

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

316.去除重复字母(2)¶

题目

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。
需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1:输入: "bcabc" 输出: "abc"
示例 2:输入: "cbacdcbc" 输出: "acdb"
注意：该题与 1081 
https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters 相同

解题思路

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

func removeDuplicateLetters(s string) string {
	stack := make([]byte, 0)
	arr := [256]byte{}
	m := make(map[byte]bool)
	for i := 0; i < len(s); i++ {
		arr[s[i]]++
	}
	for i := 0; i < len(s); i++ {
		if m[s[i]] == true {
			arr[s[i]]--
			continue
		}
		// arr[栈顶]说明有重复元素
		// 栈顶>s[i]:说明字典序不满足
		for len(stack) > 0 && stack[len(stack)-1] > s[i] && arr[stack[len(stack)-1]] > 0 {
			m[stack[len(stack)-1]] = false
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, s[i])
		arr[s[i]]--
		m[s[i]] = true
	}
	return string(stack)
}

# 2
func removeDuplicateLetters(s string) string {
	arr := [26]int{}
	pos := 0
	for i := 0; i < len(s); i++ {
		arr[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if s[i] < s[pos] {
			pos = i
		}
		arr[s[i]-'a']--
		if arr[s[i]-'a'] == 0 {
			break
		}
	}
	if len(s) == 0 {
		return ""
	}
	newStr := strings.ReplaceAll(s[pos+1:], string(s[pos]), "")
	return string(s[pos]) + removeDuplicateLetters(newStr)
}

321.拼接最大数(1)¶

题目

给定长度分别为m和n的两个数组，其元素由0-9构成，表示两个自然数各位上的数字。
现在从这两个数组中选出 k (k <= m + n)个数字拼接成一个新的数，
要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例1:输入:nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5
输出:[9, 8, 6, 5, 3]
示例 2:输入:nums1 = [6, 7]nums2 = [6, 0, 4]k = 5
输出:[6, 7, 6, 0, 4]
示例 3:输入:nums1 = [3, 9]nums2 = [8, 9] k = 3
输出:[9, 8, 9]

解题思路

No.	思路	时间复杂度	空间复杂度
01	枚举	O(n^3)	O(n)

func maxNumber(nums1 []int, nums2 []int, k int) []int {
	res := make([]int, k)
	for i := 0; i <= k; i++ {
		if i <= len(nums1) && k-i <= len(nums2) {
			a := check(nums1, i)
			b := check(nums2, k-i)
			c := merge(a, b)
			if compare(res, c) == true {
				res = c
			}
		}
	}
	return res
}

func check(num []int, k int) []int {
	stack := make([]int, 0)
	count := len(num) - k
	for i := 0; i < len(num); i++ {
		for len(stack) > 0 && count > 0 && stack[len(stack)-1] < num[i] {
			stack = stack[:len(stack)-1]
			count--
		}
		stack = append(stack, num[i])
	}
	return stack[:k]
}

func merge(nums1, nums2 []int) []int {
	res := make([]int, len(nums1)+len(nums2))
	if len(nums1) == 0 {
		copy(res, nums2)
		return res
	}
	if len(nums2) == 0 {
		copy(res, nums1)
		return res
	}
	for i := 0; i < len(res); i++ {
		if compare(nums1, nums2) {
			res[i], nums2 = nums2[0], nums2[1:]
		} else {
			res[i], nums1 = nums1[0], nums1[1:]
		}
	}
	return res
}

func compare(nums1, nums2 []int) bool {
	for i := 0; i < len(nums1) && i < len(nums2); i++ {
		if nums1[i] != nums2[i] {
			return nums1[i] < nums2[i]
		}
	}
	return len(nums1) < len(nums2)
}

327.区间和的个数(3)¶

题目

给你一个整数数组nums 以及两个整数lower 和 upper 。
求数组中，值位于范围 [lower, upper] （包含lower和upper）之内的 区间和的个数 。
区间和S(i, j)表示在nums中，位置从i到j的元素之和，包含i和j(i ≤ j)。
示例 1：输入：nums = [-2,5,-1], lower = -2, upper = 2 输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：输入：nums = [0], lower = 0, upper = 0 输出：1
提示：1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
题目数据保证答案是一个 32 位 的整数

解题思路

No.	思路	时间复杂度	空间复杂度
01	归并排序+前缀和	O(nlog(n))	O(n)
02	线段树+前缀和+离散化	O(nlog(n))	O(n)
03	树状数组+前缀和+离散化	O(nlog(n))	O(n)

func countRangeSum(nums []int, lower int, upper int) int {
	n := len(nums)
	arr := make([]int, n+1) // 前缀和
	for i := 0; i < n; i++ {
		arr[i+1] = arr[i] + nums[i]
	}
	return countSum(arr, lower, upper)
}

func countSum(nums []int, lower int, upper int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	a := append([]int{}, nums[:n/2]...)
	b := append([]int{}, nums[n/2:]...)
	res := countSum(a, lower, upper) + countSum(b, lower, upper)
	left, right := 0, 0
	for i := 0; i < len(a); i++ {
		for left < len(b) && b[left]-a[i] < lower { 
			left++
		}
		for right < len(b) && b[right]-a[i] <= upper {
			right++
		}
		res = res + right - left
	}
	i, j := 0, 0
	for k := 0; k < len(nums); k++ { // 2个有序数组合并
		if i < len(a) && (j == len(b) || a[i] <= b[j]) {
			nums[k] = a[i]
			i++
		} else {
			nums[k] = b[j]
			j++
		}
	}
	return res
}

# 2
func countRangeSum(nums []int, lower int, upper int) int {
	n := len(nums)
	preSum := make([]int, n+1) // 前缀和
	temp := make([]int, 0)
	temp = append(temp, 0) // 注意0
	for i := 0; i < n; i++ {
		preSum[i+1] = preSum[i] + nums[i]
		temp = append(temp, preSum[i+1], preSum[i+1]-lower, preSum[i+1]-upper)
	}
	tempArr, m := getLSH(temp) // 离散化
	total := len(tempArr)
	arr = make([]int, 4*total+1)
	update(0, 1, total, m[0], 1) // 注意0
	res := 0
	for i := 1; i < len(preSum); i++ {
		left := m[preSum[i]-upper]
		right := m[preSum[i]-lower]
		index := m[preSum[i]]
		count := query(0, 1, total, left, right)
		res = res + count
		update(0, 1, total, index, 1)
	}
	return res
}

// 离散化
func getLSH(a []int) ([]int, map[int]int) {
	n := len(a)
	arr := make([]int, n)
	copy(arr, a)
	sort.Ints(arr) // 排序
	m := make(map[int]int)
	m[arr[0]] = 1
	index := 1
	for i := 1; i < n; i++ {
		if arr[i] != arr[i-1] {
			index++
			m[arr[i]] = index
		}
	}
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = m[a[i]]
	}
	return res, m
}

var arr []int // 线段树

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

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

# 3
func countRangeSum(nums []int, lower int, upper int) int {
	n := len(nums)
	preSum := make([]int, n+1) // 前缀和
	temp := make([]int, 0)
	temp = append(temp, 0) // 注意0
	for i := 0; i < n; i++ {
		preSum[i+1] = preSum[i] + nums[i]
		temp = append(temp, preSum[i+1], preSum[i+1]-lower, preSum[i+1]-upper)
	}
	tempArr, m := getLSH(temp) // 离散化
	length = len(tempArr)
	c = make([]int, length+1)
	upData(m[0], 1) // 注意0
	res := 0
	for i := 1; i < len(preSum); i++ {
		left := m[preSum[i]-upper]
		right := m[preSum[i]-lower]
		index := m[preSum[i]]
		count := getSum(right) - getSum(left-1)
		res = res + count
		upData(index, 1)
	}
	return res
}

// 离散化
func getLSH(a []int) ([]int, map[int]int) {
	n := len(a)
	arr := make([]int, n)
	copy(arr, a)
	sort.Ints(arr) // 排序
	m := make(map[int]int)
	m[arr[0]] = 1
	index := 1
	for i := 1; i < n; i++ {
		if arr[i] != arr[i-1] {
			index++
			m[arr[i]] = index
		}
	}
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = m[a[i]]
	}
	return res, m
}

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

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

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

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

329.矩阵中的最长递增路径(3)¶

题目

给定一个m x n 整数矩阵matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4 
解释：最长递增路径为[1, 2, 6, 9]。
示例 2：输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]输出：4 
解释：最长递增路径是[3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：输入：matrix = [[1]]输出：1
提示：m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1

解题思路

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索	O(n^2)	O(n^2)
02	广度优先搜索+拓扑排序	O(n^2)	O(n^2)
03	排序+动态规划	O(n^2*log(n))	O(n^2)

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

func longestIncreasingPath(matrix [][]int) int {
	n, m = len(matrix), len(matrix[0])
	arr = make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
	}
	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			res = max(res, dfs(matrix, i, j))
		}
	}
	return res
}

func dfs(matrix [][]int, i, j int) int {
	if arr[i][j] != 0 {
		return arr[i][j]
	}
	arr[i][j]++ // 长度为1
	for k := 0; k < 4; k++ {
		x, y := i+dx[k], j+dy[k]
		if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[i][j] {
			arr[i][j] = max(arr[i][j], dfs(matrix, x, y)+1)
		}
	}
	return arr[i][j]
}

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

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

func longestIncreasingPath(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
	}
	queue := make([][2]int, 0) // 从最大数开始广度优先搜索
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			for k := 0; k < 4; k++ {
				x, y := i+dx[k], j+dy[k]
				if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[i][j] {
					arr[i][j]++ // 四周大于当前的个数
				}
			}
			if arr[i][j] == 0 { // 四周没有大于当前的数
				queue = append(queue, [2]int{i, j})
			}
		}
	}
	res := 0
	for len(queue) > 0 {
		res++
		length := len(queue)
		for i := 0; i < length; i++ {
			a, b := queue[i][0], queue[i][1]
			for k := 0; k < 4; k++ {
				x, y := a+dx[k], b+dy[k]
				if 0 <= x && x < n && 0 <= y && y < m && matrix[a][b] > matrix[x][y] {
					arr[x][y]--
					if arr[x][y] == 0 { // 个数为0，加入队列
						queue = append(queue, [2]int{x, y})
					}
				}
			}
		}
		queue = queue[length:]
	}
	return res
}

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

func longestIncreasingPath(matrix [][]int) int {
	n, m := len(matrix), len(matrix[0])
	dp := make([][]int, n)
	temp := make([][3]int, 0)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			dp[i][j] = 1
			temp = append(temp, [3]int{i, j, matrix[i][j]})
		}
	}
	sort.Slice(temp, func(i, j int) bool {
		return temp[i][2] < temp[j][2]
	})
	res := 1 // 一个数的时候，没有周围4个数，此时为1
	for i := 0; i < len(temp); i++ {
		a, b := temp[i][0], temp[i][1]
		for k := 0; k < 4; k++ {
			x, y := a+dx[k], b+dy[k]
			if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] > matrix[a][b] {
				dp[x][y] = max(dp[x][y], dp[a][b]+1) // 更新长度
				res = max(res, dp[x][y])
			}
		}
	}
	return res
}

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

330.按要求补齐数组(1)¶

题目

给定一个已排序的正整数数组 nums，和一个正整数n 。从[1, n]区间内选取任意个数字补充到nums中，
使得[1, n]区间内的任何数字都可以用nums中某几个数字的和来表示。
请输出满足上述要求的最少需要补充的数字个数。
示例1:输入: nums = [1,3], n = 6 输出: 1 
解释: 根据 nums里现有的组合[1], [3], [1,3]，可以得出1, 3, 4。
现在如果我们将2添加到nums 中，组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字1, 2, 3, 4, 5, 6，能够覆盖[1, 6]区间里所有的数。
所以我们最少需要添加一个数字。
示例 2:输入: nums = [1,5,10], n = 20 输出: 2
解释: 我们需要添加[2, 4]。
示例3:输入: nums = [1,2,2], n = 5 输出: 0

解题思路

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

func minPatches(nums []int, n int) int {
	res := 0
	target := 1
	for i := 0; target <= n; {
		// 对于正整数x，如果区间[1,x-1]内的所有数字都已经被覆盖，
		// 加上x后，则区间[1,2x-1]内的所有数字被覆盖。
		if i < len(nums) && nums[i] <= target {
			// 贪心思路：把当前在范围内的加上，target之前的[1,target-1]都已经满足
			target = target + nums[i]
			i++
		} else {
			// 没有就把target加入数组，范围扩大1倍
			target = target * 2
			res++
		}
	}
	return res
}

335.路径交叉(2)¶

题目

给定一个含有n个正数的数组x。从点(0,0)开始，先向北移动x[0]米，
然后向西移动x[1]米，向南移动x[2]米，向东移动x[3]米，持续移动。
也就是说，每次移动后你的方位会发生逆时针变化。
编写一个O(1)空间复杂度的一趟扫描算法，判断你所经过的路径是否相交。
示例1:
┌───┐
│  │
└───┼──>
  │
输入: [2,1,1,2] 输出: true 
示例2:
┌──────┐
│   │
│
│
└────────────>
输入: [1,2,3,4] 输出: false 
示例 3:
┌───┐
│  │
└───┼>
输入: [1,1,1,1] 输出: true 

解题思路

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

func isSelfCrossing(distance []int) bool {
	n := len(distance)
	if n < 4 {
		return false
	}
	for i := 3; i < n; i++ {
		// 长度为4相交
		if i >= 3 && distance[i] >= distance[i-2] &&
			distance[i-1] <= distance[i-3] {
			return true
		}
		// 长度为5相交
		if i >= 4 && distance[i]+distance[i-4] >= distance[i-2] &&
			distance[i-1] == distance[i-3] {
			return true
		}
		// 长度为6相交
		if i >= 5 && distance[i]+distance[i-4] >= distance[i-2] &&
			distance[i-1]+distance[i-5] >= distance[i-3] &&
			distance[i-2] > distance[i-4] &&
			distance[i-1] < distance[i-3] {
			return true
		}
	}
	return false
}

# 2
func isSelfCrossing(distance []int) bool {
	arr := append([]int{0, 0, 0, 0}, distance...)
	n := len(arr)
	i := 4
	// 圈变大
	for i < n && arr[i] > arr[i-2] {
		i++
	}
	if i == n {
		return false
	}
	if arr[i] >= arr[i-2]-arr[i-4] {
		arr[i-1] = arr[i-1] - arr[i-3]
	}
	i++
	// 圈变小
	for i < n && arr[i] < arr[i-2] {
		i++
	}
	if i == n {
		return false
	}
	return true
}

336.回文对¶

题目¶

给定一组 互不相同 的单词， 找出所有不同的索引对(i, j)，使得列表中的两个单词，
words[i] + words[j]，可拼接成回文串。
示例 1：输入：["abcd","dcba","lls","s","sssll"] 输出：[[0,1],[1,0],[3,2],[2,4]] 
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：输入：["bat","tab","cat"] 输出：[[0,1],[1,0]] 
解释：可拼接成的回文串为 ["battab","tabbat"]

解题思路¶

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

354.俄罗斯套娃信封问题(3)¶

题目

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明: 不允许旋转信封。
示例:输入: envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n)
02	贪心-二分查找	O(nlog(n))	O(n)
03	动态规划	O(n^2)	O(n)

func maxEnvelopes(envelopes [][]int) int {
	if len(envelopes) <= 1 {
		return len(envelopes)
	}
	// 宽[0] 高[1]排序
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] < envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})
	// 第i个信封套几个
	dp := make([]int, len(envelopes))
	for i := 0; i < len(dp); i++ {
		dp[i] = 1
	}
	res := 1
	for i := 1; i < len(envelopes); i++ {
		for j := 0; j < i; j++ {
			if envelopes[i][0] > envelopes[j][0] &&
				envelopes[i][1] > envelopes[j][1] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		res = max(res, dp[i])
	}
	return res
}

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

# 2
func maxEnvelopes(envelopes [][]int) int {
	if len(envelopes) <= 1 {
		return len(envelopes)
	}
	// 宽[0] 高[1]排序
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] < envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})
	arr := make([]int, 0)
	for i := 0; i < len(envelopes); i++ {
		left := 0
		right := len(arr) - 1
		for left <= right {
			mid := left + (right-left)/2
			if envelopes[i][1] > arr[mid] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
		if left >= len(arr) {
			arr = append(arr, envelopes[i][1])
		} else {
			arr[left] = envelopes[i][1]
		}
	}
	return len(arr)
}

# 3
func maxEnvelopes(envelopes [][]int) int {
	if len(envelopes) <= 1 {
		return len(envelopes)
	}
	// 宽[0] 高[1]排序
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] < envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})
	// 第i个信封套几个
	dp := make([]int, len(envelopes))
	dp[0] = 1
	res := 1
	for i := 1; i < len(envelopes); i++ {
		temp := 0
		for j := i - 1; j >= 0; j-- {
			if envelopes[i][0] > envelopes[j][0] &&
				envelopes[i][1] > envelopes[j][1] && dp[j] > temp {
				temp = dp[j]
			}
		}
		dp[i] = temp + 1
		if dp[i] > res {
			res = dp[i]
		}
	}
	return res
}

391.完美矩形(1)¶

题目

我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。
每个矩形用左下角的点和右上角的点的坐标来表示。例如，一个单位正方形可以表示为 [1,1,2,2]。
( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。
示例 1:rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]
返回 true。5个矩形一起可以精确地覆盖一个矩形区域。
示例2:rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]
返回 false。两个矩形之间有间隔，无法覆盖成一个矩形。
示例 3:rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]
返回 false。图形顶端留有间隔，无法覆盖成一个矩形。
示例 4:rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]
返回 false。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

解题思路

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

func isRectangleCover(rectangles [][]int) bool {
	minX, maxX := math.MaxInt32, math.MinInt32
	minY, maxY := math.MaxInt32, math.MinInt32
	res := 0
	m := make(map[string]bool)
	for i := 0; i < len(rectangles); i++ {
		a, b, c, d := rectangles[i][0], rectangles[i][1], rectangles[i][2], rectangles[i][3]
		minX = min(minX, a)
		minY = min(minY, b)
		maxX = max(maxX, c)
		maxY = max(maxY, d)
		res = res + (c-a)*(d-b)
		arr := []string{
            fmt.Sprintf("%d-%d", a, b), 
            fmt.Sprintf("%d-%d", c, d),
			fmt.Sprintf("%d-%d", a, d), 
            fmt.Sprintf("%d-%d", c, b),
        }
		for _, v := range arr {
			if _, ok := m[v]; ok {
				delete(m, v)
			} else {
				m[v] = true
			}
		}
	}
	if (maxX-minX)*(maxY-minY) != res { // 满足条件1：所有小矩形相加的面积之和要等于完美矩形的面积
		return false
	}
	if len(m) != 4 || // 满足条件2：除最终大矩形4个顶点外其它点都出现偶数次
		m[fmt.Sprintf("%d-%d", minX, minY)] == false || 
        m[fmt.Sprintf("%d-%d", minX, maxY)] == false ||
		m[fmt.Sprintf("%d-%d", maxX, minY)] == false || 
        m[fmt.Sprintf("%d-%d", maxX, maxY)] == false {
		return false
	}
	return true
}

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
}