剑指offer

参考资料

• leetcode专栏链接 https://leetcode.cn/problemset/lcof/

• http://zhedahht.blog.163.com/

• 《剑指Offer》第二版源代码 C++ https://github.com/zhedahht/CodingInterviewChinese2

面试题03.数组中重复的数字(6)

• 题目

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
示例 1：输入：[2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 
限制：
2 <= n <= 100000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	排序遍历	O(nlog(n))	O(1)
03	暴力法	O(n^2)	O(1)
04	遍历-置换	O(n)	O(1)
05	遍历-置反	O(n)	O(1)
06	遍历-置换(书上方法)	O(n)	O(1)

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

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

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

#
func findRepeatNumber(nums []int) int {
	for key, value := range nums {
		if key == value {
			continue
		}
		if value == nums[value] {
			return nums[value]
		}
		nums[key], nums[value] = nums[value], nums[key]
	}
	return -1
}

#
func findRepeatNumber(nums []int) int {
	countZero := 0
	for _, value := range nums {
		if value == 0 {
			if countZero > 0 {
				return 0
			}
			countZero++
			continue
		}
		if value < 0 {
			value = -value
		}
		if nums[value] < 0 {
			return value
		}
		nums[value] = -1 * nums[value]
	}
	return -1
}

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

面试题04.二维数组中的查找(6)

• 题目

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
注意：本题与主站 240 题相同：https://leetcode.cn/problems/search-a-2d-matrix-ii/

• 解题思路

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 findNumberIn2DArray(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 findNumberIn2DArray(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 findNumberIn2DArray(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 findNumberIn2DArray(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 findNumberIn2DArray(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 findNumberIn2DArray(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
}

面试题05.替换空格(2)

• 题目

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：输入：s = "We are happy." 输出："We%20are%20happy."
限制：0 <= s 的长度 <= 10000

• 解题思路

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

func replaceSpace(s string) string {
	return strings.Replace(s," ","%20",-1)
	// return strings.ReplaceAll(s, " ", "%20")
}


#
func replaceSpace(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			res = res + "%20"
		} else {
			res = res + string(s[i])
		}
	}
	return res
}

面试题06.从尾到头打印链表(5)

• 题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：输入：head = [1,3,2] 输出：[2,3,1]
限制：0 <= 链表长度 <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	反转数组	O(n)	O(n)
02	递归(书上方法)	O(n)	O(n)
03	反转链表	O(n)	O(n)
04	栈辅助(书上方法)	O(n)	O(n)
05	统计+遍历	O(n)	O(n)

func reversePrint(head *ListNode) []int {
	res := make([]int, 0)
	for head != nil {
		res = append(res, head.Val)
		head = head.Next
	}
	i := 0
	for i < len(res)/2 {
		res[i], res[len(res)-1-i] = res[len(res)-1-i], res[i]
		i++
	}
	return res
}

# 2
func reversePrint(head *ListNode) []int {
	if head == nil {
		return []int{}
	}
	res := reversePrint(head.Next)
	res = append(res, head.Val)
	return res
}

# 3
func reversePrint(head *ListNode) []int {
	res := make([]int, 0)
	if head == nil {
		return res
	}
	var newHead *ListNode
	for head != nil {
		next := head.Next
		head.Next = newHead
		newHead = head
		head = next
	}

	for newHead != nil {
		res = append(res, newHead.Val)
		newHead = newHead.Next
	}
	return res
}

# 4
func reversePrint(head *ListNode) []int {
	res := make([]int,0)
	if head == nil{
		return res
	}
	stack := make([]*ListNode, 0)
	for head != nil{
		stack = append(stack, head)
		head = head.Next
	}
	for len(stack) > 0{
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, node.Val)
	}
	return res
}

# 5
func reversePrint(head *ListNode) []int {
	cur := head
	count := 0
	for head != nil {
		count++
		head = head.Next
	}
	res := make([]int, count)
	for cur != nil {
		res[count-1] = cur.Val
		count--
		cur = cur.Next
	}
	return res
}

面试题07.重建二叉树(3)

• 题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7
限制：0 <= 节点个数 <= 5000
注意：本题与主站 105 题重复：
https://leetcode.cn/problems/
construct-binary-tree-from-preorder-and-inorder-traversal/

• 解题思路

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

func buildTree(preorder []int, inorder []int) *TreeNode {
	for k := range inorder {
		if inorder[k] == preorder[0] {
			return &TreeNode{
				Val:   preorder[0],
				Left:  buildTree(preorder[1:k+1], inorder[0:k]),
				Right: buildTree(preorder[k+1:], inorder[k+1:]),
			}
		}
	}
	return nil
}

#

func buildTree(preorder []int, inorder []int) *TreeNode {
	if preorder == nil || len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{
		Val: preorder[0],
	}
	length := len(preorder)
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	index := 0
	for i := 1; i < length; i++ {
		value := preorder[i]
		node := stack[len(stack)-1]
		if node.Val != inorder[index] {
			node.Left = &TreeNode{Val: value}
			stack = append(stack, node.Left)
		} else {
			for len(stack) > 0 && stack[len(stack)-1].Val == inorder[index] {
				node = stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				index++
			}
			node.Right = &TreeNode{Val: value}
			stack = append(stack, node.Right)
		}
	}
	return root
}

#
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	return helper(preorder, inorder)
}

func helper(preorder []int, inorder []int) *TreeNode {
	var root *TreeNode
	for k := range inorder {
		if inorder[k] == preorder[0] {
			root = &TreeNode{Val: preorder[0]}
			root.Left = helper(preorder[1:k+1], inorder[0:k])
			root.Right = helper(preorder[k+1:], inorder[k+1:])
		}
	}
	return root
}

面试题09.用两个栈实现队列(1)

• 题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：输入： ["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
    1 <= values <= 10000
    最多会对 appendTail、deleteHead 进行 10000 次调用

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	栈模拟队列	O(n)	O(n)

type stack []int

func (s *stack) Push(value int) {
	*s = append(*s, value)
}
func (s *stack) Pop() int {
	value := (*s)[len(*s)-1]
	*s = (*s)[:len(*s)-1]
	return value
}

type CQueue struct {
	tail stack
	head stack
}

func Constructor() CQueue {
	return CQueue{}
}

// 1.入队，tail栈保存
// 2.出队, head不为空，出head；head为空，tail出到head里，最后出head
func (this *CQueue) AppendTail(value int) {
	this.tail.Push(value)
}

func (this *CQueue) DeleteHead() int {
	if len(this.head) != 0 {
		return this.head.Pop()
	} else if len(this.tail) != 0 {
		for len(this.tail) > 0 {
			this.head.Push(this.tail.Pop())
		}
		return this.head.Pop()
	}
	return -1
}

面试题10- I.斐波那契数列(5)

• 题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：输入：n = 2输出：1
示例 2：输入：n = 5输出：5
提示：
    0 <= n <= 100
注意：本题与主站 509 题相同：https://leetcode.cn/problems/fibonacci-number/

• 解题思路

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

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

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

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

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

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

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

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

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


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

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

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

# 5
var m = make(map[int]int)

func fib(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	if m[n] > 0 {
		return m[n]
	}
	m[n] = (fib(n-1) + fib(n-2)) % 1000000007
	return m[n]
}

面试题10-II.青蛙跳台阶问题(3)

• 题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：输入：n = 2输出：2
示例 2：输入：n = 7输出：21
提示：
    0 <= n <= 100
注意：本题与主站 70 题相同：https://leetcode.cn/problems/climbing-stairs/

• 解题思路

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

func numWays(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]) % 1000000007
	}
	return dp[n]
}

#
func numWays(n int) int {
	if n <= 1 {
		return 1
	}
	first := 1
	second := 2
	for i := 3; i <= n; i++ {
		third := (first + second) % 1000000007
		first = second
		second = third
	}
	return second
}

# 3
var m = make(map[int]int)

func numWays(n int) int {
	if n <= 1 {
		return 1
	}
	if m[n] > 0 {
		return m[n]
	} else {
		m[n] = (numWays(n-1) + numWays(n-2)) % 1000000007
	}
	return m[n]
}

面试题11.旋转数组的最小数字(4)

• 题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  

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

示例 2：输入：[2,2,2,0,1]输出：0
注意：本题与主站 154 题相同：
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/

• 解题思路

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

func minArray(numbers []int) int {
	left := 0
	right := len(numbers) - 1
	for left < right {
		if numbers[left] < numbers[right] {
			return numbers[left]
		}
		mid := left + (right-left)/2
		if numbers[mid] > numbers[left] {
			left = mid + 1
		} else if numbers[mid] < numbers[left] {
			right = mid
		} else {
			left++
		}
	}
	return numbers[left]
}

#
func minArray(numbers []int) int {
	sort.Ints(numbers)
	return numbers[0]
}

#
func minArray(numbers []int) int {
	for i := 1; i < len(numbers); i++ {
		if numbers[i] < numbers[i-1] {
			return numbers[i]
		}
	}
	return numbers[0]
}

#
func minArray(numbers []int) int {
	left := 0
	right := len(numbers) - 1
	mid := left
	for numbers[left] >= numbers[right] {
		if right-left == 1 {
			mid = right
			break
		}
		mid = (left + right) / 2
		if numbers[left] == numbers[right] && numbers[mid] == numbers[left] {
			return minInorder(numbers, left, right)
		}
		if numbers[mid] >= numbers[left] {
			left = mid
		} else if numbers[mid] <= numbers[right] {
			right = mid
		}
	}
	return numbers[mid]
}

func minInorder(numbers []int, left, right int) int {
	result := numbers[left]
	for i := left + 1; i <= right; i++ {
		if result > numbers[i] {
			result = numbers[i]
		}
	}
	return result
}

面试题12.矩阵中的路径(2)

• 题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。
如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，
路径不能再次进入这个格子。
示例 1：输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], 
word = "ABCCED"
输出：true
示例 2：输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false
提示：
    1 <= board.length <= 200
    1 <= board[i].length <= 200
注意：本题与主站 79 题相同：https://leetcode.cn/problems/word-search/

• 解题思路

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
}

面试题13.机器人的运动范围(3)

• 题目

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
也不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：输入：m = 2, n = 3, k = 1 输出：3
示例 2：输入：m = 3, n = 1, k = 0 输出：1
提示：
    1 <= n,m <= 100
    0 <= k <= 20

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	深度优先搜索(书上方法)	O(n^2)	O(n^2)
02	暴力法	O(n^2)	O(n^2)
03	广度优先搜索	O(n^2)	O(n^2)

func movingCount(m int, n int, k int) int {
	if k < 0 || m <= 0 || n <= 0 {
		return 0
	}
	visited := make([]bool, m*n)
	res := dfs(m, n, k, visited, 0, 0)
	return res
}

func dfs(m, n, k int, visited []bool, x, y int) int {
	res := 0
	if check(m, n, k, visited, x, y) {
		visited[x*n+y] = true
		res = 1 + dfs(m, n, k, visited, x+1, y) +
			dfs(m, n, k, visited, x-1, y) +
			dfs(m, n, k, visited, x, y+1) +
			dfs(m, n, k, visited, x, y-1)
	}
	return res
}

func check(m, n, k int, visited []bool, x, y int) bool {
	if x >= 0 && x < m && y >= 0 && y < n &&
		getDigiSum(x)+getDigiSum(y) <= k && visited[x*n+y] == false {
		return true
	}
	return false
}

func getDigiSum(num int) int {
	sum := 0
	for num > 0 {
		sum = sum + num%10
		num = num / 10
	}
	return sum
}

#
func movingCount(m int, n int, k int) int {
	if k < 0 || m <= 0 || n <= 0 {
		return 0
	}
	res := 1
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	visited[0][0] = true
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if (i-1 >= 0 && visited[i-1][j] == true) || (j-1 >= 0 && visited[i][j-1] == true) {
				value := getDigiSum(i) + getDigiSum(j)
				if value <= k {
					res++
					visited[i][j] = true
				}
			}
		}
	}
	return res
}

func getDigiSum(num int) int {
	sum := 0
	for num > 0 {
		sum = sum + num%10
		num = num / 10
	}
	return sum
}

#
func movingCount(m int, n int, k int) int {
	if k < 0 || m <= 0 || n <= 0 {
		return 0
	}
	res := 0
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	visited[0][0] = true
	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		x := node[0]
		y := node[1]
		if getDigiSum(x)+getDigiSum(y) <= k {
			res++
		}
		if x+1 < m && getDigiSum(x+1)+getDigiSum(y) <= k && visited[x+1][y] == false {
			queue = append(queue, [2]int{x + 1, y})
			visited[x+1][y] = true
		}
		if x-1 >= 0 && getDigiSum(x-1)+getDigiSum(y) <= k && visited[x-1][y] == false {
			queue = append(queue, [2]int{x - 1, y})
			visited[x-1][y] = true
		}
		if y+1 < n && getDigiSum(x)+getDigiSum(y+1) <= k && visited[x][y+1] == false {
			queue = append(queue, [2]int{x, y + 1})
			visited[x][y+1] = true
		}
		if y-1 >= 0 && getDigiSum(x)+getDigiSum(y-1) <= k && visited[x][y-1] == false {
			queue = append(queue, [2]int{x, y - 1})
			visited[x][y-1] = true
		}
	}
	return res
}

func getDigiSum(num int) int {
	sum := 0
	for num > 0 {
		sum = sum + num%10
		num = num / 10
	}
	return sum
}

面试题14- I.剪绳子(2)

• 题目

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1： 输入: 2 输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2: 输入: 10 输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：2 <= n <= 58
注意：本题与主站 343 题相同：https://leetcode.cn/problems/integer-break/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划(书上方法)	O(n^2)	O(n)
02	贪心法	O(1)	O(1)

func cuttingRope(n int) int {
	if n < 2 {
		return 0
	}
	if n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	dp[2] = 2
	dp[3] = 3
	for i := 4; i <= n; i++ {
		max := 0
		for j := 1; j <= i/2; j++ {
			length := dp[j] * dp[i-j]
			if length > max {
				max = length
			}
			dp[i] = max
		}
	}
	return dp[n]
}

#
func cuttingRope(n int) int {
	if n < 2 {
		return 0
	}
	if n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}
	timesOf3 := n / 3
	if n-timesOf3*3 == 1 {
		timesOf3 = timesOf3 - 1
	}
	timesOf2 := (n - timesOf3*3) / 2
	return int(math.Pow(float64(2), float64(timesOf2))) *
		int(math.Pow(float64(3), float64(timesOf3)))
}

面试题14-II.剪绳子 II(2)

• 题目

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？
例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：2 <= n <= 1000
注意：本题与主站 343 题相同：https://leetcode.cn/problems/integer-break/

• 解题思路

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

func cuttingRope(n int) int {
	if n < 2 {
		return 0
	}
	if n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}
	timesOf3 := n / 3
	if n-timesOf3*3 == 1 {
		timesOf3 = timesOf3 - 1
	}
	timesOf2 := (n - timesOf3*3) / 2
	return int(math.Pow(float64(2), float64(timesOf2))) *
		myPow3(timesOf3) % 1000000007
}

func myPow3(n int) int {
	res := 1
	for i := 0; i < n; i++{
		res = (res * 3) % 1000000007
	}
	return res
}

#
func cuttingRope(n int) int {
	if n < 2 {
		return 0
	}
	if n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}
	timesOf3 := n / 3
	if n-timesOf3*3 == 1 {
		timesOf3 = timesOf3 - 1
	}
	timesOf2 := (n - timesOf3*3) / 2
	return int(math.Pow(float64(2), float64(timesOf2))) *
		myPow3(timesOf3) % 1000000007
}

func myPow3(n int) int {
	res := 1
	for i := 0; i < n; i++ {
		res = (res * 3) % 1000000007
	}
	return res
}

面试题15.二进制中1的个数(4)

• 题目

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。
例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1： 输入：00000000000000000000000000001011 输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：输入：00000000000000000000000010000000 输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：输入：11111111111111111111111111111101 输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
注意：本题与主站 191 题相同：https://leetcode.cn/problems/number-of-1-bits/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	循环位计算	O(1)	O(1)
02	位计算 n&(n-1)，会把该整数的最右边的1变成0(书上方法)	O(1)	O(1)
03	内置函数	O(1)	O(1)
04	遍历(书上方法)	O(1)	O(1)

func hammingWeight(num uint32) int {
	count := 0
	for num != 0 {
		if num&1 == 1 {
			count++
		}
		num = num >> 1
	}
	return count
}

#
func hammingWeight(num uint32) int {
	count := 0
	for num != 0 {
		num = num & (num - 1)
		count++
	}
	return count
}

#
func hammingWeight(num uint32) int {
	return strings.Count(strconv.FormatInt(int64(num), 2), "1")
	// return strings.Count(fmt.Sprintf("%b",num),"1")
}

#
func hammingWeight(num uint32) int {
	count := 0
	flag := uint32(1)
	for flag != 0{
		if num & flag == flag{
			count++
		}
		flag = flag << 1
	}
	return count
}

面试题16.数值的整数次方(4)

• 题目

实现函数double Power(double base, int exponent)，求base的exponent次方。
不得使用库函数，同时不需要考虑大数问题。
示例 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] 。
注意：本题与主站 50 题相同：
https://leetcode.cn/problems/powx-n/

• 解题思路

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

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

#
func myPow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	if n == 1 {
		return x
	}
	res := 1.0
	if n < 0 {
		n = -n
		x = 1 / x
	}
	for n >= 1 {
		if n%2 == 1 {
			res = res * x
			n--
		} else {
			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 < 0 {
		return 1 / myPow(x, -n)
	}
	if n%2 == 1 {
		return x * myPow(x, n-1)
	}
	return myPow(x*x, n/2)
}

面试题17.打印从1到最大的n位数(4)

• 题目

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。
比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1: 输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]
说明：
    用返回一个整数列表来代替打印
    n 为正整数

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	求最大	O(10^n)	O(10^n)
02	求最大	O(10^n)	O(10^n)
03	递归+全排列(书上方法)	O(10^n)	O(10^n)
04	模拟进位(书上方法)	O(10^n)	O(10^n)

func printNumbers(n int) []int {
	res := make([]int, 0)
	maxValue := 0
	for n > 0 {
		maxValue = maxValue*10 + 9
		n--
	}
	for i := 1; i <= maxValue; i++ {
		res = append(res, i)
	}
	return res
}

#
func printNumbers(n int) []int {
	res := make([]int, 0)
	maxValue := 1
	for i := 1; i <= n; i++ {
		maxValue = maxValue * 10
	}
	maxValue = maxValue - 1
	for i := 1; i <= maxValue; i++ {
		res = append(res, i)
	}
	return res
}

# 3
var temp []string

func printNumbers(n int) []int {
	if n <= 0 {
		return nil
	}
	temp = make([]string, 0)
	arr := make([]rune, n)
	for i := 0; i < 10; i++ {
		arr[0] = rune(i + '0')
		dfs(arr, n, 0)
	}

	res := make([]int, 0)
	for i := 0; i < len(temp); i++ {
		value, _ := strconv.Atoi(temp[i])
		res = append(res, value)
	}
	return res
}

func dfs(arr []rune, n int, index int) {
	if index == n-1 {
		if printNum(arr) != "" {
			temp = append(temp, printNum(arr))
		}
		return
	}
	for i := 0; i < 10; i++ {
		arr[index+1] = rune(i + '0')
		dfs(arr, n, index+1)
	}
}

func printNum(arr []rune) string {
	res := ""
	isBeginning := true
	for i := 0; i < len(arr); i++ {
		if isBeginning && arr[i] != '0' {
			isBeginning = false
		}
		if !isBeginning {
			res = res + string(arr[i])
		}
	}
	return res
}

# 4
func printNumbers(n int) []int {
	res := make([]int, 0)
	if n <= 0 {
		return nil
	}
	temp := make([]string, 0)
	arr := make([]rune, n)
	for i := 0; i < len(arr); i++ {
		arr[i] = '0'
	}
	for !increment(arr) {
		if printNum(arr) != "" {
			temp = append(temp, printNum(arr))
		}
	}
	for i := 0; i < len(temp); i++ {
		value, _ := strconv.Atoi(temp[i])
		res = append(res, value)
	}
	return res
}

func increment(arr []rune) bool {
	isOverflow := false
	nTakeOver := 0
	for i := len(arr) - 1; i >= 0; i-- {
		sum := int(arr[i]-'0') + nTakeOver
		if i == len(arr)-1 {
			sum++
		}
		if sum >= 10 {
			if i == 0 {
				isOverflow = true
			} else {
				sum = sum - 10
				nTakeOver = 1
				arr[i] = rune('0' + sum)
			}
		} else {
			arr[i] = rune('0' + sum)
			break
		}
	}
	return isOverflow
}

func printNum(arr []rune) string {
	res := ""
	isBeginning := true
	for i := 0; i < len(arr); i++ {
		if isBeginning && arr[i] != '0' {
			isBeginning = false
		}
		if !isBeginning {
			res = res + string(arr[i])
		}
	}
	return res
}

面试题18.删除链表的节点(2)

• 题目

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:输入: head = [4,5,1,9], val = 5 输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:输入: head = [4,5,1,9], val = 1 输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
    题目保证链表中节点的值互不相同
    若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哨兵结点+链表遍历	O(n)	O(1)
02	递归	O(n)	O(n)

func deleteNode(head *ListNode, val int) *ListNode {
	headPre := &ListNode{Next: head}
	temp := headPre
	for temp.Next != nil {
		if temp.Next.Val == val {
			temp.Next = temp.Next.Next
			break
		} else {
			temp = temp.Next
		}
	}
	return headPre.Next
}

#
func deleteNode(head *ListNode, val int) *ListNode {
	if head == nil {
		return nil
	}
	head.Next = deleteNode(head.Next, val)
	if head.Val == val {
		return head.Next
	}
	return head
}

面试题19.正则表达式匹配(3)

• 题目

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，
而'*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 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
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
注意：本题与主站 10 题相同：
https://leetcode.cn/problems/regular-expression-matching/

• 解题思路

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
}

#
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:])
}

面试题20.表示数值的字符串(1)

• 题目

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"都表示数值，
但"12e"、"1a3.14"、"1.2.3"、"+-5"、"-1E-16"及"12e+5.4"都不是。
注意：本题与主站 65 题相同：https://leetcode.cn/problems/valid-number/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历-找规律(书上方法)	O(n)	O(1)

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
}

面试题21.调整数组顺序使奇数位于偶数前面(4)

• 题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。
示例：输入：nums = [1,2,3,4] 输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。
提示：
    1 <= nums.length <= 50000
    1 <= nums[i] <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	双指针(书上方法)	O(n)	O(1)
03	遍历	O(n)	O(n)
04	遍历	O(n)	O(1)

func exchange(nums []int) []int {
	i := 0
	j := len(nums) - 1
	for i < j {
		if nums[i]%2 == 1 {
			i++
		} else if nums[j]%2 == 0 {
			j--
		} else {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	return nums
}

#
func exchange(nums []int) []int {
	i := 0
	j := len(nums) - 1
	for i < j {
		for i < j && nums[i]%2 == 1 {
			i++
		}
		for i < j && nums[j]%2 == 0 {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	return nums
}

#
func exchange(nums []int) []int {
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		if nums[i]%2 == 1 {
			res = append(res, nums[i])
		}
	}
	for i := 0; i < len(nums); i++ {
		if nums[i]%2 == 0 {
			res = append(res, nums[i])
		}
	}
	return res
}

#
func exchange(nums []int) []int {
	count := 0
	for i := 0; i < len(nums); i++ {
		if nums[i]%2 == 1 {
			nums[count], nums[i] = nums[i], nums[count]
			count++
		}
	}
	return nums
}

面试题22.链表中倒数第k个节点(5)

• 题目

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，
即链表的尾节点是倒数第1个节点。
例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。
这个链表的倒数第3个节点是值为4的节点。
示例：给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数组辅助	O(n)	O(n)
02	快慢指针(书上方法)	O(n)	O(1)
03	统计+遍历	O(n)	O(1)
04	递归	O(n)	O(n)
05	递归	O(n)	O(n)

func getKthFromEnd(head *ListNode, k int) *ListNode {
	arr := make([]*ListNode, 0)
	for head != nil {
		arr = append(arr, head)
		head = head.Next
	}
	if len(arr) >= k {
		return arr[len(arr)-k]
	}
	return nil
}

#
func getKthFromEnd(head *ListNode, k int) *ListNode {
	fast := head
	for k > 0 && head != nil {
		fast = fast.Next
		k--
	}
	if k > 0 {
		return nil
	}
	slow := head
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	return slow
}

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

#
func getKthFromEnd(head *ListNode, k int) *ListNode {
	res, count := dfs(head, k)
	if count > 0 {
		return nil
	}
	return res
}

func dfs(node *ListNode, k int) (*ListNode, int) {
	if node == nil {
		return node, k
	}
	next, nextValue := dfs(node.Next, k)
	if nextValue <= 0 {
		return next, nextValue
	}
	nextValue = nextValue - 1
	return node, nextValue
}

#
var res *ListNode
var count int

func getKthFromEnd(head *ListNode, k int) *ListNode {
	if head == nil {
		count = 0
		return nil
	}
	getKthFromEnd(head.Next, k)
	count++
	if count == k {
		res = head
	}
	return res
}

面试题24.反转链表(4)

• 题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：0 <= 节点个数 <= 5000
注意：本题与主站 206 题相同：https://leetcode.cn/problems/reverse-linked-list/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(n)
02	迭代(书上方法)	O(n)	O(1)
03	数组辅助	O(n)	O(n)
04	迭代-新建节点	O(n)	O(1)

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	result := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return result
}

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

#
func reverseList(head *ListNode) *ListNode {
	result := &ListNode{}
	arr := make([]*ListNode, 0)
	for head != nil {
		arr = append(arr, head)
		head = head.Next
	}
	temp := result
	for i := len(arr) - 1; i >= 0; i-- {
		arr[i].Next = nil
		temp.Next = arr[i]
		temp = temp.Next
	}
	return result.Next
}

#
func reverseList(head *ListNode) *ListNode {
	var res *ListNode
	for {
		if head == nil {
			break
		}
		res = &ListNode{head.Val, res}
		head = head.Next
	}
	return res
}

面试题25.合并两个排序的链表(3)

• 题目

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
限制：0 <= 链表长度 <= 1000
注意：本题与主站 21 题相同：https://leetcode.cn/problems/merge-two-sorted-lists/

• 解题思路

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)

• 题目

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：
   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：输入：A = [1,2,3], B = [3,1]输出：false
示例 2：输入：A = [3,4,5,1,2], B = [4,1]输出：true
限制：0 <= 节点个数 <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归(书上方法)	O(n^2)	O(log(n))
02	迭代+递归	O(n^2)	O(n)

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}
	return dfs(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func dfs(A *TreeNode, B *TreeNode) bool {
	if B == nil {
		return true
	}
	if A == nil {
		return false
	}
	return dfs(A.Left, B.Left) && dfs(A.Right, B.Right) && A.Val == B.Val
}

#
func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}

	res := false
	list := make([]*TreeNode, 0)
	list = append(list, A)
	for len(list) > 0 {
		node := list[0]
		list = list[1:]
		if node.Val == B.Val {
			res = dfs(node, B)
			if res == true {
				return true
			}
		}
		if node.Left != nil {
			list = append(list, node.Left)
		}
		if node.Right != nil {
			list = append(list, node.Right)
		}
	}
	return res
}

func dfs(A *TreeNode, B *TreeNode) bool {
	fmt.Println(A, B)
	if B == nil {
		return true
	}
	if A == nil {
		return false
	}
	return dfs(A.Left, B.Left) && dfs(A.Right, B.Right) && A.Val == B.Val
}

面试题27.二叉树的镜像(2)

• 题目

请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
镜像输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1
示例 1：输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
限制：0 <= 节点个数 <= 1000
注意：本题与主站 226 题相同：https://leetcode.cn/problems/invert-binary-tree/

• 解题思路

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

func mirrorTree(root *TreeNode) *TreeNode {
	if root == nil || (root.Left == nil && root.Right == nil) {
		return root
	}
	root.Left, root.Right = mirrorTree(root.Right), mirrorTree(root.Left)
	return root
}

#
func mirrorTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	var queue []*TreeNode
	queue = append(queue, root)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		node.Left, node.Right = node.Right, node.Left
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return root
}

面试题28.对称的二叉树(2)

• 题目

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3
示例 1：输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：输入：root = [1,2,2,null,3,null,3] 输出：false
限制：0 <= 节点个数 <= 1000
注意：本题与主站 101 题相同：https://leetcode.cn/problems/symmetric-tree/

• 解题思路

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

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return recur(root.Left, root.Right)
}

func recur(left, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	}
	if left == nil || right == nil {
		return false
	}

	return left.Val == right.Val &&
		recur(left.Left, right.Right) &&
		recur(left.Right, right.Left)
}

#
func isSymmetric(root *TreeNode) bool {
	leftQ := make([]*TreeNode, 0)
	rightQ := make([]*TreeNode, 0)
	leftQ = append(leftQ, root)
	rightQ = append(rightQ, root)

	for len(leftQ) != 0 && len(rightQ) != 0 {
		leftCur, rightCur := leftQ[0], rightQ[0]
		leftQ, rightQ = leftQ[1:], rightQ[1:]

		if leftCur == nil && rightCur == nil {
			continue
		} else if leftCur != nil && rightCur != nil && leftCur.Val == rightCur.Val {
			leftQ = append(leftQ, leftCur.Left, leftCur.Right)
			rightQ = append(rightQ, rightCur.Right, rightCur.Left)
		} else {
			return false
		}
	}

	if len(leftQ) == 0 && len(rightQ) == 0 {
		return true
	} else {
		return false
	}
}

面试题29.顺时针打印矩阵(2)

• 题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
示例 2：输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：0 <= matrix.length <= 100  0 <= matrix[i].length <= 100
注意：本题与主站 54 题相同：https://leetcode.cn/problems/spiral-matrix/

• 解题思路

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
}

面试题30.包含min函数的栈(2)

• 题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.
提示：
    各函数的调用总次数不超过 20000 次
注意：本题与主站 155 题相同：https://leetcode.cn/problems/min-stack/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	使用数组模拟栈，保存数据的时候同时保存当前的最小值	O(1)	O(n)
02	使用双栈(书上方法)	O(1)	O(n)

type item struct {
	min, x int
}

type MinStack struct {
	stack []item
}

func Constructor() MinStack {
	return MinStack{}
}

func (m *MinStack) Push(x int) {
	min := x
	if len(m.stack) > 0 && m.Min() < x {
		min = m.Min()
	}
	m.stack = append(m.stack, item{
		min: min,
		x:   x,
	})
}

func (m *MinStack) Pop() {
	m.stack = m.stack[:len(m.stack)-1]
}

func (m *MinStack) Top() int {
	if len(m.stack) == 0 {
		return 0
	}
	return m.stack[len(m.stack)-1].x
}

func (m *MinStack) Min() int {
	if len(m.stack) == 0 {
		return 0
	}
	return m.stack[len(m.stack)-1].min
}

#
type MinStack struct {
	data []int
	min  []int
}

func Constructor() MinStack {
	return MinStack{[]int{}, []int{}}
}

func (m *MinStack) Push(x int) {
	if len(m.data) == 0 || x <= m.Min() {
		m.min = append(m.min, x)
	}
	m.data = append(m.data, x)
}

func (m *MinStack) Pop() {
	x := m.data[len(m.data)-1]
	m.data = m.data[:len(m.data)-1]
	if x == m.Min() {
		m.min = m.min[:len(m.min)-1]
	}
}

func (m *MinStack) Top() int {
	if len(m.data) == 0 {
		return 0
	}
	return m.data[len(m.data)-1]
}

func (m *MinStack) Min() int {
	return m.min[len(m.min)-1]
}

面试题31.栈的压入弹出序列(2)

• 题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，
但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false
解释：1 不能在 2 之前弹出。
提示：
    0 <= pushed.length == popped.length <= 1000
    0 <= pushed[i], popped[i] < 1000
    pushed 是 popped 的排列。
注意：本题与主站 946 题相同：https://leetcode.cn/problems/validate-stack-sequences/

• 解题思路

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

func validateStackSequences(pushed []int, popped []int) bool {
	stack := make([]int, 0)
	j := 0
	for i := 0; i < len(pushed); i++ {
		stack = append(stack, pushed[i])
		for len(stack) > 0 && stack[len(stack)-1] == popped[j] {
			stack = stack[:len(stack)-1]
			j++
		}
	}
	if len(stack) == 0 {
		return true
	}
	return false
}

#
func validateStackSequences(pushed []int, popped []int) bool {
	stack := make([]int, 0)
	res := false
	i := 0
	j := 0
	for j < len(popped) {
		for len(stack) == 0 || stack[len(stack)-1] != popped[j] {
			if i == len(pushed) {
				break
			}
			stack = append(stack, pushed[i])
			i++
		}
		if stack[len(stack)-1] != popped[j] {
			break
		}
		stack = stack[:len(stack)-1]
		j++
	}
	if len(stack) == 0 && j == len(popped) {
		res = true
	}
	return res
}

面试题32-I.从上到下打印二叉树(2)

• 题目

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回：[3,9,20,15,7]
提示：节点总数 <= 1000

• 解题思路

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

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

#
func levelOrder(root *TreeNode) []int {
	res := make([]int, 0)
	if root == nil {
		return res
	}
	arr := levelArr(root)
	for i := 0; i < len(arr); i++ {
		res = append(res, arr[i]...)
	}
	return res
}

func levelArr(root *TreeNode) [][]int {
	temp := make([][]int, 0)
	dfs(root, &temp, 0)
	return temp
}

func dfs(root *TreeNode, temp *[][]int, level int) {
	if root == nil {
		return
	}
	if len(*temp)-1 < level {
		*temp = append(*temp, make([]int, 0))
	}
	(*temp)[level] = append((*temp)[level], root.Val)
	level = level + 1
	dfs(root.Left, temp, level)
	dfs(root.Right, temp, level)
}

面试题32-II.从上到下打印二叉树II(2)

• 题目

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]
提示：节点总数 <= 1000
注意：本题与主站 102 题相同：
https://leetcode.cn/problems/binary-tree-level-order-traversal/

• 解题思路

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

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

#
func levelOrder(root *TreeNode) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}
	return levelArr(root)
}

func levelArr(root *TreeNode) [][]int {
	temp := make([][]int, 0)
	dfs(root, &temp, 0)
	return temp
}

func dfs(root *TreeNode, temp *[][]int, level int) {
	if root == nil {
		return
	}
	if len(*temp)-1 < level {
		*temp = append(*temp, make([]int, 0))
	}
	(*temp)[level] = append((*temp)[level], root.Val)
	level = level + 1
	dfs(root.Left, temp, level)
	dfs(root.Right, temp, level)
}

面试题32-III.从上到下打印二叉树III(2)

• 题目

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：
[
  [3],
  [20,9],
  [15,7]
]
提示：节点总数 <= 1000

• 解题思路

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

func levelOrder(root *TreeNode) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}
	list := make([]*TreeNode, 0)
	list = append(list, root)
	level := 0
	for len(list) > 0 {
		length := len(list)
		temp := make([]int, 0)
		for i := 0; i < length; i++ {
			node := list[i]
			if node.Left != nil {
				list = append(list, node.Left)
			}
			if node.Right != nil {
				list = append(list, node.Right)
			}
		}
		if level%2 == 0 {
			for i := 0; i < length; i++ {
				temp = append(temp, list[i].Val)
			}
		} else {
			for i := length - 1; i >= 0; i-- {
				temp = append(temp, list[i].Val)
			}
		}
		list = list[length:]
		res = append(res, temp)
		level++
	}
	return res
}

#
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	temp := make([][]int, 0)
	dfs(root, &temp, 0)
	return temp
}

func dfs(root *TreeNode, temp *[][]int, level int) {
	if root == nil {
		return
	}
	if len(*temp)-1 < level {
		*temp = append(*temp, make([]int, 0))
	}
	if level%2 == 0 {
		(*temp)[level] = append((*temp)[level], root.Val)
	} else {
		(*temp)[level] = append([]int{root.Val}, (*temp)[level]...)
	}
	level = level + 1
	dfs(root.Left, temp, level)
	dfs(root.Right, temp, level)
}

面试题33.二叉搜索树的后序遍历序列(3)

• 题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。
假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
     5
    / \
   2   6
  / \
 1   3
示例 1：输入: [1,6,3,2,5]输出: false
示例 2：输入: [1,3,2,6,5]输出: true
提示：
    数组长度 <= 1000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归(书上方法)	O(n^2)	O(n)
02	迭代	O(n^2)	O(1)
03	栈辅助	O(n)	O(n)

func verifyPostorder(postorder []int) bool {
	return dfs(postorder, 0, len(postorder)-1)
}

func dfs(postorder []int, start, end int) bool {
	if start >= end {
		return true
	}
	i := 0
	for i = start; i < end; i++ {
		if postorder[i] > postorder[end] {
			break
		}
	}
	for j := i + 1; j < end; j++ {
		if postorder[j] < postorder[end] {
			return false
		}
	}
	return dfs(postorder, start, i-1) && dfs(postorder, i, end-1)
}

#
func verifyPostorder(postorder []int) bool {
	if len(postorder) <= 2 {
		return true
	}
	last := len(postorder) - 1
	for last > 0 {
		i := 0
		for postorder[i] < postorder[last] {
			i++
		}
		for postorder[i] > postorder[last] {
			i++
		}
		if i != last {
			return false
		}
		last--
	}
	return true
}

#
func verifyPostorder(postorder []int) bool {
	if len(postorder) <= 2 {
		return true
	}
	stack := make([]int, 0)
	rootValue := math.MaxInt32
	for i := len(postorder) - 1; i >= 0; i-- {
		if postorder[i] > rootValue {
			// 左子树元素必须要小于递增栈根节点
			return false
		}
		// 数组元素小于单调栈的元素了，表示往左子树走了，记录上个根节点
		for len(stack) > 0 && postorder[i] < stack[len(stack)-1] {
			rootValue = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, postorder[i])
	}
	return true
}

面试题34.二叉树中和为某一值的路径(2)

• 题目

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:给定如下二叉树，以及目标和 sum = 22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:
[
   [5,4,11,2],
   [5,8,4,5]
]
提示：节点总数 <= 10000
注意：本题与主站 113 题相同：https://leetcode.cn/problems/path-sum-ii/

• 解题思路

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

var res [][]int

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

func dfs(root *TreeNode, sum int, arr []int) {
	if root == nil {
		return
	}
	arr = append(arr, root.Val)
	if root.Val == sum && root.Left == nil && root.Right == nil {
		temp := make([]int, len(arr))
		copy(temp, arr)
		res = append(res, temp)
	}
	dfs(root.Left, sum-root.Val, arr)
	dfs(root.Right, sum-root.Val, arr)
	arr = arr[:len(arr)-1]
}

#
func pathSum(root *TreeNode, sum int) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}
	temp := make([]int, 0)
	stack := make([]*TreeNode, 0)
	visited := make(map[*TreeNode]bool)
	curSum := 0
	for root != nil || len(stack) > 0 {
		for root != nil {
			temp = append(temp, root.Val)
			curSum = curSum + root.Val
			visited[root] = true
			stack = append(stack, root)
			root = root.Left
		}
		node := stack[len(stack)-1]
		if node.Right == nil || visited[node.Right] {
			if node.Left == nil && node.Right == nil && curSum == sum {
				tmp := make([]int, len(temp))
				copy(tmp, temp)
				res = append(res, tmp)
			}
			stack = stack[:len(stack)-1]
			temp = temp[:len(temp)-1]
			curSum = curSum - node.Val
			root = nil
		} else {
			root = node.Right
		}
	}
	return res
}

面试题35.复杂链表的复制(3)

• 题目

请实现 copyRandomList 函数，复制一个复杂链表。
在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
还有一个 random 指针指向链表中的任意节点或者 null。
示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：输入：head = [] 输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
    -10000 <= Node.val <= 10000
    Node.random 为空（null）或指向链表中的节点。
    节点数目不超过 1000 。
注意：本题与主站 138 题相同：
https://leetcode.cn/problems/copy-list-with-random-pointer/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助-递归	O(n)	O(n)
02	哈希辅助	O(n)	O(n)
03	复制-删除(书上方法)	O(n)	O(1)

var m map[*Node]*Node

func copyRandomList(head *Node) *Node {
	m = make(map[*Node]*Node)
	return copyList(head)
}

func copyList(head *Node) *Node {
	if head == nil {
		return head
	}
	if node, ok := m[head]; ok {
		return node
	}
	temp := &Node{
		Val:    head.Val,
		Next:   nil,
		Random: nil,
	}
	m[head] = temp
	temp.Next = copyList(head.Next)
	temp.Random = copyList(head.Random)
	return temp
}

#
func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	res := new(Node)
	m := make(map[*Node]*Node)
	temp := head
	p := res
	for temp != nil {
		node := &Node{
			Val:    temp.Val,
			Next:   nil,
			Random: nil,
		}
		m[temp] = node
		p.Next = node
		p = p.Next
		temp = temp.Next

	}
	temp = head
	p = res.Next
	for temp != nil {
		p.Random = m[temp.Random]
		p = p.Next
		temp = temp.Next
	}
	return res.Next
}

# 3
func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	res := copyNext(head)
	res = copyRandom(res)
	res = cutEven(res)
	return res
}

// 原1-复制1-原2-复制2
func copyNext(head *Node) *Node {
	p := head
	for p != nil {
		node := new(Node)
		node.Val = p.Val
		node.Next = p.Next
		p.Next = node
		p = node.Next
	}
	return head
}

func copyRandom(head *Node) *Node {
	p := head
	for p != nil {
		if p.Random != nil {
			p.Next.Random = p.Random.Next
		}
		p = p.Next.Next
	}
	return head
}

func cutEven(head *Node) *Node {
	oldNode := head
	newNode := head.Next
	cur := newNode
	for oldNode != nil {
		oldNode.Next = oldNode.Next.Next
		if newNode.Next != nil{
			newNode.Next = newNode.Next.Next
		}
		oldNode = oldNode.Next
		newNode = newNode.Next
	}
	return cur
}

面试题38.字符串的排列(2)

• 题目

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]
限制：1 <= s 的长度 <= 8

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	回溯算法	O(n!)	O(n!)
02	回溯算法-交换(书上方法)	O(n!)	O(n!)

var m map[string]bool

func permutation(s string) []string {
	m = make(map[string]bool)
	dfs(s, "")
	res := make([]string, 0)
	for key := range m {
		res = append(res, key)
	}
	return res
}

func dfs(s string, str string) {
	if len(s) == 0 {
		m[str] = true
	}
	for i := 0; i < len(s); i++ {
		arr := []byte(s)
		temp := arr[i]
		if len(arr)-1 == i {
			arr = arr[:len(arr)-1]
		} else {
			arr = append(arr[:i], arr[i+1:]...)
		}
		dfs(string(arr), str+string(temp))
	}
}

#
var res []string

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

func dfs(arr []byte, index int) {
	if len(arr)-1 == index {
		res = append(res, string(arr))
		return
	}
	m := make(map[byte]bool)
	for i := index; i < len(arr); i++ {
		if _, ok := m[arr[i]]; ok {
			continue
		}
		m[arr[i]] = true
		arr[i], arr[index] = arr[index], arr[i]
		dfs(arr, index+1)
		arr[i], arr[index] = arr[index], arr[i]
	}
}

面试题39.数组中出现次数超过一半的数字(5)

• 题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
限制：1 <= 数组长度 <= 50000
注意：本题与主站 169 题相同：https://leetcode.cn/problems/majority-element/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序取半	O(nlog(n))	O(1)
02	哈希遍历	O(n)	O(n)
03	Boyer-Moore投票算法(书上方法)	O(n)	O(1)
04	位运算	O(n)	O(1)
05	分治法	O(nlog(n))	O(log(n))

func majorityElement(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums)/2]
}

# 2
func majorityElement(nums []int) int {
	m := make(map[int]int)
	result := 0
	for _, v := range nums{
		if _,ok := m[v];ok{
			m[v]++
		}else {
			m[v]=1
		}
		if m[v] > (len(nums)/2){
			result = v
		}
	}
	return result
}

# 3
func majorityElement(nums []int) int {
	result, count := 0, 0
	for i := 0; i < len(nums); i++ {
		if count == 0 {
			result = nums[i]
			count++
		} else if result == nums[i] {
			count++
		} else {
			count--
		}
	}
	return result
}

# 4
func majorityElement(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	result := int32(0)
	// 64位有坑
	mask := int32(1)
	for i := 0; i < 32; i++ {
		count := 0
		for j := 0; j < len(nums); j++ {
			if mask&int32(nums[j]) == mask {
				count++
			}
		}
		if count > len(nums)/2 {
			result = result | mask
		}
		mask = mask << 1
	}
	return int(result)
}

# 5
func majority(nums []int, start, end int) int {
	if start == end {
		return nums[start]
	}

	mid := (start + end) / 2

	left := majority(nums, start, mid)
	right := majority(nums, mid+1, end)
	if left == right {
		return left
	}

	leftCount := count(nums, left, start, end)
	rightCount := count(nums, right, start, end)
	if leftCount > rightCount {
		return left
	}
	return right
}

面试题40.最小的k个数(4)

• 题目

输入整数数组 arr ，找出其中最小的 k 个数。
例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]
示例 2：输入：arr = [0,1,2,1], k = 1 输出：[0]
限制：
    0 <= k <= arr.length <= 10000
    0 <= arr[i] <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序	O(nlog(n))	O(1)
02	堆	O(nlog(n))	O(n)
03	计数统计	O(n)	O(n)
04	快排切分(书上方法)	O(n)	O(1)

func getLeastNumbers(arr []int, k int) []int {
	if len(arr) == 0 || k == 0 {
		return nil
	}
	sort.Ints(arr)
	return arr[:k]
}

#
type IntHeap []int

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

func (i IntHeap) Less(x, y int) bool {
	return i[x] > i[y]
}

func (i IntHeap) Swap(x, y int) {
	i[x], i[y] = i[y], i[x]
}
func (i *IntHeap) Push(v interface{}) {
	*i = append(*i, v.(int))
}

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

func getLeastNumbers(arr []int, k int) []int {
	if len(arr) == 0 || k == 0 {
		return nil
	}
	intHeap := make(IntHeap, 0, k)
	heap.Init(&intHeap)

	for i := 0; i < len(arr); i++ {
		if len(intHeap) < k {
			heap.Push(&intHeap, arr[i])
		} else if len(intHeap) == k {
			if arr[i] < intHeap[0] {
				heap.Pop(&intHeap)
				heap.Push(&intHeap, arr[i])
			}
		}
	}
	return intHeap
}

#
func getLeastNumbers(arr []int, k int) []int {
	if len(arr) == 0 || k == 0 {
		return nil
	}
	a := make([]int, 10001)
	for _, v := range arr {
		a[v]++
	}
	res := make([]int, 0)
	for key, value := range a {
		if value > 0 {
			for i := 0; i < value; i++ {
				res = append(res, key)
				k--
				if k <= 0 {
					return res
				}
			}
		}
	}
	return res
}

#
func getLeastNumbers(arr []int, k int) []int {
	if len(arr) == 0 || k == 0 {
		return nil
	}
	left := 0
	right := len(arr) - 1
	for {
		index := partition(arr, left, right)
		if index+1 == k {
			break
		} else if index+1 < k {
			left = index + 1
		} else {
			right = index - 1
		}
	}
	return arr[:k]
}

func partition(arr []int, left, right int) int {
	if left == right {
		return left
	}
	value := arr[left]
	i := left
	j := right
	for {
		for arr[j] >= value && i < j {
			j--
		}
		for arr[i] <= value && i < j {
			i++
		}
		if i >= j {
			break
		}
		arr[i], arr[j] = arr[j], arr[i]
	}
	arr[left] = arr[i]
	arr[i] = value
	return i
}

面试题41.数据流中的中位数(1)

• 题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
    void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    double findMedian() - 返回目前所有元素的中位数。

示例 1：输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2： 输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：最多会对 addNum、findMedia进行 50000 次调用。
注意：本题与主站 295 题相同：
https://leetcode.cn/problems/find-median-from-data-stream/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	大小根堆-内置heap接口	O(log(n))	O(n)

type MinHeap []int

func (i MinHeap) Len() int {
	return len(i)
}

func (i MinHeap) Less(x, y int) bool {
	return i[x] < i[y]
}

func (i MinHeap) Swap(x, y int) {
	i[x], i[y] = i[y], i[x]
}
func (i *MinHeap) Push(v interface{}) {
	*i = append(*i, v.(int))
}

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

type MaxHeap []int

func (i MaxHeap) Len() int {
	return len(i)
}

func (i MaxHeap) Less(x, y int) bool {
	return i[x] > i[y]
}

func (i MaxHeap) Swap(x, y int) {
	i[x], i[y] = i[y], i[x]
}
func (i *MaxHeap) Push(v interface{}) {
	*i = append(*i, v.(int))
}

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

type MedianFinder struct {
	minArr *MinHeap
	maxArr *MaxHeap
}

func Constructor() MedianFinder {
	res := new(MedianFinder)
	res.minArr = new(MinHeap)
	res.maxArr = new(MaxHeap)
	heap.Init(res.minArr)
	heap.Init(res.maxArr)
	return *res
}

func (this *MedianFinder) AddNum(num int) {
	if this.maxArr.Len() == this.minArr.Len() {
		heap.Push(this.minArr, num)
		heap.Push(this.maxArr, heap.Pop(this.minArr))
	} else {
		heap.Push(this.maxArr, num)
		heap.Push(this.minArr, heap.Pop(this.maxArr))
	}
}

func (this *MedianFinder) FindMedian() float64 {
	if this.minArr.Len() == this.maxArr.Len() {
		return (float64((*this.maxArr)[0]) + float64((*this.minArr)[0])) / 2
	} else {
		return float64((*this.maxArr)[0])
	}
}

面试题42.连续子数组的最大和(4)

• 题目

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
    1 <= arr.length <= 10^5
    -100 <= arr[i] <= 100
注意：本题与主站 53 题相同：https://leetcode.cn/problems/maximum-subarray/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	贪心法(书上方法)	O(n)	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 {
	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
}

面试题43.1～n整数中1出现的次数(3)

• 题目

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：输入：n = 12 出：5
示例 2：输入：n = 13 出：6
限制： 1 <= n < 2^31
注意：本题与主站 233 题相同：
https://leetcode.cn/problems/number-of-digit-one/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	找规律-遍历	O(log(n))	O(1)
02	找规律-递归(书上方法)	O(log(n))	O(log(n))
03	找规律	O(log(n))	O(1)

func countDigitOne(n int) int {
	res := 0
	digit := 1
	high := n / 10
	cur := n % 10
	low := 0
	for high != 0 || cur != 0 {
		if cur == 0 {
			res = res + high*digit
		} else if cur == 1 {
			res = res + high*digit + low + 1
		} else {
			res = res + (high+1)*digit
		}
		low = low + cur*digit
		cur = high % 10
		high = high / 10
		digit = digit * 10
	}
	return res
}

#
func countDigitOne(n int) int {
	if n <= 0 {
		return 0
	}
	str := strconv.Itoa(n)
	return dfs(str)
}

func dfs(str string) int {
	if str == "" {
		return 0
	}
	first := int(str[0] - '0')
	if len(str) == 1 && first == 0 {
		return 0
	}
	if len(str) == 1 && first >= 1 {
		return 1
	}
	count := 0
	if first > 1 {
		count = int(math.Pow(float64(10), float64(len(str)-1)))
	} else if first == 1 {
		count, _ = strconv.Atoi(str[1:])
		count = count + 1
	}
	other := first * (len(str) - 1) * int(math.Pow(float64(10), float64(len(str)-2)))
	numLeft := dfs(str[1:])
	return count + numLeft + other
}

#
func countDigitOne(n int) int {
	if n <= 0 {
		return 0
	}
	res := 0
	for i := 1; i <= n; i = i * 10 {
		left := n / i
		right := n % i
		res = res + (left+8)/10*i
		if left%10 == 1 {
			res = res + right + 1
		}
	}
	return res
}

面试题44.数字序列中某一位的数字(2)

• 题目

数字以0123456789101112131415…的格式序列化到一个字符序列中。
在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：输入：n = 3 输出：3
示例 2：输入：n = 11 输出：0
限制： 0 <= n < 2^31
注意：本题与主站 400 题相同：https://leetcode.cn/problems/nth-digit/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	找规律(书上方法)	O(log(n))	O(1)
02	找规律	O(log(n))	O(1)

func findNthDigit(n int) int {
	if n < 0 {
		return -1
	}
	digits := 1
	for {
		numbers := countOfIntegers(digits)
		if n < numbers*digits {
			return digitAtIndex(n, digits)
		}
		n = n - numbers*digits
		digits++
	}
}

func countOfIntegers(n int) int {
	if n == 1 {
		return 10
	}
	count := math.Pow(float64(10), float64(n-1))
	return 9 * int(count)
}

func digitAtIndex(n, digits int) int {
	number := beginNumber(digits) + n/digits
	indexFromRight := digits - n%digits
	for i := 1; i < indexFromRight; i++ {
		number = number / 10
	}
	return number % 10
}

func beginNumber(digits int) int {
	if digits == 1 {
		return 0
	}
	return int(math.Pow(float64(10), float64(digits-1)))
}

#
/*
1-9 	9*1 1位
10-99 	90*2 2位
100-999 900*3 3位
*/
func findNthDigit(n int) int {
	if n < 10 {
		return n
	}
	digits := 1
	count := 9
	number := 1
	for n-digits*count > 0 {
		n = n - digits*count
		digits++
		count = count * 10
		number = number * 10
	}
	number = number + (n-1)/digits
	index := (n - 1) % digits
	str := strconv.Itoa(number)
	return int(str[index] - '0')
}

面试题45.把数组排成最小的数(3)

• 题目

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:输入: [10,2] 输出: "102"
示例 2:输入: [3,30,34,5,9] 输出: "3033459"
提示:0 < nums.length <= 100
说明:
    输出结果可能非常大，所以你需要返回一个字符串而不是整数
    拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	自定义排序	O(nlog(n))	O(n)
02	快排(书上方法)	O(nlog(n))	O(n)
03	实现sort接口	O(nlog(n))	O(n)

func minNumber(nums []int) string {
	sort.Slice(nums, func(i, j int) bool {
		if fmt.Sprintf("%d%d", nums[i], nums[j]) <
			fmt.Sprintf("%d%d", nums[j], nums[i]) {
			return true
		}
		return false
	})
	str := ""
	for i := 0; i < len(nums); i++ {
		str = str + fmt.Sprintf("%d", nums[i])
	}
	return str
}

#
var arr []string

func minNumber(nums []int) string {
	arr = make([]string, 0)
	for i := 0; i < len(nums); i++ {
		arr = append(arr, strconv.Itoa(nums[i]))
	}
	quickSort(0, len(arr)-1)
	str := ""
	for i := 0; i < len(arr); i++ {
		str = str + arr[i]
	}
	return str
}

func quickSort(start, end int) {
	if start >= end {
		return
	}
	temp := arr[start]
	i := start
	j := end
	for i < j {
		for i < j && arr[j]+temp >= temp+arr[j] {
			j--
		}
		for i < j && arr[i]+temp <= temp+arr[i] {
			i++
		}
		arr[i], arr[j] = arr[j], arr[i]
	}
	arr[start], arr[i] = arr[i], temp
	quickSort(start, i-1)
	quickSort(i+1, end)
}

#
type Arr []string

func (a Arr) Len() int {
	return len(a)
}

func (a Arr) Less(i, j int) bool {
	if a[i]+a[j] < a[j]+a[i] {
		return true
	}
	return false
}

func (a Arr) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func minNumber(nums []int) string {
	var arr Arr
	for i := 0; i < len(nums); i++ {
		arr = append(arr, strconv.Itoa(nums[i]))
	}
	sort.Sort(arr)
	str := ""
	for i := 0; i < len(arr); i++ {
		str = str + arr[i]
	}
	return str
}

面试题46.把数字翻译成字符串(4)

• 题目

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，
11 翻译成 “l”，……，25 翻译成 “z”。
一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:输入: 12258 输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示： 0 <= num < 231

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历(书上方法)	O(log(n))	O(log(n))
02	递归	O(log(n))	O(log(n))
03	遍历-从后往前	O(log(n))	O(1)
04	动态规划-一维数组	O(log(n))	O(log(n))

func translateNum(num int) int {
	if num < 0 {
		return 0
	}
	return getTranslateNum(strconv.Itoa(num))
}

func getTranslateNum(str string) int {
	length := len(str)
	arr := make([]int, length)
	count := 0
	for i := length - 1; i >= 0; i-- {
		count = 0
		if i < length-1 {
			count = arr[i+1]
		} else {
			count = 1
		}
		if i < length-1 {
			digit1 := str[i] - '0'
			digit2 := str[i+1] - '0'
			value := digit1*10 + digit2
			if value >= 10 && value <= 25 {
				if i < length-2 {
					count += arr[i+2]
				} else {
					count += 1
				}
			}
		}
		arr[i] = count
	}
	return arr[0]
}

#
func translateNum(num int) int {
	if num < 10 {
		return 1
	}
	var res int
	if num%100 <= 25 && num%100 > 9 {
		res = res + translateNum(num/100)
		res = res + translateNum(num/10)
	} else {
		res = res + translateNum(num/10)
	}
	return res
}

#
// f(i)=f(i-2)+f(i-1)
// f(i)=f(i-1)
func translateNum(num int) int {
	if num < 0 {
		return 0
	}
	arr := make([]int, 1)
	arr[0] = 1
	i := 0
	prev := -1
	for num > 0 {
		i++
		arr = append(arr, 0)
		arr[i] = arr[i-1]
		digit1 := num % 10
		num = num / 10
		if digit1 != 0 && prev >= 0 && digit1*10+prev <= 25 {
			arr[i] = arr[i] + arr[i-2]
		}
		prev = digit1
	}
	return arr[i]
}

#
// f(i)=f(i-2)+f(i-1)
// f(i)=f(i-1)
func translateNum(num int) int {
	if num < 0 {
		return 0
	}
	str := strconv.Itoa(num)
	arr := make([]int, len(str))
	for i := 0; i < len(str); i++ {
		arr[i] = int(str[i] - '0')
	}
	dp := make([]int, len(str)+1)
	dp[0] = 1
	dp[1] = 1
	for i := 2; i < len(str)+1; i++ {
		if arr[i-2] != 0 && (arr[i-2]*10+arr[i-1] <= 25) {
			dp[i] = dp[i-1] + dp[i-2]
		} else {
			dp[i] = dp[i-1]
		}
	}
	return dp[len(str)]
}

面试题47.礼物的最大价值(2)

• 题目

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
    0 < grid.length <= 200
    0 < grid[0].length <= 200

• 解题思路

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

func maxValue(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	dp := make([][]int, len(grid))
	for i := 0; i < len(grid); i++ {
		dp[i] = make([]int, len(grid[0]))
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			left := 0
			up := 0
			if i > 0 {
				left = dp[i-1][j]
			}
			if j > 0 {
				up = dp[i][j-1]
			}
			// dp[i][j]=grid[i-1][j-1]+max(dp[i][j-1],dp[i-1][j])
			dp[i][j] = max(left, up) + grid[i][j]
		}
	}
	return dp[len(grid)-1][len(grid[0])-1]
}

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

#
func maxValue(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	dp := make([]int, len(grid))
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			left := 0
			up := 0
			if i > 0 {
				left = dp[j]
			}
			if j > 0 {
				up = dp[j-1]
			}
			// dp[j]=grid[i-1][j-1]+max(dp[j-1],dp[j])
			dp[j] = max(left, up) + grid[i][j]
		}
	}
	return dp[len(grid[0])-1]
}

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

面试题48.最长不含重复字符的子字符串(4)

• 题目

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:输入: "abcabcbb" 输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:输入: "bbbbb" 输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:输入: "pwwkew" 输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：s.length <= 40000
注意：本题与主站 3 题相同：
https://leetcode.cn/problems/longest-substring-without-repeating-characters/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	遍历+滑动窗口	O(n)	O(n)
02	双指针	O(n)	O(1)
03	动态规划	O(n)	O(n)
04	动态规划(书上方法)	O(n)	O(1)

func lengthOfLongestSubstring(s string) int {
	if len(s) < 1 {
		return 0
	}
	m := make(map[int32]int)
	arr := make([]int32, 0)
	res := 0
	for _, value := range s {
		if v, ok := m[value]; ok && v > 0 {
			for len(arr) > 0 && arr[0] != value {
				m[arr[0]]--
				arr = arr[1:]
			}
			m[arr[0]]--
			arr = arr[1:]
		}
		m[value]++
		arr = append(arr, value)
		if len(arr) > res {
			res = len(arr)
		}
	}
	return res
}

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

#
// dp[n]=dp[n-1]+1
// dp[n]=n-lastIndex
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
}

#
func lengthOfLongestSubstring(s string) int {
	if len(s) < 1 {
		return 0
	}
	res := 1
	arr := make(map[byte]int)
	curLength := 0
	for i := 0; i < len(s); i++ {
		if preIndex, ok := arr[s[i]]; !ok || i-preIndex > curLength {
			curLength++
		} else {
			if curLength > res {
				res = curLength
			}
			curLength = i - preIndex
		}
		arr[s[i]] = i
	}
	if curLength > res {
		res = curLength
	}
	return res
}

面试题49.丑数(1)

• 题目

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:输入: n = 10 输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明: 1 是丑数。n 不超过1690。
注意：本题与主站 264 题相同：https://leetcode.cn/problems/ugly-number-ii/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	动态规划(书上方法)	O(n)	O(n)

func nthUglyNumber(n int) int {
	dp := make([]int, n)
	dp[0] = 1
    // 丑数*2或3或5之后还是丑数
	idx2, idx3, idx5 := 0, 0, 0
	for i := 1; i < n; i++ {
		dp[i] = min(dp[idx2]*2, min(dp[idx3]*3, dp[idx5]*5))
		if dp[i] == dp[idx2]*2 {
			idx2++
		}
		if dp[i] == dp[idx3]*3 {
			idx3++
		}
		if dp[i] == dp[idx5]*5 {
			idx5++
		}
	}
	return dp[n-1]
}

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

面试题50.第一个只出现一次的字符(3)

• 题目

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = "abaccdeff" 返回 "b"
s = "" 返回 " "
限制：0 <= s 的长度 <= 50000

• 解题思路

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

func firstUniqChar(s string) byte {
	res := byte(' ')
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}
	for i := 0; i < len(s); i++ {
		if m[s[i]] == 1 {
			return s[i]
		}
	}
	return res
}

#
func firstUniqChar(s string) byte {
	res := byte(' ')
	m := [26]int{}
	for i := 0; i < len(s); i++ {
		m[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if m[s[i]-'a'] == 1 {
			return s[i]
		}
	}
	return res
}

#
func firstUniqChar(s string) byte {
	res := byte(' ')
	for i := 0; i < len(s); i++ {
		flag := true
		for j := 0; j < len(s); j++ {
			if s[i] == s[j] && i != j {
				flag = false
				break
			}
		}
		if flag {
			return s[i]
		}
	}
	return res
}

面试题51.数组中的逆序对(1)

• 题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。
示例 1:输入: [7,5,6,4] 输出: 5
限制：0 <= 数组长度 <= 50000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	归并排序(书上方法)	O(nlog(n))	O(n)

var res int

func reversePairs(nums []int) int {
	res = 0
	if len(nums) <= 1 {
		return res
	}
	merge(nums, 0, len(nums)-1)
	return res
}

func merge(nums []int, left, right int) {
	if left >= right {
		return
	}
	mid := (left + right) / 2
	i, j := left, mid+1
	merge(nums, left, mid)
	merge(nums, mid+1, right)

	temp := make([]int, 0)
	for i <= mid && j <= right {
		if nums[i] <= nums[j] {
			temp = append(temp, nums[i])
			i++
		} else {
			res = res + mid - i + 1
			temp = append(temp, nums[j])
			j++
		}
	}
	temp = append(temp, nums[i:mid+1]...)
	temp = append(temp, nums[j:right+1]...)
	for key, value := range temp {
		nums[left+key] = value
	}
}

面试题52.两个链表的第一个公共节点(4)

• 题目

输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
    如果两个链表没有交点，返回 null.
    在返回结果后，两个链表仍须保持原有的结构。
    可假定整个链表结构中没有循环。
    程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
    本题与主站 160 题相同：https://leetcode.cn/problems/intersection-of-two-linked-lists/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	计算长度后，对齐长度再比较(书上方法)	O(n)	O(1)
02	交换后相连，再比较	O(n)	O(1)
03	暴力法	O(n^2)	O(1)
04	哈希法	O(n)	O(n)

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	ALength := 0
	A := headA
	for A != nil {
		ALength++
		A = A.Next
	}
	BLength := 0
	B := headB
	for B != nil {
		BLength++
		B = B.Next
	}

	pA := headA
	pB := headB
	if ALength > BLength {
		n := ALength - BLength
		for n > 0 {
			pA = pA.Next
			n--
		}
	} else {
		n := BLength - ALength
		for n > 0 {
			pB = pB.Next
			n--
		}
	}

	for pA != pB {
		pA = pA.Next
		pB = pB.Next
	}
	return pA
}

#
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	A, B := headA, headB
	for A != B {
		if A != nil {
			A = A.Next
		} else {
			A = headB
		}
		if B != nil {
			B = B.Next
		} else {
			B = headA
		}
	}
	return A
}

#
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	A, B := headA, headB
	for A != nil {
		for B != nil {
			if A == B {
				return A
			}
			B = B.Next
		}
		A = A.Next
		B = headB
	}
	return nil
}

# 4
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	m := make(map[*ListNode]bool)
	for headA != nil {
		m[headA] = true
		headA = headA.Next
	}

	for headB != nil {
		if _, ok := m[headB]; ok {
			return headB
		}
		headB = headB.Next
	}
	return nil
}

面试题53-I.在排序数组中查找数字I(5)

• 题目

统计一个数字在排序数组中出现的次数。
示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例 2:输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
限制：0 <= 数组长度 <= 50000
注意：本题与主站 34 题相同（仅返回值不同）：
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(1)
02	遍历	O(n)	O(1)
03	双指针遍历	O(n)	O(1)
04	二分查找	O(log(n))	O(1)
04	二分查找(书上方法)	O(log(n))	O(1)

func search(nums []int, target int) int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			m[target]++
		}
	}
	return m[target]
}

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

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

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

#
func search(nums []int, target int) int {
	count := 0
	if len(nums) > 0 {
		first := getFirstK(nums, target, 0, len(nums)-1)
		last := getLastK(nums, target, 0, len(nums)-1)
		if first > -1 && last > -1 {
			count = last - first + 1
		}
	}
	return count
}

func getFirstK(nums []int, target int, start, end int) int {
	if start > end {
		return -1
	}
	mid := start + (end-start)/2
	if nums[mid] == target {
		if (mid > 0 && nums[mid-1] != target) || mid == 0 {
			return mid
		} else {
			end = mid - 1
		}
	} else if nums[mid] > target {
		end = mid - 1
	} else {
		start = mid + 1
	}
	return getFirstK(nums, target, start, end)
}

func getLastK(nums []int, target int, start, end int) int {
	if start > end {
		return -1
	}
	mid := start + (end-start)/2
	if nums[mid] == target {
		if (mid < len(nums)-1 && nums[mid+1] != target) || mid == len(nums)-1 {
			return mid
		} else {
			start = mid + 1
		}
	} else if nums[mid] < target {
		start = mid + 1
	} else {
		end = mid - 1
	}
	return getLastK(nums, target, start, end)
}

面试题53-II.0～n-1中缺失的数字(6)

• 题目

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:输入: [0,1,3] 输出: 2
示例 2:输入: [0,1,2,3,4,5,6,7,9] 输出: 8
限制：1 <= 数组长度 <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	数学计算	O(n)	O(1)
02	遍历	O(n)	O(1)
03	异或-位运算	O(n)	O(1)
04	哈希辅助	O(n)	O(n)
05	二分查找(书上方法)	O(log(n))	O(1)
06	内置函数	O(n)	O(1)

func missingNumber(nums []int) int {
	n := len(nums)
	sum := n * (n + 1) / 2
	for i := 0; i < n; i++ {
		sum = sum - nums[i]
	}
	return sum
}


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

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

# 4
func missingNumber(nums []int) int {
	m := make(map[int]bool)
	for i := range nums{
		m[nums[i]] = true
	}
	for i := 0; i <= len(nums); i++{
		if m[i] == false{
			return i
		}
	}
	return 0
}

# 5
func missingNumber(nums []int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] != mid {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

#
func missingNumber(nums []int) int {
	return sort.Search(len(nums), func(i int) bool {
		return nums[i] != i
	})
}

面试题54.二叉搜索树的第k大节点(3)

• 题目

给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4
限制：1 ≤ k ≤ 二叉搜索树元素个数

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归(书上方法)	O(n)	O(log(n))
02	递归+数组	O(n)	O(n)
03	迭代	O(n)	O(n)

var count int
var res int

func kthLargest(root *TreeNode, k int) int {
	count = k
	res = 0
	dfs(root)
	return res
}
func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	dfs(root.Right)
	count--
	if count == 0 {
		res = root.Val
		return
	}
	dfs(root.Left)
}

#
var arr []int

func kthLargest(root *TreeNode, k int) int {
	arr = make([]int, 0)
	dfs(root)
	return arr[k-1]
}

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

#
func kthLargest(root *TreeNode, k int) int {
	if root == nil {
		return 0
	}
	arr := make([]int, 0)
	stack := make([]*TreeNode, 0)
	cur := root
	for len(stack) > 0 || cur != nil {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		node := stack[len(stack)-1]
		arr = append(arr, node.Val)
		stack = stack[:len(stack)-1]
		cur = node.Right
	}
	return arr[len(arr)-k]
}

面试题55-I.二叉树的深度(2)

• 题目

输入一棵二叉树的根节点，求该树的深度。
从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。
提示：节点总数 <= 10000
注意：本题与主站 104 题相同：
https://leetcode.cn/problems/maximum-depth-of-binary-tree/

• 解题思路

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

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := maxDepth(root.Left)
	right := maxDepth(root.Right)

	return max(left, right) + 1
}

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

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

面试题55-II.平衡二叉树(2)

• 题目

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回 true 。
示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4]
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。
限制：1 <= 树的结点个数 <= 10000
注意：本题与主站 110 题相同：
https://leetcode.cn/problems/balanced-binary-tree/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(log(n))
02	递归(书上方法)	O(n)	O(log(n))

func isBalanced(root *TreeNode) bool {
	_, isBalanced := recur(root)
	return isBalanced
}

func recur(root *TreeNode) (int, bool) {
	if root == nil {
		return 0, true
	}
	leftDepth, leftIsBalanced := recur(root.Left)
	if leftIsBalanced == false {
		return 0, false
	}
	rightDepth, rightIsBalanced := recur(root.Right)
	if rightIsBalanced == false {
		return 0, false
	}
	if -1 <= leftDepth-rightDepth &&
		leftDepth-rightDepth <= 1 {
		return max(leftDepth, rightDepth) + 1, true
	}
	return 0, false
}

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

#
func isBalanced(root *TreeNode) bool {
	return dfs(root) != -1
}

func dfs(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := dfs(root.Left)
	right := dfs(root.Right)
	if left != -1 && right != -1 &&
		abs(left, right) <= 1 {
		return max(left, right) + 1
	}
	return -1
}

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

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

面试题56-I.数组中数字出现的次数(5)

• 题目

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1： 输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1]
示例 2：输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]
限制：
    2 <= nums.length <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	排序	O(nlog(n))	O(1)
03	位运算	O(n)	O(1)
04	位运算	O(n)	O(1)
05	位运算(书上方法)	O(n)	O(1)

func singleNumbers(nums []int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		m[nums[i]]++
	}
	res := make([]int, 0)
	for i := range m {
		if m[i] == 1 {
			res = append(res, i)
		}
	}
	return res
}

#
func singleNumbers(nums []int) []int {
	res := make([]int, 0)
	sort.Ints(nums)
	count := 0
	for i := 0; i < len(nums)-2; {
		if nums[i] == nums[i+1] {
			i = i + 2
		}
		if i == len(nums)-1 {
			res = append(res, nums[i])
			return res
		}
		if nums[i] != nums[i+1] {
			res = append(res, nums[i])
			i++
			count++
			if count == 2 {
				return res
			}
		}
	}
	return res
}

#
/*
a = 10
1.a   00001010
2.取反 11110101
3.取反+1 11110110
4. a & (-a)
00001010
11110110
00000010
*/
func singleNumbers(nums []int) []int {
	res := make([]int, 2)
	temp := 0
	for i := 0; i < len(nums); i++ {
		temp = temp ^ nums[i]
	}
	last := temp & (-temp)
	for i := 0; i < len(nums); i++ {
		if nums[i]&last == 0 {
			res[0] = res[0] ^ nums[i]
		} else {
			res[1] = res[1] ^ nums[i]
		}
	}
	return res
}

#
func singleNumbers(nums []int) []int {
	res := make([]int, 2)
	temp := 0
	for i := 0; i < len(nums); i++ {
		temp = temp ^ nums[i]
	}
	last := 1
	for temp&last == 0 {
		last = last << 1
	}
	for i := 0; i < len(nums); i++ {
		if nums[i]&last == 0 {
			res[0] = res[0] ^ nums[i]
		} else {
			res[1] = res[1] ^ nums[i]
		}
	}
	return res
}

#
func singleNumbers(nums []int) []int {
	res := make([]int, 2)
	temp := 0
	for i := 0; i < len(nums); i++ {
		temp = temp ^ nums[i]
	}
	index := firstBit(temp)
	for i := 0; i < len(nums); i++ {
		if isBit(nums[i], index) {
			res[0] = res[0] ^ nums[i]
		} else {
			res[1] = res[1] ^ nums[i]
		}
	}
	return res
}

func firstBit(num int) int {
	res := 0
	for num&1 == 0 {
		res++
		num = num >> 1
	}
	return res
}

func isBit(num int, index int) bool {
	num = num >> index
	return num&1 == 1
}

面试题56-II.数组中数字出现的次数II(5)

• 题目

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：输入：nums = [3,4,3,3] 输出：4
示例 2：输入：nums = [9,1,7,9,7,9,7] 输出：1
限制：
    1 <= nums.length <= 10000
    1 <= nums[i] < 2^31

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	哈希辅助	O(n)	O(n)
02	统计1的位求余(书上方法)	O(n)	O(1)
03	排序遍历	O(nlog(n))	O(1)
04	求和遍历	O(n)	O(n)
05	位运算(有限状态自动机)	O(n)	O(1)

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

# 2
func singleNumber(nums []int) int {
	arr := make([]int, 32)
	for i := 0; i < len(nums); i++ {
		value := nums[i]
		for j := 31; j >= 0; j-- {
			arr[j] = arr[j] + value&1
			value = value / 2
		}
	}
	res := 0
	for i := 0; i < 32; i++ {
		res = res << 1
		res = res + arr[i]%3
	}
	return res
}

# 3
func singleNumber(nums []int) int {
	sort.Ints(nums)
	if len(nums) == 1 {
		return nums[0]
	}
	i := 0
	for i < len(nums) {
		if i == len(nums)-1 {
			return nums[len(nums)-1]
		}
		if nums[i] == nums[i+1] {
			i = i + 3
		} else {
			return nums[i]
		}
	}
	return nums[i]
}

# 4
func singleNumber(nums []int) int {
	m := make(map[int]int)
	sum1 := 0
	sum2 := 0
	for i := 0; i < len(nums); i++ {
		sum1 = sum1 + nums[i]
		if _, ok := m[nums[i]]; !ok {
			sum2 = sum2 + nums[i]
		}
		m[nums[i]]++
	}
	return (sum2*3 - sum1) / 2
}

# 5
func singleNumber(nums []int) int {
	res, temp := 0, 0
	for i := 0; i < len(nums); i++ {
		res = (res ^ nums[i]) & ^temp
		temp = (temp ^ nums[i]) & ^res
	}
	return res
}

面试题57.和为s的两个数字(2)

• 题目

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
如果有多对数字的和等于s，则输出任意一对即可。
示例 1：输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]
示例 2：输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针(书上方法)	O(n)	O(1)
02	哈希辅助	O(n)	O(n)

func twoSum(nums []int, target int) []int {
	i := 0
	j := len(nums) - 1
	for i < j {
		sum := nums[i] + nums[j]
		if sum == target {
			return []int{nums[i], nums[j]}
		} else if sum > target {
			j--
		} else {
			i++
		}
	}
	return nil
}

#
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{nums[j], nums[i]}
		}
		m[b] = i
	}
	return nil
}

面试题57-II.和为s的连续正数序列(4)

• 题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：输入：target = 9 输出：[[2,3,4],[4,5]]
示例 2：输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：1 <= target <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双指针	O(n)	O(1)
02	双指针(书上方法)	O(n)	O(1)
03	前缀和-暴力法	O(n^2)	O(n)
04	数学法	O(n)	O(1)

func findContinuousSequence(target int) [][]int {
	res := make([][]int, 0)
	i := 1
	j := 2
	for i < j {
		sum := (i + j) * (j - i + 1) / 2
		if sum == target {
			arr := make([]int, 0)
			for k := i; k <= j; k++ {
				arr = append(arr, k)
			}
			res = append(res, arr)
			i++
		} else if sum < target {
			j++
		} else {
			i++
		}
	}
	return res
}

#
func findContinuousSequence(target int) [][]int {
	res := make([][]int, 0)
	i := 1
	j := 2
	mid := (1 + target) / 2
	curSum := i + j
	for i < mid {
		if curSum == target {
			arr := make([]int, 0)
			for k := i; k <= j; k++ {
				arr = append(arr, k)
			}
			res = append(res, arr)
		}
		for curSum > target && i < mid {
			curSum = curSum - i
			i++
			if curSum == target {
				arr := make([]int, 0)
				for k := i; k <= j; k++ {
					arr = append(arr, k)
				}
				res = append(res, arr)
			}
		}
		j++
		curSum = curSum + j
	}
	return res
}

#
func findContinuousSequence(target int) [][]int {
	res := make([][]int, 0)
	arr := make([]int, target+1)
	for i := 1; i <= target; i++ {
		arr[i] = arr[i-1] + i
	}
	for i := 1; i <= (target+1)/2; i++ {
		for j := i + 1; j <= target && arr[j]-arr[i-1] <= target; j++ {
			if arr[j]-arr[i-1] == target {
				temp := make([]int, 0)
				for k := i; k <= j; k++ {
					temp = append(temp, k)
				}
				res = append(res, temp)
				break
			}
		}
	}
	return res
}

#
// target = nA1 + n(n-1)/2
func findContinuousSequence(target int) [][]int {
	res := make([][]int, 0)
	for i := (target + 1) / 2; i >= 2; i-- {
		nA1 := target - i*(i-1)/2
		if nA1 <= 0 {
			continue
		}
		if nA1%i == 0 {
			start := nA1 / i
			arr := make([]int, 0)
			for j := 0; j < i; j++ {
				arr = append(arr, start+j)
			}
			res = append(res, arr)
		}
	}
	return res
}

面试题58-I.翻转单词顺序(3)

• 题目

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
为简单起见，标点符号和普通字母一样处理。
例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：输入: "the sky is blue"  输出: "blue is sky the"
示例 2：输入: "  hello world!  " 输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：输入: "a good   example" 输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
    无空格字符构成一个单词。
    输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
注意：本题与主站 151 题相同：https://leetcode.cn/problems/reverse-words-in-a-string/
注意：此题对比原题有改动

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	内置函数	O(n)	O(n)
02	遍历-2次反转(书上方法)	O(n)	O(n)
03	遍历	O(n)	O(n)

func reverseWords(s string) string {
	s = strings.Trim(s, " ")
	arr := strings.Fields(s)
	for i := 0; i < len(arr)/2; i++ {
		arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]
	}
	return strings.Join(arr, " ")
}

#
func reverseWords(s string) string {
	arr := []byte(s)
	arr = reverse(arr)
	i := 0
	j := 0
	res := ""
	flag := false
	for i < len(arr) {
		if arr[i] == ' ' {
			if flag == true {
				res = res + " " + string(reverse(arr[j:i]))
				flag = false
			}
			i++
			j = i
		} else {
			i++
			if i == len(arr) {
				res = res + " " + string(reverse(arr[j:i]))
			}
			flag = true
		}
	}
	if len(res) > 0 {
		return res[1:]
	}
	return res
}

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

#
func reverseWords(s string) string {
	arr := []byte(s)
	i := len(arr) - 1
	j := len(arr)
	res := ""
	flag := false
	for i >= 0 {
		if arr[i] == ' ' {
			if flag == true {
				res = res + " " + string(arr[i+1:j])
				flag = false
			}
			j = i
			i--
		} else {
			if i == 0 {
				res = res + " " + string(arr[i:j])
			}
			i--
			flag = true
		}
	}
	if len(res) > 0 {
		return res[1:]
	}
	return res
}

面试题58-II.左旋转字符串(2)

• 题目

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。
比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：输入: s = "abcdefg", k = 2 输出: "cdefgab"
示例 2：输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
限制： 1 <= k < s.length <= 10000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	切片	O(n)	O(n)
02	三次反转(书上方法)	O(n)	O(n)

func reverseLeftWords(s string, n int) string {
	n = n % len(s)
	return s[n:] + s[:n]
}

#
func reverseLeftWords(s string, n int) string {
	n = n % len(s)
	arr := []byte(s)
	reverse(arr, 0, n-1)
	reverse(arr, n, len(arr)-1)
	reverse(arr, 0, len(arr)-1)
	return string(arr)
}

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

面试题59-I.滑动窗口的最大值(4)

• 题目

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 
解释: 
  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
提示：你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
注意：本题与主站 239 题相同：https://leetcode.cn/problems/sliding-window-maximum/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(n)
02	暴力法-有条件更新最大值	O(n^2)	O(n)
03	双端队列(书上方法)	O(n)	O(n)
04	堆排序	O(nlog(n))	O(n)

func maxSlidingWindow(nums []int, k int) []int {
	res := make([]int, 0)
	if len(nums) == 0 {
		return res
	}
	for i := 0; i < len(nums)-k+1; i++ {
		max := nums[i]
		for j := i; j < i+k; j++ {
			if nums[j] > max {
				max = nums[j]
			}
		}
		res = append(res, max)
	}
	return res
}

#
func maxSlidingWindow(nums []int, k int) []int {
	res := make([]int, 0)
	if len(nums) == 0 {
		return res
	}
	max := math.MaxInt32
	for i := 0; i < len(nums)-k+1; i++ {
		if i == 0 || nums[i-1] == max {
			max = nums[i]
			for j := i; j < i+k; j++ {
				if nums[j] > max {
					max = nums[j]
				}
			}
		} else {
			if nums[i+k-1] > max {
				max = nums[i+k-1]
			}
		}
		res = append(res, max)
	}
	return res
}

#
func maxSlidingWindow(nums []int, k int) []int {
	res := make([]int, 0)
	if len(nums) == 0 {
		return res
	}
	deque := make([]int, 0)
	for i := 0; i < k; i++ {
		for len(deque) > 0 && nums[i] >= nums[deque[len(deque)-1]] {
			deque = deque[:len(deque)-1]
		}
		deque = append(deque, i)
	}
	for i := k; i < len(nums); i++ {
		res = append(res, nums[deque[0]])
		for len(deque) > 0 && nums[i] >= nums[deque[len(deque)-1]] {
			deque = deque[:len(deque)-1]
		}
		if len(deque) > 0 && deque[0] <= i-k {
			deque = deque[1:]
		}
		deque = append(deque, i)
	}
	res = append(res, nums[deque[0]])
	return res
}

#
func maxSlidingWindow(nums []int, k int) []int {
	res := make([]int, 0)
	if len(nums) == 0 {
		return res
	}
	intHeap := make(IntHeap, 0, k)
	heap.Init(&intHeap)
	for i := 0; i < k; i++ {
		heap.Push(&intHeap, nums[i])
	}
	for i := k; i < len(nums); i++ {
		temp := heap.Pop(&intHeap).(int)
		res = append(res, temp)
		if temp != nums[i-k] {
			intHeap.Remove(nums[i-k])
			heap.Push(&intHeap, temp)
			heap.Push(&intHeap, nums[i])
		} else {
			heap.Push(&intHeap, nums[i])
		}
	}
	res = append(res, heap.Pop(&intHeap).(int))
	return res
}

type IntHeap []int

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

func (i IntHeap) Less(x, y int) bool {
	return i[x] > i[y]
}

func (i IntHeap) Swap(x, y int) {
	i[x], i[y] = i[y], i[x]
}
func (i *IntHeap) Push(v interface{}) {
	*i = append(*i, v.(int))
}

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

func (i *IntHeap) Remove(x interface{}) {
	for j := 0; j < len(*i); j++ {
		if (*i)[j] == x {
			*i = append((*i)[:j], (*i)[j+1:]...)
			break
		}
	}
	heap.Init(i)
}

面试题59-II.队列的最大值(2)

• 题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，
要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
限制：
    1 <= push_back,pop_front,max_value的总操作数 <= 10000
    1 <= value <= 10^5

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	双队列(书上方法)	O(1)	O(n)
02	内置list	O(1)	O(n)

type MaxQueue struct {
	data []int
	max  []int
}

func Constructor() MaxQueue {
	return MaxQueue{
		data: make([]int, 0),
		max:  make([]int, 0),
	}
}

func (this *MaxQueue) Max_value() int {
	if len(this.max) == 0 {
		return -1
	}
	return this.max[0]
}

func (this *MaxQueue) Push_back(value int) {
	this.data = append(this.data, value)
	for len(this.max) > 0 && value > this.max[len(this.max)-1] {
		this.max = this.max[:len(this.max)-1]
	}
	this.max = append(this.max, value)
}

func (this *MaxQueue) Pop_front() int {
	res := -1
	if len(this.data) > 0 {
		res = this.data[0]
		this.data = this.data[1:]
		if res == this.max[0] {
			this.max = this.max[1:]
		}
	}
	return res
}

#
type MaxQueue struct {
	data *list.List
	max  []int
}

func Constructor() MaxQueue {
	return MaxQueue{
		data:list.New(),
		max:  make([]int, 0),
	}
}

func (this *MaxQueue) Max_value() int {
	if len(this.max) == 0 {
		return -1
	}
	return this.max[0]
}

func (this *MaxQueue) Push_back(value int) {
	this.data.PushBack(value)
	for len(this.max) > 0 && value > this.max[len(this.max)-1] {
		this.max = this.max[:len(this.max)-1]
	}
	this.max = append(this.max, value)
}

func (this *MaxQueue) Pop_front() int {
	res := -1
	if this.data.Len() > 0 {
		res = this.data.Front().Value.(int)
		this.data.Remove(this.data.Front())
		if res == this.max[0] {
			this.max = this.max[1:]
		}
	}
	return res
}

面试题60.n个骰子的点数(2)

• 题目

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:输入: 2 输出: 
[0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,
0.08333,0.05556,0.02778]
限制：
1 <= n <= 11

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递推-数组辅助(书上方法)	O(n)	O(n)
02	递推-动态规划	O(n)	O(n)
03	递归-超时(书上方法)	O(6^n)	O(n)

func twoSum(n int) []float64 {
	res := make([]float64, 0)
	if n < 1 {
		return res
	}
	arr := [2][]int{}
	arr[0] = make([]int, 6*n+1)
	arr[1] = make([]int, 6*n+1)
	flag := 0
	for i := 1; i <= 6; i++ {
		arr[flag][i] = 1
	}
	for k := 2; k <= n; k++ {
		for i := 0; i < k; i++ {
			arr[1-flag][i] = 0
		}
		for i := k; i <= 6*n; i++ {
			arr[1-flag][i] = 0
			// 当前轮的第N位等于前一个数组第N-1,N-2,N-3,N-4,N-5,N-6位之和
			for j := 1; j <= i && j <= 6; j++ {
				arr[1-flag][i] += arr[flag][i-j]
			}
		}
		flag = 1 - flag
	}
	total := math.Pow(float64(6), float64(n))
	for i := n; i <= 6*n; i++ {
		ratio := float64(arr[flag][i]) / total
		res = append(res, ratio)
	}
	return res
}

#
// f(n,k)=f(n−1,k−1)+f(n−1,k−2)+f(n−1,k−3)+f(n−1,k−4)+f(n−1,k−5)+f(n−1,k−6)
func twoSum(n int) []float64 {
	res := make([]float64, 0)
	if n < 1 {
		return res
	}
	arr := make([]int, 6*n+1)
	for i := 1; i <= 6; i++ {
		arr[i] = 1
	}
	for i := 2; i <= n; i++ {
		for j := 6 * i; j >= i; j-- {
			arr[j] = 0
			for k := 1; k <= 6; k++ {
				if j-k >= i-1 {
					arr[j] = arr[j] + arr[j-k]
				}
			}
		}
	}
	total := math.Pow(float64(6), float64(n))
	for i := n; i <= 6*n; i++ {
		ratio := float64(arr[i]) / total
		res = append(res, ratio)
	}
	return res
}

#
var arr []int
var start int

func twoSum(n int) []float64 {
	res := make([]float64, 0)
	if n < 1 {
		return res
	}
	start = n
	arr = make([]int, 5*n+1)
	for i := 1; i <= 6; i++ {
		dfs(n, i)
	}
	total := math.Pow(float64(6), float64(n))
	for i := n; i <= 6*n; i++ {
		ratio := float64(arr[i-n]) / total
		res = append(res, ratio)
	}
	return res
}

func dfs(current, sum int) {
	if current == 1 {
		arr[sum-start]++
	} else {
		for i := 1; i <= 6; i++ {
			dfs(current-1, sum+i)
		}
	}
}

面试题61.扑克牌中的顺子(3)

• 题目

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:输入: [1,2,3,4,5] 输出: True
示例 2:输入: [0,0,1,2,5] 输出: True
限制：数组长度为 5 数组的数取值为 [0, 13] .

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	排序遍历	O(1)	O(1)
02	哈希辅助	O(1)	O(1)
03	排序遍历(书上方法)	O(1)	O(1)

func isStraight(nums []int) bool {
	sort.Ints(nums)
	sum := 0
	for i := 0; i < 4; i++ {
		if nums[i] == 0 {
			continue
		}
		// 非王重复
		if nums[i] == nums[i+1] {
			return false
		}
		sum = sum + nums[i+1] - nums[i]
	}
	return sum <= 4
}

#
func isStraight(nums []int) bool {
	m := make(map[int]bool)
	max, min := -1, 14
	countZero := 0
	for i := 0; i < 5; i++ {
		if nums[i] == 0 {
			countZero++
			continue
		}
		if m[nums[i]] {
			return false
		}
		m[nums[i]] = true
		if nums[i] > max {
			max = nums[i]
		}
		if nums[i] < min {
			min = nums[i]
		}
	}
	if countZero == 0 {
		return max-min == 4
	}
	return max-min <= 4
}

#
func isStraight(nums []int) bool {
	sort.Ints(nums)
	zero := 0
	gap := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			zero++
		}
	}
	small := zero
	big := small + 1
	for big < len(nums) {
		if nums[small] == nums[big] {
			return false
		}
		gap = gap + nums[big] - nums[small] - 1
		small++
		big++
	}
	if gap > zero {
		return false
	}
	return true
}

面试题62.圆圈中最后剩下的数字(2)

• 约瑟夫环理解参考： https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/

• 题目

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。
求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，
则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：输入: n = 5, m = 3 输出: 3
示例 2：输入: n = 10, m = 17 输出: 2
限制：
    1 <= n <= 10^5
    1 <= m <= 10^6

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	递归	O(n)	O(n)
02	递推(书上方法)	O(n)	O(1)
03	模拟-超时	O(n^2)	O(n)

func lastRemaining(n int, m int) int {
	if n == 1 {
		return 0
	}
	return (lastRemaining(n-1, m) + m) % n
}

# 2
func lastRemaining(n int, m int) int {
	res := 0
	for i := 2; i <= n; i++ {
		res = (res + m) % i
	}
	return res
}

# 超时
func lastRemaining(n int, m int) int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = i
	}
	last := 0
	for len(arr) > 1 {
		index := (last + m - 1) % len(arr)
		arr = remove(arr, index)
		last = index
	}
	return arr[0]
}

func remove(arr []int, index int) []int {
	if index == 0 {
		return arr[1:]
	}
	if index == len(arr)-1 {
		return arr[:len(arr)-1]
	}
	return append(arr[:index], arr[index+1:]...)
}

面试题63.股票的最大利润(3)

• 题目

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:输入: [7,1,5,3,6,4] 输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，
最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:输入: [7,6,4,3,1] 输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
限制： 0 <= 数组长度 <= 10^5
注意：本题与主站 121 题相同：
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	暴力法	O(n^2)	O(1)
02	动态规划(从前到后) 最大利润=max{前一天最大利润, 今天的价格 - 之前最低价格}(书上方法)	O(n)	O(1)
03	动态规划(从后到前)	O(n)	O(1)

func maxProfit(prices []int) int {
	max := 0
	length := len(prices)
	for i := 0; i < length-1; i++ {
		for j := i + 1; j <= length-1; j++ {
			if prices[j]-prices[i] > max {
				max = prices[j] - prices[i]
			}
		}
	}
	return max
}

#
func maxProfit(prices []int) int {
	if len(prices) < 2 {
		return 0
	}
	min := prices[0]
	profit := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] < min {
			min = prices[i]
		}
		if profit < prices[i]-min {
			profit = prices[i] - min
		}
	}
	return profit
}

#
func maxProfit(prices []int) int {
	if len(prices) < 2 {
		return 0
	}
	max := 0
	profit := 0
	for i := len(prices) - 1; i >= 0; i-- {
		if max < prices[i] {
			max = prices[i]
		}
		if profit < max-prices[i] {
			profit = max - prices[i]
		}
	}
	return profit
}

面试题64.求1+2+…+n(2)

• 题目

求 1+2+...+n ，要求不能使用乘除法、
for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：输入: n = 3 输出: 6
示例 2：输入: n = 9 输出: 45
限制：1 <= n <= 10000

• 解题思路

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

var res int

func sumNums(n int) int {
	res = 0
	dfs(n)
	return res
}

func dfs(n int) bool {
	res = res + n
	return n > 0 && dfs(n-1)
}

#
func sumNums(n int) int {
	return (int(math.Pow(float64(n), float64(2))) + n) >> 1
}

面试题65.不用加减乘除做加法(2)

• 题目

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:输入: a = 1, b = 1 输出: 2
提示：
    a, b 均可能是负数或 0
    结果不会溢出 32 位整数

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	迭代(书上方法)	O(1)	O(1)
02	递归	O(1)	O(1)

// 非进位和：异或运算
// 进位：与运算+左移一位
func add(a int, b int) int {
	for b != 0 {
		a, b = a^b, (a&b)<<1
	}
	return a
}

#
func add(a int, b int) int {
	if b == 0 {
		return a
	}
	return add(a^b, (a&b)<<1)
}

面试题66.构建乘积数组(2)

• 题目

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:输入: [1,2,3,4,5] 输出: [120,60,40,30,24]
提示：所有元素乘积之和不会溢出 32 位整数
    a.length <= 100000

• 解题思路

No.	思路	时间复杂度	空间复杂度
01	二次遍历(书上方法)	O(n)	O(1)
02	数组辅助	O(n)	O(n)

func constructArr(a []int) []int {
	res := make([]int, len(a))
	if len(a) == 0 {
		return res
	}
	res[0] = 1
	for i := 1; i < len(res); i++ {
		res[i] = res[i-1] * a[i-1]
	}
	temp := 1
	for i := len(res) - 2; i >= 0; i-- {
		res[i] = res[i] * a[i+1] * temp
		temp = temp * a[i+1]
	}
	return res
}

#
func constructArr(a []int) []int {
	res := make([]int, len(a))
	if len(a) == 0 {
		return res
	}
	left := make([]int, len(a))
	left[0] = 1
	right := make([]int, len(a))
	right[len(a)-1] = 1
	for i := 1; i < len(a); i++ {
		left[i] = left[i-1] * a[i-1]
	}
	for i := len(a) - 2; i >= 0; i-- {
		right[i] = right[i+1] * a[i+1]
	}
	for i := 0; i < len(a); i++ {
		res[i] = left[i] * right[i]
	}
	return res
}

面试题67.把字符串转换成整数(2)

• 题目

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 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 因此返回 INT_MIN (−231) 。
注意：本题与主站 8 题相同：https://leetcode.cn/problems/string-to-integer-atoi/

• 解题思路

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

func strToInt(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 strToInt(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
}