0701-0800-Easy¶

703.数据流中的第K大元素(2)¶

题目

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。
每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。

解题思路

No.	思路	时间复杂度	空间复杂度
01	最小堆+内置heap	O(nlog(n))	O(n)
02	小根堆	O(nlog(n))	O(n)

type KthLargest struct {
	k    int
	heap intHeap
}

func Constructor(k int, nums []int) KthLargest {
	h := intHeap(nums)
	heap.Init(&h)

	for len(h) > k {
		heap.Pop(&h)
	}
	return KthLargest{
		k:    k,
		heap: h,
	}
}

func (k *KthLargest) Add(val int) int {
	heap.Push(&k.heap, val)
	if len(k.heap) > k.k {
		heap.Pop(&k.heap)
	}
	return k.heap[0]
}

// 内置heap，实现接口
/*
type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}
*/
type intHeap []int

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

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

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

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

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

#
type KthLargest struct {
	nums []int
	k    int
}

func Constructor(k int, nums []int) KthLargest {
	if k < len(nums) {
		sort.Ints(nums)
		nums = nums[len(nums)-k:]
	}
	// 向上调整
	Up(nums)
	return KthLargest{
		nums: nums,
		k:    k,
	}
}

func (k *KthLargest) Add(val int) int {
	if k.k > len(k.nums) {
		k.nums = append(k.nums, val)
		Up(k.nums)
	} else {
		if val > k.nums[0] {
			// 在堆顶，向下调整
			k.nums[0] = val
			Down(k.nums, 0)
		}
	}
	return k.nums[0]
}

func Down(nums []int, index int) {
	length := len(nums)
	minIndex := index
	for {
		left := 2*index + 1
		right := 2*index + 2
		if left < length && nums[left] < nums[minIndex] {
			minIndex = left
		}
		if right < length && nums[right] < nums[minIndex] {
			minIndex = right
		}
		if minIndex == index {
			break
		}
		swap(nums, index, minIndex)
		index = minIndex
	}
}

func Up(nums []int) {
	length := len(nums)
	for i := length/2 - 1; i >= 0; i-- {
		minIndex := i
		left := 2*i + 1
		right := 2*i + 2
		if left < length && nums[left] < nums[minIndex] {
			minIndex = left
		}
		if right < length && nums[right] < nums[minIndex] {
			minIndex = right
		}
		if i != minIndex {
			swap(nums, i, minIndex)
		}
	}
}

func swap(nums []int, i, j int) {
	nums[i], nums[j] = nums[j], nums[i]
}

704.二分查找(3)¶

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
    你可以假设 nums 中的所有元素是不重复的。
    n 将在 [1, 10000]之间。
    nums 的每个元素都将在 [-9999, 9999]之间。

解题思路

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

func search(nums []int, target int) int {
	left, right:= 0, len(nums)-1
	for left <= right {
		mid := left + (right-left) / 2
		switch {
		case nums[mid] < target:
			left = mid + 1
		case nums[mid] > target:
			right = mid - 1
		default:
			return mid
		}
	}
	return -1
}

#
func search(nums []int, target int) int {
	if nums[0] > target || nums[len(nums)-1] < target {
		return -1
	}
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			return i
		}
		if nums[i] > target {
			return -1
		}
	}
	return -1
}

#
func search(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	mid := len(nums) / 2
	if nums[mid] == target {
		return mid
	} else if nums[mid] > target {
		return search(nums[:mid], target)
	} else {
		result := search(nums[mid+1:], target)
		if result == -1 {
			return result
		}
		return mid + 1 + result
	}
}

705.设计哈希集合(2)¶

题目

不使用任何内建的哈希表库设计一个哈希集合
具体地说，你的设计应该包含以下的功能
    add(value)：向哈希集合中插入一个值。
    contains(value) ：返回哈希集合中是否存在这个值。
    remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
示例:
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // 返回 true
hashSet.contains(3);    // 返回 false (未找到)
hashSet.add(2);          
hashSet.contains(2);    // 返回 true
hashSet.remove(2);          
hashSet.contains(2);    // 返回  false (已经被删除)
注意：
    所有的值都在 [0, 1000000]的范围内。
    操作的总数目在[1, 10000]范围内。
    不要使用内建的哈希集合库。

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组实现	O(1)	O(n)
02	数组实现	O(n^1/2)	)

type MyHashSet struct {
	table []bool
}

func Constructor() MyHashSet {
	return MyHashSet{
		table: make([]bool, 1000001),
	}
}

func (m *MyHashSet) Add(key int) {
	m.table[key] = true
}

func (m *MyHashSet) Remove(key int) {
	m.table[key] = false
}

func (m *MyHashSet) Contains(key int) bool {
	return m.table[key]
}

#
type MyHashSet struct {
	table [10000][]int
}

func Constructor() MyHashSet {
	return MyHashSet{
		table: [10000][]int{},
	}
}

func (m *MyHashSet) Add(key int) {
	for _, v := range m.table[key%10000] {
		if v == key {
			return
		}
	}
	m.table[key%10000] = append(m.table[key%10000], key)
}

func (m *MyHashSet) Remove(key int) {
	for k, v := range m.table[key%10000] {
		if v == key {
			m.table[key%10000] = append(m.table[key%10000][:k], m.table[key%10000][k+1:]...)
		}
	}
}

func (m *MyHashSet) Contains(key int) bool {
	for _, v := range m.table[key%10000] {
		if v == key {
			return true
		}
	}
	return false
}

706.设计哈希映射(2)¶

题目

具体地说，你的设计应该包含以下的功能
    put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
    get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
    remove(key)：如果映射中存在这个键，删除这个数值对。
示例：
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // 返回 1
hashMap.get(3);            // 返回 -1 (未找到)
hashMap.put(2, 1);         // 更新已有的值
hashMap.get(2);            // 返回 1 
hashMap.remove(2);         // 删除键为2的数据
hashMap.get(2);            // 返回 -1 (未找到) 
注意：
    所有的值都在 [0, 1000000]的范围内。
    操作的总数目在[1, 10000]范围内。
    不要使用内建的哈希库。

解题思路

No.	思路	时间复杂度	空间复杂度
01	数组实现	O(1)	O(n)
02	数组实现	O(n^1/2)	O(n^1/2)

type MyHashMap struct {
	table []int
}

func Constructor() MyHashMap {
	return MyHashMap{
		table: make([]int, 1000001),
	}
}

func (this *MyHashMap) Put(key int, value int) {
	this.table[key] = value + 1
}

func (this *MyHashMap) Get(key int) int {
	return this.table[key] - 1
}

func (this *MyHashMap) Remove(key int) {
	this.table[key] = 0
}

#
type MyHashMap struct {
	keys  [10000][]int
	value [10000][]int
}

func Constructor() MyHashMap {
	return MyHashMap{
		keys:  [10000][]int{},
		value: [10000][]int{},
	}
}

func (m *MyHashMap) Put(key int, value int) {
	for k, v := range m.keys[key%10000] {
		if v == key {
			m.value[key%10000][k] = value
			return
		}
	}
	m.keys[key%10000] = append(m.keys[key%10000], key)
	m.value[key%10000] = append(m.value[key%10000], value)
}

func (m *MyHashMap) Get(key int) int {
	for k, v := range m.keys[key%10000] {
		if v == key {
			return m.value[key%10000][k]
		}
	}
	return -1
}

func (m *MyHashMap) Remove(key int) {
	for k, v := range m.keys[key%10000] {
		if v == key {
			m.keys[key%10000] = append(m.keys[key%10000][:k], m.keys[key%10000][k+1:]...)
			m.value[key%10000] = append(m.value[key%10000][:k], m.value[key%10000][k+1:]...)
		}
	}
}

709.转换成小写字母(2)¶

题目

实现函数 ToLowerCase()，该函数接收一个字符串参数 str，
并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

示例 1：输入: "Hello" 输出: "hello"
示例 2：输入: "here" 输出: "here"
示例 3：输入: "LOVELY" 输出: "lovely"

解题思路

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

func toLowerCase(str string) string {
	return strings.ToLower(str)
}

#
func toLowerCase(str string) string {
	arr := []byte(str)
	for i := 0; i < len(arr); i++{
		if arr[i] >='A' && arr[i] <= 'Z'{
			arr[i] = arr[i] - 'A' + 'a'
		}
	}
	return string(arr)
}

717.1比特与2比特字符(3)¶

题目

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。
示例 1:输入: bits = [1, 0, 0] 输出: True
解释: 唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:输入: bits = [1, 1, 1, 0] 输出: False
解释: 唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
    1 <= len(bits) <= 1000.
    bits[i] 总是0 或 1.

解题思路

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

func isOneBitCharacter(bits []int) bool {
	n := len(bits)
	i := 0
	for i < n-1 {
		// 逢1加2,0加1位
		if bits[i] == 1 {
			i = i + 2
		} else {
			i++
		}
	}
	return i == n-1
}

#
func isOneBitCharacter(bits []int) bool {
	n := len(bits)
	count := 0
	// 统计末尾1的个数，偶数正确，奇数错误
	for i := n - 2; i >= 0; i-- {
		if bits[i] == 0 {
			break
		} else {
			count++
		}
	}
	// return count & 1 == 0
	return count%2 == 0
}

#
func isOneBitCharacter(bits []int) bool {
	return helper(bits, 0)
}

func helper(bits []int, left int) bool {
	if left == len(bits)-1 {
		return bits[left] == 0
	}
	if left < len(bits)-1 {
		if bits[left] == 0 {
			return helper(bits, left+1)
		}
		if bits[left] == 1 {
			return helper(bits, left+2)
		}
	}
	return false
}

720.词典中最长的单词(2)¶

题目

给出一个字符串数组words组成的一本英语词典。
从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案，则返回答案中字典序最小的单词。
若无答案，则返回空字符串。

示例 1:输入: words = ["w","wo","wor","worl", "world"] 输出: "world"
解释: 单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
示例 2:输入: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] 输出: "apple"
解释:  "apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。
注意:
    所有输入的字符串都只包含小写字母。
    words数组长度范围为[1,1000]。
    words[i]的长度范围为[1,30]。

解题思路

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

func longestWord(words []string) string {
	if len(words) == 0 {
		return ""
	} else if len(words) == 1 && len(words[0]) > 1 {
		return ""
	}
	sort.Strings(words)
	m := make(map[string]bool)
	res := words[0]
	for _, w := range words {
		n := len(w)
		if n == 1 {
			m[w] = true
		} else if m[w[:n-1]] {
			m[w] = true
			if len(res) < len(w) {
				res = w
			}
		}
	}
	return res
}

#
type Trie struct {
	children [26]*Trie
	index    int
}

func Constructor(str string) Trie {
	return Trie{}
}

func (t *Trie) insert(str string, index int) {
	cur := t
	for i := 0; i < len(str); i++ {
		j := str[i] - 'a'
		if cur.children[j] == nil {
			cur.children[j] = &Trie{}
		}
		cur = cur.children[j]
	}
	cur.index = index
}

func (t *Trie) bfs(words []string) string {
	res := ""
	stack := make([]*Trie, 0)
	stack = append(stack, t)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if node.index > 0 || node == t {
			if node != t {
				word := words[node.index-1]
				if len(word) > len(res) || (len(word) == len(res) && word < res) {
					res = word
				}
			}
			for i := 0; i < len(node.children); i++ {
				if node.children[i] != nil {
					stack = append(stack, node.children[i])
				}
			}
		}
	}
	return res
}

func longestWord(words []string) string {
	t := Trie{}
	for i := 0; i < len(words); i++ {
		t.insert(words[i], i+1)
	}
	return t.bfs(words)
}

724.寻找数组的中心索引(2)¶

题目

给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。
我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

示例 1:输入: nums = [1, 7, 3, 6, 5, 6] 输出: 3
解释:  索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。
同时, 3 也是第一个符合要求的中心索引。
示例 2:输入: nums = [1, 2, 3] 输出: -1
解释: 数组中不存在满足此条件的中心索引。
说明:
    nums 的长度范围为 [0, 10000]。
    任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。

解题思路

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

func pivotIndex(nums []int) int {
	sum := 0
	for i := range nums {
		sum = sum + nums[i]
	}
	left := 0
	for i := range nums {
		if left*2+nums[i] == sum {
			return i
		}
		left = left + nums[i]
	}
	return -1
}

#
func pivotIndex(nums []int) int {
	if len(nums) == 0 {
		return -1
	}
	arr := make([]int, len(nums))
	arr[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		arr[i] = arr[i-1] + nums[i]
	}
	for i := 0; i < len(nums); i++ {
		var left, right int
		if i == 0 {
			left = 0
		} else {
			left = arr[i-1]
		}
		r := i + 1
		if r > len(nums)-1 {
			right = 0
		} else {
			right = arr[len(nums)-1] - arr[i]
		}
		if left == right {
			return i
		}
	}
	return -1
}

728.自除数(2)¶

题目

自除数 是指可以被它包含的每一位数除尽的数。
例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
还有，自除数不允许包含 0 。
给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
示例 1：输入： 上边界left = 1, 下边界right = 22
输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
注意：
    每个输入参数的边界满足 1 <= left <= right <= 10000。

解题思路

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

func selfDividingNumbers(left int, right int) []int {
	res := make([]int, 0)
	for i := left; i <= right; i++ {
		if isSelfDividing(i) {
			res = append(res, i)
		}
	}
	return res
}

func isSelfDividing(n int) bool {
	temp := n
	for temp > 0 {
		d := temp % 10
		temp = temp / 10
		if d == 0 || n%d != 0 {
			return false
		}
	}
	return true
}

#
func selfDividingNumbers(left int, right int) []int {
	res := make([]int, 0)
	for i := left; i <= right; i++ {
		if isSelfDividing(i) {
			res = append(res, i)
		}
	}
	return res
}

func isSelfDividing(n int) bool {
	str := strconv.Itoa(n)
	for _, v := range str{
		if v == '0' || int32(n) % (v-'0') != 0{
			return false
		}
	}
	return true
}

733.图像渲染(2)¶

题目

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，
接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。
将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。

示例 1:输入:  image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:  在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:
    image 和 image[0] 的长度在范围 [1, 50] 内。
    给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
    image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

解题思路

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

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

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	oldColor := image[sr][sc]
	if oldColor == newColor {
		return image
	}
	m, n := len(image), len(image[0])
	list := make([][]int, 1)
	list[0] = []int{sr, sc}

	for len(list) > 0 {
		node := list[0]
		list = list[1:]
		image[node[0]][node[1]] = newColor
		for i := 0; i < 4; i++ {
			x := node[0] + dx[i]
			y := node[1] + dy[i]
			if 0 <= x && x < m && 0 <= y && y < n &&
				image[x][y] == oldColor {
				list = append(list, []int{x, y})
			}
		}
	}
	return image
}

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

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	if sr < 0 || sc < 0 || sr >= len(image) || 
		sc >= len(image[sr]) || image[sr][sc] == newColor {
		return image
	}
	oldColor := image[sr][sc]
	image[sr][sc] = newColor
	for i := 0; i < 4; i++ {
		x := sr + dx[i]
		y := sc + dy[i]
		if 0 <= x && x < len(image) && 0 <= y && y < len(image[x]) &&
			image[x][y] == oldColor {
			floodFill(image, x, y, newColor)
		}
	}
	return image
}

744.寻找比目标字母大的最小字母(3)¶

题目

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。
另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
    如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
示例：
输入:letters = ["c", "f", "j"] target = "a" 输出: "c"
输入:letters = ["c", "f", "j"] target = "c" 输出: "f"
输入:letters = ["c", "f", "j"] target = "d" 输出: "f"
输入:letters = ["c", "f", "j"] target = "g" 输出: "j"
输入:letters = ["c", "f", "j"] target = "j" 输出: "c"
输入:letters = ["c", "f", "j"] target = "k" 输出: "c"
提示：
    letters长度范围在[2, 10000]区间内。
    letters 仅由小写字母组成，最少包含两个不同的字母。
    目标字母target 是一个小写字母。

解题思路

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

func nextGreatestLetter(letters []byte, target byte) byte {
	for i := 0; i < len(letters); i++ {
		if letters[i] > target {
			return letters[i]
		}
	}
	return letters[0]
}

#
func nextGreatestLetter(letters []byte, target byte) byte {
	n := len(letters)
	i := sort.Search(n, func(i int) bool {
		return target < letters[i]
	})
	return letters[i%n]
}

#
func nextGreatestLetter(letters []byte, target byte) byte {
	left := 0
	right := len(letters) - 1
	for left <= right {
		mid := left + (right-left)/2
		if letters[mid] <= target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return letters[left%len(letters)]
}

746.使用最小花费爬楼梯(3)¶

题目

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:输入: cost = [10, 15, 20] 输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：
    cost 的长度将会在 [2, 1000]。
    每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

解题思路

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

/*
用dp[i]表示爬i个台阶所需要的成本，所以dp[0]=0，dp[1]=0
每次爬i个楼梯，计算的都是从倒数第一个结束，还是从倒数第二个结束
动态转移方程为:
dp[i] = min{dp[i-2]+cost[i-2] , dp[i-1]+cost[i-1]};
*/
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 0
	for i := 2; i <= n; i++ {
		dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
	}
	return dp[n]
}

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

#
func minCostClimbingStairs(cost []int) int {
	a := 0
	b := 0
	for i := 2; i <= len(cost); i++ {
		a, b = b, min(b+cost[i-1], a+cost[i-2])
	}
	return b
}

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

#
var arr []int

func minCostClimbingStairs(cost []int) int {
	arr = make([]int, len(cost)+1)
	return ClimbingStais(cost, len(cost))
}

func ClimbingStais(cost []int, i int) int {
	if i == 0 || i == 1 {
		return 0
	}
	if arr[i] == 0 {
		arr[i] = min(ClimbingStais(cost, i-1)+cost[i-1], 
			ClimbingStais(cost, i-2)+cost[i-2])
	}
	return arr[i]
}

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

747.至少是其他数字两倍的最大数(3)¶

题目

在一个给定的数组nums中，总是存在一个最大元素 。
查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
如果是，则返回最大元素的索引，否则返回-1。

示例 1:输入: nums = [3, 6, 1, 0] 输出: 1
解释: 6是最大的整数, 对于数组中的其他整数,6大于数组中其他元素的两倍。
6的索引是1, 所以我们返回1.
示例 2:输入: nums = [1, 2, 3, 4] 输出: -1
解释: 4没有超过3的两倍大, 所以我们返回 -1.
提示:
    nums 的长度范围在[1, 50].
    每个 nums[i] 的整数范围在 [0, 100].

解题思路

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

func dominantIndex(nums []int) int {
	n := len(nums)
	if n == 1 {
		return 0
	}
	maxIndex, secondMaxIndex := 0, 1
	if nums[maxIndex] < nums[secondMaxIndex] {
		maxIndex, secondMaxIndex = secondMaxIndex, maxIndex
	}

	for i := 2; i < n; i++ {
		if nums[maxIndex] < nums[i] {
			maxIndex, secondMaxIndex = i, maxIndex
		} else if nums[secondMaxIndex] < nums[i] {
			secondMaxIndex = i
		}
	}
	if nums[maxIndex] >= 2*nums[secondMaxIndex] {
		return maxIndex
	}
	return -1
}

#
func dominantIndex(nums []int) int {
	n := len(nums)
	if n == 1 {
		return 0
	}
	maxValue := nums[0]
	index := 0

	for i := 1; i < n; i++ {
		if nums[i] > maxValue {
			maxValue = nums[i]
			index = i
		}
	}
	for i := 0; i < n; i++ {
		if i == index {
			continue
		}
		if nums[i]*2 > maxValue {
			return -1
		}
	}
	return index
}

#
func dominantIndex(nums []int) int {
	n := len(nums)
	if n == 1 {
		return 0
	}
	temp := make([]int, len(nums))
	copy(temp, nums)
	sort.Ints(temp)
	maxValue := temp[len(temp)-1]
	if maxValue < 2*temp[len(temp)-2] {
		return -1
	}
	for i := 0; i < n; i++ {
		if nums[i] == maxValue {
			return i
		}
	}
	return -1
}

748.最短完整词(3)¶

题目

如果单词列表（words）中的一个单词包含牌照（licensePlate）中所有的字母，那么我们称之为完整词。
在所有完整词中，最短的单词我们称之为最短完整词。
单词在匹配牌照中的字母时不区分大小写，比如牌照中的 "P" 依然可以匹配单词中的 "p" 字母。
我们保证一定存在一个最短完整词。当有多个单词都符合最短完整词的匹配条件时取单词列表中最靠前的一个。
牌照中可能包含多个相同的字符，比如说：对于牌照 "PP"，单词 "pair" 无法匹配，但是 "supper" 可以匹配。

示例 1：输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出："steps"
说明：最短完整词应该包括 "s"、"p"、"s" 以及 "t"。
对于 "step" 它只包含一个 "s" 所以它不符合条件。同时在匹配过程中我们忽略牌照中的大小写。
示例 2：输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
输出："pest"
说明：存在 3 个包含字母 "s" 且有着最短长度的完整词，但我们返回最先出现的完整词。
注意:
    牌照（licensePlate）的长度在区域[1, 7]中。
    牌照（licensePlate）将会包含数字、空格、或者字母（大写和小写）。
    单词列表（words）长度在区间 [10, 1000] 中。
    每一个单词 words[i] 都是小写，并且长度在区间 [1, 15] 中。

解题思路

No.	思路	时间复杂度	空间复杂度
01	双哈希遍历	O(n)	O(1)
02	双数组遍历	O(n)	O(1)
03	排序+遍历	O(n)	O(n)

func shortestCompletingWord(licensePlate string, words []string) string {
	m := make(map[byte]int)
	licensePlate = strings.ToLower(licensePlate)
	for i := 0; i < len(licensePlate); i++ {
		if licensePlate[i] >= 'a' && licensePlate[i] <= 'z' {
			m[licensePlate[i]]++
		}
	}
	res := ""
	for i := 0; i < len(words); i++ {
		if len(words[i]) >= len(res) && res != "" {
			continue
		}
		tempM := make(map[byte]int)
		for j := 0; j < len(words[i]); j++ {
			tempM[words[i][j]]++
		}
		flag := true
		for k := range m {
			if tempM[k] < m[k] {
				flag = false
				break
			}
		}
		if flag == true {
			res = words[i]
		}
	}
	return res
}

#
func shortestCompletingWord(licensePlate string, words []string) string {
	m := make([]int, 26)
	licensePlate = strings.ToLower(licensePlate)
	for i := 0; i < len(licensePlate); i++ {
		if licensePlate[i] >= 'a' && licensePlate[i] <= 'z' {
			m[licensePlate[i]-'a']++
		}
	}
	res := ""
	for i := 0; i < len(words); i++ {
		if len(words[i]) >= len(res) && res != "" {
			continue
		}
		tempM := make([]int, 26)
		for j := 0; j < len(words[i]); j++ {
			tempM[words[i][j]-'a']++
		}
		flag := true
		for k := range m {
			if tempM[k] < m[k] {
				flag = false
				break
			}
		}
		if flag == true {
			res = words[i]
		}
	}
	return res
}

#
func shortestCompletingWord(licensePlate string, words []string) string {
	m := make([]int, 26)
	licensePlate = strings.ToLower(licensePlate)
	for i := 0; i < len(licensePlate); i++ {
		if licensePlate[i] >= 'a' && licensePlate[i] <= 'z' {
			m[licensePlate[i]-'a']++
		}
	}
	var lists [16][]string
	for _, word := range words {
		lists[len(word)] = append(lists[len(word)], word)
	}
	for _, list := range lists {
		for _, word := range list {
			tempM := make([]int, 26)
			for i := 0; i < len(word); i++ {
				tempM[word[i]-'a']++
			}
			flag := true
			for k := range m {
				if tempM[k] < m[k] {
					flag = false
					break
				}
			}
			if flag == true {
				return word
			}
		}
	}
	return ""
}

762.二进制表示中质数个计算置位(2)¶

题目

给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
示例 1: 输入: L = 6, R = 10 输出: 4
解释:
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)

示例 2: 输入: L = 10, R = 15 输出: 5
解释:
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)

注意:
    L, R 是 L <= R 且在 [1, 10^6] 中的整数。
    R - L 的最大值为 10000。

解题思路

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

func countPrimeSetBits(L int, R int) int {
	primes := [...]int{
		2:  1,
		3:  1,
		5:  1,
		7:  1,
		11: 1,
		13: 1,
		17: 1,
		19: 1,
		23: 1,
		29: 1,
		31: 1,
	}
	res := 0
	for i := L; i <= R; i++ {
		bits := 0
		for n := i; n > 0; n >>= 1 {
			// bits = bits + n & 1
			bits = bits + n % 2
		}
		res = res + primes[bits]
	}
	return res
}

766.托普利茨矩阵(2)¶

题目

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。
给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。
示例 1:输入: 
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
输出: True
解释:
在上述矩阵中, 其对角线为:"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
各条对角线上的所有元素均相同, 因此答案是True。
示例 2:输入:
matrix = [
  [1,2],
  [2,2]
]
输出: False
解释: 对角线"[1, 2]"上的元素不同。
说明:
    matrix 是一个包含整数的二维数组。
    matrix 的行数和列数均在 [1, 20]范围内。
    matrix[i][j] 包含的整数在 [0, 99]范围内。
进阶:
    如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？
    如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？

解题思路

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

func isToeplitzMatrix(matrix [][]int) bool {
	m, n := len(matrix), len(matrix[0])
	for i := 0; i < m-1; i++ {
		for j := 0; j < n-1; j++ {
			if matrix[i][j] != matrix[i+1][j+1] {
				return false
			}
		}
	}
	return true
}

#
func isToeplitzMatrix(matrix [][]int) bool {
	m := make(map[int]int)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if value, ok := m[i-j]; ok {
				if matrix[i][j] != value {
					return false
				}
			} else {
				m[i-j] = matrix[i][j]
			}
		}
	}
	return true
}

771.宝石与石头(3)¶

题目

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 
S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:输入: J = "aA", S = "aAAbbbb"输出: 3
示例 2:输入: J = "z", S = "ZZ"输出: 0

注意:
    S 和 J 最多含有50个字母。
     J 中的字符不重复。

解题思路

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

func numJewelsInStones(J string, S string) int {
	res := 0
	for _, v := range J {
		res = res + strings.Count(S, string(v))
	}
	return res
}


#
func numJewelsInStones(J string, S string) int {
	m := make(map[byte]bool)
	for i := range J {
		m[J[i]] = true
	}
	res := 0
	for i := range S {
		if m[S[i]] {
			res++
		}
	}
	return res
}

#
func numJewelsInStones(J string, S string) int {
	res := 0
	for _, v := range J {
		for _, s := range S {
			if v == s {
				res++
			}
		}
	}
	return res
}

783.二叉搜索树节点最小距离(3)¶

题目

给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。
示例：输入: root = [4,2,6,1,3,null,null] 输出: 1
解释:注意，root是树节点对象(TreeNode object)，而不是数组。
给定的树 [4,2,6,1,3,null,null] 可表示为下图:
          4
        /   \
      2      6
     / \    
    1   3  
最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
注意：
    二叉树的大小范围在 2 到 100。
    二叉树总是有效的，每个节点的值都是整数，且不重复。
    本题与 530：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 相同

解题思路

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

var minDiff, previous int

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

func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	dfs(root.Left)
	newDiff := diff(previous, root.Val)
	if minDiff > newDiff {
		minDiff = newDiff
	}
	previous = root.Val
	dfs(root.Right)
}

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

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

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

#
func minDiffInBST(root *TreeNode) int {
	arr := make([]int, 0)
	stack := make([]*TreeNode, 0)
	min := math.MaxInt32
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		arr = append(arr, node.Val)
		if len(arr) > 1 {
			temp := node.Val - arr[len(arr)-2]
			if min > temp {
				min = temp
			}
		}
		root = node.Right
	}
	return min
}

784.字母大小写全排列(4)¶

题目

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。
返回所有可能得到的字符串集合。

示例:
输入: S = "a1b2" 输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
输入: S = "3z4" 输出: ["3z4", "3Z4"]
输入: S = "12345" 输出: ["12345"]
注意：
    S 的长度不超过12。
    S 仅由数字和字母组成。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历-逐位添加	O(n*2^n)	O(n*2^n)
02	递归	O(n*2^n)	O(n*2^n)
03	遍历-遇字母翻倍	O(n*2^n)	O(n*2^n)
04	回溯-递归	O(n*2^n)	O(n*2^n)

func letterCasePermutation(S string) []string {
	res := make([]string, 1)
	for i := 0; i < len(S); i++ {
		if string(S[i]) >= "0" && string(S[i]) <= "9" {
			newRes := make([]string, 0)
			for _, v := range res {
				newRes = append(newRes, v+string(S[i]))
			}
			res = newRes
		} else if b, ok := check(S[i]); ok {
			first := string(b[0])
			second := string(b[1])
			newRes := make([]string, 0)
			for _, v := range res {
				newRes = append(newRes, v+first)
				newRes = append(newRes, v+second)
			}
			res = newRes
		}
	}
	return res
}

func check(b byte) ([]byte, bool) {
	if 'a' <= b && b <= 'z' {
		return []byte{b - 'a' + 'A', b}, true
	}
	if 'A' <= b && b <= 'Z' {
		return []byte{b, b - 'A' + 'a'}, true
	}
	return []byte{b}, false
}

#
func letterCasePermutation(S string) []string {
	size := len(S)
	if size == 0 {
		return []string{""}
	}
	postfixs := make([]string, 1)
	lastByte := S[size-1]
	postfixs[0] = string(lastByte)
	if b, ok := check(lastByte); ok {
		postfixs = append(postfixs, string(b))
	}
	prefixs := letterCasePermutation(S[:size-1])
	res := make([]string, 0)
	for _, pre := range prefixs {
		for _, post := range postfixs {
			res = append(res, pre+post)
		}
	}
	return res
}

func check(b byte) (byte, bool) {
	if 'a' <= b && b <= 'z' {
		return b - 'a' + 'A', true
	}
	if 'A' <= b && b <= 'Z' {
		return b - 'A' + 'a', true
	}
	return 0, false
}

#
func letterCasePermutation(S string) []string {
	S = strings.ToLower(S)
	res := []string{S}
	for i := range S {
		if S[i] >= 'a' {
			n := len(res)
			for j := 0; j < n; j++ {
				temp := []byte(res[j])
				temp[i] = S[i] - 'a' + 'A'
				res = append(res, string(temp))
			}
		}
	}
	return res
}

#
var res []string

func letterCasePermutation(S string) []string {
	res = make([]string, 0)
	dfs([]byte(S), 0)
	return res
}

func dfs(arr []byte, level int) {
	if level == len(arr) {
		res = append(res, string(arr))
		return
	}
	if arr[level] >= 'a' && arr[level] <= 'z' {
		dfs(arr, level+1)
		arr[level] = arr[level] - 'a' + 'A' // 大写
		dfs(arr, level+1)
		arr[level] = arr[level] - 'A' + 'a' // 小写
	} else if arr[level] >= 'A' && arr[level] <= 'Z' {
		dfs(arr, level+1)
		arr[level] = arr[level] - 'A' + 'a' // 小写
		dfs(arr, level+1)
		arr[level] = arr[level] - 'a' + 'A' // 大写
	} else {
		dfs(arr, level+1)
	}
	return
}

788.旋转数字(4)¶

题目

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，
我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；
2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；
6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
示例：输入: 10 输出: 4
解释: 在[1, 10]中有四个好数： 2, 5, 6, 9。注意 1 和 10 不是好数, 因为他们在旋转之后不变。
提示：N 的取值范围是 [1, 10000]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(nlog(n))	O(1)
02	遍历+递归	O(nlog(n))	O(log(n))
03	遍历+转字符串	O(nlog(n))	O(log(n))
04	动态规划	O(n)	O(n)

func rotatedDigits(N int) int {
	count := 0
	for i := 2; i <= N; i++ {
		if isValid(i) {
			count++
		}
	}
	return count
}

func isValid(n int) bool {
	valid := false
	for n > 0 {
		switch n % 10 {
		case 2, 5, 6, 9:
			valid = true
		case 3, 4, 7:
			return false
		}
		n = n / 10
	}
	return valid
}

#
func rotatedDigits(N int) int {
	count := 0
	for i := 2; i <= N; i++ {
		if isValid(i, false) {
			count++
		}
	}
	return count
}

func isValid(n int, flag bool) bool {
	if n == 0 {
		return flag
	}
	switch n % 10 {
	case 3, 4, 7:
		return false
	case 0, 1, 8:
		return isValid(n/10, flag)
	case 2, 5, 6, 9:
		return isValid(n/10, true)
	}
	return false
}

# 
// 每个数字由(i/10)和(i%10)组成
// dp[i]={dp[i/10],dp[i%10]}
func rotatedDigits(N int) int {
	dp := []int{0, 0, 1, -1, -1, 1, 1, -1, 0, 1}
	if N >= 10 {
		dp = append(dp, make([]int, N-9)...)
	}
	res := 0
	for i := 0; i <= N; i++ {
		if dp[i/10] == -1 || dp[i%10] == -1 {
			dp[i] = -1
		} else if dp[i] = dp[i/10] | dp[i%10]; dp[i] == 1 {
			// arr[i/10] = 1/0 arr[i%10] == 1/0
			// 异或操作，确保把0，1，8组成的数字剔除
			// 0|0 == 0
			// 0|1 == 1
			// 1|0 == 1
			// 1|1 == 1
			res++
		}
	}
	return res
}

796.旋转字符串(2)¶

题目

给定两个字符串, A 和 B。
A 的旋转操作就是将 A 最左边的字符移动到最右边。
例如, 若 A = 'abcde'，在移动一次之后结果就是'bcdea' 。
如果在若干次旋转操作之后，A 能变成B，那么返回True。

示例 1: 输入: A = 'abcde', B = 'cdeab' 输出: true
示例 2:输入: A = 'abcde', B = 'abced' 输出: false
注意：A 和 B 长度不超过 100。

解题思路

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

func rotateString(A string, B string) bool {
	return len(A) == len(B) && strings.Contains(A+A, B)
}

#
func rotateString(A string, B string) bool {
	if A == B {
		return true
	}
	if len(A) != len(B) {
		return false
	}
	for i := 0; i < len(A); i++ {
		A = A[1:] + string(A[0])
		if A == B {
			return true
		}
	}
	return false
}

0701-0800-Medium¶

701.二叉搜索树中的插入操作(2)¶

题目

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
示例 2：输入：root = [40,20,60,10,30,50,70], val = 25 
输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]
提示：给定的树上的节点数介于 0 和 10^4 之间
每个节点都有一个唯一整数值，取值范围从 0 到 10^8
-10^8 <= val <= 10^8
新值和原始二叉搜索树中的任意节点值都不同

解题思路

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

func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{
			Val: val,
		}
	}
	temp := root
	for temp != nil {
		if temp.Val > val {
			if temp.Left == nil {
				temp.Left = &TreeNode{
					Val: val,
				}
				break
			}
			temp = temp.Left
		} else {
			if temp.Right == nil {
				temp.Right = &TreeNode{
					Val: val,
				}
				break
			}
			temp = temp.Right
		}
	}
	return root
}

# 2
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{
			Val: val,
		}
	}
	if root.Val > val {
		root.Left = insertIntoBST(root.Left, val)
	} else {
		root.Right = insertIntoBST(root.Right, val)
	}
	return root
}

707.设计链表(2)¶

题目

设计链表的实现。您可以选择使用单链表或双链表。
单链表中的节点应该具有两个属性：val和next。val是当前节点的值，next是指向下一个节点的指针/引用。
如果要使用双向链表，则还需要一个属性prev以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第index个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第index个节点之前添加值为val 的节点。
如果index等于链表的长度，则该节点将附加到链表的末尾。
如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引index 有效，则删除链表中的第index 个节点。
示例：MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3
提示：所有val值都在[1, 1000]之内。
操作次数将在[1, 1000]之内。
请不要使用内置的 LinkedList 库。

解题思路

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

type MyLinkedList struct {
	size int
	head *Node
	tail *Node
}

type Node struct {
	value int
	next  *Node
}

func Constructor() MyLinkedList {
	tail := &Node{}
	head := &Node{next: tail}
	return MyLinkedList{
		head: head,
		tail: tail,
	}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || this.size <= index {
		return -1
	}
	i := 0
	cur := this.head.next
	for i < index {
		i++
		cur = cur.next
	}
	return cur.value
}

func (this *MyLinkedList) AddAtHead(val int) {
	node := &Node{value: val}
	node.next = this.head.next
	this.head.next = node
	this.size++
}

func (this *MyLinkedList) AddAtTail(val int) {
	this.tail.value = val
	node := &Node{}
	this.tail.next = node
	this.tail = node
	this.size++
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	switch {
	case index < 0 || this.size < index:
		return
	case index == 0:
		this.AddAtHead(val)
		return
	case index == this.size:
		this.AddAtTail(val)
		return
	}
	i := -1
	cur := this.head
	for i+1 < index {
		i++
		cur = cur.next
	}
	node := &Node{value: val}
	node.next = cur.next
	cur.next = node
	this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || this.size <= index {
		return
	}
	i := -1
	cur := this.head
	for i+1 < index {
		i++
		cur = cur.next
	}
	cur.next = cur.next.next
	this.size--
}

# 2
type MyLinkedList struct {
	head *Node
	size int
}

type Node struct {
	value int
	next  *Node
}

func Constructor() MyLinkedList {
	return MyLinkedList{
		head: &Node{},
		size: 0,
	}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}
	prev := this.head
	for i := 1; i <= index; i++ {
		prev = prev.next
	}
	return prev.next.value
}

func (this *MyLinkedList) AddAtHead(val int) {
	this.AddAtIndex(0, val)
}

func (this *MyLinkedList) AddAtTail(val int) {
	this.AddAtIndex(this.size, val)
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 || index > this.size {
		return
	}
	prev := this.head
	for i := 1; i <= index; i++ {
		prev = prev.next
	}
	node := &Node{
		value: val,
		next:  nil,
	}
	node.next = prev.next
	prev.next = node
	this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	prev := this.head
	for i := 1; i <= index; i++ {
		prev = prev.next
	}
	prev.next = prev.next.next
	this.size--
}

712.两个字符串的最小ASCII删除和(3)¶

题目

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
示例 1:输入: s1 = "sea", s2 = "eat" 输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
示例2:输入: s1 = "delete", s2 = "leet" 输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
注意:0 < s1.length, s2.length <= 1000。
所有字符串中的字符ASCII值在[97, 122]之间。

解题思路

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

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

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

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

# 2
func minimumDeleteSum(s1 string, s2 string) int {
	a, b := len(s1), len(s2)
	dp := make([][]int, a+1)
	for i := 0; i <= a; i++ {
		dp[i] = make([]int, b+1)
		if i > 0 {
			dp[i][0] = dp[i-1][0] + int(s1[i-1])
		}
	}
	for i := 1; i <= b; i++ {
		dp[0][i] = dp[0][i-1] + int(s2[i-1])
	}

	for i := 1; i <= a; i++ {
		for j := 1; j <= b; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = min(dp[i][j-1]+int(s2[j-1]), dp[i-1][j]+int(s1[i-1]))
			}
		}
	}
	return dp[a][b]
}

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

# 3
var m [][]int

func minimumDeleteSum(s1 string, s2 string) int {
	a, b := len(s1), len(s2)
	m = make([][]int, a+1)
	for i := 0; i <= a; i++ {
		m[i] = make([]int, b+1)
		for j := 0; j <= b; j++ {
			m[i][j] = -1
		}
	}

	total := dfs(s1, s2, 0, 0)
	return sumAscii(s1) + sumAscii(s2) - 2*total
}

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

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

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

713.乘积小于K的子数组(1)¶

题目

给定一个正整数数组 nums。
找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:输入: nums = [10,5,2,6], k = 100 输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
说明:0 < nums.length <= 50000
    0 < nums[i] < 1000
    0 <= k < 10^6

解题思路

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

func numSubarrayProductLessThanK(nums []int, k int) int {
	if k <= 1 {
		return 0
	}
	res := 0
	left := 0
	total := 1
	for right := 0; right < len(nums); right++ {
		total = total * nums[right]
		for k <= total {
			total = total / nums[left]
			left++
		}
		res = res + right - left + 1
	}
	return res
}

714.买卖股票的最佳时机含手续费(2)¶

题目

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；
非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。
如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1:输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
    0 < prices.length <= 50000.
    0 < prices[i] < 50000.
    0 <= fee < 50000.

解题思路

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

func maxProfit(prices []int, fee int) int {
	dp0, dp1 := 0, math.MinInt32
	for i := 0; i < len(prices); i++ {
		temp := dp0
		dp0 = max(dp0, dp1+prices[i])
		dp1 = max(dp1, temp-prices[i]-fee)
	}
	return dp0
}

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

# 2
func maxProfit(prices []int, fee int) int {
	dp := make([][2]int, len(prices))
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]-fee)
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}
	return dp[len(prices)-1][0]
}

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

718.最长重复子数组(3)¶

题目

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：输入：A: [1,2,3,2,1] B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。
提示：1 <= len(A), len(B) <= 1000
    0 <= A[i], B[i] < 100

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n^2)
02	动态规划	O(n^2)	O(n)
03	滑动窗口	O(n^2)	O(1)

func findLength(A []int, B []int) int {
	n, m := len(A), len(B)
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m+1)
	}
	res := math.MinInt32
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if A[i-1] == B[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			}
			if dp[i][j] > res {
				res = dp[i][j]
			}
		}
	}
	return res
}

# 2
func findLength(A []int, B []int) int {
	n, m := len(A), len(B)
	dp := make([]int, m+1)
	res := math.MinInt32
	for i := 1; i <= n; i++ {
		for j := m; j >= 1; j-- {
			if A[i-1] == B[j-1] {
				dp[j] = dp[j-1] + 1
			} else {
				dp[j] = 0 // 需要清0
			}
			if dp[j] > res {
				res = dp[j]
			}
		}
	}
	return res
}

# 3
func findLength(A []int, B []int) int {
	n, m := len(A), len(B)
	res := math.MinInt32
	for i := 0; i < n; i++ {
		length := min(n-i, m)
		maxLength := getMaxLength(A, B, i, 0, length)
		res = max(res, maxLength)
	}
	for i := 0; i < m; i++ {
		length := min(n, m-i)
		maxLength := getMaxLength(A, B, 0, i, length)
		res = max(res, maxLength)
	}
	return res
}

func getMaxLength(A, B []int, a, b int, length int) int {
	res := 0
	count := 0
	for i := 0; i < length; i++ {
		if A[a+i] == B[b+i] {
			count++
		} else {
			count = 0
		}
		res = max(res, count)
	}
	return res
}

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

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

721.账户合并(1)¶

题目

给定一个列表 accounts，每个元素 accounts[i]是一个字符串列表，
其中第一个元素 accounts[i][0]是名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。
请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。
一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。
账户本身可以以任意顺序返回。
示例 1：输入：accounts = [["John", "johnsmith@mail.com", "john00@mail.com"],
["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", 
"john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
输出：
[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], 
["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
解释：第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。 
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，
['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。
提示：accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。

解题思路

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

func accountsMerge(accounts [][]string) [][]string {
	n := len(accounts)
	fa = Init(n)
	res := make([][]string, 0)
	m := make(map[string]int)
	for i := 0; i < len(accounts); i++ {
		for j := 1; j < len(accounts[i]); j++ {
			email := accounts[i][j]
			if id, ok := m[email]; ok { // 邮箱重复出现，合并账户
				union(i, id)
			} else {
				m[email] = i
			}
		}
	}
	temp := make([][]string, n)
	for k, v := range m {
		target := find(v)
		temp[target] = append(temp[target], k)
	}
	for i := 0; i < len(temp); i++ {
		if len(temp[i]) > 0 {
			arr := temp[i]
			sort.Strings(arr)
			arr = append([]string{accounts[i][0]}, arr...)
			res = append(res, arr)
		}
	}
	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)
}

722.删除注释(1)¶

题目

给一个 C++ 程序，删除程序中的注释。这个程序source是一个数组，其中source[i]表示第i行源码。
这表示每行源码由\n分隔。
在 C++ 中有两种注释风格，行内注释和块注释。
字符串// 表示行注释，表示//和其右侧的其余字符应该被忽略。
字符串/* 表示一个块注释，它表示直到*/的下一个（非重叠）出现的所有字符都应该被忽略。
（阅读顺序为从左到右）非重叠是指，字符串/*/并没有结束块注释，因为注释的结尾与开头相重叠。
第一个有效注释优先于其他注释：如果字符串//出现在块注释中会被忽略。
同样，如果字符串/*出现在行或块注释中也会被忽略。
如果一行在删除注释之后变为空字符串，那么不要输出该行。即，答案列表中的每个字符串都是非空的。
样例中没有控制字符，单引号或双引号字符。比如，source = "string s = "/* Not a comment. */";"
不会出现在测试样例里。（此外，没有其他内容（如定义或宏）会干扰注释。）
我们保证每一个块注释最终都会被闭合， 所以在行或块注释之外的/*总是开始新的注释。
最后，隐式换行符可以通过块注释删除。 有关详细信息，请参阅下面的示例。
从源代码中删除注释后，需要以相同的格式返回源代码。
示例1:输入: 
source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", 
"int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", 
"   testing */", "a = b + c;", "}"]
示例代码可以编排成这样:
/*Test program */
int main()
{ 
  // variable declaration 
int a, b, c;
/* This is a test
   multiline  
   comment for 
   testing */
a = b + c;
}
输出: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]
编排后:
int main()
{ 
  
int a, b, c;
a = b + c;
}
解释: 第 1 行和第 6-9 行的字符串 /* 表示块注释。第 4 行的字符串 // 表示行注释。
示例 2:输入:  source = ["a/*comment", "line", "more_comment*/b"]
输出: ["ab"]
解释: 原始的 source 字符串是 "a/*comment\nline\nmore_comment*/b", 其中我们用粗体显示了换行符。
删除注释后，隐含的换行符被删除，留下字符串 "ab" 用换行符分隔成数组时就是 ["ab"].
注意:source的长度范围为[1, 100].
source[i]的长度范围为[0, 80].
每个块注释都会被闭合。
给定的源码中不会有单引号、双引号或其他控制字符。

解题思路

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

func removeComments(source []string) []string {
	res := make([]string, 0)
	flag := false // 判断是否是块注释
	temp := make([]byte, 0)
	for i := 0; i < len(source); i++ {
		str := source[i]
		j := 0
		for j < len(str) {
			if flag == false && j+1 < len(str) && str[j] == '/' && str[j+1] == '*' {
				flag = true
				j = j + 2
				continue
			}
			if flag == true && j+1 < len(str) && str[j] == '*' && str[j+1] == '/' {
				flag = false
				j = j + 2
				continue
			}
			if flag == false && j+1 < len(str) && str[j] == '/' && str[j+1] == '/' {
				break
			}
			if flag == false {
				temp = append(temp, str[j])
			}
			j++
		}
		if flag == false && len(temp) > 0 {
			res = append(res, string(temp))
			temp = make([]byte, 0)
		}
	}
	return res
}

725.分隔链表(2)¶

题目

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
示例 1：输入: root = [1, 2, 3], k = 5 输出: [[1],[2],[3],[],[]]
解释:输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2：输入:  root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
提示:root 的长度范围：[0, 1000].
输入的每个节点的大小范围：[0, 999].
k的取值范围：[1, 50].

解题思路

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

func splitListToParts(root *ListNode, k int) []*ListNode {
	res := make([]*ListNode, 0)
	cur := root
	length := 0
	for cur != nil {
		length++
		cur = cur.Next
	}
	a, b := length/k, length%k
	for i := 0; i < k; i++ {
		node := &ListNode{Next: nil}
		temp := node
		for j := 0; j < a; j++ {
			temp.Next = &ListNode{
				Val:  root.Val,
				Next: nil,
			}
			temp = temp.Next
			root = root.Next
		}
		if b > 0 {
			temp.Next = &ListNode{
				Val:  root.Val,
				Next: nil,
			}
			temp = temp.Next
			root = root.Next
			b = b - 1
		}
		res = append(res, node.Next)
	}
	return res
}

# 2
func splitListToParts(root *ListNode, k int) []*ListNode {
	res := make([]*ListNode, 0)
	cur := root
	length := 0
	for cur != nil {
		length++
		cur = cur.Next
	}
	a, b := length/k, length%k
	for i := 0; i < k; i++ {
		if root == nil {
			res = append(res, nil)
			continue
		}
		node := root
		for j := 1; j < a && root.Next != nil; j++ {
			root = root.Next
		}
		if b > 0 {
			root = root.Next
			b--
		}
		temp := root.Next
		root.Next = nil
		root = temp
		res = append(res, node)
	}
	return res
}

729.我的日程安排表I(2)¶

题目

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，
注意，这里的时间是半开区间，即 [start, end), 实数x 的范围为， start <= x < end。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。
否则，返回 false并且不要将该日程安排添加到日历中。
请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例 1:MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解释: 第一个日程安排可以添加到日历中.  第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了。
第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20 。
说明:每个测试用例，调用MyCalendar.book函数最多不超过1000次。
调用函数MyCalendar.book(start, end)时，start 和end 的取值范围为[0, 10^9]。

解题思路

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

type MyCalendar struct {
	arr [][2]int
}

func Constructor() MyCalendar {
	return MyCalendar{arr: make([][2]int, 0)}
}

func (this *MyCalendar) Book(start int, end int) bool {
	for i := 0; i < len(this.arr); i++ {
		if this.arr[i][0] < end && start < this.arr[i][1] {
			return false
		}
	}
	this.arr = append(this.arr, [2]int{start, end})
	return true
}

# 2
type MyCalendar struct {
	root *Node
}

func Constructor() MyCalendar {
	return MyCalendar{root: nil}
}

func (this *MyCalendar) Book(start int, end int) bool {
	node := &Node{
		start: start,
		end:   end,
		left:  nil,
		right: nil,
	}
	if this.root == nil {
		this.root = node
		return true
	}
	return this.root.Insert(node)
}

type Node struct {
	start int
	end   int
	left  *Node
	right *Node
}

func (this *Node) Insert(node *Node) bool {
	if node.start >= this.end {
		if this.right == nil {
			this.right = node
			return true
		}
		return this.right.Insert(node)
	} else if node.end <= this.start {
		if this.left == nil {
			this.left = node
			return true
		}
		return this.left.Insert(node)
	}
	return false
}

731.我的日程安排表II(1)¶

题目

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。
它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，
即 [start, end), 实数x 的范围为， start <= x < end。
当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。
否则，返回 false 并且不要将该日程安排添加到日历中。
请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例：MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
解释： 前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。
第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。
第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。
第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；
时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。
提示：每个测试用例，调用MyCalendar.book函数最多不超过1000次。
调用函数MyCalendar.book(start, end)时，start 和end 的取值范围为[0, 10^9]。

解题思路

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

type MyCalendarTwo struct {
	first  [][2]int
	second [][2]int
}

func Constructor() MyCalendarTwo {
	return MyCalendarTwo{}
}

func (this *MyCalendarTwo) Book(start int, end int) bool {
	for i := 0; i < len(this.second); i++ {
		a, b := this.second[i][0], this.second[i][1]
		if start < b && end > a { // 跟第二个重复
			return false
		}
	}
	for i := 0; i < len(this.first); i++ {
		a, b := this.first[i][0], this.first[i][1]
		if start < b && end > a {
			// 插入重叠的部分
			this.second = append(this.second, [2]int{max(start, a), min(end, b)})
		}
	}
	this.first = append(this.first, [2]int{start, end})
	return true
}

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

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

735.行星碰撞(2)¶

题目

给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。
每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。
如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1:输入: asteroids = [5, 10, -5] 输出: [5, 10]
解释: 10 和 -5 碰撞后只剩下 10。 5 和 10 永远不会发生碰撞。
示例 2:输入: asteroids = [8, -8] 输出: []
解释: 8 和 -8 碰撞后，两者都发生爆炸。
示例 3:输入: asteroids = [10, 2, -5] 输出: [10]
解释: 2 和 -5 发生碰撞后剩下 -5。10 和 -5 发生碰撞后剩下 10。
示例 4:输入:  asteroids = [-2, -1, 1, 2] 输出: [-2, -1, 1, 2]
解释: -2 和 -1 向左移动，而 1 和 2 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
说明:数组asteroids 的长度不超过10000。
每一颗行星的大小都是非零整数，范围是[-1000, 1000]。

解题思路

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

func asteroidCollision(asteroids []int) []int {
	left := make([]int, 0)
	right := make([]int, 0)
	for i := 0; i < len(asteroids); i++ {
		if asteroids[i] > 0 {
			right = append(right, asteroids[i])
		} else {
			if len(right) > 0 {
				for {
					if len(right) == 0 {
						left = append(left, asteroids[i])
						break
					}
					sum := asteroids[i] + right[len(right)-1]
					if sum == 0 {
						right = right[:len(right)-1]
						break
					} else if sum > 0 {
						break
					} else {
						right = right[:len(right)-1]
					}
				}
			} else {
				left = append(left, asteroids[i])
			}
		}

	}
	return append(left, right...)
}

# 2
func asteroidCollision(asteroids []int) []int {
	res := make([]int, 0)
	for i := 0; i < len(asteroids); i++ {
		value := asteroids[i]
		for value < 0 && len(res) > 0 && res[len(res)-1] > 0 {
			sum := value + res[len(res)-1]
			if sum >= 0 {
				value = 0
			}
			if sum <= 0 {
				res = res[:len(res)-1]
			}
		}
		if value != 0 {
			res = append(res, value)
		}
	}
	return res
}

738.单调递增的数字(2)¶

题目

给定一个非负整数N，找出小于或等于N的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字x和y满足x <= y时，我们称这个整数是单调递增的。）
示例 1:输入: N = 10 输出: 9
示例 2:输入: N = 1234 输出: 1234
示例 3:输入: N = 332 输出: 299
说明: N是在[0, 10^9]范围内的一个整数。

解题思路

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

func monotoneIncreasingDigits(N int) int {
	arr := []byte(strconv.Itoa(N))
	i := 1
	for i < len(arr) && arr[i-1] <= arr[i] {
		i++
	}
	// 前面有逆序的
	if i < len(arr) {
		// 前面减去1, 如：332=>2xx要减2次
		for i > 0 && arr[i] < arr[i-1] {
			arr[i-1]--
			i--
		}
		i++
		for ; i < len(arr); i++ {
			arr[i] = '9'
		}
	}
	res, _ := strconv.Atoi(string(arr))
	return res
}

# 2
func monotoneIncreasingDigits(N int) int {
	arr := []byte(strconv.Itoa(N))
	maxValue := -1
	index := -1
	for i := 0; i < len(arr)-1; i++ {
		if int(arr[i]-'0') > maxValue {
			maxValue = int(arr[i] - '0')
			index = i
		}
		if arr[i] > arr[i+1] {
			arr[index]--
			for j := index + 1; j < len(arr); j++ {
				arr[j] = '9'
			}
			break
		}
	}
	res, _ := strconv.Atoi(string(arr))
	return res
}

739.每日温度(3)¶

题目

请根据每日 气温 列表，重新生成一个列表。
对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解题思路

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

func dailyTemperatures(temperatures []int) []int {
	res := make([]int, len(temperatures))
	stack := make([]int, 0) // 栈保存递减数据的下标
	for i := 0; i < len(temperatures); i++ {
		for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
			last := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[last] = i - last
		}
		stack = append(stack, i)
	}
	return res
}

# 2
func dailyTemperatures(temperatures []int) []int {
	res := make([]int, len(temperatures))
	arr := make([]int, 101)
	for i := 0; i < len(arr); i++ {
		arr[i] = math.MaxInt64
	}
	for i := len(temperatures) - 1; i >= 0; i-- {
		temp := math.MaxInt64
		for t := temperatures[i] + 1; t < 101; t++ {
			if arr[t] < temp {
				temp = arr[t]
			}
		}
		if temp < math.MaxInt64 {
			res[i] = temp - i
		}
		arr[temperatures[i]] = i
	}
	return res
}

# 3
func dailyTemperatures(temperatures []int) []int {
	j := 0
	for i := 0; i < len(temperatures); i++ {
		for j = i + 1; j < len(temperatures); j++ {
			if temperatures[j] > temperatures[i] {
				temperatures[i] = j - i
				break
			}
		}
		if j == len(temperatures) {
			temperatures[i] = 0
		}
	}
	return temperatures
}

740.删除与获得点数(2)¶

题目

给定一个整数数组nums，你可以对它进行一些操作。
每次操作中，选择任意一个nums[i]，删除它并获得nums[i]的点数。
之后，你必须删除每个等于nums[i] - 1或nums[i] + 1的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1:输入: nums = [3, 4, 2] 输出: 6
解释: 删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。
示例2:输入: nums = [2, 2, 3, 3, 3, 4] 输出: 9
解释:  删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
注意:nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。

解题思路

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

func deleteAndEarn(nums []int) int {
	count := make([]int, 10001)
	for i := 0; i < len(nums); i++ {
		count[nums[i]]++
	}
	dp := make([]int, 10001)
	dp[1] = count[1]
	dp[2] = max(dp[1], count[2]*2)
	for i := 2; i < 10001; i++ {
		dp[i] = max(dp[i-1], dp[i-2]+i*count[i])
	}
	return dp[10000]
}

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


# 2
func deleteAndEarn(nums []int) int {
	count := make([]int, 10001)
	for i := 0; i < len(nums); i++ {
		count[nums[i]]++
	}
	a, b := 0, 0 // a使用i，b不使用i
	prev := -1
	for i := 0; i < 10001; i++ {
		if count[i] > 0 {
			maxValue := max(a, b)
			if prev != i-1 { // 不等于上一个，使用最大值
				a = i*count[i] + maxValue
				b = maxValue
			} else { // 等于上一个，使用b
				a = i*count[i] + b
				b = maxValue
			}
			prev = i
		}
	}
	return max(a, b)
}

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

743.网络延迟时间(5)¶

题目

有 n 个网络节点，标记为1到 n。
给你一个列表times，表示信号经过 有向 边的传递时间。
times[i] = (ui, vi, wi)，其中ui是源节点，vi是目标节点， wi是一个信号从源节点传递到目标节点的时间。
现在，从某个节点K发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1 。
示例 1：输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出：2
示例 2：输入：times = [[1,2,1]], n = 2, k = 1 输出：1
示例 3：输入：times = [[1,2,1]], n = 2, k = 2 输出：-1
提示：1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）

解题思路

No.	思路	时间复杂度	空间复杂度
01	Dijkstra	O(n^2)	O(n^2)
02	Dijkstra+堆	O(nlog(n))	O(n^2)
03	Bellman Ford	O(n^2)	O(n)
04	广度优先搜索	O(n^2)	O(n^2)
05	Floyd	O(n^3)	O(n^2)

func networkDelayTime(times [][]int, n int, k int) int {
	maxValue := math.MaxInt32 / 10
	arr := make([][]int, n) // i=>j的最短距离
	for i := 0; i < n; i++ {
		arr[i] = make([]int, n)
		for j := 0; j < n; j++ {
			arr[i][j] = maxValue
		}
	}
	for i := 0; i < len(times); i++ {
		a, b, c := times[i][0]-1, times[i][1]-1, times[i][2] // a=>b
		arr[a][b] = c
	}
	dis := make([]int, n) // k到其他点的距离
	for i := 0; i < n; i++ {
		dis[i] = maxValue
	}
	dis[k-1] = 0
	visited := make([]bool, n)
	for i := 0; i < n; i++ {
		target := -1 // 寻找未访问的距离起点最近点
		for j := 0; j < len(visited); j++ {
			if visited[j] == false && (target == -1 || dis[j] < dis[target]) {
				target = j
			}
		}
		visited[target] = true
		for j := 0; j < len(arr[target]); j++ { // 更新距离
			dis[j] = min(dis[j], dis[target]+arr[target][j])
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		if dis[i] == maxValue {
			return -1
		}
		res = max(res, dis[i])
	}
	return res
}

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

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

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

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

type IntHeap [][2]int

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

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

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

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

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

# 3
func networkDelayTime(times [][]int, n int, k int) int {
	maxValue := math.MaxInt32 / 10
	dis := make([]int, n) // k到其他点的距离
	for i := 0; i < n; i++ {
		dis[i] = maxValue
	}
	dis[k-1] = 0
	for k := 0; k < n-1; k++ {
		flag := true
		for i := 0; i < len(times); i++ {
			a, b, c := times[i][0]-1, times[i][1]-1, times[i][2] // a=>b
			if dis[a]+c < dis[b] {
				flag = false
				dis[b] = dis[a] + c
			}
		}
		if flag == true {
			break
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		if dis[i] == maxValue {
			return -1
		}
		res = max(res, dis[i])
	}
	return res
}

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

# 4
func networkDelayTime(times [][]int, n int, k int) int {
	maxValue := math.MaxInt32 / 10
	arr := make([][][2]int, n) // 邻接表：i=>j的集合
	for i := 0; i < len(times); i++ {
		a, b, c := times[i][0]-1, times[i][1]-1, times[i][2] // a=>b
		arr[a] = append(arr[a], [2]int{b, c})
	}
	dis := make([]int, n) // k到其他点的距离
	for i := 0; i < n; i++ {
		dis[i] = maxValue
	}
	dis[k-1] = 0
	queue := make([]int, 0)
	queue = append(queue, k-1)
	for len(queue) > 0 {
		a := queue[0]
		queue = queue[1:]
		for i := 0; i < len(arr[a]); i++ {
			b, c := arr[a][i][0], arr[a][i][1]
			if dis[a]+c < dis[b] { // 更新距离
				dis[b] = dis[a] + c
				queue = append(queue, b)
			}
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		if dis[i] == maxValue {
			return -1
		}
		res = max(res, dis[i])
	}
	return res
}

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

# 5
func networkDelayTime(times [][]int, n int, k int) int {
	maxValue := math.MaxInt32 / 10
	arr := make([][]int, n) // 邻接表：i=>j的集合
	for i := 0; i < n; i++ {
		arr[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if i == j {
				continue
			}
			arr[i][j] = maxValue
		}
	}
	for i := 0; i < len(times); i++ {
		a, b, c := times[i][0]-1, times[i][1]-1, times[i][2] // a=>b
		arr[a][b] = c
	}
	for p := 0; p < n; p++ { // floyd
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				arr[i][j] = min(arr[i][j], arr[i][p]+arr[p][j])
			}
		}
	}
	res := 0
	for i := 0; i < n; i++ {
		if arr[k-1][i] == maxValue {
			return -1
		}
		res = max(res, arr[k-1][i])
	}
	return res
}

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

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

752.打开转盘锁(1)¶

题目

你有一个带有四个圆形拨轮的转盘锁。
每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，
这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
示例 1:输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202" 输出：6
解释：可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:输入: deadends = ["8888"], target = "0009" 输出：1
解释： 把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], 
target = "8888" 输出：-1 
解释：无法旋转到目标数字且不被锁定。
示例 4:输入: deadends = ["0000"], target = "8888" 输出：-1
提示：
    死亡列表 deadends 的长度范围为 [1, 500]。
    目标数字 target 不会在 deadends 之中。
    每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

解题思路

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

func openLock(deadends []string, target string) int {
	m := make(map[string]int)
	m["0000"] = 0
	for i := 0; i < len(deadends); i++ {
		if deadends[i] == "0000" {
			return -1
		}
		m[deadends[i]] = 0
	}
	if target == "0000" {
		return 0
	}
	if _, ok := m[target]; ok {
		return -1
	}
	queue := make([]string, 0)
	queue = append(queue, "0000")
	res := 0
	dir := []int{1, -1}
	for len(queue) > 0 {
		res++
		length := len(queue)
		for i := 0; i < length; i++ {
			str := queue[i]
			for j := 0; j < 4; j++ {
				for k := 0; k < len(dir); k++ {
					char := string((int(str[j]-'0')+10+dir[k])%10 + '0')
					newStr := str[:j] + char + str[j+1:]
					if _, ok := m[newStr]; ok {
						continue
					}
					queue = append(queue, newStr)
					m[newStr] = 1
					if newStr == target {
						return res
					}
				}
			}
		}
		queue = queue[length:]
	}
	return -1
}

754.到达终点数字(2)¶

题目

在一根无限长的数轴上，你站在0的位置。终点在target的位置。
每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。
返回到达终点需要的最小移动次数。
示例 1:输入: target = 3 输出: 2
解释:第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
示例 2:输入: target = 2 输出: 3
解释: 第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
注意:target是在[-10^9, 10^9]范围中的非零整数。

解题思路

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

func reachNumber(target int) int {
	n := abs(target) // 负数转为正数，负数正数本质上都一样
	k := 0
	// S=1+...+k >= target
	// 差值：diff = S-target
	// diff为偶数：可以找到1~k之间的一个组合之和为diff/2
	// diff为奇数：需要考虑S=1~k+1或者S=1~K+2的情况，使得新diff为偶数
	for n > 0 {
		k = k + 1
		n = n - k
	}
	if n%2 == 0 {
		return k
	}
	return k + 1 + k%2
}

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

# 2
func reachNumber(target int) int {
	n := abs(target) // 负数转为正数，负数正数本质上都一样
	k := 1
	// S=1+...+k >= target
	// 差值：diff = S-target
	// diff为偶数：可以找到1~k之间的一个组合之和为diff/2
	// diff为奇数：需要考虑S=1~k+1或者S=1~K+2的情况，使得新diff为偶数
	// =>求S>=target 并且使用diff为偶数
	for {
		sum := k * (k + 1) / 2
		if sum >= n && (sum-n)%2 == 0 {
			return k
		}
		k++
	}
}

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

756.金字塔转换矩阵¶

题目¶

现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。
使用三元组表示金字塔的堆砌规则如下：
对于三元组 ABC ，C 为顶层方块，方块 A 、B 分别作为方块 C 下一层的的左、右子块。
当且仅当 ABC 是被允许的三元组，我们才可以将其堆砌上。
初始时，给定金字塔的基层bottom，用一个字符串表示。一个允许的三元组列表allowed，每个三元组用一个长度为 3 的字符串表示。
如果可以由基层一直堆到塔尖就返回 true ，否则返回 false 。
示例 1：输入：bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"] 输出：true
解释：可以堆砌成这样的金字塔:
    A
   / \
  G   E
 / \ / \
B   C   D
因为符合 BCG、CDE 和 GEA 三种规则。
示例 2：输入：bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"] 输出：false
解释：无法一直堆到塔尖。
注意, 允许存在像 ABC 和 ABD 这样的三元组，其中 C != D。
提示：bottom 的长度范围在[2, 8]。
allowed 的长度范围在[0, 200]。
方块的标记字母范围为{'A', 'B', 'C', 'D', 'E', 'F', 'G'}。

解题思路¶

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

763.划分字母区间(2)¶

题目

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。
返回一个表示每个字符串片段的长度的列表。
示例 1：输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8]
解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：S的长度在[1, 500]之间。
    S只包含小写字母 'a' 到 'z' 。

解题思路

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

func partitionLabels(S string) []int {
	m := make(map[byte]int)
	for i := 0; i < len(S); i++ {
		m[S[i]] = i
	}
	res := make([]int, 0)
	left := 0
	right := 0
	for i := 0; i < len(S); i++ {
		right = max(right, m[S[i]])
		if i == right {
			res = append(res, right-left+1)
			left = right + 1
		}
	}
	return res
}

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

# 2
func partitionLabels(S string) []int {
	res := make([]int, 0)
	left := 0
	right := 0
	for i := 0; i < len(S); i++ {
		right = max(right, strings.LastIndex(S, string(S[i])))
		if i == right {
			res = append(res, right-left+1)
			left = right + 1
		}
	}
	return res
}

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

767.重构字符串(2)¶

题目

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
示例 1:输入: S = "aab" 输出: "aba"
示例 2:输入: S = "aaab" 输出: ""
注意: S 只包含小写字母并且长度在[1, 500]区间内。

解题思路

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

func reorganizeString(S string) string {
	n := len(S)
	if n <= 1 {
		return S
	}
	res := make([]byte, 0)
	m := make(map[byte]int)
	for _, v := range S {
		m[byte(v)]++
	}
	nodeHeap := &Heap{}
	heap.Init(nodeHeap)
	for k, v := range m {
		if v > (n+1)/2 {
			return ""
		}
		heap.Push(nodeHeap, Node{
			char: k,
			num:  v,
		})
	}
	for nodeHeap.Len() >= 2 {
		node1 := heap.Pop(nodeHeap).(Node)
		node2 := heap.Pop(nodeHeap).(Node)
		res = append(res, node1.char, node2.char)
		node1.num--
		node2.num--
		if node1.num > 0 {
			heap.Push(nodeHeap, node1)
		}
		if node2.num > 0 {
			heap.Push(nodeHeap, node2)
		}
	}
	if nodeHeap.Len() > 0 {
		t := heap.Pop(nodeHeap).(Node)
		res = append(res, t.char)
	}
	return string(res)
}

type Node struct {
	char byte
	num  int
}

type Heap []Node

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

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

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

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

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

# 2
func reorganizeString(S string) string {
	arr := make([]node, 26)
	maxCount := 0
	for _, char := range S {
		index := char - 'a'
		arr[index].char = char
		arr[index].num++
		if arr[index].num > maxCount {
			maxCount = arr[index].num
		}
	}
	if maxCount > (len(S)+1)/2 {
		return ""
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i].num >= arr[j].num
	})
	res := make([]rune, len(S))
	var index int
	// 先偶后奇
	for i := 0; i < 2; i++ {
		for j := i; j < len(S); j = j + 2 {
			if arr[index].num == 0 {
				index++
			}
			res[j] = arr[index].char
			arr[index].num--
		}
	}
	return string(res)
}

769.最多能完成排序的块(1)¶

题目

数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，
并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
示例 1:输入: arr = [4,3,2,1,0] 输出: 1
解释:将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
示例 2:输入: arr = [1,0,2,3,4] 输出: 4
解释:我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
注意:arr 的长度在 [1, 10] 之间。
arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。

解题思路

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

func maxChunksToSorted(arr []int) int {
	res := 0
	maxValue := 0
	for i := 0; i < len(arr); i++ {
		if arr[i] > maxValue {
			maxValue = arr[i]
		}
		if maxValue == i {
			res++
		}
	}
	return res
}

775.全局倒置与局部倒置(3)¶

题目

数组A是[0, 1, ..., N - 1]的一种排列，N 是数组A的长度。
全局倒置指的是 i,j满足0 <= i < j < N 并且A[i] > A[j]，
局部倒置指的是 i 满足0 <= i < N并且A[i] > A[i+1]。
当数组A中全局倒置的数量等于局部倒置的数量时，返回 true 。
示例 1:输入: A = [1,0,2] 输出: true
解释: 有 1 个全局倒置，和 1 个局部倒置。
示例 2:输入: A = [1,2,0] 输出: false
解释: 有 2 个全局倒置，和 1 个局部倒置。
注意:A 是[0, 1, ..., A.length - 1]的一种排列
A 的长度在[1, 5000]之间
这个问题的时间限制已经减少了。

解题思路

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

func isIdealPermutation(A []int) bool {
	if len(A) < 3 {
		return true
	}
	// 局部倒置首先是一个全局倒置，因此无需统计局部倒置
	// 只需要判断是否存在 0<=i<k<j<N 并且A[i]>A[j]
	maxValue := A[0] // 前2位数组最大值，如果存在maxValue > A[i]，则不会相等
	for i := 2; i < len(A); i++ {
		if maxValue > A[i] {
			return false
		}
		if maxValue < A[i-1] {
			maxValue = A[i-1]
		}
	}
	return true
}

# 2
func isIdealPermutation(A []int) bool {
	if len(A) < 3 {
		return true
	}
	minValue := len(A)
	for i := len(A) - 1; i >= 2; i-- {
		if A[i] < minValue {
			minValue = A[i]
		}
		if A[i-2] > minValue {
			return false
		}
	}
	return true
}

# 3
func isIdealPermutation(A []int) bool {
	if len(A) < 3 {
		return true
	}
	for i := 0; i < len(A); i++ {
		if abs(i-A[i]) > 1 {
			return false
		}
	}
	return true
}

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

777.在LR字符串中交换相邻字符(1)¶

题目

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。
一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。
现给定起始字符串start和结束字符串end，请编写代码，
当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。
示例 :输入: start = "RXXLRXRXL", end = "XRLXXRRLX" 输出: True
解释:我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
提示：1 <= len(start) = len(end) <= 10000。
start和end中的字符串仅限于'L', 'R'和'X'。

解题思路

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

func canTransform(start string, end string) bool {
	if strings.ReplaceAll(start, "X", "") != strings.ReplaceAll(end, "X", "") {
		return false
	}
	j := 0
	for i := 0; i < len(start); i++ {
		if start[i] == 'L' { // LX=>XL, L是往右的
			for end[j] != 'L' {
				j++
			}
			if i < j {
				return false
			}
			j++
		}
	}
	j = 0
	for i := 0; i < len(start); i++ {
		if start[i] == 'R' { // XR=>RX, R是往左的
			for end[j] != 'R' {
				j++
			}
			if i > j {
				return false
			}
			j++
		}
	}
	return true
}

779.第K个语法符号(3)¶

题目

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
例子:输入: N = 1, K = 1 输出: 0
输入: N = 2, K = 1 输出: 0
输入: N = 2, K = 2 输出: 1
输入: N = 4, K = 5 输出: 1
解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001
注意： N 的范围 [1, 30]. K 的范围 [1, 2^(N-1)].

解题思路

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

func kthGrammar(N int, K int) int {
	if K == 1 {
		return 0
	}
    // N行K的数是由N-1行(K+1)/2的数来的
	temp := kthGrammar(N-1, (K+1)/2)
	if K%2 == 1 {
		return temp
	}
	return 1 - temp
}

# 2
func kthGrammar(N int, K int) int {
	if K == 1 {
		return 0
	}
	total := int(math.Pow(2, float64(N-1)))
	half := total / 2
	if K <= half {
		return kthGrammar(N-1, K)
	}
	return 1 - kthGrammar(N-1, K-half)
}

# 3
func kthGrammar(N int, K int) int {
	return bits.OnesCount(uint(K-1))%2
}

781.森林中的兔子(2)¶

题目

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。
我们将这些回答放在 answers 数组里。
返回森林中兔子的最少数量。
示例:输入: answers = [1, 1, 2] 输出: 5
解释:两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
输入: answers = [10, 10, 10] 输出: 11
输入: answers = [] 输出: 0
说明: answers 的长度最大为1000。
    answers[i] 是在 [0, 999] 范围内的整数。

解题思路

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

func numRabbits(answers []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(answers); i++ {
		value := answers[i]
		if m[value] == 0 {
			res = res + value + 1
		}
		m[value]++
		if m[value] == value+1 {
			m[value] = 0
		}
	}
	return res
}

# 2
func numRabbits(answers []int) int {
	res := 0
	m := make(map[int]int)
	for i := 0; i < len(answers); i++ {
		value := answers[i]
		m[value]++
	}
	for k, v := range m {
		target := k + 1
		res = res + v/target*target
		if v%target > 0 {
			res = res + target
		}
	}
	return res
}

785.判断二分图(3)¶

题目

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。
给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
不存在自环（graph[u] 不包含 u）。
不存在平行边（graph[u] 不包含重复值）。
如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，
并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
如果图是二分图，返回 true ；否则，返回 false 。
示例 1：输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。
示例 2：输入：graph = [[1,3],[0,2],[1,3],[0,2]] 输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。
提示：graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1
graph[u] 不会包含 u
graph[u] 的所有值 互不相同
如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

解题思路

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

// 思路同leetcode886.可能的二分法
var m map[int]int

func isBipartite(graph [][]int) bool {
	n := len(graph)
	m = make(map[int]int) // 分组： 0一组，1一组
	for i := 0; i < n; i++ {
		// 没有被分配过，分配到0一组
		if _, ok := m[i]; ok == false && dfs(graph, i, 0) == false {
			return false
		}
	}
	return true
}

func dfs(arr [][]int, index int, value int) bool {
	if v, ok := m[index]; ok {
		return v == value // 已经分配，查看是否同一组
	}
	m[index] = value
	for i := 0; i < len(arr[index]); i++ {
		target := arr[index][i]
		if dfs(arr, target, 1-value) == false { // 不喜欢的人，分配到对立组：1-value
			return false
		}
	}
	return true
}

# 2
func isBipartite(graph [][]int) bool {
	n := len(graph)
	m := make(map[int]int) // 分组： 0一组，1一组
	for i := 0; i < n; i++ {
		// 没有被分配过，分配到0一组
		if _, ok := m[i]; ok == true {
			continue
		}
		m[i] = 0
		queue := make([]int, 0)
		queue = append(queue, i)
		for len(queue) > 0 {
			node := queue[0]
			queue = queue[1:]
			for i := 0; i < len(graph[node]); i++ {
				target := graph[node][i]
				if _, ok := m[target]; ok == false {
					m[target] = 1 - m[node] // 相反一组
					queue = append(queue, target)
				} else if m[node] == m[target] { // 已经分配，查看是否同一组
					return false
				}
			}
		}
	}
	return true
}

# 3
func isBipartite(graph [][]int) bool {
	n := len(graph)
	fa = Init(n)
	for i := 0; i < n; i++ {
		for j := 0; j < len(graph[i]); j++ {
			target := graph[i][j]
			if find(i) == find(target) { // 和不喜欢的人在相同组，失败
				return false
			}
			union(graph[i][0], target) // 不喜欢的人在同一组
		}
	}
	return true
}

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 {
	for x != fa[x] {
		fa[x] = fa[fa[x]]
		x = fa[x]
	}
	return x
}

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

787.K站中转内最便宜的航班(4)¶

题目

有 n 个城市通过一些航班连接。给你一个数组flights ，
其中flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k站中转的路线，
使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
示例 1：输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 输出: 200
解释: 城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
示例 2：输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 输出: 500
解释: 城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。
提示：1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
航班没有重复，且不存在自环
0 <= src, dst, k < n
src != dst

解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划-二维	O(n^2)	O(n^2)
02	动态规划-一维	O(n^2)	O(n)
03	广度优先搜索	O(n^2)	O(n)
04	Bellman-Ford	O(n^2)	O(n)

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	maxValue := math.MaxInt32 / 10
	dp := make([][]int, k+2) // dp[i][j] => 经过i次航班到j地需要的最少花费（k次中转需要k+1次航班）
	for i := 0; i <= k+1; i++ {
		dp[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dp[i][j] = maxValue
		}
	}
	dp[0][src] = 0 // 到开始地为0
	for i := 1; i <= k+1; i++ {
		for j := 0; j < len(flights); j++ {
			a, b, c := flights[j][0], flights[j][1], flights[j][2] // a=>b c
			dp[i][b] = min(dp[i][b], dp[i-1][a]+c)
		}
	}
	res := maxValue
	for i := 1; i <= k+1; i++ {
		res = min(res, dp[i][dst])
	}
	if res == maxValue {
		return -1
	}
	return res
}

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

# 2
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	maxValue := math.MaxInt32 / 10
	dp := make([]int, n) // dp[i] => 到j地需要的最少花费（k次中转需要k+1次航班）
	for i := 0; i < n; i++ {
		dp[i] = maxValue
	}
	dp[src] = 0 // 到开始地为0
	res := maxValue
	for i := 1; i <= k+1; i++ {
		temp := make([]int, n)
		for j := 0; j < n; j++ {
			temp[j] = maxValue
		}
		for j := 0; j < len(flights); j++ {
			a, b, c := flights[j][0], flights[j][1], flights[j][2] // a=>b c
			temp[b] = min(temp[b], dp[a]+c)

		}
		res = min(res, temp[dst])
		dp = temp
	}
	if res == maxValue {
		return -1
	}
	return res
}

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

# 3
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	maxValue := math.MaxInt32 / 10
	prices := make([]int, n)
	arr := make([][][2]int, n)
	for i := 0; i < n; i++ {
		prices[i] = maxValue
	}
	prices[src] = 0
	for i := 0; i < len(flights); i++ {
		a, b, c := flights[i][0], flights[i][1], flights[i][2] // a=>b c
		arr[a] = append(arr[a], [2]int{b, c})
	}
	queue := make([][3]int, 0)
	queue = append(queue, [3]int{1, src, prices[src]}) // 次数，起点，价格
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node[0] > k+1 { // 大于k+1次退出
			break
		}
		cur, value := node[1], node[2]
		for i := 0; i < len(arr[cur]); i++ {
			b, c := arr[cur][i][0], arr[cur][i][1]
			if prices[b] > c+value {
				prices[b] = c + value
				queue = append(queue, [3]int{node[0] + 1, b, prices[b]})
			}
		}
	}
	if prices[dst] == maxValue {
		return -1
	}
	return prices[dst]
}

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

# 4
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	maxValue := math.MaxInt32 / 10
	dis := make([]int, n)
	for i := 0; i < n; i++ {
		dis[i] = maxValue
	}
	dis[src] = 0 // 到开始地为0
	for i := 1; i <= k+1; i++ {
		temp := make([]int, n)
		copy(temp, dis)
		for j := 0; j < len(flights); j++ {
			a, b, c := flights[j][0], flights[j][1], flights[j][2] // a=>b c
			temp[b] = min(temp[b], dis[a]+c)
		}
		dis = temp
	}
	if dis[dst] == maxValue {
		return -1
	}
	return dis[dst]
}

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

789.逃脱阻碍者(1)¶

题目

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是target = [xtarget, ytarget] 。
地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从ghosts[i] = [xi, yi]出发。
所有输入均为 整数坐标 。
每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。
当然，也可以选择 不动 。所有动作 同时 发生。
如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。
如果你和阻碍者同时到达了一个位置（包括目的地）都不算是逃脱成功。
只有在你有可能成功逃脱时，输出 true ；否则，输出 false 。
示例 1：输入：ghosts = [[1,0],[0,3]], target = [0,1] 输出：true
解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。 
示例 2：输入：ghosts = [[1,0]], target = [2,0] 输出：false
解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。 
示例 3：输入：ghosts = [[2,0]], target = [1,0] 输出：false
解释：阻碍者可以和你同时达到目的地。 
示例 4：输入：ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]], target = [7,7] 输出：false
示例 5：输入：ghosts = [[-1,0],[0,1],[-1,0],[0,1],[-1,0]], target = [0,0] 输出：true
提示：1 <= ghosts.length <= 100
ghosts[i].length == 2
-104 <= xi, yi <= 104
同一位置可能有 多个阻碍者 。
target.length == 2
-104 <= xtarget, ytarget <= 104

解题思路

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

func escapeGhosts(ghosts [][]int, target []int) bool {
	a := abs(target[0]) + abs(target[1])
	for i := 0; i < len(ghosts); i++ {
		b := abs(ghosts[i][0]-target[0]) + abs(ghosts[i][1]-target[1])
		if b <= a {
			return false
		}
	}
	return true
}

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

790.多米诺和托米诺平铺(2)¶

题目

有两种形状的瓷砖：一种是2x1 的多米诺形，另一种是形如"L" 的托米诺形。两种形状都可以旋转。
XX  <- 多米诺
XX  <- "L" 托米诺
X
给定N 的值，有多少种方法可以平铺2 x N 的面板？返回值 mod 10^9 + 7。
（平铺指的是每个正方形都必须有瓷砖覆盖。
两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。）
示例:输入: 3 输出: 5
解释: 下面列出了五种不同的方法，不同字母代表不同瓷砖：
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
提示：N 的范围是[1, 1000]

解题思路

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

var mod = 1000000007

func numTilings(N int) int {
	dp := [4]int{}
	dp[0] = 1
	for i := 0; i < N; i++ {
		temp := [4]int{}
		temp[0] = (dp[0] + dp[3]) % mod
		temp[1] = (dp[0] + dp[2]) % mod
		temp[2] = (dp[0] + dp[1]) % mod
		temp[3] = (dp[0] + dp[1] + dp[2]) % mod
		dp = temp
	}
	return dp[0]
}

# 2
func numTilings(N int) int {
	dp := make([]int, N+3)
	dp[1] = 1
	dp[2] = 2
	dp[3] = 5
	for i := 4; i <= N; i++ {
		dp[i] = (2*dp[i-1] + dp[i-3]) % 1000000007
	}
	return dp[N]
}

791.自定义字符串排序(3)¶

题目

字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。
S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。
更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。
返回任意一种符合条件的字符串T。
示例: 输入:
S = "cba"
T = "abcd"
输出: "cbad"
解释: S中出现了字符 "a", "b", "c", 所以 "a", "b", "c" 的顺序应该是 "c", "b", "a". 
由于 "d" 没有在S中出现, 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的输出。
注意:S的最大长度为26，其中没有重复的字符。
T的最大长度为200。
S和T只包含小写字符。

解题思路

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

func customSortString(S string, T string) string {
	m := make(map[uint8]int)
	for i := 0; i < len(S); i++ {
		m[S[i]] = i
	}
	arr := []byte(T)
	sort.Slice(arr, func(i, j int) bool {
		return m[arr[i]] < m[arr[j]]
	})
	return string(arr)
}

# 2
func customSortString(S string, T string) string {
	count := make([]int, 26)
	for i := 0; i < len(T); i++ {
		count[T[i]-'a']++
	}
	res := make([]byte, 0)
	for i := 0; i < len(S); i++ {
		for j := 0; j < count[S[i]-'a']; j++ {
			res = append(res, S[i])
		}
		count[S[i]-'a'] = 0
	}
	for i := 0; i < 26; i++ {
		for j := 0; j < count[i]; j++ {
			res = append(res, byte(i+'a'))
		}
	}
	return string(res)
}

# 3
func customSortString(S string, T string) string {
	res := []byte(T)
	index := 0
	for i := 0; i < len(S); i++ {
		for j := 0; j < len(res); j++ {
			if res[j] == S[i] {
				res[j], res[index] = res[index], res[j]
				index++
			}
		}
	}
	return string(res)
}

792.匹配子序列的单词数(2)¶

题目

给定字符串 S 和单词字典 words, 求words[i]中是S的子序列的单词个数。
示例:输入: S = "abcde" words = ["a", "bb", "acd", "ace"] 输出: 3
解释: 有三个是S 的子序列的单词: "a", "acd", "ace"。
注意:所有在words和S里的单词都只由小写字母组成。
S 的长度在[1, 50000]。
words的长度在[1, 5000]。
words[i]的长度在[1, 50]。

解题思路

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

func numMatchingSubseq(S string, words []string) int {
	res := 0
	m := make(map[string]int)
	for i := 0; i < len(words); i++ {
		m[words[i]]++
	}
	for k, v := range m {
		if judge(S, k) == true {
			res = res + v
		}
	}
	return res
}

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

# 2
func numMatchingSubseq(S string, words []string) int {
	res := 0
	for i := 0; i < len(words); i++ {
		if len(words[i]) > len(S) {
			continue
		}
		k := 0
		for j := 0; j < len(S); j++ {
			if S[j] == words[i][k] {
				k++
				if k == len(words[i]) {
					res++
					break
				}
			}
		}
	}
	return res
}

794.有效的井字游戏(1)¶

题目

用字符串数组作为井字游戏的游戏板board。当且仅当在井字游戏过程中，玩家有可能将字符放置成游戏板所显示的状态时，才返回 true。
该游戏板是一个 3 x 3 数组，由字符" "，"X"和"O"组成。字符" "代表一个空位。
以下是井字游戏的规则：
玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符 “X”，且第二个玩家总是放字符 “O”。
“X” 和 “O” 只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。
示例 1:输入: board = ["O ", " ", " "] 输出: false
解释: 第一个玩家总是放置“X”。
示例 2:输入: board = ["XOX", " X ", "   "] 输出: false
解释: 玩家应该是轮流放置的。
示例 3:输入: board = ["XXX", "   ", "OOO"] 输出: false
示例 4:输入: board = ["XOX", "O O", "XOX"] 输出: true
说明:游戏板board是长度为 3 的字符串数组，其中每个字符串board[i]的长度为3。
board[i][j]是集合{" ", "X", "O"}中的一个字符。

解题思路

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

func validTicTacToe(board []string) bool {
	var XCount, OCount int
	n := len(board)
	rows := make([][2]int, n)         // 行
	cols := make([][2]int, n)         // 列
	left, right := [2]int{}, [2]int{} // 对角线
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'X' {
				XCount++
				rows[i][0]++
				cols[j][0]++
				if i == j {
					left[0]++
				}
				if i == n-1-j {
					right[0]++
				}
			} else if board[i][j] == 'O' {
				OCount++
				rows[i][1]++
				cols[j][1]++
				if i == j {
					left[1]++
				}
				if i == n-1-j {
					right[1]++
				}
			}
		}
	}
	if XCount != OCount && XCount-1 != OCount {
		return false
	}
	for i := 0; i < n; i++ { // 行列判断
		if (rows[i][0] == n || cols[i][0] == n) && XCount-1 != OCount {
			return false
		}
		if (rows[i][1] == n || cols[i][1] == n) && XCount != OCount {
			return false
		}
	}
	if (left[0] == n || right[0] == n) && XCount-1 != OCount { // 对角线判断
		return false
	}
	if (left[1] == n || right[1] == n) && XCount != OCount {
		return false
	}
	return true
}

795.区间子数组个数(4)¶

题目

给定一个元素都是正整数的数组A，正整数 L以及R(L <= R)。
求连续、非空且其中最大元素满足大于等于L小于等于R的子数组个数。
例如 : 输入: A = [2, 1, 4, 3] L = 2 R = 3  输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].
注意:L, R 和A[i] 都是整数，范围在[0, 10^9]。
数组A的长度范围在[1, 50000]。

解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历	O(n)	O(1)
02	动态规划	O(n)	O(n)
03	遍历	O(n)	O(1)
04	双指针	O(n)	O(1)

func numSubarrayBoundedMax(nums []int, left int, right int) int {
	// L~R范围的组合数=0~R范围的组合数- 0~L-1范围的组合数
	return count(nums, right) - count(nums, left-1)
}

func count(nums []int, target int) int {
	res := 0
	total := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] <= target {
			total++
		} else {
			total = 0
		}
		res = res + total
	}
	return res
}

# 2
func numSubarrayBoundedMax(nums []int, left int, right int) int {
	// L~R范围的组合数=0~R范围的组合数- 0~L-1范围的组合数
	return count(nums, right) - count(nums, left-1)
}

func count(nums []int, target int) int {
	res := 0
	n := len(nums)
	dp := make([]int, n)
	if nums[0] <= target {
		dp[0] = 1
	}
	res = res + dp[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] <= target {
			dp[i] = dp[i-1] + 1
		}
		res = res + dp[i]
	}
	return res
}

# 3
func numSubarrayBoundedMax(nums []int, left int, right int) int {
	// L~R范围的组合数=0~R范围的组合数- 0~L-1范围的组合数
	return count(nums, right) - count(nums, left-1)
}

func count(nums []int, target int) int {
	res := 0
	total := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] <= target {
			total++
		} else {
			res = res + (total+1)*total/2
			total = 0
		}
	}
	res = res + (total+1)*total/2
	return res
}

# 4
func numSubarrayBoundedMax(nums []int, left int, right int) int {
	res := 0
	j := -1
	count := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] > right {
			j = i
		}
		if nums[i] >= left {
			count = i - j // 满足要求，如果大于right，则count=0
		}
		res = res + count
	}
	return res
}

797.所有可能的路径(1)¶

题目

给一个有n个结点的有向无环图，找到所有从0到n-1的路径并输出（不要求按顺序）
二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点
（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ）空就是没有下一个结点了。
示例 1：输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
示例 3：输入：graph = [[1],[]] 输出：[[0,1]]
示例 4：输入：graph = [[1,2,3],[2],[3],[]] 输出：[[0,1,2,3],[0,2,3],[0,3]]
示例 5：输入：graph = [[1,3],[2],[3],[]] 输出：[[0,1,2,3],[0,3]]
提示：结点的数量会在范围[2, 15]内。
你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。

解题思路

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

var res [][]int

func allPathsSourceTarget(graph [][]int) [][]int {
	res = make([][]int, 0)
	dfs(graph, 0, len(graph)-1, make([]int, 0))
	return res
}

func dfs(graph [][]int, cur, target int, path []int) {
	if cur == target {
		path = append(path, cur)
		temp := make([]int, len(path))
		copy(temp, path)
		res = append(res, temp)
		return
	}
	for i := 0; i < len(graph[cur]); i++ {
		dfs(graph, graph[cur][i], target, append(path, cur))
	}
}

799.香槟塔(1)¶

题目

我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，
第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，
任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。
当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。
（当最底层的玻璃杯满了，香槟会流到地板上）
例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。
在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。
在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。
现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（i 和 j都从0开始）。
示例 1:输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.0
解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。
示例 2:输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.5
解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。
注意:poured的范围[0, 10 ^ 9]。
query_glass和query_row的范围[0, 99]。

解题思路

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

func champagneTower(poured int, query_row int, query_glass int) float64 {
	n, m := query_row, query_glass
	dp := make([][]float64, n+2)
	for i := 0; i < n+2; i++ {
		dp[i] = make([]float64, n+2)
	}
	dp[0][0] = float64(poured) // 初始值
	for i := 0; i <= n; i++ {
		for j := 0; j <= i; j++ {
			if dp[i][j] > 1 {
				dp[i+1][j] = dp[i+1][j] + (dp[i][j]-1)/2.0     // 往左分
				dp[i+1][j+1] = dp[i+1][j+1] + (dp[i][j]-1)/2.0 // 往右分
			}
		}
	}
	if dp[n][m] > 1 {
		return 1.0
	}
	return dp[n][m]
}

0701-0800-Hard¶

710.黑名单中的随机数(1)¶

题目

给定一个包含 [0，n ) 中独特的整数的黑名单 B，写一个函数从 [ 0，n ) 中返回一个不在 B 中的随机整数。
对它进行优化使其尽量少调用系统方法 Math.random() 。
提示:1 <= N <= 1000000000
0 <= B.length < min(100000, N)
[0, N)不包含N，详细参见interval notation。
示例 1:输入: ["Solution","pick","pick","pick"] [[1,[]],[],[],[]]
输出: [null,0,0,0]
示例 2:输入: ["Solution","pick","pick","pick"] [[2,[]],[],[],[]]
输出: [null,1,1,1]
示例 3:输入: ["Solution","pick","pick","pick"] [[3,[1]],[],[],[]]
Output: [null,0,0,2]
示例 4:输入: ["Solution","pick","pick","pick"] [[4,[2]],[],[],[]]
输出: [null,1,3,1]
输入语法说明：
输入是两个列表：调用成员函数名和调用的参数。Solution的构造函数有两个参数，N和黑名单B。
pick没有参数，输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

解题思路

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

type Solution struct {
	m map[int]int
	N int
}

func Constructor(N int, blacklist []int) Solution {
	m := make(map[int]int)
	temp := make(map[int]bool)
	for i := 0; i < len(blacklist); i++ {
		temp[blacklist[i]] = true
	}
	length := N - len(blacklist)
	arr := make([]int, 0) // 需要替换为较大数
	for i := 0; i < len(blacklist); i++ {
		if blacklist[i] < length {
			arr = append(arr, blacklist[i])
		}
	}
	a := make([]int, 0) // 没有使用过的较大数
	for i := length; i < N; i++ {
		if temp[i] == false {
			a = append(a, i)
		}
	}

	for i := 0; i < len(a); i++ {
		m[arr[i]] = a[i]
	}
	return Solution{
		m: m,
		N: length,
	}
}

func (this *Solution) Pick() int {
	index := rand.Intn(this.N)
	if value, ok := this.m[index]; ok {
		return value
	}
	return index
}

719.找出第k小的距离对(2)¶

题目

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
示例 1:输入：nums = [1,3,1] k = 1 输出：0 
解释：所有数对如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
提示:2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序+二分查找	O(nlog(n))	O(1)
02	排序+计数	O(n^2)	O(n)

func smallestDistancePair(nums []int, k int) int {
	sort.Ints(nums)
	n := len(nums)
	left, right := 0, nums[n-1]-nums[0]
	for left < right {
		mid := left + (right-left)/2
		if judge(nums, mid, k) == true {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

func judge(nums []int, mid, k int) bool {
	count := 0
	left := 0
	for right := 0; right < len(nums); right++ {
		for nums[right]-nums[left] > mid {
			left++
		}
		count = count + right - left
	}
	return k <= count
}

# 2
func smallestDistancePair(nums []int, k int) int {
	sort.Ints(nums)
	n := len(nums)
	arr := make([]int, nums[n-1]-nums[0]+1)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			arr[nums[j]-nums[i]]++
		}
	}
	count := 0
	for i := 0; i < len(arr); i++ {
		count = count + arr[i]
		if count >= k {
			return i
		}
	}
	return 0
}

732.我的日程安排表III(2)¶

题目

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。
给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。
实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。
MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。
示例：输入： ["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：[null, 1, 1, 2, 3, 3, 3]
解释：MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3
提示：0 <= start < end <= 109
每个测试用例，调用 book函数最多不超过400次

解题思路

No.	思路	时间复杂度	空间复杂度
01	差分	O(n^2log(n))	O(n)
02	线段树	O(nlog(n))	O(n)

type MyCalendarThree struct {
	m map[int]int
}

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

func (this *MyCalendarThree) Book(start int, end int) int {
	this.m[start]++
	this.m[end]--
	arr := make([]int, 0)
	for k := range this.m {
		arr = append(arr, k)
	}
	sort.Ints(arr)
	res := 0
	sum := 0
	for i := 0; i < len(arr); i++ {
		sum = sum + this.m[arr[i]]
		if sum > res {
			res = sum
		}
	}
	return res
}

# 2
type MyCalendarThree struct {
	root *Node
}

func Constructor() MyCalendarThree {
	return MyCalendarThree{root: &Node{
		start: 0,
		end:   1000000000,
	}}
}

func (this *MyCalendarThree) Book(start int, end int) int {
	return this.root.Insert(start, end)
}

type Node struct {
	start int
	end   int
	count int
	delay int // 延迟更新线段树
	left  *Node
	right *Node
}

func (root *Node) getMid() int {
	return (root.start + root.end) / 2
}

func (root *Node) Left() *Node {
	if root.left == nil {
		root.left = &Node{
			start: root.start,
			end:   root.getMid(),
		}
	}
	return root.left
}

func (root *Node) Right() *Node {
	if root.right == nil {
		root.right = &Node{
			start: root.getMid(),
			end:   root.end,
		}
	}
	return root.right
}

func (root *Node) Insert(s, e int) int {
	if s <= root.start && root.end <= e { // 包含
		root.delay++
		root.count++
	} else if s < root.end && root.start < e { // 相交
		// 自上向下延迟更新
		root.Left().count = root.Left().count + root.delay
		root.Left().delay = root.Left().delay + root.delay
		root.Right().count = root.Right().count + root.delay
		root.Right().delay = root.Right().delay + root.delay
		root.delay = 0
		a := root.Left().Insert(s, e)
		b := root.Right().Insert(s, e)
		root.count = max(root.count, max(a, b))
	}
	return root.count
}

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

757.设置交集大小至少为2(2)¶

题目

一个整数区间[a, b](a < b) 代表着从a到b的所有连续整数，包括a和b。
给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
输出这个最小集合S的大小。
示例 1:输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]] 输出: 3
解释:考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况，故我们输出3。
示例 2:输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]] 输出: 5
解释: 最小的集合S = {1, 2, 3, 4, 5}.
注意:intervals的长度范围为[1, 3000]。
intervals[i]长度为2，分别代表左、右边界。
intervals[i][j] 的值是[0, 10^8]范围内的整数。

解题思路

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

func intersectionSizeTwo(intervals [][]int) int {
	n := len(intervals)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = 2 // 每个区间还需要找到的交点的个数默认为2
	}
	res := 0
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] > intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})
	for i := n - 1; i >= 0; i-- {
		start := intervals[i][0]
		for k := start; k < start+arr[i]; k++ { // 一般最多取前面2个（start、start+1）
			for j := i - 1; j >= 0; j-- { // 往前遍历
				if arr[j] > 0 && k <= intervals[j][1] { // 当前的start或者start+1小于前面的end，交点arr[j]-1
					arr[j]--
				}
			}
		}
		res = res + arr[i]
	}
	return res
}

# 2
func intersectionSizeTwo(intervals [][]int) int {
	n := len(intervals)
	arr := []int{-1, -1}
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][1] == intervals[j][1] {
			return intervals[i][0] > intervals[j][0]
		}
		return intervals[i][1] < intervals[j][1]
	})
	for i := 0; i < n; i++ {
		start, end := intervals[i][0], intervals[i][1]
		a, b := arr[len(arr)-2], arr[len(arr)-1]
		if start <= a { // 上一个开始值已经包括当前start
			continue
		}
		if b < start { // 当前开始大于之前结束，把[end-1,end]包括
			arr = append(arr, end-1)
		}
		arr = append(arr, end)
	}
	return len(arr) - 2
}

765.情侣牵手(2)¶

题目

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 
计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用0到2N-1的整数表示，情侣们按顺序编号，
第一对是(0, 1)，第二对是(2, 3)，以此类推，最后一对是(2N-2, 2N-1)。
这些情侣的初始座位row[i]是由最初始坐在第 i 个座位上的人决定的。
示例 1:输入: row = [0, 2, 1, 3] 输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。
示例 2:输入: row = [3, 2, 0, 1] 输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。
说明:len(row) 是偶数且数值在[4, 60]范围内。
可以保证row 是序列0...len(row)-1的一个全排列。

解题思路

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

func minSwapsCouples(row []int) int {
	n := len(row) / 2
	fa := make([]int, n)
	for i := 0; i < n; i++ {
		fa[i] = i
	}
	// 将每张沙发上的两个人员编号union一下，如果本来编号就相同，则表示两个人是一类
	for i := 0; i < len(row); i = i + 2 {
		a, b := row[i]/2, row[i+1]/2
		union(fa, a, b)
	}
	res := 0
	for i := 0; i < n; i++ {
		// 几个相同，就有几个环
		if find(fa, i) == i {
			res++
		}
	}
	// 如果3组1个环，需要的次数是3-1=2，另外4组1个环，需要的次数是4-1=3。4+3-2=5
	// 组数-减去环数
	return n - res
}

func union(fa []int, a, b int) {
	fa[find(fa, a)] = find(fa, b)
}

func find(fa []int, a int) int {
	for fa[a] != a {
		fa[a] = fa[fa[a]]
		a = fa[a]
	}
	return a
}

# 2
func minSwapsCouples(row []int) int {
	res := 0
	for i := 0; i < len(row); i = i + 2 {
		a, b := row[i], row[i+1]
		if b == a^1 {
			continue
		}
		res = res + 1
		for j := i + 1; j < len(row); j++ {
			if row[j] == a^1 {
				row[j], row[i+1] = row[i+1], row[j]
				break
			}
		}
	}
	return res
}

768.最多能完成排序的块II(4)¶

题目

这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。
arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。
之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
示例1:输入: arr = [5,4,3,2,1] 输出: 1
解释: 将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。 
示例 2:输入: arr = [2,1,3,4,4] 输出: 4
解释: 我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。 
注意: arr的长度在[1, 2000]之间。
arr[i]的大小在[0, 10**8]之间。

解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(nlog(n))	O(n)
02	排序	O(nlog(n))	O(n)
03	排序	O(nlog(n))	O(n)
04	单调栈	O(n)	O(n)

func maxChunksToSorted(arr []int) int {
	res := 0
	n := len(arr)
	target := make([]int, n)
	copy(target, arr)
	sort.Ints(target)
	m := make(map[int]int)
	count := 0
	for i := 0; i < n; i++ {
		m[arr[i]]++
		if m[arr[i]] == 0 {
			count--
		} else if m[arr[i]] == 1 {
			count++
		}
		m[target[i]]--
		if m[target[i]] == 0 {
			count--
		} else if m[target[i]] == -1 {
			count++
		}
		if count == 0 {
			res++
		}
	}
	return res
}

# 2
func maxChunksToSorted(arr []int) int {
	res := 0
	n := len(arr)
	target := make([]int, n)
	copy(target, arr)
	sort.Ints(target)
	diff := 0 // 不同
	for i := 0; i < n; i++ {
		diff = diff + arr[i] - target[i]
		if diff == 0 { // 累计次数抵消后为0，次数+1
			res++
		}
	}
	return res
}

# 3
func maxChunksToSorted(arr []int) int {
	res := 0
	n := len(arr)
	m := make(map[int]int)
	temp := make([][2]int, n)
	for i := 0; i < n; i++ {
		m[arr[i]]++
		temp[i] = [2]int{arr[i], m[arr[i]]}
	}
	target := make([][2]int, n)
	copy(target, temp)
	sort.Slice(target, func(i, j int) bool {
		if target[i][0] == target[j][0] {
			return target[i][1] < target[j][1]
		}
		return target[i][0] < target[j][0]
	})
	cur := temp[0]
	for i := 0; i < n; i++ {
		if compare(cur, temp[i]) == true { // 小于temp[i]更新
			cur = temp[i]
		}
		if cur == target[i] {
			res++
		}
	}
	return res
}

func compare(a, b [2]int) bool {
	if a[0] == b[0] {
		return a[1] < b[1]
	}
	return a[0] < b[0]
}

# 4
func maxChunksToSorted(arr []int) int {
	stack := make([]int, 0) // 递增栈
	for i := 0; i < len(arr); i++ {
		if len(stack) > 0 && arr[i] < stack[len(stack)-1] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			for len(stack) > 0 && arr[i] < stack[len(stack)-1] {
				stack = stack[:len(stack)-1]
			}
			stack = append(stack, top)
		} else {
			stack = append(stack, arr[i])
		}
	}
	return len(stack)
}

773.滑动谜题¶

题目¶

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用0来表示.
一次移动定义为选择0与一个相邻的数字（上下左右）进行交换.
最终当板board的结果是[[1,2,3],[4,5,0]]谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：输入：board = [[1,2,3],[4,0,5]] 输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]] 输出：-1
解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]] 输出：5
解释：最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入：board = [[3,2,4],[1,5,0]] 输出：14
提示：board是一个如上所述的 2 x 3 的数组.
board[i][j]是一个[0, 1, 2, 3, 4, 5]的排列.

解题思路¶

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

778.水位上升的泳池中游泳(4)¶

题目

在一个 N x N 的坐标方格grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为t时，此时雨水导致水池中任意位置的水位为t。
你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。
假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。
当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台(N-1, N-1)？
示例 1:输入: [[0,2],[1,3]] 输出: 3
解释:时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，
所以你可以游向坐标方格中的任意位置
示例2:输入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] 输出: 16
解释:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6
最终的路线用加粗进行了标记。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
提示:2 <= N <= 50.
grid[i][j] 是 [0, ..., N*N - 1] 的排列。

解题思路

No.	思路	时间复杂度	空间复杂度
01	堆	O(n^2log(n))	O(n^2)
02	二分查找+广度优先搜索+内置函数	O(n^2log(n))	O(n^2)
03	二分查找+广度优先搜索	O(n^2log(n))	O(n^2)
04	并查集	O(n^2log(n))	O(n^2)

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

func swimInWater(grid [][]int) int {
	n := len(grid)
	visited := make([][]bool, n)
	for i := 0; i < n; i++ {
		visited[i] = make([]bool, n)
	}
	visited[0][0] = true
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	heap.Push(&intHeap, [3]int{0, 0, grid[0][0]})
	res := 0
	for {
		node := heap.Pop(&intHeap).([3]int)
		a, b, c := node[0], node[1], node[2]
		res = max(res, c) // 更新时间
		// 经过时间t以后，可以瞬间从坐标[0,0]到坐标[N-1, N-1]。
		if a == n-1 && b == n-1 {
			return res
		}
		for i := 0; i < 4; i++ {
			x, y := a+dx[i], b+dy[i]
			if 0 <= x && x < n && 0 <= y && y < n && visited[x][y] == false {
				visited[x][y] = true
				heap.Push(&intHeap, [3]int{x, y, grid[x][y]})
			}
		}
	}
	return res
}

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

type IntHeap [][3]int

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

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

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

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

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

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

func swimInWater(grid [][]int) int {
	n := len(grid)
	return sort.Search(n*n-1, func(target int) bool {
		if target < grid[0][0] {
			return false
		}
		queue := make([][2]int, 0)
		queue = append(queue, [2]int{0, 0})
		visited := make([][]bool, n)
		for i := 0; i < n; i++ {
			visited[i] = make([]bool, n)
		}
		for len(queue) > 0 {
			a, b := queue[0][0], queue[0][1]
			queue = queue[1:]
			if a == n-1 && b == n-1 {
				return true
			}
			for i := 0; i < 4; i++ {
				x, y := a+dx[i], b+dy[i]
				if 0 <= x && x < n && 0 <= y && y < n &&
					visited[x][y] == false && grid[x][y] <= target {
					queue = append(queue, [2]int{x, y})
					visited[x][y] = true
				}
			}
		}
		return false
	})
	return 0
}

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

func swimInWater(grid [][]int) int {
	n := len(grid)
	left, right := 0, n*n-1
	res := 0
	for left <= right {
		mid := left + (right-left)/2 // 二分枚举最大值
		if mid < grid[0][0] {
			left = mid + 1
			continue
		}
		queue := make([][2]int, 0)
		queue = append(queue, [2]int{0, 0})
		visited := make([][]bool, n)
		for i := 0; i < n; i++ {
			visited[i] = make([]bool, n)
		}
		for len(queue) > 0 {
			a, b := queue[0][0], queue[0][1]
			queue = queue[1:]
			for i := 0; i < 4; i++ {
				x, y := a+dx[i], b+dy[i]
				if 0 <= x && x < n && 0 <= y && y < n &&
					visited[x][y] == false && grid[x][y] <= mid {
					queue = append(queue, [2]int{x, y})
					visited[x][y] = true
				}
			}
		}
		if visited[n-1][n-1] == true { // 缩小范围
			res = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return res
}

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

func swimInWater(grid [][]int) int {
	n := len(grid)
	arr := make([][2]int, n*n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			arr[grid[i][j]] = [2]int{i, j} // 高度对应的位置
		}
	}
	fa = Init(n * n)
	for i := 0; i < len(arr); i++ {
		a, b := arr[i][0], arr[i][1]
		for j := 0; j < 4; j++ {
			x, y := a+dx[j], b+dy[j]
			if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] <= i {
				union(x*n+y, a*n+b)
			}
		}
		if query(0, n*n-1) {
			return i
		}
	}
	return 0
}

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

780.到达终点(2)¶

题目

从点(x, y)可以转换到(x, x+y) 或者(x+y, y)。
给定一个起点(sx, sy)和一个终点(tx, ty)，如果通过一系列的转换可以从起点到达终点，则返回 True，否则返回False。
示例:输入: sx = 1, sy = 1, tx = 3, ty = 5 输出: True
解释:可以通过以下一系列转换从起点转换到终点：
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)
输入: sx = 1, sy = 1, tx = 2, ty = 2 输出: False
输入: sx = 1, sy = 1, tx = 1, ty = 1 输出: True
注意:sx, sy, tx, ty是范围在[1, 10^9]的整数。

解题思路

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

func reachingPoints(sx int, sy int, tx int, ty int) bool {
	for tx >= sx && ty >= sy {
		if tx == ty {
			break
		}
		if tx > ty {
			// (tx,ty) => (tx-ty,ty)
			if ty > sy {
				tx = tx % ty
			} else {
				return (tx-sx)%sy == 0
			}
		} else {
			if tx > sx {
				ty = ty % tx
			} else {
				return (ty-sy)%sx == 0
			}
		}
	}
	return tx == sx && ty == sy
}

# 2
func reachingPoints(sx int, sy int, tx int, ty int) bool {
	for tx > sx && ty > sy {
		if tx > ty {
			tx = tx % ty
		} else {
			ty = ty % tx
		}
	}
	if tx == sx { // (x,y) => (x, kx+y)
		return ty >= sy && (ty-sy)%sx == 0
	}
	if ty == sy { // (x,y) => (x+ky,y)
		return tx >= sx && (tx-sx)%sy == 0
	}
	return false
}

786.第K个最小的素数分数(3)¶

题目

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
那么第k个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里answer[0] == arr[i]且answer[1] == arr[j] 。
示例 1：输入：arr = [1,2,3,5], k = 3 输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5
示例 2：输入：arr = [1,7], k = 1 输出：[1,7]
提示：2 <= arr.length <= 1000
1 <= arr[i] <= 3 * 104
arr[0] == 1
arr[i] 是一个 素数 ，i > 0
arr 中的所有数字 互不相同 ，且按 严格递增 排序
1 <= k <= arr.length * (arr.length - 1) / 2

解题思路

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

func kthSmallestPrimeFraction(arr []int, k int) []int {
	n := len(arr)
	nums := make([][]int, 0)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			nums = append(nums, []int{arr[i], arr[j]})
		}
	}
	sort.Slice(nums, func(i, j int) bool {
		// a/b c/d => ad<bc
		a, b, c, d := nums[i][0], nums[i][1], nums[j][0], nums[j][1]
		return a*d < b*c
	})
	return nums[k-1]
}

# 2
func kthSmallestPrimeFraction(arr []int, k int) []int {
	n := len(arr)
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for j := 1; j < n; j++ {
		heap.Push(&intHeap, []int{arr[0], arr[j], 0, j}) // 0/j 递减：分子最小，分母依次增大
	}
	for i := 1; i <= k-1; i++ { // 取k-1个数(k从1开始)
		node := heap.Pop(&intHeap).([]int)
		x, y := node[2], node[3]
		if x+1 < y { // 下标 x+1 < y
			heap.Push(&intHeap, []int{arr[x+1], arr[y], x + 1, y})
		}
	}
	return []int{intHeap[0][0], intHeap[0][1]}
}

type IntHeap [][]int

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

# 3
func kthSmallestPrimeFraction(arr []int, k int) []int {
	n := len(arr)
	left, right := 0.0, 1.0
	for {
		mid := left + (right-left)/2
		count := 0
		x, y := 0, 1 // 记录最大的分子/分母
		i := -1
		for j := 1; j < n; j++ {
			for float64(arr[i+1])/float64(arr[j]) < mid { // 小于目标
				i++
				if arr[i]*y > arr[j]*x { // 更新：a/b > c/d => a*d > bc 保存a,b
					x, y = arr[i], arr[j]
				}
			}
			count = count + (i + 1) // 除以当前arr[j],总计几个数小于mid
		}
		if count == k {
			return []int{x, y}
		} else if count < k {
			left = mid
		} else {
			right = mid
		}
	}
}

793.阶乘函数后K个零(1)¶

题目

f(x)是x!末尾是 0 的数量。（回想一下x! = 1 * 2 * 3 * ... * x，且 0! = 1 ）
例如，f(3) = 0，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2，因为 11!= 39916800 末端有 2 个 0 。
给定K，找出多少个非负整数 x，能满足 f(x) = K 。
示例 1：输入：K = 0 输出：5
解释：0!, 1!, 2!, 3!, and 4!均符合 K = 0 的条件。
示例 2：输入：K = 5 输出：0
解释：没有匹配到这样的 x!，符合 K = 5 的条件。
提示：K 是范围在[0, 10^9]的整数。

解题思路

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

func preimageSizeFZF(k int) int {
	left, right := 0, 5*k+1
	for left < right {
		mid := left + (right-left)/2
		target := trailingZeroes(mid)
		if target == k {
			return 5 // 能找到一定会存在连续5个数的阶乘末尾0的个数为k
		} else if target < k {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return 0 // 不存在返回0
}

// leetcode 172.阶乘后的零
// n!末尾0的个数
func trailingZeroes(n int) int {
	result := 0
	for n >= 5 {
		n = n / 5
		result = result + n
	}
	return result
}