程序员面试金典
面试题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,"")
}
#
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)
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]
}
}
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.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
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 {
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))
}
}
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++ {
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
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
}
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] = "."
}
}
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] = "."
}
}
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] = "."
}
}
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 := 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 := 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 := 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) {
for i <= this.length {
this.c[i] = this.c[i] + k
i = i + this.lowBit(i)
}
}
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) |
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 {
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)
return value*b + int(1^value)*a
}
面试题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 {
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 {
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}
}
k := (y1 - y2) / (x1 - x2)
b1 := y1 - k*x1
if abs(k) > 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 {
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 {
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++ {
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
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 {
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
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)
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, " ")
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) |
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
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
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
ending int
}
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
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 ""
}
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)
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
ending int
}
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
mid := diff / 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])
}
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++ {
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]
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 {
if height[left] < height[right] {
if height[left] >= leftMax {
leftMax = height[left]
} else {
res = res + leftMax - height[left]
}
left++
} else {
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
}