0401-0500-Easy

401.二进制手表(3)

题目

二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。
例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

案例:输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

注意事项:
输出的顺序没有要求。
小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。

解题思路

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

func binCount(num int) int {
	count := make([]int, 0)
	for num != 0 {
		temp := num % 2
		count = append(count, temp)
		num = num / 2
	}
	countNum := 0
	for i := 0; i < len(count); i++ {
		if count[i] == 1 {
			countNum++
		}
	}
	return countNum
}

func readBinaryWatch(num int) []string {
	res := make([]string, 0)
	for i := 0; i < 12; i++ {
		for j := 0; j < 60; j++ {
			if binCount(i)+binCount(j) == num {
				res = append(res, fmt.Sprintf("%d:%02d", i, j))
			}
		}
	}
	return res
}

#
func readBinaryWatch(num int) []string {
	res := make([]string, 0)
	for i := 0; i < 12; i++ {
		for j := 0; j < 60; j++ {
			hour := fmt.Sprintf("%b", i)
			minute := fmt.Sprintf("%b", j)
			if strings.Count(hour, "1")+strings.Count(minute, "1") == num {
				res = append(res, fmt.Sprintf("%d:%02d", i, j))
			}
		}
	}
	return res
}

#
func readBinaryWatch(num int) []string {
	res := make([]string, 0)
	ledS := make([]bool, 10)

	var dfs func(int, int)
	dfs = func(idx, num int) {
		if num == 0 {
			// 满足条件
			m, h := get(ledS[:6]), get(ledS[6:])
			if h < 12 && m < 60 {
				res = append(res, fmt.Sprintf("%d:%02d", h, m))
			}
			return
		}
		for i := idx; i < 11-num; i++ {
			ledS[i] = true
			dfs(i+1, num-1)
			ledS[i] = false
		}
	}
	dfs(0, num)
	return res
}

func get(ledS []bool) int {
	bs := []int{1, 2, 4, 8, 16, 32}
	var sum int
	size := len(ledS)
	for i := 0; i < size; i++ {
		if ledS[i] {
			sum += bs[i]
		}
	}
	return sum
}

404.左叶子之和(2)

题目

计算给定二叉树的所有左叶子之和。
示例：
    3
   / \
  9  20
    /  \
   15   7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

解题思路

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

func sumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil {
		return sumOfLeftLeaves(root.Right)
	}
	if root.Left.Left == nil && root.Left.Right == nil {
		return root.Left.Val + sumOfLeftLeaves(root.Right)
	}
	return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}


#
func sumOfLeftLeaves(root *TreeNode) int {
	sum := 0
	if root == nil{
		return 0
	}
	queue := make([]*TreeNode,0)
	queue = append(queue, root)
	for len(queue) > 0{
		node := queue[0]
		queue = queue[1:]
		if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil{
			sum = sum + node.Left.Val
		}
		if node.Left != nil{
			queue = append(queue, node.Left)
		}
		if node.Right != nil{
			queue = append(queue, node.Right)
		}
	}
	return sum
}

405.数字转换为十六进制数(2)

题目

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
    十六进制中所有字母(a-f)都必须是小写。
    十六进制字符串中不能包含多余的前导零。
    如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。 
    给定的数确保在32位有符号整数范围内。
    不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例 1： 输入:26 输出:"1a"
示例 2： 输入:-1 输出:"ffffffff"

解题思路

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

var h = []string{
	"0", "1", "2", "3", "4", "5", "6", "7",
	"8", "9", "a", "b", "c", "d", "e", "f",
}

func toHex(num int) string {
	hex := ""
	if num == 0 {
		return "0"
	}

	for i := 0; i < 8 && num != 0; i++ {
		hex = h[num&15] + hex
		num = num >> 4
	}
	return hex
}

#
var h = []string{
	"0", "1", "2", "3", "4", "5", "6", "7",
	"8", "9", "a", "b", "c", "d", "e", "f",
}

func toHex(num int) string {
	res := ""
	if num == 0{
		return "0"
	}
	if num < 0 {
		num = num + 4294967296
	}

	for num != 0{
		temp := num % 16
		res = h[temp] + res
		num = num / 16
	}
	return res
}

409.最长回文串(2)

题目

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:假设字符串的长度不会超过 1010。
示例 1:输入:"abccccdd"输出:7
解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

解题思路

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

func longestPalindrome(s string) int {
	ret := 0
	a := [123]int{}
	for i := range s {
		a[s[i]]++
	}
	hasOdd := 0
	for i := range a {
		if a[i] == 0 {
			continue
		}
		if a[i] % 2 == 0 {
			ret += a[i]
		} else {
			ret += a[i] - 1
			hasOdd = 1
		}
	}
	return ret + hasOdd
}

#
func longestPalindrome(s string) int {
	ret := 0
	a := make(map[byte]int)
	for i := range s {
		a[s[i]]++
	}
	hasOdd := 0
	for i := range a {
		if a[i] == 0 {
			continue
		}
		if a[i]%2 == 0 {
			ret += a[i]
		} else {
			ret += a[i] - 1
			hasOdd = 1
		}
	}
	return ret + hasOdd
}

412.Fizz Buzz(1)

题目

写一个程序，输出从 1 到 n 数字的字符串表示。
1. 如果 n 是3的倍数，输出“Fizz”；
2. 如果 n 是5的倍数，输出“Buzz”；
3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：n = 15,
返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

解题思路

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

func fizzBuzz(n int) []string {
	ret := make([]string, n)
	for i := range ret {
		x := i + 1
		switch {
		case x%15 == 0:
			ret[i] = "FizzBuzz"
		case x%5 == 0:
			ret[i] = "Buzz"
		case x%3 == 0:
			ret[i] = "Fizz"
		default:
			ret[i] = strconv.Itoa(x)
		}
	}
	return ret
}

414.第三大的数(2)

题目

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1:输入: [3, 2, 1]输出: 1
解释: 第三大的数是 1.
示例 2:输入: [1, 2]输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:输入: [2, 2, 3, 1]输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。存在两个值为2的数，它们都排第二。

解题思路

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

func thirdMax(nums []int) int {
	max1, max2, max3 := math.MinInt64, math.MinInt64, math.MinInt64
	for _, n := range nums {
		if n == max1 || n == max2 {
			continue
		}
		switch {
		case max1 < n:
			max1, max2, max3 = n, max1, max2
		case max2 < n:
			max2, max3 = n, max2
		case max3 < n:
			max3 = n
		}
	}

	if max3 == math.MinInt64 {
		return max1
	}
	return max3
}

#
func thirdMax(nums []int) int {

	sort.Ints(nums)
	if len(nums) < 3 {
		return nums[len(nums)-1]
	}

	k := 2
	maxValue := nums[len(nums)-1]
	for i := len(nums) - 2; i >= 0; i-- {
		if nums[i] != nums[i+1] {
			k--
		}
		if k == 0 {
			return nums[i]
		}
	}
	return maxValue
}

415.字符串相加(2)

题目

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

解题思路

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

func addStrings(num1 string, num2 string) string {
	if len(num1) > len(num2) {
		num1, num2 = num2, num1
	}
	n1, n2 := len(num1), len(num2)
	a1, a2 := []byte(num1), []byte(num2)
	carry := byte(0)
	buf := make([]byte, n2+1)
	buf[0] = '1'

	for i := 1; i <= n2; i++ {
		if i <= n1 {
			buf[n2+1-i] = a1[n1-i] - '0'
		}
		buf[n2+1-i] = buf[n2+1-i] + a2[n2-i] + carry

		if buf[n2+1-i] > '9' {
			buf[n2+1-i] = buf[n2+1-i] - 10
			carry = byte(1)
		} else {
			carry = byte(0)
		}
	}
	if carry == 1 {
		return string(buf)
	}
	return string(buf[1:])
}

#
func addStrings(num1 string, num2 string) string {
	if len(num1) > len(num2) {
		num1, num2 = num2, num1
	}
	n1, n2 := len(num1), len(num2)
	a1, a2 := []byte(num1), []byte(num2)
	a1 = reverse(a1)
	a2 = reverse(a2)

	carry := 0
	buf := make([]byte, 0)
	for i := 0; i < n2; i++ {
		temp := 0
		if i < n1 {
			temp = int(a1[i] - '0')
		}
		temp = int(a2[i]-'0') + temp + carry
		if temp > 9 {
			buf = append(buf, byte(temp-10+'0'))
			carry = 1
		} else {
			buf = append(buf, byte(temp+'0'))
			carry = 0
		}
	}
	if carry == 1 {
		buf = append(buf, byte('1'))
	}
	return string(reverse(buf))
}

func reverse(arr []byte) []byte {
	for i := 0; i < len(arr)/2; i++ {
		arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
	}
	return arr
}

434.字符串中的单词数(2)

题目

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。
示例:输入: "Hello, my name is John"输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。

解题思路

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

func countSegments(s string) int {
	if len(s) == 0 {
		return 0
	}
	return len(strings.Fields(s))
}

#
func countSegments(s string) int {
	count := 0
	for i := 0; i < len(s); i++{
		if (i == 0 || s[i-1] == ' ') && s[i] != ' '{
			count++
		}
	}
	return count
}

437.路径总和III(4)

题目

给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:
1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n^2)	O(n)
02	2次递归	O(n^2)	O(n)
03	迭代+递归	O(n^2)	O(n)
04	保存路径	O(n^2)	O(n)

func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	res := 0
	var helper func(*TreeNode, int)
	helper = func(node *TreeNode, sum int) {
		if node == nil {
			return
		}
		sum = sum - node.Val
		// 路径不需要从根节点开始，也不需要在叶子节点结束
		if sum == 0 {
			res++
		}
		helper(node.Left, sum)
		helper(node.Right, sum)
	}
	helper(root, sum)
	return res + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

#
func helper(node *TreeNode, sum int) int {
	if node == nil {
		return 0
	}
	sum = sum - node.Val
	res := 0
	if sum == 0 {
		res = 1
	}
	return res + helper(node.Left, sum) + helper(node.Right, sum)
}

func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	return helper(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

# 迭代+递归
func helper(node *TreeNode, sum int, curSum int) int {
	res := 0
	curSum = curSum + node.Val
	if curSum == sum {
		res++
	}
	if node.Left != nil {
		res += helper(node.Left, sum, curSum)
	}
	if node.Right != nil {
		res += helper(node.Right, sum, curSum)
	}
	return res
}

func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	res := 0
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		tempSum := 0
		res += helper(node, sum, tempSum)
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return res
}

#
func helper(node *TreeNode, sum int, path []int, level int) int {
	if node == nil {
		return 0
	}
	res := 0
	if sum == node.Val {
		res = 1
	}
	temp := node.Val
	for i := level - 1; i >= 0; i-- {
		temp = temp + path[i]
		if temp == sum {
			res++
		}
	}
	path[level] = node.Val
	return res + helper(node.Left, sum, path, level+1) + 
		helper(node.Right, sum, path, level+1)
}

func pathSum(root *TreeNode, sum int) int {
	return helper(root, sum, make([]int, 1001), 0)
}

441.排列硬币(3)

题目

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
示例 2:n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.

解题思路

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

func arrangeCoins(n int) int {
	return int(math.Sqrt(float64(2*n)+0.25) - 0.5)
}

#
func arrangeCoins(n int) int {
	i := 1
	for i <= n{
		n = n - i
		i++
	}
	return i-1
}

#
func arrangeCoins(n int) int {
	if n == 0{
		return 0
	}
	left, right := 1, n
	for left < right{
		mid := left + (right-left)/2
		if mid * (mid+1)/2 < n{
			left = mid + 1
		}else {
			right = mid
		}
	}
	if left*(left+1)/2 == n{
		return left
	}
	return left-1
}

443.压缩字符串(1)

题目

给定一组字符，使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
在完成原地修改输入数组后，返回数组的新长度。
进阶：你能否仅使用O(1) 空间解决问题？

示例 1：输入：["a","a","b","b","c","c","c"]
输出：返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]
说明："aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。

示例 2：输入：["a"]
输出：返回1，输入数组的前1个字符应该是：["a"]
说明：没有任何字符串被替代。

示例 3：输入：["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：返回4，输入数组的前4个字符应该是：["a","b","1","2"]。
说明：由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
注意每个数字在数组中都有它自己的位置。
注意：
    所有字符都有一个ASCII值在[35, 126]区间内。
    1 <= len(chars) <= 1000。

解题思路

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

func compress(chars []byte) int {
	j := 0
	count := 1
	for i := 0; i < len(chars); i++ {
		char := chars[i]
		if i+1 < len(chars) && char == chars[i+1] {
			count++
		} else {
			chars[j] = char
			j++
			if count > 1 {
				for _, num := range strconv.Itoa(count) {
					chars[j] = byte(num)
					j++
				}
			}
			count = 1
		}
	}
	return j
}

447.回旋镖的数量(1)

题目

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，
其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
示例:
输入:[[0,0],[1,0],[2,0]]
输出:2
解释:两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

解题思路

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

func numberOfBoomerangs(points [][]int) int {
	res := 0
	size := len(points)
	if size < 3 {
		return 0
	}
	for i := 0; i < size; i++ {
		dMap := make(map[int]int, size)
		for j := 0; j < size; j++ {
			if i == j {
				continue
			}
			d := dSquare(points[i], points[j])
			if _, ok := dMap[d]; ok {
				dMap[d]++
			} else {
				dMap[d] = 1
			}
		}
		// 相同距离的v个点，总共有 v*(v-1)种排列
		for _, v := range dMap {
			res = res + v*(v-1)
		}
	}
	return res
}

func dSquare(p1, p2 []int) int {
	x := p2[0] - p1[0]
	y := p2[1] - p1[1]
	return x*x + y*y
}

448.找到所有数组中消失的数字(3)

题目

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

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

解题思路

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

func findDisappearedNumbers(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		for nums[i] != nums[nums[i]-1] {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}
	res := make([]int, 0)
	for i, n := range nums {
		if n != i+1 {
			res = append(res, i+1)
		}
	}
	return res
}

#
func findDisappearedNumbers(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		value := nums[i]
		if value < 0{
			value = -value
		}
		if nums[value-1] > 0{
			nums[value-1] = -nums[value-1]
		}
	}
	res := make([]int, 0)
	for key, value := range nums {
		if value > 0{
			res = append(res, key+1)
		}
	}
	return res
}

#
func findDisappearedNumbers(nums []int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]] = 1
	}
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		if _, ok := m[i+1]; !ok {
			res = append(res, i+1)
		}
	}
	return res
}

453.最小移动次数使数组元素相等(2)

题目

给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
示例:输入:[1,2,3]输出:3
解释:只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

解题思路

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

func minMoves(nums []int) int {
	sum := 0
	min := nums[0]
	for _, n := range nums {
		sum += n
		if min > n {
			min = n
		}
	}
	return sum - min*len(nums)
}

#
func minMoves(nums []int) int {
	sum := 0
	sort.Ints(nums)
	for i := 1; i < len(nums); i++{
		sum = sum + nums[i] - nums[0]
	}
	return sum
}

455.分发饼干(1)

题目

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；
并且每块饼干 j ，都有一个尺寸 sj 。
如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

示例 1:输入: [1,2,3], [1,1]  输出: 1
解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。

示例 2:输入: [1,2], [1,2,3] 输出: 2
解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2.

解题思路

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

func findContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	var i, j int
	for i < len(g) && j < len(s) {
		if g[i] <= s[j] {
			i++
		}
		j++
	}
	return i
}

459.重复的子字符串(2)

题目

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。
给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:输入: "abab"输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:输入: "aba"输出: False
示例 3:输入: "abcabcabcabc"输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

解题思路

No.	思路	时间复杂度	空间复杂度
01	2倍去除首尾匹配	O(n)	O(1)
02	暴力匹配	O(n^2)	O(1)

func repeatedSubstringPattern(s string) bool {
	if len(s) == 0 {
		return false
	}

	size := len(s)
	ss := (s + s)[1 : size*2-1]
	return strings.Contains(ss, s)
}

#
func repeatedSubstringPattern(s string) bool {
	if len(s) == 0 {
		return false
	}
	size := len(s)
	for i := 1; i < size; i++ {
		if size%i == 0 {
			count := size / i
			if strings.Repeat(s[0:i], count) == s {
				return true
			}
		}
	}
	return false
}

461.汉明距离(3)

题目

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4输出: 2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

解题思路

No.	思路	时间复杂度	空间复杂度
01	位运算+遍历统计	O(1)	O(1)
02	位运算	O(1)	O(1)
03	内置函数	O(1)	O(1)

func hammingDistance(x int, y int) int {
	x = x ^ y
	res := 0
	for x > 0 {
		if x&1 == 1{
			res++
		}
		x = x >> 1
	}
	return res
}

#
func hammingDistance(x int, y int) int {
	x = x ^ y
	res := 0
	for x > 0 {
		res++
		x = x & (x-1)
	}
	return res
}

#
func hammingDistance(x int, y int) int {
	x = x ^ y
	return bits.OnesCount(uint(x))
}

463.岛屿的周长(3)

题目

给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。
整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。
网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 :
输入:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
输出: 16

解题思路

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

func islandPerimeter(grid [][]int) int {
	var dx = []int{-1, 1, 0, 0}
	var dy = []int{0, 0, -1, 1}
	m, n := len(grid), len(grid[0])
	res := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 {
				continue
			}
			res += 4
			for k := 0; k < 4; k++ {
				x := i + dx[k]
				y := j + dy[k]
				if (0 <= x && x < m && 0 <= y && y < n) && grid[x][y] == 1 {
					res--
				}
			}
		}
	}
	return res
}

#
func islandPerimeter(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	res := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 {
				continue
			}
			res += 4
			if i > 0 && grid[i-1][j] == 1 {
				res -= 2
			}
			if j > 0 && grid[i][j-1] == 1 {
				res -= 2
			}
		}
	}
	return res
}

#
func islandPerimeter(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				return dfs(grid, i, j)
			}
		}
	}
	return 0
}

func dfs(grid [][]int, i, j int) int {
	// 边界+1
	if !(0 <= i && i < len(grid) && 0 <= j && j < len(grid[0])) {
		return 1
	}
	// 水域+1
	if grid[i][j] == 0 {
		return 1
	}
	if grid[i][j] != 1 {
		return 0
	}
	grid[i][j] = 2
	return dfs(grid, i-1, j) +
		dfs(grid, i+1, j) +
		dfs(grid, i, j-1) +
		dfs(grid, i, j+1)
}

475.供暖器(2)

题目

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
    给出的房屋和供暖器的数目是非负数且不会超过 25000。
    给出的房屋和供暖器的位置均是非负数且不会超过10^9。
    只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
    所有供暖器都遵循你的半径标准，加热的半径也一样。
    
示例 1:输入: [1,2,3],[2] 输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

示例 2:输入: [1,2,3,4],[1,4] 输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

解题思路

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

func findRadius(houses []int, heaters []int) int {
	if len(heaters) == 0 {
		return 0
	}
	sort.Ints(houses)
	sort.Ints(heaters)
	res := 0
	j := 0
	for i := 0; i < len(houses); i++ {
		// 找到最近的一个供暖器, >=确保出现重复的供暖器会往后走
		for j < len(heaters)-1 &&
			Abs(houses[i], heaters[j]) >= Abs(houses[i], heaters[j+1]) {
			j++
		}
		res = Max(Abs(houses[i], heaters[j]), res)
	}
	return res
}

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

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

#
func findRadius(houses []int, heaters []int) int {
	if len(heaters) == 0 {
		return 0
	}
	sort.Ints(houses)
	sort.Ints(heaters)
	res := 0
	length := len(heaters)
	for i := 0; i < len(houses); i++ {
		left := 0
		right := length - 1
		for left < right {
			mid := left + (right-left)/2
			if heaters[mid] < houses[i] {
				left = mid + 1
			} else {
				right = mid
			}
		}
		dis := 0
		if heaters[left] < houses[i] {
			dis = houses[i] - heaters[left]
		} else if heaters[left] > houses[i] {
			if left == 0 {
				dis = heaters[0] - houses[i]
			} else {
				dis = Min(heaters[left]-houses[i], houses[i]-heaters[left-1])
			}
		}
		res = Max(res, dis)
	}
	return res
}

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

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

476.数字的补数(3)

题目

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

示例 1:输入: 5 输出: 2
解释: 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
示例 2:输入: 1 输出: 0
解释: 1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
注意:
    给定的整数保证在 32 位带符号整数的范围内。
    你可以假定二进制数不包含前导零位。
    本题与 1009 https://leetcode.cn/problems/complement-of-base-10-integer/ 相同

解题思路

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

func findComplement(num int) int {
	temp := 1
	for num >= temp {
		temp = temp << 1
	}
	return temp - 1 - num
}

#
func findComplement(num int) int {
	temp := num
	res := 0
	for temp > 0 {
		temp = temp >> 1
		res = res << 1
		res++
	}
	return res ^ num
}

#
func findComplement(num int) int {
	res := 0
	if num == 0 {
		return 1
	}
	if num == 1 {
		return 0
	}

	exp := 1
	for num > 0 {
		temp := num % 2
		if temp == 0 {
			res = res + exp
			exp = exp * 2
		} else {
			exp = exp * 2
		}
		num = num / 2
	}
	return res
}

482.密钥格式化(2)

题目

有一个密钥字符串 S ，只包含字母，数字以及 '-'（破折号）。
其中， N 个 '-' 将字符串分成了 N+1 组。

给你一个数字 K，请你重新格式化字符串，除了第一个分组以外，每个分组要包含 K 个字符；
而第一个分组中，至少要包含 1 个字符。
两个分组之间需要用 '-'（破折号）隔开，并且将所有的小写字母转换为大写字母。
给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。

示例 1：输入：S = "5F3Z-2e-9-w", K = 4 输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；注意，两个额外的破折号需要删掉。

示例 2：输入：S = "2-5g-3-J", K = 2 输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，
第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。
提示:
    S 的长度可能很长，请按需分配大小。K 为正整数。
    S 只包含字母数字（a-z，A-Z，0-9）以及破折号'-'
    S 非空

解题思路

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

func licenseKeyFormatting(S string, K int) string {
	arr := strings.Join(strings.Split(strings.ToUpper(S), "-"), "")
	count := len(arr) / K
	first := len(arr) % K
	if first > 0 {
		count++
	}
	str := arr[:first]
	if first != 0 {
		count = count - 1
	}
	for i := 0; i < count; i++ {
		str = str + "-" + arr[first+i*K:first+(i+1)*K]
	}
	return strings.Trim(str, "-")
}

#
func licenseKeyFormatting(S string, K int) string {
	res := make([]rune, 0)
	temp := []rune(S)
	count := 0
	for i := len(temp) - 1; i >= 0; i-- {
		value := temp[i]
		if value >= 'a' {
			value = value - 'a' + 'A'
		}
		if value == '-' {
			continue
		}
		count++
		res = append([]rune{value}, res...)
		if count == K {
			res = append([]rune{'-'}, res...)
			count = 0
		}
	}
	if len(res) == 0 {
		return ""
	}
	if res[0] == '-' {
		res = res[1:]
	}
	return string(res)
}

485.最大连续1的个数(2)

题目

给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:输入: [1,1,0,1,1,1]输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：
    输入的数组只包含 0 和1。
    输入数组的长度是正整数，且不超过 10,000。

解题思路

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

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

#
func findMaxConsecutiveOnes(nums []int) int {
	max := 0
	count := 0
	for _, v := range nums {
		if v == 1 {
			count++
		} else {
			if count > max {
				max = count
			}
			count = 0
		}
	}
	if count > max {
		max = count
	}
	return max
}

492.构造矩形(1)

题目

作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 
现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

1. 你设计的矩形页面必须等于给定的目标面积。
2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。
3. 长度 L 和宽度 W 之间的差距应当尽可能小。

你需要按顺序输出你设计的页面的长度 L 和宽度 W。
示例：
输入: 4 输出: [2, 2]
解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。
但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 
所以输出长度 L 为 2， 宽度 W 为 2。
说明:
    给定的面积不大于 10,000,000 且为正整数。
    你设计的页面的长度和宽度必须都是正整数。

解题思路

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

func constructRectangle(area int) []int {
	for i := int(math.Sqrt(float64(area))); i > 1; i-- {
		if area%i == 0 {
			return []int{area / i, i}
		}
	}
	return []int{area, 1}
}

496.下一个更大元素 I(3)

题目

给定两个没有重复元素的数组nums1 和 nums2 ，其中nums1 是 nums2 的子集。
找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。
如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
    nums1和nums2中所有元素是唯一的。
    nums1和nums2 的数组大小都不超过1000。

解题思路

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

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	m := make(map[int]int)
	for i, n := range nums2 {
		m[n] = i
	}
	res := make([]int, len(nums1))
	for i, n := range nums1 {
		res[i] = -1
		for j := m[n] + 1; j < len(nums2); j++ {
			if n < nums2[j] {
				res[i] = nums2[j]
				break
			}
		}
	}
	return res
}

#
func nextGreaterElement(nums1 []int, nums2 []int) []int {
	m := make(map[int]int)
	res := make([]int, len(nums1))
	for i := 0; i < len(nums2); i++ {
		for j := i + 1; j < len(nums2); j++ {
			if nums2[j] > nums2[i] {
				m[nums2[i]] = nums2[j]
				break
			}
		}
	}
	for key, value := range nums1 {
		if _, ok := m[value]; ok {
			res[key] = m[value]
		} else {
			res[key] = -1
		}
	}
	return res
}

#
func nextGreaterElement(nums1 []int, nums2 []int) []int {
	m := make(map[int]int)
	res := make([]int, len(nums1))
	stack := make([]int, 0)
	for i := 0; i < len(nums2); i++ {
		if len(stack) > 0 {
			for len(stack) > 0 && nums2[i] > stack[len(stack)-1] {
				top := stack[len(stack)-1]
				m[top] = nums2[i]
				stack = stack[:len(stack)-1]
			}
		}
		stack = append(stack, nums2[i])
	}
	for key, value := range nums1 {
		if _, ok := m[value]; ok {
			res[key] = m[value]
		} else {
			res[key] = -1
		}
	}
	return res
}

500.键盘行(4)

题目

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
示例：
输入: ["Hello", "Alaska", "Dad", "Peace"]
输出: ["Alaska", "Dad"]
注意：
    你可以重复使用键盘上同一字符。
    你可以假设输入的字符串将只包含字母。

解题思路

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

func findWords(words []string) []string {
	m := make(map[byte]int)
	m['q'] = 1
	m['w'] = 1
	m['e'] = 1
	m['r'] = 1
	m['t'] = 1
	m['y'] = 1
	m['u'] = 1
	m['i'] = 1
	m['o'] = 1
	m['p'] = 1
	m['a'] = 2
	m['s'] = 2
	m['d'] = 2
	m['f'] = 2
	m['g'] = 2
	m['h'] = 2
	m['j'] = 2
	m['k'] = 2
	m['l'] = 2
	m['z'] = 3
	m['x'] = 3
	m['c'] = 3
	m['v'] = 3
	m['b'] = 3
	m['n'] = 3
	m['m'] = 3

	res := make([]string, 0)
	for i := 0; i < len(words); i++ {
		b := []byte(strings.ToLower(words[i]))
		level := m[b[0]]
		flag := true
		for j := 1; j < len(b); j++ {
			if m[b[j]] != level {
				flag = false
				break
			}
		}
		if flag {
			res = append(res, words[i])
		}
	}
	return res
}

#
var qRow = map[byte]bool{
	'q': true,
	'w': true,
	'e': true,
	'r': true,
	't': true,
	'y': true,
	'u': true,
	'i': true,
	'o': true,
	'p': true,
}

var aRow = map[byte]bool{
	'a': true,
	's': true,
	'd': true,
	'f': true,
	'g': true,
	'h': true,
	'j': true,
	'k': true,
	'l': true,
}

var zRow = map[byte]bool{
	'z': true,
	'x': true,
	'c': true,
	'v': true,
	'b': true,
	'n': true,
	'm': true,
}

func findWords(words []string) []string {
	res := make([]string, 0, len(words))
	for _, word := range words {
		w := strings.ToLower(word)
		if isAllIn(w, qRow) || isAllIn(w, aRow) || isAllIn(w, zRow) {
			res = append(res, word)
		}
	}
	return res
}

func isAllIn(s string, Row map[byte]bool) bool {
	for i := range s {
		if !Row[s[i]] {
			return false
		}
	}
	return true
}

#
func findWords(words []string) []string {
	res := make([]string, 0, len(words))
	for _, word := range words {
		w := strings.ToLower(word)
		flag := 0
		for _, m := range w {
			switch m {
			case 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p':
				if flag != 0 && flag != 1 {
					flag = 4
					break
				}
				flag = 1
			case 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l':
				if flag != 0 && flag != 2 {
					flag = 4
					break
				}
				flag = 2
			case 'z', 'x', 'c', 'v', 'b', 'n', 'm':
				if flag != 0 && flag != 3 {
					flag = 4
					break
				}
				flag = 3
			default:
				flag = 4
			}
		}
		if flag != 0 && flag != 4 {
			res = append(res, word)
		}
	}
	return res
}

#
func findWords(words []string) []string {
	res := make([]string, 0, len(words))
	q := "qwertyuiopQWERTYUIOP"
	a := "asdfghjklASDFGHJKL"
	z := "zxcvbnmZXCVBNM"
	for _, word := range words {
		qLen, aLen, zLen := 0, 0, 0
		for i := 0; i < len(word); i++ {
			if strings.Contains(q, string(word[i])) {
				qLen++
			}
			if strings.Contains(a, string(word[i])) {
				aLen++
			}
			if strings.Contains(z, string(word[i])) {
				zLen++
			}
		}
		if qLen == len(word) || aLen == len(word) || zLen == len(word) {
			res = append(res, word)
		}
	}
	return res
}

0401-0500-Medium

402.移掉K位数字(1)

题目

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:num 的长度小于 10002 且 ≥ k。
    num 不会包含任何前导零。
示例 1 :输入: num = "1432219", k = 3 输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :输入: num = "10200", k = 1 输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :输入: num = "10", k = 2 输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

解题思路

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

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

406.根据身高重建队列(2)

题目

假设有打乱顺序的一群人站成一个队列。 
每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 
编写一个算法来重建这个队列。
注意： 总人数少于1100人。
示例 输入:[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

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

func reconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(i, j int) bool {
		if people[i][0] == people[j][0] {
			return people[i][1] < people[j][1] // k 递增
		}
		return people[i][0] > people[j][0] // 升高 递减
	})
	for i := 0; i < len(people); i++ {
		index := people[i][1]
		p := people[i]
		copy(people[index+1:i+1], people[index:i+1]) // 后移
		people[index] = p
	}
	return people
}

# 2
func reconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(i, j int) bool {
		if people[i][0] == people[j][0] {
			return people[i][1] < people[j][1] // k 递增
		}
		return people[i][0] > people[j][0] // 升高 递减
	})
	for i := 0; i < len(people); i++ {
		index := people[i][1]
		p := people[i]
		// copy(people[index+1:i+1], people[index:i+1]) // 后移
		for j := i; j > index; j-- {
			people[j] = people[j-1]
		}
		people[index] = p
	}
	return people
}

413.等差数列划分(3)

题目

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。
数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

解题思路

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

func numberOfArithmeticSlices(A []int) int {
	n := len(A)
	if n < 3 {
		return 0
	}
	res := 0
	count := 2
	diff := A[1] - A[0]
	for i := 2; i < n; i++ {
		a := A[i] - A[i-1]
		if a == diff {
			count++
		} else {
			if count >= 3 {
				res = res + getValue(count)
			}
			count = 2
			diff = a
		}
	}
	if count >= 3 {
		res = res + getValue(count)
	}
	return res
}

func getValue(num int) int {
	n := num - 2
	return n * (n + 1) / 2
}

# 2
func numberOfArithmeticSlices(A []int) int {
	n := len(A)
	if n < 3 {
		return 0
	}
	res := 0
	dp := make([]int, n)
	for i := 2; i < n; i++ {
		if A[i]-A[i-1] == A[i-1]-A[i-2] {
			dp[i] = dp[i-1] + 1
		}
		res = res + dp[i]
	}
	return res
}

# 3
func numberOfArithmeticSlices(A []int) int {
	n := len(A)
	if n < 3 {
		return 0
	}
	res := 0
	for i := 0; i < n-2; i++ {
		diff := A[i+1] - A[i]
		for j := i + 2; j < n; j++ {
			if A[j]-A[j-1] == diff {
				res++
			} else {
				break
			}
		}
	}
	return res
}

416.分割等和子集(3)

题目

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:每个数组中的元素不会超过 100
    数组的大小不会超过 200
示例 1:输入: [1, 5, 11, 5] 输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:输入: [1, 2, 3, 5] 输出: false 
解释: 数组不能分割成两个元素和相等的子集.

解题思路

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

func canPartition(nums []int) bool {
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	if sum%2 == 1 {
		return false
	}
	target := sum / 2
	// 题目转换为0-1背包问题，容量为sum/2
	dp := make([][]bool, len(nums)+1)
	for i := 0; i <= len(nums); i++ {
		dp[i] = make([]bool, target+1)
		dp[i][0] = true
	}
	for i := 1; i <= len(nums); i++ {
		for j := 1; j <= target; j++ {
			if j-nums[i-1] < 0 {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
			}
		}
	}
	return dp[len(nums)][target]
}

# 2 
func canPartition(nums []int) bool {
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	if sum%2 == 1 {
		return false
	}
	target := sum / 2
	// 题目转换为0-1背包问题，容量为sum/2
	dp := make([]bool, target+1)
	dp[0] = true
	for i := 0; i < len(nums); i++ {
		for j := target; j >= 0; j-- {
			if j-nums[i] >= 0 && dp[j-nums[i]] == true {
				dp[j] = true
			}
		}
	}
	return dp[target]
}

# 3
func canPartition(nums []int) bool {
	sort.Ints(nums)
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	if sum%2 == 1 {
		return false
	}
	target := sum / 2
	return dfs(nums, target, 0)
}

func dfs(nums []int, target int, index int) bool {
	if target == 0 {
		return true
	}
	for i := index; i < len(nums); i++ {
		if index < i && nums[i] == nums[i-1] {
			continue
		}
		if target-nums[i] < 0 {
			return false
		}
		if dfs(nums, target-nums[i], i+1) == true {
			return true
		}
	}
	return false
}

417.太平洋大西洋水流问题(2)

题目

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。
“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：输出坐标的顺序不重要
m 和 n 都小于150
示例：给定下面的 5x5 矩阵:
太平洋 ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * 大西洋
返回:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

解题思路

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

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

func pacificAtlantic(heights [][]int) [][]int {
	res := make([][]int, 0)
	n, m = len(heights), len(heights[0])
	A, B := make([][]bool, n), make([][]bool, n)
	for i := 0; i < n; i++ {
		A[i], B[i] = make([]bool, m), make([]bool, m)
	}
	for i := 0; i < n; i++ { // 枚举左右两边往中间走
		dfs(heights, A, i, 0) // 最左边（同上边）走到A
		dfs(heights, B, i, m-1)
	}
	for j := 0; j < m; j++ { // 枚举上下两边往中间走
		dfs(heights, A, 0, j) // 最上边（同左边）走到A
		dfs(heights, B, n-1, j)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if A[i][j] == true && B[i][j] == true {
				res = append(res, []int{i, j})
			}
		}
	}
	return res
}

func dfs(heights [][]int, visited [][]bool, i, j int) {
	visited[i][j] = true
	for k := 0; k < 4; k++ {
		x, y := dx[k]+i, dy[k]+j
		if 0 <= x && x < n && 0 <= y && y < m &&
			heights[x][y] >= heights[i][j] && visited[x][y] == false {
			dfs(heights, visited, x, y)
		}
	}
}

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

func pacificAtlantic(heights [][]int) [][]int {
	res := make([][]int, 0)
	n, m = len(heights), len(heights[0])
	queue = make([][2]int, 0)
	A, B := make([][]bool, n), make([][]bool, n)
	for i := 0; i < n; i++ {
		A[i], B[i] = make([]bool, m), make([]bool, m)
	}
	for i := 0; i < n; i++ { // 枚举左右两边往中间走
		queue = append(queue, [2]int{i, 0})
		A[i][0] = true
		bfs(heights, A) // 最左边（同上边）走到A
		queue = append(queue, [2]int{i, m - 1})
		B[i][m-1] = true
		bfs(heights, B)
	}
	for j := 0; j < m; j++ { // 枚举上下两边往中间走
		queue = append(queue, [2]int{0, j})
		A[0][j] = true
		bfs(heights, A) // 最上边（同左边）走到A
		queue = append(queue, [2]int{n - 1, j})
		B[n-1][j] = true
		bfs(heights, B)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if A[i][j] == true && B[i][j] == true {
				res = append(res, []int{i, j})
			}
		}
	}
	return res
}

func bfs(heights [][]int, visited [][]bool) {
	for len(queue) > 0 {
		i, j := queue[0][0], queue[0][1]
		queue = queue[1:]
		for k := 0; k < 4; k++ {
			x, y := dx[k]+i, dy[k]+j
			if 0 <= x && x < n && 0 <= y && y < m &&
				heights[x][y] >= heights[i][j] && visited[x][y] == false {
				visited[x][y] = true
				queue = append(queue, [2]int{x, y})
			}
		}
	}
}

419.甲板上的战舰(3)

题目

给定一个二维的甲板， 请计算其中有多少艘战舰。战舰用'X'表示，空位用'.'表示。你需要遵守以下规则：
给你一个有效的甲板，仅由战舰或者空位组成。
战舰只能水平或者垂直放置。换句话说,战舰只能由1xN (1 行, N 列)组成，
或者Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
两艘战舰之间至少有一个水平或垂直的空位分隔- 即没有相邻的战舰。
示例 :
X..X
...X
...X
在上面的甲板中有2艘战舰。
无效样例 :
...X
XXXX
...X
你不会收到这样的无效甲板- 因为战舰之间至少会有一个空位将它们分开。
进阶:你可以用一次扫描算法，只使用O(1)额外空间，并且不修改甲板的值来解决这个问题吗？

解题思路

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

func countBattleships(board [][]byte) int {
	res := 0
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == 'X' {
				if (i > 0 && board[i-1][j] == 'X') ||
					(j > 0 && board[i][j-1] == 'X') {
					continue
				}
				res++
			}
		}
	}
	return res
}

# 2
func countBattleships(board [][]byte) int {
	res := 0
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == 'X' {
				res++
				board[i][j] = '.'
				for x := i + 1; x < len(board); x++ {
					if board[x][j] == 'X' {
						board[x][j] = '.'
					} else {
						break
					}
				}
				for y := j + 1; y < len(board[i]); y++ {
					if board[i][y] == 'X' {
						board[i][y] = '.'
					} else {
						break
					}
				}
			}
		}
	}
	return res
}

# 3
func countBattleships(board [][]byte) int {
	a, b := len(board), len(board[0])
	fa = Init(a * b)
	m := make(map[int]bool)
	arr := make([]int, 0)
	for i := 0; i < a; i++ {
		for j := 0; j < b; j++ {
			if board[i][j] == 'X' {
				if i < a-1 && board[i][j] == board[i+1][j] {
					union(i*b+j, i*b+b+j)
				}
				if j < b-1 && board[i][j] == board[i][j+1] {
					union(i*b+j, i*b+j+1)
				}
				arr = append(arr, i*b+j)
			}
		}
	}
	for i := 0; i < len(arr); i++ {
		m[find(arr[i])] = true
	}
	return len(m)
}

var fa []int

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

func union(a, b int) {
	x, y := find(a), find(b)
	if x != y {
		fa[x] = y
	}
}

// 彻底路径压缩
func find(x int) int {
	if fa[x] != x {
		fa[x] = find(fa[x])
	}
	return fa[x]
}

421.数组中两个数的最大异或值(2)

题目

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：输入：nums = [3,10,5,25,2,8] 输出：28
解释：最大运算结果是 5 XOR 25 = 28.
示例 2：输入：nums = [0] 输出：0
示例 3：输入：nums = [2,4] 输出：6
示例 4：输入：nums = [8,10,2] 输出：10
示例 5：输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70] 输出：127
提示：1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1

解题思路

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

func findMaximumXOR(nums []int) int {
	res := 0
	target := 0
	for i := 31; i >= 0; i-- { // 枚举每一位（第i位，从右到左），判断该为能否为1
		m := make(map[int]bool)
		target = target | (1 << i) // target第i位置1
		for j := 0; j < len(nums); j++ {
			m[nums[j]&target] = true // 高位&：取前缀
		}
		temp := res | (1 << i) // 假设结果第i位为1
		// a ^ b = temp
		// temp ^ a = b
		for k := range m {
			if _, ok := m[temp^k]; ok {
				res = temp // 能取到1
				break
			}
		}
	}
	return res
}

# 2
func findMaximumXOR(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	res := 0
	root := Trie{
		next: make([]*Trie, 2), // 0和1
	}
	for i := 0; i < n; i++ {
		temp := &root
		for j := 31; j >= 0; j-- {
			value := (nums[i] >> j) & 1
			if temp.next[value] == nil {
				temp.next[value] = &Trie{
					next: make([]*Trie, 2),
				}
			}
			temp = temp.next[value]
		}
	}
	for i := 0; i < n; i++ {
		temp := &root
		cur := 0
		for j := 31; j >= 0; j-- {
			value := (nums[i] >> j) & 1
			if temp.next[value^1] != nil { // 能取到1
				cur = cur | (1 << j) // 结果在该位可以为1
				temp = temp.next[value^1]
			} else {
				temp = temp.next[value]
			}
		}
		res = max(res, cur)
	}
	return res
}

type Trie struct {
	next []*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
}

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

423.从英文中重建数字(1)

题目

给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。
注意:输入只包含小写英文字母。
输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
输入字符串的长度小于 50,000。
示例 1:输入: "owoztneoer"输出: "012" (zeroonetwo)
示例 2:输入: "fviefuro"输出: "45" (fourfive)

解题思路

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

func originalDigits(s string) string {
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}
	// 利用字母唯一性
	arr := [10]int{}
	arr[0] = m['z']
	arr[2] = m['w']
	arr[4] = m['u']
	arr[6] = m['x']
	arr[8] = m['g']
	arr[3] = m['t'] - arr[2] - arr[8]
	arr[1] = m['o'] - arr[0] - arr[2] - arr[4]
	arr[7] = m['s'] - arr[6]
	arr[5] = m['v'] - arr[7]
	arr[9] = m['i'] - arr[5] - arr[6] - arr[8]
	res := make([]byte, 0)
	for i := 0; i < 10; i++ {
		for j := 0; j < arr[i]; j++ {
			res = append(res, byte(i+'0'))
		}
	}
	return string(res)
}

424.替换后的最长重复字符(3)

题目

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换k次。
在执行上述操作后，找到包含重复字母的最长子串的长度。
注意:字符串长度 和 k 不会超过104。
示例 1:输入:s = "ABAB", k = 2输出: 4
解释:用两个'A'替换为两个'B',反之亦然。
示例 2:输入:s = "AABABBA", k = 1 输出: 4
解释:将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

解题思路

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

func characterReplacement(s string, k int) int {
	if s == "" {
		return 0
	}
	res := 0
	left := 0
	count := 0
	arr := [26]int{}
	for right := 0; right < len(s); right++ {
		arr[s[right]-'A']++
		if arr[s[right]-'A'] > count {
			count = arr[s[right]-'A']
		}
		for right-left+1-count > k {
			arr[s[left]-'A']--
			left++
		}
		if right-left+1 > res {
			res = right - left + 1
		}
	}
	return res
}

# 2
func characterReplacement(s string, k int) int {
	if s == "" {
		return 0
	}
	left := 0
	count := 0
	arr := [26]int{}
	for right := 0; right < len(s); right++ {
		arr[s[right]-'A']++
		if arr[s[right]-'A'] > count {
			count = arr[s[right]-'A']
		}
		if right-left+1-count > k { // 窗口内不同字符超过k个开始收缩左边界
			arr[s[left]-'A']--
			left++
		}
	}
	return len(s) - left
}

# 3
func characterReplacement(s string, k int) int {
	if s == "" {
		return 0
	}
	res := 0
	for i := 0; i < len(s); i++ {
		temp := k
		j := i + 1
		for ; j < len(s); j++ {
			if s[j] != s[i] {
				if temp == 0 {
					break
				}
				temp--
			}
		}
		if j-i+temp > len(s) {
			return len(s)
		}
		if j-i+temp > res {
			res = j - i + temp
		}
	}
	return res
}

427.建立四叉树(2)

题目

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵的 四叉树 的根结点。
注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False；
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
class Node {
    public boolean val;
  public boolean isLeaf;
  public Node topLeft;
  public Node topRight;
  public Node bottomLeft;
  public Node bottomRight;
}
我们可以按以下步骤为二维区域构建四叉树：
如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，
将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容，可以参考 wiki 。
四叉树格式：输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
如果 isLeaf 或者 val 的值为 True ，则表示它在列表[isLeaf, val] 中的值为 1 ；
如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。
示例 1：输入：grid = [[0,1],[1,0]] 输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。
示例 2：输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
topLeft，bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
解释如下图所示：
示例 3：输入：grid = [[1,1],[1,1]] 输出：[[1,1]]
示例 4：输入：grid = [[0]] 输出：[[1,0]]
示例 5：输入：grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]] 输出：[[0,1],[1,1],[1,0],[1,0],[1,1]]
提示：n == grid.length == grid[i].length
n == 2^x 其中 0 <= x <= 6

解题思路

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

func construct(grid [][]int) *Node {
	n := len(grid)
	return dfs(grid, 0, 0, n, n)
}

func dfs(grid [][]int, x1, y1, x2, y2 int) *Node {
	if x1+1 == x2 {
		value := false
		if grid[x1][y1] == 1 {
			value = true
		}
		return &Node{
			Val:    value,
			IsLeaf: true,
		}
	}
	midX := (x1 + x2) / 2
	midY := (y1 + y2) / 2
	tL := dfs(grid, x1, y1, midX, midY)
	tR := dfs(grid, x1, midY, midX, y2)
	bL := dfs(grid, midX, y1, x2, midY)
	bR := dfs(grid, midX, midY, x2, y2)
	if tL.IsLeaf == true && tR.IsLeaf == true && bL.IsLeaf == true && bR.IsLeaf == true &&
		((tL.Val == true && tR.Val == true && bL.Val == true && bR.Val == true) ||
			(tL.Val == false && tR.Val == false && bL.Val == false && bR.Val == false)) {
		return &Node{
			Val:    tL.Val,
			IsLeaf: true,
		}
	}
	return &Node{
		Val:         false,
		IsLeaf:      false,
		TopLeft:     tL,
		TopRight:    tR,
		BottomLeft:  bL,
		BottomRight: bR,
	}
}

# 2
func construct(grid [][]int) *Node {
	n := len(grid)
	return dfs(grid, 0, 0, n, n)
}

func dfs(grid [][]int, x1, y1, x2, y2 int) *Node {
	isLeaf := true
	for i := x1; i < x2; i++ {
		for j := y1; j < y2; j++ {
			if grid[i][j] != grid[x1][y1] {
				isLeaf = false
				break
			}
		}
	}
	if isLeaf == true {
		return &Node{
			Val:    grid[x1][y1] == 1,
			IsLeaf: true,
		}
	}
	midX := (x1 + x2) / 2
	midY := (y1 + y2) / 2
	tL := dfs(grid, x1, y1, midX, midY)
	tR := dfs(grid, x1, midY, midX, y2)
	bL := dfs(grid, midX, y1, x2, midY)
	bR := dfs(grid, midX, midY, x2, y2)
	return &Node{
		Val:         false,
		IsLeaf:      false,
		TopLeft:     tL,
		TopRight:    tR,
		BottomLeft:  bL,
		BottomRight: bR,
	}
}

429.N叉树的层序遍历(2)

题目

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[
     [1],
     [3,2,4],
     [5,6]
]
说明:
    树的深度不会超过 1000。
    树的节点总数不会超过 5000。

解题思路

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

func levelOrder(root *Node) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}
	queue := make([]*Node, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		temp := make([]int, 0)
		length := len(queue)
		for i := 0; i < length; i++ {
			if queue[i] != nil {
				temp = append(temp, queue[i].Val)
				for j := 0; j < len(queue[i].Children); j++ {
					queue = append(queue, queue[i].Children[j])
				}
			}
		}
		res = append(res, temp)
		queue = queue[length:]
	}
	return res
}

# 2
var res [][]int

func levelOrder(root *Node) [][]int {
	res = make([][]int, 0)
	if root == nil {
		return res
	}
	dfs(root, 0)
	return res
}

func dfs(root *Node, level int) {
	if root == nil {
		return
	}
	if len(res) == level {
		res = append(res, make([]int, 0))
	}
	res[level] = append(res[level], root.Val)
	for i := 0; i < len(root.Children); i++ {
		dfs(root.Children[i], level+1)
	}
}

430.扁平化多级双向链表(3)

题目

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。
这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
示例 1：输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：输入的多级列表如下图所示：
扁平化后的链表如下图：
示例 2：输入：head = [1,2,null,3] 输出：[1,3,2]
解释：输入的多级列表如下图所示：
  1---2---NULL
  |
  3---NULL
示例 3：输入：head = [] 输出：[]
如何表示测试用例中的多级链表？
以 示例 1 为例：
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL
序列化其中的每一级之后：
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
提示：节点数目不超过 1000
1 <= Node.val <= 10^5

解题思路

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

func flatten(root *Node) *Node {
	if root == nil {
		return nil
	}
	res := &Node{}
	cur := res
	for root != nil {
		cur.Next = root
		root.Prev = cur
		cur = cur.Next
		root = root.Next
		// 处理子节点
		if cur.Child != nil {
			ch := flatten(cur.Child)
			cur.Child = nil
			cur.Next = ch
			ch.Prev = cur
			// 指针移动
			for cur.Next != nil {
				cur = cur.Next
			}
		}
	}
	res.Next.Prev = nil
	return res.Next
}

# 2
var arr []*Node

func flatten(root *Node) *Node {
	arr = make([]*Node, 0)
	dfs(root)
	for i := 0; i < len(arr); i++ {
		if i+1 < len(arr) {
			arr[i].Next = arr[i+1]
		}
		if i > 0 {
			arr[i].Prev = arr[i-1]
		}
		arr[i].Child = nil
	}
	return root
}

func dfs(root *Node) {
	if root == nil {
		return
	}
	arr = append(arr, root)
	dfs(root.Child)
	dfs(root.Next)
}

# 3
func flatten(root *Node) *Node {
	cur := root
	stack := make([]*Node, 0)
	for cur != nil {
		// 处理child
		if cur.Child != nil {
			if cur.Next != nil {
				stack = append(stack, cur.Next)
			}
			cur.Child.Prev = cur
			cur.Next = cur.Child
			cur.Child = nil
			continue
		}
		if cur.Next != nil {
            cur.Child = nil
			cur = cur.Next
			continue
		}
		if len(stack) == 0 {
			break
		}
		last := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		cur.Next = last
		last.Prev = cur
		cur = last
	}
	return root
}

433.最小基因变化(3)

题目

一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如，基因序列由"AACCGGTT"变化至"AACCGGTA"即发生了一次基因变化。
与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，
请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
注意：起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。
假定起始基因序列与目标基因序列是不一样的。
示例 1：start: "AACCGGTT" end:   "AACCGGTA" bank: ["AACCGGTA"]
返回值: 1
示例 2：start: "AACCGGTT" end:   "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
返回值: 2
示例 3：start: "AAAAACCC" end:   "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
返回值: 3

解题思路

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

func minMutation(start string, end string, bank []string) int {
	arr := []byte{'A', 'T', 'C', 'G'}
	m := make(map[string]bool)
	for i := 0; i < len(bank); i++ {
		m[bank[i]] = true
	}
	if _, ok := m[end]; ok == false {
		return -1
	}
	res := 0
	queue := make([]string, 0)
	queue = append(queue, start)
	for len(queue) > 0 {
		res++
		length := len(queue)
		for i := 0; i < length; i++ {
			str := queue[i]
			for j := 0; j < len(str); j++ {
				for k := 0; k < len(arr); k++ {
					if arr[k] != str[j] {
						newStr := str[:j] + string(arr[k]) + str[j+1:]
						if _, ok := m[newStr]; ok {
							queue = append(queue, newStr)
							delete(m, newStr)
						}
						if newStr == end {
							return res
						}
					}
				}
			}
		}
		queue = queue[length:]
	}
	return -1
}

# 2
var res int

func minMutation(start string, end string, bank []string) int {
	res = math.MaxInt32
	m := make(map[string]bool)
	for i := 0; i < len(bank); i++ {
		m[bank[i]] = true
	}
	if _, ok := m[end]; ok == false {
		return -1
	}
	dfs(start, end, 0, bank, make([]bool, len(bank)))
	if res == math.MaxInt32 {
		return -1
	}
	return res
}

func dfs(start string, end string, index int, bank []string, visited []bool) {
	if start == end {
		if index < res {
			res = index
		}
		return
	}
	for i := 0; i < len(bank); i++ {
		if visited[i] == false && judge(start, bank[i]) {
			visited[i] = true
			dfs(bank[i], end, index+1, bank, visited)
			visited[i] = false
		}
	}
}

func judge(a, b string) bool {
	count := 0
	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			count++
		}
	}
	return count == 1
}

# 3
func minMutation(start string, end string, bank []string) int {
	arr := []byte{'A', 'T', 'C', 'G'}
	m := make(map[string]bool)
	for i := 0; i < len(bank); i++ {
		m[bank[i]] = true
	}
	if _, ok := m[end]; ok == false {
		return -1
	}
	res := 0
	queueA := make([]string, 0)
	queueA = append(queueA, start)
	queueB := make([]string, 0)
	queueB = append(queueB, end)
	for len(queueA) > 0 {
		res++
		if len(queueA) > len(queueB) {
			queueA, queueB = queueB, queueA
		}
		length := len(queueA)
		for i := 0; i < length; i++ {
			str := queueA[i]
			for j := 0; j < len(str); j++ {
				for k := 0; k < len(arr); k++ {
					if arr[k] != str[j] {
						newStr := str[:j] + string(arr[k]) + str[j+1:]
						if _, ok := m[newStr]; ok {
							queueA = append(queueA, newStr)
							delete(m, newStr)
						}
						for l := 0; l < len(queueB); l++ {
							if newStr == queueB[l] {
								return res
							}
						}
					}
				}
			}
		}
		queueA = queueA[length:]
	}
	return -1
}

435.无重叠区间(4)

题目

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:可以认为区间的终点总是大于它的起点。
    区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:输入: [ [1,2], [1,2], [1,2] ]输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:输入: [ [1,2], [2,3] ] 输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解题思路

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

func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	// 按照结束时间排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	count := 1
	end := intervals[0][1]
	for i := 0; i < len(intervals); i++ {
		node := intervals[i]
		if node[0] >= end {
			end = node[1]
			count++
		}
	}
	return len(intervals) - count
}

# 2
func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	// 按照结束时间排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	count := 0
	end := intervals[0][1]
	for i := 1; i < len(intervals); i++ {
		node := intervals[i]
		if node[0] >= end {
			end = node[1]
		} else {
			if node[1] < end {
				end = node[1]
			}
			count++
		}
	}
	return count
}

# 3
func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	// 按照结束时间排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	dp := make([]int, len(intervals))
	dp[0] = 1
	res := 1
	for i := 1; i < len(intervals); i++ {
		count := 0
		for j := i - 1; j >= 0; j-- {
			if intervals[j][1] <= intervals[i][0] {
				count = max(dp[j], count)
			}
		}
		dp[i] = count + 1
		res = max(res, dp[i])
	}
	return len(intervals) - res
}

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

# 4
func eraseOverlapIntervals(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	// 按照结束时间排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	dp := make([]int, len(intervals))
	dp[0] = 1
	res := 1
	for i := 1; i < len(intervals); i++ {
		count := 0
		for j := i - 1; j >= 0; j-- {
			if intervals[j][1] <= intervals[i][0] {
				count = max(dp[j], count)
				break
			}
		}
		dp[i] = max(dp[i-1], count+1)
		res = max(res, dp[i])
	}
	return len(intervals) - res
}

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

436.寻找右区间(2)

题目

给你一个区间数组 intervals ，其中intervals[i] = [starti, endi] ，且每个starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j ，并满足 startj>= endi ，且 startj 最小化 。
返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
示例 1：输入：intervals = [[1,2]] 输出：[-1]
解释：集合中只有一个区间，所以输出-1。
示例 2：输入：intervals = [[3,4],[2,3],[1,2]] 输出：[-1, 0, 1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。
示例 3：输入：intervals = [[1,4],[2,3],[3,4]] 输出：[-1, 2, -1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
提示：1 <=intervals.length <= 2 * 104
intervals[i].length == 2
-106 <= starti <= endi <= 106
每个间隔的起点都 不相同

解题思路

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

func findRightInterval(intervals [][]int) []int {
	m := make(map[int]int)
	n := len(intervals)
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = -1
		m[intervals[i][0]] = i // 存储start对应的下标，因为起点都不相同
	}
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] < intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ { //  有坑注意：可以跟自己相比 [[1,1],[3,4]] => [0,-1]
			// 满足startj >= endi的取最小值
			if intervals[i][1] <= intervals[j][0] {
				index := m[intervals[i][0]]
				res[index] = m[intervals[j][0]]
				break
			}
		}
	}
	return res
}

# 2
func findRightInterval(intervals [][]int) []int {
	m := make(map[int]int)
	n := len(intervals)
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = -1
		m[intervals[i][0]] = i // 存储start对应的下标，因为起点都不相同
	}
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] < intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})
	for i := 0; i < n; i++ {
		target := intervals[i][1]
		index := m[intervals[i][0]]
		left, right := i, n-1
		for left <= right {
			mid := left + (right-left)/2
			if target <= intervals[mid][0] {
				res[index] = m[intervals[mid][0]]
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
	}
	return res
}

438.找到字符串中所有字母异位词(2)

题目

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：字母异位词指字母相同，但排列不同的字符串。
    不考虑答案输出的顺序。
示例 1:输入: s: "cbaebabacd" p: "abc"输出: [0, 6]
解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:输入: s: "abab" p: "ab"输出: [0, 1, 2]
解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

解题思路

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

func findAnagrams(s string, p string) []int {
	res := make([]int, 0)
	if len(p) > len(s) {
		return res
	}
	arr1, arr2 := [26]int{}, [26]int{}
	for i := 0; i < len(p); i++ {
		arr1[p[i]-'a']++
		arr2[s[i]-'a']++
	}
	for i := 0; i < len(s)-len(p); i++ {
		if arr1 == arr2 {
			res = append(res, i)
		}
		arr2[s[i]-'a']--
		arr2[s[i+len(p)]-'a']++
	}
	if arr1 == arr2 {
		res = append(res, len(s)-len(p))
	}
	return res
}

# 2
func findAnagrams(s string, p string) []int {
	res := make([]int, 0)
	if len(p) > len(s) {
		return res
	}
	m1, m2 := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(p); i++ {
		m1[p[i]-'a']++
		m2[s[i]-'a']++
	}
	for i := 0; i < len(s)-len(p); i++ {
		if compare(m1, m2) {
			res = append(res, i)
		}
		m2[s[i]-'a']--
		if m2[s[i]-'a'] == 0 {
			delete(m2, s[i]-'a')
		}
		m2[s[i+len(p)]-'a']++
	}
	if compare(m1, m2) {
		res = append(res, len(s)-len(p))
	}
	return res
}

func compare(m1, m2 map[byte]int) bool {
	if len(m1) != len(m2) {
		return false
	}
	for k := range m1 {
		if m2[k] != m1[k] {
			return false
		}
	}
	return true
}

442.数组中重复的数据(5)

题目

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：输入: [4,3,2,7,8,2,3,1] 输出:[2,3]

解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	置反	O(n)	O(1)
03	置换	O(n)	O(1)
04	累加	O(n)	O(1)
05	排序	O(nlog(n))	O(1)

func findDuplicates(nums []int) []int {
	res := make([]int, 0)
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	for k, v := range m {
		if v == 2 {
			res = append(res, k)
		}
	}
	return res
}

# 2
func findDuplicates(nums []int) []int {
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		index := abs(nums[i]) - 1
		if nums[index] < 0 {
			res = append(res, abs(nums[i]))
		} else {
			nums[index] = -nums[index]
		}
	}
	return res
}

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

# 3
func findDuplicates(nums []int) []int {
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		for nums[nums[i]-1] != nums[i] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		}
	}
	for i := 0; i < len(nums); i++ {
		if nums[i]-1 != i {
			res = append(res, nums[i])
		}
	}
	return res
}

# 4
func findDuplicates(nums []int) []int {
	res := make([]int, 0)
	n := len(nums)
	for i := 0; i < n; i++ {
		index := nums[i]%(n+1) - 1
		nums[index] = nums[index] + (n + 1)
	}
	for i := 0; i < n; i++ {
		if nums[i]/(n+1) == 2 {
			res = append(res, i+1)
		}
	}
	return res
}

# 5
func findDuplicates(nums []int) []int {
	if len(nums) == 0 {
		return nil
	}
	sort.Ints(nums)
	res := make([]int, 0)
	prev := nums[0]
	count := 1
	for i := 1; i < len(nums); i++ {
		if prev == nums[i] {
			count++
		} else {
			if count == 2 {
				res = append(res, nums[i-1])
			}
			prev = nums[i]
			count = 1
		}
	}
	if count == 2 {
		res = append(res, nums[len(nums)-1])
	}
	return res
}

445.两数相加II(3)

题目

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。
它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7

解题思路

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

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	l1 = reverse(l1)
	l2 = reverse(l2)
	res := &ListNode{}
	cur := res
	carry := 0
	for l1 != nil || l2 != nil || carry > 0 {
		sum := carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		carry = sum / 10 // 进位
		cur.Next = &ListNode{Val: sum % 10}
		cur = cur.Next
	}
	return reverse(res.Next)
}

func reverse(head *ListNode) *ListNode {
	var result *ListNode
	var temp *ListNode
	for head != nil {
		temp = head.Next
		head.Next = result
		result = head
		head = temp
	}
	return result
}

# 2
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	stack1 := make([]int, 0)
	stack2 := make([]int, 0)
	for l1 != nil {
		stack1 = append(stack1, l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		stack2 = append(stack2, l2.Val)
		l2 = l2.Next
	}
	var res *ListNode
	carry := 0
	for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
		if len(stack1) > 0 {
			carry = carry + stack1[len(stack1)-1]
			stack1 = stack1[:len(stack1)-1]
		}
		if len(stack2) > 0 {
			carry = carry + stack2[len(stack2)-1]
			stack2 = stack2[:len(stack2)-1]
		}
		temp := &ListNode{
			Val:  carry % 10,
			Next: res,
		}
		carry = carry / 10
		res = temp
	}
	return res
}

# 3
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	a, b := l1, l2
	length1, length2 := 0, 0
	for a != nil {
		length1++
		a = a.Next
	}
	for b != nil {
		length2++
		b = b.Next
	}
	res, carry := add(l1, l2, length1, length2)
	if carry > 0 {
		return &ListNode{Val: carry, Next: res}
	}
	return res
}

func add(l1, l2 *ListNode, length1, length2 int) (res *ListNode, carry int) {
	if l1 != nil && l2 != nil {
		if l1.Next == nil && l2.Next == nil {
			val := l1.Val + l2.Val
			carry = val / 10
			res = &ListNode{Val: val % 10, Next: nil}
			return
		}
	}
	a := &ListNode{}
	var b, n int
	if length1 > length2 {
		a, b = add(l1.Next, l2, length1-1, length2)
		n = l1.Val + b
	} else if length1 < length2 {
		a, b = add(l1, l2.Next, length1, length2-1)
		n = l2.Val + b
	} else {
		a, b = add(l1.Next, l2.Next, length1-1, length2-1)
		n = l1.Val + l2.Val + b
	}
	res = &ListNode{Val: n % 10, Next: a}
	carry = n / 10
	return
}

449.序列化和反序列化二叉搜索树(2)

题目

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，
以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 
您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

解题思路

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

type Codec struct {
	res []string
}

func Constructor() Codec {
	return Codec{}
}

func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return "#"
	}
	return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)
}

func (this *Codec) deserialize(data string) *TreeNode {
	this.res = strings.Split(data, ",")
	return this.dfsDeserialize()
}

func (this *Codec) dfsDeserialize() *TreeNode {
	node := this.res[0]
	this.res = this.res[1:]
	if node == "#" {
		return nil
	}
	value, _ := strconv.Atoi(node)
	return &TreeNode{
		Val:   value,
		Left:  this.dfsDeserialize(),
		Right: this.dfsDeserialize(),
	}
}

# 2
type Codec struct {
	res []string
}

func Constructor() Codec {
	return Codec{}
}

func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return ""
	}
	res := make([]string, 0)
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node != nil {
			res = append(res, strconv.Itoa(node.Val))
			queue = append(queue, node.Left, node.Right)
		} else {
			res = append(res, "#")
		}
	}
	return strings.Join(res, ",")
}

func (this *Codec) deserialize(data string) *TreeNode {
	if len(data) == 0 || data == "" {
		return nil
	}
	res := strings.Split(data, ",")
	root := &TreeNode{}
	root.Val, _ = strconv.Atoi(res[0])
	res = res[1:]
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		if res[0] != "#" {
			left, _ := strconv.Atoi(res[0])
			queue[0].Left = &TreeNode{Val: left}
			queue = append(queue, queue[0].Left)
		}
		if res[1] != "#" {
			right, _ := strconv.Atoi(res[1])
			queue[0].Right = &TreeNode{Val: right}
			queue = append(queue, queue[0].Right)
		}
		queue = queue[1:]
		res = res[2:]
	}
	return root
}

450.删除二叉搜索树中的节点(2)

题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
    首先找到需要删除的节点；
    如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:root = [5,3,6,2,4,null,7] key = 3
    5
   / \
  3   6
 / \   \
2   4   7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
    5
   / \
  4   6
 /     \
2       7
另一个正确答案是 [5,2,6,null,4,null,7]。
    5
   / \
  2   6
   \   \
    4   7

解题思路

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

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if key < root.Val {
		root.Left = deleteNode(root.Left, key)
	} else if key > root.Val {
		root.Right = deleteNode(root.Right, key)
	} else {
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		// 找到右节点的最小值，把左节点给最小值
		minNode := root.Right
		for minNode.Left != nil {
			minNode = minNode.Left
		}
		minNode.Left = root.Left
		root = root.Right
	}
	return root
}

# 2
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if key < root.Val {
		root.Left = deleteNode(root.Left, key)
	} else if key > root.Val {
		root.Right = deleteNode(root.Right, key)
	} else {
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		// 找到左节点的最大值，把右节点给最大值
		maxNode := root.Left
		for maxNode.Right != nil {
			maxNode = maxNode.Right
		}
		maxNode.Right = root.Right
		root = root.Left
	}
	return root
}

451.根据字符出现频率排序(2)

题目

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:输入:"tree"输出:"eert"
解释:'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:输入:"cccaaa"输出:"cccaaa"
解释:'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:输入:"Aabb"输出:"bbAa"
解释:此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

解题思路

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

func frequencySort(s string) string {
	m := make(map[int]int)
	for i := 0; i < len(s); i++ {
		m[int(s[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 := ""
	for i := range arr {
		for j := 0; j < arr[i][1]; j++ {
			res = res + string(arr[i][0])
		}
	}
	return res
}

# 2
func frequencySort(s string) string {
	m := make(map[byte]string)
	for i := 0; i < len(s); i++ {
		m[s[i]] = m[s[i]] + string(s[i])
	}
	var h HeapString
	heap.Init(&h)
	for _, v := range m {
		heap.Push(&h, v)
	}
	res := ""
	for h.Len() > 0 {
		str := heap.Pop(&h).(string)
		res = res + str
	}
	return res
}

type HeapString []string

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

func (h HeapString) Less(i int, j int) bool {
	return len(h[i]) >= len(h[j])
}

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

func (h *HeapString) Push(x interface{}) {
	*h = append(*h, x.(string))
}

func (h *HeapString) Pop() interface{} {
	n := len(*h)
	val := (*h)[n-1]
	*h = (*h)[:n-1]
	return val
}

452.用最少数量的箭引爆气球(1)

题目

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。
由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。
在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 
且满足 xstart≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 
弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1：输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4
示例 3：输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2
示例 4：输入：points = [[1,2]] 输出：1
示例 5：输入：points = [[2,3],[2,3]] 输出：1
提示：0 <= points.length <= 104
points[i].length == 2
-231 <= xstart <xend <= 231 - 1

解题思路

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

func findMinArrowShots(points [][]int) int {
	if len(points) == 0 {
		return 0
	}
	sort.Slice(points, func(i, j int) bool {
		return points[i][1] < points[j][1]
	})
	right := points[0][1]
	res := 1
	for i := 0; i < len(points); i++ {
		if points[i][0] > right {
			right = points[i][1]
			res++
		}
	}
	return res
}

454.四数相加II(2)

题目

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，
使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。
所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:2
解释:两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解题思路

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

func fourSumCount(A []int, B []int, C []int, D []int) int {
	res := 0
	m := make(map[int]int)
	for _, a := range A {
		for _, b := range B {
			m[a+b]++
		}
	}
	for _, c := range C {
		for _, d := range D {
			res = res + m[0-c-d]
		}
	}
	return res
}

# 2
func fourSumCount(A []int, B []int, C []int, D []int) int {
	res := 0
	mA := make(map[int]int)
	mB := make(map[int]int)
	for _, a := range A {
		for _, b := range B {
			mA[a+b]++
		}
	}
	for _, c := range C {
		for _, d := range D {
			mB[c+d]++
		}
	}
	for k, v := range mA {
		res = res + v*mB[-k]
	}
	return res
}

456.132模式(3)

题目

给定一个整数序列：a1, a2, ..., an，一个132模式的子序列ai, aj, ak被定义为：
当 i < j < k 时，ai < ak < aj。
设计一个算法，当给定有n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
示例1:输入: [1, 2, 3, 4] 输出: False
解释: 序列中不存在132模式的子序列。
示例 2:输入: [3, 1, 4, 2]输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:输入: [-1, 3, 2, 0] 输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

解题思路

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

func find132pattern(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	minArr := make([]int, len(nums)) // minArr[i]是[0,i]中的最小值
	minArr[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		minArr[i] = min(nums[i], minArr[i-1])
	}
	stack := make([]int, 0)
	for j := len(nums) - 1; j >= 0; j-- {
		// a[i]<a[k]<a[j] => min[j]<a[k]<a[j]
		if nums[j] > minArr[j] {
			for len(stack) > 0 && stack[len(stack)-1] <= minArr[j] {
				stack = stack[:len(stack)-1]
			}
			if len(stack) > 0 && stack[len(stack)-1] < nums[j] {
				return true
			}
			stack = append(stack, nums[j])
		}
	}
	return false
}

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

# 2
func find132pattern(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	minArr := make([]int, len(nums)) // minArr[i]是[0,i]中的最小值
	minArr[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		minArr[i] = min(nums[i], minArr[i-1])
	}
	for j := len(nums) - 2; j >= 0; j-- {
		if nums[j] != minArr[j] {
			for k := j + 1; k < len(nums); k++ {
				if nums[k] > minArr[j] && nums[k] < nums[j] {
					return true
				}
			}
		}
	}
	return false
}

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

# 3
func find132pattern(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	stack := make([]int, 0)
	maxValue := math.MinInt32
	for i := len(nums) - 1; i >= 0; i-- {
		// i < k
		if nums[i] < maxValue {
			return true
		}
		for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
			last := len(stack) - 1
			maxValue = max(maxValue, stack[last])
			stack = stack[:last]
		}
		stack = append(stack, nums[i])
	}
	return false
}

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

457.环形数组循环(3)

题目

给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。
相反，如果是负数 (-k)，则向后移动 k 个索引。
因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。
确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。
此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。
示例 1：输入：[2,-1,1,2,2] 输出：true
解释：存在循环，按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。
示例 2：输入：[-1,2] 输出：false
解释：按索引 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
示例 3:输入：[-2,1,-1,-2,-2] 输出：false
解释：按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为按索引 1 -> 2 的运动是向前的运动，
而按索引 2 -> 1 的运动是向后的运动。一个循环中的所有运动都必须沿着同一方向进行。
提示：-1000 ≤ nums[i] ≤ 1000
    nums[i] ≠ 0
    0 ≤ nums.length ≤ 5000
进阶：你能写出时间时间复杂度为 O(n) 和额外空间复杂度为 O(1) 的算法吗？

解题思路

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

func circularArrayLoop(nums []int) bool {
	n := len(nums)
	for i := 0; i < n; i++ {
		if nums[i] == 0 { // 原数组没有0，被标记为0，跳过
			continue
		}
		slow, fast := i, getNext(nums, n, i)
		// 保证是全正或者全负
		for nums[slow]*nums[fast] > 0 && nums[slow]*nums[getNext(nums, n, fast)] > 0 {
			if slow == fast {
				if slow == getNext(nums, n, slow) { // 等于本身，退出继续寻找
					break
				}
				return true
			}
			slow = getNext(nums, n, slow)
			fast = getNext(nums, n, getNext(nums, n, fast))
		}
		temp := i
		for nums[temp]*nums[getNext(nums, n, temp)] > 0 {
			nums[temp] = 0 // 标记为0
			temp = getNext(nums, n, temp)
		}
	}
	return false
}

func getNext(nums []int, n, cur int) int {
	return ((cur+nums[cur])%n + n) % n
}

# 2
func circularArrayLoop(nums []int) bool {
	n := len(nums)
	for i := 0; i < n; i++ {
		slow, fast := i, getNext(nums, n, i)
		// 保证是同方向
		for nums[slow]*nums[fast] > 0 && nums[slow]*nums[getNext(nums, n, fast)] > 0 {
			if slow == fast {
				if slow == getNext(nums, n, slow) { // 等于本身，退出继续寻找
					break
				}
				return true
			}
			slow = getNext(nums, n, slow)
			fast = getNext(nums, n, getNext(nums, n, fast))
		}
	}
	return false
}

func getNext(nums []int, n, cur int) int {
	return ((cur+nums[cur])%n + n) % n
}

# 3
func circularArrayLoop(nums []int) bool {
	n := len(nums)
	for i := 0; i < n; i++ {
		if judge(nums, n, i) == true {
			return true
		}
	}
	return false
}

func judge(nums []int, n, cur int) bool {
	start := cur
	dir := 1
	if nums[cur] < 0 {
		dir = -1
	}
	count := 1
	for {
		if count > n {
			return false
		}
		next := ((cur+nums[cur])%n + n) % n
		if (dir > 0 && nums[next] < 0) || (dir < 0 && nums[next] > 0) {
			return false
		}
		if next == start { // 走到起点
			return count > 1
		}
		count++
		cur = next
	}
}

462.最少移动次数使数组元素相等II(2)

题目

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。
您可以假设数组的长度最多为10000。
例如:输入: [1,2,3]输出: 2
说明：只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： 
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

解题思路

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

func minMoves2(nums []int) int {
	sort.Ints(nums)
	target := nums[len(nums)/2]
	res := 0
	for i := 0; i < len(nums); i++ {
		res = res + abs(target-nums[i])
	}
	return res
}

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

# 2
func minMoves2(nums []int) int {
	sort.Ints(nums)
	res := 0
	left, right := 0, len(nums)-1
	for left < right {
		// 无论选哪个数作为最终值，前后第n个值需要移动之和不变
		// nums[right]-target+target-nums[left] = nums[right] - nums[left]
		res = res + nums[right] - nums[left]
		left++
		right--
	}
	return res
}

464.我能赢吗(3)

题目

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，
先使得累计整数和达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定一个整数maxChoosableInteger（整数池中可选择的最大数）和另一个整数desiredTotal（累计和），
判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
你可以假设maxChoosableInteger不会大于 20，desiredTotal不会大于 300。
示例：输入：maxChoosableInteger = 10 desiredTotal = 11输出： false
解释：无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

解题思路

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

var m []bool

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	a := maxChoosableInteger
	if a*(a+1)/2 < desiredTotal {
		return false
	}
	m = make([]bool, 1<<a)
	return dfs(a, desiredTotal, 0)
}

func dfs(a, b int, status int) bool {
	if m[status] == true {
		return true
	}
	for i := 1; i <= a; i++ {
		cur := 1 << (i - 1)
		if cur&status > 0 { // 当前位(i-1)为1
			continue
		}
		if b <= i { // 当前选的数可以赢
			m[status] = true
			return true
		}
		next := status | cur            // 按位或运算：status第(i-1)变为1
		if dfs(a, b-i, next) == false { // 如果下个人要输的话，当前人要赢
			m[status] = true
			return true
		}
	}
	m[status] = false
	return false
}

# 2
var m map[int]bool

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	a := maxChoosableInteger
	if a*(a+1)/2 < desiredTotal {
		return false
	}
	m = make(map[int]bool)
	return dfs(a, desiredTotal, 0)
}

func dfs(a, b int, status int) bool {
	if v, ok := m[status]; ok {
		return v
	}
	for i := 1; i <= a; i++ {
		cur := 1 << (i - 1)
		next := status | cur                                           // 按位或运算：status第(i-1)变为1
		if cur&status == 0 && (b <= i || dfs(a, b-i, next) == false) { // 当前位(i-1)为1
			m[status] = true
			return true
		}
	}
	m[status] = false
	return false
}

# 3
func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	a, b := maxChoosableInteger, desiredTotal
	if a*(a+1)/2 < b {
		return false
	}
	total := 1 << a
	dp := make([]bool, total)
	for i := total - 1; i >= 0; i-- { // 枚举状态
		sum := 0
		for k := 0; k < a; k++ { // 状态和
			if i&(1<<k) > 0 { // i：对应状态为1位置上和
				sum = sum + (k + 1)
			}
		}
		for k := 0; k < a; k++ {
			if i&(1<<k) > 0 {
				continue
			}
			prev := i | (1 << k)
			// >=剩下值，或者之前为false
			if k+1 >= desiredTotal-sum || dp[prev] == false {
				dp[i] = true
			}
		}
	}
	return dp[0]
}

467.环绕字符串中唯一的子字符串(1)

题目

把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，
所以s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
现在我们有了另一个字符串 p 。
你需要的是找出 s 中有多少个唯一的 p 的非空子串，
尤其是当你的输入是字符串 p ，你需要输出字符串s 中 p 的不同的非空子串的数目。
注意: p仅由小写的英文字母组成，p 的大小可能超过 10000。
示例1:输入: "a" 输出: 1
解释: 字符串 S 中只有一个"a"子字符。
示例 2:输入: "cac" 输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
示例 3:输入: "zab" 输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.

解题思路

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

func findSubstringInWraproundString(p string) int {
	dp := [26]int{}
	count := 0
	for i := 0; i < len(p); i++ {
		value := int(p[i] - 'a')
		if i > 0 && (value-int(p[i-1]-'a')-1)%26 == 0 {
			count++
		} else {
			count = 1
		}
		dp[value] = max(dp[value], count)
	}
	res := 0
	for i := 0; i < len(dp); i++ {
		res = res + dp[i]
	}
	return res
}

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

468.验证IP地址(1)

题目

编写一个函数来验证输入的字符串是否是有效的 IPv4 或IPv6 地址。
如果是有效的 IPv4 地址，返回 "IPv4" ；
如果是有效的 IPv6 地址，返回 "IPv6" ；
如果不是上述类型的 IP 地址，返回 "Neither" 。
IPv4地址由十进制数和点来表示，每个地址包含 4 个十进制数，其范围为0 -255，用(".")分割。
比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址172.16.254.01 是不合法的。
IPv6地址由 8 组 16 进制的数字来表示，每组表示16 比特。这些组数字通过 (":")分割。
比如,2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。
而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。
所以，2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 
(即，忽略 0 开头，忽略大小写)。
然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。
比如，2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的 0 也是不被允许的。
比如，02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。
示例 1：输入：IP = "172.16.254.1" 输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"
示例 2：输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334" 输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"
示例 3：输入：IP = "256.256.256.256" 输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址
示例 4：输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334:" 输出："Neither"
示例 5：输入：IP = "1e1.4.5.6"输出："Neither"
提示：IP 仅由英文字母，数字，字符 '.' 和 ':' 组成。

解题思路

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

var defaultRes string = "Neither"

func validIPAddress(IP string) string {
	if strings.Contains(IP, ":") {
		return checkIPv6(IP)
	}
	return checkIPv4(IP)
}

func checkIPv4(ip string) string {
	arr := strings.Split(ip, ".")
	if len(arr) != 4 {
		return defaultRes
	}
	for i := 0; i < len(arr); i++ {
		num, err := strconv.Atoi(arr[i])
		if err != nil || num > 255 || num < 0 {
			return defaultRes
		}
		if len(arr[i]) > 1 && arr[i][0] == '0' || (i == 0 && num == 0) {
			return defaultRes
		}
	}
	return "IPv4"
}

func checkIPv6(ip string) string {
	arr := strings.Split(ip, ":")
	if len(arr) != 8 {
		return defaultRes
	}
	for i := 0; i < len(arr); i++ {
		if arr[i] == "" || len(arr[i]) > 4 {
			return defaultRes
		}
		for j := 0; j < len(arr[i]); j++ {
			if (arr[i][j] > 'F' && arr[i][j] < 'a') ||
				(arr[i][j] > 'f' && arr[i][j] <= 'z') {
				return defaultRes
			}
		}
	}
	return "IPv6"
}

470.用Rand7()实现 Rand10()(2)

题目

已有方法rand7可生成 1 到 7 范围内的均匀随机整数，
试写一个方法rand10生成 1 到 10 范围内的均匀随机整数。
不要使用系统的Math.random()方法。
示例 1:输入: 1 输出: [7]
示例 2:输入: 2 输出: [8,4]
示例 3:输入: 3 输出: [8,1,10]
提示:rand7已定义。
传入参数:n表示rand10的调用次数。
进阶:rand7()调用次数的期望值是多少?
你能否尽量少调用 rand7() ?

解题思路

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

func rand10() int {
	for {
		a := rand7()
		b := rand7()
		target := a + (b-1)*7
		if target <= 40 {
			return target%10 + 1
		}
	}
}

# 2
func rand10() int {
	for {
		a := rand7()
		b := rand7()
		target := a + (b-1)*7
		if target <= 40 { // 1-49
			return target%10 + 1
		}
		a = rand7()
		b = target - 40
		target = a + (b-1)*7 // 1-63
		if target <= 60 {
			return target%10 + 1
		}
		a = rand7()
		b = target - 60
		target = a + (b-1)*7 // 1-21
		if target <= 20 {
			return target%10 + 1
		}
	}
}

473.火柴拼正方形(2)

题目

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，
请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例1:输入: [1,1,2,2,2] 输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例2:输入: [3,3,3,3,4] 输出: false
解释: 不能用所有火柴拼成一个正方形。
注意:给定的火柴长度和在0到10^9之间。
火柴数组的长度不超过15。

解题思路

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

func makesquare(nums []int) bool {
	n := len(nums)
	if nums == nil || n < 4 {
		return false
	}
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	if sum%4 != 0 {
		return false
	}
	// 从大到小排序；从小到大可能会超时
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})
	res := make([]int, 4)
	return dfs(nums, res, sum/4, 0)
}

func dfs(nums []int, res []int, target int, level int) bool {
	if len(nums) == level {
		for i := 0; i < len(res); i++ {
			if res[i] != target {
				return false
			}
		}
		return true
	}
	for i := 0; i < len(res); i++ {
		if nums[level]+res[i] > target {
			continue
		}
		res[i] = res[i] + nums[level]
		if dfs(nums, res, target, level+1) == true {
			return true
		}
		res[i] = res[i] - nums[level]
	}
	return false
}

# 2
func makesquare(nums []int) bool {
	n := len(nums)
	if nums == nil || n < 4 {
		return false
	}
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	if sum%4 != 0 {
		return false
	}
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})
	visited := make([]bool, len(nums))
	for i := 0; i < 4; i++ {
		if dfs(nums, sum/4, 0, 0, visited) == false {
			return false
		}
	}
	return true
}

func dfs(nums []int, target int, sum int, level int, visited []bool) bool {
	if sum == target {
		return true
	}
	if len(nums) == level {

	}
	for i := level; i < len(nums); i++ {
		if visited[i] == false && sum <= target {
			visited[i] = true
			if dfs(nums, target, sum+nums[i], level+1, visited) {
				return true
			}
			visited[i] = false
		}
	}
	return false
}

474.一和零(2)

题目

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。
{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i]仅由'0' 和'1' 组成
1 <= m, n <= 100

解题思路

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

func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i < len(strs); i++ {
		a, b := getCount(strs[i])
		for j := m; j >= a; j-- {
			for k := n; k >= b; k-- {
				dp[j][k] = max(dp[j][k], dp[j-a][k-b]+1)
			}
		}
	}
	return dp[m][n]
}

func getCount(str string) (a, b int) {
	a, b = 0, 0
	for i := 0; i < len(str); i++ {
		if str[i] == '0' {
			a++
		} else {
			b++
		}
	}
	return a, b
}

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

# 2
func findMaxForm(strs []string, m int, n int) int {
	dp := make([][][]int, len(strs)+1)
	for i := 0; i <= len(strs); i++ {
		dp[i] = make([][]int, m+1)
		for j := 0; j <= m; j++ {
			dp[i][j] = make([]int, n+1)
		}
	}
	for i := 1; i <= len(strs); i++ {
		a, b := getCount(strs[i-1])
		for j := 0; j <= m; j++ {
			for k := 0; k <= n; k++ {
				dp[i][j][k] = dp[i-1][j][k]
				if a <= j && b <= k {
					dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-a][k-b]+1)
				}
			}
		}
	}
	return dp[len(strs)][m][n]
}

func getCount(str string) (a, b int) {
	a, b = 0, 0
	for i := 0; i < len(str); i++ {
		if str[i] == '0' {
			a++
		} else {
			b++
		}
	}
	return a, b
}

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

477.汉明距离总和(1)

题目

两个整数的汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
示例:输入: 4, 14, 2 输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。
（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:数组中元素的范围为从0到10^9。
数组的长度不超过10^4。

解题思路

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

func totalHammingDistance(nums []int) int {
	res := 0
	for i := 0; i < 32; i++ {
		total := 0
		for j := 0; j < len(nums); j++ {
			total = total + (nums[j]>>i)&1
		}
		// 汉明距离：两个数字的二进制数对应位不同的数量
		// 该位1的数量*该位0的数量
		res = res + total*(len(nums)-total)
	}
	return res
}

478.在圆内随机生成点(1)

题目

给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数randPoint。
说明:输入值和输出值都将是浮点数。
圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
圆周上的点也认为是在圆中。
randPoint返回一个包含随机点的x坐标和y坐标的大小为2的数组。
示例 1：输入: ["Solution","randPoint","randPoint","randPoint"] [[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
示例 2：输入: ["Solution","randPoint","randPoint","randPoint"] [[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
输入语法说明：输入是两个列表：调用成员函数名和调用的参数。Solution的构造函数有三个参数，
圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint没有参数。
输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

解题思路

No.	思路	时间复杂度	空间复杂度
01	循环	O(1)	O(1)

type Solution struct {
	x      float64
	y      float64
	radius float64
}

func Constructor(radius float64, x_center float64, y_center float64) Solution {
	return Solution{
		x:      x_center,
		y:      y_center,
		radius: radius,
	}
}

func (this *Solution) RandPoint() []float64 {
	for {
		a := this.x - this.radius + 2*this.radius*rand.Float64()
		b := this.y - this.radius + 2*this.radius*rand.Float64()
		if (a-this.x)*(a-this.x)+(b-this.y)*(b-this.y) < this.radius*this.radius {
			return []float64{a, b}
		}
	}
}

481.神奇字符串(2)

题目

神奇的字符串S只包含 '1' 和 '2'，并遵守以下规则：
字符串 S 是神奇的，因为串联字符 '1' 和 '2' 的连续出现次数会生成字符串 S 本身。
字符串S的前几个元素如下：S = “1221121221221121122 ......”
如果我们将S 中连续的 1 和 2 进行分组，它将变成：
1 22 11 2 1 22 1 22 11 2 11 22 ......
并且每个组中 '1' 或 '2' 的出现次数分别是：
1 2 2 1 1 2 1 2 2 1 2 2 ......
你可以看到上面的出现次数就是 S 本身。
给定一个整数 N 作为输入，返回神奇字符串 S中前 N 个数字中的 '1' 的数目。
注意：N 不会超过 100,000。
示例：输入：6 输出：3
解释：神奇字符串 S 的前 6 个元素是 “12211”，它包含三个 1，因此返回 3。

解题思路

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

func magicalString(n int) int {
	if n == 0 {
		return 0
	}
	if n <= 3 {
		return 1
	}
	str := []byte("122")
	res := 1
	index := 2
	for i := 2; i < n; i++ {
		if str[i] == '2' {
			if str[index] == '2' {
				str = append(str, []byte{'1', '1'}...)
			} else {
				str = append(str, []byte{'2', '2'}...)
			}
			index = index + 2
		} else {
			res++
			if str[index] == '2' {
				str = append(str, '1')
			} else {
				str = append(str, '2')
			}
			index = index + 1
		}
	}
	return res
}

# 2
func magicalString(n int) int {
	if n == 0 {
		return 0
	}
	if n <= 3 {
		return 1
	}
	str := []byte("122")
	flag := true
	for i := 2; i < n; i++ {
		count := str[i] - '0'
		if flag == true {
			for count > 0 {
				str = append(str, '1')
				count--
			}
			flag = false
		} else {
			for count > 0 {
				str = append(str, '2')
				count--
			}
			flag = true
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		if str[i] == '1' {
			res++
		}
	}
	return res
}

486.预测赢家(3)

题目

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，
随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。
每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。
最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：输入：[1, 5, 2] 输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。
如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。
示例 2：输入：[1, 5, 233, 7] 输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。
无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
     最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
提示：1 <= 给定的数组长度 <= 20.
    数组里所有分数都为非负数且不会大于 10000000 。
    如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

解题思路

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

func PredictTheWinner(nums []int) bool {
	return dfs(nums, 0, len(nums)-1) >= 0
}

func dfs(nums []int, start, end int) int {
	if start > end {
		return 0
	}
	// 玩家得分：自己得分-对手得分
	left := nums[start] - dfs(nums, start+1, end)
	right := nums[end] - dfs(nums, start, end-1)
	return max(left, right)

}

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

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

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

# 3
func PredictTheWinner(nums []int) bool {
	n := len(nums)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = nums[i]
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			// 玩家得分：自己得分-对手得分
			dp[i][j] = max(nums[i]-dp[i+1][j], nums[j]-dp[i][j-1])
		}
	}
	return dp[0][n-1] >= 0
}

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

491.递增子序列(2)

题目

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:给定数组的长度不会超过15。
    数组中的整数范围是 [-100,100]。
    给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

解题思路

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

var res [][]int

func findSubsequences(nums []int) [][]int {
	res = make([][]int, 0)
	dfs(nums, 0, math.MinInt32, make([]int, 0))
	return res
}

func dfs(nums []int, index int, prev int, arr []int) {
	if index == len(nums) {
		if len(arr) >= 2 {
			temp := make([]int, len(arr))
			copy(temp, arr)
			res = append(res, temp)
		}
		return
	}
	if prev <= nums[index] {
		arr = append(arr, nums[index])
		dfs(nums, index+1, nums[index], arr)
		arr = arr[:len(arr)-1]
	}
	if prev != nums[index] {
		dfs(nums, index+1, prev, arr)
	}
}

# 2
var res [][]int

func findSubsequences(nums []int) [][]int {
	res = make([][]int, 0)
	dfs(nums, 0, make([]int, 0))
	return res
}

func dfs(nums []int, index int, arr []int) {
	if len(arr) >= 2 {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
	}
	m := make(map[int]bool)
	for i := index; i < len(nums); i++ {
		if m[nums[i]] == true || (len(arr) > 0 && nums[i] < arr[len(arr)-1]) {
			continue
		}
		m[nums[i]] = true
		dfs(nums, i+1, append(arr, nums[i]))
	}
}

494.目标和(5)

题目

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。
对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示：数组非空，且长度不会超过 20 。
    初始的数组的和不会超过 1000 。
    保证返回的最终结果能被 32 位整数存下。

解题思路

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

func findTargetSumWays(nums []int, S int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		if nums[0] == 0 && S == 0 {
			return 2
		}
		if nums[0] == S || nums[0] == -S {
			return 1
		}
	}
	value := nums[0]
	nums = nums[1:]
	return findTargetSumWays(nums, S-value) + findTargetSumWays(nums, S+value)
}

# 2
func findTargetSumWays(nums []int, S int) int {
	dp := make(map[int]int)
	dp[nums[0]]++
	dp[-nums[0]]++
	for i := 1; i < len(nums); i++ {
		temp := make(map[int]int)
		for k, v := range dp {
			temp[k-nums[i]] = temp[k-nums[i]] + v
			temp[k+nums[i]] = temp[k+nums[i]] + v
		}
		dp = temp
	}
	return dp[S]
}

# 3
var res int

func findTargetSumWays(nums []int, S int) int {
	res = 0
	dfs(nums, 0, S)
	return res
}

func dfs(nums []int, index int, target int) {
	if index == len(nums) {
		if target == 0 {
			res++
		}
		return
	}
	dfs(nums, index+1, target+nums[index])
	dfs(nums, index+1, target-nums[index])
}


# 4
func findTargetSumWays(nums []int, S int) int {
	sum := 0
	// 非负整数数组
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	if sum < int(math.Abs(float64(S))) || (sum+S)%2 == 1 {
		return 0
	}
	// 一个正数x,一个负数背包y => x+y=sum, x-y=S => (sum+S)/2=x
	target := (sum + S) / 2
	dp := make([]int, target+1)
	dp[0] = 1
	for i := 1; i <= len(nums); i++ {
        // 从后往前，避免覆盖
		for j := target; j >= 0; j-- {
			if j >= nums[i-1] {
				// 背包足够大，都选
				dp[j] = dp[j] + dp[j-nums[i-1]]
			} else {
				// 容量不够，不选
				dp[j] = dp[j]
			}
		}
	}
	return dp[target]
}

# 5
func findTargetSumWays(nums []int, S int) int {
	sum := 0
	// 非负整数数组
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
	}
	if sum < int(math.Abs(float64(S))) || (sum+S)%2 == 1 {
		return 0
	}
	// 一个正数x,一个负数背包y => x+y=sum, x-y=S => (sum+S)/2=x
	target := (sum + S) / 2
	// 在前i个物品中选择，若当前背包的容量为j，则最多有x种方法可以恰好装满背包。
	dp := make([][]int, len(nums)+1)
	for i := 0; i <= len(nums); i++ {
		dp[i] = make([]int, target+1)
		dp[i][0] = 1 // 容量为0， 只有都不选
	}
	for i := 1; i <= len(nums); i++ {
		for j := 0; j <= target; j++ {
			if j >= nums[i-1] {
				// 背包足够大，都选
				dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
			} else {
				// 容量不够，不选
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[len(nums)][target]
}

495.提莫攻击(1)

题目

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，
他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
示例1:输入: [1,4], 2 输出: 4
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
第 4 秒初，提莫再次攻击艾希，使得艾希获得另外 2 秒中毒时间。 所以最终输出 4 秒。
示例2:输入: [1,2], 2 输出: 3
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
但是第 2 秒初，提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加，提莫在第 2 秒初的这次攻击会在第 3 秒末结束。 所以最终输出 3 。
提示：你可以假定时间序列数组的总长度不超过 10000。
    你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数，并且不超过 10,000,000。

解题思路

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

func findPoisonedDuration(timeSeries []int, duration int) int {
	res := 0
	if len(timeSeries) == 0 {
		return 0
	}
	for i := 0; i < len(timeSeries)-1; i++ {
		res = res + min(timeSeries[i+1]-timeSeries[i], duration)
	}
	return res + duration
}

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

497.非重叠矩形中的随机点(1)

题目

给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示：整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中[x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
每个矩形的长度和宽度不超过 2000。
1 <= rects.length<= 100
pick 以整数坐标数组[p_x, p_y]的形式返回一个点。
pick 最多被调用10000次。
示例 1：输入:  ["Solution","pick","pick","pick"] [[[[1,1,5,5]]],[],[],[]] 输出: [null,[4,1],[4,1],[3,3]]
示例 2：输入:  ["Solution","pick","pick","pick","pick","pick"] [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出: [null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
输入语法的说明：
输入是两个列表：调用的子例程及其参数。
Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。

解题思路

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

type Solution struct {
	nums  []int   // 前缀和
	total int     // 总和
	rects [][]int // 原数组
}

func Constructor(rects [][]int) Solution {
	arr := make([]int, 0)
	total := 0
	for i := 0; i < len(rects); i++ {
		x1, y1, x2, y2 := rects[i][0], rects[i][1], rects[i][2], rects[i][3]
		total = total + (x2-x1+1)*(y2-y1+1) // x点的个数 * y点的个数：注意包含边+1
		arr = append(arr, total)
	}
	return Solution{nums: arr, total: total, rects: rects}
}

// leetcode528.按权重随机选择
func (this *Solution) Pick() []int {
	target := rand.Intn(this.total) // 目标值
	left, right := 0, len(this.nums)
	for left < right {
		mid := left + (right-left)/2
		if this.nums[mid] <= target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	temp := this.rects[left]
	x1, y1, x2, y2 := temp[0], temp[1], temp[2], temp[3]
	width := x2 - x1 + 1
	height := y2 - y1 + 1
	start := this.nums[left] - width*height // 前缀和-目标值
	return []int{x1 + (target-start)%width, y1 + (target-start)/width}
}

498.对角线遍历(2)

题目

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，
对角线遍历如下图所示。
示例:
输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出:  [1,2,4,7,5,3,6,8,9]
说明:给定矩阵中的元素总数不会超过 100000 。

解题思路

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

func findDiagonalOrder(matrix [][]int) []int {
	res := make([]int, 0)
	if len(matrix) == 0 {
		return res
	}
	n, m := len(matrix), len(matrix[0])
	if n == 1 {
		return matrix[0]
	}
	i, j := 0, 0
	flag := false
	for j < m {
		a, b := i, j
		temp := make([]int, 0)
		temp = append(temp, matrix[a][b])
		// 从左下往右上
		for a != 0 && b != m-1 {
			a--
			b++
			temp = append(temp, matrix[a][b])
		}
		if flag == true {
			reverse(temp)
			flag = false
		} else {
			flag = true
		}
		res = append(res, temp...)
		if i != n-1 {
			i++
		} else {
			j++
		}
	}
	return res
}

func reverse(arr []int) {
	for i := 0; i < len(arr)/2; i++ {
		arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
	}
}

# 2
func findDiagonalOrder(matrix [][]int) []int {
	res := make([]int, 0)
	if len(matrix) == 0 {
		return res
	}
	n, m := len(matrix), len(matrix[0])
	if n == 1 {
		return matrix[0]
	}
	// 右边拼接一个相同的，依次遍历
	for i := 0; i < n+m-1; i++ {
		temp := make([]int, 0)
		var a, b int
		if i < m {
			a = 0
			b = i
		} else {
			a = i - m + 1
			b = m - 1
		}
		for a < n && b >= 0 {
			temp = append(temp, matrix[a][b])
			a, b = a+1, b-1
		}
		if i%2 == 0 {
			reverse(temp)
		}
		res = append(res, temp...)
	}
	return res
}

func reverse(arr []int) {
	for i := 0; i < len(arr)/2; i++ {
		arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
	}
}

0401-0500-Hard

403.青蛙过河(4)

题目

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 
青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示），
请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
开始时，青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位
（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了k个单位，那么它接下来的跳跃距离只能选择为k - 1、k或k + 1 个单位。
另请注意，青蛙只能向前方（终点的方向）跳跃。
示例 1：输入：stones = [0,1,3,5,6,8,12,17] 输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 
然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 
然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 
最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
示例 2：输入：stones = [0,1,2,3,4,8,9,11] 输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
提示：2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0

解题思路

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

var m [][]int

func canCross(stones []int) bool {
	n := len(stones)
	m = make([][]int, n)
	for i := 0; i < n; i++ {
		m[i] = make([]int, n)
		for j := 0; j < n; j++ {
			m[i][j] = -1
		}
	}
	return dfs(stones, 0, 0) == 1
}

func dfs(stones []int, index int, k int) int {
	if m[index][k] >= 0 {
		return m[index][k]
	}
	for i := index + 1; i < len(stones); i++ {
		next := stones[i] - stones[index]
		if k-1 <= next && next <= k+1 { // k-1、k或 k+1
			if dfs(stones, i, next) == 1 {
				m[index][k] = 1
				return 1
			}
		}
	}
	if index == len(stones)-1 {
		m[index][k] = 1
	} else {
		m[index][k] = 0
	}
	return m[index][k]
}

# 2
func canCross(stones []int) bool {
	n := len(stones)
	m := make(map[int]map[int]int)
	for i := 0; i < n; i++ {
		m[stones[i]] = make(map[int]int)
	}
	m[0][0] = 1
	for i := 0; i < n; i++ {
		for k := range m[stones[i]] {
			for next := k - 1; next <= k+1; next++ {
				if next > 0 {
					if _, ok := m[stones[i]+next]; ok {
						m[stones[i]+next][next] = 1
					}
				}
			}
		}
	}
	return len(m[stones[n-1]]) > 0
}

# 3
func canCross(stones []int) bool {
	n := len(stones)
	dp := make([][]bool, n+1)
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			k := stones[i] - stones[j]
			if k <= i { 
				dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1] // 满足其一
				if i == n-1 && dp[i][k] == true {
					return true
				}
			}
		}
	}
	return false
}

# 4
type Node struct {
	index int
	size  int
}

func canCross(stones []int) bool {
	n := len(stones)
	m := make(map[int]bool)
	for i := 0; i < n; i++ {
		m[stones[i]] = true
	}
	isVisited := make(map[Node]bool)

	stack := make([]Node, 0)
	node := Node{
		index: 0,
		size:  0,
	}
	stack = append(stack, node)
	isVisited[node] = true
	for len(stack) > 0 {
		node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if node.index == stones[n-1] {
			return true
		}
		for k := node.size - 1; k <= node.size+1; k++ {
			next := node.index + k
			if k > stones[n-1] {
				continue
			}
			temp := Node{
				index: next,
				size:  k,
			}
			if k > 0 && m[next] == true && isVisited[temp] == false {
				isVisited[temp] = true
				stack = append(stack, temp)
			}
		}
	}
	return false
}

410.分割数组的最大值(3)

题目

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:数组长度 n 满足以下条件:
    1 ≤ n ≤ 1000
    1 ≤ m ≤ min(50, n)
示例:输入: nums = [7,2,5,10,8] m = 2输出:18
解释:一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

解题思路

No.	思路	时间复杂度	空间复杂度
01	二分查找	O(nlog(n))	O(1)
02	动态规划+前缀和	O(n^3)	O(n^2)
03	二分查找	O(nlog(n))	O(1)

func splitArray(nums []int, m int) int {
	left, right := 0, 0 // 最小值，最大值
	for i := 0; i < len(nums); i++ {
		right = right + nums[i]
		if left < nums[i] {
			left = nums[i]
		}
	}
	for left < right {
		mid := left + (right-left)/2
		// 继续尝试
		if check(nums, mid, m) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

// 区间和的最大值为target时，所得出的区间数
func check(arr []int, target int, m int) bool {
	sum := 0
	count := 1
	for i := 0; i < len(arr); i++ {
		// 当sum加上当前值超过了target
		// 我们就把当前取的值作为新的一段分割子数组的开头，并将count加1
		if sum+arr[i] > target {
			count++
			sum = arr[i]
		} else {
			sum = sum + arr[i]
		}
	}
	return count <= m
}

# 2
func splitArray(nums []int, m int) int {
	n := len(nums)
	dp := make([][]int, n+1)
	sub := make([]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, m+1)
		for j := 0; j < m+1; j++ {
			dp[i][j] = math.MaxInt32
		}
	}
	for i := 0; i < n; i++ {
		sub[i+1] = sub[i] + nums[i]
	}
	// dp[i][j]表示前i个数字被分割成j段的结果
	// 0<=k<i枚举所有可以被分成j-1段的情况
	// 前 k个数被分割为j−1段，而第 k+1到第i个数为第j段
	// dp[i][j] = min{max(dp[k][j-1], sum(k+1, i))}
	dp[0][0] = 0
	for i := 1; i <= n; i++ {
		// 分成m段，可能不够分，最多分min(i,m)
		for j := 1; j <= min(i, m); j++ {
			for k := 0; k < i; k++ {
				dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i]-sub[k]))
			}
		}
	}
	return dp[n][m]
}

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 splitArray(nums []int, m int) int {
	left, right := 0, 0 // 最小值，最大值
	for i := 0; i < len(nums); i++ {
		right = right + nums[i]
		if left < nums[i] {
			left = nums[i]
		}
	}
	for left < right {
		mid := left + (right-left)/2
		// 分割数太多，继续尝试
		if check(nums, mid, m) > m {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

// 区间和的最大值为target时，所得出的区间数
func check(arr []int, target int, m int) int {
	sum := 0
	count := 1
	for i := 0; i < len(arr); i++ {
		// 当sum加上当前值超过了target
		// 我们就把当前取的值作为新的一段分割子数组的开头，并将count加1
		if sum+arr[i] > target {
			count++
			sum = 0
		}
		sum = sum + arr[i]
	}
	return count
}

440.字典序的第K小数字(1)

题目

给定整数n和k，找到1到n中字典序第k小的数字。
注意：1 ≤ k ≤ n ≤ 109。
示例 :输入: n: 13   k: 2 输出: 10
解释:字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

解题思路

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

func findKthNumber(n int, k int) int {
	pre := 1
	count := 1
	for count < k {
		total := getCount(pre, n)
		if count+total > k { // 超过了，*10继续尝试，缩小范围
			pre = pre * 10
			count++
		} else if count+total <= k { // 小了，尝试下一个数字开头，扩大范围
			pre++
			count = count + total
		}
	}
	return pre
}

// 以数字i开头且不超过最大数字n的数字个数
func getCount(pre, n int) int {
	count := 0
	a := pre
	b := pre + 1
	for a <= n {
		if b < n+1 {
			count = count + b - a
		} else {
			count = count + n + 1 - a
		}
		a = a * 10
		b = b * 10
	}
	return count
}

446.等差数列划分II-子序列(1)

题目

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从 0 开始。
该数组子序列将划分为整数序列(P0, P1, ..., Pk)，满足 0 ≤ P0 < P1 < ... < Pk < N。
如果序列 A[P0]，A[P1]，...，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。
值得注意的是，这意味着 k ≥ 2。
函数要返回数组 A 中所有等差子序列的个数。
输入包含 N 个整数。每个整数都在 -231 和 231-1 之间，另外 0 ≤ N ≤ 1000。保证输出小于 231-1。
示例：输入：[2, 4, 6, 8, 10] 输出：7
解释： 所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

解题思路

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

func numberOfArithmeticSlices(nums []int) int {
	n := len(nums)
	dp := make([]map[int]int, n) // dp[i][d]代表以A[i]结束且公差为d的等差数列个数
	for i := 0; i < n; i++ {
		dp[i] = make(map[int]int)
	}
	res := 0
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			diff := nums[i] - nums[j]
			dp[i][diff] = dp[i][diff] + dp[j][diff] + 1
			res = res + dp[j][diff]
		}
	}
	return res
}

458.可怜的小猪(2)

题目

有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。
它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。
不幸的是，你只有minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下：
选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。
示例 1：输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60 输出：5
示例 2：输入：buckets = 4, minutesToDie = 15, minutesToTest = 15 输出：2
示例 3：输入：buckets = 4, minutesToDie = 15, minutesToTest = 30 输出：2
提示：1 <= buckets <= 1000
1 <=minutesToDie <=minutesToTest <= 100

解题思路

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

func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
	count := minutesToTest/minutesToDie + 1 // 最多喝几次水
	res := 0
	target := 1
	// n^res<buckets
	for target < buckets {
		target = target * count
		res++
	}
	return res
}

# 2
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
	count := minutesToTest/minutesToDie + 1 // 最多喝几次水
	res := math.Log(float64(buckets)) / math.Log(float64(count))
	return int(math.Ceil(res))
}

460.LFU缓存(2)

题目

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
    get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
    put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。
    当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。
    在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
进阶：你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希+双向链表	O(1)	O(n)
02	内置list	O(1)	O(n)

type Node struct {
	key   int
	value int
	count int
	next  *Node
	prev  *Node
}

type LFUCache struct {
	cap     int
	minFreq int
	kv      map[int]*Node
	fk      map[int]*DoubleList
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		cap:     capacity,
		kv:      make(map[int]*Node),
		fk:      make(map[int]*DoubleList),
		minFreq: 0,
	}
}

func (this *LFUCache) Get(key int) int {
	node, ok := this.kv[key]
	if ok == false {
		return -1
	}
	this.increaseFreq(node)
	return node.value
}

func (this *LFUCache) Put(key int, value int) {
	if this.cap <= 0 {
		return
	}
	// 已经存在的key，修改并增加次数
	node, ok := this.kv[key]
	if ok {
		node.value = value
		this.increaseFreq(node)
		return
	}
	if this.cap <= len(this.kv) {
		last := this.remove()
		delete(this.kv, last.key)
	}
	temp := &Node{
		key:   key,
		value: value,
		count: 1,
	}
	this.kv[key] = temp
	if this.fk[1] == nil {
		this.fk[1] = NewDoubleList()
	}
	this.fk[1].Push(temp)
	this.minFreq = 1 // 新插入的频率为1
}

func (this *LFUCache) increaseFreq(node *Node) {
	freq := node.count
	this.fk[freq].Remove(node)
	if this.fk[freq+1] == nil {
		this.fk[freq+1] = NewDoubleList()
	}
	node.count++
	this.fk[freq+1].Push(node)
	if this.fk[freq].head.next == this.fk[freq].tail {
		if freq == this.minFreq {
			this.minFreq++
		}
	}
	return
}

func (this *LFUCache) remove() *Node {
	temp := this.fk[this.minFreq]
	last := temp.tail.prev
	temp.Remove(temp.tail.prev) // 删除尾部节点
	return last
}

type DoubleList struct {
	head *Node
	tail *Node
}

func NewDoubleList() *DoubleList {
	node := &DoubleList{
		head: &Node{},
		tail: &Node{},
	}
	node.head.next = node.tail
	node.tail.prev = node.head
	return node
}

// 插入头部
func (this *DoubleList) Push(node *Node) {
	next := this.head.next
	node.next = next
	node.prev = this.head
	next.prev = node
	this.head.next = node
}

// 删除指定节点
func (this *DoubleList) Remove(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
	node.next = nil
	node.prev = nil
}

# 2
type Node struct {
	key   int
	value int
	count int
}

type LFUCache struct {
	cap     int
	minFreq int
	kv      map[int]*list.Element
	fk      map[int]*list.List
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		cap:     capacity,
		minFreq: 0,
		kv:      make(map[int]*list.Element),
		fk:      make(map[int]*list.List),
	}
}

func (this *LFUCache) Get(key int) int {
	node, ok := this.kv[key]
	if ok == false {
		return -1
	}
	return this.increaseFreq(node)
}

func (this *LFUCache) Put(key int, value int) {
	data, ok := this.kv[key]
	if ok {
		node := data.Value.(*Node)
		node.value = value
		this.increaseFreq(data)
		return
	}
	if this.cap == len(this.kv) {
		cur, ok := this.fk[this.minFreq]
		if ok == false {
			return
		}
		deleteKey := cur.Front()
		cur.Remove(deleteKey)
		delete(this.kv, deleteKey.Value.(*Node).key)
	}
	temp := &Node{
		key:   key,
		value: value,
		count: 1,
	}
	if _, ok := this.fk[1]; ok == false {
		this.fk[1] = list.New()
	}
	res := this.fk[1].PushBack(temp)
	this.kv[key] = res
	this.minFreq = 1
}

func (this *LFUCache) increaseFreq(data *list.Element) int {
	node := data.Value.(*Node)
	cur, ok := this.fk[node.count]
	if ok == false {
		return -1
	}
	cur.Remove(data)
	if cur.Len() == 0 && this.minFreq == node.count {
		this.minFreq++
	}
	node.count++
	if this.fk[node.count] == nil {
		this.fk[node.count] = list.New()
	}
	res := this.fk[node.count].PushBack(node)
	this.kv[node.key] = res
	return node.value
}

466.统计重复个数(1)

题目

由 n 个连接的字符串 s 组成字符串 S，记作S = [s,n]。例如，["abc",3]=“abcabcabc”。
如果我们可以从 s2中删除某些字符使其变为 s1，则称字符串 s1可以从字符串 s2 获得。
例如，根据定义，"abc" 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。
现在给你两个非空字符串 s1和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106和 1 ≤ n2 ≤ 106。
现在考虑字符串 S1 和 S2，其中 S1=[s1,n1]、S2=[s2,n2] 。
请你找出一个可以满足使[S2,M] 从 S1获得的最大整数 M 。
示例：输入： s1 ="acb",n1 = 4 s2 ="ab",n2 = 2 返回：2

解题思路

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

func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
	count := 0
	j := 0
	for a := 0; a < n1; a++ {
		for i := 0; i < len(s1); i++ {
			if s1[i] == s2[j] {
				if j == len(s2)-1 {
					j = 0
					count++
				} else {
					j++
				}
			}
		}
	}
	return count / n2
}

472.连接词(1)

题目

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
示例 1：输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成; 
     "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成; 
     "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
示例 2：输入：words = ["cat","dog","catdog"] 输出：["catdog"]
提示：1 <= words.length <= 104
0 <= words[i].length <= 1000
words[i] 仅由小写字母组成
0 <= sum(words[i].length) <= 105

解题思路

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

func findAllConcatenatedWordsInADict(words []string) []string {
	res := make([]string, 0)
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})
	root := Trie{}
	for i := 0; i < len(words); i++ {
		if words[i] == "" {
			continue
		}
		if root.Dfs(words[i]) == true {
			res = append(res, words[i])
		} else {
			root.Insert(words[i])
		}
	}
	return res
}

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

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

func (this *Trie) Dfs(word string) bool {
	if word == "" {
		return true
	}
	temp := this
	for i := 0; i < len(word); i++ {
		value := word[i] - 'a'
		temp = temp.next[value]
		if temp == nil {
			return false
		}
		if temp.ending > 0 && this.Dfs(word[i+1:]) == true {
			return true
		}
	}
	return false
}

479.最大回文数乘积(1)

题目

你需要找到由两个 n 位数的乘积组成的最大回文数。
由于结果会很大，你只需返回最大回文数 mod 1337得到的结果。
示例:输入: 2 输出: 987
解释: 99 x 91 = 9009, 9009 % 1337 = 987
说明:n 的取值范围为[1,8]。

解题思路

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

func largestPalindrome(n int) int {
	if n == 1 {
		return 9
	}
	last := int(math.Pow10(n)) - 1 // 10^n-1 ：n=3 999
    first := last / 10             // 10^(n-1)-1 n=3 99
	for i := last; i > first; i-- {
		target := makePalindrome(i) // 依次生成对应的递减回文数：如98=>9889
		for j := last; j > first && target < j*j; j-- {
			if target%j == 0 { // 该回文数满足要求
				return target % 1337
			}
		}
	}
	return 0
}

func makePalindrome(num int) int {
	str := strconv.Itoa(num)
	arr := []byte(str)
	for i := len(str) - 1; i > -1; i-- {
		arr = append(arr, str[i])
	}
	res, _ := strconv.Atoi(string(arr))
	return res
}

480.滑动窗口中位数

题目

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：[2,3,4]，中位数是3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。
你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
示例：给出nums = [1,3,-1,-3,5,3,6,7]，以及k = 3。
窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7      -1
 1  3 [-1  -3  5] 3  6  7      -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6
因此，返回该滑动窗口的中位数数组[1,-1,-1,3,5,6]。
提示：你可以假设k始终有效，即：k 始终小于等于输入的非空数组的元素个数。
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。

解题思路

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

493.翻转对(4)

题目

给定一个数组nums，如果i < j且nums[i] > 2*nums[j]我们就将(i, j)称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:输入: [1,3,2,3,1] 输出: 2
示例 2:输入: [2,4,3,5,1] 输出: 3
注意:
给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。

解题思路

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

func reversePairs(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	a := append([]int{}, nums[:n/2]...)
	b := append([]int{}, nums[n/2:]...)
	res := reversePairs(a) + reversePairs(b) // 递归后，a、b分别有序
	i, j := 0, 0
	for i = 0; i < len(a); i++ {
		for j < len(b) && a[i] > 2*b[j] { // 统计
			j++
		}
		res = res + j
	}
	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 reversePairs(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	temp := make([]int, 0)
	for i := 0; i < n; i++ {
		// 会存在负数的情况：[-5,-5] => -5 > -10
		// 所以加入 2*nums[i] 参与离散化，后面直接查询2*nums[i]
		temp = append(temp, nums[i], 2*nums[i])
	}
	arr, m := getLSH(temp)
	length = len(arr)
	c = make([]int, length+1)
	res := 0
	for i := 0; i < n; i++ {
		index := m[2*nums[i]]
		// nums[i] > 2*nums[j] => x > 2*nums[i]
		count := getSum(index) // 统计之前插入了多少个小于等于2*nums[i]的数
		res = res + i - count  // i-count：剩下的就是大于2*nums[i]的数
		upData(m[nums[i]], 1)  // nums[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
}

# 3
func reversePairs(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	temp := make([]int, 0)
	for i := 0; i < n; i++ {
		// 会存在负数的情况：[-5,-5] => -5 > -10
		// 所以加入 2*nums[i] 参与离散化，后面直接查询2*nums[i]
		temp = append(temp, nums[i], 2*nums[i])
	}
	arr, m := getLSH(temp)
	length = len(arr)
	c = make([]int, length+1)
	res := 0
	for i := n - 1; i >= 0; i-- {
		index := m[nums[i]]
		// nums[i] > 2*nums[j] => 求小于nums[i]，其中2*nums[j]已经插入
		count := getSum(index - 1) // 统计插入了多少个小于nums[i]的数
		res = res + count          //
		upData(m[2*nums[i]], 1)    // 2*nums[j]次数+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
}

# 4
func reversePairs(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}
	temp := make([]int, 0)
	for i := 0; i < n; i++ {
		// 会存在负数的情况：[-5,-5] => -5 > -10
		// 所以加入 2*nums[i] 参与离散化，后面直接查询2*nums[i]
		temp = append(temp, nums[i], 2*nums[i])
	}
	tempArr, m := getLSH(temp)
	total := len(tempArr)
	arr = make([]int, 4*total+1)
	res := 0
	for i := n - 1; i >= 0; i-- {
		index := m[nums[i]]
		// nums[i] > 2*nums[j] => 求小于nums[i]，其中2*nums[j]已经插入
		count := query(0, 1, total, 1, index-1) // 统计插入了多少个小于nums[i]的数
		res = res + count                       //
		update(0, 1, total, m[2*nums[i]], 1)    // 2*nums[j]次数+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)
}

Files

0401-0500.md

Latest commit

History

0401-0500.md

File metadata and controls

0401-0500-Easy

401.二进制手表(3)

404.左叶子之和(2)

405.数字转换为十六进制数(2)

409.最长回文串(2)

412.Fizz Buzz(1)

414.第三大的数(2)

415.字符串相加(2)

434.字符串中的单词数(2)

437.路径总和III(4)

441.排列硬币(3)

443.压缩字符串(1)

447.回旋镖的数量(1)

448.找到所有数组中消失的数字(3)

453.最小移动次数使数组元素相等(2)

455.分发饼干(1)

459.重复的子字符串(2)

461.汉明距离(3)

463.岛屿的周长(3)

475.供暖器(2)

476.数字的补数(3)

482.密钥格式化(2)

485.最大连续1的个数(2)

492.构造矩形(1)

496.下一个更大元素 I(3)

500.键盘行(4)

0401-0500-Medium

402.移掉K位数字(1)

406.根据身高重建队列(2)

413.等差数列划分(3)

416.分割等和子集(3)

417.太平洋大西洋水流问题(2)

419.甲板上的战舰(3)

421.数组中两个数的最大异或值(2)

423.从英文中重建数字(1)

424.替换后的最长重复字符(3)

427.建立四叉树(2)

429.N叉树的层序遍历(2)

430.扁平化多级双向链表(3)

433.最小基因变化(3)

435.无重叠区间(4)

436.寻找右区间(2)

438.找到字符串中所有字母异位词(2)

442.数组中重复的数据(5)

445.两数相加II(3)

449.序列化和反序列化二叉搜索树(2)

450.删除二叉搜索树中的节点(2)

451.根据字符出现频率排序(2)

452.用最少数量的箭引爆气球(1)

454.四数相加II(2)

456.132模式(3)

457.环形数组循环(3)

462.最少移动次数使数组元素相等II(2)

464.我能赢吗(3)

467.环绕字符串中唯一的子字符串(1)

468.验证IP地址(1)

470.用Rand7()实现 Rand10()(2)

473.火柴拼正方形(2)

474.一和零(2)

477.汉明距离总和(1)

478.在圆内随机生成点(1)

481.神奇字符串(2)

486.预测赢家(3)

491.递增子序列(2)

494.目标和(5)

495.提莫攻击(1)

497.非重叠矩形中的随机点(1)

498.对角线遍历(2)

0401-0500-Hard

403.青蛙过河(4)

410.分割数组的最大值(3)

440.字典序的第K小数字(1)

446.等差数列划分II-子序列(1)

458.可怜的小猪(2)