程序员面试金典

面试题01.01.判定字符是否唯一(5)

  • 题目

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：输入: s = "leetcode" 输出: false 
示例 2：输入: s = "abc" 输出: true
限制：
    0 <= len(s) <= 100
    如果你不使用额外的数据结构，会很加分。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(1)
02 位运算 O(n) O(1)
03 遍历 O(n^2) O(1)
04 排序遍历 O(nlog(n)) O(n)
05 数组辅助 O(n) O(1) 
func isUnique(astr string) bool {
	m := make(map[byte]bool)
	for i := 0; i < len(astr); i++ {
		if m[astr[i]] == true {
			return false
		}
		m[astr[i]] = true
	}
	return true
}

# 2
func isUnique(astr string) bool {
	value := uint32(0)
	for i := 0; i < len(astr); i++ {
		index := astr[i] - 'a'
		if value&(1<<index) == (1 << index) {
			return false
		}
		value = value ^ (1 << index)
	}
	return true
}

# 3
func isUnique(astr string) bool {
	for i := 0; i < len(astr); i++ {
		for j := i + 1; j < len(astr); j++ {
			if astr[i] == astr[j] {
				return false
			}
		}
	}
	return true
}

# 4
func isUnique(astr string) bool {
	arr := []byte(astr)
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})
	for i := 1; i < len(arr); i++ {
		if arr[i] == arr[i-1] {
			return false
		}
	}
	return true
}

# 5
func isUnique(astr string) bool {
	arr := make([]int, 256)
	for i := 0; i < len(astr); i++ {
		if arr[astr[i]] > 0 {
			return false
		}
		arr[astr[i]] = 1
	}
	return true
}

面试题01.02.判定是否互为字符重排(2)

  • 题目

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
示例 1：输入: s1 = "abc", s2 = "bca" 输出: true 
示例 2：输入: s1 = "abc", s2 = "bad" 输出: false
说明：
    0 <= len(s1) <= 100
    0 <= len(s2) <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 内置函数 O(nlog(n)) O(n)
02 哈希辅助 O(n) O(1)
03 数组辅助 O(n) O(1) 
func CheckPermutation(s1 string, s2 string) bool {
	arr1 := strings.Split(s1, "")
	arr2 := strings.Split(s2, "")
	sort.Strings(arr1)
	sort.Strings(arr2)
	return strings.Join(arr1,"") == strings.Join(arr2,"")
	// return reflect.DeepEqual(arr1, arr2)
}

#
func CheckPermutation(s1 string, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	m := make(map[byte]int)
	for i := 0; i < len(s1); i++ {
		m[s1[i]]++
		m[s2[i]]--
	}
	for _, v := range m {
		if v != 0 {
			return false
		}
	}
	return true
}

#
func CheckPermutation(s1 string, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	arr := [256]int{}
	for i := 0; i < len(s1); i++ {
		arr[s1[i]]++
		arr[s2[i]]--
	}
	for _, v := range arr {
		if v != 0 {
			return false
		}
	}
	return true
}

面试题01.03.URL化(2)

  • 题目

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，
并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
示例1:输入："Mr John Smith    ", 13 输出："Mr%20John%20Smith"
示例2:输入："               ", 5 输出："%20%20%20%20%20"
提示：
    字符串长度在[0, 500000]范围内。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(n)
02 遍历 O(n) O(n) 
func replaceSpaces(S string, length int) string {
	return strings.ReplaceAll(S[:length], " ","%20")
}

#
func replaceSpaces(S string, length int) string {
	res := make([]byte,0)
	for i := 0; i < length; i++ {
		if S[i] == ' ' {
			res = append(res,'%')
			res = append(res,'2')
			res = append(res,'0')
		} else {
			res = append(res,S[i])
		}
	}
	return string(res)
}

面试题01.04.回文排列(2)

  • 题目

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例1：输入："tactcoa" 输出：true（排列有"tacocat"、"atcocta"，等等）

  • 解题思路

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

#
func canPermutePalindrome(s string) bool {
	arr := [256]int{}
	for i := 0; i < len(s); i++ {
		arr[s[i]]++
	}
	count := 0
	for i := 0; i < len(arr); i++{
		if arr[i] % 2== 1{
			count++
		}
	}
	return count <= 1
}

面试题01.05.一次编辑(2)

  • 题目

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。
给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:输入: first = "pale"second = "ple" 输出: True
示例 2:输入: first = "pales"second = "pal" 输出: False

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 遍历 O(n) O(1) 
func oneEditAway(first string, second string) bool {
	if len(first)-len(second) > 1 || len(second)-len(first) > 1 {
		return false
	}
	if first == second {
		return true
	}
	i := 0
	for ; i < len(first) && i < len(second); i++ {
		if first[i] != second[i] {
			if len(first) == len(second) {
				if first[i+1:] == second[i+1:] {
					return true
				}
			} else if len(first) < len(second) {
				if first[i:] == second[i+1:] {
					return true
				}
			} else {
				if first[i+1:] == second[i:] {
					return true
				}
			}
			break
		}
	}
	if i == len(first) || i == len(second) {
		return true
	}
	return false
}

#
func oneEditAway(first string, second string) bool {
	if len(first)-len(second) > 1 || len(second)-len(first) > 1 {
		return false
	}
	if first == second {
		return true
	}
	if len(first) > len(second) {
		first, second = second, first
	}
	for i := 0; i < len(first); i++ {
		if first[i] == second[i] {
			continue
		}
		return first[i:] == second[i+1:] || first[i+1:] == second[i+1:]
	}
	return true
}

面试题01.06.字符串压缩(2)

  • 题目

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。
你可以假设字符串中只包含大小写英文字母（a至z）。
示例1:输入："aabcccccaaa" 输出："a2b1c5a3"
示例2:输入："abbccd" 输出："abbccd" 
解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
提示：字符串长度在[0, 50000]范围内。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 双指针 O(n) O(n) 
func compressString(S string) string {
	if len(S) <= 1 {
		return S
	}
	prev := S[0]
	count := 1
	res := ""
	for i := 1; i < len(S); i++ {
		if prev == S[i] {
			count++
		} else {
			res = res + string(prev) + strconv.Itoa(count)
			prev = S[i]
			count = 1
		}
	}
	res = res + string(prev) + strconv.Itoa(count)
	if len(res) >= len(S) {
		return S
	}
	return res
}

#
func compressString(S string) string {
	if len(S) <= 1 {
		return S
	}
	i := 0
	j := 0
	res := ""
	for j = 1; j < len(S); j++ {
		if S[i] != S[j] {
			res = res + string(S[i]) + strconv.Itoa(j-i)
			i = j
		}
	}
	res = res + string(S[i]) + strconv.Itoa(j-i)
	if len(res) >= len(S) {
		return S
	}
	return res
}

面试题01.07.旋转矩阵(3)

  • 题目

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
示例 1:给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
示例 2:给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 
原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(1)
02 遍历 O(n^2) O(1)
03 数组辅助 O(n^2) O(n^2) 
func rotate(matrix [][]int) {
	n := len(matrix)
	// 同行逆置
	// [[1 2 3] [4 5 6] [7 8 9]]
	// [[3 2 1] [6 5 4] [9 8 7]]
	for i := 0; i < n; i++ {
		for j := 0; j < n/2; j++ {
			matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
		}
	}
	// 左下右上对角线对互换
	// [[3 2 1] [6 5 4] [9 8 7]]
	// [[7 4 1] [8 5 2] [9 6 3]]
	for i := 0; i < n-1; i++ {
		for j := 0; j < n-1-i; j++ {
			matrix[i][j], matrix[n-1-j][n-1-i] = matrix[n-1-j][n-1-i], matrix[i][j]
		}
	}
}

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

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

面试题01.08.零矩阵(4)

  • 题目

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
示例 1：输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
示例 2：输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^2) O(n)
02 暴力法 O(n^4) O(1)
03 遍历 O(n^2) O(1)
04 遍历 O(n^2) O(1) 
func setZeroes(matrix [][]int) {
	x := make(map[int]int)
	y := make(map[int]int)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == 0 {
				x[i] = 1
				y[j] = 1
			}
		}
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if x[i] == 1 || y[j] == 1 {
				matrix[i][j] = 0
			}
		}
	}
}

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

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

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

面试题01.09.字符串轮转(2)

  • 题目

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（
比如，waterbottle是erbottlewat旋转后的字符串）。
示例1: 输入：s1 = "waterbottle", s2 = "erbottlewat" 输出：True
示例2:输入：s1 = "aa", s2 = "aba" 输出：False
提示：字符串长度在[0, 100000]范围内。
说明: 你能只调用一次检查子串的方法吗？

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n) O(1)
02 遍历 O(n) O(1) 
func isFlipedString(s1 string, s2 string) bool {
	if len(s1) != len(s2){
		return false
	}
	return strings.Contains(s1+s1, s2)
}

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

面试题02.01.移除重复节点(3)

  • 题目

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:输入：[1, 2, 3, 3, 2, 1]输出：[1, 2, 3]
示例2:输入：[1, 1, 1, 1, 2]输出：[1, 2]
提示：
    链表长度在[0, 20000]范围内。
    链表元素在[0, 20000]范围内。
进阶：如果不得使用临时缓冲区，该怎么解决？

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 遍历 O(n^2) O(1)
03 递归 O(n) O(n) 
func removeDuplicateNodes(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	m := make(map[int]bool)
	m[head.Val] = true
	temp := head
	for temp.Next != nil {
		if m[temp.Next.Val] == true {
			temp.Next = temp.Next.Next
		} else {
			m[temp.Next.Val] = true
			temp = temp.Next
		}
	}
	return head
}

# 2
func removeDuplicateNodes(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	temp := head
	for temp != nil {
		second := temp
		for second.Next != nil {
			if second.Next.Val == temp.Val {
				second.Next = second.Next.Next
			} else {
				second = second.Next
			}
		}
		temp = temp.Next
	}
	return head
}

# 3
var m map[int]bool

func removeDuplicateNodes(head *ListNode) *ListNode {
	m = make(map[int]bool)
	return remove(head)

}

func remove(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	if m[head.Val] == true {
		return remove(head.Next)
	}
	m[head.Val] = true
	head.Next = remove(head.Next)
	return head
}

面试题02.02.返回倒数第k个节点(4)

  • 题目

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：输入： 1->2->3->4->5 和 k = 2 输出： 4
说明：给定的 k 保证是有效的。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数组辅助 O(n) O(n)
02 快慢指针 O(n) O(1)
03 统计+遍历 O(n) O(1)
04 递归 O(n) O(n) 
func kthToLast(head *ListNode, k int) int {
	arr := make([]*ListNode, 0)
	for head != nil {
		arr = append(arr, head)
		head = head.Next
	}
	if len(arr) >= k {
		return arr[len(arr)-k].Val
	}
	return -1
}

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

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

# 4
func kthToLast(head *ListNode, k int) int {
	res, count := dfs(head, k)
	if count > 0 {
		return -1
	}
	return res.Val
}

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
}

面试题02.03.删除中间节点(1)

  • 题目

实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。
示例：输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 把当前节点替换成下一个节点 O(1) O(1) 
func deleteNode(node *ListNode) {
	// *node = *node.Next
	node.Val = node.Next.Val
	node.Next = node.Next.Next
}

面试题02.04.分割链表(2)

  • 题目

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。
如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。
分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。
示例:输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 双指针 O(n) O(1)
02 数组辅助 O(n) O(n) 
func partition(head *ListNode, x int) *ListNode {
	first := &ListNode{}
	second := &ListNode{}
	a := first
	b := second
	for head != nil {
		if head.Val < x {
			a.Next = head
			a = head
		} else {
			b.Next = head
			b = head
		}
		head = head.Next
	}
	b.Next = nil
	a.Next = second.Next
	return first.Next
}

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

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

面试题02.05.链表求和(2)

  • 题目

给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912
进阶：假设这些数位是正向存放的，请再做一遍。
示例：输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295 输出：9 -> 1 -> 2，即912

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 递归 O(n) O(n) 
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	res := &ListNode{}
	cur := res
	carry := 0
	for l1 != nil || l2 != nil || carry > 0 {
		sum := carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		carry = sum / 10 // 进位
		cur.Next = &ListNode{Val: sum % 10}
		cur = cur.Next
	}
	return res.Next
}

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

面试题02.06.回文链表(4)

  • 题目

编写一个函数，检查输入的链表是否是回文的。
示例 1：输入： 1->2 输出： false 
示例 2：输入： 1->2->2->1 输出： true 
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数组辅助 O(n) O(n)
02 快慢指针反转链表 O(n) O(1)
03 栈辅助 O(n) O(n)
04 递归 O(n) O(n) 
func isPalindrome(head *ListNode) bool {
	m := make([]int, 0)
	for head != nil {
		m = append(m, head.Val)
		head = head.Next
	}
	i, j := 0, len(m)-1
	for i < j {
		if m[i] != m[j] {
			return false
		}
		i++
		j--
	}
	return true
}

# 2
func isPalindrome(head *ListNode) bool {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	var pre *ListNode
	cur := slow
	for cur != nil{
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	for pre != nil{
		if head.Val != pre.Val{
			return false
		}
		pre = pre.Next
		head = head.Next
	}
	return true
}

# 3
func isPalindrome(head *ListNode) bool {
	m := make([]int, 0)
	temp := head
	for temp != nil {
		m = append(m, temp.Val)
		temp = temp.Next
	}
	for head != nil {
		val := m[len(m)-1]
		m = m[:len(m)-1]
		if head.Val != val {
			return false
		}
		head = head.Next
	}
	return true
}

# 4
var p *ListNode
func isPalindrome(head *ListNode) bool {
	if head == nil{
		return true
	}
	if p == nil{
		p = head
	}
	if isPalindrome(head.Next) && (p.Val == head.Val){
		p = p.Next
		return true
	}
	p = nil
	return false
}

面试题02.07.链表相交(4)

  • 题目

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。
换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
示例 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) 内存。

  • 解题思路

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
}

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

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

面试题02.08.环路检测(3)

  • 题目

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。
示例 1：输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：输入：head = [1,2], pos = 0 输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：输入：head = [1], pos = -1 输出：no cycle
解释：链表中没有环。
进阶：你是否可以不用额外空间解决此题？

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 快慢指针 O(n) O(1)
03 遍历标记 O(n) O(1) 
func detectCycle(head *ListNode) *ListNode {
	m := make(map[*ListNode]bool)
	for head != nil {
		if m[head] {
			return head
		}
		m[head] = true
		head = head.Next
	}
	return nil
}

# 2
func detectCycle(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			break
		}
	}
	if fast == nil || fast.Next == nil {
		return nil
	}
	slow = head
	for fast != slow {
		fast = fast.Next
		slow = slow.Next
	}
	return slow
}

# 3
func detectCycle(head *ListNode) *ListNode {
	for head != nil {
		if head.Val == math.MaxInt32 {
			return head
		}
		head.Val = math.MaxInt32
		head = head.Next
	}
	return head
}

面试题03.01.三合一(1)

  • 题目

三合一。描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。
构造函数会传入一个stackSize参数，代表每个栈的大小。
示例1:输入：["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]
 输出：[null, null, null, 1, -1, -1, true]
说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。
示例2:输入： ["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
 输出：[null, null, null, null, 2, 1, -1, -1]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数组 O(1) O(n) 
type TripleInOne struct {
	arr    []int
	length int
	index  [3]int
}

func Constructor(stackSize int) TripleInOne {
	return TripleInOne{
		arr:    make([]int, stackSize*3),
		length: stackSize,
		index:  [3]int{0, 0, 0},
	}
}

func (this *TripleInOne) Push(stackNum int, value int) {
	if this.index[stackNum] < this.length {
		this.arr[3*this.index[stackNum]+stackNum] = value
		this.index[stackNum]++
	}
}

func (this *TripleInOne) Pop(stackNum int) int {
	res := -1
	if this.index[stackNum] != 0 {
		this.index[stackNum]--
		res = this.arr[3*this.index[stackNum]+stackNum]
	}
	return res
}

func (this *TripleInOne) Peek(stackNum int) int {
	res := -1
	if this.index[stackNum] != 0 {
		res = this.arr[3*(this.index[stackNum]-1)+stackNum]
	}
	return res
}

func (this *TripleInOne) IsEmpty(stackNum int) bool {
	if this.index[stackNum] == 0 {
		return true
	}
	return false
}

面试题03.02.栈的最小值(2)

  • 题目

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
执行push、pop和min操作的时间复杂度必须为O(1)。
示例：MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 结构体 O(n) O(n)
02 双栈 O(n) O(n) 
type item struct {
	min, x int
}

type MinStack struct {
	stack []item
}

func Constructor() MinStack {
	return MinStack{}
}

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

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

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

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

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

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

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

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

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

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

面试题03.03.堆盘子(1)

  • 题目

堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。
请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。
此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同
（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。
进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.
示例1: 输入：["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
[[1], [1], [2], [1], [], []]
 输出：[null, null, null, 2, 1, -1]
示例2:输入： ["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
[[2], [1], [2], [3], [0], [0], [0]]
 输出：[null, null, null, null, 2, 1, 3]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 栈-二维 O(1) O(n^2) 
type StackOfPlates struct {
	cap   int
	stack [][]int
}

func Constructor(cap int) StackOfPlates {
	return StackOfPlates{
		cap:   cap,
		stack: make([][]int, 0),
	}
}

func (this *StackOfPlates) Push(val int) {
	if this.cap == 0 {
		return
	}
	if len(this.stack) == 0 {
		newStack := make([]int, 0)
		newStack = append(newStack, val)
		this.stack = append(this.stack, newStack)
		return
	}
	last := this.stack[len(this.stack)-1]
	if len(last) == this.cap {
		newStack := make([]int, 0)
		newStack = append(newStack, val)
		this.stack = append(this.stack, newStack)
		return
	}
	last = append(last, val)
	this.stack[len(this.stack)-1] = last
}

func (this *StackOfPlates) Pop() int {
	if len(this.stack) == 0 {
		return -1
	}
	last := this.stack[len(this.stack)-1]
	res := last[len(last)-1]
	last = last[:len(last)-1]
	this.stack[len(this.stack)-1] = last
	if len(last) == 0 {
		this.stack = this.stack[:len(this.stack)-1]
	}
	return res
}

func (this *StackOfPlates) PopAt(index int) int {
	if index >= len(this.stack) {
		return -1
	}
	arr := this.stack[index]
	res := arr[len(arr)-1]
	arr = arr[:len(arr)-1]
	this.stack[index] = arr
	if len(arr) == 0 {
		this.stack = append(this.stack[:index], this.stack[index+1:]...)
	}
	return res
}

面试题03.04.化栈为队(3)

  • 题目

实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false
说明： 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size 
和 is empty 操作是合法的。
    你所使用的语言也许不支持栈。
    你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 使用切片 O(1) O(n)
02 使用2个栈实现 O(n) O(n)
03 使用2个切片实现 O(n) O(n) 
type MyQueue struct {
	a []int
}

func Constructor() MyQueue {
	return MyQueue{}
}

func (m *MyQueue) Push(x int) {
	m.a = append(m.a, x)
}

func (m *MyQueue) Pop() int {
	if len(m.a) == 0 {
		return 0
	}
	first := m.a[0]
	m.a = m.a[1:]
	return first
}

func (m *MyQueue) Peek() int {
	if len(m.a) == 0 {
		return 0
	}
	return m.a[0]
}

func (m *MyQueue) Empty() bool {
	if len(m.a) == 0 {
		return true
	}
	return false
}

# 2
/*
入队: 直接入栈a
出队: 栈b为空，则把栈a中全部数据出栈进入栈b，然后出栈b,不为空直接出栈b
*/
type MyQueue struct {
	a, b *Stack
}

func Constructor() MyQueue {
	return MyQueue{
		a: NewStack(),
		b: NewStack(),
	}
}

func (m *MyQueue) Push(x int) {
	m.a.Push(x)
}

func (m *MyQueue) Pop() int {
	if m.b.Len() == 0 {
		for m.a.Len() > 0 {
			m.b.Push(m.a.Pop())
		}
	}
	return m.b.Pop()
}

func (m *MyQueue) Peek() int {
	res := m.Pop()
	m.b.Push(res)
	return res
}

func (m *MyQueue) Empty() bool {
	return m.a.Len() == 0 && m.b.Len() == 0
}

type Stack struct {
	nums []int
}

func NewStack() *Stack {
	return &Stack{
		nums: []int{},
	}
}

func (s *Stack) Push(n int) {
	s.nums = append(s.nums, n)
}

func (s *Stack) Pop() int {
	res := s.nums[len(s.nums)-1]
	s.nums = s.nums[:len(s.nums)-1]
	return res
}

func (s *Stack) Len() int {
	return len(s.nums)
}

func (s *Stack) IsEmpty() bool {
	return s.Len() == 0
}

# 3
type MyQueue struct {
	a []int
	b []int
}

func Constructor() MyQueue {
	return MyQueue{}
}

func (m *MyQueue) Push(x int) {
	m.a = append(m.a, x)
}

func (m *MyQueue) Pop() int {
	m.Peek()
	temp := m.b[len(m.b)-1]
	m.b = m.b[:len(m.b)-1]
	return temp
}

func (m *MyQueue) Peek() int {
	if len(m.b) == 0 {
		for len(m.a) > 0 {
			m.b = append(m.b, m.a[len(m.a)-1])
			m.a = m.a[:len(m.a)-1]
		}
	}
	if len(m.b) == 0 {
		return -1
	}
	return m.b[len(m.b)-1]
}

func (m *MyQueue) Empty() bool {
	return len(m.a) == 0 && len(m.b) == 0
}

面试题03.05.栈排序(1)

  • 题目

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。
最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
示例1:输入：["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
 输出：[null,null,null,1,null,2]
示例2:输入： ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
 输出：[null,null,null,null,null,true]
说明:栈中的元素数目在[0, 5000]范围内。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 双栈 O(n) O(n) 
type SortedStack struct {
	stack []int
	temp  []int
}

func Constructor() SortedStack {
	return SortedStack{}
}

func (this *SortedStack) Push(val int) {
	for len(this.stack) > 0 && val >= this.stack[len(this.stack)-1] {
		this.temp = append(this.temp, this.stack[len(this.stack)-1])
		this.stack = this.stack[:len(this.stack)-1]
	}
	this.stack = append(this.stack, val)
	for len(this.temp) > 0 {
		this.stack = append(this.stack, this.temp[len(this.temp)-1])
		this.temp = this.temp[:len(this.temp)-1]
	}
}

func (this *SortedStack) Pop() {
	if len(this.stack) == 0 {
		return
	}
	this.stack = this.stack[:len(this.stack)-1]
}

func (this *SortedStack) Peek() int {
	if len(this.stack) == 0 {
		return -1
	}
	return this.stack[len(this.stack)-1]
}

func (this *SortedStack) IsEmpty() bool {
	return len(this.stack) == 0
}

面试题03.06.动物收容所(2)

  • 题目

动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。
在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，
或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。
换言之，收养人不能自由挑选想收养的对象。
请创建适用于这个系统的数据结构，实现各种操作方法，
比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
示例1:输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
 输出：[null,null,null,[0,0],[-1,-1],[1,0]]
示例2:输入：
["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
输出：[null,null,null,null,[2,1],[0,0],[1,0]]
说明:收纳所的最大容量为20000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 双数组 O(1) O(n)
02 内置list O(1) O(n) 
type AnimalShelf struct {
	cat [][]int
	dog [][]int
}

func Constructor() AnimalShelf {
	return AnimalShelf{
		cat: make([][]int, 0),
		dog: make([][]int, 0),
	}
}

func (this *AnimalShelf) Enqueue(animal []int) {
	if animal[1] == 0 {
		this.cat = append(this.cat, animal)
	} else {
		this.dog = append(this.dog, animal)
	}
}

func (this *AnimalShelf) DequeueAny() []int {
	if len(this.dog) == 0 && len(this.cat) == 0 {
		return []int{-1, -1}
	}
	if len(this.dog) == 0 || len(this.cat) == 0 {
		if len(this.dog) == 0 {
			res := this.cat[0]
			this.cat = this.cat[1:]
			return res
		}
		res := this.dog[0]
		this.dog = this.dog[1:]
		return res
	}
	if this.dog[0][0] > this.cat[0][0] {
		res := this.cat[0]
		this.cat = this.cat[1:]
		return res

	}
	res := this.dog[0]
	this.dog = this.dog[1:]
	return res
}

func (this *AnimalShelf) DequeueDog() []int {
	if len(this.dog) == 0 {
		return []int{-1, -1}
	}
	res := this.dog[0]
	this.dog = this.dog[1:]
	return res
}

func (this *AnimalShelf) DequeueCat() []int {
	if len(this.cat) == 0 {
		return []int{-1, -1}
	}
	res := this.cat[0]
	this.cat = this.cat[1:]
	return res
}

# 2
type AnimalShelf struct {
	arr [2]*list.List
}

func Constructor() AnimalShelf {
	return AnimalShelf{
		arr: [2]*list.List{list.New(), list.New()},
	}
}

func (this *AnimalShelf) Enqueue(animal []int) {
	this.arr[animal[1]].PushBack(animal[0])
}

func (this *AnimalShelf) DequeueAny() []int {
	if this.arr[0].Len() == 0 && this.arr[1].Len() == 0 {
		return []int{-1, -1}
	}
	if this.arr[1].Len() > 0 &&
		(this.arr[0].Len() == 0 || this.arr[1].Front().Value.(int) < this.arr[0].Front().Value.(int)) {
		return []int{this.arr[1].Remove(this.arr[1].Front()).(int), 1}
	}
	return []int{this.arr[0].Remove(this.arr[0].Front()).(int), 0}
}

func (this *AnimalShelf) DequeueDog() []int {
	if this.arr[1].Len() > 0 {
		return []int{this.arr[1].Remove(this.arr[1].Front()).(int), 1}
	}
	return []int{-1, -1}
}

func (this *AnimalShelf) DequeueCat() []int {
	if this.arr[0].Len() > 0 {
		return []int{this.arr[0].Remove(this.arr[0].Front()).(int), 0}
	}
	return []int{-1, -1}
}

面试题04.01.节点间通路(2)

  • 题目

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例1:输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2 
输出：true
示例2:输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], 
[1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
输出 true
提示：节点数量n在[0, 1e5]范围内。
    节点编号大于等于 0 小于 n。
    图中可能存在自环和平行边。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(n) O(n)
02 深度优先搜索 O(n) O(n) 
func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
	edges := make([][]int, n)
	// 邻接表
	for i := 0; i < len(graph); i++ {
		a := graph[i][0]
		b := graph[i][1]
		edges[a] = append(edges[a], b)
	}
	queue := make([]int, 0)
	queue = append(queue, start)
	visited := make([]bool, n)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		visited[node] = true
		if node == target {
			return true
		}
		for i := 0; i < len(edges[node]); i++ {
			if visited[edges[node][i]] == false {
				if edges[node][i] == target {
					return true
				}
				queue = append(queue, edges[node][i])
			}
		}
	}
	return false
}

# 2
func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
	edges := make([][]int, n)
	// 邻接表
	for i := 0; i < len(graph); i++ {
		a := graph[i][0]
		b := graph[i][1]
		edges[a] = append(edges[a], b)
	}

	visited := make([]bool, n)
	return dfs(edges, visited, start, target)
}

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

面试题04.02.最小高度树(2)

  • 题目

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
示例:给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
          0 
         / \ 
       -3   9 
       /   / 
     -10  5

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 迭代 O(n) O(n) 
func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	mid := len(nums) / 2
	return &TreeNode{
		Val:   nums[mid],
		Left:  sortedArrayToBST(nums[:mid]),
		Right: sortedArrayToBST(nums[mid+1:]),
	}
}

# 2
type MyTreeNode struct {
	root  *TreeNode
	start int
	end   int
}

func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	queue := make([]MyTreeNode, 0)
	root := &TreeNode{Val: 0}
	queue = append(queue, MyTreeNode{root, 0, len(nums)})
	for len(queue) > 0 {
		myRoot := queue[0]
		queue = queue[1:]
		start := myRoot.start
		end := myRoot.end
		mid := (start + end) / 2
		curRoot := myRoot.root
		curRoot.Val = nums[mid]
		if start < mid {
			curRoot.Left = &TreeNode{Val: 0}
			queue = append(queue, MyTreeNode{curRoot.Left, start, mid})
		}
		if mid+1 < end {
			curRoot.Right = &TreeNode{Val: 0}
			queue = append(queue, MyTreeNode{curRoot.Right, mid + 1, end})
		}
	}
	return root
}

面试题04.03.特定深度节点链表(2)

  • 题目

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表
（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
示例：输入：[1,2,3,4,5,null,7,8]
        1
       /  \ 
      2    3
     / \    \ 
    4   5    7
   /
  8
输出：[[1],[2,3],[4,5,7],[8]]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 层序遍历 O(n) O(n)
02 深度优先搜索 O(n) O(n) 
func listOfDepth(tree *TreeNode) []*ListNode {
	res := make([]*ListNode, 0)
	if tree == nil {
		return res
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, tree)
	for len(queue) > 0 {
		length := len(queue)
		node := &ListNode{}
		tempNode := node
		for i := 0; i < length; i++ {
			node := queue[i]
			tempNode.Next = &ListNode{
				Val: node.Val,
			}
			tempNode = tempNode.Next
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		res = append(res, node.Next)
		queue = queue[length:]
	}
	return res
}

# 2
var res []*ListNode

func listOfDepth(tree *TreeNode) []*ListNode {
	level := 0
	res = make([]*ListNode, 0)
	dfs(tree, level)
	return res
}

func dfs(root *TreeNode, level int) {
	if root == nil {
		return
	}
	if level >= len(res) {
		res = append(res, &ListNode{root.Val, nil})
	} else {
		head := res[level]
		for head.Next != nil {
			head = head.Next
		}
		head.Next = &ListNode{root.Val, nil}
	}
	dfs(root.Left, level+1)
	dfs(root.Right, level+1)
}

面试题04.04.检查平衡性(3)

  • 题目

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：
任意一个节点，其两棵子树的高度差不超过 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 。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 递归 O(n) O(log(n))
03 递归 O(n) O(log(n)) 
func isBalanced(root *TreeNode) bool {
	_, isBalanced := dfs(root)
	return isBalanced
}

func dfs(root *TreeNode) (int, bool) {
	if root == nil {
		return 0, true
	}

	leftDepth, leftIsBalanced := dfs(root.Left)
	if leftIsBalanced == false {
		return 0, false
	}
	rightDepth, rightIsBalanced := dfs(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
}

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

# 3
func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	if math.Abs(dfs(root.Left)-dfs(root.Right)) <= 1 {
		return isBalanced(root.Left) && isBalanced(root.Right)
	}
	return false
}

func dfs(root *TreeNode) float64 {
	if root == nil {
		return 0
	}
	return math.Max(dfs(root.Left), dfs(root.Right)) + 1
}

面试题04.05.合法二叉搜索树(5)

  • 题目

实现一个函数，检查一棵二叉树是否为二叉搜索树。
示例 1:输入:
    2
   / \
  1   3
输出: true
示例 2:输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 递归 O(n) O(n)
03 迭代 O(n) O(n)
04 迭代 O(n) O(n)
05 递归 O(n) O(log(n)) 
func isValidBST(root *TreeNode) bool {
	return dfs(root, math.MinInt64, math.MaxInt64)
}

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

# 2
var res []int

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

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

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

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

# 5
var pre int

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

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

面试题04.06.后继者(3)

  • 题目

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
示例 1:输入: root = [2,1,3], p = 1
  2
 / \
1   3
输出: 2
示例 2:输入: root = [5,3,6,2,4,null,null,1], p = 6
      5
     / \
    3   6
   / \
  2   4
 /   
1
输出: null

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(n)
02 递归 O(log(n)) O(log(n))
03 迭代 O(log(n)) O(1) 
var res []*TreeNode

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	res = make([]*TreeNode, 0)
	dfs(root)
	for i := 0; i < len(res)-1; i++ {
		if res[i] == p {
			return res[i+1]
		}
	}
	return nil
}

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

# 2
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if p.Val >= root.Val {
		return inorderSuccessor(root.Right, p)
	}
	res := inorderSuccessor(root.Left, p)
	if res == nil {
		return root
	}
	return res
}

# 3
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	var res *TreeNode
	cur := root
	for cur != nil {
		if p.Val >= cur.Val {
			cur = cur.Right
		} else {
			res = cur
			cur = cur.Left
		}
	}
	return res
}

面试题04.08.首个共同祖先(2)

  • 题目

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。
注意：这不一定是二叉搜索树。
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
    3
   / \
  5   1
 / \ / \
6  2 0  8
  / \
 7   4
示例 1:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉树中。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 递归 O(n) O(n) 
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == p.Val || root.Val == q.Val {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left == nil {
		return right
	}
	return left
}

# 2
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	m = make(map[int]*TreeNode)
	dfs(root)
	visited := make(map[int]bool)
	for p != nil {
		visited[p.Val] = true
		p = m[p.Val]
	}
	for q != nil {
		if visited[q.Val] == true {
			return q
		}
		q = m[q.Val]
	}
	return nil
}

func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	if root.Left != nil {
		m[root.Left.Val] = root
		dfs(root.Left)
	}
	if root.Right != nil {
		m[root.Right.Val] = root
		dfs(root.Right)
	}
}

面试题04.09.二叉搜索树序列(1)

  • 题目

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。
给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。
示例：给定如下二叉树
        2
       / \
      1   3
返回：[
   [2,1,3],
   [2,3,1]
]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(2^log(n)) O(2^log(n)) 
var res [][]int

func BSTSequences(root *TreeNode) [][]int {
	res = make([][]int, 0)
	if root == nil {
		res = append(res, []int{})
		return res
	}
	dfs(append([]*TreeNode{}, root), make([]int, 0))
	return res
}

func dfs(arr []*TreeNode, path []int) {
	if len(arr) == 0 {
		res = append(res, path)
	}
	for i, node := range arr {
		temp := make([]int, len(path))
		copy(temp, path)
		temp = append(temp, node.Val)
		tempNode := make([]*TreeNode, len(arr))
		copy(tempNode, arr)
		tempNode = append(tempNode[:i], tempNode[i+1:]...) // 去除当前用过的
		if node.Left != nil {
			tempNode = append(tempNode, node.Left)
		}
		if node.Right != nil {
			tempNode = append(tempNode, node.Right)
		}
		dfs(tempNode, temp)
	}
}

面试题04.10.检查子树(2)

  • 题目

检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。
设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，
也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
示例1:输入：t1 = [1, 2, 3], t2 = [2] 输出：true
示例2:输入：t1 = [1, null, 2, 4], t2 = [3, 2] 输出：false
提示：树的节点数目范围为[0, 20000]。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n^2) O(log(n))
02 递归+字符串辅助 O(n) O(log(n))
03 栈辅助(超时) O(n) O(n) 
func checkSubTree(t1 *TreeNode, t2 *TreeNode) bool {
	if t1 == nil {
		return false
	}
	return isSame(t1, t2) || checkSubTree(t1.Left, t2) || checkSubTree(t1.Right, t2)
}

func isSame(s *TreeNode, t *TreeNode) bool {
	if s == nil || t == nil {
		return t == s
	}
	return isSame(s.Left, t.Left) && isSame(s.Right, t.Right) && s.Val == t.Val
}

# 2
func checkSubTree(t1 *TreeNode, t2 *TreeNode) bool {
	sStr := dfs(t1, "")
	tStr := dfs(t2, "")
	return strings.Contains(sStr, tStr)
}

func dfs(s *TreeNode, pre string) string {
	if s == nil {
		return pre
	}
	return fmt.Sprintf("#%d%s%s", s.Val, dfs(s.Left, "l"), dfs(s.Right, "r"))
}

# 3
func checkSubTree(t1 *TreeNode, t2 *TreeNode) bool {
	sStr := preOrder(t1)
	tStr := preOrder(t2)
	return strings.Contains(sStr, tStr)
}

func preOrder(root *TreeNode) string {
	if root == nil {
		return ""
	}
	res := "!"
	stack := make([]*TreeNode, 0)
	temp := root
	for {
		for temp != nil {
			res += strconv.Itoa(temp.Val)
			res += "!"
			stack = append(stack, temp)
			temp = temp.Left
		}
		res += "#!"
		if len(stack) > 0 {
			node := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			temp = node.Right
		} else {
			break
		}
	}
	return res
}

面试题04.12.求和路径(4)

  • 题目

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，
打印节点数值总和等于某个给定值的所有路径的数量。
注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例:给定如下二叉树，以及目标和 sum = 22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:3
解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
提示：节点总数 <= 10000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n^2) O(n)
02 递归 O(n^2) O(n)
03 迭代+递归 O(n^2) O(n)
04 递归+路径 O(n^2) O(n) 
func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	res := 0
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, sum int) {
		if node == nil {
			return
		}
		sum = sum - node.Val
		// 路径不需要从根节点开始，也不需要在叶子节点结束
		if sum == 0 {
			res++
		}
		dfs(node.Left, sum)
		dfs(node.Right, sum)
	}
	dfs(root, sum)
	return res + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

# 2
func dfs(node *TreeNode, sum int) int {
	if node == nil {
		return 0
	}
	sum = sum - node.Val
	res := 0
	if sum == 0 {
		res = 1
	}
	return res + dfs(node.Left, sum) + dfs(node.Right, sum)
}

func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	return dfs(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

# 3
func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	res := 0
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		tempSum := 0
		res += dfs(node, sum, tempSum)
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return res
}

func dfs(node *TreeNode, sum int, curSum int) int {
	res := 0
	curSum = curSum + node.Val
	if curSum == sum {
		res++
	}
	if node.Left != nil {
		res += dfs(node.Left, sum, curSum)
	}
	if node.Right != nil {
		res += dfs(node.Right, sum, curSum)
	}
	return res
}

# 4
func pathSum(root *TreeNode, sum int) int {
	return dfs(root, sum, make([]int, 1001), 0)
}

func dfs(node *TreeNode, sum int, path []int, level int) int {
	if node == nil {
		return 0
	}
	res := 0
	if sum == node.Val {
		res = 1
	}
	temp := node.Val
	for i := level - 1; i >= 0; i-- {
		temp = temp + path[i]
		if temp == sum {
			res++
		}
	}
	path[level] = node.Val
	return res + dfs(node.Left, sum, path, level+1) +
		dfs(node.Right, sum, path, level+1)
}

面试题05.01.插入(4)

  • 题目

插入。给定两个32位的整数N与M，以及表示比特位置的i与j。
编写一种方法，将M插入N，使得M从N的第j位开始，到第i位结束。假定从j位到i位足以容纳M，也即若M = 10 011，
那么j和i之间至少可容纳5个位。例如，不可能出现j = 3和i = 2的情况，因为第3位和第2位之间放不下M。
示例1:输入：N = 1024(10000000000), M = 19(10011), i = 2, j = 6 输出：N = 1100(10001001100)
示例2:输入： N = 0, M = 31(11111), i = 0, j = 4 输出：N = 31(11111)

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 位运算 O(1) O(1)
02 位运算 O(1) O(1)
03 数组辅助 O(1) O(1)
04 位运算 O(1) O(1) 
func insertBits(N int, M int, i int, j int) int {
	a := (N >> (j + 1)) << (j + 1)
	b := (N>>i)<<i ^ N
	c := M << i
	return a | b | c
}

# 2 
func insertBits(N int, M int, i int, j int) int {
	for k := i; k <= j; k++ {
		if N&(1<<k) != 0 {
			N = N - 1<<k
		}
	}
	N = N + (M << i)
	return N
}

# 3
func insertBits(N int, M int, i int, j int) int {
	arr := make([]byte, 32)
	for i := 0; i < 32; i++ {
		arr[i] = '0'
	}
	a := fmt.Sprintf("%b", N)
	b := fmt.Sprintf("%b", M)
	for k := len(a) - 1; k >= 0; k-- {
		arr[31-(len(a)-1-k)] = a[k]
	}
	count := 0
	for k := 31 - i; k >= 31-j; k-- {
		if count < len(b) {
			arr[k] = b[len(b)-1-count]
			count++
		} else {
			arr[k] = '0'
		}
	}
	value, _ := strconv.ParseInt(string(arr), 2, 64)
	return int(value)
}

# 4
func insertBits(N int, M int, i int, j int) int {
	res := N
	setZero := 0
	for k := i; k <= j; k++ {
		setZero = setZero | (1 << k)
	}
	res = res&setZero ^ N
	res = res | (M << i)
	return res
}

面试题05.02.二进制数转字符串(2)

  • 题目

二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。
如果该数字不在0和1之间，或者无法精确地用32位以内的二进制表示，则打印“ERROR”。
示例1:输入：0.625 输出："0.101"
示例2:输入：0.1 输出："ERROR"
提示：0.1无法被二进制准确表示
提示：32位包括输出中的"0."这两位。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(1) O(1)
02 遍历 O(1) O(1) 
func printBin(num float64) string {
	res := "0."
	for num != float64(0) {
		num = num * 2
		if num >= 1 {
			res = res + "1"
			num = num - 1.0
		} else {
			res = res + "0"
		}
		if len(res) > 32 {
			return "ERROR"
		}
	}
	return res
}

# 2
func printBin(num float64) string {
	res := "0."
	value := float64(1)
	for i := 1; i <= 32; i++ {
		value = value / 2
		if num < value {
			res = res + "0"
			continue
		}
		res = res + "1"
		num = num - value
		if num == 0 {
			return res
		}
	}
	return "ERROR"
}

面试题05.03.翻转数位(2)

  • 题目

给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
示例 1：输入: num = 1775(110111011112)输出: 8
示例 2：输入: num = 7(01112)输出: 4

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(1) O(1)
02 数组辅助 O(1) O(1) 
func reverseBits(num int) int {
	res := 0
	a, b := 0, 0
	for num != 0 {
		if num%2 == 1 {
			a++
		} else {
			b = a
			a = 0
		}
		res = max(res, a+b)
		num = num / 2
	}
	return res + 1
}

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

# 2
func reverseBits(num int) int {
	res := 0
	arr := make([]int, 0)
	count := 0
	for num != 0 {
		if num%2 == 1 {
			count++
		} else {
			arr = append(arr, count)
			count = 0
		}
		num = num / 2
	}
	arr = append(arr, count)
	if len(arr) == 1 {
		return arr[0] + 1
	}
	for i := 1; i < len(arr); i++ {
		res = max(res, arr[i]+arr[i-1])
	}
	return res + 1
}

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

面试题05.04.下一个数

题目

下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。
示例1:输入：num = 2（或者0b10） 输出：[4, 1] 或者（[0b100, 0b1]）
示例2:输入：num = 1输出：[2, -1]
提示:num的范围在[1, 2147483647]之间；
    如果找不到前一个或者后一个满足条件的正数，那么输出 -1。

解题思路

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

面试题05.06.整数转换(4)

  • 题目

整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
示例1:输入：A = 29 （或者0b11101）, B = 15（或者0b01111）输出：2
示例2:输入：A = 1，B = 2 输出：2
提示: A，B范围在[-2147483648, 2147483647]之间

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 内置函数 O(1) O(1)
02 位运算 O(1) O(1)
03 位运算 O(1) O(1)
04 位运算 O(1) O(1) 
func convertInteger(A int, B int) int {
	C := uint32(A) ^ uint32(B)
	return bits.OnesCount(uint(C))
}

# 2
func convertInteger(A int, B int) int {
	C := uint32(A) ^ uint32(B)
	res := 0
	for C != 0 {
		if C&1 == 1 {
			res++
		}
		C = C >> 1
	}
	return res
}

# 3
func convertInteger(A int, B int) int {
	C := uint32(A) ^ uint32(B)
	res := 0
	for C != 0 {
		res++
		C = C & (C - 1)
	}
	return res
}

# 4
func convertInteger(A int, B int) int {
	C := A ^ B
	res := 0
	for i := 0; i < 32; i++{
		if C & 1 ==1{
			res++
		}
		C = C >> 1
	}
	return res
}

面试题05.07.配对交换(2)

  • 题目

配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令
（也就是说，位0与位1交换，位2与位3交换，以此类推）。
示例1:输入：num = 2（或者0b10）输出 1 (或者 0b01)
示例2:输入：num = 3 输出：3
提示:num的范围在[0, 2^30 - 1]之间，不会发生整数溢出。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 位运算 O(1) O(1)
02 数组辅助 O(1) O(1) 
func exchangeBits(num int) int {
	// 0x55555555 = 01010101010101010101010101010101 提取偶数位=>左移
	// 0xaaaaaaaa = 10101010101010101010101010101010 提取奇数位=>右移
	a := (num & 0x55555555) << 1
	b := (num & 0xaaaaaaaa) >> 1
	return a | b
}

# 2
func exchangeBits(num int) int {
	a := fmt.Sprintf("%b", num)
	arr := make([]byte, 32)
	for i := 0; i < 32; i++ {
		arr[i] = '0'
	}
	count := 31
	for i := len(a) - 1; i >= 0; i-- {
		arr[count] = a[i]
		count--
	}
	for i := len(arr) - 2; i >= 0; i = i - 2 {
		arr[i], arr[i+1] = arr[i+1], arr[i]
	}
	value, _ := strconv.ParseInt(string(arr), 2, 64)
	return int(value)
}

面试题05.08.绘制直线(2)

  • 题目

绘制直线。
有个单色屏幕存储在一个一维数组中，使得32个连续像素可以存放在一个 int 里。
屏幕宽度为w，且w可被32整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。
请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。
给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数y。
返回绘制过后的数组。
示例1:输入：length = 1, w = 32, x1 = 30, x2 = 31, y = 0 输出：[3]
说明：在第0行的第30位到第31为画一条直线，屏幕表示为[0b000000000000000000000000000000011]
示例2:输入：length = 3, w = 96, x1 = 0, x2 = 95, y = 0 输出：[-1, -1, -1]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 遍历 O(n) O(n) 
func drawLine(length int, w int, x1 int, x2 int, y int) []int {
	res := make([]int, length)
	for i := 0; i < length; i++ {
		start := i * 32
		var value int32
		for j := 0; j < 32; j++ {
			if x1+y*w <= start+j && start+j <= x2+y*w {
				value = value ^ (1 << (31 - j)) // 画线：把第31-j位变为1
			}
		}
		res[i] = int(value)
	}
	return res
}

# 2
func drawLine(length int, w int, x1 int, x2 int, y int) []int {
	arr := make([]int32, length)
	width := w / 32
	for i := x1; i <= x2; i++ {
		index := width*y + (i / 32)
		arr[index] = arr[index] ^ (1 << (31 - (i % 32)))
	}
	res := make([]int, length)
	for i := 0; i < length; i++ {
		res[i] = int(arr[i])
	}
	return res
}

面试题08.01.三步问题(2)

  • 题目

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。
实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:输入：n = 3 输出：4
说明: 有四种走法
示例2:输入：n = 5输出：13
提示:n范围在[1, 1000000]之间

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(1)
02 动态规划 O(n) O(n) 
func waysToStep(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	if n == 3 {
		return 4
	}
	a, b, c := 1, 2, 4
	for i := 4; i <= n; i++ {
		a, b, c = b, c, (a+b+c)%1000000007
	}
	return c
}

# 2
func waysToStep(n int) int {
	dp := make([]int, n+3)
	dp[0] = 1
	dp[1] = 2
	dp[2] = 4
	for i := 3; i < n; i++ {
		dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 1000000007
	}
	return dp[n-1]
}

面试题08.02.迷路的机器人(2)

  • 题目

设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。
机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。
设计一种算法，寻找机器人从左上角移动到右下角的路径。
网格中的障碍物和空位置分别用 1 和 0 来表示。
返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。
如果没有可行的路径，返回空数组。
示例 1:输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释: 输入中标粗的位置即为输出表示的路径，即
0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）
说明：r 和 c 的值均不超过 100。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^2) O(n)
02 动态规划 O(n^2) O(1) 
var res [][]int

func pathWithObstacles(obstacleGrid [][]int) [][]int {
	res = make([][]int, 0)
	path := make([][]int, 0)
	path = append(path, []int{0, 0})
	dfs(obstacleGrid, path)
	return res
}

func dfs(arr [][]int, path [][]int) {
	if len(res) == 0 {
		x, y := path[len(path)-1][0], path[len(path)-1][1]
		if arr[x][y] == 0 {
			arr[x][y] = 1
			if x < len(arr)-1 {
				dfs(arr, append(path, []int{x + 1, y}))
			}
			if y < len(arr[0])-1 {
				dfs(arr, append(path, []int{x, y + 1}))
			}
			if x == len(arr)-1 && y == len(arr[0])-1 {
				res = make([][]int, len(path))
				copy(res, path)
			}
		}
	}
}

# 2
func pathWithObstacles(obstacleGrid [][]int) [][]int {
	res := make([][]int, 0)
	n := len(obstacleGrid)
	m := len(obstacleGrid[0])
	if obstacleGrid[0][0] == 1 || obstacleGrid[n-1][m-1] == 1 {
		return res
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
				continue
			}
			if i == 0 && j == 0 {
				obstacleGrid[i][j] = 1
			} else if i == 0 {
				obstacleGrid[i][j] = obstacleGrid[i][j-1] + 1
			} else if j == 0 {
				obstacleGrid[i][j] = obstacleGrid[i-1][j] + 1
			} else {
				obstacleGrid[i][j] = max(obstacleGrid[i][j-1], obstacleGrid[i-1][j]) + 1
			}
		}
	}
	total := n + m - 1
	if obstacleGrid[n-1][m-1] != total {
		return res
	}
	i, j := n-1, m-1
	for i >= 0 && j >= 0 {
		if obstacleGrid[i][j] == total {
			newArr := make([][]int, 0)
			newArr = append(newArr, []int{i, j})
			res = append(newArr, res...)
			total = total - 1
		}
		if i == 0 && j == 0 {
			break
		}
		if i == 0 && obstacleGrid[i][j-1] == total {
			j--
		} else if j == 0 && obstacleGrid[i-1][j] == total {
			i--
		} else if obstacleGrid[i-1][j] == total {
			i--
		} else if obstacleGrid[i][j-1] == total {
			j--
		}
	}
	return res
}

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

面试题08.03.魔术索引(2)

  • 题目

魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。
给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。
若有多个魔术索引，返回索引值最小的一个。
示例1:输入：nums = [0, 2, 3, 4, 5] 输出：0 说明: 0下标的元素为0
示例2:输入：nums = [1, 1, 1] 输出：1
说明:
    nums长度在[1, 1000000]之间
    此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 递归 O(n) O(n) 
func findMagicIndex(nums []int) int {
	for i := 0; i < len(nums); i++{
		if nums[i] == i{
			return i
		}
	}
	return -1
}

# 2
func findMagicIndex(nums []int) int {
	return search(nums, 0, len(nums)-1)
}

func search(nums []int, left, right int) int {
	if left > right {
		return -1
	}
	mid := left + (right-left)/2
	res := search(nums, left, mid-1)
	if res != -1 {
		return res
	} else if nums[mid] == mid {
		return mid
	}
	return search(nums, mid+1, right)
}

面试题08.04.幂集(3)

  • 题目

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
示例:输入： nums = [1,2,3]输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 回溯 O(n*2^n) O(n*2^n)
02 迭代 O(n*2^n) O(n*2^n)
03 位运算 O(n*2^n) O(n*2^n) 
var res [][]int

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

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

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

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

面试题08.05.递归乘法(3)

  • 题目

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
示例1:输入：A = 1, B = 10 输出：10
示例2:输入：A = 3, B = 4 输出：12
提示:保证乘法范围不会溢出

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(n)
02 递归 O(log(n)) O(log(n))
03 迭代 O(log(n)) O(1) 
func multiply(A int, B int) int {
	if B == 0 {
		return 0
	}
	return multiply(A, B-1) + A
}

# 2
func multiply(A int, B int) int {
	if B == 0 {
		return 0
	}
	if B == 1 {
		return A
	}
	if B%2 == 1 {
		return multiply(A<<1, B>>1) + A
	}
	return multiply(A<<1, B>>1)
}

# 3
func multiply(A int, B int) int {
	res := 0
	for B != 0{
		if B % 2==1{
			res = res + A
		}
		A = A+A
		B = B >> 1
	}
	return res
}

面试题08.06.汉诺塔问题(1)

  • 题目

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。
一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。
移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0]
示例2:输入：A = [1, 0], B = [], C = [] 输出：C = [1, 0]
提示:A中盘子的数目不大于14个。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(2^n) O(n) 
func hanota(A []int, B []int, C []int) []int {
	if A == nil {
		return nil
	}
	move(len(A), &A, &B, &C)
	return C
}

func move(num int, A, B, C *[]int) {
	if num < 0 {
		return
	}
	if num == 1 {
		*C = append(*C, (*A)[len(*A)-1])
		*A = (*A)[:len(*A)-1]
		return
	}
	move(num-1, A, C, B)
	move(1, A, B, C)
	move(num-1, B, A, C)
}

面试题08.07.无重复字符串的排列组合(3)

  • 题目

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:输入：S = "qwe"输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
示例2:输入：S = "ab"输出：["ab", "ba"]
提示:字符都是英文字母。
    字符串长度在[1, 9]之间。

  • 解题思路

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

func permutation(S string) []string {
	res = make([]string, 0)
	nums := []byte(S)
	visited := make(map[int]bool)
	dfs(nums, 0, "", visited)
	return res
}

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

# 2
func permutation(S string) []string {
	if len(S) == 1 {
		return []string{S}
	}
	res := make([]string, 0)
	for i := 0; i < len(S); i++ {
		str := S[:i] + S[i+1:]
		arr := permutation(str)
		for _, v := range arr {
			res = append(res, v+string(S[i]))
		}
	}
	return res
}

# 3
var res []string

func permutation(S string) []string {
	res = make([]string, 0)
	nums := []byte(S)
	dfs(nums, 0, "")
	return res
}

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

面试题08.08.有重复字符串的排列组合(3)

  • 题目

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
示例1:输入：S = "qqe" 输出：["eqq","qeq","qqe"]
示例2:输入：S = "ab"输出：["ab", "ba"]
提示:
    字符都是英文字母。
    字符串长度在[1, 9]之间。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 回溯 O(n!) O(n*n!)
02 回溯 O(n!) O(n*n!)
03 回溯 O(n!) O(n*n!) 
var res []string

func permutation(S string) []string {
	res = make([]string, 0)
	nums := []byte(S)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	dfs(nums, 0, make([]int, len(nums)), "")
	return res
}

func dfs(nums []byte, index int, visited []int, str string) {
	if len(nums) == index {
		res = append(res, str)
		return
	}
	for i := 0; i < len(nums); i++ {
		if visited[i] == 1 {
			continue
		}
		if i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0 {
			continue
		}
		str = str + string(nums[i])
		visited[i] = 1
		dfs(nums, index+1, visited, str)
		visited[i] = 0
		str = str[:len(str)-1]
	}
}

# 2
var res []string

func permutation(S string) []string {
	res = make([]string, 0)
	nums := []byte(S)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	dfs(nums, 0)
	return res
}

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

# 3
var res []string

func permutation(S string) []string {
	res = make([]string, 0)
	nums := []byte(S)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	dfs(nums, "")
	return res
}

func dfs(nums []byte, str string) {
	if len(nums) == 0 {
		res = append(res, str)
		return
	}
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		str = str + string(nums[i])
		arr := append([]byte{}, nums[:i]...)
		arr = append(arr, nums[i+1:]...)
		dfs(arr, str)
		str = str[:len(str)-1]
	}
}

面试题08.09.括号(3)

  • 题目

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

  • 解题思路

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

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

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

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

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

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

面试题08.10.颜色填充(2)

  • 题目

编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的横坐标为 sr 纵坐标为 sc。
需要填充的新颜色为 newColor 。
「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。
示例：输入： image = [[1,1,1],[1,1,0],[1,0,1]]  sr = 1, sc = 1, newColor = 2
输出：[[2,2,2],[2,2,0],[2,0,1]]
解释: 初始坐标点位于图像的正中间，坐标 (sr,sc)=(1,1) 。
初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2 。
注意，右下角的像素没有更改为 2 ，因为它不属于初始坐标点的周围区域。
提示：
    image 和 image[0] 的长度均在范围 [1, 50] 内。
    初始坐标点 (sr,sc) 满足 0 <= sr < image.length 和 0 <= sc < image[0].length 。
    image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535] 内。

  • 解题思路

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

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

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

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

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

面试题08.11.硬币(2)

  • 题目

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。
(结果可能会很大，你需要将结果模上1000000007)
示例1:输入: n = 5 输出：2 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:输入: n = 10 输出：4 解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明：注意: 你可以假设： 0 <= n (总金额) <= 1000000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(n)
02 动态规划 O(n) O(n) 
func waysToChange(n int) int {
	coins := []int{1, 5, 10, 25}
	dp := make([][]int, 5)
	for i := 0; i <= 4; i++ {
		dp[i] = make([]int, n+1)
		dp[i][0] = 1 // 金额为0的情况，只有都不选，组合情况为1
	}
	for i := 1; i <= 4; i++ {
		for j := 1; j <= n; j++ {
			if j-coins[i-1] >= 0 {
				dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[4][n] % 1000000007
}

# 2
func waysToChange(n int) int {
	coins := []int{1, 5, 10, 25}
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 1; i <= 4; i++ {
		for j := 1; j <= n; j++ {
			if j-coins[i-1] >= 0 {
				dp[j] = dp[j] + dp[j-coins[i-1]]
			}
		}
	}
	return dp[n] % 1000000007
}

面试题08.12.八皇后(3)

  • 题目

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。
这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
注意：本题相对原题做了扩展
示例:输入：4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

  • 解题思路

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

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

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

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

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

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

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

# 3
var res [][]string

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

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

面试题08.13.堆箱子(1)

  • 题目

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。
箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。
实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组[wi, di, hi]表示每个箱子。
示例1:输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]输出：6
示例2:输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]] 输出：10
提示:箱子的数目不大于3000个。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序+动态规划 O(n^2) O(n) 
func pileBox(box [][]int) int {
	sort.Slice(box, func(i, j int) bool {
		if box[i][0] == box[j][0] {
			if box[i][1] == box[j][1] {
				return box[i][2] < box[j][2]
			}
			return box[i][1] < box[j][1]
		}
		return box[i][0] < box[j][0]
	})
	n, res := len(box), 0
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = box[i][2]
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2] {
				dp[i] = max(dp[i], dp[j]+box[i][2])
			}
		}
		res = max(res, dp[i])
	}
	return res
}

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

面试题08.14.布尔运算(3)

  • 题目

给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、
| (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
示例 1:输入: s = "1^0|0|1", result = 0  输出: 2
解释:两种可能的括号方法是
1^(0|(0|1))
1^((0|0)|1)
示例 2:输入: s = "0&0&0&1^1|0", result = 1 输出: 10
提示：运算符的数量不超过 19 个

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n^3) O(n^2)
02 动态规划 O(n^3) O(n^2)
03 动态规划 O(n^3) O(n^2) 
func countEval(s string, result int) int {
	n := len(s)
	// dp[i][j][0/1] => s[i:j+1]结果为0/1的方法数
	dp := make([][][2]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([][2]int, n)
	}
	for i := n - 1; i >= 0; i = i - 2 {
		for j := i; j < n; j = j + 2 {
			if i == j {
				if s[i] == '0' {
					dp[i][j][0]++
				} else {
					dp[i][j][1]++
				}
				continue
			}
			for k := i + 1; k < j; k = k + 2 { // 枚举操作符
				for a := 0; a <= 1; a++ {
					for b := 0; b <= 1; b++ {
						if getValue(a, b, s[k]) == 0 {
							dp[i][j][0] = dp[i][j][0] +
								dp[i][k-1][a]*dp[k+1][j][b]
						} else {
							dp[i][j][1] = dp[i][j][01] +
								dp[i][k-1][a]*dp[k+1][j][b]
						}
					}
				}
			}
		}
	}
	return dp[0][n-1][result]
}

func getValue(a, b int, op byte) int {
	if op == '&' {
		return a & b
	} else if op == '|' {
		return a | b
	}
	return a ^ b
}

# 2
func countEval(s string, result int) int {
	n := len(s)
	// dp[i][j][0/1] => s[i:j+1]结果为0/1的方法数
	dp := make([][][2]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([][2]int, n)
	}
	for i := n - 1; i >= 0; i = i - 2 {
		for j := i; j < n; j = j + 2 {
			if i == j {
				dp[i][j][s[i]-'0']++
				continue
			}
			for k := i + 1; k < j; k = k + 2 { // 枚举操作符
				for a := 0; a <= 1; a++ {
					for b := 0; b <= 1; b++ {
						temp := getValue(a, b, s[k])
						dp[i][j][temp] = dp[i][j][temp] +
							dp[i][k-1][a]*dp[k+1][j][b]
					}
				}
			}
		}
	}
	return dp[0][n-1][result]
}

func getValue(a, b int, op byte) int {
	if op == '&' {
		return a & b
	} else if op == '|' {
		return a | b
	}
	return a ^ b
}

# 3
func countEval(s string, result int) int {
	n := len(s)
	// dp[i][j][0/1] => s[i:j+1]结果为0/1的方法数
	dp := make([][][2]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([][2]int, n)
		if i%2 == 0 {
			dp[i][i][int(s[i]-'0')]++
		}
	}
	for length := 2; length <= n; length = length + 2 { // 枚举长度
		for i := 0; i <= n-length; i = i + 2 { // 枚举起点
			j := i + length                    // 确定终点
			for k := i + 1; k < j; k = k + 2 { // 枚举操作符
				for a := 0; a <= 1; a++ {
					for b := 0; b <= 1; b++ {
						temp := getValue(a, b, s[k])
						dp[i][j][temp] = dp[i][j][temp] +
							dp[i][k-1][a]*dp[k+1][j][b]
					}
				}
			}
		}
	}
	return dp[0][n-1][result]
}

func getValue(a, b int, op byte) int {
	if op == '&' {
		return a & b
	} else if op == '|' {
		return a | b
	}
	return a ^ b
}

面试题10.01.合并排序的数组(3)

  • 题目

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]
说明:A.length == n + m

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 合并后排序 O(nlog(n)) O(1)
02 双指针法 O(n) O(1)
03 数组辅助 O(n) O(n) 
func merge(A []int, m int, B []int, n int) {
	A = A[:m]
	A = append(A, B[:n]...)
	sort.Ints(A)
}

# 2
func merge(A []int, m int, B []int, n int) {
	for m > 0 && n > 0 {
		if A[m-1] < B[n-1] {
			A[m+n-1] = B[n-1]
			n--
		} else {
			A[m+n-1] = A[m-1]
			m--
		}
	}
	if m == 0 && n > 0 {
		for n > 0 {
			A[n-1] = B[n-1]
			n--
		}
	}
}

# 3
func merge(A []int, m int, B []int, n int) {
	temp := make([]int, m)
	copy(temp, A)

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

面试题10.02.变位词组(2)

  • 题目

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
注意：本题相对原题稍作修改
示例:输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：所有输入均为小写字母。
    不考虑答案输出的顺序。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^2log(n)) O(n^2)
02 哈希辅助 O(n^2) O(n^2) 
func groupAnagrams(strs []string) [][]string {
	m := make(map[string]int)
	res := make([][]string, 0)
	for i := 0; i < len(strs); i++ {
		arr := []byte(strs[i])
		sort.Slice(arr, func(i, j int) bool {
			return arr[i] < arr[j]
		})
		newStr := string(arr)
		if _, ok := m[newStr]; ok {
			res[m[newStr]] = append(res[m[newStr]], strs[i])
		} else {
			m[newStr] = len(res)
			res = append(res, []string{strs[i]})
		}
	}
	return res
}

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

面试题10.03.搜索旋转数组(2)

  • 题目

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。
请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
示例1: 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）
示例2:输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）
提示:arr 长度范围在[1, 1000000]之间

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 二分查找 O(log(n)) O(1)
02 遍历 O(n) O(1) 
func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if nums[left] < nums[mid] { // 左边升序的情况
			if nums[left] <= target && target <= nums[mid] {
				right = mid
			} else {
				left = mid + 1
			}
		} else if nums[left] > nums[mid] { // 右边升序
			if nums[mid] < target && target <= nums[right] && nums[left] > nums[right] {
				left = mid + 1
			} else {
				right = mid
			}
		} else if nums[left] == nums[mid] {
			if nums[left] != target {
				left++
			} else {
				return left
			}
		}
	}
	if nums[left] == target {
		return left
	}
	return -1
}

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

面试题10.05.稀疏数组搜索(2)

  • 题目

稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
示例1:
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
输出：-1
说明: 不存在返回-1。
示例2:
输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
输出：4
提示: words的长度在[1, 1000000]之间

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 二分查找 O(log(n)) O(1)
02 暴力法 O(n) O(1) 
func findString(words []string, s string) int {
	left := 0
	right := len(words) - 1
	for left <= right {
		mid := left + (right-left)/2
		index := mid
		word := words[mid]
		if word == "" {
			for index = mid; index <= right; index++ {
				if words[index] != "" {
					word = words[index]
					break
				}
			}
		}
		if word == s {
			return index
		} else if word < s {
			left = index + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

# 2
func findString(words []string, s string) int {
	for i := 0; i < len(words); i++ {
		if s == words[i] {
			return i
		}
	}
	return -1
}

面试题10.09.排序矩阵查找(6)

  • 题目

给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
示例:现有矩阵 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。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(1)
02 暴力法-优化 O(n^2) O(1)
03 二分查找 O(nlog(n)) O(1)
04 左下角查找 O(n) O(1)
05 右上角查找 O(n) O(1)
06 内置函数 O(n^2) O(1) 
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	if len(matrix[0]) == 0 {
		return false
	}
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			if matrix[i][j] == target {
				return true
			}
		}
	}
	return false
}

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

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

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

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

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

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

面试题10.10.数字流的秩(3)

  • 题目

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。
请实现数据结构和算法来支持这些操作，也就是说：
实现 track(int x)方法，每读入一个数字都会调用该方法；
实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。
注意：本题相对原题稍作改动
示例:输入: ["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"] [[], [1], [0], [0]]
输出: [null,0,null,1]
提示：x <= 50000
track和getRankOfNumber 方法的调用次数均不超过 2000 次

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 树状数组 O(nlog(n)) O(n)
02 暴力法 O(n^2) O(n)
03 内置函数 O(nlog(n)) O(n) 
type StreamRank struct {
	length int
	c      []int
}

func Constructor() StreamRank {
	return StreamRank{
		length: 50002,
		c:      make([]int, 50003),
	}
}

func (this *StreamRank) Track(x int) {
	this.upData(x+1, 1)
}

func (this *StreamRank) GetRankOfNumber(x int) int {
	return this.getSum(x + 1)
}

func (this *StreamRank) lowBit(x int) int {
	return x & (-x)
}

// 单点修改
func (this *StreamRank) upData(i, k int) { // 在i位置加上k
	for i <= this.length {
		this.c[i] = this.c[i] + k
		i = i + this.lowBit(i) // i = i + 2^k
	}
}

// 区间查询
func (this *StreamRank) getSum(i int) int {
	res := 0
	for i > 0 {
		res = res + this.c[i]
		i = i - this.lowBit(i)
	}
	return res
}

# 2
type StreamRank struct {
	m map[int]int
}

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

func (this *StreamRank) Track(x int) {
	this.m[x]++
}

func (this *StreamRank) GetRankOfNumber(x int) int {
	res := 0
	for k, v := range this.m {
		if k <= x {
			res = res + v
		}
	}
	return res
}

# 3
type StreamRank struct {
	arr []int
}

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

func (this *StreamRank) Track(x int) {
	index := sort.Search(len(this.arr), func(i int) bool {
		return x <= this.arr[i]
	})
	temp := append([]int{}, this.arr[:index]...)
	temp = append(temp, x)
	temp = append(temp, this.arr[index:]...)
	this.arr = temp
}

func (this *StreamRank) GetRankOfNumber(x int) int {
	return sort.Search(len(this.arr), func(i int) bool {
		return x < this.arr[i]
	})
}

面试题10.11.峰与谷(2)

  • 题目

在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。
例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。
现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。
示例:输入: [5, 3, 1, 2, 3] 输出:[5, 1, 3, 2, 3]
提示：nums.length <= 10000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 排序 O(nlog(n)) O(1) 
func wiggleSort(nums []int) {
	for i := 0; i < len(nums)-1; i++ {
		if (i%2 == 1 && nums[i] > nums[i+1]) ||
			(i%2 == 0 && nums[i] < nums[i+1]) {
			nums[i], nums[i+1] = nums[i+1], nums[i]
		}
	}
}

# 2
func wiggleSort(nums []int) {
	sort.Ints(nums)
	for i := 0; i < len(nums)-1; i = i + 2 {
		nums[i], nums[i+1] = nums[i+1], nums[i]
	}
}

面试题16.01.交换数字(3)

  • 题目

编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。
示例：输入: numbers = [1,2] 输出: [2,1]
提示： numbers.length == 2

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 直接返回 O(1) O(1)
02 位运算 O(1) O(1)
03 加减 O(1) O(1) 
func swapNumbers(numbers []int) []int {
	return []int{numbers[1], numbers[0]}
}

# 2
func swapNumbers(numbers []int) []int {
	numbers[0] = numbers[0] ^ numbers[1]
	numbers[1] = numbers[1] ^ numbers[0]
	numbers[0] = numbers[0] ^ numbers[1]
	return numbers
}

# 3
func swapNumbers(numbers []int) []int {
	numbers[0] = numbers[0] + numbers[1]
	numbers[1] = numbers[0] - numbers[1]
	numbers[0] = numbers[0] - numbers[1]
	return numbers
}

面试题16.02.单词频率(2)

  • 题目

设计一个方法，找出任意指定单词在一本书中的出现频率。
你的实现应该支持如下操作：
    WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
    get(word)查询指定单词在书中出现的频率
示例：WordsFrequency wordsFrequency = 
new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "pen"});
wordsFrequency.get("you"); //返回0，"you"没有出现过
wordsFrequency.get("have"); //返回2，"have"出现2次
wordsFrequency.get("an"); //返回1
wordsFrequency.get("apple"); //返回1
wordsFrequency.get("pen"); //返回1
提示：book[i]中只包含小写字母
    1 <= book.length <= 100000
    1 <= book[i].length <= 10
    get函数的调用次数不会超过100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
02 map O(1) O(n)
02 trie树 O(1) O(n) 
type WordsFrequency struct {
	m map[string]int
}

func Constructor(book []string) WordsFrequency {
	res := WordsFrequency{m: make(map[string]int)}
	for k := range book {
		res.m[book[k]]++
	}
	return res
}

func (this *WordsFrequency) Get(word string) int {
	return this.m[word]
}

# 2
type WordsFrequency struct {
	ending int
	next   [26]*WordsFrequency
}

func Constructor(book []string) WordsFrequency {
	res := WordsFrequency{}
	for _, v := range book {
		res.Insert(v)
	}
	return res
}

func (this *WordsFrequency) Get(word string) int {
	temp := this
	for _, v := range word {
		nextWord := v - 'a'
		if temp.next[nextWord] == nil {
			return 0
		}
		temp = temp.next[nextWord]
	}
	return temp.ending
}

func (this *WordsFrequency) Insert(word string) {
	temp := this
	for _, v := range word {
		nextWord := v - 'a'
		if temp.next[nextWord] == nil {
			temp.next[nextWord] = &WordsFrequency{}
		}
		temp = temp.next[nextWord]
	}
	temp.ending = temp.ending + 1
}

面试题16.04.井字游戏(1)

  • 题目

设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
以下是井字游戏的规则：
玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
"X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。
如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；
如果游戏以平局结束，则返回 "Draw"；
如果仍会有行动（游戏未结束），则返回 "Pending"。
示例 1：输入： board = ["O X"," XO","X O"] 输出： "X"
示例 2：输入： board = ["OOX","XXO","OXO"] 输出： "Draw"
解释： 没有玩家获胜且不存在空位
示例 3：输入： board = ["OOX","XXO","OX "] 输出： "Pending"
解释： 没有玩家获胜且仍存在空位
提示：1 <= board.length == board[i].length <= 100
输入一定遵循井字棋规则

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(n) 
func tictactoe(board []string) string {
	n := len(board)
	flag := false                     // 有没有空格
	rows := make([][2]int, n)         // 行
	cols := make([][2]int, n)         // 列
	left, right := [2]int{}, [2]int{} // 对角线
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == ' ' {
				flag = true
			} else if board[i][j] == 'X' {
				rows[i][0]++
				cols[j][0]++
				if i == j {
					left[0]++
				}
				if i == n-1-j {
					right[0]++
				}
			} else if board[i][j] == 'O' {
				rows[i][1]++
				cols[j][1]++
				if i == j {
					left[1]++
				}
				if i == n-1-j {
					right[1]++
				}
			}
		}
	}
	for i := 0; i < n; i++ { // 行列判断
		if rows[i][0] == n || cols[i][0] == n {
			return "X"
		}
		if rows[i][1] == n || cols[i][1] == n {
			return "O"
		}
	}
	if left[0] == n || right[0] == n { // 对角线判断
		return "X"
	}
	if left[1] == n || right[1] == n {
		return "O"
	}
	if flag == true {
		return "Pending"
	}
	return "Draw"
}

面试题16.05.阶乘尾数(1)

  • 题目

设计一个算法，算出 n 阶乘有多少个尾随零。
示例 1:输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。
示例 2:输入: 5输出: 1 解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数学，找规律 O(log(n)) O(1) 
// N!有多少个后缀0，即N!有多少个质因数5。
// N!有多少个质因数5，即N可以划分成多少组5个数字一组，
// 加上划分成多少组25个数字一组，加上划分多少组成125个数字一组，等等
// Ans = N/5 + N/(5^2) + N/(5^3) + ...
func trailingZeroes(n int) int {
	result := 0
	for n >= 5 {
		n = n / 5
		result = result + n
	}
	return result
}

面试题16.06.最小差(2)

  • 题目

给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
示例：输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8} 输出： 3，即数值对(11, 8)
提示：
    1 <= a.length, b.length <= 100000
    -2147483648 <= a[i], b[i] <= 2147483647
    正确结果在区间[-2147483648, 2147483647]内

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序双指针 O(nlog(n)) O(1)
02 排序+二分查找 O(nlog(n)) O(1) 
func smallestDifference(a []int, b []int) int {
	sort.Ints(a)
	sort.Ints(b)
	i, j := 0, 0
	res := math.MaxInt32
	for i < len(a) && j < len(b) {
		res = min(res, abs(a[i], b[j]))
		if a[i] > b[j] {
			j++
		} else {
			i++
		}
	}
	return res
}

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

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

# 2
func smallestDifference(a []int, b []int) int {
	sort.Ints(b)
	res := math.MaxInt32
	for i := 0; i < len(a); i++ {
		left, right := 0, len(b)-1
		for left <= right {
			mid := left + (right-left)/2
			if b[mid] == a[i] {
				return 0
			} else if b[mid] > a[i] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
		if left < len(b) {
			res = min(res, abs(a[i], b[left]))
		}
		if left > 0 {
			res = min(res, abs(a[i], b[left-1]))
		}
	}
	return res
}

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

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

面试题16.07.最大数值(3)

  • 题目

编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。
示例：输入： a = 1, b = 2 输出： 2

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数学 O(1) O(1)
02 内置函数 O(1) O(1)
03 位运算 O(1) O(1) 
func maximum(a int, b int) int {
	// max(a,b) = (abs(a-b)+a+b)/2
	return (int(math.Abs(float64(a-b))) + a + b) / 2
}

# 2
func maximum(a int, b int) int {
	return int(math.Max(float64(a), float64(b)))
}

# 3
func maximum(a int, b int) int {
	value := int(uint64(a-b) >> 63) // 取符号位，a-b>0 => 符号位为0 a-b<0 =>符号位为1
	return value*b + int(1^value)*a // value=0=> 0^1=1 1^1=0
}

面试题16.08.整数的英语表示(2)

  • 题目

给定一个整数，打印该整数的英文描述。
示例 1:输入: 123 输出: "One Hundred Twenty Three"
示例 2:输入: 12345 输出: "Twelve Thousand Three Hundred Forty Five"
示例 3:输入: 1234567 
输出: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
示例 4:输入: 1234567891
输出: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven
Thousand Eight Hundred Ninety One"

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(1) O(1)
02 递归 O(1) O(1) 
func numberToWords(num int) string {
	if num == 0 {
		return "Zero"
	}
	res := ""
	billion := num / 1000000000
	million := (num - billion*1000000000) / 1000000
	thousand := (num - billion*1000000000 - million*1000000) / 1000
	left := num - billion*1000000000 - million*1000000 - thousand*1000
	if billion != 0 {
		res += three(billion) + " Billion"
	}
	if million != 0 {
		if res != "" {
			res += " "
		}
		res += three(million) + " Million"
	}
	if thousand != 0 {
		if res != "" {
			res += " "
		}
		res += three(thousand) + " Thousand"
	}
	if left != 0 {
		if res != "" {
			res += " "
		}
		res += three(left)
	}
	return res
}

func three(num int) string {
	hundred := num / 100
	left := num - hundred*100
	if hundred == 0 {
		return two(num)
	}
	res := transfer[hundred] + " Hundred"
	if left != 0 {
		res += " " + two(left)
	}
	return res
}

func two(num int) string {
	if num == 0 {
		return ""
	} else if num < 10 {
		return transfer[num]
	} else if num < 20 {
		return transfer[num]
	}
	ten := num / 10
	left := num - ten*10
	ten = ten * 10
	res := transfer[ten]
	if left != 0 {
		res += " " + transfer[left]
	}
	return res
}

var transfer = map[int]string{
	0:  "Zero",
	1:  "One",
	2:  "Two",
	3:  "Three",
	4:  "Four",
	5:  "Five",
	6:  "Six",
	7:  "Seven",
	8:  "Eight",
	9:  "Nine",
	10: "Ten",
	11: "Eleven",
	12: "Twelve",
	13: "Thirteen",
	14: "Fourteen",
	15: "Fifteen",
	16: "Sixteen",
	17: "Seventeen",
	18: "Eighteen",
	19: "Nineteen",
	20: "Twenty",
	30: "Thirty",
	40: "Forty",
	50: "Fifty",
	60: "Sixty",
	70: "Seventy",
	80: "Eighty",
	90: "Ninety",
}

# 2
func numberToWords(num int) string {
	if num == 0 {
		return "Zero"
	}
	return strings.Trim(dfs(num), " ")
}

func dfs(n int) string {
	if n < 20 {
		return transfer[n]
	}
	if n < 100 {
		return transfer[n/10*10] + dfs(n%10)
	}
	if n < 1000 {
		return transfer[n/100] + "Hundred " + dfs(n%100)
	}
	if n < 1000000 {
		return dfs(n/1000) + "Thousand " + dfs(n%1000)
	}
	if n < 1000000000 {
		return dfs(n/1000000) + "Million " + dfs(n%1000000)
	}
	return dfs(n/1000000000) + "Billion " + dfs(n%1000000000)
}

var transfer = map[int]string{
	1:  "One ",
	2:  "Two ",
	3:  "Three ",
	4:  "Four ",
	5:  "Five ",
	6:  "Six ",
	7:  "Seven ",
	8:  "Eight ",
	9:  "Nine ",
	10: "Ten ",
	11: "Eleven ",
	12: "Twelve ",
	13: "Thirteen ",
	14: "Fourteen ",
	15: "Fifteen ",
	16: "Sixteen ",
	17: "Seventeen ",
	18: "Eighteen ",
	19: "Nineteen ",
	20: "Twenty ",
	30: "Thirty ",
	40: "Forty ",
	50: "Fifty ",
	60: "Sixty ",
	70: "Seventy ",
	80: "Eighty ",
	90: "Ninety ",
}

面试题16.10.生存人数(2)

  • 题目

给定N个人的出生年份和死亡年份，第i个人的出生年份为birth[i]，死亡年份为death[i]，
实现一个方法以计算生存人数最多的年份。
你可以假设所有人都出生于1900年至2000年（含1900和2000）之间。
如果一个人在某一年的任意时期都处于生存状态，那么他们应该被纳入那一年的统计中。
例如，生于1908年、死于1909年的人应当被列入1908年和1909年的计数。
如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。
示例：输入：birth = {1900, 1901, 1950} death = {1948, 1951, 2000} 输出： 1901
提示：0 < birth.length == death.length <= 10000
    birth[i] <= death[i]

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序双指针 O(nlog(n)) O(1)
02 计数 O(n) O(n) 
func maxAliveYear(birth []int, death []int) int {
	sort.Ints(birth)
	sort.Ints(death)
	res := birth[0]
	max := 0
	j := 0
	count := 0
	for i := 0; i < len(birth); i++ {
		count++
		for birth[i] > death[j] {
			count--
			j++
		}
		if count > max {
			max = count
			res = birth[i]
		}
	}
	return res
}

# 2
func maxAliveYear(birth []int, death []int) int {
	arr := make([]int, 102)
	for i := 0; i < len(birth); i++ {
		arr[birth[i]-1900]++
		arr[death[i]-1900+1]--
	}
	max := 0
	sum := 0
	res := 0
	for i := 0; i < len(arr); i++ {
		sum = sum + arr[i]
		if sum > max {
			max = sum
			res = i + 1900
		}
	}
	return res
}

面试题16.11.跳水板(2)

  • 题目

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，
长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
示例 1 输入：shorter = 1 longer = 2 k = 3 输出： [3,4,5,6]
解释：可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。
以此类推，得到最终结果。
提示：
    0 < shorter <= longer
    0 <= k <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(n)
02 遍历 O(n) O(n) 
func divingBoard(shorter int, longer int, k int) []int {
	res := make([]int, 0)
	if k == 0 {
		return res
	}
	if shorter == longer {
		return []int{shorter * k}
	}
	for i := 0; i <= k; i++ {
		res = append(res, shorter*(k-i)+longer*i)
	}
	return res
}

#
func divingBoard(shorter int, longer int, k int) []int {
	res := make([]int, 0)
	if k == 0 {
		return res
	}
	if shorter == longer {
		return []int{shorter * k}
	}
	start := shorter * k
	diff := longer - shorter
	for i := 0; i <= k; i++ {
		res = append(res, start+i*diff)
	}
	return res
}

面试题16.13.平分正方形(1)

  • 题目

给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。
每个正方形的数据square包含3个数值，正方形的左下顶点坐标[X,Y] = [square[0],square[1]]，以及正方形的边长square[2]。
所求直线穿过两个正方形会形成4个交点，请返回4个交点形成线段的两端点坐标（两个端点即为4个交点中距离最远的2个点，
这2个点所连成的线段一定会穿过另外2个交点）。2个端点坐标[X1,Y1]和[X2,Y2]的返回格式为{X1,Y1,X2,Y2}，
要求若X1 != X2，需保证X1 < X2，否则需保证Y1 <= Y2。
若同时有多条直线满足要求，则选择斜率最大的一条计算并返回（与Y轴平行的直线视为斜率无穷大）。
示例：输入：square1 = {-1, -1, 2} square2 = {0, -1, 2} 输出： {-1,0,2,0}
解释： 直线 y = 0 能将两个正方形同时分为等面积的两部分，返回的两线段端点为[-1,0]和[2,0]
提示：square.length == 3
square[2] > 0

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 几何 O(1) O(1) 
func cutSquares(square1 []int, square2 []int) []float64 {
	// 2个正方形的中点坐标
	x1, y1, z1 := float64(square1[0])+float64(square1[2])/2, float64(square1[1])+float64(square1[2])/2, float64(square1[2])
	x2, y2, z2 := float64(square2[0])+float64(square2[2])/2, float64(square2[1])+float64(square2[2])/2, float64(square2[2])
	var a, b, c, d float64
	if x1 == x2 { // 1、垂直
		a, b, c, d = x1, min(float64(square1[1]), float64(square2[1])), x1, max(float64(square1[1])+z1, float64(square2[1])+z2)
		return []float64{a, b, c, d}
	}
	// 2、有斜率: y = kx + b1
	k := (y1 - y2) / (x1 - x2)
	b1 := y1 - k*x1
	if abs(k) > 1 { // 斜率大于1，交点通过正方形的上边+下边（根据纵坐标求横坐标）
		b = min(float64(square1[1]), float64(square2[1]))
		d = max(float64(square1[1])+z1, float64(square2[1])+z2)
		a = (b - b1) / k
		c = (d - b1) / k
	} else { // 斜率小于等于1，交点通过正方形的左边+右边（根据横坐标求纵坐标）
		a = min(float64(square1[0]), float64(square2[0]))
		c = max(float64(square1[0])+z1, float64(square2[0])+z2)
		b = a*k + b1
		d = c*k + b1
	}
	if a > c {
		a, c = c, a
		b, d = d, b
	}
	return []float64{a, b, c, d}
}

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

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

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

面试题16.14.最佳直线(2)

  • 题目

给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。
设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，
若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。
示例：输入： [[0,0],[1,1],[1,0],[2,0]] 输出： [0,2]
解释： 所求直线穿过的3个点的编号为[0,2,3]
提示：2 <= len(Points) <= 300
len(Points[i]) = 2

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^3) O(1)
02 哈希 O(n^2) O(n^2) 
func bestLine(points [][]int) []int {
	res := []int{0, 1}
	maxCount := 0
	n := len(points)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			count := 2
			x1 := points[i][0] - points[j][0]
			y1 := points[i][1] - points[j][1]
			for k := j + 1; k < n; k++ {
				x2 := points[i][0] - points[k][0]
				y2 := points[i][1] - points[k][1]
				if x1*y2 == x2*y1 { // 斜率相同+1
					count++
				}
			}
			if count > maxCount {
				maxCount = count
				res[0] = i
				res[1] = j
			}
		}
	}
	return res
}

# 2
func bestLine(points [][]int) []int {
	res := []int{0, 1}
	maxCount := 0
	n := len(points)
	m := make(map[[3]int]int)
	mToKey := make(map[[3]int][]int)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			// AX+BY+C=0
			A := points[j][1] - points[i][1]
			B := points[i][0] - points[j][0]
			C := points[i][1]*points[j][0] - points[i][0]*points[j][1]
			com := gcd(gcd(A, B), C)
			A, B, C = A/com, B/com, C/com
			node := [3]int{A, B, C}
			if m[node] == 0 {
				mToKey[node] = []int{i, j}
			}
			m[node]++
			if m[node] > maxCount {
				maxCount = m[node]
				res = mToKey[node]
			} else if m[node] == maxCount {
				if mToKey[node][0] < res[0] ||
					(mToKey[node][0] == res[0] && mToKey[node][1] < res[1]) {
					res = mToKey[node]
				}
			}
		}
	}
	return res
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

面试题16.15.珠玑妙算(2)

  • 题目

珠玑妙算游戏（the game of master mind）的玩法如下。
计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。
例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。
作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。
要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。
注意，“猜中”不能算入“伪猜中”。
给定一种颜色组合solution和一个猜测guess，
编写一个方法，返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。
示例：输入： solution="RGBY",guess="GGRR" 输出： [1,1]
解释： 猜中1次，伪猜中1次。
提示：len(solution) = len(guess) = 4
    solution和guess仅包含"R","G","B","Y"这4种字符

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(1) O(1)
02 数组辅助 O(1) O(1) 
func masterMind(solution string, guess string) []int {
	m := make(map[byte]int)
	a, b := 0, 0
	for i := 0; i < len(solution); i++ {
		if solution[i] == guess[i] {
			a++
		} else {
			m[solution[i]]++
		}
	}
	for i := 0; i < len(guess); i++ {
		if solution[i] != guess[i] {
			if m[guess[i]] > 0 {
				b++
				m[guess[i]]--
			}
		}
	}
	return []int{a, b}
}

# 2
func masterMind(solution string, guess string) []int {
	arr := [256]int{}
	a, b := 0, 0
	for i := 0; i < len(solution); i++ {
		if solution[i] == guess[i] {
			a++
		} else {
			arr[solution[i]]++
		}
	}
	for i := 0; i < len(guess); i++ {
		if solution[i] != guess[i] {
			if arr[guess[i]] > 0 {
				b++
				arr[guess[i]]--
			}
		}
	}
	return []int{a, b}
}

面试题16.16.部分排序(2)

  • 题目

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。
注意：n-m尽量最小，也就是说，找出符合条件的最短序列。
函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
示例：输入： [1,2,4,7,10,11,7,12,6,7,16,18,19] 输出： [3,9]
提示：0 <= len(array) <= 1000000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序遍历 O(nlog(n)) O(n)
02 遍历 O(n) O(1) 
func subSort(array []int) []int {
	temp := make([]int, len(array))
	copy(temp, array)
	sort.Ints(temp)
	left, right := -1, -1
	for i := 0; i < len(array); i++ {
		if temp[i] != array[i] {
			left = i
			break
		}
	}
	for i := len(array) - 1; i >= 0; i-- {
		if temp[i] != array[i] {
			right = i
			break
		}
	}
	return []int{left, right}
}

# 2
func subSort(array []int) []int {
	left, right := -1, -1
	maxValue := math.MinInt32
	minValue := math.MaxInt32
	for i := 0; i < len(array); i++ {
		if array[i] >= maxValue {
			maxValue = array[i]
		} else {
			right = i
		}
	}
	for i := len(array) - 1; i >= 0; i-- {
		if minValue >= array[i] {
			minValue = array[i]
		} else {
			left = i
		}
	}
	return []int{left, right}
}

面试题16.17.连续数列(5)

  • 题目

给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：输入： [-2,1,-3,4,-1,2,1,-5,4]输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 贪心法 O(n) O(1)
02 暴力法 O(n^2) O(1)
03 动态规划 O(n) O(n)
04 动态规划 O(n) O(1)
05 分治 O(nlog(n)) O(log(n)) 
func maxSubArray(nums []int) int {
	result := nums[0]
	sum := 0
	for i := 0; i < len(nums); i++ {
		if sum > 0 {
			sum += nums[i]
		} else {
			sum = nums[i]
		}
		if sum > result {
			result = sum
		}
	}
	return result
}

# 2
func maxSubArray(nums []int) int {
	result := math.MinInt32
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum > result {
				result = sum
			}
		}
	}
	return result
}

# 3
// dp[i] = max(dp[i-1]+nums[i], nums[i])
// res = max(dp[i], res)
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
}

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

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

面试题16.18.模式匹配(1)

  • 题目

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。
例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），
该字符串也匹配像"a"、"ab"和"b"这样的模式。
但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
示例 1：输入： pattern = "abba", value = "dogcatcatdog" 输出： true
示例 2：输入： pattern = "abba", value = "dogcatcatfish" 输出： false
示例 3：输入： pattern = "aaaa", value = "dogcatcatdog" 输出： false
示例 4：输入： pattern = "abba", value = "dogdogdogdog" 输出： true
解释： "a"="dogdog",b=""，反之也符合规则
提示：1 <= len(pattern) <= 1000
0 <= len(value) <= 1000
你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 枚举 O(n^2) O(n) 
func patternMatching(pattern string, value string) bool {
	countA := 0
	for i := 0; i < len(pattern); i++ {
		if pattern[i] == 'a' {
			countA++
		}
	}
	countB := len(pattern) - countA
	if value == "" {
		return countA == 0 || countB == 0
	}
	if countA < countB { // 令a>b
		countA, countB = countB, countA
		str := ""
		for i := 0; i < len(pattern); i++ {
			if pattern[i] == 'a' {
				str = str + "b"
			} else {
				str = str + "a"
			}
		}
		pattern = str
	}
	for a := 0; a <= len(value)/countA; a++ { // 枚举
		if judge(pattern, value, a, countA, countB) {
			return true
		}
	}
	return false
}

func judge(pattern string, value string, a, countA, countB int) bool {
	left := len(value) - a*countA
	if (countB == 0 && left == 0) || (countB > 0 && left%countB == 0) {
		var b int
		if countB > 0 {
			b = left / countB
		}
		var strA, strB string
		index := 0
		flag := true
		for i := 0; i < len(pattern); i++ {
			if pattern[i] == 'a' {
				str := value[index : index+a]
				if strA == "" {
					strA = str
				} else if str != strA {
					flag = false
					break
				}
				index = index + a
			} else {
				str := value[index : index+b]
				if strB == "" {
					strB = str
				} else if str != strB {
					flag = false
					break
				}
				index = index + b
			}
		}
		if flag == true && strA != strB {
			return true
		}
	}
	return false
}

面试题16.19.水域大小(2)

  • 题目

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。
若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。
编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
示例：输入：
[
  [0,2,1,0],
  [0,1,0,1],
  [1,1,0,1],
  [0,1,0,1]
]
输出： [1,2,4]
提示：
    0 < len(land) <= 1000
    0 < len(land[i]) <= 1000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 深度优先搜索 O(n^2) O(n)
02 深度优先搜索 O(n^2) O(n) 
func pondSizes(land [][]int) []int {
	res := make([]int, 0)
	for i := range land {
		for j := range land[i] {
			if land[i][j] == 0 {
				res = append(res, getArea(land, i, j))
			}
		}
	}
	sort.Ints(res)
	return res
}

func getArea(grid [][]int, i, j int) int {
	if grid[i][j] != 0 {
		return 0
	}
	grid[i][j] = 1
	area := 1
	for a := i - 1; a <= i+1; a++ {
		for b := j - 1; b <= j+1; b++ {
			if (i == a && j == b) || a < 0 || a >= len(grid) ||
				b < 0 || b >= len(grid[0]) {
				continue
			}
			area = area + getArea(grid, a, b)
		}
	}
	return area
}

# 2
func pondSizes(land [][]int) []int {
	res := make([]int, 0)
	for i := range land {
		for j := range land[i] {
			if land[i][j] == 0 {
				res = append(res, getArea(land, i, j))
			}
		}
	}
	sort.Ints(res)
	return res
}

func getArea(grid [][]int, i, j int) int {
	if i < 0 || i >= len(grid) ||
		j < 0 || j >= len(grid[0]) || grid[i][j] != 0 {
		return 0
	}

	grid[i][j] = 1
	res := 1
	res = res + getArea(grid, i+1, j)
	res = res + getArea(grid, i+1, j+1)
	res = res + getArea(grid, i+1, j-1)
	res = res + getArea(grid, i-1, j)
	res = res + getArea(grid, i-1, j+1)
	res = res + getArea(grid, i-1, j-1)
	res = res + getArea(grid, i, j+1)
	res = res + getArea(grid, i, j-1)
	return res
}

面试题16.20.T9键盘(1)

  • 题目

在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。
给定一个数字序列，实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：
示例 1:输入: num = "8733", words = ["tree", "used"] 输出: ["tree", "used"]
示例 2:输入: num = "2", words = ["a", "b", "c", "d"] 输出: ["a", "b", "c"]
提示：num.length <= 1000
    words.length <= 500
    words[i].length == num.length
    num中不会出现 0, 1 这两个数字

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n^2) O(n) 
var m [26]byte = [26]byte{
	'2', '2', '2',
	'3', '3', '3',
	'4', '4', '4',
	'5', '5', '5',
	'6', '6', '6',
	'7', '7', '7', '7',
	'8', '8', '8',
	'9', '9', '9', '9',
}

func getValidT9Words(num string, words []string) []string {
	res := make([]string, 0)
	for _, str := range words {
		if len(str) != len(num) {
			continue
		}
		flag := true
		for i := 0; i < len(str); i++ {
			if num[i] != m[str[i]-'a'] {
				flag = false
				break
			}
		}
		if flag {
			res = append(res, str)
		}
	}
	return res
}

面试题16.21.交换和(1)

  • 题目

给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。
返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。
若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。
示例:输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3] 输出: [1, 3]
示例:输入: array1 = [1, 2, 3], array2 = [4, 5, 6] 输出: []
提示：1 <= array1.length, array2.length <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n) 
func findSwapValues(array1 []int, array2 []int) []int {
	m := make(map[int]bool)
	sumA, sumB := 0, 0
	for i := 0; i < len(array1); i++ {
		sumA = sumA + array1[i]
		m[array1[i]] = true
	}
	for i := 0; i < len(array2); i++ {
		sumB = sumB + array2[i]
	}
	if (sumA+sumB)%2 == 1 {
		return nil
	}
	half := (sumA - sumB) / 2
	a, b := 0, 0
	// sumA-A[i]+B[j] == sumB-B[j]+A[i]
	// sumA-sumB=2(A[i]-B[j])
	// (sumA-sumB)/2 = A[i]-B[j]
	for _, b = range array2 {
		a = b + half
		if m[a] == true {
			return []int{a, b}
		}
	}
	return nil
}

面试题16.22.兰顿蚂蚁(1)

  • 题目

一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。
每行走一步，蚂蚁执行以下操作。
(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由'X'表示，白色方格由'_'表示，
蚂蚁所在的位置由'L', 'U', 'R', 'D'表示，分别表示蚂蚁左、上、右、下 的朝向。
只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1:输入: 0 输出: ["R"]
示例 2:输入: 2 输出:
[
 "_X",
 "LX"
]
示例 3:输入: 5 输出:
[
 "_U",
 "X_",
 "XX"
]
说明：K <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历模拟 O(n) O(n) 
func printKMoves(K int) []string {
	var dirArr = []byte{'R', 'D', 'L', 'U'}
	var dx = []int{1, 0, -1, 0}
	var dy = []int{0, -1, 0, 1}
	dir := 0 // 向右
	x, y := 0, 0
	left, right := 0, 0
	up, down := 0, 0
	m := make(map[[2]int]int) // 1黑色，0白色
	for i := 0; i < K; i++ {
		if m[[2]int{x, y}] == 1 { // 变方向
			dir = (dir + 3) % 4 // 逆时针
		} else {
			dir = (dir + 1) % 4 // 顺时针
		}
		m[[2]int{x, y}] = 1 - m[[2]int{x, y}]
		x = x + dx[dir]
		y = y + dy[dir]
		left = min(left, x)
		right = max(right, x)
		down = min(down, y)
		up = max(up, y)
	}
	w := right - left + 1
	h := up - down + 1
	res := make([]string, 0)
	for i := 0; i < h; i++ {
		arr := make([]byte, w)
		for j := 0; j < w; j++ {
			newX := j + left
			newY := up - i
			arr[j] = '_'
			if v, ok := m[[2]int{newX, newY}]; ok && v == 1 {
				arr[j] = 'X'
			}
			if newX == x && newY == y {
				arr[j] = dirArr[dir]
			}
		}
		res = append(res, string(arr))
	}
	return res
}

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

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

面试题16.24.数对和(2)

  • 题目

设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例 1:输入: nums = [5,6,5], target = 11 输出: [[5,6]]
示例 2:输入: nums = [5,6,5,6], target = 11 输出: [[5,6],[5,6]]
提示：nums.length <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序双指针 O(nlog(n)) O(n)
02 哈希辅助 O(n) O(n) 
func pairSums(nums []int, target int) [][]int {
	res := make([][]int, 0)
	sort.Ints(nums)
	left, right := 0, len(nums)-1
	for left < right {
		sum := nums[left] + nums[right]
		if target == sum {
			res = append(res, []int{nums[left], nums[right]})
			left++
			right--
		} else if target > sum {
			left++
		} else {
			right--
		}
	}
	return res
}

# 2
func pairSums(nums []int, target int) [][]int {
	res := make([][]int, 0)
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		x := target - nums[i]
		if m[x] > 0 {
			res = append(res, []int{nums[i], x})
			m[x]--
			continue
		}
		m[nums[i]]++
	}
	return res
}

面试题16.25.LRU缓存(1)

  • 题目

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。
缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。
当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。
当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
示例:LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 双向链表 O(1) O(n) 
type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

type LRUCache struct {
	cap    int
	header *Node
	tail   *Node
	m      map[int]*Node
}

func Constructor(capacity int) LRUCache {
	cache := LRUCache{
		cap:    capacity,
		header: &Node{},
		tail:   &Node{},
		m:      make(map[int]*Node, capacity),
	}
	cache.header.next = cache.tail
	cache.tail.prev = cache.header
	return cache
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.m[key]; ok {
		this.remove(node)
		this.putHead(node)
		return node.value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.m[key]; ok {
		node.value = value
		this.remove(node)
		this.putHead(node)
		return
	}
	if this.cap <= len(this.m) {
		// 删除尾部
		deleteKey := this.tail.prev.key
		this.remove(this.tail.prev)
		delete(this.m, deleteKey)
	}
	// 插入到头部
	newNode := &Node{key: key, value: value}
	this.putHead(newNode)
	this.m[key] = newNode
}

// 删除尾部节点
func (this *LRUCache) remove(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

// 插入头部
func (this *LRUCache) putHead(node *Node) {
	next := this.header.next
	this.header.next = node
	node.next = next
	next.prev = node
	node.prev = this.header
}

面试题16.26.计算器(2)

  • 题目

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。
示例 1:输入: "3+2*2" 输出: 7
示例 2:输入: " 3/2 " 输出: 1
示例 3:输入: " 3+5 / 2 " 输出: 5
说明：你可以假设所给定的表达式都是有效的。
    请不要使用内置的库函数 eval。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 栈辅助 O(n) O(n)
02 栈辅助 O(n) O(n) 
func calculate(s string) int {
	stack := make([]int, 0)
	op := make([]int, 0)
	num := 0
	for i := 0; i < len(s); i++ {
		if '0' <= s[i] && s[i] <= '9' {
			num = 0
			for i < len(s) && '0' <= s[i] && s[i] <= '9' {
				num = num*10 + int(s[i]-'0')
				i++
			}
			// 处理乘除计算
			if len(op) > 0 && op[len(op)-1] > 1 {
				if op[len(op)-1] == 2 {
					stack[len(stack)-1] = stack[len(stack)-1] * num
				} else {
					stack[len(stack)-1] = stack[len(stack)-1] / num
				}
				op = op[:len(op)-1]
			} else {
				stack = append(stack, num)
			}
			i--
		} else if s[i] == '+' {
			op = append(op, 1)
		} else if s[i] == '-' {
			op = append(op, -1)
		} else if s[i] == '*' {
			op = append(op, 2)
		} else if s[i] == '/' {
			op = append(op, 3)
		}
	}
	// 处理加减
	for len(op) > 0 {
		stack[1] = stack[0] + stack[1]*op[0]
		stack = stack[1:]
		op = op[1:]
	}
	return stack[0]
}

# 2
func calculate(s string) int {
	s = strings.Trim(s, " ") // 避免"3/2 "的情况
	stack := make([]int, 0)
	num := 0
	sign := byte('+')
	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			continue
		}
		if '0' <= s[i] && s[i] <= '9' {
			num = num*10 + int(s[i]-'0')
		}
		if s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || i == len(s)-1 {
			// 处理前一个符号
			switch sign {
			case '+':
				stack = append(stack, num)
			case '-':
				stack = append(stack, -num)
			case '*':
				prev := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				stack = append(stack, num*prev)
			case '/':
				prev := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				stack = append(stack, prev/num)
			}
			num = 0
			sign = s[i]
		}
	}
	res := 0
	for i := 0; i < len(stack); i++ {
		res = res + stack[i]
	}
	return res
}

面试题17.01.不用加号的加法(2)

  • 题目

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
示例:输入: a = 1, b = 1 输出: 2
提示： a, b 均可能是负数或 0
    结果不会溢出 32 位整数

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 迭代 O(1) O(1)
02 递归 O(1) O(1) 
/*
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0（进位 1）
异或的一个重要特性是无进位加法
(a 和 b 的无进位结果) + (a 和 b 的进位结果)
*/
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)
}

面试题17.04.消失的数字(5)

  • 题目

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：输入：[3,0,1]输出：2
示例 2：输入：[9,6,4,2,3,5,7,0,1] 输出：8

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 数学计算 O(n) O(1)
02 排序遍历 O(nlog(n)) O(1)
03 异或-位运算 O(n) O(1)
04 交换排序(就地排序) O(n) O(1)
05 哈希辅助 O(n) O(n) 
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 {
	sort.Ints(nums)
	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 {
	n := len(nums)
	index := n
	for i := 0; i < n; {
		if nums[i] == n{
			index = i
			i++
			continue
		}
		if i == nums[i]{
			i++
			continue
		}
		nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
	}
	return index
}

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

面试题17.05.字母与数字(1)

  • 题目

给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点最小的。若不存在这样的数组，返回一个空数组。
示例 1:
输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]
输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
示例 2:输入: ["A","A"]输出: []
提示：array.length <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和 O(n) O(n) 
func findLongestSubarray(array []string) []string {
	m := make(map[int]int)
	m[0] = 0
	res := 0
	begin := 0
	total := 0
	for i := 0; i < len(array); i++ {
		if '0' <= array[i][0] && array[i][0] <= '9' {
			total++
		} else {
			total--
		}
		if total == 0 {
			begin = 0
			res = i + 1
		} else if index, ok := m[total]; ok {
			if i-index > res {
				res = i - index
				begin = index + 1
			}
		} else {
			m[total] = i
		}
	}
	return array[begin : begin+res]
}

面试题17.06.2出现的次数(3)

  • 题目

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
示例:输入: 25 输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
提示：n <= 10^9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 找规律 O(log(n)) O(1)
02 找规律 O(log(n)) O(1)
03 找规律 O(log(n)) O(1) 
func numberOf2sInRange(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+7)/10*i
		if left%10 == 2 {
			res = res + right + 1
		}
	}
	return res
}

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

# 3
func numberOf2sInRange(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 >= 2 {
		return 1
	}
	count := 0
	if first > 2 {
		count = int(math.Pow(float64(10), float64(len(str)-1)))
	} else if first == 2 {
		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
}

面试题17.07.婴儿名字(1)

  • 题目

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。
有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。
给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。
注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，
则 John 与 Johnny 也相同，即它们有传递和对称性。
在结果列表中，选择 字典序最小 的名字作为真实名字。
示例：输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], 
synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]
提示：names.length <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 并查集 O(n) O(n) 
func trulyMostPopular(names []string, synonyms []string) []string {
	res := make([]string, 0)
	node = Node{}
	nameArr := make([]string, 0)
	countArr := make([]int, 0)
	m := make(map[string]int)
	for i := 0; i < len(names); i++ {
		arr := strings.Split(names[i], "(")
		nameArr = append(nameArr, arr[0])
		tempArr := strings.Split(arr[1], ")")
		count, _ := strconv.Atoi(tempArr[0])
		countArr = append(countArr, count)
		m[arr[0]] = i
	}
	Init(nameArr, countArr)

	for i := 0; i < len(synonyms); i++ {
		str := strings.TrimLeft(synonyms[i], "(")
		str = strings.TrimRight(str, ")")
		arr := strings.Split(str, ",")
		a := m[arr[0]]
		b := m[arr[1]]
		union(a, b)
	}
	for i := 0; i < len(node.fa); i++ {
		if node.fa[i] < 0 {
			temp := node.names[i] + "(" + strconv.Itoa(node.count[i]) + ")"
			res = append(res, temp)
		}
	}
	return res
}

var node Node

type Node struct {
	fa    []int
	names []string
	count []int
}

// 初始化
func Init(names []string, count []int) {
	node.fa = make([]int, len(names))
	for i := 0; i < len(names); i++ {
		node.fa[i] = -1
	}
	node.names = names
	node.count = count
}

// 查询
func find(x int) int {
	if node.fa[x] < 0 {
		return x
	}
	res := find(node.fa[x])
	node.fa[x] = res
	return res
}

// 合并
func union(i, j int) {
	x, y := find(i), find(j)
	if x == y {
		return
	}
	if node.names[x] <= node.names[y] {
		node.fa[y] = x
		node.count[x] = node.count[x] + node.count[y]
	} else {
		node.fa[x] = y
		node.count[y] = node.count[y] + node.count[x]
	}
}

面试题17.08.马戏团人塔(2)

  • 题目

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。
出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。
已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110] 输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：
(56,90), (60,95),(65,100), (68,110), (70,150), (75,190)
提示： height.length == weight.length <= 10000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 二分查找 O(nlog(n)) O(n)
02 内置函数 O(nlog(n)) O(n) 
func bestSeqAtIndex(height []int, weight []int) int {
	arr := make([][2]int, 0)
	for i := 0; i < len(height); i++ {
		arr = append(arr, [2]int{height[i], weight[i]})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i][0] == arr[j][0] {
			return arr[i][1] < arr[j][1]
		}
		return arr[i][0] > arr[j][0]
	})
	res := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		if len(res) == 0 || arr[res[len(res)-1]][0] > arr[i][0] &&
			arr[res[len(res)-1]][1] > arr[i][1] {
			res = append(res, i)
		} else {
			left := 0
			right := len(res) - 1
			for left <= right {
				mid := left + (right-left)/2
				if arr[res[mid]][0] > arr[i][0] && arr[res[mid]][1] > arr[i][1] {
					left = mid + 1
				} else {
					right = mid - 1
				}
			}
			res[left] = i
		}
	}
	return len(res)
}

# 2
func bestSeqAtIndex(height []int, weight []int) int {
	arr := make([][2]int, 0)
	for i := 0; i < len(height); i++ {
		arr = append(arr, [2]int{height[i], weight[i]})
	}
	sort.Slice(arr, func(i, j int) bool {
		if arr[i][0] == arr[j][0] {
			return arr[i][1] < arr[j][1]
		}
		return arr[i][0] > arr[j][0]
	})
	res := make([]int, 0)
	for i := 0; i < len(arr); i++ {
		index := sort.Search(len(res), func(j int) bool {
			return arr[res[j]][0] <= arr[i][0] || arr[res[j]][1] <= arr[i][1]
		})
		if index == len(res) {
			res = append(res, i)
		} else {
			res[index] = i
		}
	}
	return len(res)
}

面试题17.09.第k个数(1)

  • 题目

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。
注意，不是必须有这些素因子，而是必须不包含其他的素因子。
例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例 1:输入: k = 5输出: 9

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(n) 
func getKthMagicNumber(k int) int {
	dp := make([]int, k)
	dp[0] = 1
	// *3或5或7之后得到
	idx3, idx5, idx7 := 0, 0, 0
	for i := 1; i < k; i++ {
		dp[i] = min(dp[idx3]*3, min(dp[idx5]*5, dp[idx7]*7))
		if dp[i] == dp[idx3]*3 {
			idx3++
		}
		if dp[i] == dp[idx5]*5 {
			idx5++
		}
		if dp[i] == dp[idx7]*7 {
			idx7++
		}
	}
	return dp[k-1]
}

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

面试题17.10.主要元素(5)

  • 题目

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
示例 1：输入：[1,2,5,9,5,9,5,5,5]输出：5
示例 2：输入：[3,2]输出：-1
示例 3：输入：[2,2,1,1,1,2,2]输出：2
说明：你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 Boyer-Moore投票算法 O(n) O(1)
03 排序 O(nlog(n)) O(1)
04 位运算 O(n) O(1)
05 分治法 O(nlog(n)) O(log(n)) 
func majorityElement(nums []int) int {
	m := make(map[int]int)
	result := -1
	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
}

# 2
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--
		}
	}
	total := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == result {
			total++
		}
	}
	if total <= len(nums)/2 {
		return -1
	}
	return result
}

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

# 4
func majorityElement(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	result := int32(0)
	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
	}
	total := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == int(result) {
			total++
		}
	}
	if total <= len(nums)/2 {
		return -1
	}
	return int(result)
}

# 5
func majorityElement(nums []int) int {
	res := majority(nums, 0, len(nums)-1)
	total := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == res {
			total++
		}
	}
	if total <= len(nums)/2 {
		return -1
	}
	return res
}

func count(nums []int, target int, start int, end int) int {
	countNum := 0
	for i := start; i <= end; i++ {
		if nums[i] == target {
			countNum++
		}
	}
	return countNum
}

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
}

面试题17.11.单词距离(2)

  • 题目

有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。
如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
示例：输入：words = ["I","am","a","student","from","a","university","in","a","city"], 
word1 = "a", word2 = "student"
输出：1
提示：words.length <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 遍历 O(n) O(1)
02 数组辅助 O(n) O(n) 
func findClosest(words []string, word1 string, word2 string) int {
	res := len(words) - 1
	a, b := -1, -1
	for i := 0; i < len(words); i++ {
		if words[i] == word1 {
			a = i
		}
		if words[i] == word2 {
			b = i
		}
		if a != -1 && b != -1 && abs(a, b) < res {
			res = abs(a, b)
		}
	}
	return res
}

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

# 2
func findClosest(words []string, word1 string, word2 string) int {
	res := len(words) - 1
	arrA, arrB := make([]int, 0), make([]int, 0)
	for i := 0; i < len(words); i++ {
		if words[i] == word1 {
			arrA = append(arrA, i)
		}
		if words[i] == word2 {
			arrB = append(arrB, i)
		}
	}
	i, j := 0, 0
	for i < len(arrA) && j < len(arrB) {
		if abs(arrA[i], arrB[j]) < res {
			res = abs(arrA[i], arrB[j])
		}
		if arrA[i] < arrB[j] {
			i++
		} else {
			j++
		}
	}
	return res
}

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

面试题17.12.BiNode(2)

  • 题目

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。
实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，
也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。
注意：本题相对原题稍作改动
示例：输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示：节点数量不会超过 100000。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 递归 O(n) O(log(n))
02 迭代 O(n) O(n) 
func convertBiNode(root *TreeNode) *TreeNode {
	head := &TreeNode{}
	cur := head
	dfs(root, cur)
	return head.Right
}

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

# 2
func convertBiNode(root *TreeNode) *TreeNode {
	head := &TreeNode{}
	cur := head
	stack := make([]*TreeNode, 0)
	node := root
	for node != nil || len(stack) > 0 {
		if node != nil {
			stack = append(stack, node)
			node = node.Left
		} else {
			node = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			node.Left = nil
			cur.Right = node
			cur = node
			node = node.Right
		}
	}
	return head.Right
}

面试题17.13.恢复空格(2)

  • 题目

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。
像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。
在处理标点符号和大小写之前，你得先把它断成词语。
当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。
假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
注意：本题相对原题稍作改动，只需返回未识别的字符数
示例：输入： dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
提示：0 <= len(sentence) <= 1000
dictionary中总字符数不超过 150000。
你可以认为dictionary和sentence中只包含小写字母。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划+字典树 O(n^2) O(n)
02 动态规划+哈希 O(n^2) O(n) 
func respace(dictionary []string, sentence string) int {
	n := len(sentence)
	root := &Trie{
		next: [26]*Trie{},
	}
	for i := 0; i < len(dictionary); i++ {
		root.Insert(reverse(dictionary[i])) // 反序插入
	}
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = dp[i-1] + 1 // 上一个长度+1
		cur := root
		for j := i; j >= 1; j-- {
			value := int(sentence[j-1] - 'a')
			if cur.next[value] == nil {
				break
			} else if cur.next[value].ending > 0 { // 找到，更新
				dp[i] = min(dp[i], dp[j-1])
			}
			if dp[i] == 0 {
				break
			}
			cur = cur.next[value]
		}
	}
	return dp[n]
}

func reverse(s string) string {
	arr := []byte(s)
	for i := 0; i < len(s)/2; i++ {
		arr[i], arr[len(s)-1-i] = arr[len(s)-1-i], arr[i]
	}
	return string(arr)
}

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

type Trie struct {
	next   [26]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
	ending int       // 次数（可以改为bool）
}

// 插入word
func (this *Trie) Insert(word string) {
	temp := this
	for _, v := range word {
		value := v - 'a'
		if temp.next[value] == nil {
			temp.next[value] = &Trie{
				next:   [26]*Trie{},
				ending: 0,
			}
		}
		temp = temp.next[value]
	}
	temp.ending++
}

# 2
func respace(dictionary []string, sentence string) int {
	n := len(sentence)
	m := make(map[string]bool)
	for i := 0; i < len(dictionary); i++ {
		m[dictionary[i]] = true
	}
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = dp[i-1] + 1 // 上一个长度+1
		for j := i; j >= 1; j-- {
			str := sentence[j-1 : i]
			if m[str] == true {
				dp[i] = min(dp[i], dp[j-1])
			}
			if dp[i] == 0 {
				break
			}
		}
	}
	return dp[n]
}

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

面试题17.14.最小K个数(3)

  • 题目

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：输入： arr = [1,3,5,7,2,4,6,8], k = 4 输出： [1,2,3,4]
提示：0 <= len(arr) <= 100000
    0 <= k <= min(100000, len(arr))

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 堆排序 O(nlog(n)) O(n)
02 快排 O(nlog(n)) O(log(n))
03 内置函数 O(nlog(n)) O(1) 
func smallestK(arr []int, k int) []int {
	intHeap := make(IntHeap, 0)
	heap.Init(&intHeap)
	for i := 0; i < len(arr); i++ {
		heap.Push(&intHeap, arr[i])
	}
	res := make([]int, 0)
	for i := 0; i < k; i++ {
		value := heap.Pop(&intHeap).(int)
		res = append(res, value)
	}
	return res
}

type IntHeap []int

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

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

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

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

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

# 2
func smallestK(arr []int, k int) []int {
	return quickSort(arr, 0, len(arr)-1, k)
}

func quickSort(arr []int, left, right, k int) []int {
	if left > right {
		return nil
	}
	index := partition(arr, left, right)
	if index == k {
		return arr[:k]
	} else if index < k {
		return quickSort(arr, index+1, right, k)
	}
	return quickSort(arr, left, index-1, k)
}

func partition(arr []int, left, right int) int {
	baseValue := arr[left] // 基准值
	for left < right {
		for baseValue <= arr[right] && left < right {
			right-- // 依次查找大于基准值的位置
		}
		arr[left] = arr[right]
		for arr[left] <= baseValue && left < right {
			left++ // 依次查找小于基准值的位置
		}
		arr[right] = arr[left]
	}
	arr[right] = baseValue
	return right
}

# 3
func smallestK(arr []int, k int) []int {
	sort.Ints(arr)
	return arr[:k]
}

面试题17.15.最长单词(2)

  • 题目

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。
若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：输入： ["cat","banana","dog","nana","walk","walker","dogwalker"] 输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。
提示：0 <= len(words) <= 200
1 <= len(words[i]) <= 100

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 排序+递归 O(n^2) O(n)
02 排序+动态规划 O(n^3) O(n) 
var m map[string]bool

func longestWord(words []string) string {
	m = make(map[string]bool)
	n := len(words)
	for i := 0; i < n; i++ {
		m[words[i]] = true
	}
	sort.Slice(words, func(i, j int) bool {
		if len(words[i]) == len(words[j]) {
			return words[i] < words[j]
		}
		return len(words[i]) > len(words[j])
	})
	for i := 0; i < n; i++ { // 从最长最小字典序的开始找
		m[words[i]] = false
		if dfs(words[i]) == true {
			return words[i]
		}
	}
	return ""
}

func dfs(str string) bool {
	if len(str) == 0 || m[str] == true {
		return true
	}
	for i := 1; i <= len(str); i++ {
		subStr := str[:i]
		if m[subStr] == true {
			if dfs(str[i:]) == true {
				return true
			}
		}
	}
	return false
}

# 2
var m map[string]bool

func longestWord(words []string) string {
	m = make(map[string]bool)
	n := len(words)
	for i := 0; i < n; i++ {
		m[words[i]] = true
	}
	sort.Slice(words, func(i, j int) bool {
		if len(words[i]) == len(words[j]) {
			return words[i] < words[j]
		}
		return len(words[i]) > len(words[j])
	})
	// 从最长最小字典序的开始找
	for i := 0; i < n; i++ {
		m[words[i]] = false
		if judge(words[i]) == true {
			return words[i]
		}
	}
	return ""
}

// leetcode 139.单词拆分
func judge(s string) bool {
	dp := make([]bool, len(s)+1)
	dp[0] = true
	n := len(s)
	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			if dp[j] == true && m[s[j:i]] == true {
				dp[i] = true
				break
			}
		}
	}
	return dp[n]
}

面试题17.16.按摩师(4)

  • 题目

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：输入： [1,2,3,1] 输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
示例 2：输入： [2,7,9,3,1] 输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
示例 3：输入： [2,1,4,5,3,1,1,3] 输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 动态规划 O(n) O(1)
02 动态规划+一维数组 O(n) O(n)
03 动态规划+二维数组 O(n) O(n)
04 奇偶法 O(n) O(1) 
func massage(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	a := nums[0]
	b := max(a, nums[1])

	for i := 2; i < len(nums); i++ {
		a, b = b, max(a+nums[i], b)
	}
	return b
}

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

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

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

# 3
func massage(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	n := len(nums)
	dp := make([][]int, n)
	for n := range dp {
		dp[n] = make([]int, 2)
	}
	dp[0][0], dp[0][1] = 0, nums[0]
	for i := 1; i < n; i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1])
		dp[i][1] = dp[i-1][0] + nums[i]
	}
	return max(dp[n-1][0], dp[n-1][1])
}

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

# 4
func massage(nums []int) int {
	var a, b int
	for i, v := range nums {
		if i%2 == 0 {
			a = max(a+v, b)
		} else {
			b = max(a, b+v)
		}
	}
	return max(a, b)
}

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

面试题17.17.多次搜索(3)

  • 题目

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。
输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。
示例：输入：big = "mississippi" smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
提示：0 <= len(big) <= 1000
0 <= len(smalls[i]) <= 1000
smalls的总字符数不会超过 100000。
你可以认为smalls中没有重复字符串。
所有出现的字符均为英文小写字母。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 内置函数 O(n^2log(n)) O(n^2)
02 暴力法 O(n^3) O(n^2)
03 字典树 O(n^2) O(n^2) 
func multiSearch(big string, smalls []string) [][]int {
	n := len(smalls)
	res := make([][]int, n)
	arr := suffixarray.New([]byte(big)) // 创建后缀树
	for i := 0; i < n; i++ {
		target := []byte(smalls[i])
		temp := arr.Lookup(target, -1) // 返回arr中所有target出现的位置，从后往前
		sort.Ints(temp)
		res[i] = temp
	}
	return res
}

# 2
func multiSearch(big string, smalls []string) [][]int {
	n := len(smalls)
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		arr := make([]int, 0)
		if smalls[i] == "" {
			res[i] = arr
			continue
		}
		for j := 0; j+len(smalls[i]) <= len(big); j++ {
			if big[j:j+len(smalls[i])] == smalls[i] {
				arr = append(arr, j)
			}
		}
		res[i] = arr
	}
	return res
}

# 3
func multiSearch(big string, smalls []string) [][]int {
	n := len(smalls)
	res := make([][]int, n)
	root := &Trie{
		next: [26]*Trie{},
	}
	for i := 0; i < n; i++ {
		root.Insert(smalls[i], i+1)
	}
	for i := 0; i < len(big); i++ {
		temp := root.Search(big[i:])
		for j := 0; j < len(temp); j++ {
			res[temp[j]] = append(res[temp[j]], i)
		}
	}
	return res
}

type Trie struct {
	next   [26]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
	ending int       // 下标，从1开始
}

// 插入word
func (this *Trie) Insert(word string, index int) {
	temp := this
	for _, v := range word {
		value := v - 'a'
		if temp.next[value] == nil {
			temp.next[value] = &Trie{
				next:   [26]*Trie{},
				ending: 0,
			}
		}
		temp = temp.next[value]
	}
	temp.ending = index
}

// 查找
func (this *Trie) Search(word string) []int {
	arr := make([]int, 0) // 存放匹配到的下标列表
	temp := this
	for _, v := range word {
		value := v - 'a'
		if temp = temp.next[value]; temp == nil {
			return arr
		}
		if temp.ending > 0 {
			arr = append(arr, temp.ending-1)
		}
	}
	return arr
}

面试题17.18.最短超串(1)

  • 题目

假设你有两个数组，一个长一个短，短的元素均不相同。
找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 1:输入:big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7] small = [1,5,9] 输出: [7,10]
示例 2:输入: big = [1,2,3] small = [4] 输出: []
提示： big.length <= 100000
    1 <= small.length <= 100000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 滑动窗口 O(n) O(n) 
func shortestSeq(big []int, small []int) []int {
	res := make([]int, 0)
	m := make(map[int]int)
	for i := 0; i < len(small); i++ {
		m[small[i]]++
	}
	total := len(m)
	j := 0
	for i := 0; i < len(big); i++ {
		m[big[i]]--
		if m[big[i]] == 0 {
			total--
		}
		for total == 0 {
			m[big[j]]++
			if m[big[j]] > 0 {
				total++
				if len(res) == 0 || res[1]-res[0] > i-j {
					res = []int{j, i}
				}
			}
			j++
		}
	}
	return res

面试题17.19.消失的两个数字(4)

  • 题目

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。
你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:输入: [1] 输出: [2,3]
示例 2:输入: [2,3] 输出: [1,4]
提示：nums.length <= 30000

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n) O(n)
02 数学 O(n) O(1)
03 交换 O(n) O(1)
04 异或 O(n) O(1) 
func missingTwo(nums []int) []int {
	res := make([]int, 0)
	m := make(map[int]bool)
	for i := 0; i < len(nums); i++ {
		m[nums[i]] = true
	}
	for i := 1; i <= len(nums)+2; i++ {
		if m[i] == false {
			res = append(res, i)
		}
	}
	return res
}

# 2
func missingTwo(nums []int) []int {
	n := len(nums) + 2
	sum := (1 + n) * n / 2
	total := 0
	for i := 0; i < len(nums); i++ {
		total = total + nums[i]
	}
	diff := sum - total // a+b
	mid := diff / 2     // (a+b)/2
	tempSum := (1 + mid) * mid / 2
	temp := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] <= mid {
			temp = temp + nums[i]
		}
	}
	a := tempSum - temp
	b := diff - a
	return []int{a, b}
}

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

# 4
func missingTwo(nums []int) []int {
	temp := 0
	for i := 0; i < len(nums); i++ {
		temp = temp ^ nums[i]
	}
	for i := 1; i <= len(nums)+2; i++ {
		temp = temp ^ i
	}
	a := 0
	diff := temp & (-temp)
	for i := 1; i <= len(nums)+2; i++ {
		if diff&i != 0 {
			a = a ^ i
		}
	}
	for i := 0; i < len(nums); i++ {
		if diff&nums[i] != 0 {
			a = a ^ nums[i]
		}
	}
	return []int{a, a ^ temp}
}

面试题17.20.连续中值(1)

  • 题目

随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，[2,3,4]的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

  • 解题思路

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

面试题17.21.直方图的水量(4)

  • 题目

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，
在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。
示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 暴力法 O(n^2) O(1)
02 数组辅助 O(n) O(n)
03 栈辅助 O(n) O(n)
04 双指针 O(n) O(1) 
func trap(height []int) int {
	res := 0
	for i := 0; i < len(height); i++ {
		left, right := 0, 0
		for j := i; j >= 0; j-- {
			left = max(left, height[j])
		}
		for j := i; j < len(height); j++ {
			right = max(right, height[j])
		}
		// 当前坐标形成的面积=(min(左边最高，右边最高)-当前高度) * 宽度(1,可省略)
		area := min(left, right) - height[i]
		res = res + area
	}
	return res
}

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

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

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

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

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

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

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

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

面试题17.22.单词转换(2)

  • 题目

给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。
每一步得到的新词都必须能在字典中找到。
编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
示例 1:输入:beginWord = "hit", endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:["hit","hot","dot","lot","log","cog"]
示例 2:输入:beginWord = "hit" endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 广度优先搜索 O(n^2) O(n^2)
02 广度优先搜索 O(n^2) O(n^2) 
func findLadders(beginWord string, endWord string, wordList []string) []string {
	m, preMap := make(map[string]int), make(map[string][]string)
	for i := 0; i < len(wordList); i++ {
		m[wordList[i]] = 1
	}
	if m[endWord] == 0 {
		return nil
	}
	for i := 0; i < len(wordList); i++ {
		for j := 0; j < len(wordList[i]); j++ {
			newStr := wordList[i][:j] + "*" + wordList[i][j+1:]
			preMap[newStr] = append(preMap[newStr], wordList[i])
		}
	}
	visited := make(map[string]bool)
	queue, path := make([]string, 0), make([][]string, 0)
	queue, path = append(queue, beginWord), append(path, []string{beginWord})
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			for j := 0; j < len(beginWord); j++ {
				newStr := queue[i][:j] + "*" + queue[i][j+1:]
				temp := make([]string, len(path[i]))
				copy(temp, path[i])
				for _, word := range preMap[newStr] {
					if word == endWord {
						return append(temp, endWord)
					} else if visited[word] == false {
						visited[word] = true
						queue, path = append(queue, word), append(path, append(temp, word))
					}
				}
			}
		}
		queue, path = queue[length:], path[length:]
	}
	return nil
}

# 2
func findLadders(beginWord string, endWord string, wordList []string) []string {
	m := make(map[string]int)
	for i := 0; i < len(wordList); i++ {
		m[wordList[i]] = 1
	}
	if m[endWord] == 0 {
		return nil
	}
	preMap := make(map[string][]string)
	for i := 0; i < len(wordList); i++ {
		for j := 0; j < len(wordList[i]); j++ {
			newStr := wordList[i][:j] + "*" + wordList[i][j+1:]
			if _, ok := preMap[newStr]; !ok {
				preMap[newStr] = make([]string, 0)
			}
			preMap[newStr] = append(preMap[newStr], wordList[i])
		}
	}
	visited := make(map[string]bool)
	count := 0
	queue := make([]string, 0)
	queue = append(queue, beginWord)
	path := make([][]string, 0)
	path = append(path, []string{beginWord})
	for len(queue) > 0 {
		count++
		node := queue[0]
		queue = queue[1:]
		arr := path[0]
		path = path[1:]
		for j := 0; j < len(beginWord); j++ {
			newStr := node[:j] + "*" + node[j+1:]
			temp := make([]string, len(arr))
			copy(temp, arr)
			for _, word := range preMap[newStr] {
				if word == endWord {
					return append(temp, endWord)
				}
				if visited[word] == false {
					visited[word] = true
					queue = append(queue, word)
					path = append(path, append(temp, word))
				}
			}
		}
	}
	return nil
}

面试题17.23.最大黑方阵

题目

给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中r,c分别代表子方阵左上角的行号和列号，size 是子方阵的边长。
若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。
若无满足条件的子方阵，返回空数组。
示例 1:输入:
[
  [1,0,1],
  [0,0,1],
  [0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2:输入:
[
  [0,1,1],
  [1,0,1],
  [1,1,0]
]
输出: [0,0,1]
提示：matrix.length == matrix[0].length <= 200

解题思路

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

面试题17.24.最大子矩阵(3)

  • 题目

给定一个正整数、负整数和 0 组成的 N × M矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。
若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动
示例：输入：
[
  [-1,0],
  [0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵
说明：1 <= matrix.length, matrix[0].length <= 200

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 前缀和+最大子序和 O(n^3) O(n^2)
02 前缀和+最大子序和 O(n^3) O(n^2)
03 最大子序和 O(n^3) O(n) 
func getMaxMatrix(matrix [][]int) []int {
	n, m := len(matrix), len(matrix[0])
	arr := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr[i+1][j+1] = matrix[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
		}
	}
	maxValue := math.MinInt32
	res := make([]int, 0)
	for a := 1; a <= n; a++ { // 上边界
		for b := a; b <= n; b++ { // 下边界
			left := 1
			value := 0
			for right := 1; right <= m; right++ {
				value = arr[b][right] - arr[b][left-1] - arr[a-1][right] + arr[a-1][left-1]
				if value > maxValue {
					maxValue = value
					res = []int{a - 1, left - 1, b - 1, right - 1}
				}
				if value < 0 {
					value = 0
					left = right + 1
				}
			}
		}
	}
	return res
}

# 2
func getMaxMatrix(matrix [][]int) []int {
	n, m := len(matrix), len(matrix[0])
	arr := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		arr[i] = make([]int, m+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arr[i+1][j+1] = matrix[i][j] + arr[i+1][j] + arr[i][j+1] - arr[i][j]
		}
	}
	maxValue := math.MinInt32
	res := make([]int, 0)
	for a := 0; a < n; a++ { // 上边界
		for b := a; b < n; b++ { // 下边界
			left := 0
			value := 0
			for right := 0; right < m; right++ {
				value = arr[b+1][right+1] - arr[b+1][left] - arr[a][right+1] + arr[a][left]
				if value > maxValue {
					maxValue = value
					res = []int{a, left, b, right}
				}
				if value < 0 {
					value = 0
					left = right + 1
				}
			}
		}
	}
	return res
}

# 3
func getMaxMatrix(matrix [][]int) []int {
	n, m := len(matrix), len(matrix[0])
	maxValue := math.MinInt32
	res := make([]int, 0)
	for a := 0; a < n; a++ { // 上边界
		arr := make([]int, m)
		for b := a; b < n; b++ { // 下边界
			left := 0
			value := 0
			for right := 0; right < m; right++ {
				arr[right] = arr[right] + matrix[b][right]
				value = value + arr[right]
				if value > maxValue {
					maxValue = value
					res = []int{a, left, b, right}
				}
				if value < 0 {
					value = 0
					left = right + 1
				}
			}
		}
	}
	return res
}

面试题17.26.稀疏相似度(1)

  • 题目

两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，
就是这两个文档的相似度。
例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 个，并集的元素有 5 个。
给定一系列的长篇文档，每个文档元素各不相同，并与一个 ID 相关联。
它们的相似度非常“稀疏”，也就是说任选 2 个文档，相似度都很接近 0。
请设计一个算法返回每对文档的 ID 及其相似度。
只需输出相似度大于 0 的组合。请忽略空文档。
为简单起见，可以假定每个文档由一个含有不同整数的数组表示。
输入为一个二维数组 docs，docs[i]表示id 为 i 的文档。
返回一个数组，其中每个元素是一个字符串，代表每对相似度大于 0 的文档，
其格式为 {id1},{id2}: {similarity}，其中 id1 为两个文档中较小的 id，similarity 为相似度，
精确到小数点后 4 位。以任意顺序返回数组均可。
示例:输入: 
[
 [14, 15, 100, 9, 3],
 [32, 1, 9, 3, 5],
 [15, 29, 2, 6, 8, 7],
 [7, 10]
]
输出:
[
 "0,1: 0.2500",
 "0,2: 0.1000",
 "2,3: 0.1429"
]
提示：docs.length <= 500
docs[i].length <= 500

  • 解题思路

No. 思路 时间复杂度 空间复杂度
01 哈希辅助 O(n^3) O(n^2) 
func computeSimilarities(docs [][]int) []string {
	res := make([]string, 0)
	n := len(docs)
	m := make(map[[2]int]int)
	m1 := make(map[int][]int) // 字符出现的位置
	for i := 0; i < n; i++ {
		for j := 0; j < len(docs[i]); j++ {
			char := docs[i][j]
			for _, v := range m1[char] {
				m[[2]int{v, i}]++
			}
			m1[char] = append(m1[char], i)
		}
	}
	for k, v := range m {
		x := v
		y := len(docs[k[0]]) + len(docs[k[1]]) - v
		res = append(res, fmt.Sprintf("%d,%d: %.4f",
			k[0], k[1], float64(x)/float64(y)+1e-9))
	}
	return res
}