1. 两数相加(2)

给你两个非空的链表，表示两个非负的整数。
它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0开头。

示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

type ListNode struct {
	Val  int
	Next *ListNode
}

/*
模拟法
时间复杂度：O(max(m,n))
空间复杂度：O(1)
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var head *ListNode
	var tail *ListNode
	carry := 0
	for l1 != nil || l2 != nil {
		n1, n2 := 0, 0
		if l1 != nil {
			n1 = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			n2 = l2.Val
			l2 = l2.Next
		}
		sum := n1 + n2 + carry
		sum, carry = sum%10, sum/10
		if head == nil {
			head = &ListNode{Val: sum}
			tail = head
		} else {
			tail.Next = &ListNode{Val: sum}
			tail = tail.Next
		}
	}
	if carry > 0 {
		tail.Next = &ListNode{Val: carry}
	}
	return head
}

func main() {
	l1 := new(ListNode)
	l11 := new(ListNode)
	l111 := new(ListNode)
	l1.Val = 2
	l1.Next = l11
	l11.Val = 4
	l11.Next = l111
	l111.Val = 3
	l111.Next = nil

	l2 := new(ListNode)
	l22 := new(ListNode)
	l222 := new(ListNode)
	l2.Val = 5
	l2.Next = l22
	l22.Val = 4
	l22.Next = l222
	l222.Val = 6
	l222.Next = nil

	result := addTwoNumbers(l1, l2)
	fmt.Println(result)
}

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

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

/*
滑动窗口法
时间复杂度：O(n)
空间复杂度：O(字符集个数)
*/
func lengthOfLongestSubstring(s string) int {
	//哈希集合，用于去重
	m := map[byte]int{}
	//移动的指针
	rk, ans := -1, 0
	for i := 0; i < len(s); i++ {
		if i != 0 {
			//i每移动一次，把之前的一个删掉
			delete(m, s[i-1])
		}
		//若不重复，则不断向后查找
		for rk+1 < len(s) && m[s[rk+1]] == 0 {
			m[s[rk+1]]++
			rk++
		}
		//比较长度的最大值
		if ans < rk-i+1 {
			ans = rk - i + 1
		}
	}
	return ans
}

func main() {
	s := "abcabcbb"
	fmt.Println(lengthOfLongestSubstring(s))
}

3. 最长回文子串(5)

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"
*/

/*
暴力解法
时间复杂度：O(n³)
空间复杂度：O(1)

题解：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

/*
暴力解法
时间复杂度：O(n³)
空间复杂度：O(1)

题解：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
*/
func longestPalindrome1(s string) string {
	length := len(s)
	if length < 2 {
		return s
	}
	maxLen, begin := 1, 0
	for i := 0; i < length-1; i++ {
		for j := i + 1; j < length; j++ {
			if j-i+1 > maxLen && validPalindrome(s, i, j) {
				maxLen = j - i + 1
				begin = i
			}
		}
	}
	return s[begin : begin+maxLen]
}

func validPalindrome(s string, left, right int) bool {
	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

/*
中心扩散法
时间复杂度：O(n²)
空间复杂度：O(1)
*/
func longestPalindrome2(s string) string {
	length := len(s)
	if length < 2 {
		return s
	}
	maxLen, begin := 1, 0
	for i := 0; i < length-1; i++ {
		oddLen := expendAroundCenter(s, i, i)
		evenLen := expendAroundCenter(s, i, i+1)
		if max(oddLen, evenLen) > maxLen {
			maxLen = max(oddLen, evenLen)
			begin = i - (maxLen-1)/2
		}
	}
	return s[begin : begin+maxLen]
}

func expendAroundCenter(s string, left, right int) int {
	for left >= 0 && right < len(s) {
		if s[left] == s[right] {
			left--
			right++
		} else {
			break
		}
	}
	return right - left - 1
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

/*
动态规划
时间复杂度：O(n²)
空间复杂度：O(n²)
*/
func longestPalindrome3(s string) string {
	length := len(s)
	if length < 2 {
		return s
	}

	maxLen, begin := 1, 0
	dp := make([][]bool, length)
	for i := 0; i < length; i++ {
		dp[i] = make([]bool, length)
	}

	for i := 0; i < length; i++ {
		dp[i][i] = true
	}

	for L := 2; L <= length; L++ {
		for i := 0; i < length; i++ {
			j := L + i - 1
			if j >= length {
				break
			}

			if s[i] != s[j] {
				dp[i][j] = false
			} else {
				if j-i < 3 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			}

			if dp[i][j] && j-i+1 > maxLen {
				maxLen = j - i + 1
				begin = i
			}
		}
	}

	return s[begin : begin+maxLen]
}

func main() {
	s := "babad"
	fmt.Println(longestPalindrome1(s))
	fmt.Println(longestPalindrome2(s))
	fmt.Println(longestPalindrome3(s))
}

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

给定一个长度为 n 的整数数组height。有n条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。

示例 2：
输入：height = [1,1]
输出：1

/*
对撞指针法
时间复杂度：O(n)
空间复杂度：O(1)
*/
func maxArea(height []int) int {
	first, second := 0, len(height)-1
	area := 0
	h := 0
	for first < second {
		tempArea := 0
		width := second - first
		if height[first] < height[second] {
			h = height[first]
			first++
		} else {
			h = height[second]
			second--
		}
		tempArea = width * h
		if tempArea > area {
			area = tempArea
		}
	}
	return area
}

func main() {
	data := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
	fmt.Println(maxArea(data))
}

5. 三数之和(15)

给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

/*
排序+双指针
时间复杂度：O(n²)
空间复杂度：O(log(n))
*/
func threeSum(nums []int) [][]int {
	n := len(nums)
	sort.Ints(nums)
	ans := make([][]int, 0)

	// 枚举 a
	for first := 0; first < n; first++ {
		// 需要和上一次枚举的数不相同
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}
		// c 对应的指针初始指向数组的最右端
		third := n - 1
		target := -1 * nums[first]
		// 枚举 b
		for second := first + 1; second < n; second++ {
			// 需要和上一次枚举的数不相同
			if second > first+1 && nums[second] == nums[second-1] {
				continue
			}
			// 需要保证 b 的指针在 c 的指针的左侧
			for second < third && nums[second]+nums[third] > target {
				third--
			}
			// 如果指针重合，随着 b 后续的增加
			// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
			if second == third {
				break
			}
			if nums[second]+nums[third] == target {
				ans = append(ans, []int{nums[first], nums[second], nums[third]})
			}
		}
	}
	return ans
}

func main() {
	data := []int{-1, 0, 1, 2, -1, -4}
	fmt.Println(threeSum(data))
}

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

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]

/*
回溯法
时间复杂度：O(3^m × 4^n)
空间复杂度：O(m+n)
*/
var phoneMap map[string]string = map[string]string{
	"2": "abc",
	"3": "def",
	"4": "ghi",
	"5": "jkl",
	"6": "mno",
	"7": "pqrs",
	"8": "tuv",
	"9": "wxyz",
}

var combinations []string

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	combinations = []string{}
	backtrack(digits, 0, "")
	return combinations
}

func backtrack(digits string, index int, combination string) {
	if index == len(digits) {
		combinations = append(combinations, combination)
	} else {
		digit := string(digits[index])
		letters := phoneMap[digit]
		lettersCount := len(letters)
		for i := 0; i < lettersCount; i++ {
			backtrack(digits, index+1, combination+string(letters[i]))
		}
	}
}

func main() {
	digits := "234"
	fmt.Println(letterCombinations(digits))
}

7. 删除链表的倒数第n个结点(19)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

type ListNode struct {
	Val  int
	Next *ListNode
}

/*
写法一，无头结点
时间复杂度：O(n)
空间复杂度：O(1)
*/
func removeNthFromEnd1(head *ListNode, n int) *ListNode {
	var length int
	node := head
	for node != nil {
		node = node.Next
		length++
	}
	//如果删除的是第一个结点，单独判断
	if length == n {
		return head.Next
	}
	index := length - n + 1
	h := head
	c := h
	for i := 1; i <= index; i++ {
		if i != index-1 {
			h = h.Next
		} else {
			h.Next = h.Next.Next
		}
	}
	return c
}

/*
写法二，有头结点
时间复杂度：O(n)
空间复杂度：O(1)
*/
func getLength(head *ListNode) (length int) {
	for ; head != nil; head = head.Next {
		length++
	}
	return
}

func removeNthFromEnd2(head *ListNode, n int) *ListNode {
	length := getLength(head)
	dummy := &ListNode{0, head}
	cur := dummy
	for i := 0; i < length-n; i++ {
		cur = cur.Next
	}
	cur.Next = cur.Next.Next
	return dummy.Next
}

func main() {
	n1, n2, n3, n4, n5 := new(ListNode), new(ListNode), new(ListNode), new(ListNode), new(ListNode)
	n1.Val = 1
	n2.Val = 2
	n3.Val = 3
	n4.Val = 4
	n5.Val = 5
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	n4.Next = n5
	result := removeNthFromEnd1(n1, 2)
	for result != nil {
		fmt.Println(result.Val)
		result = result.Next
	}
}

8. 括号生成(22)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

/*
回溯法
*/
func generateParenthesis(n int) []string {
	var result []string
	var backtrace func(left, right int, str string)
	backtrace = func(leftRemain, rightRemain int, str string) {
		if len(str) == 2*n { //递归出口
			result = append(result, str)
			return
		}
		if leftRemain > 0 { //剪枝条件1
			backtrace(leftRemain-1, rightRemain, str+"(")
		}
		if leftRemain < rightRemain { //剪枝条件2
			backtrace(leftRemain, rightRemain-1, str+")")
		}
	}
	backtrace(n, n, "")
	return result
}

func main() {
	fmt.Println(generateParenthesis(3))
}

9. 下一个排列(31)

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
这样，排列 [2,3,1] 的下一个排列即为 [3,1,2]。特别的，最大的排列 [3,2,1] 的下一个排列为最小的排列 [1,2,3]。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，
那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]

/*
两遍扫描 法

思路：
首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。
如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足 a[i] < a[j]。这样「较大数」即为 a[j]。
交换 a[i] 与 a[j]，此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
*/
func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2
	//从后往前数，找到第一个非升序的数，nums[i] >= nums[i+1] 该方法支持序列中存在重复元素
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i >= 0 {
		j := n - 1
		//从后往前数，找到第一个非升序的数，nums[i]>=nums[j] 该方法支持序列中存在重复元素
		for j >= 0 && nums[i] >= nums[j] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	remain := nums[i+1:]
	for p, q := 0, len(remain); p < q/2; p++ {
		remain[p], remain[q-1-p] = remain[q-1-p], remain[p]
	}
}

func main() {
	//nums := []int{4, 5, 2, 6, 3, 1}
	nums := []int{1, 1}
	nextPermutation(nums)
	fmt.Println(nums)
}

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

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为[4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，
则返回它的下标，否则返回-1。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1

/*
暴力遍历
时间复杂度：O(n)
空间复杂度：O(1)
*/
func search1(nums []int, target int) int {
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			return i
		}
	}
	return -1
}

/*
二分查找
时间复杂度：O(log(n))
空间复杂度：O(1)
*/
func search2(nums []int, target int) int {
	length := len(nums)
	if length == 0 {
		return -1
	}
	if length == 1 {
		if nums[0] == target {
			return 0
		} else if nums[0] != target {
			return -1
		}
	}
	l, r := 0, length-1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] == target {
			return mid
		}
		if nums[0] <= nums[mid] {
			if nums[0] <= target && target < nums[mid] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[length-1] {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
	}
	return -1
}

func main() {
	nums := []int{4, 5, 6, 7, 0, 1, 2}
	fmt.Println(search1(nums, 0))
	fmt.Println(search2(nums, 0))
}

11. 排序数组中找元素的第一和末位位置(34)

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回[-1, -1]。

进阶：
你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

/*
暴力遍历
时间复杂度：O(n)
空间复杂度：O(1)
*/
func searchRange1(nums []int, target int) []int {
	mapFirst := make(map[int]int)
	mapEnd := make(map[int]int)
	mapFirst[target], mapEnd[target] = -1, -1
	for i := 0; i < len(nums); i++ {
		if nums[i] == target && mapFirst[target] == -1 {
			mapFirst[target] = i
		}
		if nums[i] == target {
			mapEnd[target] = i
		}
		if i < len(nums)-1 && nums[i] == target && nums[i+1] != target {
			break
		}
	}
	return []int{mapFirst[target], mapEnd[target]}
}

/*
二分查找
时间复杂度：O(log(n))
空间复杂度：O(1)
*/
func searchRange2(nums []int, target int) []int {
	//sort.SearchInts 查找第一个找到的元素的下标(从0开始计数)，如果没有找到，则返回target可以插入的位置下标
	leftmost := sort.SearchInts(nums, target)
	if leftmost == len(nums) || nums[leftmost] != target {
		return []int{-1, -1}
	}
	rightmost := sort.SearchInts(nums, target+1) - 1
	return []int{leftmost, rightmost}
}

func main() {
	nums := []int{5, 7, 7, 8, 8, 10}
	fmt.Println(searchRange1(nums, 8))
	fmt.Println(searchRange2(nums, 8))
}

12. 组合总和(39)

给你一个 无重复元素 的整数数组candidates 和一个目标整数target，
找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为target 的不同组合数少于 150 个。

示例1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

/*
搜索回溯，无剪枝
时间复杂度：O(S)
空间复杂度：O(target)
*/
func combinationSum1(candidates []int, target int) (ans [][]int) {
	comb := []int{}
	var dfs func(target, idx int)
	dfs = func(target, idx int) {
		if idx == len(candidates) {
			return
		}
		if target == 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		// 直接跳过
		dfs(target, idx+1)
		// 选择当前数
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return
}

func combinationSum2(candidates []int, target int) [][]int {
	var res [][]int
	var dfs func(start int, temp []int, sum int)
	dfs = func(start int, temp []int, sum int) {
		if sum >= target {
			if sum == target {
				newTemp := make([]int, len(temp))
				copy(newTemp, temp)
				res = append(res, newTemp)
			}
			return
		}
		for i := start; i < len(candidates); i++ {
			temp = append(temp, candidates[i])
			dfs(i, temp, sum+candidates[i])
			temp = temp[:len(temp)-1]
		}
	}
	dfs(0, []int{}, 0)
	return res
}

func main() {
	candidates := []int{2, 3, 6, 7}
	fmt.Println(combinationSum1(candidates, 7))
	fmt.Println(combinationSum2(candidates, 7))
}

13. 全排列(46)

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

/*
回溯算法 =（递归+纯暴力搜索）因为：有的能用回溯做出来就不错了
特点：抽象
解决问题：组合、切割、子集、排列、棋盘（N皇后）
解题方法：动手画图（切忌纯想象），一般回溯问题都可以变形为n叉树形结构

解题模板：
func {
	if 终止条件 {
		收集结果
		return
	}
	for 元素集合 {
		处理结点
		递归
		回溯
	}
	正常return
}

学习视频地址：https://www.bilibili.com/video/BV1cy4y167mM/
*/
func permute(nums []int) [][]int {
	var ans [][]int
	var backTrack func(nums []int, length int, path []int)
	backTrack = func(nums []int, length int, path []int) {
		if len(nums) == 0 {
			//重新起一个地址存放，防止path上的值被覆盖
			p := make([]int, len(path))
			copy(p, path) //path -> p
			ans = append(ans, p)
		}
		for i := 0; i < length; i++ {
			cur := nums[i]

			path = append(path, cur)
			nums = append(nums[:i], nums[i+1:]...) //把位置i处的元素去除

			backTrack(nums, len(nums), path)

			//回溯之前的操作
			nums = append(nums[:i], append([]int{cur}, nums[i:]...)...)
			path = path[:len(path)-1]
		}
	}
	backTrack(nums, len(nums), []int{})
	return ans
}

func main() {
	nums := []int{5, 4, 6, 2}
	fmt.Println(permute(nums))
}

14. 旋转图像(48)

给定一个 n×n 的二维矩阵matrix 表示一个图像。请你将图像顺时针旋转 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]]

func rotate(matrix [][]int) [][]int {
	if len(matrix) == 0 {
		return nil
	}
	xlen := len(matrix[0])
	ylen := len(matrix)

	var result [][]int
	for i := 0; i <= xlen-1; i++ {
		var tempArr []int
		for j := ylen - 1; j >= 0; j-- {
			tempArr = append(tempArr, matrix[j][i])
		}
		result = append(result, tempArr)
	}
	for i := 0; i < ylen; i++ {
		for j := 0; j < xlen; j++ {
			matrix[i][j] = result[i][j]
		}
	}
	return result
}

func main() {
	/*matrix := [][]int{
		{5, 1, 9, 11},
		{2, 4, 8, 10},
		{13, 3, 6, 7},
		{15, 14, 12, 16},
	}*/
	matrix := [][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	}
	//matrix := [][]int{}
	rotate(matrix)
}

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

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

/*
排序法
排序后的作为key，对应的字符串作为value数组
*/
func groupAnagrams(strs []string) [][]string {
	mp := map[string][]string{}
	for _, str := range strs {
		sbyte := []byte(str)
		sort.Slice(sbyte, func(i, j int) bool {
			return sbyte[i] < sbyte[j]
		})
		s := string(sbyte)
		mp[s] = append(mp[s], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

func main() {
	strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	fmt.Println(groupAnagrams(strs))
}

16. 跳跃游戏(55)

给定一个非负整数数组nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

/*
贪心
时间复杂度：O(n)
空间复杂度：O(1)
*/
func canJump(nums []int) bool {
	var maxNum func(i, j int) int
	maxNum = func(i, j int) int {
		if i > j {
			return i
		} else {
			return j
		}
	}

	n := len(nums)
	rightmost := 0
	for i := 0; i < n; i++ {
		if i <= rightmost {
			rightmost = maxNum(i+nums[i], rightmost)
			if rightmost >= n-1 {
				return true
			}
		}
	}

	return false
}

func main() {
	nums := []int{2, 3, 1, 1, 4}
	fmt.Println(canJump(nums))
}

17. 合并区间(56)

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

/*
排序
时间复杂度：O(nlog(n))
空间复杂度：O(log(n))
*/
func merge(intervals [][]int) [][]int {
	var maxNum func(i, j int) int
	maxNum = func(i, j int) int {
		if i > j {
			return i
		} else {
			return j
		}
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	result := make([][]int, 0, len(intervals))
	for i := 0; i < len(intervals); i++ {
		L, R := intervals[i][0], intervals[i][1]
		if len(result) == 0 || result[len(result)-1][1] < L {
			result = append(result, []int{L, R})
		} else {
			result[len(result)-1][1] = maxNum(result[len(result)-1][1], R)
		}
	}
	return result
}

func main() {
	intervals := [][]int{{1, 4}, {0, 3}, {3, 5}, {2, 9}, {2, 7}}
	fmt.Println(merge(intervals))
}

18. 不同路径(62)

一个机器人位于一个 m x n （m行 x n列）网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
注意：1 <= m, n <= 100

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：
输入：m = 7, n = 3
输出：28

示例 4：
输入：m = 3, n = 3
输出：6

/*
动态规划
转移方程：f(i,j)=f(i−1,j)+f(i,j−1)
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
func uniquePaths(m int, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

func main() {
	fmt.Println(uniquePaths(3, 7))
}

19. 最小路径和(64)

给定一个包含非负整数的 mxn网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
注意：1 <= m, n <= 200

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

/*
动态规划
转移方程：
当 i>0 且 j=0 时，dp[i][0]=dp[i-1][0]+grid[i][0]
当 i=0 且 j>0 时，dp[0][j]=dp[0][j-1]+grid[0][j]
当 i>0 且 j>0 时，dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]

时间复杂度：O(mn)
空间复杂度：O(mn)
*/

func minPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	raw, column := len(grid), len(grid[0])
	dp := make([][]int, raw)
	for i := 0; i < raw; i++ {
		dp[i] = make([]int, column)
	}
	dp[0][0] = grid[0][0]
	for i := 1; i < raw; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for i := 1; i < column; i++ {
		dp[0][i] = dp[0][i-1] + grid[0][i]
	}
	for i := 1; i < raw; i++ {
		for j := 1; j < column; j++ {
			dp[i][j] = int(math.Min(float64(dp[i-1][j]), float64(dp[i][j-1]))) + grid[i][j]
		}
	}
	return dp[raw-1][column-1]
}

func main() {
	fmt.Println(minPathSum([][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}))
}

20. 颜色分类(75)

给定一个包含红色、白色和蓝色、共n 个元素的数组nums，原地对它们进行排序，
使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]

/*
单指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func sortColors1(nums []int) {
	var swap func(nums []int, target int) (targetIndex int)
	swap = func(nums []int, target int) (targetIndex int) {
		for i, v := range nums {
			if v == target {
				nums[i], nums[targetIndex] = nums[targetIndex], nums[i]
				targetIndex++
			}
		}
		return
	}

	index := swap(nums, 0)
	swap(nums[index:], 1)
}

/*
双指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func sortColors2(nums []int) {
	p0, p1 := 0, 0
	for i, v := range nums {
		if v == 0 {
			nums[p0], nums[i] = nums[i], nums[p0]
			if p0 < p1 {
				nums[p1], nums[i] = nums[i], nums[p1]
			}
			p0++
			p1++
		} else if v == 1 {
			nums[p1], nums[i] = nums[i], nums[p1]
			p1++
		}
	}
}

/*
双指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func sortColors3(nums []int) {
	p0, p2 := 0, len(nums)-1
	for i := 0; i <= p2; i++ {
		for ; i <= p2 && nums[i] == 2; p2-- {
			nums[p2], nums[i] = nums[i], nums[p2]
		}
		if nums[i] == 0 {
			nums[p0], nums[i] = nums[i], nums[p0]
			p0++
		}
	}
}

func main() {
	nums := []int{2, 0, 2, 1, 1, 0}
	//sortColors1(nums)
	//sortColors2(nums)
	sortColors3(nums)
	fmt.Println(nums)
}

21. 子集(78)

给你一个整数数组nums ，数组中的元素互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

/*
迭代法实现子集枚举
时间复杂度：O(n*(2^n))
空间复杂度：O(n)
*/
func subsets1(nums []int) [][]int {
	var ans [][]int
	n := len(nums)
	for i := 0; i < (1 << n); i++ {
		var set []int
		for j := 0; j < n; j++ {
			if ((i >> j) & 1) > 0 {
				set = append(set, nums[j])
			}
		}
		ans = append(ans, append([]int(nil), set...))
	}
	return ans
}

/*
递归法实现子集枚举
时间复杂度：O(n*(2^n))
空间复杂度：O(n)
解析：https://leetcode-cn.com/problems/subsets/solution/shou-hua-tu-jie-zi-ji-hui-su-fa-xiang-jie-wei-yun-/
*/
func subsets2(nums []int) [][]int {
	var ans [][]int
	var set []int
	n := len(nums)
	var dfs func(cur int)
	dfs = func(cur int) {
		if cur == n {
			ans = append(ans, append([]int(nil), set...))
			return
		}
		set = append(set, nums[cur])
		dfs(cur + 1)
		set = set[:len(set)-1] //回溯
		dfs(cur + 1)
	}
	dfs(0)
	return ans
}

func main() {
	arr := []int{1, 2, 3}
	fmt.Println(subsets1(arr))
	fmt.Println(subsets2(arr))
}

22. 单词搜索(79)

给定一个m x n 二维字符网格board 和一个字符串单词word 。
如果word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，
其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCCED'
输出：true

示例 2：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'SEE'
输出：true

示例 3：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCB'
输出：false

/*
回溯
时间复杂度：上界为 O(M*N*(3^L))，其中 M,N 为网格的长度与宽度，L 为字符串 word 的长度
空间复杂度：O(M*N)
*/
func exist(board [][]byte, word string) bool {
	type pair struct {
		x, y int
	}
	directions := []pair{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

	h, w := len(board), len(board[0])

	vis := make([][]bool, h)
	for i := 0; i < h; i++ {
		vis[i] = make([]bool, w)
	}

	var check func(i, j, k int) bool
	check = func(i, j, k int) bool {
		if board[i][j] != word[k] {
			return false
		}
		if k == len(word)-1 {
			return true
		}
		vis[i][j] = true
		for m := 0; m < len(directions); m++ {
			newI, newJ := i+directions[m].x, j+directions[m].y
			if (newI >= 0 && newI < h) && (newJ >= 0 && newJ < w) && !vis[newI][newJ] {
				if check(newI, newJ, k+1) {
					return true
				}
			}
		}
		vis[i][j] = false
		return false
	}

	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			if check(i, j, 0) {
				return true
			}
		}
	}
	return false
}

func main() {
	board := [][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}
	word := "ABCCED"
	fmt.Println(exist(board, word))
}

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

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：
输入：n = 3
输出：5

示例 2：
输入：n = 1
输出：1

解析：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/

/*
动态规划
转移方程：F(i,n)=G(i−1)⋅G(n−i)
G(i−1)表示根结点左边
G(n−i)表示根结点右边
边界情况：G(0)=1,G(1)=1
时间复杂度 : O(n^2)
空间复杂度 : O(n)
*/
func numTrees1(n int) int {
	G := make([]int, n+1)
	G[0], G[1] = 1, 1
	for i := 2; i <= n; i++ {
		for j := 1; j <= i; j++ {
			G[i] += G[j-1] * G[i-j]
		}
	}
	return G[n]
}

/*
数学公式法
时间复杂度 : O(n)
空间复杂度 : O(1)
*/
func numTrees2(n int) int {
	C := 1
	for i := 0; i < n; i++ {
		C = C * 2 * (2*i + 1) / (i + 2)
	}
	return C
}

func main() {
	fmt.Println(numTrees1(3))
	fmt.Println(numTrees2(3))
}

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

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]  //按层次遍历生成二叉树
输出：true

示例 2：
输入：root = [5,1,4,null,null,3,6]  //按层次遍历生成二叉树
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
递归
时间复杂度：O(n)
空间复杂度：O(n)
*/
func isValidBST1(root *TreeNode) bool {
	var helper func(root *TreeNode, lower, upper int) bool
	helper = func(root *TreeNode, lower, upper int) bool {
		if root == nil {
			return true
		}
		if root.Val <= lower || root.Val >= upper {
			return false
		}
		return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
	}
	return helper(root, math.MinInt64, math.MaxInt64)
}

/*
中序遍历
时间复杂度：O(n)
空间复杂度：O(n)
*/
func isValidBST2(root *TreeNode) bool {
	var stack []*TreeNode
	inorder := math.MinInt64
	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 root.Val <= inorder {
			return false
		}
		inorder = root.Val
		root = root.Right
	}
	return true
}

func main() {
	n1, n2, n3, n4, n5 := new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode)
	n1.Val, n2.Val, n3.Val, n4.Val, n5.Val = 5, 1, 4, 3, 6
	n1.Left, n1.Right = n2, n3
	n3.Left, n3.Right = n4, n5
	fmt.Println(isValidBST1(n1))
	fmt.Println(isValidBST2(n1))
}

25. 二叉树的层次遍历(102)

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
广度优先搜索
时间复杂度：O(n)
空间复杂度：O(n)
*/
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var ret [][]int
	q := []*TreeNode{root} //根结点赋值
	var i int
	for len(q) > 0 {
		ret = append(ret, []int{}) //给ret增加一个初始化
		var p []*TreeNode
		for j := 0; j < len(q); j++ {
			node := q[j]
			ret[i] = append(ret[i], node.Val)
			if node.Left != nil {
				p = append(p, node.Left)
			}
			if node.Right != nil {
				p = append(p, node.Right)
			}
		}
		q = p //把下一层结点赋值给q
		i++   //层数加一
	}

	return ret
}

func main() {
	n1, n2, n3, n4, n5 := new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode), new(TreeNode)
	n1.Val, n2.Val, n3.Val, n4.Val, n5.Val = 3, 9, 20, 15, 7
	n1.Left, n1.Right = n2, n3
	n3.Left, n3.Right = n4, n5
	fmt.Println(levelOrder(n1))
}

26. 从前序与中序遍历序列构造二叉树(105)

给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历，
inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
preorder 和 inorder 均 无重复 元素.

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
递归
时间复杂度：O(n)
空间复杂度：O(n)
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{preorder[0], nil, nil}
	i := 0
	for ; i < len(inorder); i++ {
		if inorder[i] == preorder[0] {
			break
		}
	}
	root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])
	root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
	return root
}

func main() {
	preorder := []int{3,9,20,15,7}
	inorder := []int{9,3,15,20,7}
	fmt.Println(buildTree(preorder, inorder))
}