算法题的几种模式
滑动窗口
滑动窗口用于在给定数组或者链表的特定窗口大小上执行所需的操作，比如查找最长的子字符串或者子数组。
题目 1004. 最大连续1的个数 III
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//该题可以转换为对于数组A的找到最大的区间[left, right]，使得其中包含不超过k个0
func longestOnes(nums []int, k int) int {
n := len(nums)
res, zeros := 0, 0
for left, right := 0, 0; right < n; right++ {
if nums[right] == 0 {
zeros++
}
for zeros > k {
if A[left] == 0 {
zeros--
}
left++
}
res = max(res, right-left+1)
}
return res
}
|
回溯法
backtracking回溯法，也可以理解为深度优先搜索（DFS）
回溯的本质是穷举，需要通过递归来遍历所有的解，再去进行删选。
一般涉及回溯的有三类问题：
回溯法在穷举过程中可以随时判断当前状态是否符合问题的条件
leetcode 17 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
1
2
|
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
|
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
|
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
combinations = []string{}
backtrack(digits, 0, "")
return combinations
}
func backtrack(digits string, index int, tmpStr string) {
if index == len(digits) { //判断合法的解，已经遍历到最后一个字母了
combinations = append(combinations, tmpStr)
} else {
digit := string(digits[index])
letters := phoneMap[digit]
lettersCount := len(letters)
for i:=0;i<lettersCount; i++ {
backtrack(digits, index+1, tmpStr+string[letters[i]])
}
}
}
var phoneMap map[string]string = map[string]string{
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
|
Leetcode 22 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
1
2
|
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
//只能选左括号或者右括号
//用DFS回溯遍历这棵树
//约束条件：1. 只能先选择左括号 2. 右括号剩的比较多才能选右括号
func generateParenthesis(n int) []string {
res := []string{}
var dfs func(lRemain int, rRemain int, path string)
dfs = func(lRemain int, rRemain int, path string) {
if n*2 == len(path) {
res = append(res, path)
return
}
if lRemain > 0 {
dfs(lRemain-1, rRemain, path+"(")
}
if lRemain < rRemain {
dfs(lRemain, rRemain-1, path+")")
}
}
dfs(n, n, "")
return res
}
|
二叉搜索树
二叉树
动态规划
动态规划是运筹学上的一种最优化方法。核心问题可以理解为穷举，但是需要选择最优路径。
这个最优路径就是状态转移方程，即高中学过的数学归纳法。
下面介绍几个常见的问题
-
斐波那契数列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func fib(n int) int {
var dp = make(map[int]int)
if n == 1 || n == 2 {
return 1
}
// 初始值
dp[1] = 1
dp[2] = 1
for i := 3; i <= n; i++ {
// 状态转移方程
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
/*
给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1
*/
// input:
// coins - 硬币种类集合
// amount - 总金额
package main
import (
"fmt"
"math"
)
func main() {
var coins = []int{1, 2, 5}
num := coinChange(coins, 11)
fmt.Println(num)
}
// 凑零钱问题
func coinChange(coins []int, amount int) int {
if amount == 0 {
return 0
}
return helper(coins, amount)
}
func helper(coins []int, amount int) int {
if amount == 0 {
return 0
}
if amount < 0 {
return -1
}
res := math.MaxInt32
for _, coin := range coins {
tmp := helper(coins, amount-coin)
if tmp == -1 {
continue
}
res = min(res, tmp+1)
}
if res == math.MaxInt32 {
return -1
}
return res
}
func min(a, b int) int {
if a <= b {
return a
}
return b
}
|
reference
https://labuladong.gitbook.io/algo/mu-lu-ye-2/mu-lu-ye/dong-tai-gui-hua-xiang-jie-jin-jie
链表
使用dummyNode，dummyNode.Next = head
使用node = head
栈
字典树（Trie树）
用于前缀匹配
1
2
3
4
|
type dicTreeNode {
node [26]*dicTreeNode
isEnd bool
}
|
优先队列 prioroty queue （container/heap实现）
队列：FIFO
优先队列：先pop出最高优先级的元素
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
|
// 这段代码演示了如何使用堆接口构建一个优先队列。
package main
import (
"container/heap"
"fmt"
)
// Item 是优先队列中包含的元素。
type Item struct {
value string // 元素的值，可以是任意字符串。
priority int // 元素在队列中的优先级。
// 元素的索引可以用于更新操作，它由 heap.Interface 定义的方法维护。
index int // 元素在堆中的索引。
}
// 一个实现了 heap.Interface 接口的优先队列，队列中包含任意多个 Item 结构。
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
// 我们希望 Pop 返回的是最大值而不是最小值，
// 因此这里使用大于号进行对比。
return pq[i].priority > pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1 // 为了安全性考虑而做的设置
*pq = old[0 : n-1]
return item
}
// 更新函数会修改队列中指定元素的优先级以及值。
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}
// 这个示例首先会创建一个优先队列，并在队列中包含一些元素
// 接着将一个新元素添加到队列里面，并对其进行操作
// 最后按优先级有序地移除队列中的各个元素。
func main() {
// 一些元素以及它们的优先级。
items := map[string]int{
"banana": 3, "apple": 2, "pear": 4,
}
// 创建一个优先队列，并将上述元素放入到队列里面，
// 然后对队列进行初始化以满足优先队列（堆）的不变性。
pq := make(PriorityQueue, len(items))
i := 0
for value, priority := range items {
pq[i] = &Item{
value: value,
priority: priority,
index: i,
}
i++
}
heap.Init(&pq)
// 插入一个新元素，然后修改它的优先级。
item := &Item{
value: "orange",
priority: 1,
}
heap.Push(&pq, item)
pq.update(item, item.value, 5)
// 以降序形式取出并打印队列中的所有元素。
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
fmt.Printf("%.2d:%s ", item.priority, item.value)
}
}
|