数据结构和算法初识

基础概念

数据结构

一维：

• 基础：数组 array（string），链表 linked list
• 高级：栈 stack，队列 queue，双端队列 deque，集合 set，映射 map（hash or map），etc

二维：

• 基础：树 tree，图 graph
• 高级：二叉搜索树 binary search tree（red-black tree，AVL），堆 heap，并查集 disjoint set，字典树 Trie，etc

特殊：

• 位运算 Bitwise，不用过滤器 BloomFilter
• LRU Cache

算法

以下三种方式，是几乎所有算法和数据结构的基石

• if-else,switch:branch
• for.while loop:lteration
• 递归 Recursion(Divide & Conquer, Backtrace)

在基石上的扩展

• 搜索 Search：深度优先搜索 Depth first search，广度优先搜索 Breadth first search,A*,etc
• 动态规划 Dynamic Programming
• 二分查找 Binary Search
• 贪心算法 Greedy
• 数学 Math，集合 Geometry

时间复杂度

时间复杂度用Big O notation表示，也就是O()表示。时间复杂度有这么几种：

O(1)：表示Constant Complexity 常数复杂度

O(log n)：表示Logarithmic Complexity 对数复杂度

O(n)：表示Linear Complexity 线性时间复杂度

O(n^2)：表示N Square Complexity 平方

O(n^3)：表示N Cube Complexity 立方

O(2^n)：表示Exponential Growth 指数

O(n!)：表示 Factorial 阶乘

查看一个函数的时间复杂度，主要跟N有关，而且会去掉前面的常数，也就是O(2)、O(3)统称为常数复杂度，也就是O(1)

例如

int n = 10000
fmt.Println(n)
return 

时间复杂度是 O(1)

int n = 10000
fmt.Println(n)
fmt.Println("hello + ",n)
fmt.Println("hello golang : ",n)
return 

时间复杂度也是 O(1)

for i := 1; i <= n; i++ {
    fmt.Println("hello ", n)
}

时间复杂度是 O(n)

for i := 1; i <= n; i++ {
    for j := 1; j < n; j++ {
        fmt.Println("hello ", n)
    }
}

时间复杂度是 O(n^2)

for i := 1; i <= n; i++ {
    fmt.Println("hello ", n)
}
for j := 1; j < n; j++ {
    fmt.Println("hello ", n)
}

虽然执行的时候，是 O(2n)，但是时间复杂度会去掉前面的常数，也就是 O(n)

for i := 1; i < n; i=i*2 {
    fmt.Println("hello ", n)
}

时间复杂度是 O(log(n))

func fib(n int) int {
    if n <= 2 {
        return n
    }

    return fib(n-2) + fib(n-2)
}

时间复杂度是 O(k^n)

时间复杂度是衡量一段代码效率的重要指标

可以看到，不同的时间复杂度，在n增大时，所需要的时间增大服务不一样，其中最快的是 O(1)，但是实际上几乎不会是这种，其次是 O(log(n))。

使用到 O(1)的情况，例如求和

func sum(n int) int {
    s := 0
    for i := 1; i <= n; i++ {
        s += i
    }
    return s
}

时间复杂度是 O(n)，但是使用求和公式，可以直接获取结果

func sumFormula(n int) int {
    return (1 + n) * n / 2
}

时间复杂度是 O(1)

主定理

一些常用的搜索算法，可以通过主定理直接得到时间复杂度

通过主定理，可以得到：

• 二叉树遍历-前序、中序、后序的时间复杂度都是 O(n)，因为要遍历每一个结点，n代表二叉树中的每一个结点
• 图的遍历的时间复杂度是 O(n)，n代表图里面的每一个结点
• 搜索算法，DFS、BFS时间复杂度都是 O(n)，n代表搜索空间里面的结点总数
• 二分查找法的时间复杂度是 O(log(n))

不同数据结构检索时的时间复杂度

不同数组排序算法的时间复杂度

汇总：http://www.redbubble.com/people/immortalloom/works/22929408-official-big-o-cheat-sheet-poster?p=poster&finish=semi_gloss&size=large

数据结构

一维

数组 array

在golang中定义数组

var a [3]string
b := [2]int{1, 2}

数据会在内存中开辟一段连续的空间，占用的字节数 = 元素类型字节 * 元素个数，例如上例子

fmt.Println(unsafe.Sizeof(a))        // 48，string底层由一个指向数据的指针和int类型长度组成，占16个字节
fmt.Println(unsafe.Sizeof(b))        // 16，int类型占8个字节

因此，访问第一个元素和访问中间的某一个元素的时间复杂度，是一样的，都是 O(1)。

数组的特点是访问快，但是插入、删除慢

例如要在index=3的位置插入一个元素，需要将后续的E\F\G都往后挪动（前提是数组有空余位置）

此时的时间复杂度取决于位置值，是 O(n)

删除操作也是一样的，先将 index=3的值取出来，然后将 EFG的值往前挪动

此时的时间复杂度取决于位置值，也是 O(n)

当然，在golang中，数组的长度是无法扩展的，因此通常是在切片中操作。在切片中，如果长度不足，首先会扩容，将老数组中的内容拷贝到新数组中。

链表 Linked List

链表通过指针指向下一个结点，这种数据结构可以弥补数组中数据插入和数据删除导致的性能问题。

链表根据指针的不同指向，分多种：

• 单链表：指针指向下一个结点的地址，尾结点的指针指向none

  type LinkedList struct {
    value int
    next  *LinkedList
  }

  

• 双链表：一个指针指向下一个结点的地址，另外一个指针指向上一个结点的地址，尾结点的next指向none，头结点的pre指向none

  type LinkedList struct {
    value     int
    pre, next *LinkedList
  }

• 环形链表：单链表下，尾结点的next指向头结点的地址

代码实现

List定义：

单链表：

// List holds the elements, where each element points to the next element
type List struct {                    // list 记录头和尾结点，以及list中元素个数
    first *element
    last  *element
    size  int
}

type element struct {                // 结点
    value interface{}					// 结点中使用interface包含所有类型元素
    next  *element						// 下一个结点的指针
}

双链表：

// List holds the elements, where each element points to the next and previous element
type List struct {
    first *element
    last  *element
    size  int
}

type element struct {
    value interface{}
    prev  *element
    next  *element
}

链表实现的方法

type List interface {
    Get(index int) (interface{}, bool)
    Remove(index int)
    Add(values ...interface{})
    Contains(values ...interface{}) bool
    Sort(comparator utils.Comparator)
    Swap(index1, index2 int)
    Insert(index int, values ...interface{})
    Set(index int, value interface{})

    containers.Container
    // Empty() bool
    // Size() int
    // Clear()
    // Values() []interface{}
}

• 增加结点

  在第一个node和第二个node中间插入一个node

  1. 记录前一个node指向的下一个node的指针
  2. 将前一个node的指针改成指向新的node
  3. 将新的node的指针，指向记录的指针

  

  这个操作是常数操作，事件复杂度是 O(1)

• 删除结点

  将前node的next指向被删结点的next即可

  

增加、删除的操作都不会导致其他的node迁移，在增删操作频繁的场景下，有很大的优势。

一些操作的时间复杂度：

• prepend:O(1)
• append:O(1)
• lookup:O(n)，查询操作需要逐个遍历，时间复杂度取决于便利的node个数
• insert:O(1)
• delete:O(1)

跳表 Skip List

跳表可以解决链表中查询操作慢的问题

针对链表中查询慢的情况，通过升维，或者说以空间换时间的概念，给node添加多个next

在跳表中，增加索引的概念，通过多层索引，实现一次性跨越多个元素，增加查找效率

时间复杂度

第一级索引的个数是 n/2，第二级索引个数是 n/4，以此类推，第k级别索引结点的个数就是 n/(2^k)

那么，当最高级的索引有2个结点，索引层级是h,那么

n/(2^n) = 2

得到

h = log2(n) - 1

也就是说，在跳表中查询数据的时间复杂度是 O(log(n))

当跳表在增加、删除结点之后，有些结点的指针可能指向为none

因此，跳表的维护成本相对而言是比较高的。

空间复杂度

假设原始链表大小为n，每2个结点抽1个，每层索引的结点数

n/2,n/4,...,8,4,2

假设原始链表大小为n，每3个结点抽1个，每层索引的结点数

n/3,n/9,...,9,3,1

空间复杂度是 O(n)

典型题目

在一维数据结构中，有一些典型题目

• 两数之和：https://leetcode-cn.com/problems/two-sum/

  解法1：双循环，便利每两个元素，时间复杂度 O(n^2)

  解法2：使用hash，便利的时候获取是否有target-i位置元素的数字在hash中，时间复杂度 O(n)，更优

• 盛水最多的容器：https://leetcode-cn.com/problems/container-with-most-water/

  解法1：双循环，便利每两个元素，时间复杂度 O(n^2)

  解法2：头尾双角标，判断角标数字小的，该角标向中间移动，时间复杂度 O(n)，更优

• 移动0：https://leetcode-cn.com/problems/move-zeroes/

  解法1：再创建一个等长数组，便利数组，将非0的数字拷贝到另一个数组中，时间复杂度 O(1)，但是空间复杂度 O(n)

  解法2：双角标便利，第一个角标记录非0，第二个角标往后移动，将非0的数字移动到第一个角标上，最后将剩余数字改为0，时间复杂度 O(n)，空间复杂度 O(1)

• 爬楼梯：https://leetcode.com/problems/climbing-stairs/

  解法1：找到规律，例如第3阶楼梯方法次数，为第1阶加上第2阶的总和，f(n)=f(n-1)+f(n-2)，类似斐波那契，而且这里不能使用递归，因为递归的时候会有很多重复的计算，因此要使用循环遍历，从1,2，…，一直计算到n，时间复杂度 O(n)。为了代码渐变，可以将结果放在数组里面，角标0为1，角标1为2，以此类推。

  解法2：直接推到斐波那契公式，时间复杂度 O(log(n))，这个比较复杂

• 三数之和：https://leetcode-cn.com/problems/3sum/(高频老题）

  解法1：先排序，然后三角标，第一个角标选择i，从0开始往右直到大于0，第二个角标从i+1开始，第三个角标从最右边开始，相加之后的结果如果大于0，则将第三个角标往左边移动，减小总和；如果相加之后的结果小于0，则将第二个角标往右边移动，增大总和。总共时间复杂度为 O(n^2)。这题需要注意的是要去重，去重的方法可以是在便利过程中，去掉和前一次便利相同的时刻。

• 反转链表：https://leetcode.com/problems/reverse-linked-list/

  解法1：迭代，由于指针要指向前一个节点，因此，迭代过程中保存前一个节点，然后迭代当前节点，时间复杂度 O(n)，注意，判断条件为当前节点是否为nil，返回的是前一个节点pre

  解法2：递归，将当前节点传到递归函数中进行处理，递归函数中一方面，将 node.Next.Next = node， 第二方面，将 node.Next=nil将首个node的next指向nil，第三方面，将最后一个node作为 函数返回值，从最底层递归函数返回到最上层。

• 两两交换链表中的节点：https://leetcode.com/problems/swap-nodes-in-pairs

  解法1：迭代，记录一个虚拟的head，用于返回head.Next，每次用两个node，head.Next和head.Next.Next进行迭代，终止条件是node.Next为nil或者node.Next.Next为nil，迭代过程中是将链表进行转换，时间复杂度 O(n)

  解法2：递归，两两节点处理，返回的时候，将交换后的head节点返回，用于前一对指定

• 环形链表：https://leetcode.cn/problems/linked-list-cycle/

  解法1：遍历链表中所有结点，将数据存储到map中，查看是否有重复的

  解法2：快慢指针，一个一次走两个结点，一个一次走一个结点，如果重叠，则表示有环

• 环形链表II：https://leetcode.cn/problems/linked-list-cycle-ii/

  解法1：与上一个问题一样，记录map的value为结点索引

  解法2：与上一个问题一样，但是需要注意的是，快指针从头开始，并且每次走1步，第二次相遇的结点，即是循环开始的结点

• K 个一组翻转链表：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

  解法1：将链表拆开成已翻转链表和待翻转链表，在判断后续的链表是否能翻转的时候，可以确定下一个head在哪，将链表进行翻转之后，将指针一起往后移动，pre代表开始翻转链表的上一个节点，next代表需要翻转的链表

  解法2：递归，将第k+1个节点传递到函数中进行递归，如果这个节点不存在，则返回当前节点，如果存在，则传递到函数中。递归终止条件是不满足k个节点，如果满足，则将这个节点递归，递归返回的是翻转后的head，然后将自己这个链表进行反转，最终返回的是翻转之后的头结点。

• 删除有序数组中的重复项：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

  解法1：双指针，一个指针记录不同数字，另外一个指针扫描后续数字，当数字不同，将第一个指针往后移动，并且将第二个指针的数字拷贝到第一个指针的位置

• 轮转数组：https://leetcode-cn.com/problems/rotate-array/

  解法1：新开辟一个数组，将原数组拷贝到新的数组中，原数组中(i+k)%len的位置就是新数组的位置

  解法2：反转数组，先反转所有元素，再翻转两个区间内[:k%len]和[k%length:]的元素，注意，这里可以将反转的函数提取出来，会简单很多

• 合并两个有序链表：https://leetcode-cn.com/problems/merge-two-sorted-lists/

  解法1：迭代，遍历两个链表，选择小的一个作为next，理解简单，但是写法复杂

  解法2：递归，比较将更大的元素和小元素的下一个丢到递归函数中，返回的是最大的，小元素的下一个指向返回的，然后返回这个小的元素

• 合并两个有序数组：https://leetcode-cn.com/problems/merge-sorted-array/

  解法1：比较，放入到新数组中，这个方法理解简单，但是需要额外的内存

  解法2：逆序三指针，一个指针放在数值末尾，另外的两个指针分别是两个数组的数字末尾，两个比较之后将较大的放在第一个指针的位置，指针往前移动，最后，如果有任意一个数字为0，则直接将非0的数组拷贝到前对应数组中

• 两数之和：https://leetcode-cn.com/problems/two-sum/

  解法1：使用map记录，然后遍历数组

  解法2：暴力枚举

• 移动零：https://leetcode-cn.com/problems/move-zeroes/

  解法1：双指针，将非0的数字拷贝到前面，便利结束之后，将剩余的位置全部置0

  解法2：双指针，将非0的数字和前面换位置，换了之后，指针向后移动

• 加一：https://leetcode-cn.com/problems/plus-one/

  解法1：找到最长子串9，然后处理+1

栈 stack

类似于一个容器，先进后出（FIFO），添加、删除皆为 O(1)，查询是 O(n)

基于数组实现

// List holds the elements in a slice
type List struct {
    elements []interface{}
    size     int
}

// Stack holds elements in an array-list
type Stack struct {
    list *List
}

基于单链表实现

// List holds the elements, where each element points to the next element
type List struct {
    first *element
    last  *element
    size  int
}

type element struct {
    value interface{}
    next  *element
}

// Stack holds elements in a singly-linked-list    
type Stack struct {
    list *List				// 由 单链表构成
}

栈提供的方法

// Stack interface that all stacks implement
type Stack interface {
    Push(value interface{})									// 推入一个元素
    Pop() (value interface{}, ok bool)			// 吐出一个元素
    Peek() (value interface{}, ok bool)			// 获取长度

    containers.Container
    // Empty() bool
    // Size() int
    // Clear()
    // Values() []interface{}
}

队列 queue

先进先出，添加、删除皆为 O(1)，查询是 O(n)

基于数组实现

// List holds the elements in a slice
type List struct {
    elements []interface{}
    size     int
}

// Queue holds elements in an array-list
type Queue struct {
    list *List
}

基于环实现

// Queue holds values in a slice.
type Queue struct {
    values  []interface{}
    start   int
    end     int
    full    bool
    maxSize int
    size    int
}

基于单向链表实现

// List holds the elements, where each element points to the next element
type List struct {
    first *element
    last  *element
    size  int
}

type element struct {
    value interface{}
    next  *element
}

// Queue holds elements in a singly-linked-list
type Queue struct {
    list *List
}

双端队列 deque：double end queue

可以看做是栈和队列的结合，可以从头插入或者删除，也可以从尾部插入或者删除，添加、删除皆为 O(1)，查询是 O(n)

基于数组实现

// Deque represents a single instance of the deque data structure. A Deque
// instance contains items of the type specified by the type argument.
type Deque[T any] struct {
    buf    []T
    head   int
    tail   int
    count  int
    minCap int
}

支持的方法

func (q *Deque[T]) Cap() int
func (q *Deque[T]) Len() int
func (q *Deque[T]) PushBack(elem T)
func (q *Deque[T]) PushFront(elem T)
func (q *Deque[T]) PopFront() T
func (q *Deque[T]) PopBack() T
func (q *Deque[T]) Front() T
func (q *Deque[T]) Back() T
func (q *Deque[T]) At(i int) T
func (q *Deque[T]) Set(i int, item T)
func (q *Deque[T]) Clear()
func (q *Deque[T]) Rotate(n int)
func (q *Deque[T]) Index(f func(T) bool) int
func (q *Deque[T]) RIndex(f func(T) bool) int
func (q *Deque[T]) Insert(at int, item T)
func (q *Deque[T]) Remove(at int) T
func (q *Deque[T]) SetMinCapacity(minCapacityExp uint)

优先队列

和所有的队列、stack一致，插入操作是 O(1)，取出操作是 O(log(n))，取出按照元素的优先级取出，底层具体实现的数据结构较为多样和复杂，例如通过列表实现的堆

基于列表实现堆，通过堆实现优先级，基于堆和比较器实现优先级队列，此时插入操作就不是 O(1)，而是 O(nlogn)

// Queue holds elements in an array-list
type Queue struct {
    heap       *Heap
    Comparator Comparator
}

// Heap holds elements in an array-list
type Heap struct {
    list       *List
    Comparator Comparator
}

// List holds the elements in a slice
type List struct {
    elements []interface{}
    size     int
}

// Comparator will make type assertion (see IntComparator for example),
// which will panic if a or b are not of the asserted type.
//
// Should return a number:
//    negative , if a < b
//    zero     , if a == b
//    positive , if a > b
type Comparator func(a, b interface{}) int

队列的方法

// Queue interface that all queues implement
type Queue interface {
    Enqueue(value interface{})								// 入队
    Dequeue() (value interface{}, ok bool)		// 出队
    Peek() (value interface{}, ok bool)				// 获取队列长度

    containers.Container
    // Empty() bool
    // Size() int
    // Clear()
    // Values() []interface{}
    // String() string
}

典型题目

• 有效的括号：https://leetcode.cn/problems/valid-parentheses/description/

  解法1：暴力法，不断地将字符串中的 (),{},[]替换成空字符串，最终看是否是空字符串

  解法2：使用栈，将符号压栈，下一个符号是否与栈顶元素对比，栈顶记录一个随机的符号。这个方法时间复杂度 O(n)

• 最小栈：https://leetcode.cn/problems/min-stack/

  解法1：使用两个栈，一个栈放正常数据，第二个栈存放最小值

• 柱状图中最大的矩形：https://leetcode.cn/problems/largest-rectangle-in-histogram/

  解法1：枚举法，从头开始索引，每次获取左右边界，也就是比他自身矮的，左边边界中间就是面积，每次记录最大面积，时间复杂度是 O(n^3)，会超时

  解法2：快速枚举法，也需要利用栈的思想，核心理解逻辑是柱子的左边界，如果比左边柱子高，则左边界就是左边柱子，如果比左边低或者相等，则左边界就是比自己低的

  解法3：使用栈，每次压入数据与栈顶数据对比，如果比栈顶数据大，则压入，如果小，则弹出栈顶元素，此时可以确定栈顶元素的右边界，为新元素，左边界为栈中下面的元素。以此计算每一个元素的大小，时间复杂度是O(n)

• 滑动窗口最大值：https://leetcode.cn/problems/sliding-window-maximum/

  解法1：暴力求解，嵌套循环，时间复杂度是 O(n*k)，这种方法会超时

  解法2：使用单调队列，确保新加入的元素是队列中最小的，将窗口中的数据加入到单调队列中，如果新加进来的数据大于单调队列尾部，则将队列尾部的值丢掉，直到队列单调，如果小于队列尾部，则直接加入到队列尾部。当窗口移动时，需要确定单调队列头部元素是否在窗口中，因此队列中的数据为索引，并且当队列头部数据不在窗口范围内，则去掉头部。

• 设计循环双端队列：https://leetcode.cn/problems/design-circular-deque/

  解法1：使用数组实现，左边为头部，右边为尾部，但是这种做法在插入时，或者删除时，会拷贝所有元素，可能会超时

  解法2：使用数组加上双角标实现，一个记录头部，一个记录尾部，形成一个环，此时需要注意，环的长度是k+1，头指向的是待加入的数字，尾指向的是加入数字的前一位。Golang中的channel就是这种结构。

  解法3：双向链表，时间复杂度都是 O(1)，这个是最快的

• 接雨水：https://leetcode.cn/problems/trapping-rain-water/

  解法1：将所有位置的左边高墙和右边高墙求出来，最终计算总的结果，需要注意的是，如何确定这个位置的高墙，要满足两个条件，一个条件是左边位置有高墙，第二个条件是左边位置高墙高于自身，否则左边没有高墙。

  解法2：获取每一层能够蓄水的个数，一个一个加起来，得到最终结果，例如第一层能够蓄水的个数，第i个格子能够蓄水，条件是这个格子的左边和右边，都要高于0的墙，也就是两边向中间靠拢，寻找第一个高于0的位置，然后再在这两个位置之间找到小于等于0的个数，加起来就是第1层蓄水的个数，然后顺序找第二层蓄水的个数，依然是从左边找到第一个大于2的数，从右边找到第一个大于2的数，然后找到这两个数之间小于等于1的位置的个数，加起来就是第二层蓄水的个数，以此一直循环到最高的一层。

  解法3：使用单调栈，如果放进去的数字比顶上的数字小，则可以直接放进去，否则将顶的数字拿出来，直到顶部的数字不小于新的数字，获取将要放进去的数字和此时顶部数字的最小值，这个最小值和拿出来的数字差就是水池高度。注意，如果栈取空了，则最后一个取出来的数字是最小值。

哈希表和集合以及映射

Hash Table，也叫散列表，是根据关键码值（Key value）而言，直接进行访问的数据结构。查询、插入、删除的时间复杂度一般是 O(1)

通过把关键码值映射到表中一个为止来访问记录，以加快查找的速度

这个映射函数叫做散列函数（Hash Function，也叫做哈希函数），存放记录的数组叫做哈希表（或散列表）

例如，lies通过hash函数处理，总数为429，对20取模，则将这个值放到位置值为9上

Hash Collisions 哈希碰撞

对于不同的数据，经过相同的哈希函数处理之后，得到相同的下标，这种情况就是哈希碰撞。

一般的处理方式是放一个链表，但是当碰撞过多，查找效率会从 O(1)退化到 O(n)

Hash表的完整结构

Set，集合：不重复元素的集合，相比哈希表，没有值，只有键。

映射：从查找的资料看，很少单独说映射，可以理解为映射也是hash map的一种，只是相比hash map的线程不安全，映射是线程安全的。（有的资料说是通过锁实现线程安全）

典型题目

• 有效的字母异位词：https://leetcode-cn.com/problems/valid-anagram/description/

  解法1：字符串排序，然后看排序后的字符串是否相等

  解法2：使用hash表

• 字母异位词分组：https://leetcode-cn.com/problems/group-anagrams/

  解法1：先排序，然后放到hash表中

• 两数只和：https://leetcode-cn.com/problems/two-sum/description/，以及三数之和，四数之和

  解法1：使用hash，获取target-A是不是也存在于hash中

二维

树 Tree

相比一维的链表或者跳表，是为了解决检索问题，通过升维的思想加快检索。

利用这种升维的思想，一个节点可以同时指向多个节点，这样就形成了树形结构。

注意：树没有环。

二叉树 Binary Tree

在实际开发过程中，用到的最多树形结构就是二叉树，二叉树也就是说每个节点最多只有两个子节点，分别是左子结点和右子节点。

二叉树的遍历方式可以分为三种，都是基于递归，当没有子节点时结束递归，根据递归的顺序可以分为这三种：

前序（Pre-order）：根-左-右

中序（In-order）：左-根-右

后序（Post-order）：左-右-根

图 Graph

图也是一种树形结构，但是相比树而言，图有环形结构

因此，可以这样理解，链表就是特殊化的树，树就是特殊化的图。

二叉搜索树 Binary Search Tree

二叉搜索树（Binary Search Tree），也称二叉查找树，有序二叉树（Ordered Binary Tree），排序二叉树（Sorted Binary Tree），是指一颗空树或者具有下列性质的二叉树：

• 左子树上所有节点的值，均小于它的根节点的值；
• 右子树上所有节点的值，均大于它的根节点的值；
• 以此类推；左、右子树也分别为二叉搜索树。

使用中序遍历时，就是升序排列。

查询、插入操作，都是 O(log(n))

典型题目

• 二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/

  解法1：递归，按照“左-中-右”的顺序递归

  解法2：迭代，使用栈。判断当前节点是否为空，不为空，就压栈，然后处理左边节点，不为空就压栈，直到节点为空，说明左边结束了，然后从栈中取出结点，就是便利的节点，然后处理右边的节点，处理过程与上面一致，判断是否为空，不为空就压栈。

• 二叉树的前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/

  解法1：递归，这个解法比较简单，按照“中-左-右”的顺序递归

  解法2：迭代，使用栈，判断当前节点是否为空，不为空，则放到结果中，然后将右结点压栈，节点往左边移动，直到节点为空。处理完之后，左边处理完毕，只剩下右边节点，开始接触栈，只要栈不为空，从栈中取出数据，然后按照前面的逻辑处理，判断当前节点是否为空，不为空，则当道结果中，然后将右节点压栈。这里一开始直接将root压入栈中，代码会更加漂亮。

• N叉树的后序遍历：https://leetcode.cn/problems/n-ary-tree-postorder-traversal/

  解法1：递归，按照先子节点，然后本节点的顺序递归

  解法2：迭代，使用栈，如果有子节点，则入栈，但是还需要加一个map，用于记录循环的tag

• N叉树的前序遍历：https://leetcode.cn/problems/n-ary-tree-preorder-traversal/

  解法1：递归

  解法2：迭代，使用栈，如果有子节点，则入栈，便利子节点的时候，先加入到res中，然后再判断该子节点是否有子节点，依然使用map记录便利的tag

• N叉树的层序遍历：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

  解法1：广度优先遍历，写一个BFS算法，入参是数组，出参数数组，过程是将入参的子节点全部都便利出来

高级数据结构

高级树

二叉树本质是一种链表，通过升维形成树结构。

二叉树有三种遍历方式：前序（Pre-order）、中序（In-order）、后续（Post-order），（可以通过根节点的顺序来理解和记忆）

在二叉树的基础上，满足顺序要求，左子树所有节点均小于根节点；右子树所有节点均大于根节点；其他节点以此类推。则这棵树是一个搜索二叉树，在搜索时效率很高。此时进行中序遍历就是一个升序排列。

但是，当搜索树的结构部平衡，变成一根棍子，此时搜索速度就会从O(log(n))退化到O(n)。那么保证二叉树的平衡性，就很重要了。

AVL树

AVL树是一种自平衡二叉树，具有以下特点：

• Balance Factor（平衡因子）：

  左子树的高度减去右子树的高度（有时相反）。balance factor = {-1,0,1}

• 通过旋转操作来进行平衡（四种）

为了维持平衡因子，在加入元素时

通过四种旋转操作，维持平衡因子。

1. 左旋
2. 右旋
3. 左右旋
4. 右左旋

右右子树：左旋

左左子树：右旋

左右子树：左右旋

右左子树：右左旋

总结之后：

带有子树的旋转

增加15

加到末尾

先右旋

然后左旋

AVL是一个平衡二叉搜索树。（深度差距很小）

每个节点需要存放 balcen factor = {-1,0,1}，因此不足的是需要存储额外信息、且调整次数频繁。

会拥有四种旋转操作。

对于AVL深度差距小的平衡二叉树，衍生出来深度差距不小而二叉树，也就是近似平衡二叉树。

红黑树 Red-Black Tree

红黑树是一种近似平衡的二叉搜索树（Binary Search Tree），它能够确保任何一个结点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树：

• 每个节点要么是红色，要么是黑色
• 根节点是黑色
• 每个叶结点（NIL结点，空结点）是黑色
• 不能有相邻的两个红色节点
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

关键性质：

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

AVL树和红黑树对比

• AVL树比红黑树更严格的平衡，因此AVL树的查询效率更高
• AVL树比红黑树在插入、删除操作上性能差，这也是由于AVL更严格的平衡性，会有更多的旋转操作
• AVL树的结点上需要存储平衡因子或者高度，这些都是整数，而红黑树只需要在节点上用1个bit存储颜色
• AVL树会运用在数据库上，会有更好的查询效率，而红黑树运用在一些语言的库中，例如map、映射这些数据结构中

布隆过滤器 Bloom Filter

在过滤重复数据的场景中，会经常使用HashTable

但是，在HashTable中会存储数据的key和value，相比而言，存储value的意义不大，并且在大数据量下，Hash冲突也会影响数据性能。因此，在这种场景下，更加适合布隆过滤器。

布隆过滤器由一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

优点是空间效率和查询时间都远远超过一般的算法。

缺点是有一定的误识别率和删除困难。

图中，将x、y、z通过三个hash函数，得到对应的二进制位，添加到布隆过滤器中。判断w的时候，会通过hash函数判断对应二进制位是否都为1

存在误差的情况

例如元素B，布隆过滤器查询到两个位都为1，此时会误判B已存在于布隆过滤器中。

因此，布隆过滤器一般用于缓存中，真正判断一个数据是否已存在，需要更准确的系统，例如数据库。

Golang实现

// 创建一个二进制数字

// add函数，hash之后，将对应的位置为1

// find函数
// 能找到说明可能存在

缓存 Cache

缓存是为了加速数据访问，在一些性能有较大差距的情况下会使用到，例如从数据库读取数据在高并发大访问量场景下性能不高，会引入Redis缓存，又例如CPU直接访问硬盘中的数据性能低，会以内存作为缓存，又例如CPU处理数据使用内存性能低，会有L1 Cache，L2 Cache等。

缓存的要素取决于两个：缓存大小和替换策略。

LRU Cache

Least Recently Used：最少最近优先

一般缓存会以HashTable+Double ListedList实现

具有 O(1)的查询效率

同时具有 O(1)的修改、更新效率

替换算法

LRU：least recently used

LFU：least frequently used

更多替换算法：https://en.wikipedia.org/wiki/Cache_replacement_policies

典型题目

• LRU缓存：https://leetcode.cn/problems/lru-cache/#/

  解法1：Hash表+双向链表

算法思想

递归

在树的数据结构中，一些算法的核心操作就是利用递归。

递归：通过函数体来进行的循环。

func main() {
    fmt.Println(factorial(6))
}

func factorial(n int) int {
    if n > 1 {
        return n * factorial(n-1)
    }
    return n
}

实际过程

递归代码的结构：

1. 终止条件
2. 业务逻辑
3. 将一些参数传到下一层
4. 清理当前层

递归的思维要点：

• 找最近重复子问题，拆解成可重复解决的问题，通过递归实现
• 使用数学归纳法思维

典型题目

• 爬楼梯：https://leetcode.cn/problems/climbing-stairs/

  解法1：递归的题目，找最近重复性。例如第三级台阶等于第二级台阶的次数+第一级台阶的次数。可以用缓存递归，时间复杂度是 O(n)

  解法2：使用动态规划

• 括号生成：https://leetcode.cn/problems/generate-parentheses/

  解法1：使用递归，递归的方法有两种，主要是根据判断条件不同，第一种方式是 f(n)从 f(n-1)中，获取插入括号的方式，注意需要去重；第二种方式是 f(2n)从 f(2n-1)中可以增加的方式，要么增加一个 (要么增加一个 )，判断增加之后是否合理即可。

• 反转二叉树：https://leetcode.cn/problems/invert-binary-tree/description/

  解法1：递归，反转自己的两个子节点，然后将子节点传到下一层

• 验证二叉搜索树：https://leetcode.cn/problems/validate-binary-search-tree/

  解法1：利用二叉树的中序遍历有序性，先便利，然后检验排序是否正确。排序检验可以使用sort.SliceIsSorted方法

• 二叉树的最大深度：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

  解法1：深度优先，递归，将子节点传入下一层，返回最深的子节点+1

• 二叉树的最小深度：https://leetcode.cn/problems/minimum-depth-of-binary-tree/

  解法1：广度优先，迭代，迭代的是子节点

• 二叉树的序列化与反序列化：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

  解法1：深度优先，题目是传入一个结点，先进行序列化，然后再进行反序列化，先通过中序遍历进行排序，反序列化成中序，然后再通过相同的方式进行反序列化，使用递归

  解法2：广度优先，使用迭代，先进行前序遍历进行序列化，反序列化的时候需要注意，节点拿出来的时候处理这个节点的子节点

• 二叉树的最近公共祖先：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

  解法1：暴力法，便利两次，记录对应节点的上面所有父节点，然后获取最后一个重叠的父节点

  解法2：DFS，使用前序遍历，先便利自身，然后左节点，然后遍历右节点，将父节点作为结果返回，需要注意的是判断条件，当自身满足，则返回自身，否则便利左节点和右节点，如果命中其中之一则返回该节点，否则判断子节点是否命中两个如果命中则返回自身，如果没有，则判断左节点是否为空（为空代表没有命中），不为空则返回左节点，否则返回右节点（这种判断条件会简化代码）

• 从前序与中序遍历序列构造二叉树：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

  解法1：递归，将数组切开，切割成左节点的数组和右节点的数组，传递到左节点和右节点中

• 组合：https://leetcode.cn/problems/combinations/

  解法1：递归，f(n,k)和 f(n,k-1)的关系，这里需要注意，在便利数组的时候，使用append操作，可能会导致原数组扩容，出现结果异常的情况

• 全排列：https://leetcode.cn/problems/permutations/

  解法1：递归，f(nums)和 f(nums[1:])的关系，每次往结果中插入一个数字，在任何地方插入

• 全排列 II：https://leetcode.cn/problems/permutations-ii/

  解法1：在上一题的基础上，增加数组去重

分治 Divide & Conquer

分治是从递归的思想分化而来，递归是将大问题分解为重复的小的子问题。而分治是将大问题分解为小问题，寻找小问题的重复性，最终将子问题组合，从而解决大问题。

分治代码模板（与递归差不多）：

1. 终止条件，也就是子问题没有了
2. 处理当前逻辑
3. 调用函数，下探到下一层
4. 将结果组合起来
5. 清理当前层状态

回溯

采用试错的思想，尝试分步的区解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其他的可能的分步解答再来尝试寻找问题的答案。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

典型题目

• Pow(x,n)：https://leetcode.cn/problems/powx-n/

  解法1：暴力法，乘以n次，时间复杂度是 O(n)

  解法2：分治法，将n每次对半拆开，需要注意的是需要n的奇偶性和正负性，时间复杂度是 O(log(n))

• 子集：https://leetcode.cn/problems/subsets/

  解法1：DFS，一层一层往下，产生子集，最终汇总到一起

  解法2：两个循环，一个循环数字，另外一个循环循环已经添加上的元素

  解法3：位运算，位数为数组长度

• 多数元素：https://leetcode.cn/problems/majority-element/description/

  解法1：使用HashMap

  解法2：先排序，然后取中值

  解法3：投票法，先将 [0]登记为答案，票数为1，然后遍历到最后，相同的数，票数+1，不同的数，票数-1，票数为0，则将下一个数登记为答案，票数为1，直到最后，剩下的数就是答案

• 电话号码的字母组合：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

  解法1：分治法加迭代

  解法2：递归，f("12")为1代表的字母，和 f("2")的组合，需要注意的是，初始化的时候，使用map[uint8][]string

• N皇后：https://leetcode.cn/problems/n-queens/

  解法1：暴力回溯，先放1格，然后判断第二格是否满足，满足的时候继续下，不满足的时候，将前一格踢出去，从前一格的位置往后下

  解法2：递归加回溯，一排一排遍历，便利的时候判断从0到n哪一个点满足放皇后，满足的话，继续递归到下一层，最终全部满足则为结果

深度优先搜索 DFS

在树或者图结构中，需要遍历所有节点、并且每个节点仅访问一次的情况下，可以使用深度优先或者广度优先处理。

DFS实例代码

func dfs(node *Node) {
    if _,ok := visited[node];ok {
        // already visited 
        return
    }

    visited[node] = true 

  // process current node 
  // logic 
  // 如果是一个多叉树，则需要便利所有的多叉树
    dfs(node.Left)
    dfs(node.Right)
}

遍历顺序：

先从左节点（或者右节点）往下遍历，便利到最底层，最底层没有数据之后，再访问另外一边。

图中的遍历顺序也是一样的

图中使用递归，则需要判断当前节点是否被遍历过

func dfs(node *Node) {
    if _,ok := visited[node];ok {
        // already visited 
        return
    }

    // process 
    visited[node] = true 

    // next level 
    for _,nextNode:= range node.Children {
        if _,ok := visited[nextNode];!ok {
            dfs(nextNode)
        }
    }
}

非递归写法，使用栈模拟递归

func dfs(root *Node) []*Node {
    if root == nil {
        return nil 
    }
    visited := make(map[*Node]bool)
    stack := NewStack(*Node)
    stack.Push(root)

    for stack.Len != 0 {
        node = stack.Pop()
        visited[node]=true 

        process(node)

        nodes := generate_related_nodes(node)
        stack.push(nodes)
    }
}

广度优先搜索 BFS

广度优先遍历就需要使用队列

广度优先相比深度优先的顺序：

使用队列迭代：

func bfs(start *Node) {
    queue := NewQueue(*Node)
  // 将start入队
    queue.Push(start)

    visited[start]=true 
    for len(queue) != 0 {
    // 从队列中取出，队列，先入先出
        node := queue.Pop()

        process(node)

        nodes := generate_related_nodes(node)
    // 将子node放到队列中
        queue.Push(nodes)
    }
}

典型题目

• 二叉树的层序遍历：https://leetcode.cn/problems/binary-tree-level-order-traversal/#/description

  解法1：BFS

  解法2：使用DFS，然后记录层树

  解法3：骚操作，直接通过脚标便利，每一层开始是2^(n-1)，结尾是 2^(n-1)-1

• 最小基因变化：https://leetcode.cn/problems/minimum-genetic-mutation/#/description

  解法1：BFS，但是需要注意，不能往回走

• 在每个树行中找到最大值：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/#/description

  解法1：BFS，使用数组记录下一层节点，记录这层节点的最大值，直到没有下一层，需要注意的是放入数组的条件

• 单词接龙：https://leetcode.cn/problems/word-ladder/description/

  解法1：与上面最小基因变化的代码一样，将start放到数组里面，然后比较数组里面能够变化而成的字母，放到新的数组里面，以此变化，注意，不能往回走，因此需要将所有便利过的单词记录下来

  解法2：双向BFS，头和尾两端一起BFS

• 单词接龙 II：https://leetcode.cn/problems/word-ladder-ii/description/

  解法1：这题目相比上一题，需要打印出路径，因此最好是选择使用树形结构记录下产生的树，要使用hashmap去重。将节点与总hashmap中的元素对比查看是否可以作为子节点，如果能够作为子节点，则去掉总HashMap，但是这种解法，一般会超时

  解法2：双向BFS

• 岛屿数量：https://leetcode.cn/problems/number-of-islands/

  解法1：DFS，删除最边缘的1

  解法2：BFS，往上、下、左、右扩散，碰到1，就将1和周边的1全部变成0，一直到全部变成0，次数就是岛屿数量

• 扫雷游戏：https://leetcode.cn/problems/minesweeper/description/

  解法1：DFS，递归，先判断点是不是雷，如果是，修改标记，返回，如果不是，则获取周围个数，如果个数是0，该标记，将八个方向的点递归，如果个数大于0，则标记个数，返回。

贪心算法 Greedy

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心算法可以解决一些最优化问题，如：求图中的最小生成树，求哈夫曼编码等。然后对于工程和生活中的问题，贪心算法一般不能得到所求的答案。

一旦一个问题可以通过贪心算法来解决，那么贪心算法一般是解决这个问题的最好办法。由于贪心算法的高效性以及其所求得的答案比较接近最有结果，贪心算法可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。比如最小生成树。

适用贪心算法的场景：

• 问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。
• 相比动态规划，每个子问题的解决方案做出选择，不能回退；

典型题目

• 零钱兑换：https://leetcode.cn/problems/coin-change/

  解法1：贪心算法，先用最大匹配，再用次大匹配。这是由于硬币是倍数。当硬币不是倍数，则不一定能使用贪心算法

  解法2：递归，f（n）=min(f(n-5),f(n-2),f(n-1)) +1，也就是某一个数，等于对应硬币的最小次数，加上这枚硬币。自上而下的递归会超时，需要自下而上。

• 柠檬水找零：https://leetcode.cn/problems/lemonade-change/description/

  解法1：记录5、10、20块面额钱的个数，因为只需要找5、15的面额，分别讨论即可。需要注意，贪心的是如果找15，则尽量先试用10块的面额。

• 买卖股票的最佳时机II：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

  重点是想到如何获取最大时机，是比较相邻两天。

  解法1：贪心算法，只要后面1天比前面1天高，就前1天买，后1天卖。

  解法2：动态规划，DP，其中，dp定义是一个二维数组，一位代表天数，二维代表手上有股票还是没有股票，状态转移方程是：如果今天不持有股票，则手上的钱是要么昨天有股票，将股票卖掉，要么是昨天没有股票，今天也没有，两者取最大值，dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])；如果今天要持有股票，则手上的钱是昨天不持有股票的情况再买股票，或者昨天有股票的时候，两者取最小值，dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])。

• 分发饼干：https://leetcode.cn/problems/assign-cookies/description/

  解法1：贪心算法，先排序，优先满足胃口小的孩子，双指针，一个代表孩子，一个代表饼干

• 模拟行走机器人：https://leetcode.cn/problems/walking-robot-simulation/description/

  解法1：模拟走格子即可，需要注意的是要将环境准备好，这里不需要准备二元数组作为格子，而是准备好方向，由于障碍物要一直判断，因此，需要将障碍物加入到map中

• 跳跃游戏：https://leetcode.cn/problems/jump-game/

  解法1：按照层数递归，贪心算法，能跳到最后一层则为true，不能则回溯，然后步数-1

  解法2：两重循环，通过步数，更新能跳到的点，记录为true，，时间复杂度 O(n^2)

  解法3：贪心算法，从后往前进行贪心，时间复杂度是 O(n)

  解法4：记录最大的能到的地方，便利这些地方，如果有比最大的更大，则最大能到的地方更新，直接便利完最大的地方，还没有到达终点，则为不可达，便利的时候，如果最大的地点大于或者等于终点，则代表可达

• 跳跃游戏II：https://leetcode.cn/problems/jump-game-ii/

  解法1：双指针，第一个指针从0开始，第二个指针是最大当前能够走到的步数，从指针1便利到指针2，更新最小步数，最小步数为第一个指针的步数+1，同时获取能够走到的最大下一步。更新完成之后，第一个指针移动到第二个指针的位置，第二个指针移动到最大的位置，继续便利。

二分查找

二分查找的前提：

1. 目标函数单调性（单调递增或者递减）
2. 存在上下界（bounded）
3. 能够通过索引访问（index accessible）（排除单链表）

Golang代码模板

func BinarySearch(array []int, target int) int {
    left, right := 0, len(array)-1
    for left <= right {
        mid := (left + right) / 2
        if array[mid] == target {
            return left
        } else if array[mid] > target {
            right = mid - 1				// 注意，这里要 -1 ，防止最终找不到
        } else {
            left = mid + 1
        }
    }
    return -1
}

典型题目

• x的平方根：https://leetcode.cn/problems/sqrtx/

  解法1：使用二分法，这里的二分法需要注意，end为x/2+1，条件是start<=end，返回的是start-1

  解法2：牛顿迭代法

• 有效的完全平方根：https://leetcode.cn/problems/valid-perfect-square/

  解法1：使用二分法，end为x/2+1，条件是start<=end

• 搜索旋转排序数组：https://leetcode.cn/problems/search-in-rotated-sorted-array/

  解法1：使用二分法和迭代，(nums[start] <= target && target <= nums[mid]) || (nums[mid] <= target && target <= nums[end])时，说明target在升序的数组之间，使用二分法查找即可。其他的情况，说明也是一个旋转的数组，将头和尾再进行迭代即可，需要注意的是要判断一下当target不存在于这个区间的情况，

• 搜索二维矩阵：https://leetcode.cn/problems/search-a-2d-matrix/

  解法1：先试用二分法确定行，这个其实就是将每一行的第一个元素取出来，找到最大的小于target的数，也就是目的行，然后再到这一行中使用二分法，是否能查询到数字

• 寻找旋转排序数组中的最小值：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

  解法1：先排序

  解法2：直接二分查找，关键在于需要确定小的数字在左边部分还是右边部分，时间复杂度是 O(log(n))。不停地寻找左边大于右边的数组，直到查找到[2,1]这样子的，需要注意的是，左角标往mid+1移动，而右角标等于mid

动态规划 Dynamic Programming

又叫做动态递推，将一个复杂的问题，以递归的方式将它分解为简单的子问题。相比分治，分治中每一个子问题中有一个最优解，然后得到全局最优解，但是动态规划中，不需要保存这些值。动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构），共性是找到重复子问题。

差异性是最优子结构、中途可以淘汰次优解。

例如：斐波那契数列

时间复杂度是 O(n^2)，每一个节点，都要将下面的节点计算一次，每一个下面的节点，又要将它下面的节点计算一次。

优化方法是做一个缓存，将已经计算过的数字，缓存起来。将时间复杂度降低到 O(n)

有例如走格子问题：

不同路径：https://leetcode.cn/problems/unique-paths/

不同路径II：https://leetcode.cn/problems/unique-paths-ii/

从start到end的做法，其实是从A走到end的做法+从B到end的做法，这种分治的思想。

还可以使用递推的思想，从结尾的地方，向上递推，每个格子的做法为相邻两个格子走法的和，

边界和墙都无法走向该格子，有相邻的右边格子和下边格子才能走到对应格子，最终可以得到地图上每一个格子到end的走法

动态规划关键点：

1. 最优子结构： opt[n] = best_of(opt[n-1],opt[n-2],...)

2. 存储中间状态：opt[i]

3. 递推公式（或者叫做状态转移方程或者DP方程）

   Fib: opt[n] = opt[n-1] + opt[n-2]

   二维路径: opt[i,j]=opt[i+1][j]+opt[i][j+1]（且判断 a[i,j]是否空地）

又例如最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/

解法1：暴力求解，求两个字符串的子序列，然后两个子序列对比是否存在，时间复杂度是 O(2^n)

解法2：找到重复性，看最后一个字母是否相同，如果相同，则计算减掉这个字符串之后剩余字符串的最长子序列+1，如果不相同，则随机选择一个字符串去掉一个字符，然后比较。

典型题目

• 爬楼梯：https://leetcode.cn/problems/climbing-stairs/description/

  解法1：f(n)=f(n-1)+f(n-2)

• 三角形最小路径和：https://leetcode.cn/problems/triangle/description/

  解法1：n层递归，每一层可以左也可以右，但是需要缓存起来

  解法2：DP，找到重复性，定义状态数组，列出DP方程。DP可以从上往下，也可以从下往上，相比而言，从上往下理解起来更加简单。状态转移方程，其实就是对应节点的左上和右上最小的路径，外加自身的长度。problem(i,j) = min(sub(i-1,j),sub(i-1,j-1))+a[i,j]，需要注意的是，最左侧和最右侧的路径计算方法不一样，需要独立处理。

  国际版推荐解法：https://leetcode.com/problems/triangle/solutions/38735/Python-easy-to-understand-solutions-(top-down-bottom-up)./

• 最大子数组和：https://leetcode.cn/problems/maximum-subarray/

  解法1：暴力法：起点和终点都是正数，时间复杂度是 O(n)

  解法2：动态规划，找到状态转移方程，其实就是看dp[i-1]是否大于0，如果大于0，则 dp[i]=dp[i-1]+nums[i]，如果小于0，则 dp[i]=nums[i]，dp记录的是数组中的最大和，最终的结果是dp中的最大值

• 乘积最大子数组：https://leetcode.cn/problems/maximum-product-subarray/description/

  解法1：动态规划，这里需要思考状态转移方程，由于有正负数和0的存在，加上这一个数字之后，要保留一个最大值和一个最小值，为了后续的负数存在，最大值乘以nums[i]，或者最小值乘以nums[i]，或者nums[i]本身的最大值，就是带有这个数字的数组的最大值，dp[i][0]= maxInt(dp[i-1][0]*nums[i], dp[i-1][1]*nums[i], nums[i])，dp[i][1] =minInt(dp[i-1][0]*nums[i], dp[i-1][1]*nums[i], nums[i])，最终需要便利dp，获取真正的最大值。

• 零钱兑换：https://leetcode.cn/problems/coin-change/

  解法1：广度优先，寻找节点为0的节点个数

  解法2：递归，时间复杂度 O(n^2)

  解法3：DP，状态转移方程是 f(n) = min(f(n-1),f(n-2),f(n-5))+1，也就是可以通过硬币获得本数的前一个数的最小值，这里注意，可以将amount+1作为最大值，如果无法兑换，则为最大值，最终返回结果判断是否是这个最大值，如果是最大值，则代表无法兑换。

• 打家劫舍：https://leetcode.cn/problems/house-robber/

  解法1：暴力法

  解法2：DP，重复性是指每个房子可以选择偷不偷；定义状态数组从0到i间房子中偷和不偷的最大值，dp[i][0]代表没有偷，dp[i][1]代表偷了，确定第 i个房子偷还是不偷，不偷，则是前一个房子偷或者不偷的最大值 dp[i][0] = max(dp[i-1][1],dp[i-1][0])，如果偷，则是前一个房子不偷加上现在这个房子钱的总和 dp[i][1] = dp[i-1][0] + nums[i]，取最后一个房子偷或者不偷之间的最大值 max(dp[length-1][0],dp[length-1][1])

• 打家劫舍II：https://leetcode.cn/problems/house-robber-ii/description/

  解法1：DP，但是要拆开讨论，讨论0号偷还是不偷，当0号偷的时候，那么1号就只能不偷，此时就需要从2号开始讨论dp，2号开始可以选择偷还是不偷，这个时候的最大值就是最后一家不偷。当0号不偷的时候，那么1号可以开始选择偷还是不偷，此时从2号开始讨论dp，这个之后的最大值就是最后一家偷或者不偷的最大值。最终结果就是两种情况下的最大值。

• 买卖股票的最佳时机：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/#/description

  解法1：使用栈，如果比栈顶小，入栈，如果比栈顶大，则说明有利润，则记录利润的数字，最终取利润的最大值

  解法2：使用动态规划，记录第i天的利润，以及到第i天的最小值，第i天的利润要么是前一天的利润，要么是今天的价格减去最小数，两者取最大值，最终结果取利润的最大值

• 买卖股票的最佳时机II：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

  解法1：使用DP，二维数组，第二个维度记录当前有股票或者是没有股票对应的利润，今天有股票的利润是前一天没有股票的情况下的利润购入股票或者是前一天有股票的情况下前一天的利润，两者最大值；今天没有股票的利润是前一天没有股票的利润或者是前一天有股票今天卖掉股票的利润，两者取最大值。

• 买卖股票的最佳时机III：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

  解法1：DP，二维数组，第二个维度记录当前状态，也就是第一次购入股票的最大收益、第一次卖出股票的最大收益、第二次购入股票的最大收益、第二次卖出股票的最大收益，初始化状态可以理解为第1天购入、卖出、购入、卖出，dp[0] = [4]int{-prices[0], 0, -prices[0], 0}，状态转移方程是：第i天第一次购入的最大收益，为前一天购入的最大收益和今天的价格之间，取最大值，dp[i][0] = max(dp[i-1][0], -prices[i])，第i天第一次售出的最大收益，收益为前一天购入的最大收益+今天的价格，最大值为前面一天售出的最大收益和今天售出的最大收益之前取最大值，dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])，第i天第二次购入的最大收益，为前面一天第一次卖出的最大收益-今天的价格，和前一天第二次购入的最大收益之间的最大值，dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i])，第i天第二次售出的最大收益，为前面一天第二次购入的最大收益+今天的价格，和前一天第二次卖出之间的最大值，dp[i][3] = max(dp[i-1][3],dp[i-1][2] + prices[i])。

• 最佳买卖股票时机含冷冻期：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

  解法1：DP，二维数组，第二个维度记录当前状态，0表示今天有股票的最大收益，1表示今天没有股票的最大收益，2表示冷冻期的最大收益，初始化条件，也就是今天买入股票，或者今天不购入股票，dp[0] = [3]int{-prices[0], 0, 0}，状态转移方程，第i天有股票的最大收益，是昨天冷冻期的收益-今天股票价格，或者昨天有股票的收益，取最大值，dp[i][0] = max(dp[i-1][2]-prices[i], dp[i-1][0])，第i天没有股票的最大收益，是把持有的股票卖出，和昨天冷冻期，今天不购入取最大值，dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][2])，第i天冷冻期的最大收益，是昨天没有股票，和昨天冷冻期的最大收益，dp[i][2] = max(dp[i-1][1],dp[i-1][2])，结果值是最后一天卖出或者最后一天冷冻期两者的最大值，max(dp[length-1][1], dp[length-1][2])

• 买卖股票的最佳时机IV：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

  解法1：DP，二维数组，第二个维度代表当天第i次购入的最大收益，当天第i次卖出的最大收益，第二个维度长度是2k。初始化条件是今天一次性购入k次，一次性卖出k次，这个时候的收益，也就是第1天，购入1次，卖出1次的最大收益，再次购入2次，卖出2次的最大收益，状态转移方程，需要注意的是，第i天，第一次购入的最大收益，是比较前一天第一次购入的最大收益和今天的是第一次购入的最大收益的最大值，dp[i][0] = max(dp[i-1][0], -prices[i])，任何一天的第一次卖出的最大收益，是比较前一天第一次购入的最大收益+今天的价格，和前一天第一次卖出的最大收益，dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])。第i天的第j次购入的最大收益，是昨天第j-1次卖出的收益，要么昨天买了，要么昨天没买，那么今天价格，或者昨天第j次购入，和今天第j次购入，两者的最大值，dp[i][2*j] = max(dp[i-1][2*(j-1)+1]-prices[i], dp[i-1][2*j])，第i天的第j次卖出的最大收益，是昨天第j次购入+今天的价格，或者昨天第j次卖出，两者的最大值，dp[i][2*j+1] = max(dp[i-1][2*j]+prices[i], dp[i-1][2*j+1])，最终返回结果是最后1天的第k次交易 dp[length-1][2*(k-1)+1]

• 买卖股票的最佳时机含手续费：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

  解法1：DP，二维数组，第二个维度代表当天是否持有股票的最大收益，这里取卖出的时候缴纳手续费，0 代表持有股票的钱，1 代表不持有股票的钱。初始化条件，第1天购入的最大收益，卖出的最大收益，dp[0] = [2]int{-prices[0], 0}，状态转移方程，第i天，持有的最大收益，要么今天买，要么今天不买，用昨天的股票，两者取最大值，今天买，就是昨天卖出的收益-今天的价格，今天不买，就是昨天买的收益，dp[i][0] = max(dp[i-1][1]-prices[i], dp[i-1][0])，第i天，不持有的最大收益，要么是将昨天持有的今天卖掉，要么今天不卖，两者取最大值，今天卖，就是昨天持有的最大收入+今天的价格-今天的手续费，今天不卖，就是昨天不持有股票的最大收益，dp[i][1] = max(dp[i-1][0]+prices[i]-fee, dp[i-1][1])，最终结果，取最后1天不持有股票的最大收益，dp[length-1][1]。

• 完全平方根：https://leetcode.cn/problems/perfect-squares/

  解法1：DP，一维数组，代表从0到n这几个数字的结果，从0到n计算即可。首先判断n是否是完全平方根，如果是，则结果为1，如果不是，则需要二次便利，依次减去最小平方根的数字的结果，取这些结果的最小值，f(n)=min(f(n-1),f(n-4),f(n-9)...)，结果为最小值+1

• 编辑距离：https://leetcode.cn/problems/edit-distance/

  解法1：DP，二维数组，代表两个字符串，长度分别是两个字符串的长度+1，代表一个字符串转变成另外一个字符串的次数。例如s1是””，s2是””，则是0；例如s1是””，s2是”r”，则是1；例如s1是””，s2是”ro”，则是2；例如s1是””，s2是”ros”，则是3；同理，例如s1是”h”，s2是””，则是1，以此类推，就是初始化。状态转移方程，从s1到s2有三种情况，要么是加1个字符，要么是删除1个字符，要么是修改1个字符，从短到长，可以理解为s1加1个字符变成s2，s2加1个字符变成s1，s1和s2都加1个字符之后相等。如果两个字符相同，例如”ho”和”ro”，则是从”h”到”ro”，”ho”到”r”，”h”到”r”-1之间，取最小1个+1，也就是min（2,2，1-1）+1，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]-1) + 1，如果两个字符串不相同，例如”hor”和”ros”，则是从”ho”到”ros”，”hor”到”ro”，”ho”，”ro”之间，取最小1个+1，也就是min（2，,2，1）+1，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

• 跳跃游戏：https://leetcode.cn/problems/jump-game/

  解法1：DP，一维数组，记录当前这一步是否可以达到，往数组后面便利的时候，更新能够达到的最远地点。

• 跳跃游戏II：https://leetcode.cn/problems/jump-game-ii/

  解法1：DP，一维数组，记录当前这一步能够达到的最小步数，用 map[int][]int记录对应地点能够达到的前一个地点的最小步数，dp[i]为map中对应地点最小步数+1，初始化条件是dp[0]=0。

• 不同路径：https://leetcode.cn/problems/unique-paths/

  解法1：DP，二维数组，记录当前这点能够达到的走法只和。初始化条件，因为只能往右和往下走，因此第0行和第0列的走法，都是1。状态转移方程，这个点，只能通过往右走和往下走能走到，因此，走到这个点的走法，就是这个点的上面和左边的点走法只和，dp[i][j] = dp[i-1][j]+dp[i][j-1]，最后的结果就是这个点的值，dp[m-1][n-1]

• 不同路径II：https://leetcode.cn/problems/unique-paths-ii/

  解法1：DP，二维数组，代表当前节点能够走到的方式。初始化条件，也就是初始化左边界和上边界，需要注意石头的位置，出现石头则不能再往右走或者往下走，更右边的或者更下面的，都是0。条件转移方程，有石头的地方路线为0，其他的地方，依然是左边的+上面的，dp[i][j] = dp[i-1][j] + dp[i][j-1]，最终结果为最后一个点，dp[length-1][tmpl-1]。

• 不同路径III：https://leetcode.cn/problems/unique-paths-iii/

  解法1：DFS+回溯，先将数组遍历一遍，确定起始位置、结束位置、需要走的格子个数，这里需要注意，由于要从起始位置走到结束位置，也就是结束的位置也算1步，要走的格子个数从1算起。然后进行dfs，返回结果，dfs中，先判断是否超过格子，然后判断当前是否是障碍，再判断当前障碍是否是终点，如果是终点，判断是否一个空的格子都没有，没有格子，返回1，代表这个方案可以，如果还有空格子，就回溯，都不是，则代表这个格子可以走，将这个格子标记为-1，代表后面不能再走回来，然后将四个方向继续DFS，进行DFS的时候，除了传入下一步的格子，还有步数-1，当四个方向都DFS完，结果汇总起来，最终的结果个数就是次数。

• 零钱兑换：https://leetcode.cn/problems/coin-change/

  解法1：DP，方程为 f(n)=min(f(n-1),f(n-2),f(n-5))+1

• 零钱兑换II：https://leetcode.cn/problems/coin-change-ii/

  解法1：DP，定义一维数组，长度是amount+1，代表第i个数字使用钱币组成的个数。那么，第n个数组成的次数f(n)=f(n-1)+f(n-2)+f(n-5)，但是这里不能直接便利coins，会出现去重，思路应该是当使用coins[i]硬币时f(n)的组成个数，等于使用coins[i-1]硬币时n组成的次数+使用coins[i]时f(n-coins[i])的使用次数。也就是说，例如3，先用1组成，组成0有1次，组成1有1次，组成2有1次，组成3有1次，在加一块硬币2，此时，组成0有1次，组成1有1次，组成2有2次（2-2=0,组成0的次数+使用1硬币组成2的次数=2次），组成3有2次（3-2=1，组成1的次数+使用1个硬币组成3的次数=2次）。先通过遍历硬币，再便利数字，就不会出现重复，应为大硬币都是后面加上的。总结下来，思路就是要么这个数字，是小硬币组成的，要么这个数字是使用小硬币+大硬币组成，dp[i] += dp[i-coin]。

• 最长有效括号：https://leetcode.cn/problems/longest-valid-parentheses/

  解法1：DP，定义一维数组，长度是字符串的长度，代表当结尾是这个字符串时，最长合法括号字符串的长度。初始化条件，（（、））、）（的情况，最长都是0，只有（）时，dp[1]是2，此时最长的就是2。状态转移方程从2开始，当最后1位是）,才是一个合法的括号，倒数第二位是（，例如（（），则是2+再往前数2位的长度，倒数第二位是），例如 （（）），则要往前数1位的dp值，在字符串中查询这个dp值前1位的字符是否是（，是（，才是一个合法的括号，此时的长度就是前1位的dp+2。结果取数组中的最大值。

• 最小路径和：https://leetcode.cn/problems/minimum-path-sum/

  解法1：DP，定义二维数组，值是记录到该点的最短距离。初始化条件是将i=0和j=0的值确定下来，确定的方法就是加上上一个数字或者左边一个数字的值。状态转移方程是从i=1到j=1开始，结果是左边的dp和上面的dp，两者取一个小的数，加上该点本身的数。最终取右下角的数。

• 解码方法：https://leetcode.cn/problems/decode-ways/

  解法1：DP，定义一维数组，是加上一个字符的时候，代表的解码总数，dp := make([]int, len(s)+1)。初始化条件，注意，默认0位置是1，代表一个字符都没有，也是1种，用于后续给两个字符的时候相叠加，只有1个字符也是1，排除了0为首的情况，dp[0], dp[1] = 1, 1。状态转移方程，如果当前字符合法，则数目为加上f(n-1)，dp[i+1] += dp[i]。如果与前一个字符一起合法，则数目为加上f(n-2)，dp[i+1] += dp[i-1]。

• 最大正方形：https://leetcode.cn/problems/maximal-square/

  解法1：DP，定义dp，二维数组，代表这个点的最大正方形边长，dp := make([][]int, length)。最长边长为res。先便利两个变成，i == 0 || j == 0，如果为1，则该点最大正方形变长为1，res为1。状态转移方程，只有当本身是1，则可以是一个正方形，matrix[i][j] == '1'，最大正方形的周长，是（左边，上边，左上边）正方形最大周长中的最小值+1，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，更新最大周长，最后的值即为周长的平方。

• 矩形区域不超过k的最大数值和：https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k/

  解法1：DP加暴力。dp为1，1到m，n之间的数字和。先便利一遍所有的格子，计算出所有的dp，和最小值，最小值就是将小于0的数相加。如果 i == 0 && j == 0，dp[i][j] = matrix[i][j]；如果 i > 0 && j == 0，dp[i][j] = dp[i-1][j] + matrix[i][j]，如果 i == 0 && j > 0，dp[i][j] = dp[i][j-1] + matrix[i][j]，都不是，则 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j]。这个过程可以直接判断matrix[i][j]和dp[i][j]是不是k，如果是，则直接返回，节约时间。然后开始暴力便利，将每两个格子之间的总和计算出来，逐步缩小到k，四层循环遍历，将i，j遍历两次，如果 x == 0 && y == 0，tmp = dp[i][j]，如果 x == 0 && y > 0，tmp = dp[i][j] - dp[i][y-1]，如果 x > 0 && y == 0，tmp = dp[i][j] - dp[x-1][j]，如果以上都不是，tmp = dp[i][j] - dp[i][y-1] - dp[x-1][j] + dp[x-1][y-1]，比较tmp的最小值、k的大小，逐步靠近k的值。

• 青蛙过河：https://leetcode.cn/problems/frog-jump/

  解法1：DP，定义dp代表第i个石子能够被跳到时，跳的步数，map[int]map[int]bool。先便利一遍所有的石子，记录石子的位置。初始化，第1颗石子能够达到，并且是0步，这样可以确保第1颗石子可以1步达到，dp[0] = map[int]bool{0: true}。状态转移方程，便利每一颗可以达到的石子的步数，分别记录步数k-1、k、k+1，能够达到的石子，记录这个石子到达的时候的步数，如果达到的石子是最后一个石子，则返回true，否则返回false。

• 分割数组的最大值：https://leetcode.cn/problems/split-array-largest-sum/

  解法1：DP+暴力，定义二维数组，第一维，代表份数，第二维，代表数字长度，值为对应份数和长度下，最大连续数组的和。初始化，第一个数字，份数为1的时候，此时的最大值，也就是直接相加。状态转移方程，从1份开始便利，长度也从i开始，sub:= dp[0][j] - dp[0][m]，t := max(dp[i-1][m], sub)，然后取t的最小值，dp[i][j]为t，结果值为dp的最后一位。

• 学生出勤记录II：https://leetcode.cn/problems/student-attendance-record-ii/

  解法1：DP，定义dp，三位数组，一维代表第n次，二维代表A的次数，三位对应L的连续次数，值是对应的奖励的次数。初始化，第一天A、L、P的情况下的次数，0次A，0次L、1次L，2次L，1,1,0，1次A，0次L、1次L，2次L，1,0,0。状态转移方程，第i天，0次A，0次L，只能是昨天0次L，1次L，2次L，然后今天P，dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]) % 1000000007，第i天，0次A，1次L，只能是昨天0次A，0次L，dp[i][0][1] = dp[i-1][0][0]，第i天，0次A，2次L，只能是昨天0次A，1次L，dp[i][0][2] = dp[i-1][0][1]，第i天，1次A，0次L，可以是昨天0次A，0次L，1次L，2次L，然后今天A，也可以是昨天1次A，0次L，1次L，2次L，然后今天P，dp[i][1][0] = (dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2] + dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2]) % 1000000007，第i天，1次A，1次L，只能是昨天1次A，0次L，dp[i][1][1] = dp[i-1][1][0]，第i天，1次A，2次L，只能是昨天1次A，1次L，dp[i][1][2] = dp[i-1][1][1]，最终的结果是dp最后一列的所有数之和，(dp[n-1][0][0] + dp[n-1][0][1] + dp[n-1][0][2] + dp[n-1][1][0] + dp[n-1][1][1] + dp[n-1][1][2]) % 1000000007

• 任务调度器：https://leetcode.cn/problems/task-scheduler/

  解法1：利用桶的思想，先便利出最大值和最大值相同的数的个数。这个最大值就是桶的个数，意味着至少要循环这么多次，桶的深度是n+1，桶里面就已经放了一个任务，然后将其他的任务往里面填。最终的结果有两种情况，要么是桶子没有满，要么是桶子满了出去。当桶子没有满，则是（桶子个数-1)*桶子容量+最后一个桶子的容量，如果桶子满了，则代表不会出现卡主的情况，满出来的任务，可以直接在桶子之间运行，此时的时间，就是任务的总数。最终结果，取这两种情况下的最大值。

• 回文子串：https://leetcode.cn/problems/palindromic-substrings/

  解法1：DP+暴力，dp定义，一维数组，代表当以第i个字符结尾时，值为回文个数。初始化，只有1个字符，回文个数为1。状态转移，dp[i] = dp[i-1] + 以当前字符串结尾的回文。从i-1开始往前便利，当字符串是这个的时候，判断是否是回文串。结果为dp的最后一个值。

• 最小覆盖子串：https://leetcode.cn/problems/minimum-window-substring/

  解法1：滑动窗口双指针+HashMap，先便利目标字符串，记录到HashMap中，value是出现次数。逐个遍历s，将HashMap中的value--，当HashMap中的值大于0，说明有一个这个字符都匹配，此时n--，当n为0，说明字符串全匹配，此时开始移动第二个指针，第二个指针也从0开始，往i移动，移动过程中，补充HashMap中的value，并且如果value>0，说明此时就没有包含所有的目标字符串，此时就是最短字符，然后继续移动i，继续按照上面的逻辑。

• 戳气球：https://leetcode.cn/problems/burst-balloons/

  解法1：逆向思维的DP，在[i,j]区间内，要想硬币最多，从后往前推导，也就是可以按照往i,j之间，往里面插入气球，计算硬币。这样的好处是可以将大问题划分为小问题，小问题之间不相互影响。组装新数组，将前后两个1插入进去。定义dp，二维数组，代表区间i，j之间，插入一个气球，得到的最大的硬币数量。初始化，计算出有一个数区间的数字，[0,2],[1,3],[2,4],[3,5]，计算这个区间之内，插入一个气球，得到的硬币数量。在[i,j]之间，插入一个气球，硬币最多，则是k从i+1到j-1的max(dp[i][k]+newNums[i]*newNums[k]*newNums[j]+dp[k][j])。这个里面的子系统就是dp[i][k]，子系统的计算，不会影响dp[i][j]。相比计算戳破气球，会涉及到左边界或者右边界的改动，往里面插入的思想更好。最终的结果，即是 dp[0][newLength-1]。

字典树 Trie

字典树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

基本性质：

1. 节点本身不存完整单词；
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
3. 每个节点的所有子节点路径代表的字符都不相同

节点存储额外信息

节点的内部实现

核心思想

Trie树的核心思想是空间换时间。

利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

典型题目

• 实现Tire（前缀树）：https://leetcode.cn/problems/implement-trie-prefix-tree

  解法1：通过数据结构实现。

  数据结构中，定义HashMap或者数组，key是字符，value是前缀树，还定义一个字段设置当前是否是结尾。

  便利过程是先判断是否有子树，如果有，则递归调用子树的逻辑。

• 单词搜索：https://leetcode.cn/problems/word-search/

  解法1：暴力搜索+回溯。先便利数组，找到第一个首字母符合的 [i,j]，然后进行递归回溯，递归中，返回true的条件是 word == ""，如果不是，则说明字符串没有查询完，递归条件是 i >= 0 && i < m && j >= 0 && j < n && board[i][j] == word[0]，如果满足，则将 board[i][j] = '0'，然后四个方向进行递归，如果递归结果为true，则直接返回，如果不为true，将 board[i][j]还原，也就是回溯。

• 单词搜索II：https://leetcode.cn/problems/word-search-ii/

  解法1：暴力解法，先查找字符，然后往四个反向扩散。但是这个解法，在提交后，会超时。

  解法2：由于目标字符串过多，先将目标构建字典树，将所有的字母放到Trie中，进行扩散，然后通过DFS查询目标子串。需要注意的是，字典树的构建，是child下面的字符串是最终字符串，t Tire，如果是a，则是t.child['a'].word = a。便利数组，如果字符在字典树中可以找到，则进入字典树进行DFS，依然是回溯，判断有结果的条件是 tire.word != ""，此时说明字典树中的字符串是结果。

并查集

解决组团、配对问题，判断两个个体是不是在一个集合当中。

并查集的基本操作

• makeSet(s)：建立一个新的并查集，其中包含s个单元素集合。
• unionSet(x,y)：把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并
• find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。

初始化过程：将每个元素指向自身

合并过程：将两个结合的代表结合成一个（可以对比选择小的或者大的元素）

路径压缩

实现并查集

典型问题

• 省份数量：https://leetcode.cn/problems/number-of-provinces/

  解法1：DFS，逐次便利所有的城市，将相邻的城市之间的关联去掉，然后DFS相邻的城市。

  解法2：BFS，逐次便利所有的城市，将相邻的城市放在第二层将要便利的待选城市中，每次便利的城市，都将isConnected设置为0。

  解法3：并查集，逐次将城市插入到并查集中，最终返回并查集的个数。

• 岛屿数量：https://leetcode.cn/problems/number-of-islands/

  解法1：前面使用了DFS，这里使用并查集，将相邻的岛屿，插入到并查集中，最终获取并查集的个数

• 被围绕的区域：https://leetcode.cn/problems/surrounded-regions/

  解法1：DFS，便利所有边界上的O，将这些O标记，最终将所有没有被标记的地方改为X。

  解法2：BFS

  解法3：并查集，将与边界相连的O，与这个O相连的O，都放到并查集中，最终再次便利，如果在并查集中，就改为O，如果不在，则改为X。

高级搜索

初级搜索

1. 朴素搜索，或者叫做暴力搜索

2. 优化方式：不重复（fibonacci）、剪枝（生成括号问题）

3. 搜索方向：

   1. DFS：Deep First Search 深度优先搜索，一般用于判断是否存在某个结果
   2. BFS：Breadth First Search 广度优先搜索，一般用于求出最短或者最优解。

   双向搜索、启发式搜索（通过优先队列，从优先队列中拿到优先元素进行搜索）

高级搜索

剪枝：将状态树中已经处理过的节点减掉。例如fibonacci问题中，将节点缓存起来，然后再计算的时候，就不需要重复计算这个节点。

回溯法

回溯也就是分治+试错，然后回溯。回溯需要注意：1、满足条件，何时返回true。2、递归结束时，回溯之前，需要将状态还原。

典型题目

• 爬楼梯：https://leetcode.cn/problems/climbing-stairs/

  解法1：转换成fibonacci问题，从3开始计算，f(1)=1,f(2)=2,f(n)=f(n-1)+f(n-2)

• 括号生成：https://leetcode.cn/problems/generate-parentheses/

  解法1：DP，定义长度为n的一维数组，代表括号对数是的组成次数。状态转移方程是dp[n] = dp[i] + dp[n-i-1],i从0到n-1。

  解法2：当做2n个格子，使用回溯法，每一个格子进行左括号和右括号的尝试。

• N皇后：https://leetcode.cn/problems/n-queens/

  解法1：回溯，下一层尝试，通过判断列、45度、135度进行剪枝

  推荐解法1（基于C++）：https://leetcode.com/problems/n-queens/solutions/19808/Accepted-4ms-c++-solution-use-backtracking-and-bitmask-easy-understand/

  推荐解法2（基于Python）：https://leetcode.com/problems/n-queens/solutions/19810/Fast-short-and-easy-to-understand-python-solution-11-lines-76ms/

• 有效的数独：https://leetcode.cn/problems/valid-sudoku/description/

  解法1：便利数独中每一个数，便利这个数的同一行、同一列、宫内是否出现一次，这里确定了长度，可以使用数组替代map。

• 解数独：https://leetcode.cn/problems/sudoku-solver/#/description

  解法1：回溯，暴力破解，需要剪枝，将无法放的数字排除。详细来说，就是先便利出需要填的数字，如果没有这个数字，也就是说没有 .，说明已经写完。如果有，则暴力获取这个地方可以填入的数字，依然是数独的规则，获取一排、一列、宫内可以填的数字，依次尝试这个数字，直到返回true，如果返回false，则替换其他的数字，如果所有的数字都试过了，则还原填入的这一格，然后回溯。

双向BFS

例如一个双向连接图，寻找A-L的路

如果是BFS，那么就是先分层，然后扩散

双向BFS，就是从A扩散，从L扩散，同时扩散，相遇的时候就是最短的

典型题目

• 单词接龙：https://leetcode.cn/problems/word-ladder/

  解法1：BFS，多次搜索

  解法2：双向BFS，从头和尾同时BFS，有相交点即为True

启发式搜索 A* Search

再BFS的过程中，POP出一个元素的时候，更加智能，采用有限队列，POP出优先级更高的元素，然后再扩散。

启发式搜索：h(n)，用来评价哪些节点最有希望时一个我们要找的节点，h(n)会返回一个非负实数，也可以认为是从节点n的目标节点路径的估计成本。

启发式函数是一种告知搜索方向的方法，提供了一种明智的方法来猜测哪个邻居结点会导向一个目标。

估价函数:
h(current_state) = distance(current_state, target_state)

典型题目

• 二进制矩阵中的最短路径：https://leetcode.cn/problems/shortest-path-in-binary-matrix/

  解法1：DP

  解法2：BFS，将能到达的点标记成1，然后依次遍历能到达的八个方向的点。

  解法3：A*，更好的扩散方式是斜向下的方向，估价函数是两点之间最小的距离

  A*的推荐解法：https://leetcode.com/problems/shortest-path-in-binary-matrix/solutions/313347/A*-search-in-Python/

• 滑动谜题：https://leetcode.cn/problems/sliding-puzzle/

  解法1：BFS（DFS也可以，但是BFS更优），将所有位置能交换的位置列出来，

• 解数独：https://leetcode.cn/problems/sudoku-solver/

  解法1：暴力，回溯。

位运算

在计算机中，数字表示方式和存储格式都是二进制。

十进制和二进制转换：

4(d): 0100 
8(d): 01000 
5(d): 0101 
6(d): 0110

位运算符

含义	运算符	实例
左移	<<	0011 => 0110
右移	>>	0110 => 0011
按位或	`	`
按位与	&	0011 ——- => 0011 1011
按位取反	~	0011 => 1100
按位异或(相同为零不同为一)	^	0011 ——- => 1000 1011

异或 XOR

相同为0，不同为1，也可用 “不进位加法”来解释。

异或操作的一些特点：

x ^ 0 = x
x ^ 1s = ~x  （1s代表全1）(~x代表取反)
x ^ (~x) = 1s
x ^ x = 0 
c = a ^ b ==>  a ^ c = b,b ^ c = a             // 交换两个数
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c        // associative，相连的

指定位置的位运算(0开始到n位)

1. 将x最右边的n位清零： x &(~0 << n)
2. 获取x的第n位值（0或者1）：(x >> n ) & 1
3. 获取x的第n位的幂值：x & (1 << (n -1 ))
4. 仅将第n位置为1：x|(1 << n)
5. 仅将第n位置为0：x&~(1 << n)
6. 将x最高位至第n位（含）清零：x & ((1 << n) - 1)
7. 将第n位至第0位（含）清零：x & (~((1 << (n + 1)) -1))

位运算要点

• 判断奇偶

  x % 2 == 1 --> (x & 1) == 1
  x % 2 == 0 --> (x & 0) == 0 

• x >> 1 --> x / 2

  y = x / 2  --> y = x >> 1;
  // 例如二分法取中间，可以使用位操作
  mid  = (left + right) / 2 --> mid = (left + right) >> 1;

• y = x&(x - 1)清零最低位的1

• x & -x可以得到最低位的1（负数是取反然后+1）

• x&~x == 0

典型题目

• 位1的个数：https://leetcode.cn/problems/number-of-1-bits/

  解法1：循环n次，不可取

  解法2：向右移动，取模或者与1；或者将1往左移动，与目标数取模，如果等于左移的1，则说明该位有1。

  解法3：当x大于0时，打掉最后的1，循环次数为结果，最右

• 2的幂：https://leetcode.cn/problems/power-of-two/

  解法1：打掉最后一位的1，然后判断是否为0。或者直接判断这个数字是否是幂，就是n&(n-1)==0，说明是2的幂

• 颠倒二进制位：https://leetcode.cn/problems/reverse-bits/

  解法1：用位运算，从0位开始，如果是1，则将第n位的数字移动到对应31-n位。

• N皇后：https://leetcode.cn/problems/n-queens/description/

  解法1：使用位运算取代数组

• N皇后II：https://leetcode.cn/problems/n-queens-ii/description/

  解法1：与N皇后题目一样，只是返回结题次数。

• 比特位计数：https://leetcode.cn/problems/counting-bits/description/

  解法1：DP+位运算

  解法2：位运算，不停地打掉最后一位1，也就是 x &= x - 1

排序算法

排序算法分为两类：

1. 比较类排序

   通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlog(n))，因此也称为非线性时间比较类排序。

2. 非比较类排序

   不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

排序算法分类：

排序算法的时间复杂度

其中，比较重要的是三种 O(nlog(n))的时间复杂度：堆排序、快速排序、归并排序。

排序过程图：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

【简单明了】9种经典排序算法可视化动画：https://www.bilibili.com/video/av25136272/

6分钟看完15种排序算法动画展示：https://www.bilibili.com/video/av63851336/

初级排序 O(n^2)

• 选择排序 Selection Sort

  

  每次找最小值，然后放到待排序数组的起始位置：第1次循环从0开始，找到最小的数字，与位置0互换，第二次循环，从1开始，找到最小的数字，与位置1互换，依次类推

  func selectSort(s []int) {
      for i := 0; i < len(s); i++ {
          for j := i + 1; j < len(s); j++ {
              if s[j] < s[i] {
                  s[i], s[j] = s[j], s[i]
              }
          }
      }
  }

• 插入排序 Insertion Sort

  

  从前到后逐步构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入：第一次循环，从位置1开始，与位置0排序，第二次循环，从位置2开始，与位置1、位置0比较，查询其中，以此类推

  func insertSort(s []int) {
      for i := 1; i < len(s); i++ {
          tmp := s[i]
          j := i
          for ; j >= 0; j-- {
              if tmp > s[j] {
                  break
              }
          }
          copy(s[j+2:i+1], s[j+1:i])
          s[j+1] = tmp
      }
  }

• 希尔排序 Shell Sort

  

  是简单插入排序的改进版，与插入排序不同之处在于，会优先比较距离远的元素。希尔排序又叫做缩小增量排序

  先将队列个数除以2，作为增量因子，间隔增量因子的数进行选择排序；第二遍将增量因子除以2，再次进行插入排序，依次类推，都进行插入排序，直到增量因子等于1

  func shellSort(s []int) {
      for i := len(s) / 2; i > 0; i = i / 2 {
          // 切割每一个分段
          for j := 0; j < i; j++ {
              // golang 使用插入排序不友好，改成使用选择排序，将每一个间隔进行排序
              for m := j; m < len(s); m += i {
                  for n := m + i; n < len(s); n += i {
                      if s[m] > s[n] {
                          s[m], s[n] = s[n], s[m]
                      }
                  }
              }
          }
      }
  }

• 冒泡排序 Bubble Sort

  

  嵌套循环，每次查看相邻的元素如果逆序，则交换：每次选择相邻两个数字排序，将数字大的放在后面，第一次循环之后，最大元素放在最后；下次再从0开始。

高级排序 O(nlog(n))

• 快速排序 Quick Sort

  

  数组取标杆 pivot，将小元素放pivot左边，大元素放右边，然后依次对右边和右边的子数组继续快排；以达到整个序列有序。：

• 归并排序 Merge Sort 分治

  

  可以看作是快排的逆向操作

  1. 把长度为n的输入序列分成两个长度为n/2的子序列
  2. 对这两个子序列分别采用归并排序
  3. 将两个子序列合并成一个最终的排序序列

• 堆排序 Heap Sort

  

  堆插入 O(log(n))，取最大/小值 O(1)

  1. 数组元素依次建立小顶堆
  2. 依次取堆顶元素，并删除

特殊排序 O(n)

• 计数排序 Counting Sort

  

  要求输入的数据必须时有确定范围的整数，将输入的数据值转化为键存储在额外开辟的数组空间中；然后依次把计数大于1的填充回原数组

• 桶排序 Bucket Sort

  

  原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）

• 基数排序 Radix Sort

  

  按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。

典型题目

• 数组的相对排序：https://leetcode.cn/problems/relative-sort-array/

  解法1：hash+排序，其中hash用于区别已经存在的数字，排序是当数字不存在时需要进行升序排序，排序过程方法有很多种，可以是使用堆，也可以用二分法寻找第一个大于本数的index，或者最简单的比较排序，然后copy。

• 有效的字母异位词：https://leetcode.cn/problems/valid-anagram/

  解法1：使用快排，将字符串进行排序

  解法2：使用数组，将字节码作为角标，最终判断数组是否相等

• 合并区间：https://leetcode.cn/problems/merge-intervals/

  解法1：先排序，然后合并

  解法2：一个一个往结果中合并，情况有三种，interval[0] >= res[i][0] && interval[0] <= res[i][1]，interval[1] >= res[i][0] && interval[1] <= res[i][1]，interval[1] >= res[i][1] && interval[0] <= res[i][0]，然后进行递归

• 翻转对：https://leetcode.cn/problems/reverse-pairs/

  解法1：暴力法，两个嵌套循环，时间复杂度是 O(n^2)。这种解决方案会超时

  解法2：归并排序，O(nlog(n))

  解法3：树状数组，O(nlog(n))

高级动态规划

DP顺推

func DP(){
    dp := [][] // 二维情况
    
    for i:=0;i<M;i++ {
        for j = 0;j<M;j++ {	// dp状态方程和递推公式
            dp[i][j] = Function(dp[i][j]...)
        }
    }

    return dp[m][n]
}

DP在处理一些具有重复子问题的场景非常有效

例如：

• 爬楼梯问题

  递归公式：f(n) = f(n - 1) + f(n - 2) , f(1) = 1, f(0) = 0

• 爬格子问题

  递归公式：f(x, y) = f(x-1, y) + f(x, y-1)

• 打家劫舍问题

  状态定义方式：max $ of robbing A[0 -> i]

  递归公式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

  通过多加一个维度，记录偷了还是没偷的状态。

  dp[i][0]状态定义：max $ of robbing A[0 -> i] 且没偷 nums[i]

  dp[i][1]状态定义：max $ of robbing A[0 -> i] 且偷了 nums[i]

  递归公式：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);

  dp[i][1] = dp[i - 1][0] + nums[i];

  这种升维的解法，在高级动态规划的场景中会经常使用到。

• 最小路径和

  dp[i][j]状态的定义: minPath(A[1 -> i][1 -> j])

  递归公式：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + A[i][j]

  以及可以再考虑中间有障碍物的情况

• 股票买卖问题

  统一解决思路：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/。

  状态定义：dp[i][k][0 or 1] (0 <= i <= n-1, 1 <= k <= K)

  i为天数

  k为最多交易次数

  [0,1]为是否持有股票

  状态转移方程

  dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) 
                              max( 选择 rest , 选择 sell )

  解释:今天我没有持有股票，有两种可能:

  1. 我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有;
  2. 我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

  dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) 
                              max( 选择 rest , 选择 buy )

  解释:今天我持有着股票，有两种可能:

  1. 我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票;
  2. 我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

  总结出来，初始状态:

  dp[-1][k][0] = dp[i][0][0] = 0
  dp[-1][k][1] = dp[i][0][1] = -infinity

  状态转移方程:

  dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

解决DP问题的核心是找到状态定义方式，和递归公式。

复杂度提升

1. 状态拥有更多维度（二维、三位、或者更多、甚至需要压缩）
2. 状态方程更加复杂

例如：

• 爬楼梯问题改进

  • 一次可以走1次、2次和3次：解法差不多
  • 每次步伐限定是某几个整数：解法差不多
  • 前后不能走相同的步伐：需要升维，记录当前阶梯是第几步走上来的

• 编辑距离：https://leetcode.cn/problems/edit-distance/

  • 解法1：双端BFS，长度向中间逼近

  • 高级DP：

    如果word1[i]与word2[j]相同，则dp[i][i]=dp[i-1][j-1]

    如果word1[i]与word2[j]不相同，那么 dp[i][j]可以通过

    1. 在 dp[i-1][j-1]的基础上做replace操作达到目的
    2. 在 dp[i-1][j]的基础上做insert操作达到目的
    3. 在 dp[i][j-1]的基础上做delete操作达到目的

    取三者最小情况即可

典型问题

• 使用最小花费爬楼梯：https://leetcode.cn/problems/min-cost-climbing-stairs/

  解法1：DP，定义DP，为爬到这一层的最少花费；从第二层开始遍历；状态转移方程，第i层，可以由i-1层爬过来，也可以从i-2层爬过来，两者取最小值，dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])；最终返回dp最后一个数。

• 最长递增子序列：https://leetcode.cn/problems/longest-increasing-subsequence/

  解法1：DP，dp代表当下序列的最长递增子序列，便利nums时，需要判断之前的dp值，nums[i] > nums[j] && dp[j] > max时，更新最大值，dp为最大值+1，最终结果取最大值。

• 解码方法：https://leetcode.cn/problems/decode-ways/

  解法1：DP，代表当前子字符长度的字符串代表的解码次数，需要注意的是状态转移方程，需要处理的是这个字符是否有二义性，也就是1开头、2开头、0开头。

• 最长有效括号：https://leetcode.cn/problems/longest-valid-parentheses/

  解法1：DP，代表当前字符串长度的最长有效括号长度，状态转移方程，是指右括号结尾，加上左边的符合长度以及做括号，或者左边括号+左边的dp

• 最大矩阵：https://leetcode.cn/problems/maximal-rectangle/

  解法1：数据降维和单调栈，先将二维数据降低到多个一维，然后题目变成计算柱状图中最大的矩形。

  这里需要额外注意计算柱状图的解法：

  1. 使用单调递增栈
  2. 每一个index都会入栈，也会出栈
  3. 出栈的时候，计算面积，因为此时，右边界就是i，高度就是自身的高度，左边界就是新的栈顶，这里需要注意，面积的算法是(i - stack[len(stack)-1]-1) * array[out]，有一个-1
  4. 便利完了之后，还需要处理最终的栈，将栈中所有元素依次出栈，出栈的时候计算面积，计算方式与上面一样，只是右边界变成了len(array)

• 不同的子序列：https://leetcode.cn/problems/distinct-subsequences/

  解法1：dp，二维数组，从空字符串开始，一直到最终两个字符串的结果，当字符相等，dp[i][j] = dp[i-1][j] + dp[i-1][j-1]，当字符不想等，dp[i][j] = dp[i-1][j]

• 赛车：https://leetcode.cn/problems/race-car/

  解法1：DP，记录到target的次数，首先记录一直加速的情况下，可以达到的距离，加速1次，2次，3次。。。到达的距离，这些点的次数最小就是一直加速。继续加速的下一个地方，就是position，如果是终点，则直接返回。开始便利dp，从2开始。状态转移，从第2个位置开始，走到第i个位置时，要么是加速到k+1次之后，往回走，也是重复子问题；要么走到终点找不到往回走的点，此时就是在position位置返回；要么是加速k-1次之后，往回走，往回走0次、1次、2次，然后重复子问题。至于说往回走多少步，就需要便利。最终结果取dp的target位。

字符串

在不同的语言中，字符串属性不同。例如在C#、Python、Java、Golang中，String是不可变的，改变了内容之后，会创建一个新的string。而C++、PHP这些语言中，是可变的。

遍历字符串

var s := "abc"
for i:=0;i<len(s);i++{
  fmt.Println(s[i])
}

字符串判断

var x = "abc"
var y = "abc"
fmt.Println(x == y)

字符串转换大小写

strings.ToUpper(s)
strings.ToLower(s)

字符串转换

ss := []byte(s)
res := string(ss)

字符串判断是否是字母

ss := []byte(s)
unicode.IsLetter(rune(ss[i]))

字符串匹配算法

可以理解为两个字符串，其中一个在另外一个中出现的位置

1. 暴力法，先循环，匹配第一个首字母之后，再继续匹配后面的字母。这个方法不好，可以优化

2. Rabin-Karp算法：使用子串的hash值进行对比加速，去掉第二层的循环，解决的巧妙方法是是使用滑动窗口机制取hash

3. KMP算法：用来找已经匹配上的子串的最大前缀和最大后缀，也就是利用已知短字符串的信息，跳过已经比较过的位置。https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

   https://www.bilibili.com/video/av11866460/?from=search&seid=17425875345653862171

典型问题

• 转换成小写字母：https://leetcode.cn/problems/to-lower-case/

  解法1：直接 strings.ToLower(s)

• 最后一个单词的长度：https://leetcode.cn/problems/length-of-last-word/

  解法1：便利字符串，从尾到头开始便利，记录开始和结尾。需要注意的是，需要判断是否便利到结尾，如果便利到，结果为 start - end，如果没有便利到，结果为 start + 1

• 宝石与石头：https://leetcode.cn/problems/jewels-and-stones/

  解法1：使用数组，记录所有的宝石，代替HashMap，可以节省速度。

• 字符串中的第一个唯一字符：https://leetcode.cn/problems/first-unique-character-in-a-string/

  解法1：双循环，时间复杂度 O(n^2)

  解法2：使用map，找重复，性能上，使用有限数组性能更好

  解法3：字母对应下标统计，找到第一个下标是1的字母

• 字符串转换整数：https://leetcode.cn/problems/string-to-integer-atoi/

  解法1：便利字符串，通过条件判断出现各种符号时的逻辑

• 最长公共前缀：https://leetcode.cn/problems/longest-common-prefix/description/

  解法1：纯暴力，选取第一个字符串为初始共同序列和长度，以此遍历第二个字符串，并且更新长度。

  解法2：行列遍历

  解法3：Trie，将所有字符串放到Trie中

• 反转字符串：https://leetcode.cn/problems/reverse-string/

  解法1：头指针、尾指针转换

• 反转字符串II：https://leetcode.cn/problems/reverse-string-ii/

  解法1：双指针，第一个指针是k的倍数，第二个指针是第一个指针+k，或者到最末尾，将两个指针之间的字符串反转。

• 反转字符串中的单词：https://leetcode.cn/problems/reverse-words-in-a-string/

  解法1：通过空格切割成数组，然后转换，然后组合成string

  解法2：先反转整个字符串，单后单独反转每个单词

• 反转字符串中的单词III：https://leetcode.cn/problems/reverse-words-in-a-string-iii/

  解法1：先切割成单个字符串，反转该字符串。

• 仅仅反转字符串：https://leetcode.cn/problems/reverse-only-letters/

  解法1：双指针，转换为数组，然后跟rune格式对比是否是字母，移动双指针

• 有效的字母异位词：https://leetcode.cn/problems/valid-anagram/

  解法1：使用有限数组记录字母个数，然后对比，相比使用HashMap效率更高

• 字母异位词分组：https://leetcode.cn/problems/group-anagrams/

  解法1：先排序，然后判断是否相等

  解法2：使用有限数组来区分是否是异位词

• 找到字符串中所有字母异位词：https://leetcode.cn/problems/find-all-anagrams-in-a-string/

  解法1：排序，然后判断是否相等在，这种做法会超时

  解法2：滑动窗口+有序数组，使用滑动窗口字符组成的数组是否相等，如果相等，则说明是异位词

• 验证回文串：https://leetcode.cn/problems/valid-palindrome/

  解法1：按照题目意思，先将字符串全部转为小写，然后遍历，通过unicode.IsLetter判断是否为字母，通过unicode.IsDigit判断是否为数字，放入到另一个数组中，最终比较另外一个数组。

• 验证回文串II：https://leetcode.cn/problems/valid-palindrome-ii/

  解法1：暴力，当出现不同的字符，将去掉左边或者右边的字符进行回文串的判断，只要有一个满足，则满足，否则为不满足。

• 最长回文子串：https://leetcode.cn/problems/longest-palindromic-substring/

  解法1：暴力双循环，将所有的子串都进行回文串判断，时间复杂度 O(n^2)

  解法2：DP，DP[i][j]代表字符串i到字符串j是否是回文串，然后循环去判断j+1和i-1是否相等，或者判断i和j+1是否相等，再判断dp[i][j]是否是回文串，或者dp[i+1][j]是否是回文串

• 最长公共子序列：https://leetcode.cn/problems/longest-common-subsequence/

  解法1：DP，二维数组，第一个维度是第一个字符串长度，第二个维度是第二个字符串长度，代表对应两个字符串长度时的最长公共子序列长度。需要注意初始化条件，先初始化dp[0]，然后从i=1开始，并且每次便利i的时候，先确定j=0的情况，之后从j=1开始便利。状态转移方程为

  if text1[i] == text2[j] {
      dp[i][j] = dp[i-1][j-1] + 1
  } else {
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  }

  如果是求最长公共子串，也就是字符串不能打散

  dp[i][j] = dp[i-1][j-1] + 1 (if s1[i-1] == s2[j-1]) 
  else dp[i][j] = 0

• 编辑距离：https://leetcode.cn/problems/edit-distance/

  解法1：嵌套循环，暴力求解，O(n^3)

  解法2：暴力情况下加速，枚举中心，向外面扩张时，字符串相同，O(n^2)

  解法2：DP，二维数组，第一个维度代表第一个字符串的长度，第二个维度代表第二个字符串的长度，值是编辑的距离。

  首先定义二维数组，每个维度的第一个数字代表当一个字符串为空字符串时的编辑距离

  dp := make([][]int, l1+1)

  状态方程：

  如果两个字符相同，例如”ho”和”ro”，则是从”h”到”ro”，”ho”到”r”，”h”到”r”-1之间，取最小1个+1，也就是min（2，,2，1-1）+1

  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]-1) + 1

  如果两个字符串不相同，例如”hor”和”ros”，则是从”ho”到”ros”，”hor”到”ro”，”ho”，”ro”之间，取最小1个+1，也就是min（2，,2，1）+1

  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

  最终结果为dp的最后一位

• 正则表达式匹配：https://leetcode.cn/problems/regular-expression-matching/

  解法1：DP，[i][j]分别代表前后两个元素的角标，需要注意的是，角标从0开始，也就是从空字符串开始，i从0开始，j从1开始。dp状态转移方程，理解的难度在于需要区分j的字符，如果是 *，则有两种情况，要么是匹配0次，将字符打掉，或者如果字符i和字符j匹配，则判断i-1，j是否匹配，只要两者可以匹配，则代表i到j可以匹配；或者不是 *，那么就判断i和j是否匹配，如果匹配，则是i-1和j-1的匹配情况。

  解法思想：https://leetcode.cn/problems/regular-expression-matching/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang-jie-b/

• 不同的子序列：https://leetcode.cn/problems/distinct-subsequences/

  解法1：暴力递归，一般不考虑

  解法2：DP，[i][j]代表s前i字符串可组成t前j字符串组成的最多个数。最好是在前面都加上一个空字符串，这样理解起来会更加简单。dp[0][0]=1，代表当都是空字符串时，可以不删除即可集成。状态转移方程，其实就是判断是否删除i的字符串，当相等时，可以选择删除，也可以选择不删除，如果要删除，则是dp[i-1][j]；如果不删除，则是dp[i-1][j-1]；如果不想等，则只能删除。

  动态方程：

  当 S[j] == T[i], dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
  当 S[j] != T[i], dp[i][j] = dp[i-1][j]

• 字符串中的第一个唯一字符：https://leetcode.cn/problems/first-unique-character-in-a-string/

  解法1：使用hashmap

  解法2：使用有限数组代替HashMap，可以节省时间

• 字符串转换整数：https://leetcode.cn/problems/string-to-integer-atoi/

  解法1：暴力便利，需要注意的是，在有符号或者数字的时候，就不能再获取除了数字之外的其他符号，否则就结束。

• 反转字符串II：https://leetcode.cn/problems/reverse-string-ii/

  解法1：便利字符串的时候反转

• 反转字符串中的单词：https://leetcode.cn/problems/reverse-words-in-a-string/

  解法1：切割成单词，然后反转单词

• 反转字符串中的单词III：https://leetcode.cn/problems/reverse-words-in-a-string-iii/

  解法1：切割成单词之后，反转每一个单词

• 仅仅反转字母：https://leetcode.cn/problems/reverse-only-letters/

  解法1：双指针，出现非单词的时候，指针移动

• 找到字符串中所有字母异位词：https://leetcode.cn/problems/find-all-anagrams-in-a-string/

  解法1：滑动窗口和有限数组，先将目标字符串放到有限数组中，然后开始使用滑动窗口存储到临时有限数组中，比较有限数组。

• 最长回文子串：https://leetcode.cn/problems/longest-palindromic-substring/

  解法1：暴力法，双层循环，然后获取这个字符串的子串是否是回文字符串

  解法2：DP，二维数组，代表从角标i到角标j之间的子串是否是回文字符串，间隔从1到2到最大，如果s[i]==s[j]则需要判断dp[i][j]是否是回文串，如果s[i]!=s[j]，则不是回文串，返回最大的j-i

• 同构字符串：https://leetcode.cn/problems/isomorphic-strings/

  解法1：使用两个有限数组，记录转换的对应关系，以及已经被转换的字符，便利字符串，如果没有转换过，则判断目标字符是否被转换过，如果被转换过，则返回false，否则记录转换关系。如果已经转换过，则判断是否是之前的转换关系，如果不是之前的转换关系，则返回false。

• 验证回文串II：https://leetcode.cn/problems/valid-palindrome-ii/

  解法1：双指针，如果字符相等，则移动指针，如果字符不相等，则删除左边或者右边指针的字符，判断接下来的字符是否是回文串。

• 通配符匹配：https://leetcode.cn/problems/wildcard-matching/

  解法1：DP，二维数组，记录两个长度下是否可以匹配。分情况讨论，如果都是字母，相等，则为dp[i][j]=dp[i-1][j-1]；如果是*，dp[i][0]则是dp[i-1][0]，否则就剩下是?，dp[i][j] = dp[i-1][j] || dp[i][j-1]

  for i := 1; i <= m; i++ {
     dp[i] = make([]bool,n+1)
     if p[i-1] == '*' {
        dp[i][0] = dp[i-1][0]
     }
     for j := 1; j <= n; j++ {
        if unicode.IsLetter(rune(p[i-1])) {
           if p[i-1] == s[j-1] {
              dp[i][j] = dp[i-1][j-1]
           } else {
              dp[i][j] = false
           }
        } else if p[i-1] == '*' {
           dp[i][j] = dp[i-1][j] || dp[i][j-1]
        } else {
           dp[i][j] = dp[i-1][j-1]
        }
     }

• 最长有效括号：https://leetcode.cn/problems/longest-valid-parentheses/

  解法1：动态规划，记录到i角标的字符串的最长有效括号长度字符只能是)才可能是一个有效的字符，然后判断i-1是否是(，是则代表是一个有效括号，然后再判断dp[i-2]的长度，以及有效长度的左边，肯定是一个无效的括号，判断这个无效的括号是否可以跟i组成有效的括号，最终结果返回dp[i-1]

推荐阅读

golang数据结构源码实现

了解时间复杂度

数据结构和算法动态可视化 (Chinese)

Python中最流行的五种相似性度量实现

花花酱 8 Puzzles – Bidirectional A* vs Bidirectional BFS

Self-balancing binary search tree

使用BloomFilter布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重

布隆过滤器(Bloom Filter)的原理和实现

十大经典排序算法（动图演示）

字符串匹配的Boyer-Moore算法

字符串匹配之KMP、BoyerMoore、Sunday算法