1501-1600-Easy

1502.判断能否形成等差数列(2)

  • 题目

给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
示例 1：输入：arr = [3,5,1] 输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：输入：arr = [1,2,4] 输出：false
解释：无法通过重新排序得到等差数列。
提示：
    2 <= arr.length <= 1000
    -10^6 <= arr[i] <= 10^6

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(1)
02 哈希辅助 O(n) O(n) 
func canMakeArithmeticProgression(arr []int) bool {
	sort.Ints(arr)
	diff := arr[1] - arr[0]
	for i := 2; i < len(arr); i++ {
		if arr[i]-arr[i-1] != diff {
			return false
		}
	}
	return true
}

#
func canMakeArithmeticProgression(arr []int) bool {
	min, max := arr[0], arr[0]
	m := make(map[int]bool)
	for i := 0; i < len(arr); i++ {
		if arr[i] <= min {
			min = arr[i]
		}
		if arr[i] >= max {
			max = arr[i]
		}
		m[arr[i]] = true
	}
	diff := (max - min) / (len(arr) - 1)
	for i := 0; i < len(m); i++ {
		value := min + diff*i
		if _, ok := m[value]; !ok {
			return false
		}
	}
	return true
}

1507.转变日期格式(1)

  • 题目

给你一个字符串 date ，它的格式为 Day Month Year ，其中：
    Day 是集合 {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"} 中的一个元素。
    Month 是集合 {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", 
    "Aug", "Sep", "Oct", "Nov", "Dec"} 中的一个元素。
    Year 的范围在 [1900, 2100] 之间。
请你将字符串转变为 YYYY-MM-DD 的格式，其中：
    YYYY 表示 4 位的年份。
    MM 表示 2 位的月份。
    DD 表示 2 位的天数。
示例 1：输入：date = "20th Oct 2052" 输出："2052-10-20"
示例 2：输入：date = "6th Jun 1933" 输出："1933-06-06"
示例 3：输入：date = "26th May 1960" 输出："1960-05-26"
提示： 给定日期保证是合法的，所以不需要处理异常输入。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历-内置函数 O(n) O(n) 
func reformatDate(date string) string {
	month := []string{"", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}
	arr := strings.Split(date, " ")
	res := arr[2] + "-"
	for i := 1; i < len(month); i++ {
		if month[i] == arr[1] {
			res = res + fmt.Sprintf("%02d", i) + "-"
		}
	}
	/*
		if arr[0][1] >= '0' && arr[0][1] <= '9' {
			res = res + arr[0][:2]
		} else {
			res = res + "0" + arr[0][:1]
		}
	*/
	if len(arr[0]) == 3 {
		res = res + "0" + arr[0][:1]
	} else {
		res = res + arr[0][:2]
	}
	return res
}

1512.好数对的数目(3)

  • 题目

给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：输入：nums = [1,2,3,1,1,3] 输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：输入：nums = [1,1,1,1] 输出：6
解释：数组中的每组数字都是好数对
示例 3：输入：nums = [1,2,3] 输出：0
提示：
    1 <= nums.length <= 100
    1 <= nums[i] <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(1)
02 数组辅助 O(n) O(1)
03 哈希辅助 O(n) O(1) 
func numIdenticalPairs(nums []int) int {
	res := 0
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] == nums[j] {
				res++
			}
		}
	}
	return res
}

#
func numIdenticalPairs(nums []int) int {
	res := 0
	arr := make([]int, 101)
	for i := 0; i < len(nums); i++ {
		res = res + arr[nums[i]]
		arr[nums[i]]++
	}
	return res
}

#
func numIdenticalPairs(nums []int) int {
	res := 0
	m := make(map[int]int, 101)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	for _, v := range m {
		if v > 0 {
			res = res + v*(v-1)/2
		}
	}
	return res
}

1518.换酒问题(2)

  • 题目

小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。
请你计算 最多 能喝到多少瓶酒。
示例 1：输入：numBottles = 9, numExchange = 3 输出：13
解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
示例 2：输入：numBottles = 15, numExchange = 4 输出：19
解释：你可以用 4 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 15 + 3 + 1 = 19 瓶酒。
示例 3：输入：numBottles = 5, numExchange = 5 输出：6
示例 4：输入：numBottles = 2, numExchange = 3 输出：2
提示：
    1 <= numBottles <= 100
    2 <= numExchange <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(log(n)) O(1)
02 计算 O(1) O(1) 
func numWaterBottles(numBottles int, numExchange int) int {
	res := numBottles
	for numBottles > 0 {
		times := numBottles / numExchange
		res = res + times
		numBottles = numBottles%numExchange + times
		if numBottles < numExchange {
			break
		}
	}
	return res
}

#
func numWaterBottles(numBottles int, numExchange int) int {
	return numBottles + (numBottles-1)/(numExchange-1)
}

1523.在区间范围内统计奇数数目(2)

  • 题目

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。
示例 1：输入：low = 3, high = 7 输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。
示例 2：输入：low = 8, high = 10输出：1
解释：8 到 10 之间奇数数字为 [9] 。
提示：0 <= low <= high <= 10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数学 O(1) O(1)
02 数学 O(1) O(1) 
func countOdds(low int, high int) int {
	if low%2 == 1 {
		low = low - 1
	}
	if high%2 == 1 {
		high = high + 1
	}
	return (high - low) / 2
}

#
func countOdds(low int, high int) int {
	if low%2 == 0 && high%2 == 0 {
		return (high - low) / 2
	}
	return (high-low)/2 + 1
}

1528.重新排列字符串(1)

  • 题目

给你一个字符串 s 和一个 长度相同 的整数数组 indices 。
请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。
返回重新排列后的字符串。
示例 1：输入：s = "codeleet", indices = [4,5,6,7,0,2,1,3] 输出："leetcode"
解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。
示例 2：输入：s = "abc", indices = [0,1,2] 输出："abc"
解释：重新排列后，每个字符都还留在原来的位置上。
示例 3：输入：s = "aiohn", indices = [3,1,4,2,0] 输出："nihao"
示例 4：输入：s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]输出："arigatou"
示例 5：输入：s = "art", indices = [1,0,2] 输出："rat"
提示：
    s.length == indices.length == n
    1 <= n <= 100
    s 仅包含小写英文字母。
    0 <= indices[i] < n
    indices 的所有的值都是唯一的（也就是说，indices 是整数 0 到 n - 1 形成的一组排列）。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n) 
func restoreString(s string, indices []int) string {
	arr := []byte(s)
	res := make([]byte, len(s))
	for i := 0; i < len(indices); i++ {
		res[indices[i]] = arr[i]
	}
	return string(res)
}

1534.统计好三元组(2)

  • 题目

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。
如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。
    0 <= i < j < k < arr.length
    |arr[i] - arr[j]| <= a
    |arr[j] - arr[k]| <= b
    |arr[i] - arr[k]| <= c
其中 |x| 表示 x 的绝对值。
返回 好三元组的数量 。
示例 1：输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3 输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。
示例 2：输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1 输出：0
解释：不存在满足所有条件的三元组。
提示：
    3 <= arr.length <= 100
    0 <= arr[i] <= 1000
    0 <= a, b, c <= 1000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^3) O(1)
02 遍历 O(n^3) O(1) 
func countGoodTriplets(arr []int, a int, b int, c int) int {
	res := 0
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			for k := j + 1; k < len(arr); k++ {
				if abs(arr[i], arr[j]) <= a &&
					abs(arr[j], arr[k]) <= b &&
					abs(arr[i], arr[k]) <= c {
					res++
				}
			}
		}
	}
	return res
}

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

#
func countGoodTriplets(arr []int, a int, b int, c int) int {
	res := 0
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			if abs(arr[i], arr[j]) > a {
				continue
			}
			for k := j + 1; k < len(arr); k++ {
				if abs(arr[j], arr[k]) <= b &&
					abs(arr[i], arr[k]) <= c {
					res++
				}
			}
		}
	}
	return res
}

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

1539.第k个缺失的正整数(3)

  • 题目

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。
示例 1：输入：arr = [2,3,4,7,11], k = 5 输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。
示例 2：输入：arr = [1,2,3,4], k = 2 输出：6
解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。
提示：1 <= arr.length <= 1000
    1 <= arr[i] <= 1000
    1 <= k <= 1000
    对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1)
03 二分查找 O(log(n)) O(1) 
func findKthPositive(arr []int, k int) int {
	start := 1
	i := 0
	for {
		if i < len(arr) && arr[i] == start {
			i++
		} else {
			k--
			if k == 0 {
				return start
			}
		}
		start++
	}
}

# 2
func findKthPositive(arr []int, k int) int {
	for i := 0; i < len(arr); i++ {
		if arr[i]-(i+1) >= k {
			return k + i
		}
	}
	return k + len(arr)
}

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

1544.整理字符串(1)

  • 题目

给你一个由大小写英文字母组成的字符串 s 。
一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：
    0 <= i <= s.length - 2
    s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。
示例 1：输入：s = "leEeetcode" 输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。
示例 2：输入：s = "abBAcC" 输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""
示例 3：输入：s = "s"输出："s"
提示： 1 <= s.length <= 100
    s 只包含小写和大写英文字母

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 栈辅助 O(n) O(n) 
func makeGood(s string) string {
	if len(s) <= 1 {
		return s
	}
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		stack = append(stack, s[i])
		if len(stack) > 1 {
			length := len(stack)
			if stack[length-1]-'A'+'a' == stack[length-2] ||
				stack[length-1]-'a'+'A' == stack[length-2] {
				stack = stack[:length-2]
			}
		}
	}
	return string(stack)
}

1550.存在连续三个奇数的数组(2)

  • 题目

给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：
如果存在，请返回 true ；否则，返回 false 。
示例 1：输入：arr = [2,6,4,1] 输出：false
解释：不存在连续三个元素都是奇数的情况。
示例 2：输入：arr = [1,2,34,3,4,5,7,23,12] 输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。
提示： 1 <= arr.length <= 1000
    1 <= arr[i] <= 1000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n) O(1)
02 遍历 O(n) O(1) 
func threeConsecutiveOdds(arr []int) bool {
	for i := 0; i < len(arr)-2; i++ {
		if arr[i]%2 == 1 && arr[i+1]%2 == 1 && arr[i+2]%2 == 1 {
			return true
		}
	}
	return false
}

# 2
func threeConsecutiveOdds(arr []int) bool {
	count := 0
	for i := 0; i < len(arr); i++ {
		if arr[i]%2 == 1 {
			count++
		} else {
			count = 0
		}
		if count == 3 {
			return true
		}
	}
	return false
}

1556.千位分隔数(1)

  • 题目

给你一个整数 n，请你每隔三位添加点（即 "." 符号）作为千位分隔符，并将结果以字符串格式返回。
示例 1：输入：n = 987 输出："987"
示例 2：输入：n = 1234 输出："1.234"
示例 3：输入：n = 123456789 输出："123.456.789"
示例 4：输入：n = 0 输出："0"
提示： 0 <= n < 2^31

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1) 
func thousandSeparator(n int) string {
	res := ""
	if n == 0 {
		return "0"
	}
	count := 0
	for n != 0 {
		count++
		value := n % 10
		if count%3 == 1 {
			res = strconv.Itoa(value) + "." + res
		} else {
			res = strconv.Itoa(value) + res
		}
		n = n / 10
	}
	return strings.Trim(res, ".")
}

1560.圆形赛道上经过次数最多的扇区(2)

  • 题目

给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。
现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。
其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。
举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。
请你以数组形式返回经过次数最多的那几个扇区，按扇区编号 升序 排列。
注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。
示例 1：输入：n = 4, rounds = [1,3,1,2] 输出：[1,2]
解释：本场马拉松比赛从扇区 1 开始。经过各个扇区的次序如下所示：
1 --> 2 --> 3（阶段 1 结束）--> 4 --> 1（阶段 2 结束）--> 2
（阶段 3 结束，即本场马拉松结束）其中，扇区 1 和 2 都经过了两次，它们是经过次数最多的两个扇区。
扇区 3 和 4 都只经过了一次。
示例 2：输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2] 出：[2]
示例 3：输入：n = 7, rounds = [1,3,5,7] 出：[1,2,3,4,5,6,7]
提示：
    2 <= n <= 100
    1 <= m <= 100
    rounds.length == m + 1
    1 <= rounds[i] <= n
    rounds[i] != rounds[i + 1] ，其中 0 <= i < m

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数组模拟 O(n^2) O(n)
02 遍历 O(n) O(n) 
func mostVisited(n int, rounds []int) []int {
	arr := make([]int, n+1)
	res := make([]int, 0)
	max := 0
	arr[rounds[0]]++
	for i := 0; i < len(rounds)-1; i++ {
		start := rounds[i]
		end := rounds[i+1]
		if start < end {
			for j := start + 1; j <= end; j++ {
				arr[j]++
			}
		} else {
			for j := start + 1; j <= n; j++ {
				arr[j]++
			}
			for j := 1; j <= end; j++ {
				arr[j]++
			}
		}
	}
	for i := 1; i < len(arr); i++ {
		if arr[i] > max {
			max = arr[i]
			res = make([]int, 0)
			res = append(res, i)
		} else if arr[i] == max {
			res = append(res, i)
		}
	}
	return res
}

# 2
func mostVisited(n int, rounds []int) []int {
	res := make([]int, 0)
	start := rounds[0]
	end := rounds[len(rounds)-1]
	if start <= end {
		for i := start; i <= end; i++ {
			res = append(res, i)
		}
	} else {
		for i := 1; i <= end; i++ {
			res = append(res, i)
		}
		for i := start; i <= n; i++ {
			res = append(res, i)
		}
	}
	return res
}

1566.重复至少K次且长度为M的模式(2)

  • 题目

给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。
如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回  false 。
示例 1：输入：arr = [1,2,4,4,4,4], m = 1, k = 3 输出：true
解释：模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。
示例 2：输入：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2 输出：true
解释：模式 (1,2) 长度为 2 ，且连续重复 2 次。另一个符合题意的模式是 (2,1) ，同样重复 2 次。
示例 3：输入：arr = [1,2,1,2,1,3], m = 2, k = 3 输出：false
解释：模式 (1,2) 长度为 2 ，但是只连续重复 2 次。不存在长度为 2 且至少重复 3 次的模式。
示例 4：输入：arr = [1,2,3,1,2], m = 2, k = 2 输出：false
解释：模式 (1,2) 出现 2 次但并不连续，所以不能算作连续重复 2 次。
示例 5：输入：arr = [2,2,2,2], m = 2, k = 3 输出：false
解释：长度为 2 的模式只有 (2,2) ，但是只连续重复 2 次。注意，不能计算重叠的重复次数。
提示： 2 <= arr.length <= 100
    1 <= arr[i] <= 100
    1 <= m <= 100
    2 <= k <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(1)
02 遍历 O(n^2) O(1) 
func containsPattern(arr []int, m int, k int) bool {
	for i := 0; i < len(arr)-m; i++ {
		count := 0
		j := i
		for j+m <= len(arr) {
			flag := true
			for l := 0; l < m; l++ {
				if arr[i+l] != arr[j+l] {
					flag = false
					break
				}
			}
			if flag == true {
				count++
				j = j + m
			} else {
				break
			}
		}
		if count >= k {
			return true
		}
	}
	return false
}

# 2
func containsPattern(arr []int, m int, k int) bool {
	n := len(arr)
	if n < m*k {
		return false
	}
	i, j := 0, 0
	for i = 0; i <= n-m*k; i++ {
		for j = i + m; j < i+m*k; j++ {
			if arr[j] != arr[j-m] {
				break
			}
		}
		if j == i+m*k {
			return true
		}
	}
	return false
}

1572.矩阵对角线元素的和(2)

  • 题目

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。
示例  1：输入：mat = [[1,2,3],
            [4,5,6],
            [7,8,9]]
输出：25
解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
请注意，元素 mat[1][1] = 5 只会被计算一次。
示例  2：输入：mat = [[1,1,1,1],
            [1,1,1,1],
            [1,1,1,1],
            [1,1,1,1]]
输出：8
示例 3：输入：mat = [[5]] 输出：5
提示：
    n == mat.length == mat[i].length
    1 <= n <= 100
    1 <= mat[i][j] <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1) 
func diagonalSum(mat [][]int) int {
	res := 0
	for i := 0; i < len(mat); i++ {
		a, b := i, len(mat)-1-i
		if a == b {
			res = res + mat[a][b]
		} else {
			res = res + mat[a][a]
			res = res + mat[a][b]
		}
	}
	return res
}

# 2
func diagonalSum(mat [][]int) int {
	res := 0
	for i := 0; i < len(mat); i++ {
		a, b := i, len(mat)-1-i
		res = res + mat[a][a]
		res = res + mat[a][b]

	}
	if len(mat)%2 == 1 {
		res = res - mat[len(mat)/2][len(mat)/2]
	}
	return res
}

1576.替换所有的问号(1)

  • 题目

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，
请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。
注意：你 不能 修改非 '?' 字符。
题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。
在完成所有转换（可能无需转换）后返回最终的字符串。
如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。
示例 1：输入：s = "?zs" 输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。
只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。
示例 2：输入：s = "ubv?w"输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。
因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。
示例 3：输入：s = "j?qg??b" 输出："jaqgacb"
示例 4：输入：s = "??yw?ipkj?" 输出："acywaipkja"
提示：1 <= s.length <= 100
    s 仅包含小写英文字母和 '?' 字符

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1) 
func modifyString(s string) string {
	res := []byte(s)
	for i := 0; i < len(s); i++ {
		if s[i] == '?' {
			for j := byte('a'); j <= 'z'; j++ {
				if (i == 0 || res[i-1] != j) && (i == len(s)-1 || s[i+1] != j) {
					res[i] = j
					break
				}
			}
		}
	}
	return string(res)
}

1582.二进制矩阵中的特殊位置(2)

  • 题目

给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，
请返回 矩阵 mat 中特殊位置的数目 。
特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0
（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。
示例 1：输入：mat = [[1,0,0],
            [0,0,1],
            [1,0,0]]
输出：1
解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0
示例 2：输入：mat = [[1,0,0],
            [0,1,0],
            [0,0,1]]
输出：3
解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
示例 3：输入：mat = [[0,0,0,1],
            [1,0,0,0],
            [0,1,1,0],
            [0,0,0,0]]
输出：2
示例 4：输入：mat = [[0,0,0,0,0],
            [1,0,0,0,0],
            [0,1,0,0,0],
            [0,0,1,0,0],
            [0,0,0,1,1]]
输出：3
提示：
    rows == mat.length
    cols == mat[i].length
    1 <= rows, cols <= 100
    mat[i][j] 是 0 或 1

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^3) O(1)
02 数组辅助 O(n^2) O(n) 
func numSpecial(mat [][]int) int {
	res := 0
	for i := 0; i < len(mat); i++ {
		for j := 0; j < len(mat[i]); j++ {
			if mat[i][j] == 1 && judge(mat, i, j) == true {
				res++
			}
		}
	}
	return res
}

func judge(mat [][]int, i, j int) bool {
	for a := 0; a < len(mat[i]); a++ {
		if mat[i][a] == 1 && a != j {
			return false
		}
	}
	for a := 0; a < len(mat); a++ {
		if mat[a][j] == 1 && a != i {
			return false
		}
	}
	return true
}

# 2
func numSpecial(mat [][]int) int {
	res := 0
	rows, cols := make([]int, len(mat)), make([]int, len(mat[0]))
	for i := 0; i < len(mat); i++ {
		for j := 0; j < len(mat[i]); j++ {
			rows[i] = rows[i] + mat[i][j]
			cols[j] = cols[j] + mat[i][j]
		}
	}
	for i := 0; i < len(mat); i++ {
		for j := 0; j < len(mat[i]); j++ {
			if mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1 {
				res++
			}
		}
	}
	return res
}

1588.所有奇数长度子数组的和(3)

  • 题目

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
示例 1：输入：arr = [1,4,2,5,3] 输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
示例 2：输入：arr = [1,2] 输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
示例 3：输入：arr = [10,11,12] 输出：66
提示：
    1 <= arr.length <= 100
    1 <= arr[i] <= 1000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和 O(n^2) O(n)
02 暴力法 O(n^3) O(1)
03 数学 O(n) O(1) 
func sumOddLengthSubarrays(arr []int) int {
	sum := make([]int, len(arr)+1)
	sum[0] = 0
	for i := 1; i <= len(arr); i++ {
		sum[i] = sum[i-1] + arr[i-1]
	}
	res := 0
	for i := 1; i <= len(arr); i = i + 2 {
		for j := 0; j < len(arr); j++ {
			k := j + i
			if k <= len(arr) {
				total := sum[k] - sum[j]
				res = res + total
			}
		}
	}
	return res
}

# 2
func sumOddLengthSubarrays(arr []int) int {
	res := 0
	for i := 1; i <= len(arr); i = i + 2 {
		for j := 0; j < len(arr); j++ {
			k := j + i
			for start := j; start < k && k <= len(arr); start++ {
				res = res + arr[start]
			}
		}
	}
	return res
}

# 3 
# https://leetcode.cn/problems/sum-of-all-odd-length-subarrays/solution/cong-on3-dao-on-de-jie-fa-by-liuyubobobo/
func sumOddLengthSubarrays(arr []int) int {
	res := 0
	n := len(arr)
	for i := 0; i < n; i++ {
		left := i + 1
		right := n - i
		leftEven := (left + 1) / 2
		rightEven := (right + 1) / 2
		leftOdd := left / 2
		rightOdd := right / 2
		res = res + arr[i]*(leftEven*rightEven+leftOdd*rightOdd)
	}
	return res
}

1592.重新排列单词间的空格(1)

  • 题目

给你一个字符串 text ，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，
并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词 。
请你重新排列空格，使每对相邻单词之间的空格数目都 相等 ，并尽可能 最大化 该数目。
如果不能重新平均分配所有空格，请 将多余的空格放置在字符串末尾 ，
这也意味着返回的字符串应当与原 text 字符串的长度相等。
返回 重新排列空格后的字符串 。
示例 1：输入：text = "  this   is  a sentence " 输出："this   is   a   sentence"
解释：总共有 9 个空格和 4 个单词。可以将 9 个空格平均分配到相邻单词之间，相邻单词间空格数为：
9 / (4-1) = 3 个。
示例 2：输入：text = " practice   makes   perfect" 输出："practice   makes   perfect "
解释：总共有 7 个空格和 3 个单词。7 / (3-1) = 3 个空格加上 1 个多余的空格。
多余的空格需要放在字符串的末尾。
示例 3：输入：text = "hello   world" 输出："hello   world"
示例 4：输入：text = "  walks  udp package   into  bar a"
输出："walks  udp  package  into  bar  a "
示例 5：输入：text = "a" 输出："a"
提示： 1 <= text.length <= 100
    text 由小写英文字母和 ' ' 组成
    text 中至少包含一个单词

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n) 
func reorderSpaces(text string) string {
	count := strings.Count(text, " ")
	arr := strings.Fields(text)
	if len(arr) == 1 {
		return arr[0] + strings.Repeat(" ", count)
	}
	value := count / (len(arr) - 1)
	left := count % (len(arr) - 1)
	res := strings.Join(arr, strings.Repeat(" ", value))
	res = res + strings.Repeat(" ", left)
	return res
}

1598.文件夹操作日志搜集器(1)

  • 题目

每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。
下面给出对变更操作的说明：
    "../" ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则 继续停留在当前文件夹 。
    "./" ：继续停留在当前文件夹。
    "x/" ：移动到名为 x 的子文件夹中。题目数据 保证总是存在文件夹 x 。
给你一个字符串列表 logs ，其中 logs[i] 是用户在 ith 步执行的操作。
文件系统启动时位于主文件夹，然后执行 logs 中的操作。
执行完所有变更文件夹操作后，请你找出 返回主文件夹所需的最小步数 。
示例 1：输入：logs = ["d1/","d2/","../","d21/","./"] 输出：2
解释：执行 "../" 操作变更文件夹 2 次，即可回到主文件夹
示例 2：输入：logs = ["d1/","d2/","./","d3/","../","d31/"] 输出：3
示例 3：输入：logs = ["d1/","../","../","../"] 输出：0
提示： 1 <= logs.length <= 103
    2 <= logs[i].length <= 10
    logs[i] 包含小写英文字母，数字，'.' 和 '/'
    logs[i] 符合语句中描述的格式
    文件夹名称由小写英文字母和数字组成

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 栈 O(n) O(n) 
func minOperations(logs []string) int {
	stack := make([]string, 0)
	for i := 0; i < len(logs); i++ {
		if logs[i] == "../" {
			if len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
		} else if logs[i] != "./" {
			stack = append(stack, logs[i])
		}
	}
	return len(stack)
}

1501-1600-Medium

1503.所有蚂蚁掉下来前的最后一刻(2)

  • 题目

有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。
其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。
假设更改方向不会花费任何额外时间。
而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
给你一个整数 n 和两个整数数组 left 以及 right 。
两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。
示例 1：输入：n = 4, left = [4,3], right = [0,1] 输出：4
解释：如上图所示：
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。
（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。
示例 2：输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7] 输出：7
解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。
示例 3：输入：n = 7, left = [0,1,2,3,4,5,6,7], right = [] 输出：7
解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
示例 4：输入：n = 9, left = [5], right = [4] 输出：5
解释：t = 1 秒时，两只蚂蚁将回到初始位置，但移动方向与之前相反。
示例 5：输入：n = 6, left = [6], right = [0] 输出：6
提示：
    1 <= n <= 10^4
    0 <= left.length <= n + 1
    0 <= left[i] <= n
    0 <= right.length <= n + 1
    0 <= right[i] <= n
    1 <= left.length + right.length <= n + 1
    left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 排序 O(nlog(n)) O(1) 
// 2只蚂蚁相遇=>两只蚂蚁都不改变移动方向=>求离终点最远距离
func getLastMoment(n int, left []int, right []int) int {
	max := 0
	for i := 0; i < len(left); i++ {
		if left[i] > max {
			max = left[i]
		}
	}
	for i := 0; i < len(right); i++ {
		if n-right[i] > max {
			max = n - right[i]
		}
	}
	return max
}

# 2
func getLastMoment(n int, left []int, right []int) int {
	sort.Ints(left)
	sort.Ints(right)
	if len(left) == 0 {
		return n - right[0]
	}
	if len(right) == 0 {
		return left[len(left)-1]
	}
	if n-right[0] > left[len(left)-1] {
		return n - right[0]
	}
	return left[len(left)-1]
}

1504.统计全1子矩形(2)

  • 题目

给你一个只包含 0 和 1 的rows * columns矩阵mat，请你返回有多少个子矩形的元素全部都是 1 。
示例 1：输入：mat = [[1,0,1],
           [1,1,0],
           [1,1,0]]
输出：13
解释：有 6个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13。
示例 2：输入：mat = [[0,1,1,0],
           [0,1,1,1],
           [1,1,1,0]]
输出：24
解释：有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
示例 3：输入：mat = [[1,1,1,1,1,1]] 输出：21
示例 4：输入：mat = [[1,0,1],[0,1,0],[1,0,1]] 输出：5
提示：1 <= rows<= 150
1 <= columns<= 150
0 <= mat[i][j] <= 1

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和 O(n^3) O(1)
02 前缀和 O(n^3) O(n^2) 
func numSubmat(mat [][]int) int {
	res := 0
	n, m := len(mat), len(mat[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if j > 0 && mat[i][j] == 1 {
				mat[i][j] = mat[i][j-1] + 1 // 到左边连续1的个数
			}
			target := mat[i][j]       // 底：当前行以mat[i][j]=1结尾的连续1的个数
			for k := i; k >= 0; k-- { // 遍历高
				if target > mat[k][j] { // 上一层连续1的个数小
					target = mat[k][j] // 缩小底
				}
				// 示例1：右下角一行3个1
				// 1(1) 1(2) 1(3) => 有3种组成矩形的情况
				// 第1种情况.1(3)
				// 第2种情况.1(2)+1(3)
				// 第3种情况.1(1)+1(2)+1(3)
				res = res + target // 加上该高度的个数
			}
		}
	}
	return res
}

# 2
func numSubmat(mat [][]int) int {
	res := 0
	n, m := len(mat), len(mat[0])
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if j == 0 {
				arr[i][j] = mat[i][j]
			} else if j > 0 && mat[i][j] == 1 {
				arr[i][j] = arr[i][j-1] + 1 // 到左边连续1的个数
			}
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			target := arr[i][j]
			for k := i; k >= 0; k-- {
				if target > arr[k][j] {
					target = arr[k][j]
				}
				res = res + target
			}
		}
	}
	return res
}

1508.子数组和排序后的区间和(1)

  • 题目

给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，
得到一个新的包含 n * (n + 1) / 2 个数字的数组。
请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：输入：nums = [1,2,3,4], n = 4, left = 1, right = 5 输出：13 
解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。
将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。
下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。
示例 2：输入：nums = [1,2,3,4], n = 4, left = 3, right = 4 输出：6
解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。
下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。
示例 3：输入：nums = [1,2,3,4], n = 4, left = 1, right = 10 输出：50
提示：
    1 <= nums.length <= 10^3
    nums.length == n
    1 <= nums[i] <= 100
    1 <= left <= right <= n * (n + 1) / 2

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2log(n)) O(n^2) 
func rangeSum(nums []int, n int, left int, right int) int {
	arr := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum = sum + nums[j]
			arr = append(arr, sum)
		}
	}
	sort.Ints(arr)
	res := 0
	for i := left - 1; i <= right-1; i++ {
		res = (res + arr[i]) % 1000000007
	}
	return res
}

1509.三次操作后最大值与最小值的最小差(2)

  • 题目

给你一个数组 nums ，每次操作你可以选择 nums 中的任意一个元素并将它改成任意值。
请你返回三次操作后， nums 中最大值与最小值的差的最小值。
示例 1：输入：nums = [5,3,2,4] 输出：0
解释：将数组 [5,3,2,4] 变成 [2,2,2,2].
最大值与最小值的差为 2-2 = 0 。
示例 2：输入：nums = [1,5,0,10,14] 输出：1
解释：将数组 [1,5,0,10,14] 变成 [1,1,0,1,1] 。
最大值与最小值的差为 1-0 = 1 。
示例 3：输入：nums = [6,6,0,1,1,4,6] 输出：2
示例 4：输入：nums = [1,5,6,14,15] 输出：1
提示：
    1 <= nums.length <= 10^5
    -10^9 <= nums[i] <= 10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
02 排序 O(nlog(n)) O(1) 
func minDifference(nums []int) int {
	if len(nums) < 5 {
		return 0
	}
	sort.Ints(nums)
	res := math.MaxInt32
	for i := 0; i <= 3; i++ {
		res = min(res, nums[len(nums)-1-(3-i)]-nums[i])
	}
	return res
}

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

#
func minDifference(nums []int) int {
	if len(nums) < 5 {
		return 0
	}
	sort.Ints(nums)
	res := math.MaxInt32
	res = min(res, nums[len(nums)-1]-nums[3])
	res = min(res, nums[len(nums)-2]-nums[2])
	res = min(res, nums[len(nums)-3]-nums[1])
	res = min(res, nums[len(nums)-4]-nums[0])
	return res
}

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

1513.仅含1的子串数(2)

  • 题目

给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例 1：输入：s = "0110111" 输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次
示例 2：输入：s = "101" 输出：2
解释：子字符串 "1" 在 s 中共出现 2 次
示例 3：输入：s = "111111" 输出：21
解释：每个子字符串都仅由 '1' 组成
示例 4：输入：s = "000" 输出：0
提示：
    s[i] == '0' 或 s[i] == '1'
    1 <= s.length <= 10^5

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1) 
func numSub(s string) int {
	res := 0
	count := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '1' {
			count++
		} else {
			res = (res + (count+1)*count/2) % 1000000007
			count = 0
		}
	}
	if count > 0 {
		res = (res + (count+1)*count/2) % 1000000007
	}
	return res
}

#
func numSub(s string) int {
	res := 0
	count := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '1' {
			count++
		} else {
			count = 0
		}
		res = (res + count) % 1000000007
	}
	return res
}

1514.概率最大的路径(2)

  • 题目

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，
其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，
就会被视作正确答案。
示例 1：
输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25
示例 2：
输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000
示例 3：输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径
提示：2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
每两个节点之间最多有一条边

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 Dijkstra-堆 O(nlog(n)) O(n)
02 Dijkstra O(n^2) O(n) 
func maxProbability(n int, edges [][]int, succProb []float64, start int, end int) float64 {
	arr := make([][]Node, n)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		arr[a] = append(arr[a], Node{index: b, Value: succProb[i]})
		arr[b] = append(arr[b], Node{index: a, Value: succProb[i]})
	}
	visited := make([]bool, n)
	maxValue := make([]float64, n)
	nodeHeap := make(NodeHeap, 0)
	heap.Init(&nodeHeap)
	heap.Push(&nodeHeap, Node{
		Value: 1,
		index: start,
	})
	for nodeHeap.Len() > 0 {
		node := heap.Pop(&nodeHeap).(Node)
		visited[node.index] = true
		if node.index == end {
			return node.Value
		}
		for i := 0; i < len(arr[node.index]); i++ {
			next := arr[node.index][i]
			if visited[next.index] == true || node.Value*next.Value < maxValue[next.index] {
				continue
			}
			maxValue[next.index] = node.Value * next.Value
			heap.Push(&nodeHeap, Node{
				Value: maxValue[next.index],
				index: next.index,
			})
		}
	}
	return 0
}

type Node struct {
	Value float64
	index int
}

type NodeHeap []Node

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

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

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

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

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

# 2
func maxProbability(n int, edges [][]int, succProb []float64, start int, end int) float64 {
	arr := make([][]Node, n)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		arr[a] = append(arr[a], Node{index: b, Value: succProb[i]})
		arr[b] = append(arr[b], Node{index: a, Value: succProb[i]})
	}
	maxValue := make([]float64, n)
	maxValue[start] = 1.0
	queue := make([]Node, 0)
	queue = append(queue, Node{
		Value: 1.0,
		index: start,
	})
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if maxValue[node.index] > node.Value {
			continue
		}
		for i := 0; i < len(arr[node.index]); i++ {
			next := arr[node.index][i]
			// 注意使用<=，即=号要过滤，不然容易超时
			if maxValue[node.index]*next.Value <= maxValue[next.index] {
				continue
			}
			maxValue[next.index] = maxValue[node.index] * next.Value
			queue = append(queue, Node{
				Value: maxValue[next.index],
				index: next.index,
			})
		}
	}
	return maxValue[end]
}

type Node struct {
	Value float64
	index int
}

1519.子树中标签相同的节点数(2)

  • 题目

给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，
且恰好有 n - 1 条 edges 。
树的根节点为节点 0 ，树上的每一个节点都有一个标签，
也就是字符串 labels 中的一个小写字符（编号为 i 的 节点的标签就是 labels[i] ）
边数组 edges 以 edges[i] = [ai, bi] 的形式给出，该格式表示节点 ai 和 bi 之间存在一条边。
返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。
树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。
示例 1：输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
输出：[2,1,1,1,1,1,1]
解释：节点 0 的标签为 'a' ，以 'a' 为根节点的子树中，节点 2 的标签也是 'a' ，因此答案为 2 。
注意树中的每个节点都是这棵子树的一部分。
节点 1 的标签为 'b' ，节点 1 的子树包含节点 1、4 和 5，
但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。
示例 2：输入：n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb" 输出：[4,2,1,1]
解释：节点 2 的子树中只有节点 2 ，所以答案为 1 。
节点 3 的子树中只有节点 3 ，所以答案为 1 。
节点 1 的子树中包含节点 1 和 2 ，标签都是 'b' ，因此答案为 2 。
节点 0 的子树中包含节点 0、1、2 和 3，标签都是 'b'，因此答案为 4 。
示例 3：输入：n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab" 输出：[3,2,1,1,1]
示例 4：输入：n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
输出：[1,2,1,1,2,1]
示例 5：输入：n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
输出：[6,5,4,1,3,2,1]
提示：1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ai,bi < n
ai !=bi
labels.length == n
labels 仅由小写英文字母组成

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^2) O(n)
02 深度优先搜索 O(n^2) O(n) 
var arr [][]int // 邻接表
var res []int   // 结果

func countSubTrees(n int, edges [][]int, labels string) []int {
	res = make([]int, n)
	arr = make([][]int, n)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		arr[a] = append(arr[a], b)
		arr[b] = append(arr[b], a)
	}
	dfs(labels, 0, 0)
	return res
}

// 后序遍历
func dfs(s string, cur int, prev int) [26]int {
	count := [26]int{}
	for i := 0; i < len(arr[cur]); i++ {
		next := arr[cur][i]
		if next == prev { // 注意避免重复往回走
			continue
		}
		res := dfs(s, next, cur)
		for j := 0; j < len(res); j++ {
			count[j] = count[j] + res[j]
		}
	}
	value := int(s[cur] - 'a')
	count[value]++
	res[cur] = count[value]
	return count
}

# 2
var arr [][]int   // 邻接表
var res []int     // 结果
var m map[int]int // 临时结果
func countSubTrees(n int, edges [][]int, labels string) []int {
	res = make([]int, n)
	arr = make([][]int, n)
	m = make(map[int]int)
	for i := 0; i < len(edges); i++ {
		a, b := edges[i][0], edges[i][1]
		arr[a] = append(arr[a], b)
		arr[b] = append(arr[b], a)
	}
	dfs(labels, 0, 0)
	for i := 0; i < n; i++ {
		value := int(labels[i] - 'a')
		res[i] = m[i*26+value]
	}
	return res
}

// 后序遍历
func dfs(s string, cur int, prev int) {
	m[cur*26+int(s[cur]-'a')]++
	for i := 0; i < len(arr[cur]); i++ {
		next := arr[cur][i]
		if next == prev { // 注意避免重复往回走
			continue
		}
		dfs(s, next, cur)
		for j := 0; j < 26; j++ { // 子节点的结果
			m[cur*26+j] = m[cur*26+j] + m[next*26+j]
		}
	}
}

1524.和为奇数的子数组数目(2)

  • 题目

给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
示例 1：输入：arr = [1,3,5] 输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。
示例 2 ：输入：arr = [2,4,6] 输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。
示例 3：输入：arr = [1,2,3,4,5,6,7] 输出：16
示例 4：输入：arr = [100,100,99,99] 输出：4
示例 5：输入：arr = [7] 输出：1
提示：1 <= arr.length <= 10^5
    1 <= arr[i] <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和 O(n) O(1)
02 动态规划 O(n) O(n) 
func numOfSubarrays(arr []int) int {
	odd, even := 0, 1
	res := 0
	total := 0
	for i := 0; i < len(arr); i++ {
		total = total + arr[i]
		if total%2 == 0 {
			res = res + odd
			even = even + 1
		} else {
			res = res + even
			odd = odd + 1
		}
	}
	return res % 1000000007
}

# 2
func numOfSubarrays(arr []int) int {
	res := 0
	dp := make([][2]int, len(arr))
	// dp[i][0]子数组和为奇数的个数
	// dp[i][1]子数组和为偶数的个数
	if arr[0]%2 == 1 {
		dp[0][0] = 1
		res++
	} else {
		dp[0][1] = 1
	}
	for i := 1; i < len(arr); i++ {
		if arr[i]%2 == 1 {
			dp[i][0] = dp[i-1][1] + 1
			dp[i][1] = dp[i-1][0]
		} else {
			dp[i][0] = dp[i-1][0]
			dp[i][1] = dp[i-1][1] + 1
		}
		res = res + dp[i][0]
	}
	return res % 1000000007
}

1525.字符串的好分割数目(2)

  • 题目

给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：
将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。
请你返回 s 中好分割的数目。
示例 1：输入：s = "aacaba" 输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。
示例 2：输入：s = "abcd"输出：1 解释：好分割为将字符串分割成 ("ab", "cd") 。
示例 3：输入：s = "aaaaa"输出：4 解释：所有分割都是好分割。
示例 4：输入：s = "acbadbaada"输出：2
提示：s 只包含小写英文字母。 1 <= s.length <= 10^5

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(1)
02 数组辅助 O(n) O(1) 
func numSplits(s string) int {
	left := make(map[byte]int)
	right := make(map[byte]int)
	for i := 0; i < len(s); i++{
		left[s[i]]++
	}
	res := 0
	for i := 0; i < len(s); i++{
		left[s[i]]--
		right[s[i]]++
		if left[s[i]] == 0{
			delete(left,s[i])
		}
		if len(left) == len(right){
			res++
		}
	}
	return res
}

#
func numSplits(s string) int {
	left := [256]int{}
	right := [256]int{}
	leftCount := 0
	rightCount := 0
	for i := 0; i < len(s); i++ {
		left[s[i]]++
		if left[s[i]] == 1 {
			leftCount++
		}
	}
	res := 0
	for i := 0; i < len(s); i++ {
		left[s[i]]--
		right[s[i]]++
		if left[s[i]] == 0 {
			leftCount--
		}
		if right[s[i]] == 1 {
			rightCount++
		}
		if leftCount == rightCount {
			res++
		}
	}
	return res
}

1529.灯泡开关IV(2)

  • 题目

房间中有 n 个灯泡，编号从 0 到 n-1 ，自左向右排成一行。最开始的时候，所有的灯泡都是 关 着的。
请你设法使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 第 i 个灯泡是开着的，
等于 0 意味着第 i 个灯是关着的。
有一个开关可以用于翻转灯泡的状态，翻转操作定义如下：
    选择当前配置下的任意一个灯泡（下标为 i ）
    翻转下标从 i 到 n-1 的每个灯泡
翻转时，如果灯泡的状态为 0 就变为 1，为 1 就变为 0 。
返回达成 target 描述的状态所需的 最少 翻转次数。
示例 1：输入：target = "10111" 输出：3 解释：初始配置 "00000".
从第 3 个灯泡（下标为 2）开始翻转 "00000" -> "00111"
从第 1 个灯泡（下标为 0）开始翻转 "00111" -> "11000"
从第 2 个灯泡（下标为 1）开始翻转 "11000" -> "10111"
至少需要翻转 3 次才能达成 target 描述的状态
示例 2：输入：target = "101" 输出：3 解释："000" -> "111" -> "100" -> "101".
示例 3：输入：target = "00000" 输出：0
示例 4：输入：target = "001011101" 输出：5
提示：
    1 <= target.length <= 10^5
    target[i] == '0' 或者 target[i] == '1'

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1) 
func minFlips(target string) int {
	res := 0
	prev := uint8('0')
	for i := 0; i < len(target); i++ {
		// 只要后一个与前一个不相等, 都会额外增加一次翻转
		if prev != target[i] {
			res++
			prev = target[i]
		}
	}
	return res
}

# 2
func minFlips(target string) int {
	res := 0
	target = "0" + target
	for i := 1; i < len(target); i++ {
		// 只要后一个与前一个不相等, 都会额外增加一次翻转
		// 从前往后，每次翻转一样的
		// 如: "10111" => 00000=>(1)1111=>(10)000=>(10111)
		if target[i] != target[i-1] {
			res++
		}
	}
	return res
}

1530.好叶子节点对的数量(2)

  • 题目

给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
示例 1：输入：root = [1,2,3,null,4], distance = 3 输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
示例 2：输入：root = [1,2,3,4,5,6,7], distance = 3 输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。
但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。
示例 3：输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3 输出：1
解释：唯一的好叶子节点对是 [2,5] 。
示例 4：输入：root = [100], distance = 1 输出：0
示例 5：输入：root = [1,1,1], distance = 2 输出：1
提示：tree 的节点数在 [1, 2^10] 范围内。
每个节点的值都在 [1, 100] 之间。
1 <= distance <= 10

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n^2) O(n)
02 递归 O(n^2) O(n) 
func countPairs(root *TreeNode, distance int) int {
	_, res := dfs(root, distance)
	return res
}

func dfs(root *TreeNode, distance int) (arr []int, count int) {
	arr = make([]int, distance+2)
	if root == nil {
		return arr, 0
	}
	if root.Left == nil && root.Right == nil {
		arr[1] = 1
		return arr, 0
	}
	leftArr, rightArr := make([]int, distance+1), make([]int, distance+1)
	leftCount, rightCount := 0, 0
	if root.Left != nil {
		leftArr, leftCount = dfs(root.Left, distance)
	}
	if root.Right != nil {
		rightArr, rightCount = dfs(root.Right, distance)
	}
	for i := 1; i <= distance; i++ {
		arr[i+1] = leftArr[i] + rightArr[i]
	}
	count = 0
	for i := 0; i <= distance; i++ {
		for j := 0; j <= distance-i; j++ {
			count = count + leftArr[i]*rightArr[j]
		}
	}
	return arr, count + leftCount + rightCount
}

# 2
var res int

func countPairs(root *TreeNode, distance int) int {
	res = 0
	dfs(root, distance)
	return res
}

func dfs(root *TreeNode, distance int) (arr []int) {
	arr = make([]int, distance+2)
	if root == nil {
		return arr
	}
	if root.Left == nil && root.Right == nil {
		arr[1] = 1
		return arr
	}
	leftArr, rightArr := make([]int, distance+1), make([]int, distance+1)
	if root.Left != nil {
		leftArr = dfs(root.Left, distance)
	}
	if root.Right != nil {
		rightArr = dfs(root.Right, distance)
	}
	for i := 1; i <= distance; i++ {
		arr[i+1] = leftArr[i] + rightArr[i]
	}
	for i := 0; i <= distance; i++ {
		for j := 0; j <= distance-i; j++ {
			res = res + leftArr[i]*rightArr[j]
		}
	}
	return arr
}

1535.找出数组游戏的赢家(1)

  • 题目

给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。
比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，
较小的整数移至数组的末尾。
当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
返回赢得比赛的整数。
题目数据 保证 游戏存在赢家。
示例 1：输入：arr = [2,1,3,5,4,6,7], k = 2 输出：5
解释：一起看一下本场游戏每回合的情况：
因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。
示例 2：输入：arr = [3,2,1], k = 10 输出：3
解释：3 将会在前 10 个回合中连续获胜。
示例 3：输入：arr = [1,9,8,2,3,7,6,4,5], k = 7 输出：9
示例 4：输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000 输出：99
提示：2 <= arr.length <= 10^5
    1 <= arr[i] <= 10^6
    arr 所含的整数 各不相同 。
    1 <= k <= 10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1) 
func getWinner(arr []int, k int) int {
	res := arr[0]
	count := 0
	for i := 1; i < len(arr); i++ {
		if arr[i] > res {
			res = arr[i]
			count = 1
		} else {
			count++
		}
		if count == k {
			break
		}
	}
	return res
}

1536.排布二进制网格的最少交换次数(1)

  • 题目

给你一个nx n的二进制网格grid，每一次操作中，你可以选择网格的相邻两行进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 0。
请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1。
主对角线指的是从(1, 1)到(n, n)的这些格子。
示例 1：输入：grid = [[0,0,1],[1,1,0],[1,0,0]] 输出：3
示例 2：输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] 输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。
示例 3：输入：grid = [[1,0,0],[1,1,0],[1,1,1]] 输出：0
提示：n == grid.length
n == grid[i].length
1 <= n<= 200
grid[i][j]要么是0要么是1。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历+排序 O(n^2) O(n) 
func minSwaps(grid [][]int) int {
	n := len(grid)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		count := 0
		for j := n - 1; j >= 0; j-- {
			if grid[i][j] == 0 {
				count++
			} else {
				break
			}
		}
		arr[i] = count
	}
	res := 0
	for i := 0; i < n-1; i++ {
		if arr[i] >= n-1-i { // 满足条件
			continue
		}
		j := i
		for ; j < n; j++ { // 往后找
			if arr[j] >= n-1-i {
				break
			}
		}
		if j == n { // 找不到
			return -1
		}
		for ; j > i; j-- { // 前移
			arr[j], arr[j-1] = arr[j-1], arr[j]
			res++
		}
	}
	return res
}

1540.K次操作转变字符串(2)

  • 题目

给你两个字符串 s 和 t ，你的目标是在 k 次操作以内把字符串 s 转变成 t 。
在第 i 次操作时（1 <= i <= k），你可以选择进行如下操作：
    选择字符串 s 中满足 1 <= j <= s.length 且之前未被选过的任意下标 j （下标从 1 开始），
    并将此位置的字符切换 i 次。
    不进行任何操作。
切换 1 次字符的意思是用字母表中该字母的下一个字母替换它（字母表环状接起来，所以 'z' 切换后会变成 'a'）。
请记住任意一个下标 j 最多只能被操作 1 次。
如果在不超过 k 次操作内可以把字符串 s 转变成 t ，那么请你返回 true ，否则请你返回 false 。
示例 1：输入：s = "input", t = "ouput", k = 9 输出：true
解释：第 6 次操作时，我们将 'i' 切换 6 次得到 'o' 。第 7 次操作时，我们将 'n' 切换 7 次得到 'u' 。
示例 2：输入：s = "abc", t = "bcd", k = 10 输出：false
解释：我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 'a' 切换成 'b' ，
但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。
示例 3：输入：s = "aab", t = "bbb", k = 27 输出：true
解释：第 1 次操作时，我们将第一个 'a' 切换 1 次得到 'b' 。
在第 27 次操作时，我们将第二个字母 'a' 切换 27 次得到 'b' 。
提示：1 <= s.length, t.length <= 10^5
    0 <= k <= 10^9
    s 和 t 只包含小写英文字母。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(1)
02 数组辅助 O(n) O(1) 
func canConvertString(s string, t string, k int) bool {
	if len(s) != len(t) {
		return false
	}
	m := make(map[int]int)
	maxValue := 0
	for i := 0; i < len(s); i++ {
		if s[i] != t[i] {
			count := (int(t[i]) - int(s[i]) + 26) % 26 // 最少操作的次数
			// 1 <= i <= k，其中i只能出现一次，如果切换的次数一样，需要到下N一圈(i+26xN)才行
			maxValue = 26*m[count] + count
			if maxValue > k {
				return false
			}
			m[count]++
		}
	}
	return true
}

# 2
func canConvertString(s string, t string, k int) bool {
	if len(s) != len(t) {
		return false
	}
	next := [26]int{}
	for i := 0; i < 26; i++ {
		next[i] = i
	}
	for i := 0; i < len(s); i++ {
		if s[i] != t[i] {
			count := (int(t[i]) - int(s[i]) + 26) % 26 // 最少操作的次数
			// 1 <= i <= k，其中i只能出现一次，如果切换的次数一样，需要到下N一圈(i+26xN)才行
			if next[count] > k {
				return false
			}
			next[count] = next[count] + 26
		}
	}
	return true
}

1541.平衡括号字符串的最少插入次数(2)

  • 题目

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
    任何左括号 '(' 必须对应两个连续的右括号 '))' 。
    左括号 '(' 必须在对应的连续两个右括号 '))' 之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：输入：s = "(()))" 输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。
我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：输入：s = "())" 输出：0
解释：字符串已经平衡了。
示例 3：输入：s = "))())(" 输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：输入：s = "((((((" 输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：输入：s = ")))))))" 输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
提示：
    1 <= s.length <= 10^5
    s 只包含 '(' 和 ')' 。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 栈辅助 O(n) O(n) 
func minInsertions(s string) int {
	res := 0
	left := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			left++
		} else if s[i] == ')' {
			if i+1 < len(s) && s[i+1] == ')' {
				i++
			} else {
				res++ // 少一个')'补一个')'到2个')'
			}
			if left > 0 {
				left--
			} else {
				res++ // 左边无'('补一个
			}
		}
	}
	res = res + left*2
	return res
}

# 2
func minInsertions(s string) int {
	res := 0
	stack := make([]byte, 0)
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, '(')
		} else if s[i] == ')' {
			if i+1 < len(s) && s[i+1] == ')' {
				if len(stack) == 0 {
					// '))'的情况，补'('
					res++
				} else {
					stack = stack[:len(stack)-1]
				}
				i++
			} else {
				if len(stack) == 0 {
					// ')('的情况，')'补2'()'
					res = res + 2
				} else {
					// '()('的情况, '()'补')'
					res++
					stack = stack[:len(stack)-1]
				}
			}
		}
	}
	res = res + len(stack)*2
	return res
}

1545.找出第N个二进制字符串中的第K位(2)

  • 题目

给你两个正整数 n 和 k，二进制字符串  Sn 的形成规则如下：
    S1 = "0"
    当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，
而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）
例如，符合上述描述的序列的前 4 个字符串依次是：
    S1 = "0"
    S2 = "011"
    S3 = "0111001"
    S4 = "011100110110001"
请你返回  Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。
示例 1：输入：n = 3, k = 1 输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。
示例 2：输入：n = 4, k = 11 输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。
示例 3：输入：n = 1, k = 1 输出："0"
示例 4：输入：n = 2, k = 3 输出："1"
提示：
    1 <= n <= 20
    1 <= k <= 2n - 1

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(n)
02 暴力 O(2^n) O(2^n)
03 遍历 O(n) O(1) 
func findKthBit(n int, k int) byte {
	if n == 1 {
		return '0'
	}
	mid := 1 << (n - 1)
	if k == mid {
		return '1'
	} else if k < mid {
		return findKthBit(n-1, k)
	}
	// 下标从1开始，如n=4,k=15=>3,1(2^4-15=16-15=1)
	return change(findKthBit(n-1, (1<<n)-k))
}

func change(char byte) byte {
	if char == '0' {
		return '1'
	}
	return '0'
}

# 2
func findKthBit(n int, k int) byte {
	arr := generate(n)
	return arr[k-1]
}

func generate(n int) []byte {
	arr := make([][]byte, n)
	arr[0] = []byte{'0'}
	for i := 1; i < n; i++ {
		arr[i] = append(arr[i], arr[i-1]...)
		arr[i] = append(arr[i], '1')
		arr[i] = append(arr[i], reverse(invert(arr[i-1]))...)
	}
	return arr[n-1]
}

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
}

func invert(arr []byte) []byte {
	for i := 0; i < len(arr); i++ {
		arr[i] = '1' - arr[i] + '0'
	}
	return arr
}

# 3
func findKthBit(n int, k int) byte {
	if n == 1 {
		return '0'
	}
	flag := false
	mid := 1 << (n - 1)
	for k > 1 {
		if k == mid {
			if flag == true {
				return '0'
			}
			return '1'
		} else if k > mid {
			if flag == true {
				flag = false
			} else {
				flag = true
			}
			k = (mid << 1) - k
		}
		mid = mid >> 1
	}
	if flag == true {
		return '1'
	}
	return '0'
}

1546.和为目标值的最大数目不重叠非空子数组数目(2)

  • 题目

给你一个数组 nums 和一个整数 target 。
请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。
示例 1：输入：nums = [1,1,1,1,1], target = 2 输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
示例 2：输入：nums = [-1,3,5,1,4,2,-9], target = 6 输出：2
解释：总共有 3 个子数组和为 6 。([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
示例 3：输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10 输出：3
示例 4：输入：nums = [0,0,0], target = 0 输出：3
提示： 1 <= nums.length <= 10^5
    -10^4 <= nums[i] <= 10^4
    0 <= target <= 10^6

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和-哈希辅助 O(n) O(n)
02 前缀和-哈希辅助 O(n) O(n) 
func maxNonOverlapping(nums []int, target int) int {
	res := 0
	m := make(map[int]int)
	m[0] = -1
	sum := 0
	prev := -1
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
		if index, ok := m[sum-target]; ok && index >= prev {
			res++
			prev = i
		}
		m[sum] = i
	}
	return res
}

# 2
func maxNonOverlapping(nums []int, target int) int {
	res := 0
	m := make(map[int]int)
	m[0] = -1
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum = sum + nums[i]
		if _, ok := m[sum-target]; ok {
			m = make(map[int]int)
			sum = 0
			res++
		}
		m[sum] = i
	}
	return res
}

1551.使数组中所有元素相等的最小操作数(3)

  • 题目

存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。
一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、
arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。
最终的目标是使数组中的所有元素都 相等 。
题目测试用例将会 保证 ：在执行若干步操作后，数组中的所有元素最终可以全部相等。
给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。
示例 1：输入：n = 3 输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]
示例 2：输入：n = 6 输出：9
提示： 1 <= n <= 10^4

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数学 O(n) O(1)
02 数学 O(1) O(1)
03 数学 O(1) O(1) 
func minOperations(n int) int {
	res := 0
	for i := 1; i < n; i = i + 2 {
		res = res + n - i
	}
	return res
}

# 2
func minOperations(n int) int {
	res := 0
	if n == 1 {
		return res
	}
	if n%2 == 1 {
		value := n / 2
		res = value * (value + 1)
	} else {
		value := n / 2
		res = value * value
	}
	return res
}

# 3
func minOperations(n int) int {
	return n*n/4
}

1552.两球之间的磁力(2)

  • 题目

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力
。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，
使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
示例 1：输入：position = [1,2,3,4,7], m = 3 输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。
我们没办法让最小磁力大于 3 。
示例 2：输入：position = [5,4,3,2,1,1000000000], m = 2 输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。
提示：n == position.length
    2 <= n <= 10^5
    1 <= position[i] <= 10^9
    所有 position 中的整数 互不相同 。
    2 <= m <= position.length

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 二分查找 O(nlog(n)) O(1)
02 二分查找 O(nlog(n)) O(1) 
func maxDistance(position []int, m int) int {
	sort.Ints(position)
	n := len(position)
	maxValue := position[n-1] - position[0] // 最大值
	minValue := position[n-1]               // 求最小值
	for i := 1; i < n; i++ {
		if minValue > position[i]-position[i-1] {
			minValue = position[i] - position[i-1]
		}
	}
	if m == 2 {
		return maxValue
	}
	left, right := minValue, maxValue
	for left <= right {
		mid := left + (right-left)/2
		if check(position, mid, m) {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left - 1
}

func check(arr []int, value int, m int) bool {
	count := 1
	target := arr[0] + value
	for i := 0; i < len(arr); i++ {
		if arr[i] >= target {
			count++
			target = arr[i] + value
		}
	}
	return count >= m
}

# 2
func maxDistance(position []int, m int) int {
	sort.Ints(position)
	n := len(position)
	maxValue := (position[n-1] - position[0]) / (m - 1) // 最大值
	minValue := 1                                       // 最小值
	left, right := minValue, maxValue
	res := 1
	for left <= right {
		mid := left + (right-left)/2
		// 满足条件，left=mid+1尝试最大
		if check(position, mid, m) {
			res = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return res
}

func check(arr []int, value int, m int) bool {
	count := 1
	prev := 0
	for i := 1; i < len(arr); i++ {
		if arr[i]-arr[prev] >= value {
			count++
			prev = i
		}
	}
	return count >= m
}

1557.可以到达所有点的最少点数目(2)

  • 题目

给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，
其中 edges[i] = [fromi, toi] 表示一条从点  fromi 到点 toi 的有向边。
找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
你可以以任意顺序返回这些节点编号。
示例 1：输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] 输出：[0,3]
解释：从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。
从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。
示例 2：输入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] 输出：[0,2,3]
解释：注意到节点 0，3 和 2 无法从其他节点到达，所以我们必须将它们包含在结果点集中，
这些点都能到达节点 1 和 4 。
提示：
    2 <= n <= 10^5
    1 <= edges.length <= min(10^5, n * (n - 1) / 2)
    edges[i].length == 2
    0 <= fromi, toi < n
    所有点对 (fromi, toi) 互不相同。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 入度统计 O(n) O(n)
02 哈希辅助 O(n) O(n) 
func findSmallestSetOfVertices(n int, edges [][]int) []int {
	res := make([]int, 0)
	inEdges := make([]int, n)
	for i := 0; i < len(edges); i++ {
		// a->b
		b := edges[i][1]
		inEdges[b]++ // 入度
	}
	for i := 0; i < len(inEdges); i++ {
		if inEdges[i] == 0 {
			res = append(res, i)
		}
	}
	return res
}

# 2
func findSmallestSetOfVertices(n int, edges [][]int) []int {
	res := make([]int, 0)
	m := make(map[int]bool)
	for i := 0; i < n; i++ {
		m[i] = true
	}
	for i := 0; i < len(edges); i++ {
		b := edges[i][1]
		delete(m, b)
	}
	for k := range m {
		res = append(res, k)
	}
	return res
}

1558.得到目标数组的最少函数调用次数(2)

  • 题目

给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。
请你返回将 arr 变成 nums 的最少函数调用次数。
答案保证在 32 位有符号整数以内。
示例 1：输入：nums = [1,5] 输出：5
解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。
总操作次数为：1 + 2 + 2 = 5 。
示例 2：输入：nums = [2,2] 输出：3
解释：给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。
将所有数字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。
总操作次数为： 2 + 1 = 3 。
示例 3：输入：nums = [4,2,5] 输出：6
解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> 
[4,2,4] -> [4,2,5] （nums 数组）。
示例 4：输入：nums = [3,2,2,4] 输出：7
示例 5：输入：nums = [2,4,8,16] 输出：8
提示：1 <= nums.length <= 10^5
    0 <= nums[i] <= 10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 模拟 O(n) O(1)
02 数学 O(n) O(1) 
func minOperations(nums []int) int {
	res := 0
	for judge(nums) != true {
		res++ // 最后一次循环会多算一次,最后要减掉
		res = res + div(nums)
	}
	return res - 1
}

func judge(arr []int) bool {
	for i := 0; i < len(arr); i++ {
		if arr[i] != 0 {
			return false
		}
	}
	return true
}

func div(arr []int) int {
	res := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] == 0 {
			continue
		}
		if arr[i]%2 == 1 {
			res++
		}
		arr[i] = arr[i] / 2
	}
	return res
}

# 2
func minOperations(nums []int) int {
	res := 0
	maxValue := 0 // 保存x2的次数
	for i := 0; i < len(nums); i++ {
		count := 0
		n := nums[i]
		for n != 0 {
			if n%2 == 0 {
				n = n / 2
				count++
			} else {
				n = n - 1
				res = res + 1 // 单独加1
			}
		}
		maxValue = max(maxValue, count)
	}
	return res + maxValue
}

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

1561.你可以获得的最大硬币数目(3)

  • 题目

有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
    每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
    Alice 将会取走硬币数量最多的那一堆。
    你将会取走硬币数量第二多的那一堆。
    Bob 将会取走最后一堆。
    重复这个过程，直到没有更多硬币。
给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
返回你可以获得的最大硬币数目。
示例 1：输入：piles = [2,4,1,2,7,8] 输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
示例 2：输入：piles = [2,4,5] 输出：4
示例 3：输入：piles = [9,8,7,6,5,1,2,3,4] 输出：18
提示：
    3 <= piles.length <= 10^5
    piles.length % 3 == 0
    1 <= piles[i] <= 10^4

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序 O(nlog(n)) O(1)
02 排序 O(nlog(n)) O(1)
03 排序 O(nlog(n)) O(1) 
func maxCoins(piles []int) int {
	res := 0
	sort.Ints(piles)
	count := len(piles) / 3
	for i := 0; i < count; i++ {
		index := len(piles) - 1 - i*2 - 1
		res = res + piles[index]
	}
	return res
}

# 2
func maxCoins(piles []int) int {
	res := 0
	sort.Slice(piles, func(i, j int) bool {
		return piles[i] > piles[j]
	})
	for i := 0; i < len(piles)/3; i++ {
		res = res + piles[i*2+1]
	}
	return res
}

# 3
func maxCoins(piles []int) int {
	res := 0
	sort.Ints(piles)
	left := 0
	right := len(piles)-1
	for left < right{
		left++
		right--
		res = res + piles[right]
		right--
	}
	return res
}

1562.查找大小为M的最新分组(2)

  • 题目

给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。
有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），
二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。
一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
返回存在长度 恰好 为 m 的 一组 1  的最后步骤。如果不存在这样的步骤，请返回 -1 。
示例 1：输入：arr = [3,5,1,2,4], m = 1 输出：4
解释：步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："00101"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："11101"，由 1 构成的组：["111", "1"]
步骤 5："11111"，由 1 构成的组：["11111"]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。
示例 2：输入：arr = [3,1,5,4,2], m = 2 输出：-1
解释：步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："10100"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："10111"，由 1 构成的组：["1", "111"]
步骤 5："11111"，由 1 构成的组：["11111"]
不管是哪一步骤都无法形成长度为 2 的一组 1 。
示例 3：输入：arr = [1], m = 1 输出：1
示例 4：输入：arr = [2,1], m = 2 输出：2
提示：n == arr.length
    1 <= n <= 10^5
    1 <= arr[i] <= n
    arr 中的所有整数 互不相同
    1 <= m <= arr.length

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 数组辅助 O(n) O(n) 
func findLatestStep(arr []int, m int) int {
	res := -1
	temp := make([]int, len(arr)+2)
	M := make(map[int]bool)
	for i := 0; i < len(arr); i++ {
		index := arr[i]
		temp[index] = 1
		left := temp[index-1]
		right := temp[index+1]
		total := 1 + left + right
		temp[index] = total
		temp[index-left] = total
		temp[index+right] = total
		for k := range M {
			if index-left <= k && k < index {
				delete(M, k)
			}
			if index < k && k <= index+right {
				delete(M, k)
			}
		}
		if total == m {
			M[index] = true
		}
		if len(M) > 0 {
			res = i + 1
		}
	}
	return res
}

# 2
func findLatestStep(arr []int, m int) int {
	if len(arr) == m {
		return len(arr)
	}
	res := -1
	temp := make([]int, len(arr)+2)
	for i := 0; i < len(arr); i++ {
		index := arr[i]
		total := 1 + temp[index-1] + temp[index+1]
		// 上一步一定存在m
		if temp[index-1] == m || temp[index+1] == m {
			res = i
		}
		temp[index-temp[index-1]] = total
		temp[index+temp[index+1]] = total
	}
	return res
}

1567.乘积为正数的最长子数组长度(2)

  • 题目

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例  1：输入：nums = [1,-2,-3,4] 输出：4
解释：数组本身乘积就是正数，值为 24 。
示例 2：输入：nums = [0,1,-2,-3,-4] 输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
示例 3：输入：nums = [-1,-2,-3,0,1] 输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
示例 4：输入：nums = [-1,2] 输出：1
示例 5：输入：nums = [1,2,3,5,-6,4,0,10] 输出：4
提示：1 <= nums.length <= 10^5
    -10^9 <= nums[i] <= 10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历+贪心 O(n) O(n)
02 动态规划 O(n) O(n) 
func getMaxLen(nums []int) int {
	arr := make([][]int, 0)
	temp := make([]int, 0)
	res := 0
	total := 1
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			total = total * 1
		} else if nums[i] < 0 {
			total = total * -1
		} else {
			total = 0
		}
		if total > 0 {
			temp = append(temp, 1)
		} else if nums[i] == 0 {
			if len(temp) > 0 {
				arr = append(arr, temp)
				temp = make([]int, 0)
			}
			total = 1
		} else if total < 0 {
			temp = append(temp, -1)
		}
	}
	if len(temp) > 0 {
		arr = append(arr, temp)
	}
	for i := 0; i < len(arr); i++ {
		tempArr := arr[i]
		// 1、寻找最后一个1
		left, right := 0, len(tempArr)-1
		for 0 <= right && tempArr[right] != 1 {
			right--
		}
		res = max(res, right-left+1)
		// 2、寻找前后2个-1
		left, right = 0, len(tempArr)-1
		for left < len(tempArr) && tempArr[left] != -1 {
			left++
		}
		for 0 <= right && tempArr[right] != -1 {
			right--
		}
		res = max(res, right-left)
	}
	return res
}

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

# 2
func getMaxLen(nums []int) int {
	dp := make([][2]int, len(nums)+1)
	res := 0
	for i := 1; i <= len(nums); i++ {
		if nums[i-1] == 0 {
			dp[i][0] = 0
			dp[i][1] = 0
		} else if nums[i-1] > 0 {
			dp[i][0] = dp[i-1][0] + 1
			if dp[i-1][1] != 0 {
				dp[i][1] = dp[i-1][1] + 1
			} else {
				dp[i][1] = 0
			}
		} else {
			if dp[i-1][1] != 0 {
				dp[i][0] = dp[i-1][1] + 1
			} else {
				dp[i][0] = 0
			}
			dp[i][1] = dp[i-1][0] + 1
		}
		res = max(res, dp[i][0])
	}
	return res
}

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

1568.使陆地分离的最少天数(1)

  • 题目

给你一个由若干 0 和 1 组成的二维网格 grid ，其中 0 表示水，而 1 表示陆地。
岛屿由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
一天内，可以将任何单个陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
示例 1：输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]] 输出：2
解释：至少需要 2 天才能得到分离的陆地。
将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。
示例 2：输入：grid = [[1,1]] 输出：2
解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。
示例 3：输入：grid = [[1,0,1,0]] 输出：0
示例 4：输入：grid = [[1,1,0,1,1],
             [1,1,1,1,1],
             [1,1,0,1,1],
             [1,1,0,1,1]]
             输出：1
示例 5：输入：grid = [[1,1,0,1,1],
             [1,1,1,1,1],
             [1,1,0,1,1],
             [1,1,1,1,1]]
输出：2
提示：1 <= grid.length, grid[i].length <= 30
    grid[i][j] 为 0 或 1

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^4) O(n^2) 
func minDays(grid [][]int) int {
	temp := copyArr(grid)
	nums := numIslands(temp)
	if nums >= 2 {
		return 0
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 0 {
				continue
			}
			temp = copyArr(grid)
			temp[i][j] = 0
			if numIslands(temp) == 2 {
				return 1
			}
		}
	}
	return 2
}

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

func dfs(grid [][]int, i, j int) {
	if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) ||
		grid[i][j] == 0 {
		return
	}
	grid[i][j] = 0
	dfs(grid, i+1, j)
	dfs(grid, i-1, j)
	dfs(grid, i, j+1)
	dfs(grid, i, j-1)
}

func copyArr(grid [][]int) [][]int {
	temp := make([][]int, len(grid))
	for i := 0; i < len(grid); i++ {
		temp[i] = make([]int, len(grid[i]))
		for j := 0; j < len(grid[i]); j++ {
			temp[i][j] = grid[i][j]
		}
	}
	return temp
}

1573.分割字符串的方案数(2)

  • 题目

给你一个二进制串 s  （一个只包含 0 和 1 的字符串），
我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 （s1 + s2 + s3 = s）。
请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。
由于答案可能很大，请将它对 10^9 + 7 取余后返回。
示例 1：输入：s = "10101" 输出：4
解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"
示例 2：输入：s = "1001" 输出：0
示例 3：输入：s = "0000" 输出：3
解释：总共有 3 种分割 s 的方法。
"0|0|00"
"0|00|0"
"00|0|0"
示例 4：输入：s = "100100010100110" 输出：12
提示：
    s[i] == '0' 或者 s[i] == '1'
    3 <= s.length <= 10^5

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(n) 
func numWays(s string) int {
	total := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '1' {
			total++
		}
	}
	if total%3 != 0 {
		return 0
	}
	if total == 0 {
		return ((len(s) - 2) * (len(s) - 1) / 2) % 1000000007
	}
	single := total / 3
	first, second := single*1, single*2
	var start, left, right int
	for i := 0; i < len(s); i++ {
		if s[i] == '1' {
			start++
		} else {
			continue
		}
		if start == first {
			left = i + 1
		} else if start == first+1 {
			left = i - left
		}
		if start == second {
			right = i + 1
		} else if start == second+1 {
			right = i - right
		}
	}
	return (left + 1) * (right + 1) % 1000000007
}

1574.删除最短的子数组使剩余数组有序(1)

  • 题目

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。
示例 1：输入：arr = [1,2,3,10,4,2,3,5] 输出：3
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
另一个正确的解为删除子数组 [3,10,4] 。
示例 2：输入：arr = [5,4,3,2,1] 输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，
要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。
示例 3：输入：arr = [1,2,3] 输出：0
解释：数组已经是非递减的了，我们不需要删除任何元素。
示例 4：输入：arr = [1] 输出：0
提示：
    1 <= arr.length <= 10^5
    0 <= arr[i] <= 10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1) 
func findLengthOfShortestSubarray(arr []int) int {
	if len(arr) < 2 {
		return 0
	}
	flag := true
	left := 0
	for i := 1; i < len(arr); i++ {
		if arr[i-1] > arr[i] {
			flag = false
			break
		} else {
			left = i
		}
	}
	if flag == true {
		return 0
	}
	right := len(arr) - 1
	for i := len(arr) - 1; i >= 1; i-- {
		if arr[i-1] <= arr[i] {
			right = i - 1
		} else {
			break
		}
	}
	leftC, rightC := 0, 0
	for i := left; i >= 0 && arr[i] > arr[right]; i-- {
		leftC++
	}
	for i := right; i < len(arr) && arr[i] < arr[left]; i++ {
		rightC++
	}
	res := 0
	res = max(res, (left+1)+(len(arr)-right)-leftC)
	res = max(res, (left+1)+(len(arr)-right)-rightC)
	return len(arr) - res
}

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

1577.数的平方等于两数乘积的方法数(1)

  • 题目

给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：
    类型 1：三元组 (i, j, k) ，如果 nums1[i]2 == nums2[j] * nums2[k] 
    其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
    类型 2：三元组 (i, j, k) ，如果 nums2[i]2 == nums1[j] * nums1[k] 
    其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length
示例 1：输入：nums1 = [7,4], nums2 = [5,2,8,9] 输出：1
解释：类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)
示例 2：输入：nums1 = [1,1], nums2 = [1,1,1] 输出：9
解释：所有三元组都符合题目要求，因为 1^2 = 1 * 1
类型 1：(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2), 
nums1[i]^2 = nums2[j] * nums2[k]
类型 2：(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]
示例 3：输入：nums1 = [7,7,8,3], nums2 = [1,2,9,7] 输出：2
解释：有两个符合题目要求的三元组
类型 1：(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]
类型 2：(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]
示例 4：输入：nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18] 输出：0
解释：不存在符合题目要求的三元组
提示：1 <= nums1.length, nums2.length <= 1000
    1 <= nums1[i], nums2[i] <= 10^5

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^2) O(n) 
func numTriplets(nums1 []int, nums2 []int) int {
	res := 0
	res = res + getCount(nums1, nums2)
	res = res + getCount(nums2, nums1)
	return res
}

func getCount(nums1 []int, nums2 []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(nums1); i++ {
		m[nums1[i]*nums1[i]]++
	}
	for i := 0; i < len(nums2); i++ {
		for j := i + 1; j < len(nums2); j++ {
			res = res + m[nums2[i]*nums2[j]]
		}
	}
	return res
}

1578.避免重复字母的最小删除成本(2)

  • 题目

给你一个字符串 s 和一个整数数组 cost ，其中 cost[i] 是从 s 中删除字符 i 的代价。
返回使字符串任意相邻两个字母不相同的最小删除成本。
请注意，删除一个字符后，删除其他字符的成本不会改变。
示例 1：输入：s = "abaac", cost = [1,2,3,4,5] 输出：3
解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。
示例 2：输入：s = "abc", cost = [1,2,3] 输出：0
解释：无需删除任何字母，因为字符串中不存在相邻两个字母相同的情况。
示例 3：输入：s = "aabaa", cost = [1,2,3,4,1] 输出：2
解释：删除第一个和最后一个字母，得到字符串 ("aba") 。
提示： s.length == cost.length
    1 <= s.length, cost.length <= 10^5
    1 <= cost[i] <= 10^4
    s 中只含有小写英文字母

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历交换 O(n) O(1) 
func minCost(s string, cost []int) int {
	res := 0
	cur := 0
	for i := 0; i < len(s)-1; i++ {
		if s[cur] == s[i+1] {
			res = res + min(cost[cur], cost[i+1])
			if cost[cur] < cost[i+1] {
				cur = i + 1 // 相同，保存较大的
			}
		} else {
			cur = i + 1
		}
	}
	return res
}

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

# 2
func minCost(s string, cost []int) int {
	res := 0
	for i := 0; i < len(s)-1; i++ {
		if s[i] == s[i+1] {
			res = res + min(cost[i], cost[i+1])
			if cost[i] > cost[i+1] {
				cost[i], cost[i+1] = cost[i+1], cost[i] // 相同，把较大的存在后面
			}
		}
	}
	return res
}

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

1583.统计不开心的朋友(1)

  • 题目

给你一份 n 位朋友的亲近程度列表，其中 n 总是 偶数 。
对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。
换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。
每个列表中的朋友均以 0 到 n-1 之间的整数表示。
所有的朋友被分成几对，配对情况以列表 pairs 给出，其中 pairs[i] = [xi, yi] 表示 xi 与 yi 配对，
且 yi 与 xi 配对。
但是，这样的配对情况可能会是其中部分朋友感到不开心。在 x 与 y 配对且 u 与 v 配对的情况下，
如果同时满足下述两个条件，x 就会不开心：
    x 与 u 的亲近程度胜过 x 与 y，且
    u 与 x 的亲近程度胜过 u 与 v
返回 不开心的朋友的数目 。
示例 1：输入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]],
pairs = [[0, 1], [2, 3]] 输出：2
解释：朋友 1 不开心，因为：
- 1 与 0 配对，但 1 与 3 的亲近程度比 1 与 0 高，且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心，因为：
- 3 与 2 配对，但 3 与 1 的亲近程度比 3 与 2 高，且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。
示例 2：输入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]] 输出：0
解释：朋友 0 和 1 都开心。
示例 3：输入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]],
pairs = [[1, 3], [0, 2]] 输出：4
提示：2 <= n <= 500
    n 是偶数
    preferences.length == n
    preferences[i].length == n - 1
    0 <= preferences[i][j] <= n - 1
    preferences[i] 不包含 i
    preferences[i] 中的所有值都是独一无二的
    pairs.length == n/2
    pairs[i].length == 2
    xi != yi
    0 <= xi, yi <= n - 1
    每位朋友都 恰好 被包含在一对中

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(n^2) 
func unhappyFriends(n int, preferences [][]int, pairs [][]int) int {
	arr := make(map[int]map[int]int)
	for i := 0; i < n; i++ {
		arr[i] = make(map[int]int)
	}
	for i := 0; i < len(preferences); i++ {
		total := n
		for j := 0; j < len(preferences[i]); j++ {
			arr[i][preferences[i][j]] = total
			total = total - 1
		}
	}
	m := make(map[int]bool)
	for i := 0; i < len(pairs); i++ {
		x, y := pairs[i][0], pairs[i][1]
		x1, y1 := pairs[i][1], pairs[i][0]
		for j := 0; j < len(pairs); j++ {
			if i == j {
				continue
			}
			u, v := pairs[j][0], pairs[j][1]
			u1, v1 := pairs[j][1], pairs[j][0]
			if arr[x][u] > arr[x][y] && arr[u][x] > arr[u][v] {
				m[x] = true
			}
			if arr[x1][u] > arr[x1][y1] && arr[u][x1] > arr[u][v] {
				m[x1] = true
			}
			if arr[x][u1] > arr[x][y] && arr[u1][x] > arr[u1][v1] {
				m[x] = true
			}
			if arr[x1][u1] > arr[x1][y1] && arr[u1][x1] > arr[u1][v1] {
				m[x1] = true
			}
		}
	}
	return len(m)
}

1584.连接所有点的最小费用(3)

  • 题目

给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。
连接点[xi, yi] 和点[xj, yj]的费用为它们之间的 曼哈顿距离：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有一条简单路径时，才认为所有点都已连接。
示例 1：输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 输出：20
解释：我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：输入：points = [[3,12],[-2,5],[-4,1]] 输出：18
示例 3：输入：points = [[0,0],[1,1],[1,0],[-1,1]] 输出：4
示例 4：输入：points = [[-1000000,-1000000],[1000000,1000000]] 输出：4000000
示例 5：输入：points = [[0,0]] 输出：0
提示：1 <= points.length <= 1000
-106<= xi, yi <= 106
所有点(xi, yi)两两不同。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 Kruskal-排序+并查集 O(n^2log(n)) O(n^2)
02 Prime O(n^2) O(n^2)
03 Prime+堆优化 O(nlog(n)) O(n^2) 
func minCostConnectPoints(points [][]int) int {
	n := len(points)
	arr := make([][3]int, 0)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			arr = append(arr, [3]int{i, j, dis(points[i], points[j])}) // a=>b c
		}
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][2] < arr[j][2]
	})
	return Kruskal(n, arr)
}

func Kruskal(n int, arr [][3]int) int {
	res := 0
	fa = Init(n)
	count := 0
	for i := 0; i < len(arr); i++ {
		a, b, c := arr[i][0], arr[i][1], arr[i][2]
		if query(a, b) == false {
			union(a, b)
			res = res + c
			count++
			if count == n-1 {
				break
			}
		}
	}
	return res
}

var fa []int

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

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

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

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

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

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

# 2
func minCostConnectPoints(points [][]int) int {
	n := len(points)
	arr := make([][]int, n) // 邻接矩阵
	for i := 0; i < n; i++ {
		arr[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			c := dis(points[i], points[j])
			arr[i][j] = c
			arr[j][i] = c
		}
	}
	return Prime(arr)
}

// Prime：传入邻接矩阵
func Prime(arr [][]int) int {
	res := 0
	n := len(arr)
	visited := make([]bool, n)
	target := 0
	visited[target] = true // 任选1个即可
	dis := make([]int, n)  // 任意选择的节点：到其它点的距离
	for i := 0; i < n; i++ {
		dis[i] = arr[target][i]
	}
	for i := 1; i < n; i++ { // 执行n-1次：n-1条边
		var index int
		minValue := math.MaxInt32
		for j := 0; j < n; j++ { // 寻找：未访问过的最短边
			if visited[j] == false && dis[j] < minValue {
				minValue = dis[j]
				index = j
			}
		}
		visited[index] = true    // 标记为访问过的点
		res = res + minValue     // 加上最短边
		for j := 0; j < n; j++ { // 更新距离：以index为起点，更新生成树到每一个非树顶点的距离
			if visited[j] == false && dis[j] > arr[index][j] {
				dis[j] = arr[index][j]
			}
		}
	}
	return res
}

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

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

# 3
func minCostConnectPoints(points [][]int) int {
	n := len(points)
	arr := make([][]int, n) // 邻接矩阵
	for i := 0; i < n; i++ {
		arr[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			c := dis(points[i], points[j])
			arr[i][j] = c
			arr[j][i] = c
		}
	}
	return Prime(arr)
}

// Prime-堆优化-邻接表
func Prime(arr [][]int) int {
	res := 0
	n := len(arr)
	visited := make([]bool, n)
	target := 0
	dis := make([]int, n) // 任意选择的节点：到其它点的距离
	for i := 0; i < n; i++ {
		dis[i] = math.MaxInt32
	}
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	heap.Push(&intHeap, [2]int{0, target}) // [2]int{距离，下标}
	for intHeap.Len() > 0 {
		node := heap.Pop(&intHeap).([2]int)
		minValue, index := node[0], node[1]
		if visited[index] == true {
			continue
		}
		visited[index] = true
		res = res + minValue
		for j := 0; j < len(arr[index]); j++ {
			if visited[j] == false && dis[j] > arr[index][j] {
				dis[j] = arr[index][j]
				heap.Push(&intHeap, [2]int{arr[index][j], j})
			}
		}
	}
	return res
}

type IntHeap [][2]int

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

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

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

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

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

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

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

1589.所有排列中的最大和(1)

  • 题目

有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。
第 i 个查询求 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的结果 ，
starti 和 endi 数组索引都是 从 0 开始 的。
你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。
由于答案可能会很大，请你将它对 109 + 7 取余 后返回。
示例 1：输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]] 输出：19
解释：一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为：8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。
示例 2：输入：nums = [1,2,3,4,5,6], requests = [[0,1]] 输出：11
解释：一个总和最大的排列为 [6,5,4,3,2,1] ，查询和为 [11]。
示例 3：输入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]] 输出：47
解释：一个和最大的排列为 [4,10,5,3,2,1] ，查询结果分别为 [19,18,10]。
提示：n == nums.length
    1 <= n <= 105
    0 <= nums[i] <= 105
    1 <= requests.length <= 105
    requests[i].length == 2
    0 <= starti <= endi < n

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 差分+排序 O(nlog(n)) O(n) 
func maxSumRangeQuery(nums []int, requests [][]int) int {
	d := make([]int, len(nums)+1)
	arr := make([]int, len(nums))
	for i := 0; i < len(requests); i++ {
		start := requests[i][0]
		end := requests[i][1]
		d[start]++
		d[end+1]--
	}
	arr[0] = d[0]
	for i := 1; i < len(nums); i++ {
		arr[i] = d[i] + arr[i-1]
	}
	sort.Ints(arr)
	sort.Ints(nums)
	res := 0
	for i := len(arr) - 1; i >= 0; i-- {
		res = (res + arr[i]*nums[i]) % 1000000007
	}
	return res
}

1590.使数组和能被P整除(2)

  • 题目

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 
不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
子数组 定义为原数组中连续的一组元素。
示例 1：输入：nums = [3,1,4,2], p = 6 输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
示例 2：输入：nums = [6,3,5,2], p = 9 输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。
示例 3：输入：nums = [1,2,3], p = 3 输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。
示例  4：输入：nums = [1,2,3], p = 7 输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。
示例 5：输入：nums = [1000000000,1000000000,1000000000], p = 3 输出：0
提示： 1 <= nums.length <= 105
    1 <= nums[i] <= 109
    1 <= p <= 109

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和 O(n) O(n)
02 哈希辅助 O(n) O(n) 
func minSubarray(nums []int, p int) int {
	n := len(nums)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		arr[i+1] = (arr[i] + nums[i]) % p
	}
	if arr[n] == 0 {
		return 0
	}
	targetValue := arr[n]
	res := n
	m := make(map[int]int)
	m[0] = -1
	for i := 0; i < n; i++ {
		target := (arr[i+1] - targetValue + p) % p
		if value, ok := m[target]; ok {
			if res > i-value {
				res = i - value
			}
		}
		m[arr[i+1]] = i
	}
	if res == n {
		return -1
	}
	return res
}

# 2
func minSubarray(nums []int, p int) int {
	n := len(nums)
	targetValue := 0
	for i := 0; i < n; i++ {
		targetValue = (targetValue + nums[i]) % p
	}
	if targetValue == 0 {
		return 0
	}
	res := n
	m := make(map[int]int)
	m[0] = -1
	total := 0
	for i := 0; i < n; i++ {
		total = (total + nums[i] + p) % p
		target := (total - targetValue + p) % p
		if value, ok := m[target]; ok {
			if res > i-value {
				res = i - value
			}
		}
		m[total] = i
	}
	if res == n {
		return -1
	}
	return res
}

1593.拆分字符串使唯一子字符串的数目最大(1)

  • 题目

给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。
但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。
示例 1：输入：s = "ababccc" 输出：5
解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。
像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，
因为其中的 'a' 和 'b' 都出现了不止一次。
示例 2：输入：s = "aba" 输出：2
解释：一种最大拆分方法为 ['a', 'ba'] 。
示例 3：输入：s = "aa" 输出：1
解释：无法进一步拆分字符串。
提示：1 <= s.length <= 16
    s 仅包含小写英文字母。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 回溯 O(n*2^n) O(n) 
var res int

func maxUniqueSplit(s string) int {
	res = 1
	dfs(s, make(map[string]bool), make([]string, 0))
	return res
}

func dfs(s string, m map[string]bool, arr []string) {
	if len(s) == 0 {
		if len(arr) > res {
			res = len(arr)
		}
		return
	}
	for i := 0; i < len(s); i++ {
		newStr := s[:i+1]
		if m[newStr] == false {
			m[newStr] = true
			dfs(s[i+1:], m, append(arr, newStr))
			m[newStr] = false
		}
	}
}

1594.矩阵的最大非负积(2)

  • 题目

给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，
每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，
找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为负数，则返回 -1 。
注意，取余是在得到最大积之后执行的。
示例 1：输入：grid = [[-1,-2,-3],
             [-2,-3,-3],
             [-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1
示例 2：输入：grid = [[1,-2,1],
             [1,-2,1],
             [3,-4,1]]
输出：8
解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)
示例 3：输入：grid = [[1, 3],
             [0,-4]]
输出：0
解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)
示例 4：输入：grid = [[ 1, 4,4,0],
             [-2, 0,0,1],
             [ 1,-1,1,1]]
输出：2
解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)
提示：1 <= rows, cols <= 15
    -4 <= grid[i][j] <= 4

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^2) O(n^2)
02 递归 O(n^2) O(n) 
func maxProductPath(grid [][]int) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])
	dp := make([][][2]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([][2]int, m)
	}
	dp[0][0][0] = grid[0][0] // 负数
	dp[0][0][1] = grid[0][0] // 正数
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 && j != 0 {
				dp[i][j][0] = min(dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])
				dp[i][j][1] = max(dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])
			} else if i != 0 && j == 0 {
				dp[i][j][0] = min(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j])
				dp[i][j][1] = max(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j])
			} else if i != 0 && j != 0 {
				if grid[i][j] > 0 {
					dp[i][j][0] = min(min(dp[i-1][j][0], dp[i][j-1][0]), min(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
					dp[i][j][1] = max(max(dp[i-1][j][0], dp[i][j-1][0]), max(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
				} else {
					dp[i][j][0] = max(max(dp[i-1][j][0], dp[i][j-1][0]), max(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
					dp[i][j][1] = min(min(dp[i-1][j][0], dp[i][j-1][0]), min(dp[i-1][j][1], dp[i][j-1][1])) * grid[i][j]
				}
			}
		}
	}
	a, b := dp[n-1][m-1][0], dp[n-1][m-1][1]
	if a == 0 || b == 0 {
		return max(0, max(a, b))
	}
	if a > 0 && b > 0 {
		return max(a, b) % 1000000007
	}
	if b > 0 {
		return b % 1000000007
	}
	if a > 0 {
		return a % 1000000007
	}
	return -1
}

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
}

# 2
var res int

func maxProductPath(grid [][]int) int {
	if len(grid) == 0 {
		return 0
	}
	res = -1
	dfs(grid, 0, 0, 1)
	if res < 0 {
		return -1
	}
	return res % 1000000007
}

func dfs(grid [][]int, i, j int, value int) {
	value = value * grid[i][j]
	if grid[i][j] == 0 {
		if value > res {
			res = value
		}
		return
	}
	if i == len(grid)-1 && j == len(grid[0])-1 {
		if value > res {
			res = value
		}
	}
	if i < len(grid)-1 {
		dfs(grid, i+1, j, value)
	}
	if j < len(grid[0])-1 {
		dfs(grid, i, j+1, value)
	}
}

1599.经营摩天轮的最大利润(2)

  • 题目

你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。
你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。
摩天轮每次轮转都恰好转动 1 / 4 周。
给你一个长度为 n 的数组 customers ， 
customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。
这也意味着你必须在新游客到来前轮转 i 次。
每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，
他们就会离开座舱结束游玩。
你可以随时停下摩天轮，即便是 在服务所有游客之前 。
如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。
注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。
返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回 -1 。
示例 1：输入：customers = [8,3], boardingCost = 5, runningCost = 6 输出：3
解释：座舱上标注的数字是该座舱的当前游客数。
1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4 * $5 - 1 * $6 = $14 。
2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8 * $5 - 2 * $6 = $28 。
3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11 * $5 - 3 * $6 = $37 。
轮转 3 次得到最大利润，最大利润为 $37 。
示例 2：输入：customers = [10,9,6], boardingCost = 6, runningCost = 4 输出：7
解释：1. 10 位游客抵达，4 位登舱，6 位等待下一舱，摩天轮轮转。当前利润为 4 * $6 - 1 * $4 = $20 。
2. 9 位游客抵达，4 位登舱，11 位等待（2 位是先前就在等待的，9 位新加入等待的），摩天轮轮转。
当前利润为 8 * $6 - 2 * $4 = $40 。
3. 最后 6 位游客抵达，4 位登舱，13 位等待，摩天轮轮转。当前利润为 12 * $6 - 3 * $4 = $60 。
4. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 * $6 - 4 * $4 = $80 。
5. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 20 * $6 - 5 * $4 = $100 。
6. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 24 * $6 - 6 * $4 = $120 。
7. 1 位登舱，摩天轮轮转。当前利润为 25 * $6 - 7 * $4 = $122 。
轮转 7 次得到最大利润，最大利润为$122 。
示例 3：输入：customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92 输出：-1
解释：1. 3 位游客抵达，3 位登舱，0 位等待，摩天轮轮转。当前利润为 3 * $1 - 1 * $92 = -$89 。
2. 4 位游客抵达，4 位登舱，0 位等待，摩天轮轮转。当前利润为 is 7 * $1 - 2 * $92 = -$177 。
3. 0 位游客抵达，0 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 3 * $92 = -$269 。
4. 5 位游客抵达，4 位登舱，1 位等待，摩天轮轮转。当前利润为 12 * $1 - 4 * $92 = -$356 。
5. 1 位游客抵达，2 位登舱，0 位等待，摩天轮轮转。当前利润为 13 * $1 - 5 * $92 = -$447 。
利润永不为正，所以返回 -1 。
示例 4：输入：customers = [10,10,6,4,7], boardingCost = 3, runningCost = 8 输出：9
解释：1. 10 位游客抵达，4 位登舱，6 位等待，摩天轮轮转。当前利润为 4 * $3 - 1 * $8 = $4 。
2. 10 位游客抵达，4 位登舱，12 位等待，摩天轮轮转。当前利润为 8 * $3 - 2 * $8 = $8 。
3. 6 位游客抵达，4 位登舱，14 位等待，摩天轮轮转。当前利润为 12 * $3 - 3 * $8 = $12 。
4. 4 位游客抵达，4 位登舱，14 位等待，摩天轮轮转。当前利润为 16 * $3 - 4 * $8 = $16 。
5. 7 位游客抵达，4 位登舱，17 位等待，摩天轮轮转。当前利润为 20 * $3 - 5 * $8 = $20 。
6. 4 位登舱，13 位等待，摩天轮轮转。当前利润为 24 * $3 - 6 * $8 = $24 。
7. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 28 * $3 - 7 * $8 = $28 。
8. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 32 * $3 - 8 * $8 = $32 。
9. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 36 * $3 - 9 * $8 = $36 。
10. 1 位登舱，0 位等待，摩天轮轮转。当前利润为 37 * $3 - 10 * $8 = $31 。
轮转 9 次得到最大利润，最大利润为 $36 。
提示：n == customers.length
    1 <= n <= 105
    0 <= customers[i] <= 50
    1 <= boardingCost, runningCost <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 转数组模拟 O(n) O(n)
02 遍历 O(n) O(1) 
func minOperationsMaxProfit(customers []int, boardingCost int, runningCost int) int {
	n := len(customers)
	arr := make([]int, 0)
	total := 0
	for i := 0; i < len(customers)-1; i++ {
		total = total + customers[i]
		if total > 4 {
			arr = append(arr, 4)
			total = total - 4
			customers[i+1] = customers[i+1] + total
			total = 0
		} else {
			arr = append(arr, total)
			total = 0
		}
	}
	if customers[n-1] > 0 {
		for customers[n-1] > 4 {
			arr = append(arr, 4)
			customers[n-1] = customers[n-1] - 4
		}
		arr = append(arr, customers[n-1])
	}
	maxValue := 0
	res := -1
	total = 0
	for i := 0; i < len(arr); i++ {
		total = total + arr[i]
		profit := total*boardingCost - (i+1)*runningCost
		if profit > 0 {
			if profit > maxValue {
				maxValue = profit
				res = i + 1
			}
		}
	}
	return res
}

# 2
func minOperationsMaxProfit(customers []int, boardingCost int, runningCost int) int {
	maxValue := 0
	res := -1
	total := 0
	i := 0
	profit := 0
	for total > 0 || i < len(customers) {
		if i < len(customers) {
			total = total + customers[i]
		}
		count := min(total, 4)
		total = total - count
		profit = profit + count*boardingCost - runningCost
		if profit > maxValue {
			maxValue = profit
			res = i + 1
		}
		i++
	}
	return res
}

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

1600.皇位继承顺序(2)

  • 题目

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。
这个王国有一个明确规定的皇位继承顺序，第一继承人总是国王自己。
我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。
Successor(x, curOrder):
    如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
        如果 x 是国王，那么返回 null
        否则，返回 Successor(x 的父亲, curOrder)
    否则，返回 x 不在 curOrder 中最年长的孩子
比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。
    一开始， curOrder 为 ["king"].
    调用 Successor(king, curOrder) ，返回 Alice ，
    所以我们将 Alice 放入 curOrder 中，得到 ["king", "Alice"] 。
    调用 Successor(Alice, curOrder) ，返回 Jack ，
    所以我们将 Jack 放入 curOrder 中，得到 ["king", "Alice", "Jack"] 。
    调用 Successor(Jack, curOrder) ，返回 Bob ，
    所以我们将 Bob 放入 curOrder 中，得到 ["king", "Alice", "Jack", "Bob"] 。
    调用 Successor(Bob, curOrder) ，返回 null 。
    最终得到继承顺序为 ["king", "Alice", "Jack", "Bob"] 。
通过以上的函数，我们总是能得到一个唯一的继承顺序。
请你实现 ThroneInheritance 类：
    ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。
    国王的名字作为构造函数的参数传入。
    void birth(string parentName, 
    string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
    void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，
    也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
    string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。
示例：输入：
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", 
"getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], 
["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"],
[null], ["bob"], [null]]
输出：[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", 
"alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", 
"catherine"]]
解释：
ThroneInheritance t= new ThroneInheritance("king"); // 继承顺序：king
t.birth("king", "andy"); // 继承顺序：king > andy
t.birth("king", "bob"); // 继承顺序：king > andy > bob
t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex",
"asha", "catherine"]
t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > 
asha > catherine
t.getInheritanceOrder(); 
// 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]
提示：
    1 <= kingName.length, parentName.length, childName.length, name.length <= 15
    kingName，parentName， childName 和 name 仅包含小写英文字母。
    所有的参数 childName 和 kingName 互不相同。
    所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。
    每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。
    最多调用 105 次birth 和 death 。
    最多调用 10 次 getInheritanceOrder 。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前序遍历 O(n) O(n)
02 递归 O(n) O(n) 
type Node struct {
	Name  string
	Child []*Node
}

type ThroneInheritance struct {
	isDead map[string]bool
	m      map[string]*Node
	king   *Node
}

func Constructor(kingName string) ThroneInheritance {
	node := &Node{
		Name:  kingName,
		Child: make([]*Node, 0),
	}
	res := ThroneInheritance{
		king:   node,
		m:      map[string]*Node{},
		isDead: map[string]bool{},
	}
	res.m[kingName] = node
	return res
}

func (this *ThroneInheritance) Birth(parentName string, childName string) {
	node := this.m[parentName]
	child := &Node{
		Name:  childName,
		Child: make([]*Node, 0),
	}
	this.m[childName] = child
	node.Child = append(node.Child, child)
}

func (this *ThroneInheritance) Death(name string) {
	this.isDead[name] = true
}

func (this *ThroneInheritance) GetInheritanceOrder() []string {
	res := make([]string, 0)
	root := this.king
	stack := make([]*Node, 0)
	stack = append(stack, root)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if this.isDead[node.Name] == false {
			res = append(res, node.Name)
		}
		if len(node.Child) > 0 {
			for i := len(node.Child) - 1; i >= 0; i-- {
				stack = append(stack, node.Child[i])
			}
		}
	}
	return res
}

# 2
type ThroneInheritance struct {
	isDead   map[string]bool
	children map[string][]string
	king     string
}

func Constructor(kingName string) ThroneInheritance {
	return ThroneInheritance{
		isDead:   make(map[string]bool),
		children: make(map[string][]string),
		king:     kingName,
	}
}

func (this *ThroneInheritance) Birth(parentName string, childName string) {
	this.children[parentName] = append(this.children[parentName], childName)
}

func (this *ThroneInheritance) Death(name string) {
	this.isDead[name] = true
}

func (this *ThroneInheritance) GetInheritanceOrder() []string {
	return dfs(this, this.king)
}

func dfs(this *ThroneInheritance, name string) []string {
	res := make([]string, 0)
	if this.isDead[name] == false {
		res = append(res, name)
	}
	for _, child := range this.children[name] {
		res = append(res, dfs(this, child)...)
	}
	return res
}

1501-1600-Hard

1510.石子游戏IV(1)

  • 题目

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
示例 1：输入：n = 1 输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：输入：n = 2 输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：输入：n = 4 输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：输入：n = 7 输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，
Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，
Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：输入：n = 17 输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
提示： 1 <= n <= 10^5

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^(3/2)) O(n) 
func winnerSquareGame(n int) bool {
	dp := make([]bool, n+1)
	count := 1
	for i := 1; i <= n; i++ {
		if count*count == i {
			dp[i] = true
			count++
			continue
		}
		for j := 1; j*j < i; j++ {
			if dp[i-j*j] == false {
				dp[i] = true
				break
			}
		}
	}
	return dp[n]
}

1526.形成目标数组的子数组最少增加次数(1)

  • 题目

给你一个整数数组 target 和一个数组 initial ，initial 数组与 target  数组有同样的维度，
且一开始全部为 0 。
请你返回从 initial 得到  target 的最少操作次数，每次操作需遵循以下规则：
    在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
答案保证在 32 位有符号整数以内。
示例 1：输入：target = [1,2,3,2,1] 输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。
示例 2：输入：target = [3,1,1,2] 输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。
示例 3：输入：target = [3,1,5,4,2] 输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。
示例 4：输入：target = [1,1,1,1] 输出：1
提示：
    1 <= target.length <= 10^5
    1 <= target[i] <= 10^5

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1) 
func minNumberOperations(target []int) int {
	res := target[0]
	for i := 1; i < len(target); i++ {
		res = res + max(target[i]-target[i-1], 0)
	}
	return res
}

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

1537.最大得分(1)

  • 题目

你有两个 有序且数组内元素互不相同的数组nums1 和nums2。
一条合法路径定义如下：
选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
从左到右遍历当前数组。
如果你遇到了 nums1和 nums2中都存在的值，
那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
得分定义为合法路径中不同数字的和。
请你返回所有可能合法路径中的最大得分。
由于答案可能很大，请你将它对 10^9 + 7 取余后返回。
示例 1：输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9] 输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10]。
示例 2：输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100] 输出：109
解释：最大得分由路径 [1,3,5,100] 得到。
示例 3：输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10] 输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。
示例 4：输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12] 输出：61
提示：1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 和nums2都是严格递增的数组。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1) 
func maxSum(nums1 []int, nums2 []int) int {
	n := len(nums1)
	m := len(nums2)
	a, b := 0, 0
	i, j := 0, 0
	for i < n || j < m {
		if i < n && j < m {
			if nums1[i] < nums2[j] {
				a = a + nums1[i]
				i++
			} else if nums1[i] > nums2[j] {
				b = b + nums2[j]
				j++
			} else {
				temp := max(a, b) + nums1[i] // 遇到相同值，取较大值
				a = temp
				b = temp
				i++
				j++
			}
		} else if i < n {
			a = a + nums1[i]
			i++
		} else if j < m {
			b = b + nums2[j]
			j++
		}
	}
	return max(a, b) % 1000000007
}

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

1542.找出最长的超赞子字符串(1)

  • 题目

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件：
该字符串是 s 的一个非空子字符串
进行任意次数的字符交换后，该字符串可以变成一个回文字符串
示例 1：输入：s = "3242415" 输出：5
解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
示例 2：输入：s = "12345678" 输出：1
示例 3：输入：s = "213123" 输出：6
解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
示例 4：输入：s = "00" 输出：2
提示：1 <= s.length <= 10^5
s 仅由数字组成

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和+位运算 O(n) O(1) 
func longestAwesome(s string) int {
	res := 0
	n := len(s)
	m := make(map[int]int) // 保存每个状态第1次出现的下标
	m[0] = -1              // 0对应的下标
	cur := 0
	for i := 0; i < n; i++ {
		value := int(s[i] - '0')
		cur = cur ^ (1 << value)
		if index, ok := m[cur]; ok { // 相同的情况
			res = max(res, i-index)
		} else {
			m[cur] = i
		}
		for j := 0; j < 10; j++ { // 相差1位的情况
			if index, ok := m[cur^(1<<j)]; ok {
				res = max(res, i-index)
			}
		}
	}
	return res
}

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

1547.切棍子的最小成本(3)

  • 题目

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。
对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。
请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1：输入：n = 7, cuts = [1,3,4,5] 输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。
第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，
最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。
示例 2：输入：n = 9, cuts = [5,6,1,4,2] 输出：22
解释：如果按给定的顺序切割，则总成本为 25 。
总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。
提示：2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts 数组中的所有整数都 互不相同

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^3) O(n^2)
02 动态规划 O(n^3) O(n^2)
03 动态规划-递归 O(n^3) O(n^2) 
func minCost(n int, cuts []int) int {
	m := len(cuts)
	cuts = append(cuts, 0, n)
	sort.Ints(cuts)
	dp := make([][]int, m+2) // dp[L][R]为切割以L,R为左右端点的最小成本
	for i := 0; i < m+2; i++ {
		dp[i] = make([]int, m+2)
	}
	for i := m; i >= 1; i-- {
		for j := i; j <= m; j++ {
			dp[i][j] = math.MaxInt32
			for k := i; k <= j; k++ { // 枚举切割点
				dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])
			}
			dp[i][j] = dp[i][j] + cuts[j+1] - cuts[i-1]
		}
	}
	return dp[1][m]
}

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

# 2
func minCost(n int, cuts []int) int {
	m := len(cuts)
	cuts = append(cuts, 0, n)
	sort.Ints(cuts)
	dp := make([][]int, m+2) // dp[L][R]为切割以L,R为左右端点的最小成本
	for i := 0; i < m+2; i++ {
		dp[i] = make([]int, m+2)
	}
	for length := 2; length <= m+1; length++ { // 枚举长度
		for i := 1; i <= m; i++ {
			j := i + length - 2
			if j > m {
				break
			}
			dp[i][j] = math.MaxInt32
			for k := i; k <= j; k++ { // 枚举切割点
				dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])
			}
			dp[i][j] = dp[i][j] + cuts[j+1] - cuts[i-1]
		}
	}
	return dp[1][m]
}

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

# 3
var dp [][]int

func minCost(n int, cuts []int) int {
	m := len(cuts)
	cuts = append(cuts, 0, n)
	sort.Ints(cuts)
	dp = make([][]int, m+2) // dp[L][R]为切割以L,R为左右端点的最小成本
	for i := 0; i < m+2; i++ {
		dp[i] = make([]int, m+2)
	}
	return dfs(cuts, 1, m)
}

func dfs(cuts []int, i, j int) int {
	if dp[i][j] != 0 {
		return dp[i][j]
	}
	if i > j {
		return 0
	}
	if i == j {
		return cuts[j+1] - cuts[i-1]
	}
	dp[i][j] = math.MaxInt32
	for k := i; k <= j; k++ {
		dp[i][j] = min(dp[i][j], dfs(cuts, i, k-1)+dfs(cuts, k+1, j))
	}
	dp[i][j] = dp[i][j] + cuts[j+1] - cuts[i-1]
	return dp[i][j]
}

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

1553.吃掉N个橘子的最少天数(2)

  • 题目

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
    吃掉一个橘子。
    如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
    如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
示例 1：输入：n = 10 输出：4
解释：你总共有 10 个橘子。
第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。
示例 2：输入：n = 6 输出：3
解释：你总共有 6 个橘子。
第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。
示例 3：输入：n = 1 输出：1
示例 4：输入：n = 56 输出：6
提示： 1 <= n <= 2*10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划-递归 O(log(n)) O(log(n))
02 广度优先搜索 O(log(n)) O(log(n)) 
var dp map[int]int

func minDays(n int) int {
	dp = make(map[int]int)
	dp[0] = 0
	dp[1] = 1
	return dfs(n)
}

func dfs(n int) int {
	if value, ok := dp[n]; ok {
		return value
	}
	// 吃n/2的情况，先吃掉n%2，然后就剩下dfs(n/2)+1
	// 吃n/3的情况，先吃点n%3, 然后就剩下dfs(n/3)+1
	dp[n] = min(dfs(n/2)+n%2+1, dfs(n/3)+n%3+1)
	return dp[n]
}

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

# 2
func minDays(n int) int {
	m := make(map[int]bool)
	queue := make([]int, 0)
	queue = append(queue, n)
	res := 0
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			day := queue[i]
			if day == 0 {
				return res
			}
			if day%3 == 0 && m[day/3] == false {
				queue = append(queue, day/3)
				m[day/3] = true
			}
			if day%2 == 0 && m[day/2] == false {
				queue = append(queue, day/2)
				m[day/2] = true
			}
			if m[day-1] == false {
				queue = append(queue, day-1)
				m[day-1] = true
			}
		}
		res++
		queue = queue[length:]
	}
	return res
}

1559.二维网格图中探测环(1)

  • 题目

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，
你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。
同时，你也不能回到上一次移动时所在的格子。比方说，环  (1, 1) -> (1, 2) -> (1, 1) 是不合法的，
因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。
如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。
示例 1：
输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：
示例 2：
输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：
示例 3：输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]] 输出：false
提示： m == grid.length
    n == grid[i].length
    1 <= m <= 500
    1 <= n <= 500
    grid 只包含小写英文字母。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^2) O(n^2) 
var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

var visited map[[2]int]bool

func containsCycle(grid [][]byte) bool {
	n, m := len(grid), len(grid[0])
	visited = make(map[[2]int]bool)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if visited[[2]int{i, j}] == true {
				continue
			}
			start := grid[i][j]
			if dfs(grid, start, i, j, -1, -1) == true {
				return true
			}
		}
	}
	return false
}

// x,y 当前节点， pX,pY 父节点
func dfs(grid [][]byte, start byte, x, y int, pX, pY int) bool {
	visited[[2]int{x, y}] = true
	for i := 0; i < 4; i++ {
		newX := x + dx[i]
		newY := y + dy[i]
		if newX < 0 || newX >= len(grid) || newY < 0 || newY >= len(grid[0]) ||
			(newX == pX && newY == pY) {
			continue
		}
		if start == grid[newX][newY] {
			if visited[[2]int{newX, newY}] == true {
				return true
			}
			result := dfs(grid, start, newX, newY, x, y)
			if result == true {
				return true
			}
		}
	}
	return false
}

1563.石子游戏V(2)

  • 题目

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；
Bob 负责计算每一行的值，即此行中所有石子的值的总和。
Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。
如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。
返回 Alice 能够获得的最大分数 。
示例 1：输入：stoneValue = [6,2,3,4,5,5] 输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。
左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。
游戏结束，因为这行只剩下一块石头了。
示例 2：输入：stoneValue = [7,7,7,7,7,7,7] 输出：28
示例 3：输入：stoneValue = [4] 输出：0
提示：

    1 <= stoneValue.length <= 500
    1 <= stoneValue[i] <= 10^6

  • 解题思路

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

func stoneGameV(stoneValue []int) int {
	n := len(stoneValue)
	sum := make([]int, n+1)
	sum[0] = stoneValue[0]
	for i := 1; i < n; i++ {
		sum[i] = sum[i-1] + stoneValue[i]
	}
    // dp[i][j]：代表从i到j区间,Alice分数最大值
	dp := make([][]int, n+1)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n+1)
	}
	// 长度从2开始到N依次枚举
	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			for k := i; k <= j; k++ {
				if i > k || k+1 > j {
					continue
				}
				left := dp[i][k]
				right := dp[k+1][j]
				leftSum := sum[k]
				if i > 0 {
					leftSum = sum[k] - sum[i-1]
				}
				rightSum := sum[j] - sum[k]
				if leftSum == rightSum {
					dp[i][j] = max(dp[i][j], max(left, right)+leftSum)
				} else if leftSum > rightSum {
					dp[i][j] = max(dp[i][j], right+rightSum)
				} else if leftSum < rightSum {
					dp[i][j] = max(dp[i][j], left+leftSum)
				}
			}
		}
	}
	return dp[0][n-1]
}

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

# 2
var dp [][]int
var sum []int

func stoneGameV(stoneValue []int) int {
	n := len(stoneValue)
	sum = make([]int, n+1)
	sum[0] = 0
	for i := 0; i < n; i++ {
		sum[i+1] = sum[i] + stoneValue[i]
	}
	dp = make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
		for j := 0; j <= n; j++ {
			dp[i][j] = -1
		}
	}
	return dfs(1, n)
}

func dfs(left, right int) int {
	if dp[left][right] != -1 {
		return dp[left][right]
	}
	if left == right {
		dp[left][right] = 0
	} else {
		value := 0
		for i := left; i < right; i++ {
			leftSum := sum[i] - sum[left-1]
			rightSum := sum[right] - sum[i]
			if leftSum < rightSum {
				value = max(value, leftSum+dfs(left, i))
			} else if leftSum > rightSum {
				value = max(value, rightSum+dfs(i+1, right))
			} else {
				value = max(value, max(dfs(left, i), dfs(i+1, right))+leftSum)
			}
		}
		dp[left][right] = value
	}
	return dp[left][right]
}

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

1579.保证图可完全遍历(1)

  • 题目

Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：
类型 1：只能由 Alice 遍历。
类型 2：只能由 Bob 遍历。
类型 3：Alice 和 Bob 都可以遍历。
给你一个数组 edges ，其中 edges[i] = [typei, ui, vi]表示节点 ui 和 vi 之间存在类型为 typei 的双向边。
请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。
如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。
返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
示例 1：输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]] 输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。
再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。
示例 2：输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]] 输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。
示例 3：输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]] 输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。
提示：1 <= n <= 10^5
1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
edges[i].length == 3
1 <= edges[i][0] <= 3
1 <= edges[i][1] < edges[i][2] <= n
所有元组 (typei, ui, vi) 互不相同

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 并查集 O(nlog(n)) O(n) 
func maxNumEdgesToRemove(n int, edges [][]int) int {
	res := len(edges)
	alice, bob := &UnionFind{}, &UnionFind{}
	alice.Init(n)
	bob.Init(n)
	for i := 0; i < len(edges); i++ {
		a, b, c := edges[i][0], edges[i][1]-1, edges[i][2]-1
		if a == 3 && (alice.query(b, c) == false || bob.query(b, c) == false) { // 公共边不在一个集合
			alice.union(b, c)
			bob.union(b, c)
			res--
		}
	}
	for i := 0; i < len(edges); i++ {
		a, b, c := edges[i][0], edges[i][1]-1, edges[i][2]-1
		if a == 1 && alice.query(b, c) == false { // 单边不在一个集合
			alice.union(b, c)
			res--
		}
		if a == 2 && bob.query(b, c) == false { // 单边不在一个集合
			bob.union(b, c)
			res--
		}
	}
	if alice.count > 1 || bob.count > 1 {
		return -1
	}
	return res
}

type UnionFind struct {
	fa    []int
	count int
}

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

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

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

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

1585.检查字符串是否可以通过排序子字符串得到另一个字符串(1)

  • 题目

给你两个字符串s 和t，请你通过若干次以下操作将字符串s转化成字符串t：
选择 s中一个 非空子字符串并将它包含的字符就地 升序排序。
比方说，对下划线所示的子字符串进行操作可以由"14234"得到"12344"。
如果可以将字符串 s变成 t，返回 true。否则，返回 false。
一个 子字符串定义为一个字符串中连续的若干字符。
示例 1：输入：s = "84532", t = "34852" 输出：true
解释：你可以按以下操作将 s 转变为 t ：
"84532" （从下标 2 到下标 3）-> "84352"
"84352" （从下标 0 到下标 2） -> "34852"
示例 2：输入：s = "34521", t = "23415" 输出：true
解释：你可以按以下操作将 s 转变为 t ：
"34521" -> "23451"
"23451" -> "23415"
示例 3：输入：s = "12345", t = "12435" 输出：false
示例 4：输入：s = "1", t = "2" 输出：false
提示：s.length == t.length
1 <= s.length <= 105
s 和t都只包含数字字符，即'0'到'9' 。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 贪心 O(n) O(n) 
func isTransformable(s string, t string) bool {
	n := len(s)
	arr := [10][]int{}
	for i := 0; i < n; i++ {
		arr[int(s[i]-'0')] = append(arr[int(s[i]-'0')], i)
	}
	for i := 0; i < n; i++ {
		index := int(t[i] - '0')
		if len(arr[index]) == 0 {
			return false
		}
		// 看当前位置s中等于t[i]的第x个元素，能不能移动到前面
		// 一次交换前后2个，目标值往前移（冒泡排序）
		for j := 0; j < index; j++ {
			// 前面不能存在比当前值小的，因为2个数排序后当前值会在后面
			if len(arr[j]) > 0 && arr[j][0] < arr[index][0] {
				return false
			}
		}
		arr[index] = arr[index][1:] // 当前数字匹配到了，往后移
	}
	return true
}