0001-0100-Easy

1.两数之和(3)

• 题目

给定一个整数数组 nums 和一个目标值 target，
请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

• 解答思路

No.	思路	时间复杂度	空间复杂度
01	暴力法: 2层循环遍历	O(n^2)	O(1)
02	两遍哈希遍历	O(n)	O(n)
03(最优)	一遍哈希遍历	O(n)	O(n)

# 暴力法: 2层循环遍历
func twoSum(nums []int, target int) []int {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}
	return []int{}
}

# 两遍哈希遍历
func twoSum(nums []int, target int) []int {
	m := make(map[int]int,len(nums))
	for k, v := range nums{
		m[v] = k
	}

	for i := 0; i < len(nums); i++{
		b := target - nums[i]
		if num, ok := m[b]; ok && num != i{
			return []int{i,m[b]}
		}
	}
	return []int{}
}

# 一遍哈希遍历
func twoSum(nums []int, target int) []int {
	m := make(map[int]int, len(nums))
	for i, b := range nums {
		if j, ok := m[target-b]; ok {
			return []int{j, i}
		}
		m[b] = i
	}
	return nil
}

7.整数反转(2)

• 题目

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:输入: 123 输出: 321
示例 2:输入: -123 输出: -321
示例 3:输入: 120 输出: 21
注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31,  2^31 − 1]。
请根据这个假设，如果反转后整数溢出那么就返回 0。

• 解答思路

No.	思路	时间复杂度	空间复杂度
01	使用符号标记，转成正数，循环得到%10的余数，再加上符号	O(log(x))	O(1)
02(最优)	对x进行逐个%10取个位，一旦溢出，直接跳出循环	O(log(x))	O(1)

// 使用符号标记，转成正数，循环得到%10的余数，再加上符号
func reverse(x int) int {
	flag := 1
	if x < 0 {
		flag = -1
		x = -1 * x
	}

	result := 0
	for x > 0 {
		temp := x % 10
		x = x / 10

		result = result*10 + temp
	}

	result = flag * result
	if result > math.MaxInt32 || result < math.MinInt32 {
		result = 0
	}
	return result
}

// 对x进行逐个%10取个位，一旦溢出，直接跳出循环
func reverse(x int) int {
	result := 0
	for x != 0 {
		temp := x % 10
		result = result*10 + temp
		if result > math.MaxInt32 || result < math.MinInt32 {
			return 0
		}
		x = x / 10
	}
	return result
}

9.回文数(3)

• 题目

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:	输入: 121	输出: true
示例 2:输入: -121	输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:输入: 10  	输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶: 你能不将整数转为字符串来解决这个问题吗？

• 解答思路

No.	思路	时间复杂度	空间复杂度
01(最优)	数学解法，取出后半段数字进行翻转，然后判断是否相等	O(log(x))	O(1)
02	转成字符串，依次判断	O(log(x))	O(log(x))
03	转成byte数组，依次判断，同2	O(log(x))	O(log(x))

// 数学解法，取出后半段数字进行翻转，然后判断是否相等
func isPalindrome(x int) bool {
	if x < 0 || (x%10 == 0 && x != 0) {
		return false
	}

	revertedNumber := 0
	for x > revertedNumber {
		temp := x % 10
		revertedNumber = revertedNumber*10 + temp
		x = x / 10
	}
	// for example:
	// x = 1221  => x = 12 revertedNumber = 12
	// x = 12321 => x = 12 revertedNumber = 123
	return x == revertedNumber || x == revertedNumber/10
}

// 转成字符串，依次判断
func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}

	s := strconv.Itoa(x)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}

// 转成byte数组，依次判断，同2
func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}
	arrs := []byte(strconv.Itoa(x))
	Len := len(arrs)
	for i := 0; i < Len/2; i++ {
		if arrs[i] != arrs[Len-i-1] {
			return false
		}
	}
	return true
}

13.罗马数字转整数(2)

• 题目

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 
27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。
但也存在特例，例如 4 不写做 IIII，而是 IV。
数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
    I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
    X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
    C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:输入: "III" 输出: 3
示例 2:	输入: "IV" 输出: 4
示例 3:	输入: "IX"	输出: 9
示例 4:	输入: "LVIII"	输出: 58 解释: L = 50, V= 5, III = 3.
示例 5: 输入: "MCMXCIV"	输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.

• 解答思路

No.	思路	时间复杂度	空间复杂度
01	本质上其实就是全部累加，然后遇到特殊的就做判断。使用一个字段记录递增	O(n)	O(1)
02(最优)	从右到左遍历字符串，如果当前字符代表的值不小于其右边，就加上该值；否则就减去该值。	O(n)	O(1)

// 带标记位
func romanToInt(s string) int {
	m := map[byte]int{
		'I': 1,
		'V': 5,
		'X': 10,
		'L': 50,
		'C': 100,
		'D': 500,
		'M': 1000,
	}
	result := 0
	last := 0

	for i := len(s) - 1; i >= 0; i-- {
		current := m[s[i]]
		flag := 1
		if current < last {
			flag = -1
		}
		result = result + flag*current
		last = current
	}
	return result
}

// 不带标记位，小于则减去2倍数
func romanToInt(s string) int {
	m := map[byte]int{
		'I': 1,
		'V': 5,
		'X': 10,
		'L': 50,
		'C': 100,
		'D': 500,
		'M': 1000,
	}
	result := 0
	last := 0

	for i := len(s) - 1; i >= 0; i-- {
		current := m[s[i]]
		if current < last {
			result = result - current
		}else {
			result = result + current
		}
		last = current
	}
	return result
}

14.最长公共前缀(6)

• 题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:输入: ["flower","flow","flight"] 输出: "fl"
示例 2:输入: ["dog","racecar","car"] 输出: ""
解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z 。

• 解答思路

No.	思路	时间复杂度	空间复杂度
01	先找最短的一个字符串，依次比较最短字符串子串是否是其他字符串子串	O(n^2)/O(n*m)	O(1)
02	纵向扫描(暴力法):直接取第一个字符串作为最长公共前缀，将其每个字符遍历过一次	O(n^2)/O(n*m)	O(1)
03(最优)	排序后，然后计算第一个，和最后一个字符串的最长前缀	O(nlog(n))	O(1)
04	trie树	O(n^2)	O(n^2)
05	水平扫描法:比较前2个字符串得到最长前缀，然后跟第3个比较得到一个新的最长前缀，继续比较，直到最后	O(n^2)/O(n*m)	O(1)
06	分治法	O(n^2)	O(1)

// 先找最短的一个字符串，依次比较最短字符串子串是否是其他字符串子串
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0{
		return ""
	}
	if len(strs) == 1{
		return strs[0]
	}

	short := strs[0]
	for _, s := range strs{
		if len(short) > len(s){
			short = s
		}
	}

	for i := range short{
		shortest := short[:i+1]
		for _,str := range strs{
			if strings.Index(str,shortest) != 0{
				return short[:i]
			}
		}
	}
	return short
}

// 暴力法:直接依次遍历
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	if len(strs) == 1 {
		return strs[0]
	}

	length := 0

	for i := 0; i < len(strs[0]); i++ {
		char := strs[0][i]
		for j := 1; j < len(strs); j++ {
			if i >= len(strs[j]) || char != strs[j][i] {
				return strs[0][:length]
			}
		}
		length++
	}
	return strs[0][:length]
}

// 排序后，遍历比较第一个，和最后一个字符串
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0{
		return ""
	}
	if len(strs) == 1{
		return strs[0]
	}

	sort.Strings(strs)
	first := strs[0]
	last := strs[len(strs)-1]
	i := 0
	length := len(first)
	if len(last) < length{
		length = len(last)
	}
	for i < length{
		if first[i] != last[i]{
			return first[:i]
		}
		i++
	}

	return first[:i]
}

// trie树
var trie [][]int
var index int

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	if len(strs) == 1 {
		return strs[0]
	}

	trie = make([][]int, 2000)
	for k := range trie {
		value := make([]int, 26)
		trie[k] = value
	}
	insert(strs[0])

	minValue := math.MaxInt32
	for i := 1; i < len(strs); i++ {
		retValue := insert(strs[i])
		if minValue > retValue {
			minValue = retValue
		}
	}
	return strs[0][:minValue]
}

func insert(str string) int {
	p := 0
	count := 0
	for i := 0; i < len(str); i++ {
		ch := str[i] - 'a'
		// fmt.Println(string(str[i]),p,ch,trie[p][ch])
		if value := trie[p][ch]; value == 0 {
			index++
			trie[p][ch] = index
		} else {
			count++
		}
		p = trie[p][ch]
	}
	return count
}

// 水平扫描法:比较前2个字符串得到最长前缀，然后跟第3个比较得到一个新的最长前缀，继续比较，直到最后
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	if len(strs) == 1 {
		return strs[0]
	}

	commonStr := common(strs[0], strs[1])
	if commonStr == "" {
		return ""
	}
	for i := 2; i < len(strs); i++ {
		if commonStr == "" {
			return ""
		}
		commonStr = common(commonStr, strs[i])
	}
	return commonStr
}

func common(str1, str2 string) string {
	length := 0
	for i := 0; i < len(str1); i++ {
		char := str1[i]
		if i >= len(str2) || char != str2[i] {
			return str1[:length]
		}
		length++
	}
	return str1[:length]
}

// 分治法
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	if len(strs) == 1 {
		return strs[0]
	}

	return commonPrefix(strs, 0, len(strs)-1)
}

func commonPrefix(strs []string, left, right int) string {
	if left == right {
		return strs[left]
	}

	middle := (left + right) / 2
	leftStr := commonPrefix(strs, left, middle)
	rightStr := commonPrefix(strs, middle+1, right)
	return commonPrefixWord(leftStr, rightStr)
}

func commonPrefixWord(leftStr, rightStr string) string {
	if len(leftStr) > len(rightStr) {
		leftStr = leftStr[:len(rightStr)]
	}

	if len(leftStr) < 1 {
		return leftStr
	}

	for i := 0; i < len(leftStr); i++ {
		if leftStr[i] != rightStr[i] {
			return leftStr[:i]
		}
	}
	return leftStr
}

20.有效的括号(3)

• 题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1: 输入: "()" 输出: true
示例 2: 输入: "()[]{}" 输出: true
示例 3: 输入: "(]" 输出: false
示例 4: 输入: "([)]" 输出: false
示例 5: 输入: "{[]}" 输出: true

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	使用栈结构实现栈	O(n)	O(n)
02	借助数组实现栈	O(n)	O(n)
03	借助数组实现栈，使用数字表示来匹配	O(n)	O(n)

// 使用栈结构实现
func isValid(s string) bool {
	st := new(stack)
	for _, char := range s {
		switch char {
		case '(', '[', '{':
			st.push(char)
		case ')', ']', '}':
			ret, ok := st.pop()
			if !ok || ret != match[char] {
				return false
			}
		}
	}

	if len(*st) > 0 {
		return false
	}
	return true
}

var match = map[rune]rune{
	')': '(',
	']': '[',
	'}': '{',
}

type stack []rune

func (s *stack) push(b rune) {
	*s = append(*s, b)
}
func (s *stack) pop() (rune, bool) {
	if len(*s) > 0 {
		res := (*s)[len(*s)-1]
		*s = (*s)[:len(*s)-1]
		return res, true
	}
	return 0, false
}

// 借助数组实现栈
func isValid(s string) bool {
	if s == "" {
		return true
	}

	stack := make([]rune, len(s))
	length := 0
	var match = map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
	}

	for _, char := range s {
		switch char {
		case '(', '[', '{':
			stack[length] = char
			length++
		case ')', ']', '}':
			if length == 0 {
				return false
			}
			if stack[length-1] != match[char]{
				return false
			} else {
				length--
			}
		}
	}
	return length == 0
}

// 借助数组实现栈，使用数字表示来匹配
func isValid(s string) bool {
	if s == "" {
		return true
	}

	stack := make([]int, len(s))
	length := 0
	var match = map[rune]int{
		')': 1,
		'(': -1,
		']': 2,
		'[': -2,
		'}': 3,
		'{': -3,
	}

	for _, char := range s {
		switch char {
		case '(', '[', '{':
			stack[length] = match[char]
			length++
		case ')', ']', '}':
			if length == 0 {
				return false
			}
			if stack[length-1]+match[char] != 0 {
				return false
			} else {
				length--
			}
		}
	}
	return length == 0
}

21.合并两个有序链表(3)

• 题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

• 解题思路

No.	思路	时间复杂度	空间复杂度
01(最优)	迭代遍历	O(n)	O(1)
02	递归实现	O(n)	O(n)
03	迭代	O(n)	O(1)

// 迭代遍历
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}

	var head, node *ListNode
	if l1.Val < l2.Val {
		head = l1
		node = l1
		l1 = l1.Next
	} else {
		head = l2
		node = l2
		l2 = l2.Next
	}

	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			node.Next = l1
			l1 = l1.Next
		} else {
			node.Next = l2
			l2 = l2.Next
		}
		node = node.Next
	}
	if l1 != nil {
		node.Next = l1
	}
	if l2 != nil {
		node.Next = l2
	}
	return head
}

// 递归遍历
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}

	if l1.Val < l2.Val{
		l1.Next = mergeTwoLists(l1.Next,l2)
		return l1
	}else {
		l2.Next = mergeTwoLists(l1,l2.Next)
		return l2
	}
}

#
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	res := &ListNode{}
	temp := res
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			temp.Next = l1
			l1 = l1.Next
		} else {
			temp.Next = l2
			l2 = l2.Next
		}
		temp = temp.Next
	}
	if l1 != nil {
		temp.Next = l1
	} else {
		temp.Next = l2
	}
	return res.Next
}

26.删除排序数组中的重复项(2)

• 题目

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针法	O(n)	O(1)
02(最优)	计数法	O(n)	O(1)

// 双指针法
func removeDuplicates(nums []int) int {
	i , j , length := 0, 1, len(nums)
	for ; j < length; j++{
		if nums[i] == nums[j]{
			continue
		}
		i++
		nums[i] = nums[j]
	}
	return i+1
}

// 计数法
func removeDuplicates(nums []int) int {
	count := 1
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] != nums[i+1] {
			nums[count] = nums[i+1]
			count++
		}
	}
	return count
}

27.移除元素(3)

• 题目

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

• 解题思路

No.	思路	时间复杂度	空间复杂度
01(最优)	双指针，数字前移	O(n)	O(1)
02	双指针，出现重复最后数字前移	O(n)	O(1)
03	首位指针法	O(n)	O(1)

// 双指针，数字前移
func removeElement(nums []int, val int) int {
	i := 0
	for j := 0; j < len(nums); j++{
		if nums[j] != val{
			nums[i] = nums[j]
			i++
		}
	}
	return i
}

// 双指针，出现重复最后数字前移
func removeElement(nums []int, val int) int {
	i := 0
	n := len(nums)
	for i < n{
		if nums[i] == val{
			nums[i] = nums[n-1]
			n--
		}else {
			i++
		}
	}
	return n
}

// 首位指针法
func removeElement(nums []int, val int) int {
	i, j := 0, len(nums)-1
	for {
		// 从左向右找到等于 val 的位置
		for i < len(nums) && nums[i] != val {
			i++
		}
		// 从右向左找到不等于 val 的位置
		for j >= 0 && nums[j] == val {
			j--
		}
		if i >= j {
			break
		}
		// fmt.Println(i,j)
		nums[i], nums[j] = nums[j], nums[i]
	}
	return i
}

28.实现strStr()(4)

• 题目

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，
在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。
如果不存在，则返回-1。
示例 1:输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。
这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01(最优)	Sunday算法	O(n)	O(1)
02	直接匹配	O(n)	O(1)
03	系统函数	O(n)	O(1)
04	kmp算法	O(n)	O(n)

// Sunday算法
func strStr(haystack string, needle string) int {
	if needle == ""{
		return 0
	}
	if len(needle) > len(haystack){
		return -1
	}
	// 计算模式串needle的偏移量
	m := make(map[int32]int)
	for k,v := range needle{
		m[v] = len(needle)-k
	}

	index := 0
	for index+len(needle) <= len(haystack){
		// 匹配字符串
		str := haystack[index:index+len(needle)]
		if str == needle{
			return index
		}else {
			if index + len(needle) >= len(haystack){
				return -1
			}
			// 后一位字符串
			next := haystack[index+len(needle)]
			if nextStep,ok := m[int32(next)];ok{
				index = index+nextStep
			}else {
				index = index+len(needle)+1
			}
		}
	}
	if index + len(needle) >= len(haystack){
		return -1
	}else {
		return index
	}
}

// 
func strStr(haystack string, needle string) int {
	hlen, nlen := len(haystack), len(needle)
	for i := 0; i <= hlen-nlen; i++ {
		if haystack[i:i+nlen] == needle {
			return i
		}
	}
	return -1
}

//
func strStr(haystack string, needle string) int {
	return strings.Index(haystack, needle)
}

//
func strStr(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}

	next := getNext(needle)

	i := 0
	j := 0
	for i < len(haystack) && j < len(needle) {
		if j == -1 || haystack[i] == needle[j] {
			i++
			j++
		} else {
			j = next[j]
		}
	}

	if j == len(needle) {
		return i - j
	}
	return -1
}

// 求next数组
func getNext(str string) []int {
	var next = make([]int, len(str))
	next[0] = -1

	i := 0
	j := -1

	for i < len(str)-1 {
		if j == -1 || str[i] == str[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}
	return next
}

35.搜索插入位置(3)

• 题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
示例 4: 输入: [1,3,5,6], 0 输出: 0

• 解题思路

No.	思路	时间复杂度	空间复杂度
01(最优)	二分查找	O(log(n))	O(1)
02	顺序查找	O(n)	O(1)
03	顺序查找	O(n)	O(1)

// 二分查找
func searchInsert(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := (low + high) / 2
		switch {
		case nums[mid] < target:
			low = mid + 1
		case nums[mid] > target:
			high = mid - 1
		default:
			return mid
		}
	}
	return low
}

// 顺序查找
func searchInsert(nums []int, target int) int {
	i := 0
	for i < len(nums) && nums[i] < target {
		if nums[i] == target {
			return i
		}
		i++
	}
	return i
}

// 顺序查找
func searchInsert(nums []int, target int) int {
	for i := 0; i < len(nums); i++ {
		if nums[i] >= target {
			return i
		}
	}
	return len(nums)
}

38.报数(2)

• 题目

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1.     1
2.     11
3.     21
4.     1211
5.     111221
1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例 1:输入: 1 输出: "1"
示例 2: 输入: 4 输出: "1211"

• 解题思路

No.	思路	时间复杂度	空间复杂度
01 (最优)	递推+双指针计数	O(n^2)	O(1)
02	递归+双指针计数	O(n^2)	O(n)

// 递推+双指针计数
func countAndSay(n int) string {
	strs := []byte{'1'}
	for i := 1; i < n; i++ {
		strs = say(strs)
	}
	return string(strs)
}

func say(strs []byte) []byte {
	result := make([]byte, 0, len(strs)*2)

	i, j := 0, 1
	for i < len(strs) {
		for j < len(strs) && strs[i] == strs[j] {
			j++
		}
		// 几个几
		result = append(result, byte(j-i+'0'))
		result = append(result, strs[i])
		i = j
	}
	return result
}

// 递归+双指针计数
func countAndSay(n int) string {
	if n == 1 {
		return "1"
	}
	strs := countAndSay(n - 1)

	result := make([]byte, 0, len(strs)*2)

	i, j := 0, 1
	for i < len(strs) {
		for j < len(strs) && strs[i] == strs[j] {
			j++
		}
		// 几个几
		result = append(result, byte(j-i+'0'))
		result = append(result, strs[i])
		i = j
	}
	return string(result)
}

53.最大子序和(5)

• 题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01(最优)	贪心法	O(n)	O(1)
02	暴力法	O(n^2)	O(1)
03	动态规划	O(n)	O(n)
04	动态规划	O(n)	O(1)
05	分治	O(nlog(n))	O(log(n))

// 贪心法
func maxSubArray(nums []int) int {
	result := nums[0]
	sum := 0
	for i := 0; i < len(nums); i++ {
		if sum > 0 {
			sum += nums[i]
		} else {
			sum = nums[i]
		}
		if sum > result {
			result = sum
		}
	}
	return result
}

// 暴力法
func maxSubArray(nums []int) int {
	result := math.MinInt32

	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum > result {
				result = sum
			}
		}
	}
	return result
}

// 
func maxSubArray(nums []int) int {
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	result := nums[0]

	for i := 1; i < len(nums); i++ {
		if dp[i-1]+nums[i] > nums[i] {
			dp[i] = dp[i-1] + nums[i]
		} else {
			dp[i] = nums[i]
		}

		if dp[i] > result {
			result = dp[i]
		}
	}
	return result
}

// 动态规划
func maxSubArray(nums []int) int {
	dp := nums[0]
	result := dp

	for i := 1; i < len(nums); i++ {
		if dp+nums[i] > nums[i] {
			dp = dp + nums[i]
		} else {
			dp = nums[i]
		}

		if dp > result {
			result = dp
		}
	}
	return result
}

// 分治法
func maxSubArray(nums []int) int {
	result := maxSubArr(nums, 0, len(nums)-1)
	return result
}

func maxSubArr(nums []int, left, right int) int {
	if left == right {
		return nums[left]
	}

	mid := (left + right) / 2
	leftSum := maxSubArr(nums, left, mid)        // 最大子序在左边
	rightSum := maxSubArr(nums, mid+1, right)    // 最大子序在右边
	midSum := findMaxArr(nums, left, mid, right) // 跨中心
	result := max(leftSum, rightSum)
	result = max(result, midSum)
	return result
}

func findMaxArr(nums []int, left, mid, right int) int {
	leftSum := math.MinInt32
	sum := 0
	// 从右到左
	for i := mid; i >= left; i-- {
		sum += nums[i]
		leftSum = max(leftSum, sum)
	}

	rightSum := math.MinInt32
	sum = 0
	// 从左到右
	for i := mid + 1; i <= right; i++ {
		sum += nums[i]
		rightSum = max(rightSum, sum)
	}
	return leftSum + rightSum
}

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

58.最后一个单词的长度(2)

• 题目

给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例: 输入: "Hello World" 输出: 5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01(最优)	调用系统函数，切割为数组取最后一个值	O(n)	O(1)
02	遍历统计	O(n)	O(1)

// 调用系统函数，切割为数组取最后一个值
func lengthOfLastWord(s string) int {
	arr := strings.Split(strings.Trim(s, " "), " ")
	return len(arr[len(arr)-1])
}

// 遍历统计
func lengthOfLastWord(s string) int {
	length := len(s)
	if length == 0 {
		return 0
	}

	result := 0
	for i := length - 1; i >= 0; i-- {
		if s[i] == ' ' {
			if result > 0 {
				return result
			}
			continue
		}
		result++
	}
	return result
}

66.加一(2)

• 题目

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。
示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	直接模拟	O(n)	O(1)
02(最优)	直接模拟	O(n)	O(1)

// 模拟进位
func plusOne(digits []int) []int {
	length := len(digits)
	if length == 0 {
		return []int{1}
	}

	digits[length-1]++
	for i := length - 1; i > 0; i-- {
		if digits[i] < 10 {
			break
		}
		digits[i] = digits[i] - 10
		digits[i-1]++
	}

	if digits[0] > 9 {
		digits[0] = digits[0] - 10
		digits = append([]int{1}, digits...)
	}

	return digits
}

// 模拟进位
func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] < 9 {
			digits[i]++
			return digits
		} else {
			digits[i] = 0
		}
	}
	return append([]int{1}, digits...)
}

67.二进制求和(2)

• 题目

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1: 输入: a = "11", b = "1" 输出: "100"
示例 2:输入: a = "1010", b = "1011" 输出: "10101"

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数组	O(n)	O(n)
02(最优)	模拟	O(n)	O(n)

// 转换成数组模拟
func addBinary(a string, b string) string {
	if len(a) < len(b) {
		a, b = b, a
	}
	length := len(a)

	A := transToInt(a, length)
	B := transToInt(b, length)

	return makeString(add(A, B))
}

func transToInt(s string, length int) []int {
	result := make([]int, length)
	ls := len(s)
	for i, b := range s {
		result[length-ls+i] = int(b - '0')
	}
	return result
}

func add(a, b []int) []int {
	length := len(a) + 1
	result := make([]int, length)
	for i := length - 1; i >= 1; i-- {
		temp := result[i] + a[i-1] + b[i-1]
		result[i] = temp % 2
		result[i-1] = temp / 2
	}
	i := 0
	for i < length-1 && result[i] == 0 {
		i++
	}
	return result[i:]
}

func makeString(nums []int) string {
	bytes := make([]byte, len(nums))
	for i := range bytes {
		bytes[i] = byte(nums[i]) + '0'
	}
	return string(bytes)
}

// 直接模拟
func addBinary(a string, b string) string {
	i := len(a) - 1
	j := len(b) - 1
	result := ""
	flag := 0
	current := 0

	for i >= 0 || j >= 0 {
		intA, intB := 0, 0
		if i >= 0 {
			intA = int(a[i] - '0')
		}
		if j >= 0 {
			intB = int(b[j] - '0')
		}
		current = intA + intB + flag
		flag = 0
		if current >= 2 {
			flag = 1
			current = current - 2
		}
		cur := strconv.Itoa(current)
		result = cur + result
		i--
		j--
	}
	if flag == 1 {
		result = "1" + result
	}
	return result
}

69.x的平方根 (5)

• 题目

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:输入: 4 输出: 2
示例 2:输入: 8 输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	系统函数	O(log(n))	O(1)
02	系统函数	O(log(n))	O(1)
03(最优)	牛顿迭代法	O(log(n))	O(1)
04	二分查找法	O(log(n))	O(1)
05	暴力法:遍历	O(n)	O(1)

// 系统函数
func mySqrt(x int) int {
	result := int(math.Sqrt(float64(x)))
	return result
}

// 系统函数
func mySqrt(x int) int {
	result := math.Floor(math.Sqrt(float64(x)))
	return int(result)
}

// 牛顿迭代法
func mySqrt(x int) int {
	result := x
	for result*result > x {
		result = (result + x/result) / 2
	}
	return result
}

// 二分查找法
func mySqrt(x int) int {
	left := 1
	right := x
	for left <= right {
		mid := (left + right) / 2
		if mid == x/mid {
			return mid
		} else if mid < x/mid {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if left * left <= x{
		return left
	}else {
		return left-1
	}
}

// 暴力法:遍历
func mySqrt(x int) int {
	result := 0
	for i := 1; i <= x/i; i++ {
		if i*i == x {
			return i
		}
		result = i
	}
	return result
}

70.爬楼梯(3)

• 题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 
1.  1 阶 + 1 阶
2.  2 阶
示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(n)
02	动态规划	O(n)	O(n)
03(最优)	斐波那契	O(n)	O(1)

// 递归
var arr []int

func climbStairs(n int) int {
	arr = make([]int, n+1)
	return climbStart(0, n)
}

func climbStart(i, n int) int {
	if i > n {
		return 0
	}
	if i == n {
		return 1
	}
	if arr[i] > 0 {
		return arr[i]
	}
	arr[i] = climbStart(i+1, n) + climbStart(i+2, n)
	return arr[i]
}

// 动态规划
func climbStairs(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

// 斐波那契
func climbStairs(n int) int {
	if n == 1 {
		return 1
	}
	first := 1
	second := 2
	for i := 3; i <= n; i++ {
		third := first + second
		first = second
		second = third
	}
	return second
}

83.删除排序链表中的重复元素(3)

• 题目

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:输入: 1->1->2 输出: 1->2
示例 2:输入: 1->1->2->3->3 输出: 1->2->3

• 解题思路

No.	思路	时间复杂度	空间复杂度
01( 最优)	直接法	O(n)	O(1)
02	递归法	O(n)	O(1)
03	双指针法	O(n)	O(1)

// 直接法
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	temp := head
	for temp.Next != nil {
		if temp.Val == temp.Next.Val {
			temp.Next = temp.Next.Next
		} else {
			temp = temp.Next
		}
	}
	return head
}

// 递归法
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil{
		return head
	}
	head.Next = deleteDuplicates(head.Next)
	if head.Val == head.Next.Val{
		head = head.Next
	}
	return head
}

// 双指针法
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil{
		return head
	}
	p := head
	q := head.Next
	for p.Next != nil{
		if p.Val == q.Val{
			if q.Next == nil{
				p.Next = nil
			}else {
				p.Next = q.Next
				q = q.Next
			}
		}else {
			p = p.Next
			q = q.Next
		}
	}
	return head
}

88.合并两个有序数组(3)

• 题目

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
    初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
    你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	合并后排序	O(nlog(n))	O(1)
02(最优)	双指针法	O(n)	O(1)
03	拷贝后插入	O(n)	O(n)

// 合并后排序
func merge(nums1 []int, m int, nums2 []int, n int) {
	nums1 = nums1[:m]
	nums1 = append(nums1, nums2[:n]...)
	sort.Ints(nums1)
}

// 双指针法
func merge(nums1 []int, m int, nums2 []int, n int) {
	for m > 0 && n > 0 {
		if nums1[m-1] < nums2[n-1] {
			nums1[m+n-1] = nums2[n-1]
			n--
		} else {
			nums1[m+n-1] = nums1[m-1]
			m--
		}
	}
	if m == 0 && n > 0 {
		for n > 0 {
			nums1[n-1] = nums2[n-1]
			n--
		}
	}
}

// 拷贝后插入
func merge(nums1 []int, m int, nums2 []int, n int) {
	temp := make([]int, m)
	copy(temp, nums1)

	if n == 0 {
		return
	}
	first, second := 0, 0
	for i := 0; i < len(nums1); i++ {
		if second >= n {
			nums1[i] = temp[first]
			first++
			continue
		}
		if first >= m {
			nums1[i] = nums2[second]
			second++
			continue
		}
		if temp[first] < nums2[second] {
			nums1[i] = temp[first]
			first++
		} else {
			nums1[i] = nums2[second]
			second++
		}
	}
}

100.相同的树(2)

• 题目

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入:       1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true
示例 2:
输入:      1          1
          /           \
         2             2
        [1,2],     [1,null,2]
输出: false
示例 3:
输入:       1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
输出: false

• 解题思路

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

// 递归(深度优先)
func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}

	if p == nil || q == nil {
		return false
	}

	return p.Val == q.Val && isSameTree(p.Left, q.Left) &&
		isSameTree(p.Right, q.Right)
}

// 层序遍历(宽度优先)
func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}

	var queueP, queueQ []*TreeNode
	if p != nil {
		queueP = append(queueP, p)
		queueQ = append(queueQ, q)
	}

	for len(queueP) > 0 && len(queueQ) > 0 {
		tempP := queueP[0]
		queueP = queueP[1:]

		tempQ := queueQ[0]
		queueQ = queueQ[1:]

		if tempP.Val != tempQ.Val {
			return false
		}

		if (tempP.Left != nil && tempQ.Left == nil) ||
			(tempP.Left == nil && tempQ.Left != nil) {
			return false
		}
		if tempP.Left != nil {
			queueP = append(queueP, tempP.Left)
			queueQ = append(queueQ, tempQ.Left)
		}

		if (tempP.Right != nil && tempQ.Right == nil) ||
			(tempP.Right == nil && tempQ.Right != nil) {
			return false
		}
		if tempP.Right != nil {
			queueP = append(queueP, tempP.Right)
			queueQ = append(queueQ, tempQ.Right)
		}
	}
	return true
}

0001-0100-Medium

2.两数相加(2)

• 题目

给出两个 非空 的链表用来表示两个非负的整数。
其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8
原因：342 + 465 = 807

• 解题思路

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

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

#
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil && l2 == nil {
		return nil
	}
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	sum := l1.Val + l2.Val
	res := &ListNode{Val: sum % 10}
	if sum >= 10 {
		l1.Next = addTwoNumbers(l1.Next, &ListNode{Val: 1})
	}
	res.Next = addTwoNumbers(l1.Next, l2.Next)
	return res
}

3.无重复字符的最长子串(4)

• 题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:输入: "abcabcbb"输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:输入: "bbbbb" 输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:输入: "pwwkew" 输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
同剑指offer面试题48.最长不含重复字符的子字符串

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	双指针-内置函数	O(n^2)	O(1)
03	哈希辅助-双指针	O(n)	O(1)
04	动态规划	O(n)	O(n)
05	双指针	O(n)	O(1)

func lengthOfLongestSubstring(s string) int {
	arr := [256]int{}
	for i := range arr {
		arr[i] = -1
	}
	max, j := 0, 0
	for i := 0; i < len(s); i++ {
		if arr[s[i]] >= j {
			j = arr[s[i]] + 1
		} else if i+1-j > max {
			max = i + 1 - j
		}
		arr[s[i]] = i
	}
	return max
}

# 2
func lengthOfLongestSubstring(s string) int {
	max, j := 0, 0
	for i := 0; i < len(s); i++ {
		index := strings.Index(s[j:i], string(s[i]))
		if index == -1 {
			continue
		}
		if i-j > max {
			max = i - j
		}
		j = j + index + 1
	}
	if len(s)-j > max {
		max = len(s) - j
	}
	return max
}

# 3
func lengthOfLongestSubstring(s string) int {
	m := make(map[uint8]int)
	max, j := 0, 0
	for i := 0; i < len(s); i++ {
		if v, ok := m[s[i]]; ok && v >= j {
			j = v + 1
		} else if i+1-j > max {
			max = i + 1 - j
		}
		m[s[i]] = i
	}
	return max
}

# 4
func lengthOfLongestSubstring(s string) int {
	if len(s) < 1 {
		return 0
	}
	dp := make([]int, len(s))
	dp[0] = 1
	res := 1
	m := make(map[byte]int)
	m[s[0]] = 0
	for i := 1; i < len(s); i++ {
		index := -1
		if value, ok := m[s[i]]; ok {
			index = value
		}
		if i-index > dp[i-1] {
			dp[i] = dp[i-1] + 1
		} else {
			dp[i] = i - index
		}
		m[s[i]] = i
		if dp[i] > res {
			res = dp[i]
		}
	}
	return res
}

# 5
func lengthOfLongestSubstring(s string) int {
	arr := [256]int{}
	for i := range arr {
		arr[i] = -1
	}
	res, j := 0, -1
	for i := 0; i < len(s); i++ {
		if arr[s[i]] > j { // 出现重复了，更新下标
			j = arr[s[i]]
		} else {
			res = max(res, i-j) // 没有重复，更新长度
		}
		arr[s[i]] = i
	}
	return res
}

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

5.最长回文子串(5)

• 题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：输入: "babad"输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：输入: "cbbd" 输出: "bb"

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划	O(n^2)	O(n^2)
02	中心扩展	O(n^2)	O(1)
03	暴力法	O(n^3)	O(1)
04	Manacher算法	O(n^2)	O(n)
05	Manacher算法	O(n)	O(n)

// dp(l,r)=dp(l+1,r−1)&&(s[l]==s[r])
// dp[l,r]：字符串s从索引l到r的子串是否是回文串
func longestPalindrome(s string) string {
	if len(s) <= 1 {
		return s
	}
	dp := make([][]bool, len(s))
	start := 0
	max := 1
	for r := 0; r < len(s); r++ {
		dp[r] = make([]bool, len(s))
		dp[r][r] = true
		for l := 0; l < r; l++ {
			if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1] == true) {
				dp[l][r] = true
			} else {
				dp[l][r] = false
			}
			if dp[l][r] == true {
				if r-l+1 > max {
					max = r - l + 1
					start = l
				}
			}
		}
	}
	return s[start : start+max]
}

# 2
func longestPalindrome(s string) string {
	if len(s) <= 1 {
		return s
	}
	start := 0
	end := 0
	for i := 0; i < len(s); i++ {
		left1, right1 := find(s, i, i)
		left2, right2 := find(s, i, i+1)
		if right1-left1 > end-start {
			start, end = left1, right1
		}
		if right2-left2 > end-start {
			start, end = left2, right2
		}
	}
	return s[start : end+1]
}

func find(s string, left, right int) (int, int) {
	for ; 0 <= left && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {
	}
	return left + 1, right - 1
}

# 3
func longestPalindrome(s string) string {
	if len(s) <= 1 {
		return s
	}
	res := ""
	for i := 0; i < len(s); i++ {
		for j := i; j < len(s); j++ {
			str := s[i : j+1]
			if len(str) < len(res) && res != "" {
				continue
			}
			if judge(str) == true && len(res) < len(str) {
				res = str
			}
		}
	}
	return res
}

func judge(s string) bool {
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-1-i] {
			return false
		}
	}
	return true
}

# 4
func longestPalindrome(s string) string {
	if len(s) <= 1 {
		return s
	}
	str := add(s)
	length := len(str)
	max := 1
	begin := 0
	for i := 0; i < length; i++ {
		curLength := search(str, i)
		if curLength > max {
			max = curLength
			begin = (i - max) / 2
		}
	}
	return s[begin : begin+max]
}

func search(s string, center int) int {
	i := center - 1
	j := center + 1
	step := 0
	for ; i >= 0 && j < len(s) && s[i] == s[j]; i, j = i-1, j+1 {
		step++
	}
	return step
}

func add(s string) string {
	var res []rune
	for _, v := range s {
		res = append(res, '#')
		res = append(res, v)
	}
	res = append(res, '#')
	return string(res)
}

#
func longestPalindrome(s string) string {
	if len(s) <= 1 {
		return s
	}
	str := add(s)
	length := len(str)
	temp := make([]int, length)
	maxRight := 0
	center := 0
	max := 1
	begin := 0
	for i := 0; i < length; i++ {
		if i < maxRight {
			mirror := 2*center - i
			temp[i] = min(maxRight-i, temp[mirror])
		}
		left := i - (1 + temp[i])
		right := i + (1 + temp[i])
		for left >= 0 && right < len(str) && str[left] == str[right] {
			temp[i]++
			left--
			right++
		}
		if i+temp[i] > maxRight {
			maxRight = i + temp[i]
			center = i
		}
		if temp[i] > max {
			max = temp[i]
			begin = (i - max) / 2
		}
	}
	return s[begin : begin+max]
}

func add(s string) string {
	var res []rune
	for _, v := range s {
		res = append(res, '#')
		res = append(res, v)
	}
	res = append(res, '#')
	return string(res)
}

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

6.Z字形变换(2)

• 题目

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L   C   I   R
E T O E S I I G
E   D   H   N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN"
示例 2:输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG"
解释:
L     D     R
E   O E   I I
E C   I H   N
T     S     G

• 解题思路

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

func convert(s string, numRows int) string {
	if numRows == 1 {
		return s
	}
	arr := []rune(s)
	total := numRows*2 - 2
	res := make([]string, numRows)
	for i := 0; i < len(arr); i++ {
		index := i % total
		if index < numRows {
			res[index] = res[index] + string(arr[i])
		} else {
			res[total-index] = res[total-index] + string(arr[i])
		}
	}
	return strings.Join(res, "")
}

#
func convert(s string, numRows int) string {
	if numRows == 1 {
		return s
	}
	arr := []rune(s)
	res := make([]string, numRows)
	flag := -1
	index := 0
	for i := 0; i < len(arr); i++ {
		res[index] = res[index] + string(arr[i])
		if index == 0 || index == numRows-1 {
			flag = -flag
		}
		index = index + flag
	}
	return strings.Join(res, "")
}

8.字符串转换整数 (atoi)(3)

• 题目

请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
   如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
   假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
   该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，
则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
    本题中的空白字符只包括空格字符 ' ' 。
    假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。
    如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:输入: "42" 输出: 42
示例 2:输入: "   -42" 输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:输入: "4193 with words" 输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:输入: "words and 987" 输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。
示例 5:输入: "-91283472332" 输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

• 解题思路

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

func myAtoi(str string) int {
	i := 0
	for i < len(str) && str[i] == ' ' {
		i++
	}
	str = str[i:]
	arr := make([]byte, 0)
	isFlag := byte(' ')
	for j := 0; j < len(str); j++ {
		if str[j] >= '0' && str[j] <= '9' {
			arr = append(arr, str[j])
		} else {
			if len(arr) > 0 {
				break
			}
			if str[j] != ' ' && str[j] != '+' && str[j] != '-' {
				return 0
			}
			if isFlag != ' ' {
				return 0
			}
			isFlag = str[j]
		}
	}
	res := 0
	for i := 0; i < len(arr); i++ {
		value := int(arr[i] - '0')
		res = res*10 + value
		if isFlag == '-' {
			if -1*res < math.MinInt32 {
				return math.MinInt32
			}
		} else if isFlag == ' ' || isFlag == '+' {
			if res > math.MaxInt32 {
				return math.MaxInt32
			}
		}
	}
	if isFlag == '-' {
		return -1 * res
	}
	return res
}

#
func myAtoi(str string) int {
	re := regexp.MustCompile(`^[+-]?\d+`)
	arrS := re.FindAllString(strings.Trim(str, " "), -1)
	if len(arrS) == 0{
		return 0
	}
	arr := arrS[0]
	res := 0
	isFlag := byte(' ')
	if !(arr[0] >= '0' && arr[0] <= '9') {
		isFlag = arr[0]
		arr = arr[1:]
	}
	for i := 0; i < len(arr); i++ {
		value := int(arr[i] - '0')
		if isFlag == '-' {
			if res > 214748364 || (res==214748364 && value >= 8) {
				return math.MinInt32
			}
		} else if isFlag == ' ' || isFlag == '+' {
			if res > 214748364 || (res==214748364 && value >= 7) {
				return math.MaxInt32
			}
		}
		res = res*10 + value
	}
	if isFlag == '-' {
		return -1 * res
	}
	return res
}

#
func myAtoi(str string) int {
	str = strings.TrimSpace(str)
	result := 0
	flag := 1
	for i, v := range str {
		if v >= '0' && v <= '9' {
			result = result*10 + int(v-'0')
		} else if v == '-' && i == 0 {
			flag = -1
		} else if v == '+' && i == 0 {
			flag = 1
		} else {
			break
		}
		if result > math.MaxInt32 {
			if flag == -1 {
				return math.MinInt32
			}
			return math.MaxInt32
		}
	}
	return flag * result
}

11.盛最多水的容器(2)

• 题目

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：输入：[1,8,6,2,5,4,8,3,7] 输出：49

• 解题思路

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

func maxArea(height []int) int {
	i := 0
	j := len(height) - 1
	res := 0
	for i < j {
		area := (j - i) * min(height[i], height[j])
		if area > res {
			res = area
		}
		// 移动较小的指针，尝试获取更大的面积
		if height[i] > height[j] {
			j--
		} else {
			i++
		}
	}
	return res
}

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

#
func maxArea(height []int) int {
	res := 0
	for i := 0; i < len(height); i++ {
		for j := i + 1; j < len(height); j++ {
			area := (j - i) * min(height[i], height[j])
			if area > res {
				res = area
			}
		}
	}
	return res
}

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

12.整数转罗马数字(2)

• 题目

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 
27 写做  XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。
数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
    I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
    X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
    C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:输入: 3输出: "III"
示例 2:输入: 4 输出: "IV"
示例 3:输入: 9 输出: "IX"
示例 4:输入: 58 输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:输入: 1994 输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

• 解题思路

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

func intToRoman(num int) string {
	m := map[int]string{
		1:    "I",
		4:    "IV",
		5:    "V",
		9:    "IX",
		10:   "X",
		40:   "XL",
		50:   "L",
		90:   "XC",
		100:  "C",
		400:  "CD",
		500:  "D",
		900:  "CM",
		1000: "M",
	}
	arr := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	result := ""
	for i := 0; i < len(arr); i++ {
		if num == 0 {
			break
		}
		value := num / arr[i]
		for j := 0; j < value; j++ {
			result = result + m[arr[i]]
		}
		num = num - value*arr[i]
	}
	return result
}

#
func intToRoman(num int) string {
	res := ""
	arr1 := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
	arr2 := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
	arr3 := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
	arr4 := []string{"", "M", "MM", "MMM"}
	res = arr4[num/1000] + arr3[num%1000/100] + arr2[num%100/10] + arr1[num%10]
	return res
}

15.三数之和(2)

• 题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

• 解题思路

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

func threeSum(nums []int) [][]int {
	res := make([][]int, 0)
	sort.Ints(nums)
	for i := 0; i < len(nums)-1; i++ {
		target := 0 - nums[i]
		left := i + 1
		right := len(nums) - 1
		if nums[i] > 0 || nums[i]+nums[left] > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for left < right {
			if left > i+1 && nums[left] == nums[left-1] {
				left++
				continue
			}
			if right < len(nums)-2 && nums[right] == nums[right+1] {
				right--
				continue
			}
			if nums[left]+nums[right] > target {
				right--
			} else if nums[left]+nums[right] < target {
				left++
			} else {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				left++
				right--
			}
		}
	}
	return res
}

#
func threeSum(nums []int) [][]int {
	res := make([][]int, 0)
	m := make(map[[2]int]int)
	p := make(map[int]int)
	sort.Ints(nums)
	for k, v := range nums {
		p[v] = k
	}
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if j != i+1 && nums[j] == nums[j-1] {
				continue
			}
			sum := nums[i] + nums[j]
			if sum > 0 {
				break
			}
			if value, ok := p[-sum]; ok && value > j {
				if _, ok2 := m[[2]int{nums[i], nums[j]}]; !ok2 {
					res = append(res, []int{nums[i], nums[j], 0 - nums[i] - nums[j]})
					m[[2]int{nums[i], nums[j]}] = 1
				}
			}
		}
	}
	return res
}

16.最接近的三数之和(2)

• 题目

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：输入：nums = [-1,2,1,-4], target = 1 输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
    3 <= nums.length <= 10^3
    -10^3 <= nums[i] <= 10^3
    -10^4 <= target <= 10^4

• 解题思路

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

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	res := nums[0] + nums[1] + nums[2]
	for i := 0; i < len(nums); i++ {
		left := i + 1
		right := len(nums) - 1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum > target {
				right--
			} else if sum < target {
				left++
			} else {
				return target
			}
			if abs(sum, target) < abs(res, target) {
				res = sum
			}
		}
	}
	return res
}

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

#
func threeSumClosest(nums []int, target int) int {
	res := nums[0] + nums[1] + nums[2]
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				sum := nums[i] + nums[j] + nums[k]
				if abs(sum, target) < abs(res, target) {
					res = sum
				}
			}
		}
	}
	return res
}

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

17.电话号码的字母组合(2)

• 题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

• 解题思路

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

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return nil
	}
	arr := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	res := []string{""}
	for i := 0; i < len(digits); i++ {
		length := len(res)
		for j := 0; j < length; j++ {
			for k := 0; k < len(arr[digits[i]-'0']); k++ {
				res = append(res, res[j]+string(arr[digits[i]-'0'][k]))
			}
		}
		res = res[length:]
	}
	return res
}

#
var res []string
var arr = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return nil
	}
	res = make([]string, 0)
	dfs(digits, 0, "")
	return res
}

func dfs(digits string, index int, str string) {
	if index == len(digits) {
		res = append(res, str)
		return
	}
	for i := 0; i < len(arr[digits[index]-'0']); i++ {
		dfs(digits, index+1, str+string(arr[digits[index]-'0'][i]))
	}
}

18.四数之和(3)

• 题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，
使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n^3)	O(n^3)
02	哈希辅助	O(n^3)	O(n^3)
03	全排列+递归	O(n^3)	O(n^3)

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums)
	res := make([][]int, 0)
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums); j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			temp := target - nums[i] - nums[j]
			left := j + 1
			right := len(nums) - 1
			for left < right {
				if left > j+1 && nums[left] == nums[left-1] {
					left++
					continue
				}
				if right < len(nums)-2 && nums[right] == nums[right+1] {
					right--
					continue
				}
				if nums[left]+nums[right] > temp {
					right--
				} else if nums[left]+nums[right] < temp {
					left++
				} else {
					res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
					left++
					right--
				}
			}
		}
	}
	return res
}

#
func fourSum(nums []int, target int) [][]int {
	m := make(map[[3]int]int)
	p := make(map[int]int)
	sort.Ints(nums)
	for k, v := range nums {
		p[v] = k
	}
	res := make([][]int, 0)
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				sum := nums[i] + nums[j] + nums[k]
				if value, ok := p[target-sum]; ok && value > k {
					if _, ok2 := m[[3]int{nums[i], nums[j], nums[k]}]; !ok2 {
						res = append(res, []int{nums[i], nums[j], nums[k], target - nums[i] - nums[j] - nums[k]})
						m[[3]int{nums[i], nums[j], nums[k]}] = 1
					}
				}
			}
		}
	}
	return res
}

#
var res [][]int

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums)
	res = make([][]int, 0)
	dfs(nums, target, []int{}, 0)
	return res
}

func dfs(nums []int, target int, arr []int, level int) {
	if len(arr) == 4 {
		sum := 0
		for i := 0; i < len(arr); i++ {
			sum = sum + arr[i]
		}
		if sum == target {
			tempArr := make([]int, len(arr))
			copy(tempArr, arr)
			res = append(res, tempArr)
		}
		return
	}
	prev := math.MaxInt32
	for i := level; i < len(nums); i++ {
		if nums[i] != prev {
			prev = nums[i]
			arr = append(arr, nums[i])
			dfs(nums, target, arr, i+1)
			arr = arr[:len(arr)-1]
		}
	}
}

19.删除链表的倒数第N个节点(3)

• 题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？

• 解题思路

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

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	temp := &ListNode{Next: head}
	cur := temp
	total := 0
	for cur.Next != nil {
		cur = cur.Next
		total++
	}
	cur = temp
	count := 0
	for cur.Next != nil {
		if total-n == count {
			cur.Next = cur.Next.Next
			break
		}
		cur = cur.Next
		count++
	}
	return temp.Next
}

#
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	temp := &ListNode{Next: head}
	fast, slow := temp, temp
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return temp.Next
}

#
var count int

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		count = 0
		return nil
	}
	head.Next = removeNthFromEnd(head.Next, n)
	count = count + 1
	if count == n {
		return head.Next
	}
	return head
}

22.括号生成(3)

• 题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	全排列-递归	O(4^n/n^(1/2))	O(4^n/n^(1/2))
02	动态规划	O(4^n/n^(1/2))	O(4^n/n^(1/2))
03	广度优先搜索	O(4^n/n^(1/2))	O(4^n/n^(1/2))

var res []string

func generateParenthesis(n int) []string {
	res = make([]string, 0)
	dfs(0, 0, n, "")
	return res
}

func dfs(left, right, max int, str string) {
	if left == right && left == max {
		res = append(res, str)
		return
	}
	if left < max {
		dfs(left+1, right, max, str+"(")
	}
	if right < left {
		dfs(left, right+1, max, str+")")
	}
}

#
/*
dp[i]表示n=i时括号的组合
dp[i]="(" + dp[j] + ")"+dp[i-j-1] (j<i)
dp[0] = ""
*/
func generateParenthesis(n int) []string {
	dp := make([][]string, n+1)
	dp[0] = make([]string, 0)
	if n == 0 {
		return dp[0]
	}
	dp[0] = append(dp[0], "")
	for i := 1; i <= n; i++ {
		dp[i] = make([]string, 0)
		for j := 0; j < i; j++ {
			for _, a := range dp[j] {
				for _, b := range dp[i-j-1] {
					str := "(" + a + ")" + b
					dp[i] = append(dp[i], str)
				}
			}
		}
	}
	return dp[n]
}

#
type Node struct {
	str   string
	left  int
	right int
}

func generateParenthesis(n int) []string {
	res := make([]string, 0)
	if n == 0 {
		return res
	}
	queue := make([]*Node, 0)
	queue = append(queue, &Node{
		str:   "",
		left:  n,
		right: n,
	})
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node.left == 0 && node.right == 0 {
			res = append(res, node.str)
		}
		if node.left > 0 {
			queue = append(queue, &Node{
				str:   node.str + "(",
				left:  node.left - 1,
				right: node.right,
			})
		}
		if node.right > 0 && node.left < node.right {
			queue = append(queue, &Node{
				str:   node.str + ")",
				left:  node.left,
				right: node.right - 1,
			})
		}
	}
	return res
}

24.两两交换链表中的节点(2)

• 题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:给定 1->2->3->4, 你应该返回 2->1->4->3.

• 解题思路

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

func swapPairs(head *ListNode) *ListNode {
	temp := &ListNode{Next: head}
	prev := temp
	for head != nil && head.Next != nil {
		first, second := head, head.Next
		prev.Next = second
		first.Next, second.Next = second.Next, first
		prev, head = first, first.Next
	}
	return temp.Next
}

#
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	first, second := head, head.Next
	first.Next, second.Next = swapPairs(second.Next), first
	return second
}

29.两数相除(2)

• 题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，
例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:输入: dividend = 10, divisor = 3输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:输入: dividend = 7, divisor = -3 输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
    被除数和除数均为 32 位有符号整数。
    除数不为 0。
    假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,  2^31 − 1]。
    本题中，如果除法结果溢出，则返回 2^31 − 1。

• 解题思路

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

func divide(dividend int, divisor int) int {
	if divisor == 0 || dividend == 0 {
		return 0
	}
	if divisor == 1 {
		return dividend
	}
	flag, count := 1, 1
	if dividend < 0 {
		flag = -flag
		dividend = -dividend
	}
	if divisor < 0 {
		flag = -flag
		divisor = -divisor
	}
	a, b, c := dividend, divisor, 0
	temp := b
	for a-b >= 0 {
		for a-b >= 0 {
			a = a - b
			c = c + count
			b = b + b
			count = count + count
		}
		b = temp
		count = 1
	}
	if c > math.MaxInt32 {
		return math.MaxInt32
	}
	if flag < 0 {
		return -c
	}
	return c
}

#
func divide(dividend int, divisor int) int {
	res := dividend / divisor
	if res > math.MaxInt32 {
		return math.MaxInt32
	}
	return res
}

31.下一个排列(2)

• 题目

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

• 解题思路

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

func nextPermutation(nums []int) {
	n := len(nums)
	left := n - 2
	// 以12385764为例，从后往前找到5<7 的升序情况，目标值为左边的数5
	for left >= 0 && nums[left] >= nums[left+1] {
		left--
	}
	if left == -1 {
		sort.Ints(nums)
		return
	}
	right := n - 1
	// 从后往前，找到第一个大于目标值的数，如6>5，然后交换
	for right >= 0 && nums[right] <= nums[left] {
		right--
	}
	nums[left], nums[right] = nums[right], nums[left]
	count := 0
	// 后面是降序状态，让它变为升序
	for i := left + 1; i <= (left+1+n-1)/2; i++ {
		nums[i], nums[n-1-count] = nums[n-1-count], nums[i]
		count++
	}
}

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

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

33.搜索旋转排序数组(2)

• 题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
示例 2:输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

• 解题思路

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

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[left] <= nums[mid] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}

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

34.在排序数组中查找元素的第一个和最后一个位置(4)

• 题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
示例 2:输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]

• 解题思路

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

func searchRange(nums []int, target int) []int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		if nums[left] != target {
			if target > nums[left] {
				left++
			}
		}
		if nums[right] != target {
			if target < nums[right] {
				right--
			}
		}
		if left < len(nums) && right >= 0 &&
			nums[left] == nums[right] && nums[left] == target {
			break
		}
	}
	if right < left {
		return []int{-1, -1}
	}
	return []int{left, right}
}

#
func searchRange(nums []int, target int) []int {
	left := -1
	right := -1
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			right = i
		} else if nums[i] > target {
			break
		}
	}
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] == target {
			left = i
		} else if nums[i] < target {
			break
		}
	}
	return []int{left, right}
}

# 3
func searchRange(nums []int, target int) []int {
	if len(nums) == 0 || nums[0] > target || nums[len(nums)-1] < target {
		return []int{-1, -1}
	}
	left := leftSearch(nums, target)
	right := rightSearch(nums, target)
	return []int{left, right}
}

func leftSearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if target > nums[mid] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if left < len(nums) && nums[left] == target {
		return left
	}
	return -1
}

func rightSearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if target < nums[mid] {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if right >= 0 && nums[right] == target {
		return right
	}
	return -1
}

#
func searchRange(nums []int, target int) []int {
	left := -1
	right := -1
	for i, j := 0, len(nums)-1; i <= j; {
		mid := i + (j-i)/2
		if nums[mid] < target {
			i = mid + 1
		} else if nums[mid] > target {
			j = mid - 1
		} else {
			for temp := mid; temp >= 0; temp-- {
				if target == nums[temp] {
					left = temp
				} else {
					break
				}
			}
			for temp := mid; temp < len(nums); temp++ {
				if target == nums[temp] {
					right = temp
				} else {
					break
				}
			}
			break
		}
	}
	return []int{left, right}
}

36.有效的数独(1)

• 题目

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
    一个有效的数独（部分已被填充）不一定是可解的。
    只需要根据以上规则，验证已经填入的数字是否有效即可。
    给定数独序列只包含数字 1-9 和字符 '.' 。
    给定数独永远是 9x9 形式的。

• 解题思路

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

func isValidSudoku(board [][]byte) bool {
	var row, col, arr [9][9]int
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				num := board[i][j] - '1'
				index := (i/3)*3 + j/3
				if row[i][num] == 1 || col[j][num] == 1 || arr[index][num] == 1 {
					return false
				}
				row[i][num] = 1
				col[j][num] = 1
				arr[index][num] = 1
			}
		}
	}
	return true
}

39.组合总和(2)

• 题目

给定一个无重复元素的数组 candidates 和一个目标数 target ，
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
    所有数字（包括 target）都是正整数。
    解集不能包含重复的组合。 
示例 1:输入: candidates = [2,3,6,7], target = 7, 所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:输入: candidates = [2,3,5], target = 8, 所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

• 解题思路

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

var res [][]int

func combinationSum(candidates []int, target int) [][]int {
	res = make([][]int, 0)
	sort.Ints(candidates)
	dfs(candidates, target, []int{}, 0)
	return res
}

func dfs(candidates []int, target int, arr []int, index int) {
	if target == 0 {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	if target < 0{
		return
	}
	for i := index; i < len(candidates); i++ {
		arr = append(arr, candidates[i])
		dfs(candidates, target-candidates[i], arr, i)
		arr = arr[:len(arr)-1]
	}
}

#
var res [][]int

func combinationSum(candidates []int, target int) [][]int {
	res = make([][]int, 0)
	sort.Ints(candidates)
	dfs(candidates, target, []int{}, 0)
	return res
}

func dfs(candidates []int, target int, arr []int, index int) {
	if target == 0 {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := index; i < len(candidates); i++ {
		if target < candidates[i] {
			return
		}
		dfs(candidates, target-candidates[i], append(arr, candidates[i]), i)
	}
}

40.组合总和II(2)

• 题目

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
    所有数字（包括目标数）都是正整数。
    解集不能包含重复的组合。 
示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

• 解题思路

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

var res [][]int

func combinationSum2(candidates []int, target int) [][]int {
	res = make([][]int, 0)
	sort.Ints(candidates)
	dfs(candidates, target, []int{}, 0)
	return res
}

func dfs(candidates []int, target int, arr []int, index int) {
	if target == 0 {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	if target < 0 {
		return
	}
	for i := index; i < len(candidates); i++ {
		origin := i
		for i < len(candidates)-1 && candidates[i] == candidates[i+1] {
			i++
		}
		arr = append(arr, candidates[i])
		dfs(candidates, target-candidates[i], arr, origin+1)
		arr = arr[:len(arr)-1]
	}
}

#
var res [][]int

func combinationSum2(candidates []int, target int) [][]int {
	res = make([][]int, 0)
	sort.Ints(candidates)
	dfs(candidates, target, []int{}, 0)
	return res
}

func dfs(candidates []int, target int, arr []int, index int) {
	if target == 0 {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := index; i < len(candidates); i++ {
		if i != index && candidates[i] == candidates[i-1] {
			continue
		}
		if target < 0 {
			return
		}
		arr = append(arr, candidates[i])
		dfs(candidates, target-candidates[i], arr, i+1)
		arr = arr[:len(arr)-1]
	}
}

43.字符串相乘(1)

• 题目

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，
它们的乘积也表示为字符串形式。
示例 1:输入: num1 = "2", num2 = "3"输出: "6"
示例 2:输入: num1 = "123", num2 = "456"输出: "56088"
说明：
    num1 和 num2 的长度小于110。
    num1 和 num2 只包含数字 0-9。
    num1 和 num2 均不以零开头，除非是数字 0 本身。
    不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

• 解题思路

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

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	arr := make([]int, len(num1)+len(num2))
	for i := len(num1) - 1; i >= 0; i-- {
		a := int(num1[i] - '0')
		for j := len(num2) - 1; j >= 0; j-- {
			b := int(num2[j] - '0')
			value := a*b + arr[i+j+1]
			arr[i+j+1] = value % 10
			arr[i+j] = value/10 + arr[i+j]
		}
	}
	res := ""
	for i := 0; i < len(arr); i++ {
		if i == 0 && arr[i] == 0 {
			continue
		}
		res = res + string(arr[i]+'0')
	}
	return res
}

# 2
func multiply(num1 string, num2 string) string {
	a, b := new(big.Int), new(big.Int)
	a.SetString(num1, 10)
	b.SetString(num2, 10)
	a.Mul(a, b)
	return a.String()
}

46.全排列(3)

• 题目

给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:输入: [1,2,3]输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

• 解题思路

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

var res [][]int

func permute(nums []int) [][]int {
	res = make([][]int, 0)
	arr := make([]int, 0)
	visited := make(map[int]bool)
	dfs(nums, 0, arr, visited)
	return res
}

func dfs(nums []int, index int, arr []int, visited map[int]bool) {
	if index == len(nums) {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := 0; i < len(nums); i++ {
		if visited[i] == false {
			arr = append(arr, nums[i])
			visited[i] = true
			dfs(nums, index+1, arr, visited)
			arr = arr[:len(arr)-1]
			visited[i] = false
		}
	}
}

#
func permute(nums []int) [][]int {
	if len(nums) == 1 {
		return [][]int{nums}
	}
	res := make([][]int, 0)
	for i := 0; i < len(nums); i++ {
		tempArr := make([]int, len(nums)-1)
		copy(tempArr[0:], nums[:i])
		copy(tempArr[i:], nums[i+1:])
		arr := permute(tempArr)
		for _, v := range arr {
			res = append(res, append(v, nums[i]))
		}
	}
	return res
}

#
var res [][]int

func permute(nums []int) [][]int {
	res = make([][]int, 0)
	arr := make([]int, len(nums))
	dfs(nums, 0, arr)
	return res
}

func dfs(nums []int, index int, arr []int) {
	if index == len(nums) {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := index; i < len(nums); i++ {
		arr[index] = nums[i]
		nums[i], nums[index] = nums[index], nums[i]
		dfs(nums, index+1, arr)
		nums[i], nums[index] = nums[index], nums[i]
	}
}

47.全排列II(3)

• 题目

给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:输入: [1,1,2] 输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

• 解题思路

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

var res [][]int

func permuteUnique(nums []int) [][]int {
	res = make([][]int, 0)
	sort.Ints(nums)
	dfs(nums, 0, make([]int, len(nums)), make([]int, 0))
	return res
}

func dfs(nums []int, index int, visited []int, arr []int) {
	if len(nums) == index {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := 0; i < len(nums); i++ {
		if visited[i] == 1 {
			continue
		}
		// visited[i-1] == 0 或者 visited[i-1] == 1都可以
		if i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0 {
			// if i > 0 && nums[i] == nums[i-1] && visited[i-1] == 1 {
			continue
		}
		arr = append(arr, nums[i])
		visited[i] = 1
		dfs(nums, index+1, visited, arr)
		visited[i] = 0
		arr = arr[:len(arr)-1]
	}
}

# 2
var res [][]int

func permuteUnique(nums []int) [][]int {
	res = make([][]int, 0)
	sort.Ints(nums)
	dfs(nums, 0)
	return res
}

func dfs(nums []int, index int) {
	if index == len(nums) {
		temp := make([]int, len(nums))
		copy(temp, nums)
		res = append(res, temp)
		return
	}
	m := make(map[int]int)
	for i := index; i < len(nums); i++ {
		if _, ok := m[nums[i]]; ok {
			continue
		}
		m[nums[i]] = 1
		nums[i], nums[index] = nums[index], nums[i]
		dfs(nums, index+1)
		nums[i], nums[index] = nums[index], nums[i]
	}
}

# 3
var res [][]int

func permuteUnique(nums []int) [][]int {
	res = make([][]int, 0)
	sort.Ints(nums)
	dfs(nums, make([]int, 0))
	return res
}

func dfs(nums []int, arr []int) {
	if len(nums) == 0 {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := 0; i < len(nums); i++ {
		if i != 0 && nums[i] == nums[i-1] {
			continue
		}
		tempArr := make([]int, len(nums))
		copy(tempArr, nums)
		arr = append(arr, nums[i])
		dfs(append(tempArr[:i], tempArr[i+1:]...), arr)
		arr = arr[:len(arr)-1]
	}
}

48.旋转图像(3)

• 题目

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
示例 2:给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 
原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

• 解题思路

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

func rotate(matrix [][]int) {
	n := len(matrix)
	// 同行逆置
	// [[1 2 3] [4 5 6] [7 8 9]]
	// [[3 2 1] [6 5 4] [9 8 7]]
	for i := 0; i < n; i++ {
		for j := 0; j < n/2; j++ {
			matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
		}
	}
	// 左下右上对角线对互换
	// [[3 2 1] [6 5 4] [9 8 7]]
	// [[7 4 1] [8 5 2] [9 6 3]]
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-1-i; j++ {
			matrix[i][j], matrix[n-1-j][n-1-i] = matrix[n-1-j][n-1-i], matrix[i][j]
		}
	}
}

# 2
func rotate(matrix [][]int) {
	n := len(matrix)
	for start, end := 0, n-1; start < end; {
		for s, e := start, end; s < end; {
			matrix[start][s], matrix[e][start], matrix[end][e], matrix[s][end] =
				matrix[e][start], matrix[end][e], matrix[s][end], matrix[start][s]
			s++
			e--
		}
		start++
		end--
	}
}

# 3
func rotate(matrix [][]int) {
	n := len(matrix)
	arr := make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			arr[j][n-1-i] = matrix[i][j]
		}
	}
	copy(matrix, arr)
}

49.字母异位词分组(2)

• 题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：
    所有输入均为小写字母。
    不考虑答案输出的顺序。

• 解题思路

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

func groupAnagrams(strs []string) [][]string {
	m := make(map[string]int)
	res := make([][]string, 0)
	for i := 0; i < len(strs); i++ {
		arr := []byte(strs[i])
		sort.Slice(arr, func(i, j int) bool {
			return arr[i] < arr[j]
		})
		newStr := string(arr)
		if _, ok := m[newStr]; ok {
			res[m[newStr]] = append(res[m[newStr]], strs[i])
		} else {
			m[newStr] = len(res)
			res = append(res, []string{strs[i]})
		}
	}
	return res
}

#
func groupAnagrams(strs []string) [][]string {
	m := make(map[[26]int]int)
	res := make([][]string, 0)
	for i := 0; i < len(strs); i++ {
		arr := [26]int{}
		for j := 0; j < len(strs[i]); j++{
			arr[strs[i][j]-'a']++
		}
		if _, ok := m[arr]; ok {
			res[m[arr]] = append(res[m[arr]], strs[i])
		} else {
			m[arr] = len(res)
			res = append(res, []string{strs[i]})
		}
	}
	return res
}

50.Pow(x,n)(4)

• 题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:输入: 2.00000, 10 输出: 1024.00000
示例 2:输入: 2.10000, 3 输出: 9.26100
示例 3:输入: 2.00000, -2 输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:  -100.0 < x < 100.0
    n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

• 解题思路

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

func myPow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	if n < 0 {
		return 1 / myPow(x, -n)
	}
	if n%2 == 1 {
		return x * myPow(x, n-1)
	}
	return myPow(x*x, n/2)
}

#
func myPow(x float64, n int) float64 {
	if n < 0 {
		x = 1 / x
		n = -n
	}
	res := float64(1)
	for n > 0 {
		if n%2 == 1 {
			res = res * x
		}
		x = x * x
		n = n / 2
	}
	return res
}

#
func myPow(x float64, n int) float64 {
	return math.Pow(x, float64(n))
}

#
func myPow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	if n == 1 {
		return x
	}
	res := 1.0
	if n > 0 {
		res = myPow(x, n/2)
		return res * res * myPow(x, n%2)
	} else {
		res = myPow(x, -n/2)
		res = res * res * myPow(x, -n%2)
		return 1 / res
	}
}

54.螺旋矩阵(2)

• 题目

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

• 解题思路

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

var res []int

func spiralOrder(matrix [][]int) []int {
	res = make([]int, 0)
	rows := len(matrix)
	if rows == 0 {
		return res
	}
	cols := len(matrix[0])
	if cols == 0 {
		return res
	}
	start := 0
	for cols > start*2 && rows > start*2 {
		printCircle(matrix, cols, rows, start)
		start++
	}
	return res
}

func printCircle(matrix [][]int, cols, rows, start int) {
	x := cols - 1 - start
	y := rows - 1 - start
	// 左到右
	for i := start; i <= x; i++ {
		res = append(res, matrix[start][i])
	}
	// 上到下
	if start < y {
		for i := start + 1; i <= y; i++ {
			res = append(res, matrix[i][x])
		}
	}
	// 右到左
	if start < x && start < y {
		for i := x - 1; i >= start; i-- {
			res = append(res, matrix[y][i])
		}
	}
	// 下到上
	if start < x && start < y-1 {
		for i := y - 1; i >= start+1; i-- {
			res = append(res, matrix[i][start])
		}
	}
}

#
func spiralOrder(matrix [][]int) []int {
	res := make([]int, 0)
	rows := len(matrix)
	if rows == 0 {
		return res
	}
	cols := len(matrix[0])
	if cols == 0 {
		return res
	}
	x1, x2, y1, y2 := 0, rows-1, 0, cols-1
	direct := 0
	for x1 <= x2 && y1 <= y2 {
		direct = (direct + 4) % 4
		if direct == 0 {
			for i := y1; i <= y2; i++ {
				res = append(res, matrix[x1][i])
			}
			x1++
		} else if direct == 1 {
			for i := x1; i <= x2; i++ {
				res = append(res, matrix[i][y2])
			}
			y2--
		} else if direct == 2 {
			for i := y2; i >= y1; i-- {
				res = append(res, matrix[x2][i])
			}
			x2--
		} else if direct == 3 {
			for i := x2; i >= x1; i-- {
				res = append(res, matrix[i][y1])
			}
			y1++
		}
		direct++
	}
	return res
}

55.跳跃游戏(4)

• 题目

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:输入: [2,3,1,1,4] 输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:输入: [3,2,1,0,4] 输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 
所以你永远不可能到达最后一个位置。

• 解题思路

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

func canJump(nums []int) bool {
	j := len(nums) - 1
	for i := len(nums) - 2; i >= 0; i-- {
		if nums[i]+i >= j {
			j = i
		}
	}
	return j <= 0
}

#
func canJump(nums []int) bool {
	if len(nums) <= 1 {
		return true
	}
	dp := make([]bool, len(nums))
	dp[0] = true
	for i := 1; i < len(nums); i++ {
		flag := false
		for j := 0; j < i; j++ {
			if dp[j] && nums[j]+j >= i {
				flag = true
				break
			}
		}
		dp[i] = flag
	}
	return dp[len(nums)-1]
}

#
func canJump(nums []int) bool {
	max := 0
	for i := 0; i < len(nums); i++ {
		if i <= max {
			if i+nums[i] > max {
				max = i + nums[i]
			}
			if max >= len(nums)-1 {
				return true
			}
		}
	}
	return false
}

#
func canJump(nums []int) bool {
	zero := -1
	for i := len(nums) - 2; i >= 0; i-- {
		if zero > 0 {
			if i+nums[i] > zero {
				zero = -1
			}
			continue
		}
		if nums[i] == 0 {
			zero = i
			continue
		}
	}
	return zero < 0
}

56.合并区间(2)

• 题目

给出一个区间的集合，请合并所有重叠的区间。
示例 1:输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:输入: [[1,4],[4,5]] 输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

• 解题思路

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

func merge(intervals [][]int) [][]int {
	res := make([][]int, 0)
	if len(intervals) == 0 {
		return nil
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	res = append(res, intervals[0])
	for i := 1; i < len(intervals); i++ {
		arr := res[len(res)-1]
		if intervals[i][0] > arr[1] {
			res = append(res, intervals[i])
		} else if intervals[i][1] > arr[1] {
			res[len(res)-1][1] = intervals[i][1]
		}
	}
	return res
}

#
func merge(intervals [][]int) [][]int {
	res := make([][]int, 0)
	if len(intervals) == 0 {
		return nil
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	for i := 0; i < len(intervals); {
		end := intervals[i][1]
		j := i + 1
		for j < len(intervals) && intervals[j][0] <= end {
			if intervals[j][1] > end {
				end = intervals[j][1]
			}
			j++
		}
		res = append(res, []int{intervals[i][0], end})
		i = j
	}
	return res
}

59.螺旋矩阵II(2)

• 题目

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:输入: 3 输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

• 解题思路

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

func generateMatrix(n int) [][]int {
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, n)
	}
	count := 1
	level := 1
	for count <= n*n {
		top, bottom, left, right := level-1, n-level, level-1, n-level
		// 左到右
		for i := left; i <= right && left <= right; i++ {
			res[top][i] = count
			count++
		}
		// 上到下
		for i := top + 1; i <= bottom && top <= bottom; i++ {
			res[i][right] = count
			count++
		}
		// 右到左
		for i := right - 1; i >= left && left <= right; i-- {
			res[bottom][i] = count
			count++
		}
		// 下到上
		for i := bottom - 1; i >= top+1 && top <= bottom; i-- {
			res[i][left] = count
			count++
		}
		level++
	}
	return res
}

#
func generateMatrix(n int) [][]int {
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, n)
	}
	count := 1
	top, bottom, left, right := 0, n-1, 0, n-1
	for count <= n*n {
		for i := left; i <= right; i++ {
			res[top][i] = count
			count++
		}
		top++
		for i := top; i <= bottom; i++ {
			res[i][right] = count
			count++
		}
		right--
		for i := right; i >= left; i-- {
			res[bottom][i] = count
			count++
		}
		bottom--
		for i := bottom; i >= top; i-- {
			res[i][left] = count
			count++
		}
		left++
	}
	return res
}

60.第k个排列(1)

• 题目

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
    "123"
    "132"
    "213"
    "231"
    "312"
    "321"
给定 n 和 k，返回第 k 个排列。
说明：
    给定 n 的范围是 [1, 9]。
    给定 k 的范围是[1,  n!]。
示例 1:输入: n = 3, k = 3 输出: "213"
示例 2:输入: n = 4, k = 9 输出: "2314"

• 解题思路

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

func getPermutation(n int, k int) string {
	res := ""
	arr := []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
	times := make([]int, 0)
	times = append(times, 1)
	value := 1
	for i := 1; i <= 9; i++ {
		times = append(times, value*i)
		value = value * i
	}
	k--
	for n > 0 {
		i := k / times[n-1]
		k = k % times[n-1]
		n--
		res = res + arr[i]
		arr = append(arr[:i], arr[i+1:]...)
	}
	return res
}

61.旋转链表(2)

• 题目

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	统计遍历	O(n)	O(1)
02	数组辅助	O(n)	O(n)

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || k == 0 {
		return head
	}
	temp := head
	count := 1
	for temp.Next != nil {
		temp = temp.Next
		count++
	}
	temp.Next = head
	k = k % count
	for i := 0; i < count-k; i++ {
		temp = temp.Next
	}
	head, temp.Next = temp.Next, nil
	return head
}

#
func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || k == 0 {
		return head
	}
	temp := head
	count := 0
	arr := make([]*ListNode, 0)
	for temp != nil {
		arr = append(arr, temp)
		temp = temp.Next
		count++
	}
	k = k % count
	if k == 0 {
		return head
	}
	arr[count-1].Next = head
	temp = arr[count-1-k]
	head, temp.Next = temp.Next, nil
	return head
}

62.不同路径(4)

• 题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:输入: m = 3, n = 2 输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:输入: m = 7, n = 3 输出: 28
提示：
    1 <= m, n <= 100
    题目数据保证答案小于等于 2 * 10 ^ 9

• 解题思路

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

// dp[i][j] = dp[i-1][j] + dp[i][j-1]
func uniquePaths(m int, n int) int {
	if m <= 0 || n <= 0 {
		return 0
	}
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		dp[i][0] = 1
	}
	for i := 0; i < m; i++ {
		dp[0][i] = 1
	}
	for i := 1; i < n; i++ {
		for j := 1; j < m; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[n-1][m-1]
}

#
// dp[i]= dp[i-1] + dp[i]
func uniquePaths(m int, n int) int {
	if m <= 0 || n <= 0 {
		return 0
	}
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[j] = dp[j] + dp[j-1]
		}
	}
	return dp[n-1]
}

# 3
func uniquePaths(m int, n int) int {
	if m == 1 || n == 1 {
		return 1
	}
	if m > n {
		m, n = n, m
	}
	a := 1
	for i := 1; i <= m-1; i++ {
		a = a * i
	}
	b := 1
	for i := n; i <= m+n-2; i++ {
		b = b * i
	}
	return b / a
}

# 4
var arr [][]int

func uniquePaths(m int, n int) int {
	arr = make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	return dfs(m, n)
}

func dfs(m, n int) int {
	if m <= 0 || n <= 0 {
		return 0
	}
	if m == 1 || n == 1 {
		return 1
	}
	if arr[n][m] > 0 {
		return arr[n][m]
	}
	arr[n][m] = dfs(m, n-1) + dfs(m-1, n)
	return arr[n][m]
}

63.不同路径II(3)

• 题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

• 解题思路

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

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	n := len(obstacleGrid)
	if n < 1 {
		return 0
	}
	m := len(obstacleGrid[0])
	if m < 1 {
		return 0
	}
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
		for j := 0; j < m; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = 1
			} else if i == 0 && j != 0 {
				if obstacleGrid[i][j] == 0 {
					dp[i][j] = dp[i][j-1]
				}
			} else if i != 0 && j == 0 {
				if obstacleGrid[i][j] == 0 {
					dp[i][j] = dp[i-1][j]
				}
			} else {
				if obstacleGrid[i][j] == 0 {
					dp[i][j] = dp[i-1][j] + dp[i][j-1]
				}
			}
		}
	}
	return dp[n-1][m-1]
}

# 2
// dp[j] = dp[j] + dp[j-1]
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	n := len(obstacleGrid)
	if n < 1 {
		return 0
	}
	m := len(obstacleGrid[0])
	if m < 1 {
		return 0
	}
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	dp := make([]int, m)
	dp[0] = 1
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if obstacleGrid[i][j] == 1 {
				dp[j] = 0
				continue
			}
			if j >= 1 && obstacleGrid[i][j-1] == 0 {
				dp[j] = dp[j] + dp[j-1]
			}
		}
	}
	return dp[m-1]
}

# 3
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	n := len(obstacleGrid)
	if n < 1 {
		return 0
	}
	m := len(obstacleGrid[0])
	if m < 1 {
		return 0
	}
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
				continue
			}
			if i == 0 {
				if j == 0 {
					obstacleGrid[i][j] = 1
				} else {
					obstacleGrid[i][j] += obstacleGrid[i][j-1]
				}
			} else {
				if j == 0 {
					obstacleGrid[i][j] += obstacleGrid[i-1][j]
				} else {
					obstacleGrid[i][j] += obstacleGrid[i][j-1] + obstacleGrid[i-1][j]
				}
			}
		}
	}
	return obstacleGrid[n-1][m-1]
}

64.最小路径和(4)

• 题目

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。

• 解题思路

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

func minPathSum(grid [][]int) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}
	dp[0][0] = grid[0][0]
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 && j != 0 {
				dp[i][j] = dp[i][j-1] + grid[i][j]
			} else if i != 0 && j == 0 {
				dp[i][j] = dp[i-1][j] + grid[i][j]
			} else if i != 0 && j != 0 {
				dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
			}
		}
	}
	return dp[n-1][m-1]
}

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

#
func minPathSum(grid [][]int) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 && j != 0 {
				grid[i][j] = grid[i][j-1] + grid[i][j]
			} else if i != 0 && j == 0 {
				grid[i][j] = grid[i-1][j] + grid[i][j]
			} else if i != 0 && j != 0 {
				grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
			}
		}
	}
	return grid[n-1][m-1]
}

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

# 3
func minPathSum(grid [][]int) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])
	dp := make([]int, m)
	dp[0] = grid[0][0]

	for i := 1; i < m; i++ {
		dp[i] = dp[i-1] + grid[0][i]
	}
	for i := 1; i < n; i++ {
		dp[0] = dp[0] + grid[i][0]
		for j := 1; j < m; j++ {
			dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
		}
	}
	return dp[m-1]
}

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

# 4
var arr [][]int

func minPathSum(grid [][]int) int {
	n := len(grid)
	if n == 0 {
		return 0
	}
	m := len(grid[0])
	arr = make([][]int, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]int, m)
	}
	return dfs(grid, n-1, m-1)
}

func dfs(grid [][]int, n, m int) int {
	if m == 0 && n == 0 {
		arr[0][0] = grid[0][0]
		return grid[0][0]
	}
	if n == 0 {
		return grid[0][m] + dfs(grid, 0, m-1)
	}
	if m == 0 {
		return grid[n][0] + dfs(grid, n-1, 0)
	}
	if arr[n][m] > 0 {
		return arr[n][m]
	}
	arr[n][m] = min(dfs(grid, n-1, m), dfs(grid, n, m-1)) + grid[n][m]
	return arr[n][m]
}

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

71.简化路径(2)

• 题目

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；
此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。
最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：输入："/home/" 输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：输入："/../" 输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：输入："/home//foo/" 输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：输入："/a/./b/../../c/" 输出："/c"
示例 5：输入："/a/../../b/../c//.//" 输出："/c"
示例 6：输入："/a//b////c/d//././/.." 输出："/a/b/c"

• 解题思路

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

func simplifyPath(path string) string {
	stack := make([]string, 0)
	arr := strings.Split(path, "/")
	for i := 0; i < len(arr); i++ {
		if arr[i] == "." || arr[i] == "" {
			continue
		}
		if arr[i] == ".." {
			if len(stack) > 0 {
				stack = stack[:len(stack)-1]
			}
		} else {
			stack = append(stack, arr[i])
		}
	}
	return "/" + strings.Join(stack, "/")
}

#
func simplifyPath(path string) string {
	return filepath.Clean(path)
}

73.矩阵置零(4)

• 题目

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
示例 2:
输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]
进阶:
    一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
    一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
    你能想出一个常数空间的解决方案吗？

• 解题思路

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

func setZeroes(matrix [][]int) {
	x := make(map[int]int)
	y := make(map[int]int)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				x[i] = 1
				y[j] = 1
			}
		}
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if x[i] == 1 || y[j] == 1 {
				matrix[i][j] = 0
			}
		}
	}
}

#
func setZeroes(matrix [][]int) {
	m := make(map[[2]int]bool)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == math.MinInt32 {
				m[[2]int{i, j}] = true
			}
		}
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				for k := 0; k < len(matrix); k++ {
					for l := 0; l < len(matrix[k]); l++ {
						if (k == i || l == j) && matrix[k][l] != 0 {
							delete(m, [2]int{k, l})
							matrix[k][l] = math.MinInt32
						}
					}
				}
			}
		}
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == math.MinInt32 && m[[2]int{i, j}] == false {
				matrix[i][j] = 0
			}
		}
	}
}

# 3
func setZeroes(matrix [][]int) {
	flag := false
	for i := 0; i < len(matrix); i++ {
		if matrix[i][0] == 0 {
			flag = true
		}
		for j := 1; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0
				matrix[0][j] = 0
			}
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[i]); j++ {
			if matrix[i][0] == 0 || matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}
	// 第一行处理
	if matrix[0][0] == 0 {
		for j := 0; j < len(matrix[0]); j++ {
			matrix[0][j] = 0
		}
	}
	// 第一列处理
	if flag == true {
		for i := 0; i < len(matrix); i++ {
			matrix[i][0] = 0
		}
	}
}

# 4
func setZeroes(matrix [][]int) {
	flag := false
	for i := 0; i < len(matrix); i++ {
		if matrix[i][0] == 0 {
			flag = true
		}
		for j := 1; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0
				matrix[0][j] = 0
			}
		}
	}
	for i := len(matrix) - 1; i >= 0; i-- {
		for j := len(matrix[i]) - 1; j >= 1; j-- {
			if matrix[i][0] == 0 || matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}
	// 第一列处理
	if flag == true {
		for i := 0; i < len(matrix); i++ {
			matrix[i][0] = 0
		}
	}
}

74.搜索二维矩阵(6)

• 题目

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
    每行中的整数从左到右按升序排列。
    每行的第一个整数大于前一行的最后一个整数。
示例 1:输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true
示例 2:输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(1)
02	暴力法-优化	O(n^2)	O(1)
03	二分查找	O(nlog(n))	O(1)
04	左下角查找	O(n)	O(1)
05	右上角查找	O(n)	O(1)
06	内置函数	O(n^2)	O(1)

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	if len(matrix[0]) == 0 {
		return false
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == target {
				return true
			}
		}
	}
	return false
}

# 2
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	if len(matrix[0]) == 0 {
		return false
	}
	for i := 0; i < len(matrix); i++ {
		if matrix[i][0] <= target && matrix[i][len(matrix[i])-1] >= target {
			for j := 0; j < len(matrix[i]); j++ {
				if matrix[i][j] == target {
					return true
				}
			}
		}
	}
	return false
}

# 3
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	if len(matrix[0]) == 0 {
		return false
	}
	for i := 0; i < len(matrix); i++ {
		if matrix[i][0] <= target && matrix[i][len(matrix[i])-1] >= target {
			res := binarySearch(matrix[i], target)
			if res == true {
				return true
			}
		}
	}
	return false
}

func binarySearch(arr []int, target int) bool {
	left := 0
	right := len(arr) - 1
	for left <= right {
		mid := left + (right-left)/2
		if arr[mid] == target {
			return true
		} else if arr[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return false
}

# 4
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	if len(matrix[0]) == 0 {
		return false
	}
	i := len(matrix) - 1
	j := 0
	for i >= 0 && j < len(matrix[0]) {
		if matrix[i][j] == target {
			return true
		} else if matrix[i][j] > target {
			i--
		} else {
			j++
		}
	}
	return false
}

# 5
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	if len(matrix[0]) == 0 {
		return false
	}
	i := 0
	j := len(matrix[0]) - 1
	for j >= 0 && i < len(matrix) {
		if matrix[i][j] == target {
			return true
		} else if matrix[i][j] > target {
			j--
		} else {
			i++
		}
	}
	return false
}

# 6
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	if len(matrix[0]) == 0 {
		return false
	}
	for i := 0; i < len(matrix); i++ {
		index := sort.SearchInts(matrix[i], target)
		if index < len(matrix[i]) && target == matrix[i][index] {
			return true
		}
	}
	return false
}

75.颜色分类(3)

• 题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，
使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
进阶：
    一个直观的解决方案是使用计数排序的两趟扫描算法。
    首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
    你能想出一个仅使用常数空间的一趟扫描算法吗？

• 解题思路

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

func sortColors(nums []int) {
	sort.Ints(nums)
}

# 2
func sortColors(nums []int) {
	left := 0
	right := len(nums) - 1
	for i := 0; i <= right; i++ {
		if nums[i] == 0 {
			nums[left], nums[i] = nums[i], nums[left]
			left++
		} else if nums[i] == 2 {
			nums[right], nums[i] = nums[i], nums[right]
			right--
			i--
		}
	}
}

# 3
func sortColors(nums []int) {
	arr := make([]int, 3)
	for i := 0; i < len(nums); i++ {
		arr[nums[i]]++
	}
	count := 0
	for i := 0; i < len(arr); i++ {
		for j := 0; j < arr[i]; j++ {
			nums[count] = i
			count++
		}
	}
}

77.组合(5)

• 题目

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:输入: n = 4, k = 2 输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	回溯-递归	O(kC(n,k))	O(C(n,k))
02	回溯	O(kC(n,k))	O(C(n,k))
03	回溯	O(kC(n,k))	O(C(n,k))
04	迭代	O(kC(n,k))	O(C(n,k))
05	回溯	O(kC(n,k))	O(C(n,k))

var res [][]int

func combine(n int, k int) [][]int {
	res = make([][]int, 0)
	nums := make([]int, 0)
	for i := 1; i <= n; i++ {
		nums = append(nums, i)
	}
	dfs(nums, 0, k)
	return res
}

func dfs(nums []int, index, k int) {
	if index == k {
		temp := make([]int, k)
		copy(temp, nums[:k])
		res = append(res, temp)
		return
	}
	for i := index; i < len(nums); i++ {
		if index == 0 || nums[i] > nums[index-1] {
			nums[i], nums[index] = nums[index], nums[i]
			dfs(nums, index+1, k)
			nums[i], nums[index] = nums[index], nums[i]
		}
	}
}

# 2
var res [][]int

func combine(n int, k int) [][]int {
	res = make([][]int, 0)
	dfs(n, k, 1, make([]int, 0))
	return res
}

func dfs(n, k, index int, arr []int) {
	if len(arr) == k {
		temp := make([]int, k)
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := index; i <= n; i++ {
		arr = append(arr, i)
		dfs(n, k, i+1, arr)
		arr = arr[:len(arr)-1]
	}
}

# 3
var res [][]int

func combine(n int, k int) [][]int {
	res = make([][]int, 0)
	nums := make([]int, 0)
	for i := 1; i <= n; i++ {
		nums = append(nums, i)
	}
	dfs(nums, 0, k, make([]int, 0))
	return res
}

func dfs(nums []int, index, k int, arr []int) {
	if len(arr) == k {
		temp := make([]int, k)
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	for i := index; i < len(nums); i++ {
		arr = append(arr, nums[i])
		dfs(nums, i+1, k, arr)
		arr = arr[:len(arr)-1]
	}
}

# 4
func combine(n int, k int) [][]int {
	res := make([][]int, 0)
	arr := make([]int, 0)
	for i := 1; i <= k; i++ {
		arr = append(arr, 0)
	}
	i := 0
	for i >= 0 {
		arr[i]++
		if arr[i] > n {
			i--
		} else if i == k-1 {
			temp := make([]int, k)
			copy(temp, arr)
			res = append(res, temp)
		} else {
			i++
			arr[i] = arr[i-1]
		}
	}
	return res
}

# 5
var res [][]int

func combine(n int, k int) [][]int {
	res = make([][]int, 0)
	dfs(n, k, 1, make([]int, 0))
	return res
}

func dfs(n, k, index int, arr []int) {
	if index > n+1 {
		return
	}
	if len(arr) == k {
		temp := make([]int, k)
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	dfs(n, k, index+1, arr)
	arr = append(arr, index)
	dfs(n, k, index+1, arr)
}

78.子集(4)

• 题目

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:输入: nums = [1,2,3] 输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

• 解题思路

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)

var res [][]int

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

func dfs(nums []int, arr []int, level int) {
	temp := make([]int, len(arr))
	copy(temp, arr)
	res = append(res, temp)
	for i := level; i < len(nums); i++ {
		dfs(nums, append(arr, nums[i]), i+1)
	}
}

# 2
func subsets(nums []int) [][]int {
	res := make([][]int, 0)
	res = append(res, []int{})
	for i := 0; i < len(nums); i++ {
		temp := make([][]int, len(res))
		for key, value := range res {
			value = append(value, nums[i])
			temp[key] = append(temp[key], value...)
		}
		for _, v := range temp {
			res = append(res, v)
		}
	}
	return res
}

# 3
func subsets(nums []int) [][]int {
	res := make([][]int, 0)
	n := len(nums)
	left := 1 << n
	right := 1 << (n + 1)
	for i := left; i < right; i++ {
		temp := make([]int, 0)
		for j := 0; j < n; j++ {
			if i&(1<<j) != 0 {
				temp = append(temp, nums[j])
			}
		}
		res = append(res, temp)
	}
	return res
}

# 4
var res [][]int

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

func dfs(nums []int, arr []int, level int) {
	if level >= len(nums) {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
		return
	}
	dfs(nums, arr, level+1)
	dfs(nums, append(arr, nums[level]), level+1)
}

79.单词搜索(2)

• 题目

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。
示例:board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示：
    board 和 word 中只包含大写和小写英文字母。
    1 <= board.length <= 200
    1 <= board[i].length <= 200
    1 <= word.length <= 10^3

• 解题思路

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

func exist(board [][]byte, word string) bool {
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if dfs(board, i, j, word, 0) {
				return true
			}
		}
	}
	return false
}

func dfs(board [][]byte, i, j int, word string, level int) bool {
	if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) ||
		board[i][j] != word[level] {
		return false
	}
	if level == len(word)-1 {
		return true
	}
	temp := board[i][j]
	board[i][j] = ' '
	res := dfs(board, i+1, j, word, level+1) ||
		dfs(board, i-1, j, word, level+1) ||
		dfs(board, i, j+1, word, level+1) ||
		dfs(board, i, j-1, word, level+1)
	board[i][j] = temp
	return res
}

#
func exist(board [][]byte, word string) bool {
	visited := make([][]bool, len(board))
	for i := 0; i < len(board); i++ {
		visited[i] = make([]bool, len(board[0]))
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if dfs(board, i, j, word, 0, visited) {
				return true
			}
		}
	}
	return false
}

func dfs(board [][]byte, i, j int, word string, level int, visited [][]bool) bool {
	res := false
	if i >= 0 && i < len(board) && j >= 0 && j < len(board[0]) &&
		visited[i][j] == false && board[i][j] == word[level] {
		if level == len(word)-1 {
			return true
		}
		visited[i][j] = true
		level = level + 1
		res = dfs(board, i+1, j, word, level, visited) ||
			dfs(board, i-1, j, word, level, visited) ||
			dfs(board, i, j+1, word, level, visited) ||
			dfs(board, i, j-1, word, level, visited)
		if !res {
			visited[i][j] = false
			level = level - 1
		}
	}
	return res
}

80.删除排序数组中的重复项II(2)

• 题目

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
示例 2:给定 nums = [0,0,1,1,1,1,2,3,3],
函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
你不需要考虑数组中超出新长度后面的元素。
说明:为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

• 解题思路

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

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

#
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	prev := nums[0]
	count := 1
	j := 1
	for i := 1; i < len(nums); i++ {
		if nums[i] == prev {
			count = count + 1
		} else {
			count = 1
			prev = nums[i]
		}
		if count <= 2 {
			nums[j] = nums[i]
			j++
		}
	}
	return j
}

81.搜索旋转排序数组II(2)

• 题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true
示例 2:输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false
进阶:
    这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
    这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

• 解题思路

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

func search(nums []int, target int) bool {
	for i := 0; i < len(nums); i++ {
		if target == nums[i] {
			return true
		}
	}
	return false
}

#
func search(nums []int, target int) bool {
	left, right := 0, len(nums)-1
	for left <= right {
		for left < right && nums[left] == nums[left+1] {
			left++
		}
		for left < right && nums[right] == nums[right-1] {
			right--
		}
		mid := left + (right-left)/2
		if nums[mid] == target {
			return true
		}
		if nums[left] <= nums[mid] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return false
}

82.删除排序链表中的重复元素II(3)

• 题目

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:输入: 1->2->3->3->4->4->5 输出: 1->2->5
示例 2:输入: 1->1->1->2->3 输出: 2->3

• 解题思路

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

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	temp := &ListNode{Next: head}
	cur := temp
	value := 0
	for cur.Next != nil && cur.Next.Next != nil {
		if cur.Next.Val == cur.Next.Next.Val {
			value = cur.Next.Val
			for cur.Next != nil && cur.Next.Val == value {
				cur.Next = cur.Next.Next
			}
		} else {
			cur = cur.Next
		}
	}
	return temp.Next
}

#
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	flag := false
	for head.Next != nil && head.Val == head.Next.Val{
		head = head.Next
		flag = true
	}
	head.Next = deleteDuplicates(head.Next)
	if flag{
		return head.Next
	}
	return head
}

#
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	flag := false
	for head.Next != nil && head.Val == head.Next.Val{
		head = head.Next
		flag = true
	}
	head.Next = deleteDuplicates(head.Next)
	if flag{
		return head.Next
	}
	return head
}

86.分隔链表(2)

• 题目

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

• 解题思路

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

func partition(head *ListNode, x int) *ListNode {
	first := &ListNode{}
	second := &ListNode{}
	a := first
	b := second
	for head != nil {
		if head.Val < x {
			a.Next = head
			a = head
		} else {
			b.Next = head
			b = head
		}
		head = head.Next
	}
	b.Next = nil
	a.Next = second.Next
	return first.Next
}

#
func partition(head *ListNode, x int) *ListNode {
	a := make([]*ListNode, 0)
	b := make([]*ListNode, 0)

	for head != nil {
		if head.Val < x {
			a = append(a, head)
		} else {
			b = append(b, head)
		}
		head = head.Next
	}
	temp := &ListNode{}
	node := temp
	for i := 0; i < len(a); i++ {
		node.Next = a[i]
		node = node.Next
	}
	for i := 0; i < len(b); i++ {
		node.Next = b[i]
		node = node.Next
	}
	node.Next = nil
	return temp.Next
}

89.格雷编码(3)

• 题目

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。
示例 1:输入: 2 输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的 n，其格雷编码序列并不唯一。例如，[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0
10 - 2
11 - 3
01 - 1
示例 2:输入: 0 输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
     给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
     因此，当 n = 0 时，其格雷编码序列为 [0]。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历-推导	O(2^n)	O(2^n)
02	公式	O(2^n)	O(2^n)
03	遍历	O(2^n)	O(2^n)

func grayCode(n int) []int {
	if n == 0 {
		return []int{0}
	}
	res := []int{0, 1}
	for i := 1; i < n; i++ {
		temp := make([]int, 0)
		value := 1 << i
		for j := len(res) - 1; j >= 0; j-- {
			// 10 1 11
			// 10 0 10
			// 100 10 110
			// 100 11 111
			// 100 1 101
			// 100 0 100
			// fmt.Printf("%b %b %b\n", value, res[j], res[j]^value)

			// temp = append(temp, res[j]|value)
			// temp = append(temp, res[j]^value)
			temp = append(temp, res[j]+value)
		}
		res = append(res, temp...)
	}
	return res
}

# 2
func grayCode(n int) []int {
	total := 1 << n
	res := make([]int, 0)
	for i := 0; i < total; i++ {
		res = append(res, i^(i>>1))
	}
	return res
}

# 3
func grayCode(n int) []int {
	if n == 0 {
		return []int{0}
	}
	res := []int{0, 1}
	for i := 1; i < n; i++ {
		value := 1 << i
		for j := len(res) - 1; j >= 0; j-- {
			res= append(res, res[j]+value)
		}
	}
	return res
}

90.子集II(2)

• 题目

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:输入: [1,2,2] 输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

• 解题思路

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

var res [][]int

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	res = make([][]int, 0)
	dfs(nums, make([]int, 0), 0)
	return res
}

func dfs(nums []int, arr []int, level int) {
	temp := make([]int, len(arr))
	copy(temp, arr)
	res = append(res, temp)
	for i := level; i < len(nums); i++ {
		if i > level && nums[i] == nums[i-1] {
			continue
		}
		arr = append(arr, nums[i])
		dfs(nums, arr, i+1)
		arr = arr[:len(arr)-1]
	}
}

# 2
var res [][]int

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	res = make([][]int, 0)
	dfs(nums, make([]int, 0))
	return res
}

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

91.解码方法(3)

• 题目

一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:输入: "12" 输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:输入: "226" 输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

• 解题思路

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

func numDecodings(s string) int {
	if s[0] == '0' {
		return 0
	}
	pre := 1
	cur := 1
	for i := 1; i < len(s); i++ {
		temp := cur
		if s[i] == '0' {
			if s[i-1] == '1' || s[i-1] == '2' {
				cur = pre
			} else {
				return 0
			}
		} else if s[i-1] == '1' || 
			(s[i-1] == '2' && s[i] >= '1' && s[i] <= '6') {
			cur = cur + pre
		}
		pre = temp
	}
	return cur
}

# 2
func numDecodings(s string) int {
	if s[0] == '0' {
		return 0
	}
	dp := make([]int, len(s)+1)
	dp[0] = 1
	for i := 0; i < len(s); i++{
		if s[i] == '0' {
			if i == 0 || s[i-1] == '1' || s[i-1] == '2' {
				return 0
			}
			dp[i+1] = dp[i-1]
		} else{
			if  i > 0 && (s[i-1] == '2' && s[i] >= '1' && s[i] <= '6') {
				dp[i+1] = dp[i-1]+dp[i]
			}else {
				dp[i+1] = dp[i]
			}
		}
	}
	return dp[len(s)]
}

# 3
var m map[string]int

func numDecodings(s string) int {
	m = make(map[string]int)
	return dfs(s)
}

func dfs(s string) int {
	if m[s] > 0 {
		return m[s]
	}
	if len(s) == 0 {
		return 1
	}
	if s[0] == '0' {
		return 0
	}
	if len(s) == 1 {
		return 1
	}
	if (s[0]-'0')*10+s[1]-'0' > 26 {
		return dfs(s[1:])
	}
	m[s] = dfs(s[1:]) + dfs(s[2:])
	return m[s]
}

92.反转链表II(2)

• 题目

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

• 解题思路

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

func reverseBetween(head *ListNode, m int, n int) *ListNode {
	if m == n || head == nil {
		return head
	}
	temp := &ListNode{Next: head}
	prev := temp
	for i := 1; i < m; i++ {
		prev = prev.Next
	}
	head = prev.Next
	for i := m; i < n; i++ {
		next := head.Next
		head.Next = next.Next
		next.Next = prev.Next
		prev.Next = next
	}
	return temp.Next
}

# 2
func reverseBetween(head *ListNode, m int, n int) *ListNode {
	if m == 1 {
		return reverseN(head, n)
	}
	head.Next = reverseBetween(head.Next, m-1, n-1)
	return head
}

var next *ListNode

func reverseN(head *ListNode, n int) *ListNode {
	if n == 1 {
		next = head.Next
		return head
	}
	prev := reverseN(head.Next, n-1)
	head.Next.Next = head
	head.Next = next
	return prev
}

93.复原IP地址(2)

• 题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
示例:输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]

• 解题思路

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

var res []string

func restoreIpAddresses(s string) []string {
	res = make([]string, 0)
	if len(s) < 4 || len(s) > 12 {
		return nil
	}
	dfs(s, make([]string, 0), 0)
	return res
}

func dfs(s string, arr []string, level int) {
	if level == 4 {
		if len(s) == 0 {
			str := strings.Join(arr, ".")
			res = append(res, str)
		}
		return
	}
	for i := 1; i <= 3; i++ {
		if i <= len(s) {
			value, _ := strconv.Atoi(s[:i])
			if value <= 255 {
				str := s[i:]
				dfs(str, append(arr, s[:i]), level+1)
			}
			if value == 0 {
				// 避免出现001,01这种情况
				break
			}
		}
	}
}

# 2
func restoreIpAddresses(s string) []string {
	res := make([]string, 0)
	if len(s) < 4 || len(s) > 12 {
		return nil
	}
	for i := 1; i <= 3 && i < len(s)-2; i++ {
		for j := i + 1; j <= i+3 && j < len(s)-1; j++ {
			for k := j + 1; k <= j+3 && k < len(s); k++ {
				if judge(s[:i]) && judge(s[i:j]) &&
					judge(s[j:k]) && judge(s[k:]) {
					res = append(res, s[:i]+"."+s[i:j]+"."+s[j:k]+"."+s[k:])
				}
			}
		}
	}
	return res
}

func judge(s string) bool {
	if len(s) > 1 && s[0] == '0' {
		return false
	}
	value, _ := strconv.Atoi(s)
	if value > 255 {
		return false
	}
	return true
}

94.二叉树的中序遍历(3)

• 题目

给定一个二叉树，返回它的中序 遍历。
示例:输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

• 解题思路

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

func inorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	left := inorderTraversal(root.Left)
	right := inorderTraversal(root.Right)
	res := left
	res = append(res, root.Val)
	res = append(res, right...)
	return res
}

# 2
func inorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	stack := make([]*TreeNode, 0)
	res := make([]int, 0)
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		last := len(stack) - 1
		res = append(res, stack[last].Val)
		root = stack[last].Right
		stack = stack[:last]
	}
	return res
}

# 3
var res []int

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

func dfs(root *TreeNode) {
	if root != nil {
		dfs(root.Left)
		res = append(res, root.Val)
		dfs(root.Right)
	}
}

95.不同的二叉搜索树II(2)

• 题目

给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
示例：输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：以上的输出对应以下 5 种不同结构的二叉搜索树：
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
提示：
    0 <= n <= 8

• 解题思路

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

func generateTrees(n int) []*TreeNode {
	if n == 0 {
		return nil
	}
	return dfs(1, n)
}

func dfs(left, right int) []*TreeNode {
	if left > right {
		return []*TreeNode{nil}
	}
	if left == right {
		return []*TreeNode{
			{Val: left},
		}
	}
	arr := make([]*TreeNode, 0)
	for i := left; i <= right; i++ {
		leftTree := dfs(left, i-1)
		rightTree := dfs(i+1, right)
		for j := 0; j < len(leftTree); j++ {
			for k := 0; k < len(rightTree); k++ {
				node := &TreeNode{Val: i}
				node.Left = leftTree[j]
				node.Right = rightTree[k]
				arr = append(arr, node)
			}
		}
	}
	return arr
}

# 2
func generateTrees(n int) []*TreeNode {
	if n == 0 {
		return nil
	}
	dp := make([][]*TreeNode, n+1)
	dp[1] = append(dp[1], &TreeNode{Val: 1})
	for i := 2; i <= n; i++ {
		for _, node := range dp[i-1]{
			root := &TreeNode{Val:i}
			root.Left = node
			dp[i] = append(dp[i], copyTree(root))
			root = node
			temp := root
			newNode := &TreeNode{Val:i}
			for temp != nil{
				newNode.Left = temp.Right
				temp.Right = newNode
				dp[i] = append(dp[i], copyTree(root))
				temp.Right = newNode.Left
				newNode.Left = nil
				temp = temp.Right
			}
		}
	}
	return dp[n]
}

func copyTree(node *TreeNode) *TreeNode {
	if node == nil {
		return nil
	}
	newNode := &TreeNode{Val: node.Val}
	newNode.Left = copyTree(node.Left)
	newNode.Right = copyTree(node.Right)
	return newNode
}

96.不同的二叉搜索树(3)

• 题目

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:输入: 3 输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

• 解题思路

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

func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0] =1
	dp[1] =1
	for i := 2; i <= n;i++{
		for j := 1; j <= i; j++{
			dp[i] = dp[i] + dp[j-1]*dp[i-j]
		}
	}
	return dp[n]
}

#
/*
C0 = 1
Cn+1 = 2(2n+1)/(n+2) * Cn
*/
func numTrees(n int) int {
	c := 1
	for i := 1; i < n;i++{
		c = c * 2 * (2*i+1)/(i+2)
	}
	return c
}

#
func numTrees(n int) int {
	c := 1
	for i := 1; i <= n;i++{
		c = c * (n+i)/i
	}
	return c/(n+1)
}

98.验证二叉搜索树(5)

• 题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。
示例 1:输入:
    2
   / \
  1   3
输出: true
示例 2:输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

• 解题思路

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

func isValidBST(root *TreeNode) bool {
	return dfs(root, math.MinInt64, math.MaxInt64)
}

func dfs(root *TreeNode, left, right int) bool {
	if root == nil {
		return true
	}
	if left >= root.Val || right <= root.Val {
		return false
	}
	return dfs(root.Left, left, root.Val) && dfs(root.Right, root.Val, right)
}

# 2
var res []int

func isValidBST(root *TreeNode) bool {
	res = make([]int, 0)
	dfs(root)
	for i := 0; i < len(res)-1; i++ {
		if res[i] >= res[i+1] {
			return false
		}
	}
	return true
}

func dfs(root *TreeNode) {
	if root != nil {
		dfs(root.Left)
		res = append(res, root.Val)
		dfs(root.Right)
	}
}

# 3
func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	stack := make([]*TreeNode, 0)
	res := make([]int, 0)
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		last := len(stack) - 1
		res = append(res, stack[last].Val)
		root = stack[last].Right
		stack = stack[:last]
	}
	for i := 0; i < len(res)-1; i++ {
		if res[i] >= res[i+1] {
			return false
		}
	}
	return true
}

# 4
func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	stack := make([]*TreeNode, 0)
	pre := math.MinInt64
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		last := len(stack) - 1
		if stack[last].Val <= pre {
			return false
		}
		pre = stack[last].Val
		root = stack[last].Right
		stack = stack[:last]
	}
	return true
}

# 5
var pre int

func isValidBST(root *TreeNode) bool {
	pre = math.MinInt64
	return dfs(root)
}

func dfs(root *TreeNode) bool {
	if root == nil {
		return true
	}
	if dfs(root.Left) == false {
		return false
	}
	if root.Val <= pre {
		return false
	}
	pre = root.Val
	return dfs(root.Right)
}

0001-1000-Hard

4.寻找两个正序数组的中位数(4)

• 题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:nums1 = [1, 3] nums2 = [2]
则中位数是 2.0
示例 2:nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

• 解题思路

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

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	nums1 = append(nums1, nums2...)
	sort.Ints(nums1)
	if len(nums1)%2 == 1 {
		return float64(nums1[len(nums1)/2])
	}
	return float64(nums1[len(nums1)/2]+nums1[len(nums1)/2-1]) / 2
}

# 2
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	total := len(nums1) + len(nums2)
	if total%2 == 1 {
		mid := total / 2
		return float64(getKth(nums1, nums2, mid+1))
	}
	mid1, mid2 := total/2-1, total/2
	return float64(getKth(nums1, nums2, mid1+1)+getKth(nums1, nums2, mid2+1)) / 2.0
}

func getKth(nums1 []int, nums2 []int, k int) int {
	a, b := 0, 0
	for {
		if a == len(nums1) {
			return nums2[b+k-1]
		}
		if b == len(nums2) {
			return nums1[a+k-1]
		}
		if k == 1 {
			return min(nums1[a], nums2[b])
		}
		mid := k / 2
		newA := min(a+mid, len(nums1)) - 1
		newB := min(b+mid, len(nums2)) - 1
		valueA, valueB := nums1[newA], nums2[newB]
		if valueA < valueB {
			k = k - (newA - a + 1)
			a = newA + 1
		} else {
			k = k - (newB - b + 1)
			b = newB + 1
		}
	}
}

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

# 3
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	total := len(nums1) + len(nums2)
	a, b := total/2, (total-1)/2
	count := 0
	res := 0
	for i, j := 0, 0; i < len(nums1) || j < len(nums2); count++ {
		if i < len(nums1) && (j == len(nums2) || nums1[i] < nums2[j]) {
			if count == a {
				res = res + nums1[i]
			}
			if count == b {
				res = res + nums1[i]
			}
			i++
		} else {
			if count == a {
				res = res + nums2[j]
			}
			if count == b {
				res = res + nums2[j]
			}
			j++
		}
	}
	return float64(res) / 2
}

# 4
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	n, m := len(nums1), len(nums2)
	if n > m {
		return findMedianSortedArrays(nums2, nums1)
	}
	left, right := 0, n
	a, b := 0, 0
	for left <= right {
		// 左半部分最大的值小于等于右半部分最小的值: max(A[i-1],B[j-1])) <= min(A[i],B[j]))
		i := left + (right-left)/2 // i,j分别对num1,num2的划分
		j := (n+m+1)/2 - i         // i+j == (n+m+1)/2
		// 偶数求a=>max(A[i-1],B[j-1])) b=>min(A[i],B[j]))
		// 奇数求a=>max(A[i-1],B[j-1]))
		if j != 0 && i != n && nums1[i] < nums2[j-1] {
			left = i + 1
		} else if i != 0 && j != m && nums1[i-1] > nums2[j] {
			right = i - 1
		} else {
			if i == 0 {
				a = nums2[j-1]
			} else if j == 0 {
				a = nums1[i-1]
			} else {
				a = max(nums1[i-1], nums2[j-1])
			}
			if (n+m)%2 == 1 {
				return float64(a)
			}
			if i == n {
				b = nums2[j]
			} else if j == m {
				b = nums1[i]
			} else {
				b = min(nums1[i], nums2[j])
			}
			return float64(a+b) / 2.0
		}
	}
	return 0.0
}

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
}

10.正则表达式匹配(3)

• 题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:输入:s = "aa" p = "a" 输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:输入: s = "aa" p = "a*" 输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。
因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:输入: s = "ab" p = ".*" 输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:输入:s = "aab"p = "c*a*b" 输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:输入:s = "mississippi"p = "mis*is*p*." 输出: false

• 解题思路

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

func isMatch(s string, p string) bool {
	return dfs(s, p, 0, 0)
}

func dfs(s string, p string, i, j int) bool {
	if i >= len(s) && j >= len(p) {
		return true
	}
	if i <= len(s) && j >= len(p) {
		return false
	}
	if j+1 < len(p) && p[j+1] == '*' {
		if (i < len(s) && p[j] == s[i]) || (p[j] == '.' && i < len(s)) {
			return dfs(s, p, i+1, j+2) ||
				dfs(s, p, i+1, j) ||
				dfs(s, p, i, j+2)
		} else {
			return dfs(s, p, i, j+2)
		}
	}
	if (i < len(s) && s[i] == p[j]) || (p[j] == '.' && i < len(s)) {
		return dfs(s, p, i+1, j+1)
	}
	return false
}

# 2
func isMatch(s string, p string) bool {
	// dp[i][j]表示p[:i]能否正则匹配s[:j]
	dp := make([][]bool, len(p)+1)
	for i := 0; i < len(p)+1; i++ {
		dp[i] = make([]bool, len(s)+1)
	}
	// 1.初始化
	dp[0][0] = true
	for i := 2; i < len(p)+1; i++ {
		if i%2 == 0 && p[i-1] == '*' {
			dp[i][0] = dp[i-2][0]
		}
	}
	// 2.dp状态转移
	for i := 1; i < len(p)+1; i++ {
		for j := 1; j < len(s)+1; j++ {
			// 2.1 相同或者 .
			if p[i-1] == s[j-1] || p[i-1] == '.' {
				dp[i][j] = dp[i-1][j-1]
			} else if p[i-1] == '*' {
				if i > 1 {
					if p[i-2] == s[j-1] || p[i-2] == '.' {
						dp[i][j] = dp[i][j-1] || dp[i-2][j-1] || dp[i-2][j]
					} else {
						dp[i][j] = dp[i-2][j]
					}
				}
			}
		}
	}
	return dp[len(p)][len(s)]
}

# 3
func isMatch(s string, p string) bool {
	if len(s) == 0 && len(p) == 0 {
		return true
	} else if len(p) == 0 {
		return false
	}
	match := false
	// 正常匹配条件=>相等，或者 p[0]等于.就不用管s[0]
	if len(s) > 0 && (s[0] == p[0] || p[0] == '.') {
		match = true
	}
	// 匹配多个 就把 s 往后移1位，注意p不移动
	// 匹配0个 就把 p 往后移2位，相当于p的*当前作废
	if len(p) > 1 && p[1] == '*' {
		return (match && isMatch(s[1:], p)) || isMatch(s, p[2:])
	}
	// 匹配当前成功，同时往后移
	return match && isMatch(s[1:], p[1:])
}

23.合并K个排序链表(4)

• 题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	顺序合并	O(n^2)	O(1)
02	归并(分治)合并	O(nlog(n))	O(log(n))
03	堆辅助	O(nlog(n))	O(log(n))
04	自定义排序	O(nlog(n))	O(n)

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	temp := &ListNode{}
	for i := 0; i < len(lists); i++ {
		temp.Next = mergeTwoLists(temp.Next, lists[i])
	}
	return temp.Next
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	res := &ListNode{}
	temp := res
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			temp.Next = l1
			l1 = l1.Next
		} else {
			temp.Next = l2
			l2 = l2.Next
		}
		temp = temp.Next
	}
	if l1 != nil {
		temp.Next = l1
	} else {
		temp.Next = l2
	}
	return res.Next
}

# 2
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	first := mergeKLists(lists[:len(lists)/2])
	second := mergeKLists(lists[len(lists)/2:])
	return mergeTwoLists(first, second)
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	res := &ListNode{}
	temp := res
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			temp.Next = l1
			l1 = l1.Next
		} else {
			temp.Next = l2
			l2 = l2.Next
		}
		temp = temp.Next
	}
	if l1 != nil {
		temp.Next = l1
	} else {
		temp.Next = l2
	}
	return res.Next
}

# 3
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	var h IntHeap
	heap.Init(&h)
	for i := 0; i < len(lists); i++ {
		if lists[i] != nil {
			heap.Push(&h, lists[i])
		}
	}
	res := &ListNode{}
	temp := res
	for h.Len() > 0 {
		minItem := heap.Pop(&h).(*ListNode)
		temp.Next = minItem
		temp = temp.Next
		if minItem.Next != nil {
			heap.Push(&h, minItem.Next)
		}
	}
	return res.Next
}

type IntHeap []*ListNode

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
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.(*ListNode)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

# 4
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	arr := make([]*ListNode, 0)
	for i := 0; i < len(lists); i++ {
		temp := lists[i]
		for temp != nil {
			arr = append(arr, temp)
			temp = temp.Next
		}
	}
	if len(arr) == 0 {
		return nil
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i].Val < arr[j].Val
	})
	for i := 0; i < len(arr)-1; i++ {
		arr[i].Next = arr[i+1]
	}
	arr[len(arr)-1].Next = nil
	return arr[0]
}

25.K个一组翻转链表(4)

• 题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
    你的算法只能使用常数的额外空间。
    你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

• 解题思路

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

func reverseKGroup(head *ListNode, k int) *ListNode {
	length := getLength(head)
	if length < k || k <= 1 {
		return head
	}
	pre := &ListNode{}
	cur := head
	for i := 0; i < k; i++ {
		temp := cur
		cur = cur.Next
		temp.Next = pre
		pre = temp
	}
	head.Next = reverseKGroup(cur, k)
	return pre
}

func getLength(head *ListNode) int {
	if head == nil {
		return 0
	}
	temp := head
	res := 0
	for temp != nil {
		res++
		temp = temp.Next
	}
	return res
}

# 2
func reverseKGroup(head *ListNode, k int) *ListNode {
	res := 0
	temp := head
	for temp != nil {
		res++
		temp = temp.Next
	}
	if res < k || k <= 1 {
		return head
	}
	pre := &ListNode{}
	cur := head
	for i := 0; i < k; i++ {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	head.Next = reverseKGroup(cur, k)
	return pre
}

# 3
func reverseKGroup(head *ListNode, k int) *ListNode {
	res := &ListNode{Next: head}
	prev := res
	for head != nil {
		tail := prev
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil {
				return res.Next
			}
		}
		next := tail.Next
		head, tail = reverse(head, tail)
		prev.Next = head
		tail.Next = next
		prev = tail
		head = tail.Next
	}
	return res.Next
}

func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
	prev := tail.Next
	temp := head
	for prev != tail {
		next := temp.Next
		temp.Next = prev
		prev = temp
		temp = next
	}
	return tail, head
}

# 4
func reverseKGroup(head *ListNode, k int) *ListNode {
	res := &ListNode{Next: head}
	prev, end := res, res
	for end.Next != nil {
		for i := 0; i < k && end != nil; i++ {
			end = end.Next
		}
		if end == nil {
			break
		}
		start := prev.Next         // 开始的位置
		next := end.Next           // 结束的下一个位置
		end.Next = nil             // 断开尾部连接
		prev.Next = reverse(start) // 反转后接到prev.Next
		start.Next = next          // start的指针指向下一个开头（此时start已经是反转的最后一个节点）
		prev = start               // 已经处理后的最后一个节点
		end = prev                 // end也移动到prev
	}
	return res.Next
}

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

30.串联所有单词的子串(2)

• 题目

给定一个字符串 s 和一些长度相同的单词 words。
找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：输入：s = "barfoothefoobarman",words = ["foo","bar"] 输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：输入：s = "wordgoodgoodgoodbestword",words = ["word","good","best","word"]输出：[]

• 解题思路

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

func findSubstring(s string, words []string) []int {
	res := make([]int, 0)
	length,n := len(s),len(words)
	if length == 0 || n == 0 || len(words[0]) == 0 {
		return res
	}
	single := len(words[0])
	m := make(map[string]int)
	for i := 0; i < len(words); i++ {
		m[words[i]]++
	}
	for i := 0; i <= length-n*single; i++ {
		temp := make(map[string]int)
		for j := 0; j < n; j++ {
			l := i + j*single
			str := s[l : l+single]
			if _, ok := m[str]; !ok {
				break
			}
			temp[str]++
			if temp[str] > m[str] {
				break
			}
			if compare(m, temp) == true {
				res = append(res, i)
				break
			}
		}
	}
	return res
}

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

# 2
func findSubstring(s string, words []string) []int {
	res := make([]int, 0)
	length := len(s)
	n := len(words)
	if length == 0 || n == 0 || len(words[0]) == 0 {
		return res
	}
	single := len(words[0])
	m := make(map[string]int)
	for i := 0; i < len(words); i++ {
		m[words[i]]++
	}
	for i := 0; i < single; i++ {
		left, right, count := i, i, 0
		temp := make(map[string]int)
		for right+single <= length {
			str := s[right : right+single]
			right = right + single
			if m[str] > 0 {
				temp[str]++
				if temp[str] == m[str] {
					count++
				}
			}
			if right-left == n*single {
				if count == len(m) {
					res = append(res, left)
				}
				leftStr := s[left : left+single]
				left = left + single
				if m[leftStr] > 0 {
					if temp[leftStr] == m[leftStr] {
						count--
					}
					temp[leftStr]--
				}
			}
		}
	}
	return res
}

32.最长有效括号(4)

• 题目

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:输入: "(()"输出: 2
解释: 最长有效括号子串为 "()"
示例 2:输入: ")()())" 输出: 4
解释: 最长有效括号子串为 "()()"

• 解题思路

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

func longestValidParentheses(s string) int {
	res := 0
	stack := make([]int, 0)
	stack = append(stack, -1)
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, i)
		} else {
			stack = stack[:len(stack)-1] // 弹出栈顶元素表示匹配了当前右括号
			if len(stack) == 0 {         // 没有匹配到左括号，存入最后一个没有被匹配到的右括号下标
				stack = append(stack, i)
			} else {
				res = max(res, i-stack[len(stack)-1])
			}
		}
	}
	return res
}

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

# 2
func longestValidParentheses(s string) int {
	res := 0
	dp := make([]int, len(s))
	for i := 1; i < len(s); i++ {
		if s[i] == ')' {
			// '()' 匹配到
			if s[i-1] == '(' {
				if i < 2 {
					dp[i] = 2
				} else {
					dp[i] = dp[i-2] + 2
				}
			} else {
				// '))'情况
				if i-dp[i-1] > 0 && s[i-dp[i-1]-1] == '(' {
					if i-dp[i-1] < 2 {
						dp[i] = dp[i-1] + 2
					} else {
						dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
					}
				}
			}
		}
		res = max(res, dp[i])
	}
	return res
}

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

# 3
func longestValidParentheses(s string) int {
	res := 0
	left, right := 0, 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			res = max(res, 2*left)
		} else if right > left {
			left, right = 0, 0
		}
	}
	left, right = 0, 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			res = max(res, 2*left)
		} else if left > right {
			left, right = 0, 0
		}
	}
	return res
}

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

# 4
func longestValidParentheses(s string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		count := 0
		for j := i; j < len(s); j++ {
			if s[j] == '(' {
				count++
			} else {
				count--
			}
			if count < 0 {
				break
			}
			if count == 0 {
				res = max(res, j+1-i)
			}
		}
	}
	return res
}

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

37.解数独(2)

• 题目

编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:给定的数独序列只包含数字 1-9 和字符 '.' 。
    你可以假设给定的数独只有唯一解。
    给定数独永远是 9x9 形式的。

• 解题思路

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

var rows, cols, arrs [9][9]int

func solveSudoku(board [][]byte) {
	rows = [9][9]int{}
	cols = [9][9]int{}
	arrs = [9][9]int{}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				num := board[i][j] - '1'
				index := (i/3)*3 + j/3
				rows[i][num] = 1
				cols[j][num] = 1
				arrs[index][num] = 1
			}
		}
	}
	dfs(board, 0)
}

func dfs(board [][]byte, index int) bool {
	if index == 81 {
		return true
	}
	row := index / 9
	col := index % 9
	c := (row/3)*3 + col/3
	if board[row][col] != '.' {
		return dfs(board, index+1)
	}
	for i := 0; i < 9; i++ {
		if rows[row][i] == 1 || cols[col][i] == 1 || arrs[c][i] == 1 {
			continue
		}
		board[row][col] = byte(i + '1')
		rows[row][i], cols[col][i], arrs[c][i] = 1, 1, 1
		if dfs(board, index+1) == true {
			return true
		}
		rows[row][i], cols[col][i], arrs[c][i] = 0, 0, 0
		board[row][col] = '.'
	}
	return false
}

# 2
func solveSudoku(board [][]byte) {
	dfs(board, 0)
}

func dfs(board [][]byte, index int) bool {
	if index == 81 {
		return true
	}
	row := index / 9
	col := index % 9
	if board[row][col] != '.' {
		return dfs(board, index+1)
	}
	for i := 0; i < 9; i++ {
		board[row][col] = byte(i + '1')
		if isValidSudoku(board) == false {
			board[row][col] = '.'
			continue
		}
		if dfs(board, index+1) == true {
			return true
		}
		board[row][col] = '.'
	}
	return false
}

func isValidSudoku(board [][]byte) bool {
	var row, col, arr [9][9]int
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				num := board[i][j] - '1'
				index := (i/3)*3 + j/3
				if row[i][num] == 1 || col[j][num] == 1 || arr[index][num] == 1 {
					return false
				}
				row[i][num] = 1
				col[j][num] = 1
				arr[index][num] = 1
			}
		}
	}
	return true
}

41.缺失的第一个正数(5)

• 题目

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:输入: [1,2,0] 输出: 3
示例 2:输入: [3,4,-1,1]输出: 2
示例 3:输入: [7,8,9,11,12]输出: 1
提示：你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	标负	O(n)	O(1)
02	置换	O(n)	O(1)
03	哈希辅助	O(n)	O(n)
04	暴力法	O(n^2)	O(1)
05	桶	O(n)	O(n)

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		// 非正数处理
		if nums[i] <= 0 {
			nums[i] = n + 1
		}
	}
	for i := 0; i < n; i++ {
		value := abs(nums[i])
		// 标负
		if value <= n {
			nums[value-1] = -abs(abs(nums[value-1]))
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] > 0 {
			return i + 1
		}
	}
	return n + 1
}

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

# 2
func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}

# 3
func firstMissingPositive(nums []int) int {
	n := len(nums)
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		m[nums[i]] = 1
	}
	for i := 1; i <= n; i++ {
		if m[i] == 0 {
			return i
		}
	}
	return n + 1
}

# 4
func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 1; i <= n; i++ {
		flag := false
		for j := 0; j < n; j++ {
			if i == nums[j] {
				flag = true
				break
			}
		}
		if flag == false {
			return i
		}
	}
	return n + 1
}

# 5
func firstMissingPositive(nums []int) int {
	n := len(nums)
	arr := make([]int, n+1)
	for i := 0; i < n; i++ {
		if 1 <= nums[i] && nums[i] <= n {
			arr[nums[i]] = 1
		}
	}
	for i := 1; i <= n; i++ {
		if arr[i] == 0 {
			return i
		}
	}
	return n + 1
}

42.接雨水(4)

• 题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6

• 解题思路

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

func trap(height []int) int {
	res := 0
	for i := 0; i < len(height); i++ {
		left, right := 0, 0
		for j := i; j >= 0; j-- {
			left = max(left, height[j])
		}
		for j := i; j < len(height); j++ {
			right = max(right, height[j])
		}
		// 当前坐标形成的面积=(min(左边最高，右边最高)-当前高度) * 宽度(1,可省略)
		area := min(left, right) - height[i]
		res = res + area
	}
	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 trap(height []int) int {
	res := 0
	if len(height) == 0{
		return 0
	}
	left := make([]int, len(height))
	right := make([]int, len(height))
	left[0] = height[0]
	right[len(right)-1] = height[len(height)-1]
	for i := 1; i < len(height); i++ {
		left[i] = max(height[i], left[i-1])
	}
	for i := len(height) - 2; i >= 0; i-- {
		right[i] = max(height[i], right[i+1])
	}
	for i := 0; i < len(height); i++ {
		// 当前坐标形成的面积=(min(左边最高，右边最高)-当前高度) * 宽度(1,可省略)
		area := min(left[i], right[i]) - height[i]
		res = res + area
	}
	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
}

# 3
func trap(height []int) int {
	res := 0
	stack := make([]int, 0)
	for i := 0; i < len(height); i++ {
		for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
			bottom := height[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			if len(stack) > 0 {
				prev := stack[len(stack)-1]
				// 横着的面积=长(min(height[i], height[prev])-bottom)*宽(i-prev-1)
				h := min(height[i], height[prev]) - bottom
				w := i - prev - 1
				area := h * w
				res = res + area
			}
		}
		stack = append(stack, i)
	}
	return res
}

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

# 4
func trap(height []int) int {
	res := 0
	if len(height) == 0 {
		return 0
	}
	left := 0
	right := len(height) - 1
	leftMax := 0  // 左边的最大值
	rightMax := 0 // 右边的最大值
	for left < right {
		// 当前坐标形成的面积=(min(左边最高，右边最高)-当前高度) * 宽度(1,可省略)
		// 选择高度低的一边处理并求最大值, 说明当前侧最大值小于另一侧
		if height[left] < height[right] {
			// 也可以写成这样
			// leftMax = max(leftMax, height[left])
			// res = res + leftMax - height[left]
			if height[left] >= leftMax { // 递增无法蓄水
				leftMax = height[left]
			} else {
				res = res + leftMax - height[left]
			}
			left++
		} else {
			// 也可以写成这样
			// rightMax = max(rightMax, height[right])
			// res = res + rightMax - height[right]
			if height[right] >= rightMax { // 递减无法蓄水
				rightMax = height[right]
			} else {
				res = res + rightMax - height[right]
			}
			right--
		}
	}
	return res
}

44.通配符匹配(3)

• 题目

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1: 输入:s = "aa" p = "a" 输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2: 输入: s = "aa" p = "*" 输出: true
解释: '*' 可以匹配任意字符串。
示例 3:输入: s = "cb" p = "?a" 输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:输入:s = "adceb" p = "*a*b" 输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:输入:s = "acdcb" p = "a*c?b" 输出: false

• 解题思路

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

func isMatch(s string, p string) bool {
	n, m := len(s), len(p)
	dp := make([][]bool, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]bool, m+1)
	}
	dp[0][0] = true
	for i := 1; i <= m; i++ {
		if p[i-1] == '*' { // 可以匹配任意字符串（包括空字符串）
			dp[0][i] = true
		} else {
			break
		}
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if p[j-1] == '*' {
				// dp[i][j-1]=>不使用这个*，dp[i-1][j]=>使用这个*
				dp[i][j] = dp[i][j-1] || dp[i-1][j]
			} else if p[j-1] == '?' || s[i-1] == p[j-1] {
				dp[i][j] = dp[i-1][j-1]
			}
		}
	}
	return dp[n][m]
}

# 2
var dp [][]int

func isMatch(s string, p string) bool {
	n, m := len(s), len(p)
	dp = make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, m+1)
	}
	return dfs(s, p, 0, 0)
}

func dfs(s, p string, i, j int) bool {
	if i == len(s) && j == len(p) {
		return true
	}
	if dp[i][j] > 0 {
		if dp[i][j] == 1 {
			return false
		} else {
			return true
		}
	}
	if i >= len(s) {
		return p[j] == '*' && dfs(s, p, i, j+1)
	}
	if j >= len(p) {
		return false
	}
	res := false
	if p[j] == '*' {
		res = dfs(s, p, i+1, j) || dfs(s, p, i, j+1)
	} else {
		res = (s[i] == p[j] || p[j] == '?') && dfs(s, p, i+1, j+1)
	}
	if res == true {
		dp[i][j] = 2
	} else {
		dp[i][j] = 1
	}
	return res
}

# 3
func isMatch(s string, p string) bool {
	i, j := 0, 0
	start, last := 0, 0
	for i = 0; i < len(s); {
		if j < len(p) && (s[i] == p[j] || p[j] == '?') {
			i++
			j++
		} else if j < len(p) && p[j] == '*' {
			last = i  // 记录s的位置
            j++
			start = j // 记录*的位置
		} else if start != 0 {
			last++
			i = last // 更新到记录位置的下一个
			j = start
		} else {
			return false
		}
	}
	for ; j < len(p) && p[j] == '*'; j++ {
	}
	return j == len(p)
}

45.跳跃游戏II(4)

• 题目

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:输入: [2,3,1,1,4] 输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:假设你总是可以到达数组的最后一个位置。

• 解题思路

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

func jump(nums []int) int {
	last := len(nums) - 1
	res := 0
	for last > 0 {
		// 从前往后，找到第一个一步能走到终点的，更新终点的位置
		for i := 0; i < last; i++ {
			if i+nums[i] >= last {
				last = i
				res++
				break
			}
		}
	}
	return res
}

# 2
func jump(nums []int) int {
	res := 0
	end := 0
	maxValue := 0
	for i := 0; i < len(nums)-1; i++ {
		maxValue = max(maxValue, i+nums[i])
		if i == end {
			end = maxValue
			res++
		}
	}
	return res
}

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

# 3
func jump(nums []int) int {
	dp := make([]int, len(nums))
	dp[0] = 0
	for i := 1; i < len(nums); i++ {
		dp[i] = i
		for j := 0; j < i; j++ {
			if nums[j]+j >= i {
				dp[i] = min(dp[i], dp[j]+1)
			}
		}
	}
	return dp[len(nums)-1]
}

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

# 4
func jump(nums []int) int {
	if len(nums) <= 1 {
		return 0
	}
	dp := make([]int, len(nums))
	for i := 1; i < len(nums); i++ {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0
	for i := 0; i < len(nums)-1; i++ {
		if i+nums[i] >= len(nums)-1 {
			return dp[i] + 1
		}
		for j := i + 1; j <= i+nums[i]; j++ {
			if j < len(nums) {
				dp[j] = min(dp[j], dp[i]+1)
			} else {
				break
			}
		}
	}
	return dp[len(nums)-1]
}

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

51.N皇后(3)

• 题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4皇后问题存在两个不同的解法。
提示：
    皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。
    当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。

• 解题思路

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

var res [][]string

func solveNQueens(n int) [][]string {
	res = make([][]string, 0)
	// 初始化棋盘
	arr := make([][]string, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]string, n)
		for j := 0; j < n; j++ {
			arr[i][j] = "."
		}
	}
	// 从第1行开始,上层是满足条件
	dfs(arr, 0)
	return res
}

func dfs(arr [][]string, row int) {
	if len(arr) == row {
		temp := make([]string, 0)
		for i := 0; i < len(arr); i++ {
			str := ""
			for j := 0; j < len(arr[i]); j++ {
				str = str + arr[i][j]
			}
			temp = append(temp, str)
		}
		res = append(res, temp)
		return
	}
	// 每列尝试
	for col := 0; col < len(arr[0]); col++ {
		if valid(arr, row, col) == false {
			continue
		}
		arr[row][col] = "Q"
		dfs(arr, row+1)
		arr[row][col] = "."
	}
}

func valid(arr [][]string, row, col int) bool {
	n := len(arr)
	// 当前列判断(竖着)
	for row := 0; row < n; row++ {
		if arr[row][col] == "Q" {
			return false
		}
	}
	// 左上角
	for row, col := row-1, col-1; row >= 0 && col >= 0; row, col = row-1, col-1 {
		if arr[row][col] == "Q" {
			return false
		}
	}
	// 右上角
	for row, col := row-1, col+1; row >= 0 && col < n; row, col = row-1, col+1 {
		if arr[row][col] == "Q" {
			return false
		}
	}
	return true
}

# 2
var res [][]string
var rows, left, right []bool

func solveNQueens(n int) [][]string {
	res = make([][]string, 0)
	rows, left, right = make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
	// 初始化棋盘
	arr := make([][]string, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]string, n)
		for j := 0; j < n; j++ {
			arr[i][j] = "."
		}
	}
	// 从第1行开始,上层是满足条件
	dfs(arr, 0)
	return res
}

func dfs(arr [][]string, row int) {
	n := len(arr)
	if len(arr) == row {
		temp := make([]string, 0)
		for i := 0; i < n; i++ {
			str := ""
			for j := 0; j < n; j++ {
				str = str + arr[i][j]
			}
			temp = append(temp, str)
		}
		res = append(res, temp)
		return
	}
	// 每列尝试
	for col := 0; col < n; col++ {
		if rows[col] == true || left[row-col+n-1] == true || right[row+col] == true {
			continue
		}
		rows[col], left[row-col+n-1], right[row+col] = true, true, true
		arr[row][col] = "Q"
		dfs(arr, row+1)
		arr[row][col] = "."
		rows[col], left[row-col+n-1], right[row+col] = false, false, false
	}
}

# 3
var res [][]string

func solveNQueens(n int) [][]string {
	res = make([][]string, 0)
	// 初始化棋盘
	arr := make([][]string, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]string, n)
		for j := 0; j < n; j++ {
			arr[i][j] = "."
		}
	}
	// 从第1行开始,上层是满足条件
	dfs(arr, 0, 0, 0, 0)
	return res
}

func dfs(arr [][]string, row int, rows, left, right int) {
	n := len(arr)
	if len(arr) == row {
		temp := make([]string, 0)
		for i := 0; i < n; i++ {
			str := ""
			for j := 0; j < n; j++ {
				str = str + arr[i][j]
			}
			temp = append(temp, str)
		}
		res = append(res, temp)
		return
	}
	// 每列尝试
	for col := 0; col < n; col++ {
		a := uint(col)
		b := uint(row - col + n - 1)
		c := uint(row + col)
		if ((rows>>a)&1) != 0 || ((left>>b)&1) != 0 || ((right>>c)&1) != 0 {
			continue
		}
		arr[row][col] = "Q"
		dfs(arr, row+1, rows^(1<<a), left^(1<<b), right^(1<<c))
		arr[row][col] = "."
	}
}

52.N皇后II(3)

• 题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
提示：皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。
    当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	回溯	O(n^n)	O(n^2)
02	回溯	O(n^n)	O(n^2)
03	回溯-位运算	O(n^n)	O(n)

var res int
var rows, left, right []bool

func totalNQueens(n int) int {
	res = 0
	rows, left, right = make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
	// 初始化棋盘
	arr := make([][]string, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]string, n)
		for j := 0; j < n; j++ {
			arr[i][j] = "."
		}
	}
	// 从第1行开始,上层是满足条件
	dfs(arr, 0)
	return res
}

func dfs(arr [][]string, row int) {
	n := len(arr)
	if len(arr) == row {
		res++
		return
	}
	// 每列尝试
	for col := 0; col < n; col++ {
		if rows[col] == true || left[row-col+n-1] == true || right[row+col] == true {
			continue
		}
		rows[col], left[row-col+n-1], right[row+col] = true, true, true
		arr[row][col] = "Q"
		dfs(arr, row+1)
		arr[row][col] = "."
		rows[col], left[row-col+n-1], right[row+col] = false, false, false
	}
}

# 2
var res int

func totalNQueens(n int) int {
	res = 0
	// 初始化棋盘
	arr := make([][]string, n)
	for i := 0; i < n; i++ {
		arr[i] = make([]string, n)
		for j := 0; j < n; j++ {
			arr[i][j] = "."
		}
	}
	// 从第1行开始,上层是满足条件
	dfs(arr, 0)
	return res
}

func dfs(arr [][]string, row int) {
	if len(arr) == row {
		res++
		return
	}
	// 每列尝试
	for col := 0; col < len(arr[0]); col++ {
		if valid(arr, row, col) == false {
			continue
		}
		arr[row][col] = "Q"
		dfs(arr, row+1)
		arr[row][col] = "."
	}
}

func valid(arr [][]string, row, col int) bool {
	n := len(arr)
	// 当前列判断(竖着)
	for row := 0; row < n; row++ {
		if arr[row][col] == "Q" {
			return false
		}
	}
	// 左上角
	for row, col := row-1, col-1; row >= 0 && col >= 0; row, col = row-1, col-1 {
		if arr[row][col] == "Q" {
			return false
		}
	}
	// 右上角
	for row, col := row-1, col+1; row >= 0 && col < n; row, col = row-1, col+1 {
		if arr[row][col] == "Q" {
			return false
		}
	}
	return true
}

# 3
var res int

func totalNQueens(n int) int {
	res = 0
	// 从第1行开始,上层是满足条件
	dfs(0, n, 0, 0, 0)
	return res
}

func dfs(row, n int, rows, left, right int) {
	if n == row {
		res++
		return
	}
	// 每列尝试
	for col := 0; col < n; col++ {
		a := uint(col)
		b := uint(row - col + n - 1)
		c := uint(row + col)
		if ((rows>>a)&1) != 0 || ((left>>b)&1) != 0 || ((right>>c)&1) != 0 {
			continue
		}
		dfs(row+1, n, rows^(1<<a), left^(1<<b), right^(1<<c))
	}
}

57.插入区间(3)

• 题目

给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1： 输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]
示例 2： 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。

• 解题思路

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

func insert(intervals [][]int, newInterval []int) [][]int {
	res := make([][]int, 0)
	if len(intervals) == 0 {
		res = append(res, newInterval)
		return res
	}
	i := 0
	for ; i < len(intervals) && intervals[i][1] < newInterval[0]; i++ {
		res = append(res, intervals[i])
	}
	for ; i < len(intervals) && intervals[i][0] <= newInterval[1]; i++ {
		newInterval[0] = min(newInterval[0], intervals[i][0])
		newInterval[1] = max(newInterval[1], intervals[i][1])
	}
	res = append(res, newInterval)
	for ; i < len(intervals); i++ {
		res = append(res, intervals[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
}

# 2
func insert(intervals [][]int, newInterval []int) [][]int {
	if len(intervals) == 0 {
		return [][]int{newInterval}
	}
	i := 0
	for ; i < len(intervals) && intervals[i][1] < newInterval[0]; i++ {
	}
	left := i
	i = len(intervals) - 1
	for ; i >= 0 && intervals[i][0] > newInterval[1]; i-- {
	}
	right := i
	if left > right {
		return append(intervals[:left], append([][]int{newInterval}, intervals[left:]...)...)
	}
	newInterval[0] = min(newInterval[0], intervals[left][0])
	newInterval[1] = max(newInterval[1], intervals[right][1])
	return append(intervals[:left], append([][]int{newInterval}, intervals[right+1:]...)...)
}

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

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

# 3
func insert(intervals [][]int, newInterval []int) [][]int {
	res := make([][]int, 0)
	intervals = append(intervals, newInterval)
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	res = append(res, intervals[0])
	for i := 1; i < len(intervals); i++ {
		arr := res[len(res)-1]
		if intervals[i][0] > arr[1] {
			res = append(res, intervals[i])
		} else if intervals[i][1] > arr[1] {
			res[len(res)-1][1] = intervals[i][1]
		}
	}
	return res
}

65.有效数字(1)

• 题目

验证给定的字符串是否可以解释为十进制数字。
例如:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。
这里给出一份可能存在于有效十进制数字中的字符列表：
    数字 0-9
    指数 - "e"
    正/负号 - "+"/"-"
    小数点 - "."
当然，在输入中，这些字符的上下文也很重要。

• 解题思路

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

func isNumber(s string) bool {
	s = strings.Trim(s, " ")
	if s == "" || len(s) == 0 || len(s) == 0 {
		return false
	}
	arr := []byte(s)
	i := 0
	numeric := scanInteger(&arr, &i)
	if i < len(arr) && arr[i] == '.' {
		i++
		numeric = scanUnsignedInteger(&arr, &i) || numeric
	}
	if i < len(arr) && (arr[i] == 'e' || arr[i] == 'E') {
		i++
		numeric = numeric && scanInteger(&arr, &i)
	}
	return numeric && len(arr) == i
}

func scanInteger(arr *[]byte, index *int) bool {
	if len(*arr) <= *index {
		return false
	}
	if (*arr)[*index] == '+' || (*arr)[*index] == '-' {
		*index++
	}
	return scanUnsignedInteger(arr, index)
}

func scanUnsignedInteger(arr *[]byte, index *int) bool {
	j := *index
	for *index < len(*arr) {
		if (*arr)[*index] < '0' || (*arr)[*index] > '9' {
			break
		}
		*index++
	}
	return j < *index
}

68.文本左右对齐(1)

• 题目

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，
且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。
必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。
如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
说明:单词是指由非空格字符组成的字符序列。
    每个单词的长度大于 0，小于等于 maxWidth。
    输入单词数组 words 至少包含一个单词。
示例:输入: words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
示例 2:输入: words = ["What","must","be","acknowledgment","shall","be"] maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:
输入:words = ["Science","is","what","we","understand","well","enough","to","explain",
         "to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

• 解题思路

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

func fullJustify(words []string, maxWidth int) []string {
	res := make([]string, 0)
	count := 0
	start := 0
	for i := 0; i < len(words); i++ {
		count = count + len(words[i])
		if count > maxWidth {
			temp := justify(words, start, i-1, maxWidth)
			res = append(res, temp)
			start = i
			if i == len(words)-1 {
				count = 0
				i--
			} else {
				count = len(words[i]) + 1
			}
		} else if i == len(words)-1 {
			temp := justify(words, start, i, maxWidth)
			res = append(res, temp)
		} else {
			count++
		}
	}
	return res
}

func justify(words []string, start, end int, maxWidth int) string {
	arr := make([]byte, maxWidth)
	for i := 0; i < len(arr); i++ {
		arr[i] = byte(' ')
	}
	index := 0
	// 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
	if start == end || end == len(words)-1 {
		for i := start; i <= end; i++ {
			copy(arr[index:], words[i])
			index = index + len(words[i]) + 1
		}
	} else {
		// 要求尽可能均匀分配单词间的空格数量。
		// 如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
		count := end - start + 1
		left := maxWidth - count + 1
		for i := start; i <= end; i++ {
			left = left - len(words[i])
		}
		space := left / (count - 1) // 均分
		mod := left % (count - 1)   // 多的放左边
		for i := start; i <= end; i++ {
			copy(arr[index:], words[i])
			index = index + len(words[i]) + 1 + space
			if mod > 0 {
				index++
				mod--
			}
		}
	}
	return string(arr)
}

72.编辑距离(2)

• 题目

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
    插入一个字符
    删除一个字符
    替换一个字符
示例 1：输入：word1 = "horse", word2 = "ros" 输出：3
解释：horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：输入：word1 = "intention", word2 = "execution" 输出：5
解释： intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

• 解题思路

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

func minDistance(word1 string, word2 string) int {
	n1 := len(word1)
	n2 := len(word2)
	// dp[i][j]代表 word1的i位置转换成word2的j位置需要最少步数
	dp := make([][]int, n1+1)
	for i := 0; i < n1+1; i++ {
		dp[i] = make([]int, n2+1)
	}
	dp[0][0] = 0
	// 到word2[0]需要全部删除，有多少删除多少
	for i := 1; i <= n1; i++ {
		dp[i][0] = i
	}
	// 到word2[i]需要添加，有多少添加多少
	for i := 1; i <= n2; i++ {
		dp[0][i] = i
	}
	for i := 1; i <= n1; i++ {
		for j := 1; j <= n2; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1] // 相同不需要操作
			} else {
				dp[i][j] = dp[i-1][j-1] + 1            // 替换
				dp[i][j] = min(dp[i][j], dp[i][j-1]+1) // 插入
				dp[i][j] = min(dp[i][j], dp[i-1][j]+1) // 删除
			}
		}
	}
	return dp[n1][n2]
}

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

# 2
var dp [][]int

func minDistance(word1 string, word2 string) int {
	dp = make([][]int, len(word1)+1)
	for i := 0; i < len(word1)+1; i++ {
		dp[i] = make([]int, len(word2)+1)
	}
	return helper(word1, word2, 0, 0)
}

func helper(word1, word2 string, i, j int) int {
	if dp[i][j] > 0 {
		return dp[i][j]
	}
	if i == len(word1) || j == len(word2) {
		return len(word1) - i + len(word2) - j
	}
	if word1[i] == word2[j] {
		return helper(word1, word2, i+1, j+1)
	}
	inserted := helper(word1, word2, i, j+1)
	deleted := helper(word1, word2, i+1, j)
	replaced := helper(word1, word2, i+1, j+1)
	dp[i][j] = min(inserted, min(deleted, replaced)) + 1
	return dp[i][j]
}

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

76.最小覆盖子串(2)

• 题目

给你一个字符串 S、一个字符串 T 。
请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：输入：S = "ADOBECODEBANC", T = "ABC" 输出："BANC"
提示：如果 S 中不存这样的子串，则返回空字符串 ""。
    如果 S 中存在这样的子串，我们保证它是唯一的答案。

• 解题思路

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

func minWindow(s string, t string) string {
	if len(s) < len(t) {
		return ""
	}
	window := make(map[byte]int)
	need := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	left, right := -1, -1
	minLength := math.MaxInt32
	for l, r := 0, 0; r < len(s); r++ {
		if r < len(s) && need[s[r]] > 0 {
			window[s[r]]++
		}
		// 找到，然后left往右移
		for check(need, window) == true && l <= r {
			if r-l+1 < minLength {
				minLength = r - l + 1
				left, right = l, r+1
			}
			if _, ok := need[s[l]]; ok {
				window[s[l]]--
			}
			l++
		}
	}
	if left == -1 {
		return ""
	}
	return s[left:right]
}

func check(need, window map[byte]int) bool {
	for k, v := range need {
		if window[k] < v {
			return false
		}
	}
	return true
}

# 2
func minWindow(s string, t string) string {
	if len(s) < len(t) {
		return ""
	}
	arr := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		arr[t[i]]++
	}
	l, count := 0, 0
	res := ""
	minLength := math.MaxInt32
	for r := 0; r < len(s); r++ {
		arr[s[r]]--
		if arr[s[r]] >= 0 {
			count++
		}
		// left往右边移动
		for count == len(t) {
			if minLength > r-l+1 {
				minLength = r - l + 1
				res = s[l : r+1]
			}
			arr[s[l]]++
			if arr[s[l]] > 0 {
				count--
			}
			l++
		}
	}
	return res
}

84.柱状图中最大的矩形(5)

• 题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:输入: [2,1,5,6,2,3]输出: 10

• 解题思路

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

func largestRectangleArea(heights []int) int {
	n := len(heights)
	res := 0
	for i := 0; i < n; i++ {
		height := heights[i]
		for j := i; j < n; j++ {
			width := j - i + 1
			height = min(height, heights[j])
			res = max(res, width*height)
		}
	}
	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 largestRectangleArea(heights []int) int {
	n := len(heights)
	res := 0
	for i := 0; i < n; i++ {
		height := heights[i]
		left, right := i, i
		for left > 0 && heights[left-1] >= height {
			left--
		}
		for right < n-1 && heights[right+1] >= height {
			right++
		}
		width := right - left + 1
		res = max(res, width*height)
	}
	return res
}

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

# 3
func largestRectangleArea(heights []int) int {
	n := len(heights)
	res := 0
	left := make([]int, n)
	right := make([]int, n)
	stack := make([]int, 0)
	for i := 0; i < n; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			left[i] = -1
		} else {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	stack = make([]int, 0)
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			right[i] = n
		} else {
			right[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	for i := 0; i < n; i++ {
		res = max(res, heights[i]*(right[i]-left[i]-1))
	}
	return res
}

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

# 4
func largestRectangleArea(heights []int) int {
	n := len(heights)
	res := 0
	left := make([]int, n)
	right := make([]int, n)
	stack := make([]int, 0)
	for i := 0; i < n; i++ {
		right[i] = n
	}
	for i := 0; i < n; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			right[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			left[i] = -1
		} else {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}

	for i := 0; i < n; i++ {
		res = max(res, heights[i]*(right[i]-left[i]-1))
	}
	return res
}

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

# 5
func largestRectangleArea(heights []int) int {
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	n := len(heights)
	res := 0
	stack := make([]int, 0)
	for i := 0; i < n; i++ {
		// 递增栈
		for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
			height := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			width := i - stack[len(stack)-1] - 1
			res = max(res, height*width)
		}
		stack = append(stack, i)
	}
	return res
}

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

85.最大矩形(2)

• 题目

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

• 解题思路

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

func maximalRectangle(matrix [][]byte) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	res := 0
	n, m := len(matrix), len(matrix[0])
	height := make([]int, m) // 高度
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if matrix[i][j] == '0' {
				height[j] = 0
			} else {
				height[j] = height[j] + 1
			}
		}
		res = max(res, getMaxArea(height))
	}
	return res
}

func getMaxArea(heights []int) int {
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	n := len(heights)
	res := 0
	stack := make([]int, 0)
	for i := 0; i < n; i++ {
		// 递增栈
		for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
			height := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			width := i - stack[len(stack)-1] - 1
			res = max(res, height*width)
		}
		stack = append(stack, i)
	}
	return res
}

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

# 2
func maximalRectangle(matrix [][]byte) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	res := 0
	n, m := len(matrix), len(matrix[0])
	left, right, height := make([]int, m), make([]int, m), make([]int, m)
	for i := 0; i < m; i++ {
		right[i] = m
	}
	for i := 0; i < n; i++ {
		curLeft, curRight := 0, m
		// 高度
		for j := 0; j < m; j++ {
			if matrix[i][j] == '1' {
				height[j]++
			} else {
				height[j] = 0
			}
		}
		// 左边
		for j := 0; j < m; j++ {
			if matrix[i][j] == '1' {
				left[j] = max(left[j], curLeft)
			} else {
				left[j] = 0
				curLeft = j + 1
			}
		}
		// 右边
		for j := m - 1; j >= 0; j-- {
			if matrix[i][j] == '1' {
				right[j] = min(right[j], curRight)
			} else {
				right[j] = m
				curRight = j
			}
		}
		for j := 0; j < m; j++ {
			res = max(res, height[j]*(right[j]-left[j]))
		}
	}
	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
}

87.扰乱字符串(2)

• 题目

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
下图是字符串 s1 = "great" 的一种可能的表示形式。
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat" 。
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
我们将 "rgeat” 称作 "great" 的一个扰乱字符串。
同样地，如果我们继续交换节点 "eat" 和 "at" 的子节点，将会产生另一个新的扰乱字符串 "rgtae" 。
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
我们将 "rgtae” 称作 "great" 的一个扰乱字符串。
给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
示例 1:输入: s1 = "great", s2 = "rgeat" 输出: true
示例 2:输入: s1 = "abcde", s2 = "caebd" 输出: false

• 解题思路

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

func isScramble(s1 string, s2 string) bool {
	n, m := len(s1), len(s2)
	if n != m {
		return false
	}
	// dp[i][j][l]:表示s1从i开始，s2从j开始长度为l的两个子字符串是扰乱
	dp := make([][][]bool, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([][]bool, n+1)
		for j := 0; j <= n; j++ {
			dp[i][j] = make([]bool, n+1)
		}
	}
	// 单个字符
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			dp[i][j][1] = s1[i] == s2[j]
		}
	}
	for k := 2; k <= n; k++ { // 枚举长度: 2-n
		for i := 0; i <= n-k; i++ { // s1起点
			for j := 0; j <= n-k; j++ { // s2起点
				dp[i][j][k] = false
				// 长度为w，分为两部分，其中最少是1
				for w := 1; w <= k-1; w++ {
					// 划分不交换：S1->T1, S2->T2
					// 划分交换： S1->T2, S2->T1
					if (dp[i][j][w] == true && dp[i+w][j+w][k-w] == true) ||
						(dp[i][j+k-w][w] == true && dp[i+w][j][k-w] == true) {
						dp[i][j][k] = true
					}
				}
			}
		}
	}
	return dp[0][0][n]
}

# 2
func isScramble(s1 string, s2 string) bool {
	return dfs([]byte(s1), []byte(s2))
}

func dfs(arr1, arr2 []byte) bool {
	if compare(arr1, arr2) == false {
		return false
	}
	if len(arr1) <= 2 {
		return (len(arr1) == 2 && ((arr1[0] == arr2[0] && arr1[1] == arr2[1]) ||
			(arr1[0] == arr2[1] && arr1[1] == arr2[0]))) ||
			(len(arr1) == 1 && arr1[0] == arr2[0])
	}
	for i := 1; i < len(arr1); i++ {
		leftA, rightA := arr1[:i], arr1[i:]
		leftB, rightB := arr2[:i], arr2[i:]
		LB, RB := arr2[len(arr1)-i:], arr2[:len(arr1)-i]
		if (dfs(leftA, leftB) && dfs(rightA, rightB)) || (dfs(leftA, LB) && dfs(rightA, RB)) {
			return true
		}
	}
	return false
}

func compare(arr1, arr2 []byte) bool {
	if len(arr1) != len(arr2) {
		return false
	}
	arrA := make([]byte, 26)
	arrB := make([]byte, 26)
	for i := 0; i < len(arr1); i++ {
		arrA[arr1[i]-'a']++
		arrB[arr2[i]-'a']++
	}
	for i := 0; i < len(arrA); i++ {
		if arrA[i] != arrB[i] {
			return false
		}
	}
	return true
}

97.交错字符串(3)

• 题目

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出：true
示例 2：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出：false

• 解题思路

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

func isInterleave(s1 string, s2 string, s3 string) bool {
	n, m, t := len(s1), len(s2), len(s3)
	if n+m != t {
		return false
	}
	// dp[i][j]表示s1的前i个元素和s2的前j个元素是否能交错组成s3的前i+j个元素
	dp := make([][]bool, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]bool, m+1)
	}
	dp[0][0] = true
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			total := i + j - 1
			if i > 0 && dp[i-1][j] == true && s1[i-1] == s3[total] {
				dp[i][j] = true
			}
			if j > 0 && dp[i][j-1] == true && s2[j-1] == s3[total] {
				dp[i][j] = true
			}
		}
	}
	return dp[n][m]
}

# 2
func isInterleave(s1 string, s2 string, s3 string) bool {
	n, m, t := len(s1), len(s2), len(s3)
	if n+m != t {
		return false
	}
	// dp[j]表示s1的前i个元素和s2的前j个元素是否能交错组成s3的前i+j个元素
	dp := make([]bool, m+1)
	dp[0] = true
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			total := i + j - 1
			if i > 0 {
				if dp[j] == true && s1[i-1] == s3[total] {
					dp[j] = true
				} else {
					dp[j] = false
				}
			}
			if j > 0 {
				if dp[j] == true || (dp[j-1] == true && s2[j-1] == s3[total]) {
					dp[j] = true
				} else {
					dp[j] = false
				}
			}
		}
	}
	return dp[m]
}

# 3
func isInterleave(s1 string, s2 string, s3 string) bool {
	if len(s1)+len(s2) != len(s3) {
		return false
	}
	return dfs(s1, s2, s3, 0, 0, 0)
}

func dfs(s1, s2, s3 string, i, j, k int) bool {
	if k == len(s3) && i == len(s1) && j == len(s2) {
		return true
	}
	if k >= len(s3) {
		return false
	}
	if i < len(s1) {
		if s1[i] == s3[k] {
			if dfs(s1, s2, s3, i+1, j, k+1) {
				return true
			}
		}
	}
	if j < len(s2) {
		if s2[j] == s3[k] {
			if dfs(s1, s2, s3, i, j+1, k+1) {
				return true
			}
		}
	}
	return false
}

99.恢复二叉搜索树(4)

• 题目

二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:输入: [1,3,null,null,2]
   1
  /
 3
  \
   2
输出: [3,1,null,null,2]
   3
  /
 1
  \
   2
示例 2:输入: [3,1,4,null,null,2]
  3
 / \
1   4
   /
  2
输出: [2,1,4,null,null,3]
  2
 / \
1   4
   /
  3
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

• 解题思路

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

var arr []*TreeNode

func recoverTree(root *TreeNode) {
	arr = make([]*TreeNode, 0)
	dfs(root)
	a, b := -1, -1
	for i := 0; i < len(arr)-1; i++ {
		if arr[i].Val > arr[i+1].Val {
			b = i + 1
			if a == -1 {
				a = i
			}
		}
	}
	arr[a].Val, arr[b].Val = arr[b].Val, arr[a].Val
}

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

# 2
var prev, first, second *TreeNode

func recoverTree(root *TreeNode) {
	prev, first, second = nil, nil, nil
	dfs(root)
	first.Val, second.Val = second.Val, first.Val
}

func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	dfs(root.Left)
	if prev != nil && prev.Val > root.Val {
		second = root
		if first == nil {
			first = prev
		} else {
			return
		}
	}
	prev = root
	dfs(root.Right)
}

# 3
func recoverTree(root *TreeNode) {
	var prev, first, second *TreeNode
	stack := make([]*TreeNode, 0)
	for len(stack) > 0 || root != nil {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if prev != nil && root.Val < prev.Val {
			second = root
			if first == nil {
				first = prev
			} else {
				break
			}
		}
		prev = root
		root = root.Right
	}
	first.Val, second.Val = second.Val, first.Val
}

# 4
func recoverTree(root *TreeNode) {
	var prev, temp, first, second *TreeNode
	for root != nil {
		temp = root.Left
		if temp != nil {
            // 当前root节点向左走一步，然后一直向右走至无法走为止
			for temp.Right != nil && temp.Right != root {
				temp = temp.Right
			}
			if temp.Right == nil {
				temp.Right = root
				root = root.Left
				continue
			} else {
				temp.Right = nil
			}
		}
		if prev != nil && prev.Val > root.Val {
			second = root
			if first == nil {
				first = prev
			}
		}
		prev = root
		root = root.Right
	}
	first.Val, second.Val = second.Val, first.Val
}