0501-0600-Easy¶

501.二叉搜索树中的众数(2)¶

题目

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
    结点左子树中所含结点的值小于等于当前结点的值
    结点右子树中所含结点的值大于等于当前结点的值
    左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
   1
    \
     2
    /
   2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归+哈希辅助	O(n)	O(n)
02	递归+中序遍历	O(n)	O(log(n))

func findMode(root *TreeNode) []int {
	m := map[int]int{}
	dfs(root, m)
	max := -1
	res := make([]int, 0)
	for i, v := range m {
		if max <= v {
			if max < v {
				max = v
				res = res[0:0]
			}
			res = append(res, i)
		}
	}
	return res
}

func dfs(root *TreeNode, rec map[int]int) {
	if root == nil {
		return
	}
	rec[root.Val]++
	dfs(root.Left, rec)
	dfs(root.Right, rec)
}

#
var max int
var res []int
var cur int
var count int

func findMode(root *TreeNode) []int {
	res = make([]int, 0)
	max, cur, count = 0, 0, 0
	dfs(root)
	return res
}

// 中序遍历保证利用二叉搜索树的性质，得到的结果是升序的
func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	dfs(root.Left)
	if root.Val != cur {
		count = 0
	}
	count++
	if max < count {
		max = count
		res = []int{root.Val}
	} else if max == count {
		res = append(res, root.Val)
	}
	cur = root.Val
	dfs(root.Right)
}

504.七进制数(3)¶

题目

给定一个整数，将其转化为7进制，并以字符串形式输出。
示例 1:输入: 100 输出: "202"
示例 2: 输入: -7 输出: "-10"
注意: 输入范围是 [-1e7, 1e7] 。

解题思路

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

func convertToBase7(num int) string {
	if num == 0 {
		return "0"
	}

	minus := ""
	if num < 0 {
		minus = "-"
		num = -1 * num
	}

	s := ""
	for num > 0 {
		s = fmt.Sprintf("%d", num%7) + s
		num = num / 7
	}
	return minus + s
}

#
func convertToBase7(num int) string {
	return strconv.FormatInt(int64(num), 7)
}

#
func convertToBase7(num int) string {
	if num < 0 {
		return "-" + convertToBase7(-1*num)
	}
	if num < 7 {
		return strconv.Itoa(num)
	}
	return convertToBase7(num/7) + strconv.Itoa(num%7)
}

506.相对名次(1)¶

题目

给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。
前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”
（"Gold Medal", "Silver Medal", "Bronze Medal"）。
(注：分数越高的选手，排名越靠前。)

示例 1:
输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的，
因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。
提示:
    N 是一个正整数并且不会超过 10000。
    所有运动员的成绩都不相同。

解题思路

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

func findRelativeRanks(nums []int) []string {
	temp := make([]int, len(nums))
	copy(temp, nums)
	sort.Ints(temp)
	m := make(map[int]string)
	for i := 0; i < len(temp); i++ {
		if i == len(temp)-1 {
			m[temp[i]] = "Gold Medal"
		} else if i == len(temp)-2 {
			m[temp[i]] = "Silver Medal"
		} else if i == len(temp)-3 {
			m[temp[i]] = "Bronze Medal"
		} else {
			m[temp[i]] = strconv.Itoa(len(temp) - i)
		}
	}
	res := make([]string,0)
	for i := 0; i < len(nums); i++ {
		res = append(res, m[nums[i]])
	}
	return res
}

507.完美数(1)¶

题目

对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。
给定一个 整数 n， 如果他是完美数，返回 True，否则返回 False
示例：输入: 28 输出: True 解释: 28 = 1 + 2 + 4 + 7 + 14
提示：输入的数字 n 不会超过 100,000,000. (1e8)

解题思路

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

func checkPerfectNumber(num int) bool {
	if num == 1 {
		return false
	}
	sum := 1
	for i := 2; i <= num/i; i++ {
		if num%i == 0 {
			sum = sum + i + (num / i)
		}
	}
	return sum == num
}

509.斐波那契数(6)¶

题目

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：输入：2输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：输入：3输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：输入：4输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
    0 ≤ N ≤ 30

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	遍历+数组	O(n)	O(n)
03	递归	O(2^n)	O(n)
04	公式法	O(1)	O(1)
05	矩阵快速幂	O(log(n))	O(1)
06	矩阵快速幂	O(n)	O(1)

func fib(N int) int {
	if N == 0 {
		return 0
	}
	if N == 1 {
		return 1
	}
	n1, n2 := 0, 1
	for i := 2; i <= N; i++ {
		n1, n2 = n2, n1+n2
	}
	return n2
}

#
func fib(N int) int {
	if N == 0 {
		return 0
	}
	if N == 1 {
		return 1
	}
	res := make([]int, N+1)
	res[0] = 0
	res[1] = 1
	for i := 2; i <= N; i++ {
		res[i] = res[i-1] + res[i-2]
	}
	return res[N]
}

#
func fib(N int) int {
	if N == 0 {
		return 0
	}
	if N == 1 {
		return 1
	}
	return fib(N-1) + fib(N-2)
}

#
func fib(N int) int {
	temp1 := (1 + math.Sqrt(5)) / 2
	temp2 := (1 - math.Sqrt(5)) / 2
	fn := math.Round((math.Pow(temp1, float64(N))- math.Pow(temp2, float64(N)))/ math.Sqrt(5))
	return int(fn)
}

# 5
func fib(N int) int {
	if N == 0 {
		return 0
	}
	/*
		ans = [Fn+1 Fn
			   Fn Fn-1]
			= [ 1 0
		 		0 1]
	*/
	ans := matrix{
		a: 1,
		b: 0,
		c: 0,
		d: 1,
	}
	m := matrix{
		a: 1,
		b: 1,
		c: 1,
		d: 0,
	}
	for N > 0 {
		if N%2 == 1 {
			ans = multi(ans, m)
		}
		m = multi(m, m)
		N = N >> 1
	}
	return ans.b
}

/*
a b
c d
*/
type matrix struct {
	a, b, c, d int
}

// 矩阵乘法
func multi(x, y matrix) matrix {
	newA := x.a*y.a + x.b*y.c
	newB := x.a*y.b + x.b*y.d
	newC := x.c*y.a + x.d*y.c
	newD := x.c*y.b + x.d*y.d
	return matrix{
		a: newA,
		b: newB,
		c: newC,
		d: newD,
	}
}

# 6
func fib(N int) int {
	if N == 0 {
		return 0
	}
	/*
		ans = [Fn+1 Fn
			   Fn Fn-1]
			= [ 1 0
		 		0 1]
	*/
	ans := matrix{
		a: 1,
		b: 0,
		c: 0,
		d: 1,
	}
	m := matrix{
		a: 1,
		b: 1,
		c: 1,
		d: 0,
	}
	for N > 0 {
		ans = multi(ans, m)
		N--
	}
	return ans.b
}

/*
a b
c d
*/
type matrix struct {
	a, b, c, d int
}

// 矩阵乘法
func multi(x, y matrix) matrix {
	newA := x.a*y.a + x.b*y.c
	newB := x.a*y.b + x.b*y.d
	newC := x.c*y.a + x.d*y.c
	newD := x.c*y.b + x.d*y.d
	return matrix{
		a: newA,
		b: newB,
		c: newC,
		d: newD,
	}
}

520.检测大写字母(2)¶

题目

给定一个单词，你需要判断单词的大写使用是否正确。
我们定义，在以下情况时，单词的大写用法是正确的：
    全部字母都是大写，比如"USA"。
    单词中所有字母都不是大写，比如"leetcode"。
    如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。
否则，我们定义这个单词没有正确使用大写字母。
示例 1:输入: "USA"输出: True
示例 2:输入: "FlaG"输出: False
注意: 输入是由大写和小写拉丁字母组成的非空单词。

解题思路

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

func detectCapitalUse(word string) bool {
	if word == "" {
		return false
	}
	count := 0
	for i := 0; i < len(word); i++ {
		if word[i] >= 'A' && word[i] <= 'Z' {
			count++
		}
	}

	if count == 0 || count == len(word) ||
		(count == 1 && word[0] >= 'A' && word[0] <= 'Z') {
		return true
	}
	return false
}

#
func detectCapitalUse(word string) bool {
	pattern := "(^[a-z]+)$|(^[A-Z]+)$|(^[A-Z]{1}[a-z]*)$"
	isMatch, _ := regexp.MatchString(pattern, word)
	return isMatch
}

521.最长特殊序列Ⅰ(1)¶

题目

给你两个字符串，请你从这两个字符串中找出最长的特殊序列。
「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。

输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

示例 1：输入: "aba", "cdc" 输出: 3 
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。
示例 2：输入：a = "aaa", b = "bbb"输出：3
示例 3：输入：a = "aaa", b = "aaa"输出：-1
提示：
    两个字符串长度均处于区间 [1 - 100] 。
    字符串中的字符仅含有 'a'~'z' 。

解题思路

No.	思路	时间复杂度	空间复杂度
01	比较	O(1)	O(1)

func findLUSlength(a string, b string) int {
	if a == b {
		return -1
	}
	return max(len(a), len(b))
}

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

530.二叉搜索树的最小绝对差(3)¶

题目

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：

   1
    \
     3
    /
   2

输出：1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
提示：
    树中至少有 2 个节点。
    本题与 783 https://leetcode.cn/problems/minimum-distance-between-bst-nodes/ 相同

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归+中序遍历	O(n)	O(log(n))
02	递归+遍历	O(n)	O(n)
03	迭代	O(n)	O(n)

var minDiff, previous int
func getMinimumDifference(root *TreeNode) int {
	minDiff, previous  = math.MaxInt32, math.MaxInt32
	dfs(root)
	return minDiff
}

func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	dfs(root.Left)

	newDiff := diff(previous, root.Val)
	if minDiff > newDiff {
		minDiff = newDiff
	}
	previous = root.Val
	dfs(root.Right)
}

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

#
func getMinimumDifference(root *TreeNode) int {
	arr := make([]int, 0)
	dfs(root, &arr)
	minDiff := arr[1] - arr[0]
	for i := 2; i < len(arr); i++ {
		if minDiff > arr[i]-arr[i-1] {
			minDiff = arr[i] - arr[i-1]
		}
	}
	return minDiff
}

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

532.数组中的K-diff数对(3)¶

题目

给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。
这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

示例 1: 输入: [3, 1, 4, 1, 5], k = 2 输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。
示例 2:输入:[1, 2, 3, 4, 5], k = 1 输出: 4
解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3:输入: [1, 3, 1, 5, 4], k = 0 输出: 1
解释: 数组中只有一个 0-diff 数对，(1, 1)。
注意:
    数对 (i, j) 和数对 (j, i) 被算作同一数对。
    数组的长度不超过10,000。
    所有输入的整数的范围在 [-1e7, 1e7]。

解题思路

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

func findPairs(nums []int, k int) int {
	if k < 0 {
		return 0
	}
	record := make(map[int]int)
	for _, num := range nums {
		record[num]++
	}
	res := 0
	if k == 0 {
		for _, count := range record {
			if count > 1 {
				res++
			}
		}
		return res
	} else {
		for n := range record {
			if record[n-k] > 0 {
				res++
			}
		}
		return res
	}
}

#
func findPairs(nums []int, k int) int {
	if k < 0 {
		return 0
	}
	m := make(map[int]bool)
	res := make(map[int]bool)
	for _, value := range nums {
		if m[value-k] {
			res[value-k] = true
		}
		if m[value+k] {
			res[value] = true
		}
		m[value] = true
	}
	return len(res)
}

538.把二叉搜索树转换为累加树(2)¶

题目

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，
使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树:
              5
            /   \
           2     13
输出: 转换为累加树:
             18
            /   \
          20     13
注意：
本题和 1038: https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/ 相同

解题思路

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

func convertBST(root *TreeNode) *TreeNode {
	sum := 0
	dfs(root, &sum)
	return root
}

func dfs(root *TreeNode, sum *int) {
	if root == nil {
		return
	}
	dfs(root.Right, sum)
	*sum = *sum + root.Val
	root.Val = *sum
	dfs(root.Left, sum)
}

#
func convertBST(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	stack := make([]*TreeNode, 0)
	temp := root
	sum := 0
	for {
		if temp != nil {
			stack = append(stack, temp)
			temp = temp.Right
		} else if len(stack) != 0 {
			temp = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			temp.Val = temp.Val + sum
			sum = temp.Val
			temp = temp.Left
		} else {
			break
		}
	}
	return root
}

541.反转字符串II(2)¶

题目

给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。
如果剩余少于 k 个字符，则将剩余的所有全部反转。
如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。

示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
要求:
    该字符串只包含小写的英文字母。
    给定字符串的长度和 k 在[1, 10000]范围内。

解题思路

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

func reverseStr(s string, k int) string {
	arr := []byte(s)
	for i := 0; i < len(s); i = i + 2*k {
		j := min(i+k, len(s))
		reverse(arr[i:j])
	}
	return string(arr)
}

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

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

#
func reverseStr(s string, k int) string {
	arr := []byte(s)
	for i := 0; i < len(s); i = i + k {
		if i%(2*k) == 0 {
			j := i + k
			if len(arr) < j {
				j = len(arr)
			}
			reverse(arr[i:j])
		}
	}
	return string(arr)
}

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

543.二叉树的直径(2)¶

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。

解题思路

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

var res int
func diameterOfBinaryTree(root *TreeNode) int {
	res = 0
	dfs(root)
	return res
}

func dfs(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := dfs(root.Left)
	right := dfs(root.Right)
	path := max(left, right)
	res = max(left+right, res) // 当前节点最大直径与当前保存最大值比较
	return path + 1 // 以该节点为根的最大深度
}

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

#
func diameterOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	max := 0
	stack := make([]*TreeNode, 0)
	m := make(map[*TreeNode]int)

	cur := root
	var prev *TreeNode
	for cur != nil || len(stack) != 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		if cur.Right == nil || cur.Right == prev {
			cur = stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			leftLen := 0
			rightLen := 0
			if v, ok := m[cur.Left]; ok {
				leftLen = v
			}
			if v, ok := m[cur.Right]; ok {
				rightLen = v
			}
			if leftLen > rightLen {
				m[cur] = leftLen + 1
			} else {
				m[cur] = rightLen + 1
			}
			if max < leftLen+rightLen {
				max = leftLen + rightLen
			}
			prev = cur
			cur = nil
		} else {
			cur = cur.Right
		}
	}
	return max
}

551.学生出勤记录 I(2)¶

题目

给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：
    'A' : Absent，缺勤
    'L' : Late，迟到
    'P' : Present，到场
如果一个学生的出勤记录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到),那么这个学生会被奖赏。
你需要根据这个学生的出勤记录判断他是否会被奖赏。

示例 1:输入: "PPALLP"输出: True
示例 2:输入: "PPALLL"输出: False

解题思路

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

func checkRecord(s string) bool {
	if strings.Count(s, "A") <= 1 && strings.Count(s, "LLL") == 0 {
		return true
	}
	return false
}

#
func checkRecord(s string) bool {
	aNum := 0
	lNum := 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'A' {
			aNum++
		}
		if s[i] == 'L' {
			lNum++
		} else {
			lNum = 0
		}
		if aNum == 2 {
			return false
		}
		if lNum == 3 {
			return false
		}
	}
	return true
}

557.反转字符串中的单词 III(2)¶

题目

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc" 

注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

解题思路分析

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

func reverseWords(s string) string {
	strS := strings.Split(s, " ")
	for i, s := range strS {
		strS[i] = reverse(s)
	}
	return strings.Join(strS, " ")
}

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

#
func reverseWords(s string) string {
	arr := []byte(s)
	j := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] == ' ' {
			reverse(arr, j, i-1)
			j = i + 1
		}
	}
	reverse(arr, j, len(arr)-1)
	return string(arr)
}

func reverse(arr []byte, i, j int) []byte {
	for i < j {
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
	return arr
}

559.N叉树的最大深度(2)¶

题目

给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如，给定一个 3叉树 :
我们应返回其最大深度，3。
说明:
    树的深度不会超过 1000。
    树的节点总不会超过 5000。

解题思路

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

func maxDepth(root *Node) int {
	if root == nil {
		return 0
	}
	depth := 0
	for _, node := range root.Children {
		depth = max(depth, maxDepth(node))
	}
	return depth + 1
}

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

#
func maxDepth(root *Node) int {
	if root == nil {
		return 0
	}
	queue := make([]*Node, 0)
	depth := 0
	queue = append(queue, root)
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			temp := queue[0]
			for _, node := range temp.Children {
				queue = append(queue, node)
			}
			queue = queue[1:]
		}
		depth++
	}
	return depth
}

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

561.数组拆分 I(2)¶

题目

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，
使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:输入: [1,4,3,2]输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:
    n 是正整数,范围在 [1, 10000].
    数组中的元素范围在 [-10000, 10000].

解题思路

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

func arrayPairSum(nums []int) int {
	sort.Ints(nums)
	sum := 0
	for k, v := range nums {
		if k%2 == 0 {
			sum = sum + v
		}
	}
	return sum
}

#
func arrayPairSum(nums []int) int {
	var arr [20010]int
	for _, num := range nums {
		arr[num+10000]++
	}
	sum := 0
	needAdd := true
	for num, count := range arr {
		for count > 0 {
			if needAdd {
				sum = sum + num - 10000
			}
			needAdd = !needAdd
			count--
		}
	}
	return sum
}

563.二叉树的坡度(2)¶

题目

给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。

示例:

输入: 
         1
       /   \
      2     3
输出: 1
解释: 
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
注意:
    任何子树的结点的和不会超过32位整数的范围。
    坡度的值不会超过32位整数的范围。

解题思路

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

var total int

func findTilt(root *TreeNode) int {
	total = 0
	dfs(root)
	return total
}

func dfs(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := dfs(root.Left)
	right := dfs(root.Right)
	total = total + abs(left, right)
	return left + right + root.Val // 返回节点之和
}

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

#
func findTilt(root *TreeNode) int {
	if root == nil {
		return 0
	}
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	list := make([]*TreeNode, 0)
	total := 0
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		list = append([]*TreeNode{node}, list...)
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	for i := range list {
		node := list[i]
		left := 0
		right := 0
		if node.Left != nil {
			left = node.Left.Val
		}
		if node.Right != nil {
			right = node.Right.Val
		}
		total = total + abs(left, right)
		node.Val = left + right + node.Val
	}
	return total
}

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

566.重塑矩阵(2)¶

题目

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1:输入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
输出: 
[[1,2,3,4]]
解释:行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

示例 2:输入: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
输出: 
[[1,2],
 [3,4]]
解释:没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
注意：
    给定矩阵的宽和高范围在 [1, 100]。
    给定的 r 和 c 都是正数。

解题思路

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

func matrixReshape(nums [][]int, r int, c int) [][]int {
	row, col := len(nums), len(nums[0])
	if (row*col != r*c) || (row == r && col == c) {
		return nums
	}
	res := make([][]int, r)
	for i := 0; i < len(res); i++ {
		res[i] = make([]int, c)
	}
	for i := 0; i < r*c; i++ {
		res[i/c][i%c] = nums[i/col][i%col]
	}
	return res
}

#
func matrixReshape(nums [][]int, r int, c int) [][]int {
	row, col := len(nums), len(nums[0])
	if (row*col != r*c) || (row == r && col == c) {
		return nums
	}
	res := make([][]int, 0)
	arr := make([]int, 0)
	count := 0
	for _, num := range nums {
		for _, value := range num {
			arr = append(arr, value)
			count++
			if count == c {
				res = append(res, arr)
				arr = []int{}
				count = 0
			}
		}
	}
	return res
}

572.另一个树的子树(3)¶

题目

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
     3
    / \
   4   5
  / \
 1   2

给定的树 t：
   4 
  / \
 1   2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

     3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t：
   4
  / \
 1   2
返回 false。

解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n^2)	O(log(n))
02	递归+字符串辅助	O(n)	O(log(n))
03	栈辅助	O(n)	O(n)

func isSubtree(s *TreeNode, t *TreeNode) bool {
	if s == nil {
		return false
	}
	return isSame(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
}

func isSame(s *TreeNode, t *TreeNode) bool {
	if s == nil || t == nil{
		return t == s
	}
	return isSame(s.Left, t.Left) && isSame(s.Right, t.Right) && s.Val == t.Val
}

#
func isSubtree(s *TreeNode, t *TreeNode) bool {
	sStr := dfs(s, "")
	tStr := dfs(t, "")
	return strings.Contains(sStr, tStr)
}

func dfs(s *TreeNode, pre string) string {
	if s == nil {
		return pre
	}
	return fmt.Sprintf("#%d%s%s", s.Val, dfs(s.Left, "l"), dfs(s.Right, "r"))
}

#
func isSubtree(s *TreeNode, t *TreeNode) bool {
	sStr := preOrder(s)
	tStr := preOrder(t)
	return strings.Contains(sStr, tStr)
}

func preOrder(root *TreeNode) string {
	if root == nil {
		return ""
	}
	res := "!"
	stack := make([]*TreeNode,0)
	temp := root
	for {
		for temp != nil{
			res += strconv.Itoa(temp.Val)
			res += "!"
			stack = append(stack, temp)
			temp = temp.Left
		}
		res += "#!"
		if len(stack) > 0{
			node := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			temp = node.Right
		}else {
			break
		}
	}
	return res
}

575.分糖果(2)¶

题目

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。
你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:输入: candies = [1,1,2,2,3,3] 输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
     最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 : 输入: candies = [1,1,2,3] 输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。
这样使得妹妹可以获得的糖果种类数最多。

注意:
    数组的长度为[2, 10,000]，并且确定为偶数。
    数组中数字的大小在范围[-100,000, 100,000]内。 

解题思路

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

func distributeCandies(candies []int) int {
	n := len(candies)
	r := make(map[int]bool, n)
	for _, c := range candies {
		r[c] = true
	}
	return min(len(r), n/2)
}

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

#
func distributeCandies(candies []int) int {
	length := len(candies)
	half := length / 2
	count := 1
	sort.Ints(candies)
	for i := 1; i < length; i++ {
		if candies[i] != candies[i-1] {
			count++
		}
	}
	if count >= half {
		return half
	}
	return count
}

581.最短无序连续子数组(3)¶

题目

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
    输入的数组长度范围在 [1, 10,000]。
    输入的数组可能包含重复元素 ，所以升序的意思是<=。

解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	2次遍历	O(n)	O(1)
03	排序遍历	O(nlog(n))	O(n)

func findUnsortedSubarray(nums []int) int {
	length := len(nums)
	left, right := 0, -1
	min, max := nums[length-1], nums[0]
	for i := 1; i < length; i++ {
		if max <= nums[i] {
			max = nums[i]
		} else {
			right = i
		}
		j := length - i - 1
		if min >= nums[j] {
			min = nums[j]
		} else {
			left = j
		}
	}
	return right - left + 1
}

#
func findUnsortedSubarray(nums []int) int {
	length := len(nums)
	right := -1
	max := nums[0]
	for i := 1; i < length; i++ {
		if max <= nums[i] {
			max = nums[i]
		} else {
			right = i
		}
	}
	if right == 0 {
		// 针对升序，特殊处理
		// 如去掉判断
		// 需要保证left,right初始值满足right-left+1=0
		return 0
	}
	left := 0
	min := nums[length-1]
	for i := length - 2; i >= 0; i-- {
		if min >= nums[i] {
			min = nums[i]
		} else {
			left = i
		}
	}
	return right - left + 1
}

#
func findUnsortedSubarray(nums []int) int {
	temp := make([]int,len(nums))
	copy(temp,nums)
	sort.Ints(temp)
	i, j := 0, len(nums)-1
	for i < len(nums) && nums[i] == temp[i]{
		i++
	}
	for i+1 < j && nums[j] == temp[j]{
		j--
	}
	return j-i+1
}

589.N叉树的前序遍历(2)¶

题目

给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 :
返回其前序遍历: [1,3,5,6,2,4]。
说明: 递归法很简单，你可以使用迭代法完成此题吗?

解题思路

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

var res []int

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

func dfs(root *Node) {
	if root == nil {
		return
	}
	res = append(res, root.Val)
	for _, value := range root.Children {
		dfs(value)
	}
}

#
func preorder(root *Node) []int {
	res := make([]int, 0)
	if root == nil {
		return res
	}
	stack := make([]*Node, 0)
	stack = append(stack, root)
	for len(stack) > 0 {
		temp := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, temp.Val)
		for i := len(temp.Children) - 1; i >= 0; i-- {
			stack = append(stack, temp.Children[i])
		}
	}
	return res
}

590.N叉树的后序遍历(2)¶

题目

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单，你可以使用迭代法完成此题吗?

解题思路

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

var res []int
func postorder(root *Node) []int {
	res = make([]int, 0)
	dfs(root)
	return res
}

func dfs(root *Node) {
	if root == nil {
		return
	}
	for _, value := range root.Children {
		dfs(value)
	}
	res = append(res, root.Val)
}

#
// 后序：(左右)根
// 前序：根(左右)=>根(右左)=>左右根
func postorder(root *Node) []int {
	res := make([]int, 0)
	if root == nil {
		return res
	}
	stack := make([]*Node, 0)
	stack = append(stack, root)
	for len(stack) > 0 {
		temp := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, temp.Val)
		for i := 0; i < len(temp.Children); i++ {
			stack = append(stack, temp.Children[i])
		}
	}
	for i := 0; i < len(res)/2; i++ {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
	}
	return res
}

594.最长和谐子序列(2)¶

题目

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。
示例 1:输入: [1,3,2,2,5,2,3,7]输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.

解题思路

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

func findLHS(nums []int) int {
	m := make(map[int]int, len(nums))
	for _, n := range nums {
		m[n]++
	}
	res := 0
	for key, value := range m {
		value2, ok := m[key+1]
		if ok {
			t := value + value2
			if res < t {
				res = t
			}
		}
	}
	return res
}

#
func findLHS(nums []int) int {
	sort.Ints(nums)
	res := 0
	left := 0
	for i := 0; i < len(nums); i++ {
		for nums[i]-nums[left] > 1 {
			left++
		}
		if nums[i]-nums[left] == 1 {
			if res < i-left+1 {
				res = i - left + 1
			}
		}
	}
	return res
}

598.范围求和 II(1)¶

题目

给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，
含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。
在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

示例 1:输入: m = 3, n = 3operations = [[2,2],[3,3]] 输出: 4
解释: 初始状态, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
执行完操作 [2,2] 后, M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]
执行完操作 [3,3] 后, M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
注意:
    m 和 n 的范围是 [1,40000]。
    a 的范围是 [1,m]，b 的范围是 [1,n]。
    操作数目不超过 10000。

解题思路

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

func maxCount(m int, n int, ops [][]int) int {
	for _, o := range ops {
		m = min(m, o[0])
		n = min(n, o[1])
	}
	return m * n
}

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

599.两个列表的最小索引总和(2)¶

题目

假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。
你可以假设总是存在一个答案。

示例 1:输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

提示:
    两个列表的长度范围都在 [1, 1000]内。
    两个列表中的字符串的长度将在[1，30]的范围内。
    下标从0开始，到列表的长度减1。
    两个列表都没有重复的元素。

解题思路

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

func findRestaurant(list1 []string, list2 []string) []string {
	if len(list1) > len(list2) {
		list1, list2 = list2, list1
	}
	m2 := make(map[string]int, len(list2))
	for i := range list2 {
		m2[list2[i]] = i
	}
	min := 2000
	res := make([]string, 0, 1000)
	for key, value := range list1 {
		if key2, ok := m2[value]; ok {
			if min == key+key2 {
				res = append(res, value)
			}
			if min > key+key2 {
				min = key + key2
				res = []string{value}
			}
		}
	}
	return res
}

#
func findRestaurant(list1 []string, list2 []string) []string {
	min := 2000
	res := make([]string, 0, 1000)
	for key1, value1 := range list1 {
		for key2, value2 := range list2{
			if value1 == value2{
				if min == key1+key2 {
					res = append(res, value1)
				}
				if min > key1+key2 {
					min = key1 + key2
					res = []string{value1}
				}
			}
		}
	}
	return res
}

0501-0600-Medium¶

503.下一个更大元素II(2)¶

题目

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，
这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:输入: [1,2,1] 输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。

解题思路

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

func nextGreaterElements(nums []int) []int {
	res := make([]int, len(nums))
	if len(nums) == 0 {
		return res
	}
	for i := 0; i < len(nums); i++ {
		res[i] = -1
	}
	stack := make([]int, 0)
	for i := 0; i < len(nums)*2; i++ {
		index := i % len(nums)
		for len(stack) > 0 && nums[index] > nums[stack[len(stack)-1]] {
			if res[stack[len(stack)-1]] == -1 {
				res[stack[len(stack)-1]] = nums[index]
			}
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, index)
	}
	return res
}

# 2
func nextGreaterElements(nums []int) []int {
	res := make([]int, len(nums))
	if len(nums) == 0 {
		return res
	}
	stack := make([]int, 0)
	for i := 2*len(nums) - 1; i >= 0; i-- {
		index := i % len(nums)
		for len(stack) > 0 && nums[index] >= stack[len(stack)-1] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			res[index] = -1
		} else {
			res[index] = stack[len(stack)-1]
		}
		stack = append(stack, nums[index])
	}
	return res
}

508.出现次数最多的子树元素和(1)¶

题目

给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。
一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
你需要返回出现次数最多的子树元素和。
如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
示例 1：输入:
  5
 /  \
2   -3
返回[2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。
示例2：输入：
  5
 /  \
2   -5
返回[2]，只有 2 出现两次，-5 只出现 1 次。
提示：假设任意子树元素和均可以用 32 位有符号整数表示。

解题思路

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

var m map[int]int

func findFrequentTreeSum(root *TreeNode) []int {
	m = make(map[int]int)
	res := make([]int, 0)
	dfs(root)
	maxValue := 0
	for k, v := range m {
		if v > maxValue {
			maxValue = v
			res = []int{k}
		} else if maxValue == v {
			res = append(res, k)
		}
	}
	return res
}

func dfs(root *TreeNode) int {
	if root == nil {
		return 0
	}
	sum := root.Val + dfs(root.Left) + dfs(root.Right)
	m[sum]++
	return sum
}

513.找树左下角的值(2)¶

题目

给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:输入:
    2
   / \
  1   3
输出:1
示例 2:输入:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
输出:7

解题思路

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

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

# 2
var res int
var maxLevel int

func findBottomLeftValue(root *TreeNode) int {
	res = 0
	maxLevel = -1
	if root == nil {
		return res
	}
	dfs(root, 0)
	return res
}

func dfs(root *TreeNode, level int) {
	if root == nil {
		return
	}
	dfs(root.Left, level+1)
	if level > maxLevel {
		maxLevel = level
		res = root.Val
	}
	dfs(root.Right, level+1)
}

515.在每个树行中找最大值(2)¶

题目

您需要在二叉树的每一行中找到最大的值。
示例：输入: 
          1
         / \
        3   2
       / \   \  
      5   3   9 
输出: [1, 3, 9]

解题思路

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

func largestValues(root *TreeNode) []int {
	res := make([]int, 0)
	if root == nil {
		return res
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		length := len(queue)
		maxValue := math.MinInt32
		for i := 0; i < length; i++ {
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
			if maxValue < queue[i].Val {
				maxValue = queue[i].Val
			}
		}
		res = append(res, maxValue)
		queue = queue[length:]
	}
	return res
}

# 2
var res []int

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

func dfs(root *TreeNode, level int) {
	if root == nil {
		return
	}
	if level >= len(res) {
		res = append(res, math.MinInt32)
	}
	res[level] = max(res[level], root.Val)
	dfs(root.Left, level+1)
	dfs(root.Right, level+1)
}

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

516.最长回文子序列(3)¶

题目

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:输入:"bbbab"输出:4
一个可能的最长回文子序列为 "bbbb"。
示例 2:输入:"cbbd"输出:2
一个可能的最长回文子序列为 "bb"。
提示：
    1 <= s.length <= 1000
    s 只包含小写英文字母

解题思路

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

func longestPalindromeSubseq(s string) int {
	if len(s) <= 1 {
		return len(s)
	}
	n := len(s)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1] + 2 // 内层+2
			} else {
				dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			}
		}
	}
	return dp[0][n-1]
}

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

# 2
func longestPalindromeSubseq(s string) int {
	if len(s) <= 1 {
		return len(s)
	}
	n := len(s)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
	}
	for i := n - 1; i >= 0; i-- {
		prev := 0
		for j := i + 1; j < n; j++ {
			temp := dp[j]
			if s[i] == s[j] {
				dp[j] = prev + 2 // 内层+2
			} else {
				dp[j] = max(dp[j], dp[j-1])
			}
			prev = temp
		}
	}
	return dp[n-1]
}

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

# 3
var dp [][]int

func longestPalindromeSubseq(s string) int {
	if len(s) <= 1 {
		return len(s)
	}
	n := len(s)
	dp = make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	return dfs(s, 0, n-1)
}

func dfs(s string, i, j int) int {
	if i == j {
		return 1
	}
	if i > j {
		return 0
	}
	if dp[i][j] > 0 {
		return dp[i][j]
	}
	if s[i] == s[j] {
		dp[i][j] = dfs(s, i+1, j-1) + 2
	} else {
		dp[i][j] = max(dfs(s, i+1, j), dfs(s, i, j-1))
	}
	return dp[i][j]
}

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

518.零钱兑换II(2)¶

题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 
示例 1:输入: amount = 5, coins = [1, 2, 5] 输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:输入: amount = 3, coins = [2] 输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:输入: amount = 10, coins = [10]  输出: 1
注意:你可以假设：
    0 <= amount (总金额) <= 5000
    1 <= coin (硬币面额) <= 5000
    硬币种类不超过 500 种
    结果符合 32 位符号整数

解题思路

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

func change(amount int, coins []int) int {
	n := len(coins)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, amount+1)
		dp[i][0] = 1 // 金额为0的情况，只有都不选，组合情况为1
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= amount; j++ {
			if j-coins[i-1] >= 0 {
				dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[n][amount]
}

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

519.随机翻转矩阵(1)¶

题目

题中给出一个 n_rows 行 n_cols 列的二维矩阵，且所有值被初始化为 0。
要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 [row_id,col_id]；
同样编写一个 reset 函数，将所有的值都重新置为 0。
尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。
注意:1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows 并且 0 <= col.id < n_cols
当矩阵中没有值为 0 时，不可以调用 flip 函数
调用 flip 和 reset 函数的次数加起来不会超过 1000 次
示例 1：输入:  ["Solution","flip","flip","flip","flip"]  [[2,3],[],[],[],[]]
输出: [null,[0,1],[1,2],[1,0],[1,1]]
示例 2：输入:  ["Solution","flip","flip","reset","flip"] [[1,2],[],[],[],[]]
输出: [null,[0,0],[0,1],null,[0,0]]
输入语法解释：
输入包含两个列表：被调用的子程序和他们的参数。Solution 的构造函数有两个参数，分别为 n_rows 和 n_cols。
flip和 reset 没有参数，参数总会以列表形式给出，哪怕该列表为空

解题思路

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

type Solution struct {
	m     map[int]bool
	rows  int
	cols  int
	total int
}

func Constructor(n_rows int, n_cols int) Solution {
	return Solution{
		m:     make(map[int]bool),
		rows:  n_rows,
		cols:  n_cols,
		total: 0,
	}
}

func (this *Solution) Flip() []int {
	if this.total >= this.rows*this.cols {
		return nil
	}
	for {
		index := rand.Intn(this.rows * this.cols)
		if this.m[index] == true {
			continue
		}
		a, b := index/this.cols, index%this.cols
		this.m[index] = true
		this.total++
		return []int{a, b}
	}
}

func (this *Solution) Reset() {
	this.m = make(map[int]bool)
	this.total = 0
}

522.最长特殊序列II(3)¶

题目

给定字符串列表，你需要从它们中找出最长的特殊序列。
最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。
空序列为所有字符串的子序列，任何字符串为其自身的子序列。
输入将是一个字符串列表，输出是最长特殊序列的长度。如果最长特殊序列不存在，返回 -1 。
示例：输入: "aba", "cdc", "eae" 输出: 3
提示：所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。

解题思路

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

func findLUSlength(strs []string) int {
	m := make(map[string]int)
	for i := 0; i < len(strs); i++ {
		total := 1 << (len(strs[i]))
		for j := 0; j < total; j++ {
			s := ""
			for k := 0; k < len(strs[i]); k++ {
				if (j>>k)&1 != 0 {
					s = s + string(strs[i][k])
				}
			}
			m[s]++
		}
	}
	res := -1
	for k, v := range m {
		if v == 1 && len(k) > res {
			res = len(k)
		}
	}
	return res
}

# 2
func findLUSlength(strs []string) int {
	res := -1
	var j int
	for i := 0; i < len(strs); i++ {
		for j = 0; j < len(strs); j++ {
			if i == j {
				continue
			}
			if judge(strs[i], strs[j]) == true {
				break
			}
		}
		if j == len(strs) && len(strs[i]) > res {
			res = len(strs[i])
		}
	}

	return res
}

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

# 3
func findLUSlength(strs []string) int {
	sort.Slice(strs, func(i, j int) bool {
		return len(strs[i]) > len(strs[j])
	})
	res := -1
	var j int
	for i := 0; i < len(strs); i++ {
		for j = 0; j < len(strs); j++ {
			if i == j {
				continue
			}
			if judge(strs[i], strs[j]) == true {
				break
			}
		}
		if j == len(strs) {
			return len(strs[i])
		}
	}
	return res
}

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

523.连续的子数组和(2)¶

题目

给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，
其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1：输入：[23,2,4,6,7], k = 6 输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：输入：[23,2,6,4,7], k = 6 输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明：
    数组的长度不会超过 10,000 。
    你可以认为所有数字总和在 32 位有符号整数范围内。

解题思路

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

func checkSubarraySum(nums []int, k int) bool {
	if len(nums) == 0 {
		return false
	}
	m := make(map[int]int)
	m[0] = -1
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
		if k != 0 {
			sum = sum % k
		}
		if _, ok := m[sum]; ok {
			// 确保数组大小至少为2
			if i-m[sum] >= 2 {
				return true
			}
		} else {
			m[sum] = i
		}
	}
	return false
}

# 2
func checkSubarraySum(nums []int, k int) bool {
	if len(nums) == 0 {
		return false
	}
	arr := make([]int, len(nums))
	arr[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		arr[i] = arr[i-1] + nums[i]
	}
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			sum := arr[j] - arr[i] + nums[i]
			if sum == k || (k != 0 && sum%k == 0) {
				return true
			}
		}
	}
	return false
}

524.通过删除字母匹配到字典里最长单词(2)¶

题目

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] 输出："apple"
示例 2：输入：s = "abpcplea", dictionary = ["a","b","c"] 输出："a"
提示：1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+子序列	O(n^2)	O(1)
02	子序列	O(n^2)	O(n)

func findLongestWord(s string, dictionary []string) string {
	sort.Slice(dictionary, func(i, j int) bool {
		if len(dictionary[i]) == len(dictionary[j]) {
			return dictionary[i] < dictionary[j]
		}
		return len(dictionary[i]) > len(dictionary[j])
	})
	for i := 0; i < len(dictionary); i++ {
		if isSubsequence(dictionary[i], s) {
			return dictionary[i]
		}
	}
	return ""
}

// leetcode392.判断子序列
func isSubsequence(s string, t string) bool {
	if len(s) > len(t) {
		return false
	}
	i := 0
	j := 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == len(s)
}

# 2
func findLongestWord(s string, dictionary []string) string {
	res := ""
	for i := 0; i < len(dictionary); i++ {
		if isSubsequence(dictionary[i], s) {
			if len(dictionary[i]) > len(res) ||
				(len(dictionary[i]) == len(res) && dictionary[i] < res) {
				res = dictionary[i]
			}
		}
	}
	return res
}

// leetcode392.判断子序列
func isSubsequence(s string, t string) bool {
	if len(s) > len(t) {
		return false
	}
	i := 0
	j := 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == len(s)
}

525.连续数组(1)¶

题目

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
示例 1:输入: [0,1] 输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:输入: [0,1,0] 输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
注意:给定的二进制数组的长度不会超过50000。

解题思路

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

func findMaxLength(nums []int) int {
   res := 0
   m := make(map[int]int)
   m[0] = -1
   total := 0
   for i := 0; i < len(nums); i++ {
   	if nums[i] == 0 {
   		total--
   	} else {
   		total++
   	}
   	if first, ok := m[total]; !ok {
   		m[total] = i
   	} else {
   		if i-first > res {
   			res = i - first
   		}
   	}
   }
   return res
}

526.优美的排列(2)¶

题目

假设有从 1 到 N 的N个整数，如果从这N个数字中成功构造出一个数组，
使得数组的第 i位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
第i位的数字能被i整除
i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？
示例1:输入: 2 输出: 2
解释: 
第 1 个优美的排列是 [1, 2]:
  第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
  第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除
第 2 个优美的排列是 [2, 1]:
  第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
  第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除
说明:N 是一个正整数，并且不会超过15。

解题思路

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

var res [][]int

func countArrangement(n int) int {
	res = make([][]int, 0)
	dfs(n, make([]int, 0), make([]bool, n+1))
	fmt.Println(res)
	return len(res)
}

func dfs(n int, path []int, visited []bool) {
	if len(path) == n {
		temp := make([]int, len(path))
		copy(temp, path)
		res = append(res, temp)
		return
	}
	for i := 1; i <= n; i++ {
		index := len(path) + 1
		if visited[i] == false && (i%index == 0 || index%i == 0) {
			visited[i] = true
			dfs(n, append(path, i), visited)
			visited[i] = false
		}
	}
}

# 2
var res int

func countArrangement(n int) int {
	res = 0
	dfs(n, make([]int, 0), make([]bool, n+1))
	return res
}

func dfs(n int, path []int, visited []bool) {
	if len(path) == n {
		res++
		return
	}
	for i := 1; i <= n; i++ {
		index := len(path) + 1
		if visited[i] == false && (i%index == 0 || index%i == 0) {
			visited[i] = true
			dfs(n, append(path, i), visited)
			visited[i] = false
		}
	}
}

528.按权重随机选择(1)¶

题目

给定一个正整数数组w ，其中w[i]代表下标 i的权重（下标从 0 开始），
请写一个函数pickIndex，它可以随机地获取下标 i，选取下标 i的概率与w[i]成正比。
例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3)= 0.25 （即，25%），
而选取下标 1 的概率为 3 / (1 + 3)= 0.75（即，75%）。
也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
示例 1：输入：["Solution","pickIndex"] [[[1]],[]]输出： [null,0]
解释：Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
示例 2：输入： ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] 
[[[1,3]],[],[],[],[],[]]
输出：[null,1,1,1,1,0]
解释：Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。
提示：1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex将被调用不超过10000次

解题思路

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

type Solution struct {
	nums  []int
	total int
}

func Constructor(w []int) Solution {
	total := 0
	arr := make([]int, len(w)) // 前缀和
	for i := 0; i < len(w); i++ {
		total = total + w[i]
		arr[i] = total
	}
	return Solution{
		nums:  arr,
		total: total,
	}
}

func (this *Solution) PickIndex() 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
		}
	}
	return left
}

529.扫雷游戏(2)¶

题目

让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，
'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，
数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，
返回相应位置被点击后对应的面板：
    如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
    如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），
    并且所有和其相邻的未挖出方块都应该被递归地揭露。
    如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
    如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例 1：输入: [['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
输出: [['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
解释:示例 2：输入: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
输出: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]
解释:
注意：输入矩阵的宽和高的范围为 [1,50]。
    点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。
    输入面板不会是游戏结束的状态（即有地雷已被挖出）。
    简单起见，未提及的规则在这个问题中可被忽略。
    例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。

解题思路

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

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

func updateBoard(board [][]byte, click []int) [][]byte {
	x, y := click[0], click[1]
	if board[x][y] == 'M' {
		board[x][y] = 'X'
	} else {
		dfs(board, x, y)
	}
	return board
}

func dfs(board [][]byte, x, y int) {
	count := 0
	for i := 0; i < 8; i++ {
		newX := dx[i] + x
		newY := dy[i] + y
		if newX < 0 || newX >= len(board) || newY < 0 || newY >= len(board[0]) {
			continue
		}
		if board[newX][newY] == 'M' {
			count++
		}
	}
	if count > 0 {
		board[x][y] = byte(count + '0')
	} else {
		board[x][y] = 'B'
		for i := 0; i < 8; i++ {
			newX := dx[i] + x
			newY := dy[i] + y
			if newX < 0 || newX >= len(board) ||
				newY < 0 || newY >= len(board[0]) ||
				board[newX][newY] != 'E' {
				continue
			}
			dfs(board, newX, newY)
		}
	}
}

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

func updateBoard(board [][]byte, click []int) [][]byte {
	x, y := click[0], click[1]
	if board[x][y] == 'M' {
		board[x][y] = 'X'
	} else {
		bfs(board, x, y)
	}
	return board
}

func bfs(board [][]byte, x, y int) {
	visited := make([][]bool, len(board))
	for i := 0; i < len(board); i++ {
		visited[i] = make([]bool, len(board[i]))
	}
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{x, y})
	visited[x][y] = true
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		count := 0
		a := node[0]
		b := node[1]
		for j := 0; j < 8; j++ {
			newX := dx[j] + a
			newY := dy[j] + b
			if newX < 0 || newX >= len(board) ||
				newY < 0 || newY >= len(board[0]) ||
				visited[newX][newY] == true {
				continue
			}
			if board[newX][newY] == 'M' {
				count++
			}
		}
		if count > 0 {
			board[a][b] = byte(count + '0')
		} else {
			board[a][b] = 'B'
			for j := 0; j < 8; j++ {
				newX := dx[j] + a
				newY := dy[j] + b
				if newX < 0 || newX >= len(board) ||
					newY < 0 || newY >= len(board[0]) ||
					board[newX][newY] != 'E' ||
					visited[newX][newY] == true {
					continue
				}
				queue = append(queue, [2]int{newX, newY})
				visited[newX][newY] = true
			}
		}
	}
}

537.复数乘法(2)¶

题目

给定两个表示复数的字符串。
返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。
示例 1:输入: "1+1i", "1+1i" 输出: "0+2i"
解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。
示例 2:输入: "1+-1i", "1+-1i" 输出: "0+-2i"
解释: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。 
注意:输入字符串不包含额外的空格。
输入字符串将以a+bi 的形式给出，其中整数 a 和 b 的范围均在 [-100, 100] 之间。输出也应当符合这种形式。

解题思路

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

func complexNumberMultiply(a string, b string) string {
	a1, a2 := getValue(a)
	b1, b2 := getValue(b)
	return fmt.Sprintf("%d+%di", a1*b1-a2*b2, a1*b2+a2*b1)
}

func getValue(str string) (a, b int) {
	arr := strings.Split(str, "+")
	a, _ = strconv.Atoi(arr[0])
	b, _ = strconv.Atoi(arr[1][:len(arr[1])-1])
	return a, b
}

# 2
func complexNumberMultiply(a string, b string) string {
	var a1, a2, b1, b2 int
	fmt.Sscanf(a, "%d+%di", &a1, &a2)
	fmt.Sscanf(b, "%d+%di", &b1, &b2)
	return fmt.Sprintf("%d+%di", a1*b1-a2*b2, a1*b2+a2*b1)
}

539.最小时间差(2)¶

题目

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1：输入：timePoints = ["23:59","00:00"] 输出：1
示例 2：输入：timePoints = ["00:00","23:59","00:00"]输出：0
提示：2 <= timePoints <= 2 * 104
timePoints[i] 格式为 "HH:MM"

解题思路

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

func findMinDifference(timePoints []string) int {
	m := make(map[int]bool)
	for i := 0; i < len(timePoints); i++ {
		value := getValue(timePoints[i])
		if _, ok := m[value]; ok {
			return 0
		}
		m[value] = true
	}
	arr := make([]int, 0)
	for k := range m {
		arr = append(arr, k)
	}
	sort.Ints(arr)
	res := math.MaxInt32
	arr = append(arr, arr[0]+1440)
	for i := 1; i < len(arr); i++ {
		if res > arr[i]-arr[i-1] {
			res = arr[i] - arr[i-1]
		}
	}
	return res
}

func getValue(str string) int {
	hour, _ := strconv.Atoi(str[:2])
	minute, _ := strconv.Atoi(str[3:])
	return hour*60 + minute
}

# 2
func findMinDifference(timePoints []string) int {
	arr := make([]int, 0)
	for i := 0; i < len(timePoints); i++ {
		value := getValue(timePoints[i])
		arr = append(arr, value)
	}
	sort.Ints(arr)
	res := math.MaxInt32
	arr = append(arr, arr[0]+1440)
	for i := 1; i < len(arr); i++ {
		if res > arr[i]-arr[i-1] {
			res = arr[i] - arr[i-1]
		}
	}
	return res
}

func getValue(str string) int {
	hour, _ := strconv.Atoi(str[:2])
	minute, _ := strconv.Atoi(str[3:])
	return hour*60 + minute
}

540.有序数组中的单一元素(3)¶

题目

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:输入: [1,1,2,3,3,4,4,8,8]输出: 2
示例 2:输入: [3,3,7,7,10,11,11]输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

解题思路

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

func singleNonDuplicate(nums []int) int {
	for i := 0; i < len(nums)-1; i = i + 2 {
		if nums[i] != nums[i+1] {
			return nums[i]
		}
	}
	return nums[len(nums)-1]
}

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

# 3
func singleNonDuplicate(nums []int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		res = res ^ nums[i]
	}
	return res
}

542.01矩阵(3)¶

题目

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1: 输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2: 输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
    给定矩阵的元素个数不超过 10000。
    给定矩阵中至少有一个元素是 0。
    矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解题思路

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

func updateMatrix(matrix [][]int) [][]int {
	n := len(matrix)
	m := len(matrix[0])
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			if matrix[i][j] == 1 {
				dp[i][j] = math.MaxInt32 / 10
				if i > 0 {
					dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
				}
				if j > 0 {
					dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
				}
			} else {
				dp[i][j] = 0
			}
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if dp[i][j] > 1 {
				if i < n-1 {
					dp[i][j] = min(dp[i][j], dp[i+1][j]+1)
				}
				if j < m-1 {
					dp[i][j] = min(dp[i][j], dp[i][j+1]+1)
				}
			}
		}
	}
	return dp
}

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

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

func updateMatrix(matrix [][]int) [][]int {
	n := len(matrix)
	m := len(matrix[0])
	queue := make([][2]int, 0)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if matrix[i][j] == 0 {
				queue = append(queue, [2]int{i, j})
			} else {
				matrix[i][j] = -1
			}
		}
	}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		for i := 0; i < 4; i++ {
			x := node[0] + dx[i]
			y := node[1] + dy[i]
			if 0 <= x && x < n && 0 <= y && y < m && matrix[x][y] == -1 {
				matrix[x][y] = matrix[node[0]][node[1]] + 1
				queue = append(queue, [2]int{x, y})
			}
		}
	}
	return matrix
}

# 3
func updateMatrix(matrix [][]int) [][]int {
	n := len(matrix)
	m := len(matrix[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if matrix[i][j] == 1 {
				matrix[i][j] = math.MaxInt32 / 10
				if i > 0 {
					matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1)
				}
				if j > 0 {
					matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1)
				}
			} else {
				matrix[i][j] = 0
			}
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if matrix[i][j] > 1 {
				if i < n-1 {
					matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1)
				}
				if j < m-1 {
					matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1)
				}
			}
		}
	}
	return matrix
}

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

547.省份数量(3)¶

题目

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]输出：2
示例 2：输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3
提示：1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

解题思路

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

func findCircleNum(M [][]int) int {
	n := len(M)
	fa = Init(n)
	count = n
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if M[i][j] == 1 {
				union(i, j)
			}
		}
	}
	return getCount()
}

var fa []int
var count int

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

// 查询
func find(x int) int {
	if fa[x] == x {
		return x
	}
	// 路径压缩
	fa[x] = find(fa[x])
	return fa[x]
}

// 合并
func union(i, j int) {
	x, y := find(i), find(j)
	if x != y {
		fa[x] = y
		count--
	}
}

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

func getCount() int {
	return count
}

# 2
var arr []bool

func findCircleNum(M [][]int) int {
	n := len(M)
	arr = make([]bool, n)
	res := 0
	for i := 0; i < n; i++ {
		if arr[i] == false {
			dfs(M, i)
			res++
		}
	}
	return res
}

func dfs(M [][]int, index int) {
	for i := 0; i < len(M); i++ {
		if arr[i] == false && M[index][i] == 1 {
			arr[i] = true
			dfs(M, i)
		}
	}
}

# 3
func findCircleNum(M [][]int) int {
	n := len(M)
	arr := make([]bool, n)
	res := 0
	queue := make([]int, 0)
	for i := 0; i < n; i++ {
		if arr[i] == false {
			queue = append(queue, i)
			for len(queue) > 0 {
				node := queue[0]
				queue = queue[1:]
				arr[node] = true
				for j := 0; j < n; j++ {
					if M[node][j] == 1 && arr[j] == false {
						queue = append(queue, j)
					}
				}
			}
			res++
		}
	}
	return res
}

553.最优除法(1)¶

题目

给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如，[2,3,4] -> 2 / 3 / 4 。
但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。
你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。
示例：输入: [1000,100,10,2] 输出: "1000/(100/10/2)"
解释:1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。
其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
说明:输入数组的长度在 [1, 10] 之间。
数组中每个元素的大小都在 [2, 1000] 之间。
每个测试用例只有一个最优除法解。

解题思路

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

func optimalDivision(nums []int) string {
	res := make([]string,0)
	for i := 0; i < len(nums); i++{
		res = append(res, strconv.Itoa(nums[i]))
	}
	if len(res) < 3{
		return strings.Join(res, "/")
	}
	return res[0]+"/("+strings.Join(res[1:],"/") + ")"
}

554.砖墙(1)¶

题目

你的面前有一堵矩形的、由多行砖块组成的砖墙。这些砖块高度相同但是宽度不同。
你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。
你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
示例：输入: [[1,2,2,1],
      [3,1,2],
      [1,3,2],
      [2,4],
      [3,1,2],
      [1,3,1,1]]
输出: 2
解释: 提示：每一行砖块的宽度之和应该相等，并且不能超过 INT_MAX。
每一行砖块的数量在[1,10,000] 范围内，墙的高度在[1,10,000] 范围内，总的砖块数量不超过 20,000。

解题思路

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

func leastBricks(wall [][]int) int {
	maxCount := 0
	m := make(map[int]int)
	for i := 0; i < len(wall); i++ {
		index := 0
		for j := 0; j < len(wall[i])-1; j++ {
			index = index + wall[i][j]
            m[index]++ // 保留去除开头和结尾的位置(空隙地方)
			if maxCount <= m[index] {
				maxCount = m[index]
			}
		}
	}
	return len(wall) - maxCount
}

556.下一个更大元素III(2)¶

题目

给你一个正整数n ，请你找出符合条件的最小整数，其由重新排列 n中存在的每位数字组成，并且其值大于 n 。
如果不存在这样的正整数，则返回 -1 。
注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。
示例 1：输入：n = 12 输出：21
示例 2：输入：n = 21 输出：-1
提示：1 <= n <= 231 - 1

解题思路

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

func nextGreaterElement(n int) int {
	arr := make([]int, 0)
	for n > 0 {
		arr = append(arr, n%10)
		n = n / 10
	}
	reverse(arr, 0, len(arr)-1)
	arr = nextPermutation(arr)
	if arr == nil {
		return -1
	}
	res := 0
	for i := 0; i < len(arr); i++ {
		res = res*10 + arr[i]
		if res > math.MaxInt32 {
			return -1
		}
	}
	return res
}

// leetcode31.下一个排列
func nextPermutation(nums []int) []int {
	n := len(nums)
	left := n - 2
	// 以12385764为例，从后往前找到5<7 的升序情况，目标值为左边的数5
	for left >= 0 && nums[left] >= nums[left+1] {
		left--
	}
	if left >= 0 { // 存在升序的情况
		right := n - 1
		// 从后往前，找到第一个大于目标值的数，如6>5，然后交换
		for right >= 0 && nums[right] <= nums[left] {
			right--
		}
		nums[left], nums[right] = nums[right], nums[left]
	} else {
		return nil
	}
	reverse(nums, left+1, n-1)
	return nums
}

func reverse(nums []int, left, right int) {
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

# 2
func nextGreaterElement(n int) int {
	nums := []byte(strconv.Itoa(n))
	length := len(nums)
	left := length - 2
	// 以12385764为例，从后往前找到5<7 的升序情况，目标值为左边的数5
	for left >= 0 && nums[left] >= nums[left+1] {
		left--
	}
	if left >= 0 { // 存在升序的情况
		right := length - 1
		// 从后往前，找到第一个大于目标值的数，如6>5，然后交换
		for right >= 0 && nums[right] <= nums[left] {
			right--
		}
		nums[left], nums[right] = nums[right], nums[left]
	} else {
		return -1
	}
	left = left + 1
	right := length - 1
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
	res, _ := strconv.Atoi(string(nums))
	if res > math.MaxInt32 {
		return -1
	}
	return res
}

558.四叉树交集(1)¶

题目

二进制矩阵中的所有元素不是 0 就是 1 。
给你两个四叉树，quadTree1 和 quadTree2。其中 quadTree1 表示一个 n * n 二进制矩阵，
而 quadTree2 表示另一个 n * n 二进制矩阵。
请你返回一个表示 n * n 二进制矩阵的四叉树，它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。
注意，当 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：输入：quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]], 
quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
输出：[[0,0],[1,1],[1,1],[1,1],[1,0]]
解释：quadTree1 和 quadTree2 如上所示。由四叉树所表示的二进制矩阵也已经给出。
如果我们对这两个矩阵进行按位逻辑或运算，则可以得到下面的二进制矩阵，由一个作为结果的四叉树表示。
注意，我们展示的二进制矩阵仅仅是为了更好地说明题意，你无需构造二进制矩阵来获得结果四叉树。
示例 2：输入：quadTree1 = [[1,0]], quadTree2 = [[1,0]] 输出：[[1,0]]
解释：两个数所表示的矩阵大小都为 1*1，值全为 0 
结果矩阵大小为 1*1，值全为 0 。
示例 3：输入：quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]] , quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]
输出：[[1,1]]
示例 4：输入：quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]],
quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
输出：[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
示例 5：输入：quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]], 
quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]
输出：[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]
提示：quadTree1 和 quadTree2 都是符合题目要求的四叉树，每个都代表一个 n * n 的矩阵。
n == 2^x ，其中 0 <= x <= 9.

解题思路

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

func intersect(quadTree1 *Node, quadTree2 *Node) *Node {
	res := &Node{}
	if quadTree1.IsLeaf == true { // 叶子节点
		if quadTree1.Val == true {
			return quadTree1
		}
		return quadTree2
	}
	if quadTree2.IsLeaf == true { // 叶子节点
		if quadTree2.Val == true {
			return quadTree2
		}
		return quadTree1
	}
	tL := intersect(quadTree1.TopLeft, quadTree2.TopLeft)
	tR := intersect(quadTree1.TopRight, quadTree2.TopRight)
	bL := intersect(quadTree1.BottomLeft, quadTree2.BottomLeft)
	bR := intersect(quadTree1.BottomRight, quadTree2.BottomRight)
	// 叶子节点判断
	if tL.IsLeaf == true && tR.IsLeaf == true && bL.IsLeaf == true && bR.IsLeaf == true &&
		tL.Val == tR.Val && tR.Val == bL.Val && bL.Val == bR.Val {
		res.IsLeaf = true
		res.Val = tL.Val // 4个值都相同
		return res
	}
	res.TopLeft = tL
	res.TopRight = tR
	res.BottomLeft = bL
	res.BottomRight = bR
	res.Val = false
	res.IsLeaf = false
	return res
}

560.和为K的子数组(4)¶

题目

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明:数组的长度为 [1, 20,000]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(1)
02	前缀和-遍历	O(n^2)	O(n)
03	前缀和-哈希辅助	O(n)	O(n)
04	前缀和-哈希辅助	O(n)	O(n)

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

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

# 3
func subarraySum(nums []int, k int) int {
	res := 0
	m := make(map[int]int)
	m[0] = 1 // 保证第一个k的存在
	sum := 0
	// sum[i:j]= sum[0:j]-sum[0:i]，把sum[i:j]设为k，
	// 于是可以转化为sum[0:j]-k=sum[0:i]
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
		if _, ok := m[sum-k]; ok {
			res = res + m[sum-k]
		}
		m[sum]++
	}
	return res
}

# 4
func subarraySum(nums []int, k int) int {
	res := 0
	m := make(map[int][]int)
	m[0] = []int{-1} // 保证第一个k的存在
	sum := 0
	// sum[i:j]= sum[0:j]-sum[0:i]，把sum[i:j]设为k，
	// 于是可以转化为sum[0:j]-k=sum[0:i]
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
		if _, ok := m[sum-k]; ok {
			res = res + len(m[sum-k])
            // 输出满足条件的子数组下标
			// for _, v := range m[sum-k] {
			//	fmt.Println(v+1, i)
			// }
		}
		m[sum] = append(m[sum], i)
	}
	return res
}

565.数组嵌套(4)¶

题目

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，
其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，
之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例1:输入: A = [5,4,0,3,1,6,2] 输出: 4
解释:  A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
提示：N是[1, 20,000]之间的整数。
A中不含有重复的元素。
A中的元素大小在[0, N-1]之间。

解题思路

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

func arrayNesting(nums []int) int {
	m := make(map[int]bool)
	res := 0
	for i := 0; i < len(nums); i++ {
		if m[nums[i]] == true {
			continue
		}
		count := 0
		cur := i
		for {
			count++
			m[cur] = true
			cur = nums[cur]
			if cur == i {
				break
			}
		}
		if count > res {
			res = count
		}
	}
	return res
}

# 2
func arrayNesting(nums []int) int {
	m := make(map[int]bool)
	res := 0
	for i := 0; i < len(nums); i++ {
		if m[nums[i]] == true {
			continue
		}
		count := 0
		cur := i
		for {
			count++
			m[cur] = true
			cur = nums[cur]
			if m[cur] == true {
				break
			}
		}
		if count > res {
			res = count
		}
	}
	return res
}

# 3
func arrayNesting(nums []int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		count := 1
		for nums[i] != i {
			count++
			nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
		}
		if count > res {
			res = count
		}
	}
	return res
}

# 4
func arrayNesting(nums []int) int {
	res := 0
	fa = Init(len(nums))
	for i := 0; i < len(nums); i++ {
		union(i, nums[i])
	}
	m := make(map[int]int)
	for i := 0; i < len(fa); i++ {
		m[find(i)]++
	}
	for _, v := range m {
		if v > res {
			res = v
		}
	}
	return res
}

var fa []int

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

// 查询
func find(x int) int {
	if fa[x] == x {
		return x
	}
	// 路径压缩
	fa[x] = find(fa[x])
	return fa[x]
}

// 合并
func union(i, j int) {
	x, y := find(i), find(j)
	if x != y {
		fa[x] = y
	}
}

567.字符串的排列(2)¶

题目

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:输入: s1 = "ab" s2 = "eidbaooo" 输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:输入: s1= "ab" s2 = "eidboaoo" 输出: False
注意：输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

解题思路

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

func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}
	arr1, arr2 := [26]int{}, [26]int{}
	for i := 0; i < len(s1); i++ {
		arr1[s1[i]-'a']++
		arr2[s2[i]-'a']++
	}
	for i := 0; i < len(s2)-len(s1); i++ {
		if arr1 == arr2 {
			return true
		}
		arr2[s2[i]-'a']--
		arr2[s2[i+len(s1)]-'a']++
	}
	return arr1 == arr2
}

# 2
func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}
	m1, m2 := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(s1); i++ {
		m1[s1[i]-'a']++
		m2[s2[i]-'a']++
	}
	for i := 0; i < len(s2)-len(s1); i++ {
		if compare(m1, m2) {
			return true
		}
		m2[s2[i]-'a']--
		if m2[s2[i]-'a'] == 0 {
			delete(m2, s2[i]-'a')
		}
		m2[s2[i+len(s1)]-'a']++
	}
	return compare(m1, m2)
}

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
}

576.出界的路径数(2)¶

题目

给定一个 m × n 的网格和一个球。球的起始坐标为(i,j)，你可以将球移到相邻的单元格内，
或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动N次。
找出可以将球移出边界的路径数量。答案可能非常大，返回 结果 mod 109+ 7 的值。
示例 1：输入: m = 2, n = 2, N = 2, i = 0, j = 0 输出: 6
解释:
示例 2：输入: m = 1, n = 3, N = 3, i = 0, j = 1 输出: 12
解释:
说明:球一旦出界，就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。

解题思路

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

var dp [60][60][60]int
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
var mod = 1000000007

func findPaths(m int, n int, N int, i int, j int) int {
	dp = [60][60][60]int{}
	for i := 0; i < 60; i++ {
		for j := 0; j < 60; j++ {
			for k := 0; k < 60; k++ {
				dp[i][j][k] = -1
			}
		}
	}
	return dfs(m, n, i+1, j+1, N) // 下标取正
}

func dfs(m, n, i, j, k int) int {
	if k < 0 { // 次数够了
		return 0
	}
	if i < 1 || i > m || j < 1 || j > n { // 出界次数+1
		return 1
	}
	if dp[i][j][k] != -1 {
		return dp[i][j][k]
	}
	dp[i][j][k] = 0
	for a := 0; a < 4; a++ { // 上下左右4个方向
		x := i + dx[a]
		y := j + dy[a]
		dp[i][j][k] = (dp[i][j][k] + dfs(m, n, x, y, k-1)) % mod
	}
	return dp[i][j][k]
}

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

func findPaths(m int, n int, N int, i int, j int) int {
	dp := [60][60][60]int{}
	for k := 1; k <= N; k++ {
		for a := 0; a < m; a++ {
			for b := 0; b < n; b++ {
				for i := 0; i < 4; i++ {
					x := a + dx[i]
					y := b + dy[i]
					if x < 0 || x >= m || y < 0 || y >= n { // 出界次数+1
						dp[a][b][k]++
					} else {
						dp[a][b][k] = (dp[a][b][k] + dp[x][y][k-1]) % mod
					}
				}
			}
		}
	}
	return dp[i][j][N] % mod
}

583.两个字符串的删除操作(3)¶

题目

给定两个单词word1和word2，找到使得word1和word2相同所需的最小步数，
每步可以删除任意一个字符串中的一个字符。
示例：输入: "sea", "eat" 输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
提示：给定单词的长度不超过500。
给定单词中的字符只含有小写字母。

解题思路

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

func minDistance(word1 string, word2 string) int {
	a, b := len(word1), len(word2)
	// 最长公共子序列
	dp := make([][]int, a+1)
	for i := 0; i <= a; i++ {
		dp[i] = make([]int, b+1)
	}
	for i := 1; i <= a; i++ {
		for j := 1; j <= b; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			}
		}
	}
	return a + b - 2*dp[a][b]
}

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

# 2
func minDistance(word1 string, word2 string) int {
	a, b := len(word1), len(word2)
	dp := make([][]int, a+1)
	for i := 0; i <= a; i++ {
		dp[i] = make([]int, b+1)
		dp[i][0] = i
	}
	for i := 0; i <= b; i++ {
		dp[0][i] = i
	}
	for i := 1; i <= a; i++ {
		for j := 1; j <= b; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1
			}
		}
	}
	return dp[a][b]
}

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

# 3
var m [][]int

func minDistance(word1 string, word2 string) int {
	a, b := len(word1), len(word2)
	m = make([][]int, a+1)
	for i := 0; i <= a; i++ {
		m[i] = make([]int, b+1)
		for j := 0; j <= b; j++ {
			m[i][j] = -1
		}
	}
	total := dfs(word1, word2, 0, 0)
	return a + b - 2*total
}

func dfs(word1 string, word2 string, i, j int) int {
	if len(word1) == i || len(word2) == j {
		return 0
	}
	if m[i][j] > -1 {
		return m[i][j]
	}
	if word1[i] == word2[j] {
		m[i][j] = dfs(word1, word2, i+1, j+1) + 1
	} else {
		m[i][j] = max(dfs(word1, word2, i, j+1), dfs(word1, word2, i+1, j))
	}
	return m[i][j]
}

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

592.分数加减运算(1)¶

题目

给定一个表示分数加减运算表达式的字符串，你需要返回一个字符串形式的计算结果。这个结果应该是不可约分的分数，即最简分数。
如果最终结果是一个整数，例如2，你需要将它转换成分数形式，其分母为1。所以在上述例子中, 2应该被转换为2/1。
示例1:输入:"-1/2+1/2" 输出: "0/1"
示例 2:输入:"-1/2+1/2+1/3" 输出: "1/3"
示例 3:输入:"1/3-1/2" 输出: "-1/6"
示例 4:输入:"5/3+1/3" 输出: "2/1"
说明:输入和输出字符串只包含'0' 到'9'的数字，以及'/', '+' 和'-'。
输入和输出分数格式均为±分子/分母。如果输入的第一个分数或者输出的分数是正数，则'+'会被省略掉。
输入只包含合法的最简分数，每个分数的分子与分母的范围是[1,10]。如果分母是1，意味着这个分数实际上是一个整数。
输入的分数个数范围是 [1,10]。
最终结果的分子与分母保证是 32 位整数范围内的有效整数。

解题思路

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

func fractionAddition(expression string) string {
	s := strings.ReplaceAll(expression, "-", "+-") // 替换-为+-
	s = strings.ReplaceAll(s, "/", "+")            // 替换/为+
	temp := strings.Split(s, "+")                  // 根据+切割
	arr := make([]int, 0)
	for i := 0; i < len(temp); i++ {
		if temp[i] == "" { // 第一个数的分子如果为负数，+切割会为空
			continue
		}
		value, _ := strconv.Atoi(temp[i])
		arr = append(arr, value)
	}
	a, b := 0, 1
	for i := 0; i < len(arr); i = i + 2 { // 遍历每个数：分子+分母
		c, d := arr[i], arr[i+1]
		// a/b+c/d=ad/bd+bc/bd=(ad+bc)/bd
		a = a*d + b*c
		b = b * d
		g := gcd(a, b)
		if g < 0 { // 约分为负数，需要转换为正数，这样确保分母一直为正数
			g = -g
		}
		a, b = a/g, b/g
	}
	return fmt.Sprintf("%d/%d", a, b)
}

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

593.有效的正方形(2)¶

题目

给定二维空间中四点的坐标，返回四点是否可以构造一个正方形。
一个点的坐标（x，y）由一个有两个整数的整数数组表示。
示例:输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] 输出: True
注意:所有输入整数都在 [-10000，10000] 范围内。
一个有效的正方形有四个等长的正长和四个等角（90度角）。
输入点没有顺序。

解题思路

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

func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
	m := make(map[int]int)
	m[getDis(p1, p2)]++
	m[getDis(p1, p3)]++
	m[getDis(p1, p4)]++
	m[getDis(p2, p3)]++
	m[getDis(p2, p4)]++
	m[getDis(p3, p4)]++
	a, b := 0, 0
	for k, v := range m {
		if v == 2 {
			a = k
		} else if v == 4 {
			b = k
		} else {
			return false
		}
	}
	return len(m) == 2 && a == 2*b
}

func getDis(a, b []int) int {
	return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
}

# 2
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
	arr := make([]int, 0)
	arr = append(arr, getDis(p1, p2))
	arr = append(arr, getDis(p1, p3))
	arr = append(arr, getDis(p1, p4))
	arr = append(arr, getDis(p2, p3))
	arr = append(arr, getDis(p2, p4))
	arr = append(arr, getDis(p3, p4))
	sort.Ints(arr)
	return arr[0] > 0 && arr[0] == arr[3] && arr[4] == arr[5] && arr[0]*2 == arr[4]
}

func getDis(a, b []int) int {
	return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
}

0501-0600-Hard¶

502.IPO(2)¶

题目

假设 力扣（LeetCode）即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司，
力扣 希望在 IPO 之前开展一些项目以增加其资本。 
由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。
帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。
最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。
示例 1:输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
输出: 4
解释:由于你的初始资本为 0，你尽可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
注意:假设所有输入数字都是非负整数。
    表示利润和资本的数组的长度不超过 50000。
    答案保证在 32 位有符号整数范围内。

解题思路

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

func findMaximizedCapital(k int, W int, Profits []int, Capital []int) int {
	maxProfit := &ProfitNode{}
	minCapital := &CapitalNode{}
	heap.Init(maxProfit)
	heap.Init(minCapital)
	for i := 0; i < len(Profits); i++ {
		heap.Push(minCapital, Node{
			Profits: Profits[i],
			Capital: Capital[i],
		})
	}
	for i := 0; i < k; i++ {
		for minCapital.Len() > 0 {
			node := heap.Pop(minCapital).(Node)
			if node.Capital <= W {
				heap.Push(maxProfit, node)
			} else {
				heap.Push(minCapital, node)
				break
			}
		}
		if maxProfit.Len() == 0 {
			return W
		}
		node := heap.Pop(maxProfit).(Node)
		W = W + node.Profits
	}
	return W
}

type Node struct {
	Profits int
	Capital int
}

type ProfitNode []Node

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

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

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

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

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

type CapitalNode []Node

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

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

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

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

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

# 2
type Node struct {
	profit  int
	capital int
}

func findMaximizedCapital(k int, W int, Profits []int, Capital []int) int {
	arr := make([]Node, 0)
	for i := 0; i < len(Profits); i++ {
		arr = append(arr, Node{
			profit:  Profits[i],
			capital: Capital[i],
		})
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i].profit > arr[j].profit
	})
	index := 0
	for k > 0 {
		if index == len(arr) {
			return W
		}
		// 挑选一个满足条件的项目，利润最大即可
		if arr[index].capital <= W {
			k--
			W = W + arr[index].profit
			arr = append(arr[:index], arr[index+1:]...)
			index = 0
			continue
		}
		index++
	}
	return W
}

514.自由之路(2)¶

题目

电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，
并使用表盘拼写特定关键词才能开门。
给定一个字符串ring，表示刻在外环上的编码；给定另一个字符串key，表示需要拼写的关键词。
您需要算出能够拼写关键词中所有字符的最少步数。
最初，ring的第一个字符与12:00方向对齐。
您需要顺时针或逆时针旋转 ring 以使key的一个字符在 12:00 方向对齐，
然后按下中心按钮，以此逐个拼写完key中的所有字符。
旋转ring拼出 key 字符key[i]的阶段中：
您可以将ring顺时针或逆时针旋转一个位置，计为1步。
旋转的最终目的是将字符串ring的一个字符与 12:00 方向对齐，并且这个字符必须等于字符key[i] 。
如果字符key[i]已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作1 步。
按完之后，您可以开始拼写key的下一个字符（下一阶段）, 直至完成所有拼写。
示例：输入: ring = "godding", key = "gd" 输出: 4
解释: 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。
提示：ring 和key的字符串长度取值范围均为1 至100；
两个字符串中都只有小写字符，并且均可能存在重复字符；
字符串key一定可以由字符串 ring旋转拼出。

解题思路

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

func findRotateSteps(ring string, key string) int {
	maxValue := math.MaxInt32 / 10
	n := len(key)
	m := len(ring)
	dp := make([][]int, n) // dp[i][j] => key[:i+1]，ring[:j+1]的最少步数
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			dp[i][j] = maxValue
		}
	}
	arr := [26][]int{}
	for i := 0; i < len(ring); i++ {
		value := int(ring[i] - 'a')
		arr[value] = append(arr[value], i)
	}
	for _, v := range arr[key[0]-'a'] {
		dp[0][v] = min(v, m-v) + 1 // 移到次数
	}
	for i := 1; i < n; i++ {
		for _, j := range arr[key[i]-'a'] { // 枚举当前字母位置
			for _, k := range arr[key[i-1]-'a'] { // 枚举上一个字母位置
				minValue := min(abs(j-k), m-abs(j-k))
				dp[i][j] = min(dp[i][j], dp[i-1][k]+minValue+1)
			}
		}
	}
	res := math.MaxInt32
	for i := 0; i < m; i++ {
		res = min(res, dp[n-1][i])
	}
	return res
}

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

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

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

func findRotateSteps(ring string, key string) int {
	n := len(key)
	m := len(ring)
	dp = make([][]int, n) // dp[i][j] => key[:i+1]，ring[:j+1]的最少步数
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			dp[i][j] = -1
		}
	}
	arr = [26][]int{}
	for i := 0; i < len(ring); i++ {
		value := int(ring[i] - 'a')
		arr[value] = append(arr[value], i)
	}
	return n + dfs(key, ring, 0, 0)
}

func dfs(key, ring string, keyIndex, ringIndex int) int {
	if keyIndex == len(key) {
		return 0
	}
	if dp[keyIndex][ringIndex] != -1 {
		return dp[keyIndex][ringIndex]
	}
	cur := int(key[keyIndex] - 'a')
	res := math.MaxInt32
	for _, v := range arr[cur] {
		minValue := min(abs(ringIndex-v), len(ring)-abs(ringIndex-v))
		res = min(res, minValue+dfs(key, ring, keyIndex+1, v))
	}
	dp[keyIndex][ringIndex] = res
	return res
}

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

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

517.超级洗衣机(1)¶

题目

假设有 n台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
在每一步操作中，你可以选择任意 m（1 ≤ m ≤ n）台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
给定一个非负整数数组代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数。
如果不能使每台洗衣机中衣物的数量相等，则返回 -1。
示例 1：输入: [1,0,5] 输出: 3
解释: 第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2   
示例 2：输入: [0,3,0] 输出: 2
解释:  第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1     
示例 3:输入: [0,2,0] 输出: -1
解释:  不可能让所有三个洗衣机同时剩下相同数量的衣物。
提示：n 的范围是 [1, 10000]。
在每台超级洗衣机中，衣物数量的范围是 [0, 1e5]。

解题思路

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

func findMinMoves(machines []int) int {
	n := len(machines)
	sum := 0
	for i := 0; i < n; i++ {
		sum = sum + machines[i]
	}
	if sum%n != 0 { // 先判断
		return -1
	}
	per := sum / n // 最终每个洗衣机里面的衣服数
	for i := 0; i < n; i++ {
		machines[i] = machines[i] - per // 计算每个洗衣机需要拿出或者需要放入的衣服数
	}
	maxValue := 0
	curSum := 0
	res := 0
	// 注意：选择任意m台，不要求连续
	// 2种情况：
	// 1、数组的最大值：是取出，每次一件，会有最大值的次数
	// 2、前缀和的最大绝对值：前面多余或者需要的数量
	for i := 0; i < n; i++ {
		curSum = curSum + machines[i]              // 前缀和：需要移动curSum件衣服到当前节点
		maxValue = max(maxValue, abs(curSum))      // 需要移动的最大值
		res = max(res, max(maxValue, machines[i])) // 取：数组的最大值和数组前缀和的绝对值的最大值中的较大值
	}
	return res
}

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

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

535.TinyURL的加密与解密(2)¶

题目

TinyURL是一种URL简化服务， 比如：当你输入一个URLhttps://leetcode.com/problems/design-tinyurl时，
它将返回一个简化的URLhttp://tinyurl.com/4e9iAk.
要求：设计一个 TinyURL 的加密encode和解密decode的方法。
你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，
并且这个TinyURL可以用解密方法恢复成原本的URL。

解题思路

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

type Codec struct {
	m     map[string]string
	index int
}

func Constructor() Codec {
	return Codec{
		m:     make(map[string]string),
		index: 1,
	}
}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
	res := "http://tinyurl.com/" + strconv.Itoa(this.index)
	this.m[res] = longUrl
	this.index++
	return res
}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
	return this.m[shortUrl]
}

# 2
type Codec struct {
	m     map[string]string
	index int
}

func Constructor() Codec {
	return Codec{
		m:     make(map[string]string),
		index: 1,
	}
}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
	str := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	res := "http://tinyurl.com/"
	this.index++
	count := this.index
	temp := make([]byte, 0)
	for count > 0 {
		temp = append(temp, str[count%62])
		count = count / 62
	}
	res = res + string(temp)
	this.m[res] = longUrl
	return res
}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
	return this.m[shortUrl]
}

546.移除盒子¶

题目¶

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。
每一轮你可以移除具有相同颜色的连续 k 个盒子（k>= 1），这样一轮之后你将得到 k * k 个积分。
当你将所有盒子都去掉之后，求你能获得的最大积分和。
示例 1：输入：boxes = [1,3,2,2,2,3,4,3,1] 输出：23
解释：[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)
示例 2：输入：boxes = [1,1,1] 输出：9
示例 3：输入：boxes = [1] 输出：1
提示：1 <= boxes.length <= 100
1 <= boxes[i]<= 100

解题思路¶

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

552.学生出勤记录II(1)¶

题目

给定一个正整数n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。 
答案可能非常大，你只需返回结果mod 109 + 7的值。
学生出勤记录是只包含以下三个字符的字符串：
'A' : Absent，缺勤
'L' : Late，迟到
'P' : Present，到场
如果记录不包含多于一个'A'（缺勤）或超过两个连续的'L'（迟到），则该记录被视为可奖励的。
示例 1:输入: n = 2 输出: 8 
解释：有8个长度为2的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。
注意：n 的值不会超过100000。

解题思路

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

var mod = 1000000007

func checkRecord(n int) int {
	dp := [6]int{}
	dp[0] = 1 // 0A 0L
	dp[1] = 1 // 0A 1L
	dp[2] = 0 // 0A 2L
	dp[3] = 1 // 1A 0L
	dp[4] = 0 // 1A 1L
	dp[5] = 0 // 1A 2L
	for i := 2; i <= n; i++ {
		temp := [6]int{}
		temp[0] = (dp[0] + dp[1] + dp[2]) % mod                         // +P
		temp[1] = dp[0]                                                 // +L
		temp[2] = dp[1]                                                 // +L
		temp[3] = (dp[0] + dp[1] + dp[2] + dp[3] + dp[4] + dp[5]) % mod // 0、1、2+A，3、4、5+P
		temp[4] = dp[3]                                                 // +L
		temp[5] = dp[4]                                                 // +L
		dp = temp
	}
	res := 0
	for i := 0; i < len(dp); i++ {
		res = (res + dp[i]) % 1000000007
	}
	return res
}

600.不含连续1的非负整数(1)¶

题目

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含连续的1的个数。
示例 1:输入: 5 输出: 5
解释: 下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。
说明: 1 <= n <= 109

解题思路

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

func findIntegers(n int) int {
	dp := make(map[int]int) // dp[i]=>高度为i，根节点为0的满二叉树，不包含连续1的路径数量（下标从1开始）
	dp[1] = 1               // 高度为1的时候，只有0等1种情况
	dp[2] = 2               // 高度为2的时候，有00、01等2种情况
	for i := 3; i <= 32; i++ {
		dp[i] = dp[i-1] + dp[i-2] // 左子树(0)+右子树的左子树(10)的数量
	}
	res := 0
	prev := 0
	for i := 32; i >= 1; i-- { // 从最高位开始遍历进行替换（下标从1开始）
		if n&(1<<(i-1)) > 0 { // 第i位为1，替换该位，前缀不变
			// 1xxx1xx => 0xxxxxx => 该位变为0
			// 1xxx1xx => 1xxx0xx => 该位变为0，前缀不变
			res = res + dp[i] // 高度为i：高度=i，根节点为0的都小于n（把i位的1替换为0）
			if prev == 1 {    // 出现连续1退出，比如后面使用1011xx的前缀就不满足题目要求了
				break
			}
			prev = 1
		} else {
			prev = 0
		}
		if i == 1 { // 如果能走到最后1位，也要算上n，说明n也满足条件(小于等于n,即n也算1次)
			res++
		}
	}
	return res
}