数据结构与算法面试题
2022-10-28 / 可可西里

常见高频面试数据结构与算法题

出现的频率从上到下依次递减

1. 反转链表（Go）206-容易

题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

示例：

1
2
3
4
5
6
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
输入：head = [1,2]
输出：[2,1]
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

思路：

方法一：迭代
假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次
  • 空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package main

import "fmt"

// ListNode 定义单链表
type ListNode struct {
	Value int
	Next  *ListNode
}

// Solution 反转单链表
func Solution(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head
	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}

// CreateListNode 使用slice生成单链表
func CreateListNode(nums []int) *ListNode {
	var head ListNode
	var pre ListNode
	for _, num := range nums {
		node := ListNode{Value: num, Next: nil}
		if head.Next == nil {
			head.Next = &node
		}
		if pre.Next == nil {
			pre.Next = &node
		} else {
			pre.Next.Next = &node
			pre = *pre.Next
		}
	}
	return head.Next
}

// Traverse 遍历链表
func Traverse(t *ListNode) {
	if t == nil {
		fmt.Println("空链表")
	}
	for t != nil {
		fmt.Printf("%d ", t.Value)
		t = t.Next
	}
	fmt.Println()
}

func main() {
	nums := []int{1, 3, 2, 4, 5, 7, 8, 9, 6, 10}
	head := CreateListNode(nums)
	// 遍历链表
	Traverse(head)
	// 反转链表
	solution := Solution(head)
	// 遍历反转后的链表
	Traverse(solution)
}

2. LRU缓存（Go）146-中等

题目：

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构
实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

思路：

方法一：哈希表 + 双向链表

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的
  • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

  • 对于 get 操作，首先判断 key 是否存在：

    • 如果 key 不存在，则返回 −1
    • 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值

  • 对于 put 操作，首先判断 key 是否存在：

    • 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项
    • 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部

上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成

复杂度分析：

  • 时间复杂度：对于 put 和 get 都是 O(1)
  • 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
type LRUCache struct {
    size int
    capacity int
    cache map[int]*DLinkedNode
    head, tail *DLinkedNode
}

type DLinkedNode struct {
    key, value int
    prev, next *DLinkedNode
}

func initDLinkedNode(key, value int) *DLinkedNode {
    return &DLinkedNode{
        key: key,
        value: value,
    }
}

func Constructor(capacity int) LRUCache {
    lruCache := LRUCache{
        cache: map[int]*DLinkedNode{},
        head: initDLinkedNode(0, 0),
        tail: initDLinkedNode(0, 0),
        capacity: capacity,
    }
    lruCache.head.next = lruCache.tail
    lruCache.tail.prev = lruCache.head
    return lruCache
}

func (this *LRUCache) Get(key int) int {
    _, ok := this.cache[key]
    if !ok {
        return -1
    }
    node := this.cache[key]
    this.moveToHead(node)
    return node.value
}

func (this *LRUCache) Put(key int, value int)  {
    _, ok := this.cache[key]
    if !ok {
        node := initDLinkedNode(key, value)
        this.cache[key] = node
        this.addToHead(node)
        this.size++
        if this.size > this.capacity {
            removeed :=this.removeTail()
            delete(this.cache, removeed.key)
            this.size--
        }
    } else {
        node := this.cache[key]
        node.value = value
        this.moveToHead(node)
    }
}

func (this *LRUCache) addToHead(node *DLinkedNode) {
    node.prev = this.head
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
}

func (this *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (this *LRUCache) moveToHead(node *DLinkedNode) {
    this.removeNode(node)
    this.addToHead(node)
}

func (this *LRUCache) removeTail() *DLinkedNode {
    node := this.tail.prev
    this.removeNode(node)
    return node
}

3. CodeTop补充题：手撕快速排序（Go） | 排序数组 912-中等

10大排序算法： 1. 冒泡排序，2. 选择排序，3. 插入排序，4. 归并排序，5. 快速排序，6. 堆排序，8. 计数排序，9. 桶排序，10. 基数排序

题目：

给你一个整数数组 nums，请你将该数组升序排列

示例：

1
2
3
4
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

  • 1 <= nums.length <= 5 * 10^4
  • -5 * 10^4 <= nums[i] <= 5 * 10^4

思路：

方法一：快速排序
思路和算法

快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序

我们定义函数 randomized_quicksort(nums, l, r) 为对 nums 数组里 [l,r]的部分进行排序，每次先调用 randomized_partition 函数对 nums 数组里 [l,r]的部分进行划分，并返回分界值的下标 pos，然后按上述将的递归调用 randomized_quicksort(nums, l, pos - 1) 和 randomized_quicksort(nums, pos + 1, r) 即可

那么核心就是划分函数的实现了，划分函数一开始需要确定一个分界值（我们称之为主元 pivot)，然后再进行划分。而主元的选取有很多种方式，这里我们采用随机的方式，对当前划分区间 [l,r] 里的数等概率随机一个作为我们的主元，再将主元放到区间末尾，进行划分

整个划分函数 partition 主要涉及两个指针 i 和 j，一开始 i = l - 1，j = l。我们需要实时维护两个指针使得任意时候，对于任意数组下标 k，我们有如下条件成立：

  1. l≤k≤i 时，nums[k]≤pivot
  2. i+1≤k≤j−1 时，nums[k]>pivot
  3. k==r 时，nums[k]=pivot

我们每次移动指针 j ，如果 nums[j]>pivot，我们只需要继续移动指针 j ，即能使上述三个条件成立，否则我们需要将指针 i 加一，然后交换 nums[i] 和 nums[j]，再移动指针 j 才能使得三个条件成立

当 j 移动到 r−1 时结束循环，此时我们可以由上述三个条件知道 [l,i] 的数都小于等于主元 pivot，[i+1,r−1] 的数都大于主元 pivot，那么我们只要交换 nums[i+1] 和 nums[r] ，即能使得 [l,i+1] 区间的数都小于 [i+2,r] 区间的数，完成一次划分，且分界值下标为 i+1，返回即可

复杂度分析：

  • 时间复杂度：基于随机选取主元的快速排序时间复杂度为期望 O(nlogn)，其中 n 为数组的长度
  • 空间复杂度：O(h)，其中 h 为快速排序递归调用的层数。我们需要额外的 O(h) 的递归调用的栈空间，由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 O(n) 的空间，最优情况下每次都平衡，此时整个递归树高度为 logn，空间复杂度为 O(logn)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package main

import "fmt"

// 函数将对数组进行原地排序，不返回任何东西。
func quickSort(nums []int, left, right int) {
	// 如果左索引小于右索引，说明还有元素需要排序
	if left < right {
		// 执行分区操作，获取基准元素的索引
		pivot := partition(nums, left, right)
		// 递归地对基准元素的左边和右边进行快速排序
		quickSort(nums, left, pivot-1)
		quickSort(nums, pivot+1, right)
	}
}

// 定义一个分区函数，接受一个整数数组和左右索引，返回基准元素的索引
func partition(nums []int, left, right int) int {
	// 选择最右边的元素作为基准元素
	pivot := nums[right]
	// 定义 i 为小于基准元素的区域的右边界，初始值为 left-1
	i := left - 1
	// 遍历左边到右边之间的元素
	for j := left; j < right; j++ {
		// 如果当前元素小于基准元素，就将其移到小于区域的右边界之后
		if nums[j] < pivot {
			i++
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	// 最后，将基准元素移到小于区域的右边界之后，并返回其索引
	nums[i+1], nums[right] = nums[right], nums[i+1]
	return i + 1
}

func main() {
	nums := []int{10, 7, 8, 9, 1, 5, 25, 11}
	quickSort(nums, 0, len(nums)-1)
	fmt.Println("Sorted nums:", nums)
}

4. 合并两个有序链表（Go） 21-简单

题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

示例：

1
2
3
4
5
6
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = []
输出：[]
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

思路：

方法一：递归
思路

我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

list1[0] + merge(list1[1:], list2) list1[0] < list2[0]

list2[0] + merge(list1, list2[1:]) otherwise

也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并

算法：

我们直接将以上递归过程建模，同时需要考虑边界情况

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束

复杂度分析：

  • 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)
  • 空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package main

import "fmt"

type ListNode struct {
	Value int
	Next  *ListNode
}

// CreateListNode 使用slice创建单链表
func CreateListNode(nums []int) *ListNode {
	var head ListNode
	var pre ListNode
	for _, num := range nums {
		node := ListNode{Value: num, Next: nil}
		if head.Next == nil {
			head.Next = &node
		}
		if pre.Next == nil {
			pre.Next = &node
		} else {
			pre.Next.Next = &node
			pre = *pre.Next
		}
	}
	return head.Next
}

// Traverse 遍历链表
func Traverse(t *ListNode) {
	if t == nil {
		fmt.Println("空链表")
	}
	for t != nil {
		fmt.Printf(" %d", t.Value)
		t = t.Next
	}
	fmt.Println()
}

// MergeTwoListNode 合并2个链表
func MergeTwoListNode(List1, List2 *ListNode) *ListNode {
	// 如果有一条链表为nil，直接返回另一条链表
	if List1 == nil {
		return List2
	}
	if List2 == nil {
		return List1
	}
	// 定义一个节点
	var result *ListNode
	if List1.Value >= List2.Value {
		result = List2
		result.Next = MergeTwoListNode(List1, List2.Next)
	} else {
		result = List1
		result.Next = MergeTwoListNode(List1.Next, List2)
	}
	return result
}

func main() {
	nums1 := []int{1, 3, 5, 7, 9}
	nums2 := []int{2, 3, 4, 6, 8, 10, 11}
	lis1 := CreateListNode(nums1)
	lis2 := CreateListNode(nums2)
	mergeTwoListNode := MergeTwoListNode(lis1, lis2)
	Traverse(mergeTwoListNode)
}

5. 最大子数组和（Go）53-简单

题目：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

子数组 是数组中的一个连续部分

示例：

1
2
3
4
5
6
7
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6
输入：nums = [1]
输出：1
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

思路：

方法一：动态规划（核心：若前一个元素大于0，则将其加到当前元素上）
思路和算法

假设 nums 数组的长度是 n，下标从 0 到 n−1

我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：
0≤i的max≤n−1的{f(i)}

因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考虑 nums[i] 单独成为一段还是加入 f(i−1) 对应的那一段，这取决于 nums[i] 和 f(i-1) +nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：
f(i)=max{f(i−1)+nums[i],nums[i]}

不难给出一个时间复杂度 O(n)、空间复杂度 O(n) 的实现，即用一个 ff 数组来保存 f(i) 的值，用一个循环求出所有 f(i)。考虑到 f(i) 只和 f(i−1) 相关，于是我们可以只用一个变量 pre 来维护对于当前 f(i) 的 f(i−1) 的值是多少，从而让空间复杂度降低到 O(1)，这有点类似「滚动数组」的思想

复杂度分析：

  • 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量

代码：

1
2
3
4
5
6
7
8
9
10
11
12
func maxSubArray(nums []int) int {
    max := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] + nums[i - 1] > nums[i] {
            nums[i] += nums[i - 1]
        }
        if nums[i] > max {
            max = nums[i]
        }
    }
    return max
}

6. 字符串相加（Go）415-简单

题目：

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式

示例：

1
2
3
4
5
6
输入：num1 = "11", num2 = "123"
输出："134"
输入：num1 = "456", num2 = "77"
输出："533"
输入：num1 = "0", num2 = "0"
输出："0"

提示：

  • 1 <= num1.length, num2.length <= 10的4次方
  • num1 和num2 都只包含数字 0-9
  • num1 和num2 都不包含任何前导零

思路：

方法一：模拟
思路与算法

本题我们只需要对两个大整数模拟「竖式加法」的过程。竖式加法就是我们平常学习生活中常用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的操作，是不是如下图将相同数位对齐，从低到高逐位相加，如果当前位和超过 10，则向高位进一位？因此我们只要将这个过程用代码写出来即可

具体实现也不复杂，我们定义两个指针 i 和 j 分别指向 num1 和 num 2 的末尾，即最低位，同时定义一个变量 add 维护当前是否有进位，然后从末尾到开头逐位相加即可。你可能会想两个数字位数不同怎么处理，这里我们统一在指针当前下标处于负数的时候返回 0，等价于对位数较短的数字进行了补零操作，这样就可以除去两个数字位数不同情况的处理，具体可以看下面的代码

复杂度分析：

  • 时间复杂度：O(max(len1,len2))，其中 len1=num1.length，len2=num2.length。竖式加法的次数取决于较大数的位数
  • 空间复杂度：O(1)。除答案外我们只需要常数空间存放若干变量。在 Java 解法中使用到了 StringBuffer，故 Java 解法的空间复杂度为O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func addStrings(num1 string, num2 string) string {
    add := 0
    ans := ""
    for i, j := len(num1) - 1, len(num2) - 1; i >= 0 ||
    j >= 0 || add != 0; i, j = i - 1, j - 1 {
        var x, y int
        if i >= 0 {
            x = int(num1[i] - '0')
        }
        if j >= 0 {
            y = int(num2[j] - '0')
        }
        result := x + y + add
        ans = strconv.Itoa(result % 10) + ans
        add = result / 10
    }
    return ans
}

7. 二分查找（Go）704-简单

题目：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1

示例：

1
2
3
4
5
6
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的
  2. n 将在 [1, 10000]之间
  3. nums 的每个元素都将在 [-9999, 9999]之间

思路：

方法一：二分查找
在升序数组 nums 中寻找目标值 target，对于特定下标 i，比较 nums[i] 和 target 的大小：

  • 如果 nums[i] = target，则下标 i 即为要寻找的下标

  • 如果 nums[i] > target，则 target 只可能在下标 i 的左侧

  • 如果 nums[i] < target，则 target 只可能在下标 i 的右侧

基于上述事实，可以在有序数组中使用二分查找寻找目标值
二分查找的做法是，定义查找的范围 [left,right]，初始查找范围是整个数组。每次取查找范围的中点 mid，比较 nums[mid] 和 target 的大小，如果相等则 mid 即为要寻找的下标，如果不相等则根据 nums[mid] 和 target 的大小关系将查找范围缩小一半

由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 O(logn)，其中 n 是数组的长度

二分查找的条件是查找范围不为空，即 left <= right。如果 target 在数组中，二分查找可以保证找到 target，返回 target 在数组中的下标。如果 target 不在数组中，则当 left > right 时结束查找，返回 -1

复杂度分析：

  • 时间复杂度：O(logn)，其中 n 是数组的长度
  • 空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func search(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for left < right {
        mid := (right - left) / 2 + left
        num := nums[mid]
        if num == target {
            return mid
        } else if num > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

8. 无重复字符串的最长子串（Go）3-中等

题目：

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

示例：

1
2
3
4
5
6
7
8
9
10
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

思路：

方法一：滑动窗口

思路和算法

我们先用一个例子考虑如何在较优的时间复杂度内通过本题

我们不妨以示例一中的字符串 abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

  • 以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb

  • 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb

  • 以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb

  • 以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb

  • 以 abca(b)cbb 开始的最长字符串为 abca(bc)bb

  • 以 abcab(c)bb 开始的最长字符串为 abcab(cb)b

  • 以 abcabc(b)b 开始的最长字符串为 abcabc(b)b

  • 以 abcabcb(b) 开始的最长字符串为 abcabcb(b)

发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 tk 。那么当我们选择第 k+1 个字符作为起始位置时，首先从 k+1 到 tk 的字符显然是不重复的，并且由于少了原本的第 k 个字符，我们可以尝试继续增大 tk，直到右侧出现了重复字符为止

这样一来，我们就可以使用「滑动窗口」来解决这个问题了：

  • 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 rk
  • 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度
  • 在枚举结束后，我们找到的最长的子串的长度即为答案

判断重复字符：

在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（即 C++中的 std::unordered_set，Java 中的 HashSet，Python 中的 set , JavaScript 中的 Set）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符

至此，我们就完美解决了本题

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次
  • 空间复杂度：O(∣Σ∣)，其中Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func lengthOfLongestSubstring(s string) int {
    // 哈希集合，记录每个字符串是否出现过
    m := map[byte]int{}
    n := len(s)
    // 右指针，初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动
    rk, ans := -1, 0
    for i := 0; i < n; i++ {
        if i != 0 {
        // 左指针向右移动一格，移除一个字符串
            delete(m, s[i - 1])
        }
        for rk + 1 < n && m[s[rk + 1]] == 0 {
            // 不断的移动右指针
            m[s[rk + 1]]++
            rk++
        }
        // 第i到rk个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1)
    }
    return ans
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

9. 数组中的第K个最大元素（Go）215-中等

题目：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

示例：

1
2
3
4
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 10的4次方
  • -10的4次方 <= nums[i] <= 10的4次方

思路：

方法一：基于快速排序的选择方法

思路和算法

我们可以用快速排序来解决这个问题，先对原数组排序，再返回倒数第 k 个位置，这样平均时间复杂度是 O(nlogn)，但其实我们可以做的更快

首先我们来回顾一下快速排序，这是一个典型的分治算法。我们对数组 a[l⋯r] 做快速排序的过程是（参考《算法导论》）：

  • 分解： 将数组 a[l⋯r] 「划分」成两个子数组 a[l⋯q−1]、a[q+1⋯r]，使得 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。其中，计算下标 q 也是「划分」过程的一部分
  • 解决： 通过递归调用快速排序，对子数组 a[l⋯q−1] 和 a[q+1⋯r] 进行排序
  • 合并： 因为子数组都是原址排序的，所以不需要进行合并操作，a[l⋯r] 已经有序
  • 上文中提到的 「划分」 过程是：从子数组 a[l⋯r] 中选择任意一个元素 x 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， x 的最终位置就是 q

由此可以发现每次经过「划分」操作后，我们一定可以确定一个元素的最终位置，即 x 的最终位置为 q，并且保证 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案。 我们只关心这一点，至于 a[l⋯q−1] 和 a[q+1⋯r] 是否是有序的，我们不关心

因此我们可以改进快速排序算法来解决这个问题：在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法

我们知道快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n−1，每次递归的时候又向 n−1 的集合中递归，这种情况是最坏的，时间代价是 O n的2次方。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」

复杂度分析：

  • 时间复杂度：O(n)，如上文所述，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」
  • 空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为 O(logn)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func findKthLargest(nums []int, k int) int {
    rand.Seed(time.Now().UnixNano())
    return quickSelect(nums, 0, len(nums) - 1, len(nums) - k)
}

func quickSelect(a []int, l, r, index int) int {
    q := randomPartition(a, l, r)
    if q == index {
        return a[q]
    } else if q < index {
        return quickSelect(a, q + 1, r, index)
    }
    return quickSelect(a, l, q - 1, index)
}

func randomPartition(a []int, l, r int) int {
    i := rand.Int() % (r - l + 1) + 1
    a[i], a[r] = a[r], a[i]
    return partition(a, l, r)
}

func partition(a []int, l, r int) int {
    x := a[r]
    i := l - 1
    for j := 1; j < r; j ++ {
        if a[j] <= x {
            i++
            a[i], a[j] = a[j], a[i]
        }
    }
    a[i + 1], a[r] = a[r], a[i + 1]
    return i + 1
}

10. 字符串转换整数 8-中等

题目：

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数

函数 myAtoi(string s) 的算法如下：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略
    将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）
  4. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整
  5. 应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1
  6. 返回整数作为最终结果

注意：

  • 本题中的空白字符只包括空格字符 ' '
  • 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193

提示：

  • 0 <= s.length <= 200
  • s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

思路：

方法一：自动机

思路

字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码

因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：

我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s 的表格即可解决题目中的问题

算法

本题可以建立如下图所示的自动机：

我们也可以用下面的表格来表示这个自动机：

接下来编程部分就非常简单了：我们只需要把上面这个状态转换表抄进代码即可

另外自动机也需要记录当前已经输入的数字，只要在 s 为 in_number 时，更新我们输入的数字，即可最终得到输入的数字

复杂度分析：

  • 时间复杂度：O(n)，其中 nn 为字符串的长度。我们只需要依次处理所有的字符，处理每个字符需要的时间为 O(1)
  • 空间复杂度：O(1)。自动机的状态只需要常数空间存储

代码：

1
2
3
class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31

class Automaton:
    def __init__(self):
        self.state = 'start'
        self.sign = 1
        self.ans = 0
        self.table = {
            'start': ['start', 'signed', 'in_number', 'end'],
            'signed': ['end', 'end', 'in_number', 'end'],
            'in_number': ['end', 'end', 'in_number', 'end'],
            'end': ['end', 'end', 'end', 'end'],
        }
        
    def get_col(self, c):
        if c.isspace():
            return 0
        if c == '+' or c == '-':
            return 1
        if c.isdigit():
            return 2
        return 3

    def get(self, c):
        self.state = self.table[self.state][self.get_col(c)]
        if self.state == 'in_number':
            self.ans = self.ans * 10 + int(c)
            self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
        elif self.state == 'signed':
            self.sign = 1 if c == '+' else -1

class Solution:
    def myAtoi(self, str: str) -> int:
        automaton = Automaton()
        for c in str:
            automaton.get(c)
        return automaton.sign * automaton.ans

11. 回文链表（Go）234-简单

题目：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false

示例：

1
2
3
4
输入：head = [1,2,2,1]
输出：true
输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 10^5] 内
  • 0 <= Node.val <= 9

思路：

方法一：将值复制到数组中后用双指针法
思路

如果你还不太熟悉链表，下面有关于列表的概要讲述

有两种常用的列表实现，分别为数组列表和链表。如果我们想在列表中存储值，它们是如何实现的呢

  • 数组列表底层是使用数组存储值，我们可以通过索引在 O(1) 的时间访问列表任何位置的值，这是由基于内存寻址的方式
  • 链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 O(n) 的时间，因为要通过指针获取到下一个位置的节点

确定数组列表是否回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。这需要 O(n) 的时间，因为访问每个元素的时间是 O(1)，而有 n 个元素要访问

然而同样的方法在链表上操作并不简单，因为不论是正向访问还是反向访问都不是 O(1)。而将链表的值复制到数组列表中是 O(n)，因此最简单的方法就是将链表的值复制到数组列表中，再使用双指针法判断

算法

一共为两个步骤：

  1. 复制链表值到数组列表中
  2. 使用双指针法判断是否为回文

第一步，我们需要遍历链表将值复制到数组列表中。我们用 currentNode 指向当前节点。每次迭代向数组添加 currentNode.val，并更新 currentNode = currentNode.next，当 currentNode = null` 时停止循环

执行第二步的最佳方法取决于你使用的语言。在 Python 中，很容易构造一个列表的反向副本，也很容易比较两个列表。而在其他语言中，就没有那么简单。因此最好使用双指针法来检查是否为回文。我们在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，返回 false；相同则将两个指针向内移动，并继续判断，直到两个指针相遇

在编码的过程中，注意我们比较的是节点值的大小，而不是节点本身。正确的比较方式是：node_1.val == node_2.val，而 node_1 == node_2 是错误的

复杂度分析：

  • 时间复杂度：O(n)，其中 n 指的是链表的元素个数

    • 第一步： 遍历链表并将值复制到数组中，O(n)
    • 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)
    • 总的时间复杂度：O(2n)=O(n)

  • 空间复杂度：O(n)，其中 nn 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
func isPalindrome(head *ListNode) bool {
    vals := []int{}
    for ; head != nil; head = head.Next {
        vals = append(vals, head.Val)
    }
    n := len(vals)
    for i, v := range vals[:n / 2] {
        if v != vals[n - 1 - i] {
            return false
        }
    }
    return true
}

12. 用Rand7()实现Rand10()（Go）470-中等

题目：

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数

示例：

1
2
3
4
5
6
输入: 1
输出: [2]
输入: 2
输出: [2,8]
输入: 3
输出: [3,8,10]

提示：

  • 1 <= n <= 10^5

思想：

方法一：拒绝采样

思路与算法

我们可以用拒绝采样的方法实现 Rand10()。在拒绝采样中，如果生成的随机数满足要求，那么就返回该随机数，否则会不断生成，直到生成一个满足要求的随机数为止

  • 我们只需要能够满足等概率的生成 10 个不同的数即可，具体的生成方法可以有很多种，比如我们可以利用两个 Rand7() 相乘，我们只取其中等概率的 10 个不同的数的组合即可，当然还有许多其他不同的解法，可以利用各种运算和函数的组合等方式来实现
    • 比如我们可以利用两个Rand7()相乘，分别可以得到结果如下：一大个表格
    • 我们可以得到每个数生成的概率为：一大个表格
    • 我们可以从中挑选 10个等概率的数即可
  • 题目中要求尽可能的减少 Rand7() 的调用次数，则我们应该尽量保证生成的每个不同的数的生成概率尽可能的大，即调用 Rand7() 期望次数尽可能的小
  • 我们可以调用两次 Rand7()，那么可以生成 [1,49] 之间的随机整数，我们只用到其中的前 40 个用来实现 Rand10()，而拒绝剩下的 9 个数，如下图所示
  • 我们可以看到表中的 [1,49] 每个数生成的概率为49分之1。我们实际上只取 [1,40] 这前 40 个数，转化为 [1,10] 时，这 10 个数中每个数的生成概率则为 49分之1

复杂度分析：

  • 时间复杂度：期望时间复杂度为 O(1)，但最坏情况下会达到 O*(∞)（一直被拒绝）
  • 空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
func rand10() int {
    for {
        row := rand7()
        col := rand7()
        idx := (row - 1) * 7 + col
        if idx <= 40 {
            return 1 + (idx - 1) % 10
        }
    }
}

13. 两数之和（Go）1-简单

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现

你可以按任意顺序返回答案

示例：

1
2
3
4
5
6
7
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
输入：nums = [3,2,4], target = 6
输出：[1,2]
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

思想：

方法二：哈希表

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配

复杂度分析：

时间复杂度：O(N)，其中 NN 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x

空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销

代码：

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    hashTable := map[int]int{}
    for i, x := range nums {
        if p, ok := hashTable[target - x]; ok {
            return []int{p, i}
        }
        hashTable[x] = i
    }
    return nil
}

14. 爬楼梯（Go）70-简单

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

示例：

1
2
3
4
5
6
7
8
9
10
11
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45

思路：

方法一：动态规划

思路和算法

我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
f(x)=f(x−1)+f(x−2)

它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和

以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0)=1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果

我们不妨写几项来验证一下，根据转移方程得到 f(2)=2，f(3)=3，f(4)=5，……，我们把这些情况都枚举出来，发现计算的结果是正确的

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现，但是由于这里的 f(x) 只和 f(x−1) 与 f(x−2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现

复杂度分析：

  • 时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)
  • 空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)

代码：

1
2
3
4
5
6
7
8
9
func climbStairs(n int) int {
    p, q, r := 0, 0, 1
    for i := 1; i <= n; i++ {
        p = q
        q = r
        r = p + q
    }
    return r
}

15. 最长递增子系列（Go） 300-中等

题目：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例：

1
2
3
4
5
6
7
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4
输入：nums = [0,1,0,3,2,3]
输出：4
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -10的4次方 <= nums[i] <= 10的4次方

思路：

方法一：动态规划

思路与算法

定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取

我们从小到大计算 dp 数组的值，在计算 dp[i] 之前，我们已经计算出 dp[0…i−1] 的值，则状态转移方程为：
dp[i] = max(dp[j]) + 1，其中0<=j<i并且num[j]<num[i]

即考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]。由于 dp[j] 代表 nums[0…j] 中以 nums[j] 结尾的最长上升子序列，所以如果能从 dp[j] 这个状态转移过来，那么 nums[i] 必然要大于 nums[j]，才能将 nums[i] 放在 nums[j] 后面以形成更长的上升子序列

最后，整个数组的最长上升子序列即所有 dp[i] 中的最大值

LISlength = max(dp[i])，其中0<=i<n

复杂度分析：

  • 时间复杂度：O(n的2次方)，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n的2次方)
  • 空间复杂度：O(n)，需要额外使用长度为 n 的 dp 数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main

import "fmt"

func LengthOfList(nums []int) int {
	// 定义dp[i]标识以nums[i]这个数据结尾的最长递增子系列的长度
	dp := make([]int, len(nums))
	ans := 0
	for i := 0; i < len(dp); i++ {
		dp[i] = 1
	}
	for j := 0; j < len(nums); j++ {
		for k := 0; k < j; k++ {
			if nums[j] > nums[k] {
				if dp[j] < dp[k]+1 {
					dp[j] = dp[k] + 1
				}
			}
		}
	}
	for _, v := range dp {
		if v > ans {
			ans = v
		}
	}
	return ans
}

func main() {
	nums := []int{1, 2, 3, 5, 6, 7, 12, 2, 4, 11}
	fmt.Println("结果为：", LengthOfList(nums))
}

16. 有效的括号（Go）20-简单

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合
  2. 左括号必须以正确的顺序闭合

示例：

1
2
3
4
5
6
7
8
9
10
输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
输入：s = "([)]"
输出：false
输入：s = "{[]}"
输出：true

提示：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

思路：

方法一：栈

判断括号的有效性可以使用「栈」这一数据结构来解决

我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号

在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度
  • 空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')':'(',
        ']':'[',
        '}':'{',
    }
    stack := []byte{}
    for i := 0; i < n; i++ {
        if pairs[s[i]] > 0 {
            if len(stack) == 0 || stack[len(stack) - 1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack) - 1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

17. 环形链表（Go）141-简单

题目：

给你一个链表的头节点 head ，判断链表中是否有环

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况

如果链表中存在环 ，则返回 true 。 否则，返回 false

示例：

1
2
3
4
5
6
7
8
9
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点
输入：head = [1], pos = -1
输出：false
解释：链表中没有环

提示：

  • 链表中节点的数目范围是 [0, 10^4]
  • -10^5<= Node.val <= 10^5
  • pos 为 -1 或者链表中的一个 有效索引

思路：

方法一：哈希表
思路及算法

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次
  • 空间复杂度：O(N)，其中 N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次

代码：

1
2
3
4
5
6
7
8
9
10
11
func hasCycle(head *ListNode) bool {
    seen := map[*ListNode]struct{}{}
    for head != nil {
        if _, ok := seen[head]; ok {
            return true
        }
        seen[head] = struct{}{}
        head = head.Next
    }
    return false
}

18. 寻找旋转排序数组中的最小值（Go）153-中等

题目：

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

示例：

1
2
3
4
5
6
7
8
9
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路：

方法一：二分查找

思路与算法

一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标

我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值

在二分查找的每一步中，左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较，可能会有以下的三种情况：

第一种情况是 nums[pivot]<nums[high]。如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分

第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分

由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与 high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high] 的情况

当二分查找结束时，我们就得到了最小值所在的位置

复杂度分析：

  • 时间复杂度：时间复杂度为 O(logn)，其中 nn 是数组 nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为 O(logn)
  • 空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
func findMin(nums []int) int {
    low, high := 0, len(nums) - 1
    for low < high {
        pivot := low + (high - low) / 2
        if nums[pivot] < nums[high] {
            high = pivot
        } else {
            low = pivot + 1
        }
    }
    return nums[low]
}

19. 最长回文子串（Go）5-中等

题目：

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

示例：

1
2
3
4
5
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

思路：

方法二：中心扩展算法

思路与算法

我们仔细观察一下方法一中的状态转移方程：

P(i,i) = true
P(i,i+1) = (Si==Si+1)

P(i,j) = P(i+1, j+1)^(Si==Sj)

找出其中的状态转移链：

P(i,j)←P(i+1,j−1)←P(i+2,j−2)←⋯←某一边界情况

可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案

边界情况即为子串长度为 1 或 2 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从 P(i+1,j−1) 扩展到 P(i,j)；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了

聪明的读者此时应该可以发现，「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案

复杂度分析：

  • 时间复杂度：O(n的2次方)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 O(n) 次
  • 空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestPalindrome(s string) string {
    if s == "" {
        return ""
    }
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        left1, right1 := expandAroundCenter(s, i ,i)
        left2, right2 := expandAroundCenter(s, i, i + 1)
        if right1 - left1 > end - start {
            start, end = left1, right1
        }
        if right2 - left2 > end - start {
            start ,end = left2, right2
        }
    }
    return s[start:end + 1]
}

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

20. 最长公共子序列（Go）1143-中等

题目：

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列

示例：

1
2
3
4
5
6
7
8
9
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成

思路：

方法一：动态规划
最长公共子序列问题是典型的二维动态规划问题

假设字符串 text 1和 text2的长度分别为 m 和 n，创建 m+1 行 n+1 列的二维数组 dp，其中 dp[i] [j]表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度

上述表示中，text1[0:i] 表示 text1的长度为 i 的前缀，text2[0:j] 表示 text2的长度为 j 的前缀

考虑动态规划的边界情况：

  • 当 i=0 时，text1[0:i] 为空，空字符串和任何字符串的最长公共子序列的长度都是 0，因此对任意 0≤j≤n，有 dp[0] [j]=0
  • 当 j=0 时，text2 [0:j] 为空，同理可得，对任意 0≤i≤m，有 dp[i] [0]=0

因此动态规划的边界情况是：当 i=0 或 j=0 时，dp[i] [j]=0

当 i>0 且 j>0 时，考虑 dp[i] [j] 的计算：

  • 当text1[i-1]!=text2[j-1]时，将这两个相同的字符称为公共字符，考虑text1[0:i-1]和text2[0:j-1]的最长公共子序列，再增加一个字符（即公共字符）即可得到text1[0:i]和text2[0:j]的最长公共子序列，因此dp[i] [j]=dp[i-1] [j-1]+1
  • 当text1[i-1]!=text2[j-1]时，考虑以下两项：
    • text1[0:i-1]和text2[0:j]的最长公共子序列
    • text1[0:i]和text2[0:j-1]的最长公共子系列

要得到text1[0:i]和text[o:j]的最长公共子系列，应取两项中的长度较大的一项，因此dp[i] [j]=max(dp[i-1],dp[i][j-1])

由此可得到如下状态转移方程：

dp[i] [j]=1:dp[i-1] [j-1]+1,text1[i-1]=text2[j-1] 2:max(dp[i-1] [j],dp[i] [j-1]),text[i-1]!=text[j-1]

最终计算得到db[m] [n] 即为text1和text2的最长公共子系列的长度

复杂度分析：

  • 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 text1和 text 2的长度。二维数组 dp 有m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算
  • 空间复杂度：O(mn)，其中 m 和 n 分别是字符串 text1和 text 2的长度。创建了 m+1 行 n+1 列的二维数组 dp

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m + 1)
    for i := range dp {
        dp[i] = make([]int, n + 1)
    }
    for i, c1 := range text1 {
        for j, c2 := range text2 {
            if c1 == c2 {
                dp[i + 1][j + 1] = dp[i][j] + 1
            } else {
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) 
            }
        }
    }
    return dp[m][n]
}

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

21. 三数之和（Go）15-中等

题目：

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

示例：

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

提示：

  • 0 <= nums.length <= 3000
  • -10的5次方 <= nums[i] <= 10的5次方

思路：

方法一：排序 + 双指针

复杂度分析：

  • 时间复杂度：O(N的2次方)，其中 N 是数组 nums 的长度
  • 空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func threeSum(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    ans := make([][]int, 0)
    // 枚举a
    for first := 0; first < n; first++ {
        // 需要和上一次枚举的数不同
        if first > 0 && nums[first] == nums[first -1] {
            continue
        }
        // c对应的指针初始指向数组的最右端
        third := n - 1
        target := -1 * nums[first]
        // 枚举b
        for second := first + 1; second < n; second++ {
            // 需要和上一次枚举的数不相同
            if second > first + 1 && nums[second] == nums[second - 1] {
                continue
            }
            // 需要保证b的指针在c的指针左侧
            for second < third && nums[second] + nums[third] > target {
                third --
            }
            // 如果指针重合，随着b后续的增加，就不会有满足a+b+c=0并且b<c的c了，可以退出循环
            if second == third {
                break
            }
            if nums[second] + nums[third] == target {
                ans = append(ans, []int{nums[first], nums[second], nums[third]})
            }
        }
    }
    return ans
}

22. 寻找两个正序数组的中位数（Go）4-困难

题目：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数

算法的时间复杂度应该为 O(log (m+n))

示例：

1
2
3
4
5
6
7
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
===
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

思路：

方法一：二分查找

给定两个有序数组，要求找到两个有序数组的中位数，最直观的思路有以下两种：

  • 使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数
  • 不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置

复杂度分析：

  • 时间复杂度：O(log(m+n))，其中 mm 和 nn 分别是数组nums1和 nums2的长度。初始时有 k=(m+n)/2 或 k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是 O(log(m+n))
  • 空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package main

import "fmt"

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	totalLength := len(nums1) + len(nums2)
	if totalLength%2 == 1 {
		midIndex := totalLength / 2
		return float64(getKthElement(nums1, nums2, midIndex+1))
	} else {
		midIndex1, midIndex2 := totalLength/2-1, totalLength/2
		return float64(getKthElement(nums1, nums2, midIndex1+1)+getKthElement(nums1, nums2, midIndex2+1)) / 2.0
	}
	return 0
}

func getKthElement(nums1, nums2 []int, k int) int {
	index1, index2 := 0, 0
	for {
		if index1 == len(nums1) {
			return nums2[index2+k-1]
		}
		if index2 == len(nums2) {
			return nums1[index1+k-1]
		}
		if k == 1 {
			return min(nums1[index1], nums2[index2])
		}
		half := k / 2
		newIndex1 := min(index1+half, len(nums1)) - 1
		newIndex2 := min(index2+half, len(nums2)) - 1
		pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2]
		if pivot1 <= pivot2 {
			k -= (newIndex1 - index1 + 1)
			index1 = newIndex1 + 1
		} else {
			k -= (newIndex2 - index2 + 1)
			index2 = newIndex2 + 1
		}
	}
	return 0
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	nums1 := []int{1, 2, 4, 6, 7, 9}
	nums2 := []int{3, 6, 7, 8, 9, 10}
	fmt.Println("结果为：", findMedianSortedArrays(nums1, nums2))
}

23. 二叉树的层序遍历（Go）102-中等

题目：

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

示例：

1
2
3
4
5
6
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
输入：root = [1]
输出：[[1]]
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

思路：

方法一：广度优先搜索

思路和算法

复杂度分析：

  • 时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)
  • 空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package main

import "fmt"

// TreeNode 定义二叉树
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// CreateNode 创建二叉树
func CreateNode(i int, nums []int) *TreeNode {
	tree := &TreeNode{nums[i], nil, nil}
	// 左节点的数组下标为1，,3，,5...2*i+1
	if i < len(nums) && 2*i+1 < len(nums) {
		tree.Left = CreateNode(2*i+1, nums)
	}
	// 右节点的数组下标为2,4,6...2*i+2
	if i < len(nums) && 2*i+2 < len(nums) {
		tree.Right = CreateNode(2*i+2, nums)
	}
	return tree
}

// LevelOrder 二叉树层序遍历（广度优先搜索）-中等
func LevelOrder(root *TreeNode) [][]int {
	var ret [][]int
	if root == nil {
		return ret
	}
	q := []*TreeNode{root}
	for i := 0; len(q) > 0; i++ {
		ret = append(ret, []int{})
		var p []*TreeNode
		for j := 0; j < len(q); j++ {
			node := q[j]
			ret[i] = append(ret[i], node.Val)
			if node.Left != nil {
				p = append(p, node.Left)
			}
			if node.Right != nil {
				p = append(p, node.Right)
			}
		}
		q = p
	}
	return ret
}

// PreorderTraversal 二叉树前序遍历（递归）-简单-根节点——左子树——右子树
func PreorderTraversal(root *TreeNode) (vals []int) {
	var preorder func(*TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		vals = append(vals, node.Val)
		preorder(node.Left)
		preorder(node.Right)
	}
	preorder(root)
	return
}

// InorderTraversal 二叉树中序遍历（递归）-简单-左子树——根节点——右子树
func InorderTraversal(root *TreeNode) (res []int) {
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Left)
		res = append(res, node.Val)
		inorder(node.Right)
	}
	inorder(root)
	return
}

// PostorderTraversal 二叉树后续遍历（递归）-简单-左子树——右子树——根节点
func PostorderTraversal(root *TreeNode) (res []int) {
	var postorder func(*TreeNode)
	postorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		postorder(node.Left)
		postorder(node.Right)
		res = append(res, node.Val)
	}
	postorder(root)
	return
}

func main() {
	// 0代表节点为空
	nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	// 将数组切片转化为二叉树结构体
	tree := CreateNode(0, nums)
	levelOrder := LevelOrder(tree)
	fmt.Println("二叉树层序遍历：", levelOrder)
	preorderTraversal := PreorderTraversal(tree)
	fmt.Println("二叉树前序遍历：", preorderTraversal)
	inorderTraversal := InorderTraversal(tree)
	fmt.Println("二叉树中序遍历：", inorderTraversal)
	postorderTraversal := PostorderTraversal(tree)
	fmt.Println("二叉树后序遍历：", postorderTraversal)
}

24. 补充题6：手撕堆排序（Go） 912-中等

题目：

给你一个整数数组 nums，请你将该数组升序排列

示例：

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

提示：

思路：

算法描述：首先建一个堆，然后调整堆，调整过程是将节点和子节点进行比较，将 其中最大的值变为父节点，递归调整调整次数lgn,最后将根节点和尾节点交换再n次 调整O(nlgn)

步骤：

  • 创建最大堆或者最小堆（我是最小堆）
  • 调整堆
  • 交换首尾节点(为了维持一个完全二叉树才要进行收尾交换)

复杂度分析：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package main

import "fmt"

func HeapSortMax(nums []int, length int) []int {
	if length <= 1 {
		return nums
	}
	// 二叉树深度
	depth := length/2 - 1
	for i := depth; i >= 0; i-- {
		// 假定最大的位置就在i的位置
		topmax := i
		leftchild := 2*i + 1
		rightchild := 2*i + 2
		// nums[leftchild] > nums[topmax] 防止越界
		if leftchild <= length-1 && nums[leftchild] > nums[topmax] {
			topmax = leftchild
		}
		// nums[rightchild] > nums[topmax] 防止越界
		if rightchild <= length-1 && nums[rightchild] > nums[topmax] {
			topmax = rightchild
		}
		if topmax != i {
			nums[i], nums[topmax] = nums[topmax], nums[i]
		}
	}
	return nums
}

func HeapSort(nums []int) []int {
	lenght := len(nums)
	for i := 0; i < lenght; i++ {
		lastLen := lenght - i
		HeapSortMax(nums, lastLen)
		if i < lenght {
			nums[0], nums[lastLen-1] = nums[lastLen-1], nums[0]
		}
	}
	return nums
}

func main() {
	nums := []int{1, 3, 7, 8, 9, 2, 4, 5, 10, 6}
	fmt.Println("结果为：", HeapSort(nums))
}

25. 相交链表（Go）160-简单

题目：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环

注意，函数返回结果后，链表必须 保持其原始结构

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
输入：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

提示：

思路：

方法一：哈希集合
思路和算法

判断两个链表是否相交，可以使用哈希集合存储链表节点

首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：

  • 如果当前节点不在哈希集合中，则继续遍历下一个节点
  • 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点

如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null

复杂度分析：

  • 时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次
  • 空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点

代码：

1
2
3
4
5
6
7
8
9
10
11
12
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    vis := map[*ListNode]bool{}
    for tmp := headA; tmp != nil; tmp = tmp.Next {
        vis[tmp] = true
    }
    for tmp := headB; tmp != nil; tmp = tmp.Next {
        if vis[tmp] {
            return tmp
        }
    }
    return nil
}

26. 二叉搜索树的第K大节点（Go） 剑指offer54-简单

题目：

给定一棵二叉搜索树，请找出其中第 k 大的节点的值

示例：

提示：

思路：

  1. 通过二叉树的中序遍历便是一个从小到大的排序
  2. 设置一个count，每遍历一个数据便自增1，当count=k时，就找到了正确答案

复杂度分析：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package main

import "fmt"

// 思路：返回中序遍历生成的序列中的第k个节点
// 此题最好只实现：InorderTraverse和KthLargest
// 在Goland IDE里实现全部貌似结果不正确

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

// CreateNode 创建二叉树
func CreateNode(i int, nums []int) *TreeNode {
	tree := &TreeNode{nums[i], nil, nil}
	// 左节点的数组下标为1,3,5...2*i+1
	if i < len(nums) && 2*i+1 < len(nums) {
		tree.Left = CreateNode(2*i+1, nums)
	}
	// 右节点的数组下标为2,4,6...2*i+2
	if i < len(nums) && 2*i+2 < len(nums) {
		tree.Right = CreateNode(2*i+2, nums)
	}
	return tree
}

func InorderTraverse(root *TreeNode, ret *[]int) {
	if root == nil {
		return
	}
	InorderTraverse(root.Left, ret)
	*ret = append(*ret, root.Val)
	InorderTraverse(root.Right, ret)
}

func KthLargest(root *TreeNode, k int) int {
	ret := &[]int{}
	InorderTraverse(root, ret)
	// 说明没找到第k大节点
	if k < 1 && k > len(*ret) {
		return -1
	}
	return (*ret)[len(*ret)-k]
}

func main() {
	nums := []int{1, 2, 3, 4, 5}
	// 0代表节点为空
	treeNode := CreateNode(0, nums)
	fmt.Println("结果为：", KthLargest(treeNode, 1))
}

27. LFU缓存（Go） 460-困难

题目：

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构

示例：

提示：

思路：

方法二：双哈希表

复杂度分析：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package main

import "fmt"

type Node struct {
	Key   int
	Value int
	freq  int
	pre   *Node
	next  *Node
}

type LFUCache struct {
	limit   int
	HashMap map[int]*Node
	head    *Node
	end     *Node
}

func LFUConstructor(capacity int) LFUCache {
	lfuCache := LFUCache{}
	lfuCache.limit = capacity
	lfuCache.HashMap = make(map[int]*Node, capacity)
	return lfuCache
}

func (lfuCache *LFUCache) Get(key int) int {
	if value, ok := lfuCache.HashMap[key]; ok {
		value.freq++
		lfuCache.refreshNode(value)
		return value.Value
	} else {
		return -1
	}
}

func (lfuCache *LFUCache) Put(key, value int) {
	if v, ok := lfuCache.HashMap[key]; !ok {
		if len(lfuCache.HashMap) >= lfuCache.limit {
			oldKey := lfuCache.removeNode(lfuCache.head)
			delete(lfuCache.HashMap, oldKey)
		}
		node := Node{Key: key, Value: value, freq: 1}
		lfuCache.addNode(&node)
		lfuCache.HashMap[key] = &node
	} else {
		v.Value = value
		v.freq++
		lfuCache.refreshNode(v)
	}
}

func (lfuCache *LFUCache) refreshNode(node *Node) {
	if node == lfuCache.end {
		return
	}
	lfuCache.removeNode(node)
	lfuCache.addNode(node)
}

func (lfuCache *LFUCache) removeNode(node *Node) int {
	if node == lfuCache.end {
		lfuCache.end = lfuCache.end.pre
		lfuCache.end.next = nil
	} else if node == lfuCache.head {
		lfuCache.head = lfuCache.head.next
		lfuCache.head.pre = nil
	} else {
		node.pre.next = node.next
		node.next.pre = node.pre
	}
	return node.Key
}

func (lfuCache *LFUCache) addNode(node *Node) {

	if lfuCache.head == nil && lfuCache.end == nil {
		lfuCache.head = node
		lfuCache.end = node
		return
	}
	head := lfuCache.head
	for head != nil && node.freq >= head.freq {
		head = head.next
	}
	if head == nil {
		lfuCache.end.next = node
		node.pre = lfuCache.end
		lfuCache.end = node
	}
	if head != nil {
		head.pre.next = node
		node.pre = head.pre
		head.pre = node
		node.next = head
	}

	lfuCache.head.pre = nil
	lfuCache.end.next = nil
	return
}

func main() {
	lfuCache := LFUConstructor(3)
	lfuCache.Put(1, 3)
	lfuCache.Put(2, 4)
	lfuCache.Put(3, 5)
	fmt.Println(lfuCache) // 此时的链表顺序应该是 1 : 3   2 : 4   3 : 5   lfuCache.head 为1 : 3   lfuCache.end 为3 : 5
	lfuCache.Get(1)
	fmt.Println(lfuCache) // 此时的链表顺序应该是  2 : 4   3 : 5  1 : 3   lfuCache.head 为2 : 4    lfuCache.end 为1 : 3
	lfuCache.Put(4, 6)
	fmt.Println(lfuCache) // 此时的链表顺序应该是  3 : 5  4 : 6   1 : 3    lfuCache.head 为3 : 5   lfuCache.end 为1 : 3
}

28. K个一组翻转链表（Go）25-困难

题目：

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换

示例：

提示：

思路：

复杂度分析：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package main

type ListNode struct {
	Value int
	Next  *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	dummyNode := &ListNode{Next: head}
	pre := dummyNode
	for head != nil {
		tail := pre
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil {
				return dummyNode.Next
			}
		}
		//记录tail后一个节点，以及pre后一个节点
		nextGroupHead := tail.Next
		head = pre.Next
		//反转
		ReverseList(head, tail)
		//拼接
		pre.Next = tail
		head.Next = nextGroupHead
		//更新pre和head
		pre = head
		head = nextGroupHead
	}
	return dummyNode.Next
}

// ReverseList 翻转链表
func ReverseList(head *ListNode, tail *ListNode) {
	var pre *ListNode
	cur := head
	for pre != tail {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
}

29. 买卖股票的最佳时机（Go）121-简单

题目：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

示例：

1
2
3
4
5
6
7
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0

提示：

  • 1 <= prices.length <= 10的5次方
  • 0 <= prices[i] <= 10的4次方

思路：

方法二：一次遍历（贪心算法）

算法

假设给定的数组为：[7, 1, 5, 3, 6, 4]

如果我们在图表上绘制给定数组中的数字，我们将会得到：

我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢

显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案

复杂度分析：

  • 时间复杂度：O(n)，只需要遍历一次
  • 空间复杂度：O(1)，只使用了常数个变量

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import "fmt"

func MaxProfit(prices []int) int {
	// 贪心
	res := 0
	m := prices[0]
	for i := 1; i < len(prices); i++ {
		if prices[i] > m {
			if (prices[i] - m) > res {
				res = prices[i] - m
			}
		} else {
			m = prices[i]
		}
	}
	return res
}

func main() {
	nums := []int{7, 1, 5, 3, 6, 4}
	fmt.Println("结果为：", MaxProfit(nums))
}

30. 基本计算器2（Go）227-中等

题目：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值

整数除法仅保留整数部分

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval()

示例：

1
2
3
4
5
6
输入：s = "3+2*2"
输出：7
输入：s = " 3/2 "
输出：1
输入：s = " 3+5 / 2 "
输出：5

提示：

  • 1 <= s.length <= 3 * 10^5
  • s 由整数和算符 (‘+’, ‘-‘, ‘*’, ‘/‘) 组成，中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

思路：

方法一：栈
思路

由于乘除优先于加减计算，因此不妨考虑先进行所有乘除运算，并将这些乘除运算后的整数值放回原表达式的相应位置，则随后整个表达式的值，就等于一系列整数加减后的值

基于此，我们可以用一个栈，保存这些（进行乘除运算后的）整数的值。对于加减号后的数字，将其直接压入栈中；对于乘除号后的数字，可以直接与栈顶元素计算，并替换栈顶元素为计算后的结果

具体来说，遍历字符串 s，并用变量 preSign 记录每个数字之前的运算符，对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 preSign 来决定计算方式：

  • 加号：将数字压入栈
  • 减号：将数字的相反数压入栈
  • 乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果

代码实现中，若读到一个运算符，或者遍历到字符串末尾，即认为是遍历到了数字末尾。处理完该数字后，更新 preSign 为当前遍历的字符

遍历完字符串 s 后，将栈中元素累加，即为该字符串表达式的值

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值

空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈的元素个数不超过 n

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func calculate(s string) (ans int) {
    stack := []int{}
    preSign := '+'
    num := 0
    for i, ch := range s {
        isDigit := '0' < ch && ch <= '9'
        if isDigit {
            num = num * 10 + int(ch - '0')
        }
        if !isDigit && ch != ' ' || i == len(s) - 1 {
            switch preSign {
            case '+':
                stack = append(stack, num)
            case '-':
                stack = append(stack, -num)
            case '*':
                stack[len(stack) - 1] *= num
            default:
                stack[len(stack) - 1] /= num
            }
            preSign = ch
            num = 0
        }
    }
    for _, v := range stack {
        ans += v
    }
    return
}

31. 数组中重复的数据（Go）442-中等

题目：

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题

示例：

1
2
3
4
5
6
输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]
输入：nums = [1,1,2]
输出：[1]
输入：nums = [1]
输出：[]

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • nums 中的每个元素出现 一次 或 两次

思路：

方法一：将元素交换到对应的位置
思路与算法

由于给定的 n 个数都在 [1,n] 的范围内，如果有数字出现了两次，就意味着 [1,n] 中有数字没有出现过

因此，我们可以尝试将每一个数放在对应的位置。由于数组的下标范围是 [0,n−1]，我们需要将数 i 放在数组中下标为 i−1 的位置：

  • 如果 i 恰好出现了一次，那么将 i 放在数组中下标为 i−1 的位置即可
  • 如果 i 出现了两次，那么我们希望其中的一个 i 放在数组下标中为 i−1 的位置，另一个 i 放置在任意「不冲突」的位置 j。也就是说，数 j+1 没有在数组中出现过

这样一来，如果我们按照上述的规则放置每一个数，那么我们只需要对数组进行一次遍历。当遍历到位置 i 时，如果 nums[i]−1!=i，说明 nums[i] 出现了两次（另一次出现在位置 num[i]−1），我们就可以将 num[i] 放入答案

放置的方法也很直观：我们对数组进行一次遍历。当遍历到位置 i 时，我们知道 nums[i] 应该被放在位置 nums[i]−1。因此我们交换 num[i] 和 nums[nums[i]−1] 即可，直到待交换的两个元素相等为止

复杂度分析：

  • 时间复杂度：O(n)。每一次交换操作会使得至少一个元素被交换到对应的正确位置，因此交换的次数为 O(n)，总时间复杂度为 O(n)

  • 空间复杂度：O(1)。返回值不计入空间复杂度

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
func findDuplicates(nums []int) (ans []int) {
    for i := range nums {
        for nums[i] != nums[nums[i] - 1] {
            nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
        }
    }
    for i, num := range nums {
        if num - 1 != i {
            ans = append(ans, num)
        }
    }
    return
}

32. 零钱兑换（Go） 332-中等

题目：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的

示例：

提示：

思路：

动态规划

复杂度分析：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package main

import "fmt"

func CoinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	// 初始化线性备忘录
	for k := range dp {
		// 相当于无限大，方便比较
		dp[k] = amount + 1
	}
	// 这个就是占位的
	dp[0] = 0
	for i := 0; i < len(dp); i++ {
		for _, coin := range coins {
			// 至少包含 1 枚某种硬币
			if i-coin < 0 {
				continue // 这种情况别闹
			}
			// 选择一个较小的
			dp[i] = min(dp[i], 1+dp[i-coin])
		}
	}
	if dp[amount] == amount+1 {
		// 没有合适的
		return -1
	}
	return dp[amount]
}

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

func main() {
	nums := []int{1, 2, 5}
	fmt.Println("结果为：", CoinChange(nums, 11))
}

33. 两数相加（Go）2-中等

题目：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字

请你将两个数相加，并以相同形式返回一个表示和的链表

你可以假设除了数字 0 之外，这两个数都不会以 0 开头

示例：

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

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

思路：

方法一：模拟
思路与算法

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry)mod10，而新的进位值为 ⌊
n1+n2+carry除以10⌋

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0

此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry

复杂度分析：

  • 时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间
  • 空间复杂度：O(1)。注意返回值不计入空间复杂度

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func addTwoNumbers(l1 *ListNode, l2 *ListNode) (head *ListNode) {
    var tail *ListNode
    carry := 0
    for l1 != nil || l2 != nil {
        n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 +carry
        sum, carry = sum % 10, sum / 10
        if head == nil {
            head = &ListNode{Val: sum}
            tail = head
        } else {
            tail.Next = &ListNode{Val: sum}
            tail = tail.Next
        }
    }
    if carry > 0 {
        tail.Next = &ListNode{Val: carry}
    }
    return
}

34. 链表中倒数第K个节点（Go）剑指offer22-简单

题目：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点

示例：

1
2
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

提示：

思路：

方法一：顺序查找
思路与算法

最简单直接的方法即为顺序查找，假设当前链表的长度为 n，则我们知道链表的倒数第 k 个节点即为正数第 n−k 个节点，此时我们只需要顺序遍历到链表的第 n−k 个节点即为倒数第 k 个节点

我们首先求出链表的长度 n，然后顺序遍历到链表的第 n−k 个节点返回即可

复杂度分析：

  • 时间复杂度：O(n)，其中 n 为链表的长度。需要两次遍历
  • 空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
func getKthFromEnd(head *ListNode, k int) (kth *ListNode) {
    n := 0
    for node := head; node != nil; node = node.Next {
        n++
    }
    for kth = head; n > k; n-- {
        kth = kth.Next
    }
    return
}

35. 路径总和（Go）112-简单

题目：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false

叶子节点 是指没有子节点的节点

示例：

1
2
3
4
5
6
7
8
9
10
11
12
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径

提示：

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

思路：

方法一：广度优先搜索
思路及算法

首先我们可以想到使用广度优先搜索的方式，记录从根节点到当前节点的路径和，以防止重复计算

这样我们使用两个队列，分别存储将要遍历的节点，以及根节点到这些节点的路径和即可

复杂度分析：

时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次

空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    queNode := []*TreeNode{}
    queVal := []int{}
    queNode = append(queNode, root)
    queVal = append(queVal, root.Val)
    for len(queNode) != 0 {
        now := queNode[0]
        queNode = queNode[1:]
        temp := queVal[0]
        queVal = queVal[1:]
        if now.Left == nil && now.Right == nil {
            if temp == targetSum {
                return true
            }
            continue
        }
        if now.Left != nil {
            queNode = append(queNode, now.Left)
            queVal = append(queVal, now.Left.Val + temp)
        }
        if now.Right != nil {
            queNode = append(queNode, now.Right)
            queVal = append(queVal, now.Right.Val + temp)
        }
    }
    return false
}

36. 字符串相乘（Go）43-中等

题目：

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数

示例：

1
2
3
4
输入: num1 = "2", num2 = "3"
输出: "6"
输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成
  • num1 和 num2 都不包含任何前导零，除了数字0本身

思路：

方法一：做加法
如果 num1和 num2之一是 0，则直接将 0 作为结果返回即可

如果 num1和 num2都不是 0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 num1，乘数是 num2

需要注意的是，num2除了最低位以外，其余的每一位的运算结果都需要补 0

复杂度分析：

  • 时间复杂度：O(mn+n^2)，其中 m 和 n 分别是 num1和 num2的长度。需要从右往左遍历 num2，对于 num2 的每一位，都需要和 num1的每一位计算乘积，因此计算乘积的总次数是 mn。字符串相加操作共有 n 次，相加的字符串长度最长为 m+n，因此字符串相加的时间复杂度是 O(mn+n^2)。总时间复杂度是 O(mn+n^2)
  • 空间复杂度：O(m+n)，其中 m 和 n 分别是 num1和 num2的长度。空间复杂度取决于存储中间状态的字符串，由于乘积的最大长度为 m+n，因此存储中间状态的字符串的长度不会超过 m+n

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }
    ans := "0"
    m, n := len(num1), len(num2)
    for i := n - 1; i >= 0; i-- {
        curr := ""
        add := 0
        for j := n - 1; j > i; j-- {
            curr += "0"
        }
        y := int(num2[i] - '0')
        for j := m - 1; j >= 0; j-- {
            x := int(num1[j] - '0')
            product := x * y + add
            curr = strconv.Itoa(product % 10) + curr
            add = product / 10
        }
        for ; add != 0; add /= 10 {
            curr = strconv.Itoa(add % 10) + curr
        }
        ans = addStrings(ans, curr)
    }
    return ans
}

func addStrings(num1, num2 string) string {
    i, j := len(num1) - 1, len(num2) - 1
    add := 0
    ans := ""
    for ; i >= 0 || j >= 0 || add != 0; i, j = i - 1, j - 1 {
        x, y := 0, 0
        if x >= 0 {
            x = int(num1[i] - '0')
        }
        if j >= 0 {
            y = int(num2[j] - '0')
        }
        result := x + y + add
        ans = strconv.Itoa(result % 10) + ans
        add = result / 10
    }
    return ans
}

37. 用栈实现队列（Go） 232-简单

题目：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek 和 empty
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

思路：

队列是一种 先进先出（first in - first out， FIFO）的数据结构，队列中的元素都从后端（rear）入队（push），从前端（front）出队（pop）
实现队列最直观的方法是用链表，但在这篇文章里我会介绍另一个方法 - 使用栈

栈是一种 后进先出（last in - first out， LIFO）的数据结构，栈中元素从栈顶（top）压入（push)，也从栈顶弹出（pop）

为了满足队列的 FIFO 的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序

方法一（使用两个栈 入队 - O(n)， 出队 - O(1)）

算法

一. 入队（push）

一个队列是 FIFO 的，但一个栈是 LIFO 的。这就意味着最新压入的元素必须得放在栈底。为了实现这个目的，我们首先需要把 s1 中所有的元素移到 s2 中，接着把新元素压入 s2。最后把 s2 中所有的元素弹出，再把弹出的元素压入 s1

二. 出队（pop）

直接从 s1 弹出就可以了，因为 s1 的栈顶元素就是队列的队首元素。同时我们把弹出之后 s1 的栈顶元素赋值给代表队首元素的 front 变量

三. 判断空（empty）

s1 存储了队列所有的元素，所以只需要检查 s1 的是否为空就可以了

四. 取队首元素（peek）

在我们的算法中，用了 front 变量来存储队首元素，在每次 入队 操作或者 出队 操作之后这个变量都会随之更新

复杂度分析：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
type MyQueue struct {
    stack []int
    back []int
}

func Constructor() MyQueue {
    return MyQueue{
        stack: make([]int, 0),
        back: make([]int, 0),
    }
}

func (this *MyQueue) Push(x int)  {
    for len(this.back) != 0 {
        val := this.back[len(this.back) - 1]
        this.back = this.back[:len(this.back) - 1]
        this.stack = append(this.stack, val)
    }
    this.stack = append(this.stack, x)
}

func (this *MyQueue) Pop() int {
    for len(this.stack) != 0 {
        val := this.stack[len(this.stack) - 1]
        this.stack = this.stack[:len(this.stack) - 1]
        this.back = append(this.back, val)
    }
    if len(this.back) == 0 {
        return 0
    }
    val := this.back[len(this.back) - 1]
    this.back = this.back[:len(this.back) - 1]
    return val
}

func (this *MyQueue) Peek() int {
    for len(this.stack) != 0 {
        val := this.stack[len(this.stack) - 1]
        this.stack = this.stack[:len(this.stack) - 1]
        this.back = append(this.back, val)
    }
    if len(this.back) == 0 {
        return 0
    }
    val := this.back[len(this.back) - 1]
    return val
}

func (this *MyQueue) Empty() bool {
    return len(this.stack) == 0 && len(this.back) == 0
}

38. 用队列实现栈（Go）225-简单

题目：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）

示例：

提示：

思路：

复杂度分析：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
type MyStack struct {
	queue1, queue2 []int
}

// Constructor 在这里初始化你的数据结构
func Constructor() (s MyStack) {
	return
}

func (s *MyStack) Push(x int) {
	s.queue2 = append(s.queue2, x)
	for len(s.queue1) > 0 {
		s.queue2 = append(s.queue2, s.queue1[0])
		s.queue1 = s.queue1[1:]
	}
	s.queue1, s.queue2 = s.queue2, s.queue1
}

func (s *MyStack) Pop() int {
	v := s.queue1[0]
	s.queue1 = s.queue1[1:]
	return v
}

func (s *MyStack) Top() int {
	return s.queue1[0]
}

func (s *MyStack) Empty() bool {
	return len(s.queue1) == 0
}

39. 翻转字符串里的单词 151-中等

题目：

示例：

提示：

思路：

复杂度分析：

代码：

40. 平衡二叉树（Go）110-简单

题目：

给定一个二叉树，判断它是否是高度平衡的二叉树

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

示例：

1
2
3
4
5
6
输入：root = [3,9,20,null,null,15,7]
输出：true
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
输入：root = []
输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • -10^4 <= Node.val <= 10^4

思路：

前言
这道题中的平衡二叉树的定义是：二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上

方法一：自顶向下的递归
定义函数 height，用于计算二叉树中的任意一个节点 p 的高度：

有了计算节点高度的函数，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程

复杂度分析：

  • 时间复杂度：O(n^2)，其中 n 是二叉树中的节点个数

    最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)

    对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 h 满足 O(h)=O(logn)，因为 d≤h，所以总时间复杂度为 O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)

  • 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return abs(height(root.Left) - height(root.Right)) <= 1 &&
    isBalanced(root.Left) && isBalanced(root.Right)
}

func height(root * TreeNode) int {
    if root == nil {
        return 0
    }
    return max(height(root.Left), height(root.Right)) + 1
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func abs(x int) int {
    if x < 0 {
        return -1 * x
    }
    return x
}

41. 螺旋矩阵（Go）54-中等

题目：

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素

示例：

1
2
3
4
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i] [j] <= 100

思路：

方法一：模拟
可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向

判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将 visited 中的对应位置的元素设为已访问

如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回

复杂度分析：

  • 时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次
  • 空间复杂度：O(mn)。需要创建一个大小为 m×n 的矩阵 visited 记录每个位置是否被访问过

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package main

import "fmt"

func SpiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return []int{}
	}
	rows, columns := len(matrix), len(matrix[0])
	visited := make([][]bool, rows)
	for i := 0; i < rows; i++ {
		visited[i] = make([]bool, columns)
	}

	var (
		total          = rows * columns
		order          = make([]int, total)
		row, column    = 0, 0
		directions     = [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
		directionIndex = 0
	)

	for i := 0; i < total; i++ {
		order[i] = matrix[row][column]
		visited[row][column] = true
		nextRow, nextColumn := row+directions[directionIndex][0],
			column+directions[directionIndex][1]
		if nextRow < 0 || nextRow >= rows || nextColumn < 0 ||
			nextColumn >= columns || visited[nextRow][nextColumn] {
			directionIndex = (directionIndex + 1) % 4
		}
		row += directions[directionIndex][0]
		column += directions[directionIndex][1]
	}
	return order
}

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

下面的题为面试经历过的题目

1. Golang合并2个切片并去重排序

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

import (
	"fmt"
	"sort"
)

func Solution(nums1, nums2 []int) []int {
	nums1 = append(nums1, nums2...)
	hashMap := make(map[int]struct{})
	var result []int
	for _, num := range nums1 {
		// 先计算Map长度，然后再往Map里添加数据
		hashMapLen := len(hashMap)
		hashMap[num] = struct{}{}
		// 如何Map的长度有变化，说明num没有重复，可以将其添加到切片里
		if len(hashMap) != hashMapLen {
			result = append(result, num)
		}
	}
	// 内置方法排序
	sort.Ints(result)
	return result
}

func main() {
	nums1 := []int{1, 3, 5, 7, 9, 8, 2}
	nums2 := []int{2, 3, 4, 5, 6, 10, 1}
	fmt.Println("结果为：", Solution(nums1, nums2))
}

2. 约瑟夫环问题

题目：有n个人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，循环报数，问最后剩下的人是开始围圈时的第几号

思路：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main

import "fmt"

func JosephRing(nums [13]int, n, m int) {
	var front, rear, round = 0, n, 0
	for {
		// 队不为空
		if rear-front == 0 {
			break
		}
		for i := 0; i < m-1; i++ {
			front = (front + 1) % n
			rear = (rear + 1) % n
			nums[rear] = nums[front]
		}
		front = (front + 1) % n
		round++
		fmt.Printf("第%d轮：%d\n", round, nums[front])
	}
}

func main() {
	var nums [13]int
	var n, m = 12, 3
	nums[0] = n
	// 初始化队列，入队
	for i := 1; i < n+1; i++ {
		nums[i] = i
	}
	JosephRing(nums, n, m)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package main

import "fmt"

func Josephus(n int, k int) int {
	if n == 1 {
		return n
	}
	return (Josephus(n-1, k)+k-1)%n + 1
}

func main() {
	n := 12
	k := 3
	res := Josephus(n, k)
	fmt.Println("结果为：", res)
}

3. 一个单链表，如何求倒数第n-1个节点的值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
package main

import (
	"fmt"
)

type ListNode struct {
	Value int
	Next  *ListNode
}

// ListNodeLen 求单链表长度
// 参数：
// 	head：单链表
// 返回值：
// 	lenght：单链表长度
func ListNodeLen(head *ListNode) (lenght int) {
	for ; head != nil; head = head.Next {
		lenght++
	}
	return lenght
}

// ToSlice 将链表转化切片，然后直接下标取值
// 参数：
// 	head：单链表；n：第n个元素
// 返回值：
// 	result：单链表第倒数n-1个元素的值
func ToSlice(head *ListNode, n int) (result int) {
	var values []int
	for ; head != nil; head = head.Next {
		values = append(values, head.Value)
	}
	// 切片长度=链表长度
	valuesLen := len(values)
	// 判断是否会越界，左右都需要判断
	if n-1 >= 1 && n <= valuesLen+1 {
		return values[valuesLen-n+1]
	} else {
		return
	}
}

// FastSlow 快慢指针
// 参数：
// 	head：单链表；n：第n个元素
// 返回值：
// 	result：单链表第倒数n-1个元素的值
func FastSlow(head *ListNode, n int) (result int) {
	dummy := &ListNode{0, head}
	first, second := head, dummy
	// 需要判断是否会越界
	listNodeLen := ListNodeLen(head)
	if n-1 >= 1 && n <= listNodeLen+1 {
		for i := 0; i < n-1; i++ {
			first = first.Next
		}
		for ; first != nil; first = first.Next {
			second = second.Next
		}
		return second.Next.Value
	} else {
		return
	}
}

// DoublePointer 双指针，优化后，不需要判断临界值
// 参数：
// 	head：单链表；n：第n个元素
// 返回值：
// 	result：单链表第倒数n-1个元素的值
func DoublePointer(head *ListNode, n int) (result int) {
	var second, first *ListNode
	first = head
	second = head
	for i := 1; first.Next != nil; i++ {
		//间隔n-1才赋值
		if i >= n-1 {
			second = second.Next
		}
		//头部往后移动
		first = first.Next
	}
	return second.Value
}

// ReverseList 反转链表，链表反转后，未反转的链表的倒数第n-1个节点的值就是反转后链表的第n-1个的值
// 参数：
// 	head：单链表；n：第n个元素
// 返回值：
// 	result：单链表第倒数n-1个元素的值
func ReverseList(head *ListNode, n int) (result int) {
	var prev *ListNode
	curr := head
	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	// 遍历反转后的链表，然后取出第n-1个的值
	i := 1
	for prev != nil {
		if i == n-1 {
			result = prev.Value
			break
		}
		i++
		prev = prev.Next
	}
	return result
}

// CreateListNode 使用slice生成单链表
func CreateListNode(nums []int) *ListNode {
	var head ListNode
	var pre ListNode
	for _, num := range nums {
		node := ListNode{Value: num, Next: nil}
		if head.Next == nil {
			head.Next = &node
		}
		if pre.Next == nil {
			pre.Next = &node
		} else {
			pre.Next.Next = &node
			pre = *pre.Next
		}
	}
	return head.Next
}

func main() {
	nums := []int{1, 3, 6, 2, 7, 9, 10, 5, 8}
	n := 5
	head := CreateListNode(nums)
	// n值如果不在临界值内，返回0
	toSlice := ToSlice(head, n)
	fmt.Printf("链表转切片，链表倒数第%d-1个：%d\n", n, toSlice)

	// n值如果不在临界值内，返回0
	fastSlow := FastSlow(head, n)
	fmt.Printf("快慢指针，链表倒数第%d-1个：%d\n", n, fastSlow)

	// n值如果小于临界值指向链表最后一个元素，大于临界值指向链表第一个元素（倒数第n-1个元素）
	doublePointer := DoublePointer(head, n)
	fmt.Printf("双指针优化后，链表倒数第%d-1个：%d\n", n, doublePointer)

	// n值如果不在临界值内，返回0
	reverseList := ReverseList(head, n)
	fmt.Printf("反转链表，链表倒数第%d-1个：%d\n", n, reverseList)

	// ToDo
	// 将单链表转为双链表，只需要找到第n个节点，然后取出双链表的第n个节点的上一个节点的值
}

4. abc组成的字符串删除

题目： 一个字符串，只有abc三个字符组成，现在需要删除字符串，删除规则为：每次只能删除2个字符，删除a和b或者删除a和c，字符串能否被全部删除，如果能，需要多少次

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main

import "fmt"

func Solution(str string) int {
	// 判断字符串长度是否为奇数，奇数则无法完全删除
	if len(str) == 0 || len(str)%2 != 0 {
		return -1
	}
	a, b, c := 0, 0, 0
	for _, s := range str {
		switch string(s) {
		case "a":
			a += 1
		case "b":
			b += 1
		case "c":
			c += 1
		}
	}
	// a的数量等于b+c的数量
	if a == b+c {
		return a
	} else {
		return -1
	}
}

func main() {
	str := "aabbccaaaaabbcbb"
	fmt.Println("结果为：", Solution(str))
}

5. 计算非负数的平方根

给你一个非负小数x，计算并返回x的算术平方根。保留2位小数

注意：不允许使用任何内置指数函数和算符，例如Pow(x,0.5)或者 ×**0.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import "fmt"

func sqrt(x float64) float64 {
	if x == 0 {
		return 0
	}
	// 初始的猜测值为x的一半
	z := x / 2
	// 迭代求解
	for i := 0; i < 1000; i++ {
		z = z - (z*z-x)/(2*z)
	}
	return z
}

func main() {
	x := 8.0
	result := sqrt(x)
	fmt.Printf("%.2f\n", result)
}

Go编程题30题

链接：点击跳转

本文链接：
https://huajun-chen.github.io/2022/10/28/数据结构与算法面试题/