1.链表与邻接表

一般笔试的时候不会采用动态链表的情况。

用数组模拟单链表：静态链表

面试题中单链表用的最多的是邻接表，其最主要的应用是存储图和树
e[i]用来存储节点i的值，ne[i]表示节点i的next指针是多少

模拟链表的基本操作

用数组模拟双链表

双链表用的最多的是优化某些问题

e[i]用来储存节点i的值，l[i]表示节点i的左指针，r[i]表示节点i的右指针

用数组模拟链表的增删查改和指针表示链表的增删查改过程是一致的，只不过前者改变数组对应的存储值，后者改变指针的指向
基本操作

2.栈与队列

用数组模拟栈和队列

栈

栈的特性是后进先出
这是二叉树的前序非递归遍历，其中的栈就是用数组实现的

func preorderTraversal(root *TreeNode) []int {
    var ans []int
    var stack []*TreeNode
    if root == nil {
        return ans
    }

    for root != nil || len(stack) > 0 {
        if root!= nil{
            ans = append(ans,root.Val)
            stack = append(stack,root)
            root = root.Left
        }else {
            num := len(stack)
            root = stack[num-1]
            stack = stack[:num-1]
            root = root.Right
        }
    }

    return ans
}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数


如果存在这样的关系，那么可以将ax从栈中删除，所以栈中最后剩下的序列就是单调序列

每来一个新的数ai，判断栈顶元素与ai的大小，如果ai比栈顶元素小或者等于，可以将栈顶元素删除

tt := 0 
for i:= 1 ; i < n ; i++{
    for tt > 0 &&check(q[tt],i){
        tt--
    }
    tt++
    stack[tt]=i
}

例题：

//单调栈的经典用法，找每个数左边第一个比它小的数以及右边第一个比它小的数
//这里面栈存储的是数组的下标
func largestRectangleArea(heights []int) int {
    n := len(heights)
    var stack1,stack2 []int
    var left []int = make([]int,n)
    var right []int = make([]int,n)
    res := 0
    for i := 0 ; i < n ; i++{
        for len(stack1) > 0 && heights[stack1[len(stack1)-1]] >= heights[i] {
            stack1 = stack1[:len(stack1)-1]
        }  
        if len(stack1) == 0 {
            left[i] = -1
        }else{
            left[i] = stack1[len(stack1)-1]
        }
        stack1 = append(stack1,i)
    }
    for i := n-1 ; i >=0 ; i-- {
        for len(stack2) > 0 && heights[stack2[len(stack2)-1]] >= heights[i] {
            stack2 = stack2[:len(stack2)-1]
        }
        if len(stack2) == 0 {
            right[i] = n
        }else{
            right[i] = stack2[len(stack2)-1]
        }
        stack2 = append(stack2,i)
    }
    for i := 0 ; i < n ; i ++{
        res = max(res,heights[i]*(right[i]-left[i]-1))
    }
    return res

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

队列

队列的特性是先进先出
这是二叉树的层序遍历，其中使用的队列就是用数组实现的

func levelOrder(root *TreeNode) [][]int {
    var res [][]int
    if root == nil {
        return res
    }

    var queue []*TreeNode
    queue = append(queue,root)

    for i:= 0 ; len(queue) > 0 ; i++{
        p := []*TreeNode{}
        res = append(res,[]int{})
        for j:= 0 ; j < len(queue) ; j++{
            root = queue[j]
            res[i] = append(res[i],root.Val)
            if root.Left != nil{
                p = append(p,root.Left)
            }
            if root.Right != nil{
                p = append(p,root.Right)
            }
        }
        queue = p
    }

    return res
}

单调队列

常见模型：找出滑动窗口中的最大值/最小值

hh := 0
tt := -1
for i := 0 ; i < n ; i++{
    for hh<=tt && check_out(q[hh]){
        hh++ //判断队头是否滑出窗口
    }
    for hh<=tt && check(q[tt],i){
        tt--
    }
    tt++
    q[tt]=i
}

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

//队列里存储的是下标，队头元素什么时候出队，当队头元素不在[i-k+1,i]这个区间内时

func maxSlidingWindow(nums []int, k int) []int {
    var queue []int = make([]int,len(nums))
    var res []int
    if len(nums) == 0 {
        return res
    }
    head := 0
    tail := -1
    for i := 0 ; i < len(nums) ; i++ {
        //判断队头是否滑出窗口
        if head <= tail && i-k+1 > queue[head] {
            head++
        } 
        for head <= tail && nums[queue[tail]] <= nums[i] {
            tail--
        }
        tail++
        queue[tail] = i 
        if i >= k - 1 {
            res = append(res,nums[queue[head]])
        }

    }
    return res
}

3.KMP

给定一个 S 字符串和一个 p 字符串，在 S 字符串中找出 p 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

KMP的朴素算法-暴力算法
其中S是主串，p是子串（模式串）

我们要寻找当 当前不匹配时，子串需要移动的最小距离
next[i]表示以i为结尾的后缀和从头开始的前缀相等，且这个长度最长也即p[0,j]=p[i-j,i],所以next[i]表示，当前i匹配失败，将退回到哪个位置继续匹配

试图和当前字符S[i]进行匹配的是p[j+1]

func strStr(haystack string, needle string) int {
    n:=len(haystack)//主串
    m:=len(needle)//模式串（子串）
    if (m==0){
        return 0
    }
    if (n<m){
        return -1
    }
    next:=compute_next(needle)

    q:=0
    for i:=0;i<n;i++ {
        for q>0 && haystack[i]!=needle[q]{
            q=next[q-1]
        }
        if ( haystack[i]==needle[q]){
            q++
        }
        if (q==m){
            return i+1-m;
        }
    }
    return -1

}

func compute_next( pattern string) []int {
    n:=len(pattern)
    next:=make([]int,n)
    k:=0
    for q:=1;q<n;q++ {
        for k>0 && ( pattern[k]!=pattern[q]){
            k=next[k-1];
        }
        if ( pattern[k]==pattern[q]){
            k++;
        }
        next[q]=k;
    }
    return next
}