Golang通用题解模板 | Khaos‘s Blog

type

status

date

slug

summary

📝 主旨内容

算法题常用方法


math.MaxInt
sort.Ints()
sort.Slice(arr_struct,func (next,front){
	return arr_struct[next]<arr_struct[front]
})
fmt.Scanf("%c \\n",&choice)

arr:=make([][]int,5)
for i := range arr{
	arr[i] = make([]int, 3)
}

KMP


func kmp(S string, T string) bool {
	n, m := len(S), len(T)
	next := make([]int, n)
	next[0] = 0
	for i, l := 1, 0; i < n; {
		if S[i] == S[l] {  //相同
			l++
			next[i] = l
			i++
		} else { //不相同
			if l != 0 {  //已有相同前缀
				l = next[l-1]
			} else {    //无，0
				next[i] = 0
				i++
			}
		}
	}
	fmt.Println(next)
	for i, j := 0, 0; i < m; {
		//i遍历母串，j遍历子串
		if T[i] == S[j] {
			//如果当前字符相同，就一起向后遍历
			i++
			j++
		} else {
			if j == 0 {
				i++
			} else {
				j = next[j-1]
			}
			//如果当前字符不相同，母串指针不动，子串指针回到上一个相同的地方
		}
		//如果j==n了，说明子串遍历完了，因此返回真，提前结束
		if j == n {
			fmt.Println(i - n)
			return true
		}
	}
	return false
}

next数组思路：

首先创建一个长度为n的数组next，并将其第一个元素初始化为0。

在循环中，变量i从1开始遍历字符串S。

判断S[i]是否与S[l]相等，其中l表示上一次匹配成功的索引位置。如果相等，说明S[i]可以接在上一个匹配序列的后面，因此更新l和next[i]。然后将i加1，继续向后匹配。

如果S[i]与S[l]不相等，说明当前匹配失败。此时我们需要回溯到已经匹配成功的序列中去尝试寻找更短的前缀子串，以便继续匹配。具体做法是利用next数组，将l跳到next[l-1]处继续匹配，直到l=0或者匹配成功。

当l=0时，说明已经无法继续匹配了，只能更新next[i]为0，然后将i加1，继续向后匹配。

最终得到的next数组就是字符串S的部分匹配表，可以用于进行字符串匹配操作。

二分查找

简单模板


func TFCZ(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

题目

旋转后的数组中查找


func search(nums []int, target int) int {
    n := len(nums)
    if n == 0 {
        return -1
    }
    if n == 1 {
        if nums[0] == target {
            return 0
        } else {
            return -1
        }
    }
    left, right := 0, n-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }
        if nums[0] > nums[mid] {
            if target <= nums[n-1] && target > nums[mid] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        } else {
            if target >= nums[0] && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
    }
    return -1
}

回溯

模板

回溯如果不能重复可以加个visitd的boolean数组判断


class Solution {
    List<String> 结果 = new ArrayList();
    public List<String> 结果函数(结果函数参数) {
        定义路径
        回溯(路径，选择列表);
        return 结果;
    }
    public void 回溯(路径，选择列表){
        if(满足结束条件) {
            结果.add(路径);
            return ;
        }
        for(选择判断循环)
            做选择
            回溯(路径，选择列表);
            撤销选择
        }
    }
}

动态规划

模板

题目


package main
import (
    "math"
)

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        min := math.MaxInt32
        for j := 1; j*j <= i; j++ {
            min = minInt(min, dp[i-j*j])
        }
        dp[i] = min + 1
    }
    return dp[n]
}

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

栈


package main
func solve( s string ) int {
    i:=0
    var helper func(string)int
    helper = func (s string) int{
        sign := byte('+')
        num := 0
        bytes := []byte(s)
        stack := []int{}
        for i < len(bytes){
            b:=s[i]
            i++
            if isDigit(b){
                num = num * 10 + int(b-'0')
            }
            if b == '('{
                num = helper(s)
            } 
            if !isDigit(b) && b != ' ' || i == len(bytes){
                switch sign{
                case '+':
                    stack = append(stack,num)
                case '-':
                    stack = append(stack,-num)
                case '*':
                    stack[len(stack)-1]*=num
                case '/':
                    stack[len(stack)-1]/=num
                }
                sign = b
                num = 0
            }
            if b==')'{
                break
            }
        }
        return sum(stack)     
    }
    return helper(s)
}
func isDigit(b byte)bool{
    return b>='0' && b<='9'
} 
func sum(stack []int)int{
    s:=0
    for _,num := range stack{
        s+=num
    }
    return s
}

将每个元素的符号区别开，合并。

DFS

BFS


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

func BFS(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    array := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        array = append(array, node.Val)
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return array
}

双指针


/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

贪心算法


func canJump(nums []int) bool {
  n := len(nums)
  right := 0
  for i := 0; i < n; i++ {
    if i <= right {
      right = max(right, i+nums[i])
      if right >= n-1 {
        return true
      }
    }
  }
  return false
}

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

排序算法

快速排序

方式1


func QuickSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	flag := arr[0]
	left, right := []int{}, []int{}
	for i := 1; i < len(arr); i++ {
		if arr[i] < flag {
			left = append(left, arr[i])
		} else {
			right = append(right, arr[i])
		}
	}
	left = QuickSort(left)
	right = QuickSort(right)
	sorted := append(append(left, flag), right...)
	return sorted
}

方式2


func quickSort(arr []int, start, end int) {
    if start < end {
        i, j := start, end
        key := arr[(start+end)/2]
        for i <= j {
            for arr[i] < key {
                i++
            }
            for arr[j] > key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }

        if start < j {
            quickSort(arr, start, j)
        }
        if end > i {
            quickSort(arr, i, end)
        }
    }
}

非递归


package main

import "fmt"

func quickSort(arr []int) {
    if len(arr) <= 1 {
        return
    }

    stack := make([]int, len(arr))
    top := -1
    top++
    stack[top] = 0
    top++
    stack[top] = len(arr) - 1

    for top >= 0 {
        end := stack[top]
        top--
        start := stack[top]
        top--

        pivotIndex := partition(arr, start, end)

        if pivotIndex-1 > start {
            top++
            stack[top] = start
            top++
            stack[top] = pivotIndex - 1
        }

        if pivotIndex+1 < end {
            top++
            stack[top] = pivotIndex + 1
            top++
            stack[top] = end
        }
    }
}

func partition(arr []int, start int, end int) int {
    pivot := arr[end]
    i := start - 1

    for j := start; j < end; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }

    arr[i+1], arr[end] = arr[end], arr[i+1]

    return i + 1
}

func main() {
    arr := []int{7, 2, 1, 6, 8, 5, 3, 4}
    fmt.Println("Before sorting:", arr)
    quickSort(arr)
    fmt.Println("After sorting:", arr)
}

快速排序和归并排序是两种常见的排序算法。它们都是按照相同的思路进行排序，即分而治之，将原问题分解成若干个规模更小的子问题进行解决。但是，它们的实现方式有一些不同。

快速排序的基本思路是，首先选择一个枢纽元素，然后将数组中的其他元素按照大小关系分成两部分，其中比枢纽元素小的元素放在左边，比枢纽元素大的元素放在右边。然后对左右两部分分别递归地调用快速排序，直到每个子序列只包含一个元素。最后将所有子序列合并起来，即可得到一个有序的序列。

归并排序的基本思路是，首先将数组中的元素分成两个子序列，然后对两个子序列分别递归地调用归并排序，直到每个子序列只包含一个元素。然后将所有子序列合并起来，从两个子序列中逐一比较每个元素的大小，并将较小的元素放入新的序列中。最后将所有子序列合并起来，即可得到一个有序的序列。

快速排序和归并排序的主要区别在于排序过程中的操作方式不同。快速排序是在排序的过程中对数组进行原地的分区操作，通过交换元素的位置来实现排序。而归并排序则是通过比较两个子序列的元素大小来实现排序，它不会对原数组进行修改，而是将排序的结果保存在新的序列中。

快速排序的时间复杂度为 O(nlog n)，空间复杂度为 O(log n)，其中 n 是数组的长度。归并排序的时间复杂度也为 O(nlog n)，空间复杂度为 O(n)。

二叉树

二叉树前中后序遍历

递归版本


package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
*/
var pre = make([]int, 0)
var min = make([]int, 0)
var post = make([]int, 0)
func threeOrders( root *TreeNode ) [][]int {
    // write code here
    var res [][]int
    preOrder(root)
    midOrder(root)
    backOrder(root)
    res = append(res,pre)
    res = append(res,min)
    res = append(res,post)
    return res

}

func preOrder(root *TreeNode){
    if root == nil{
        return
    }
    pre = append(pre, root.Val)
    preOrder(root.Left)    
    preOrder(root.Right)
}

func midOrder(root *TreeNode) {
    if root == nil{
        return
    }
    midOrder(root.Left)    
    min = append(min, root.Val)
    midOrder(root.Right)
}
func backOrder(root *TreeNode) (res []int){
    if root == nil{
        return
    }
    backOrder(root.Left)    
    backOrder(root.Right)
    post = append(post, root.Val)
    return
}

非递归


func (root *TreeNode) preorder() []int{       //非递归前序遍历
	res:=[]int{}
	if root==nil{
		return res
	}
	stack:=[]*TreeNode{}           //定义一个栈储存节点信息
	for root!=nil || len(stack)!=0{
		if root!=nil{
			res=append(res,root.data)
			stack=append(stack,root)        
			root=root.Lchild
		}else{
			root=stack[len(stack)-1]
			stack=stack[:len(stack)-1]
			root=root.Rchild
		}
	}
	return res
}

func (root *TreeNode) inorder()[]int{
	res:=[]int{}
	if root==nil{
		return res
	}
	stack:=[]*TreeNode{}
	for root!=nil || len(stack)!=0{
		if root!=nil{
			stack=append(stack,root)
			root=root.Lchild
		}else{
			root=stack[len(stack)-1]
			res=append(res,root.data)
			stack=stack[:len(stack)-1]
			root=root.Rchild
		}
	}
	return res
}

func postorderTraversal(root *TreeNode) []int {
    var res []int
    var stack []*TreeNode
    var last *TreeNode
    for root != nil || len(stack) > 0 {
        // 左子树入栈
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        // 取出栈顶元素
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if top.Right == nil || top.Right == last {
            // 如果top没有右子树或者右子树已经被访问过了，则输出top
            res = append(res, top.Val)
            last = top
        } else {
            // 否则，按照右子树、左子树的顺序把right、left入栈
            stack = append(stack, top)
            root = top.Right
        }
    }

    return res
}

图

哈希表


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

import "math"

func detectCycle(head *ListNode) *ListNode {
    set := make(map[*ListNode]struct{})
    for head != nil {
        if _, ok := set[head]; ok {
            return head
        }
        set[head] = struct{}{}
        head = head.Next
    }
    return nil
}

其他

快速选择


func quickSelect(nums []int, k int) int {
    pivot := nums[0]
    left := []int{}
    right := []int{}

    for _, num := range nums[1:] {
        if num < pivot {
            left = append(left, num)
        } else {
            right = append(right, num)
        }
    }

    if k <= len(right) {
        return quickSelect(right, k)
    } else if k > len(nums) - len(left) {
        return quickSelect(left, k - (len(nums) - len(left)))
    } else {
        return pivot
    }
}

LRU


type LRUCache struct {
    cap int
    ll *list.List
    cache map[int]*list.Element
}
type entry struct{
    key,value int
}


func Constructor(capacity int) LRUCache {
    return LRUCache{
        cap: capacity,
        ll: list.New(),
        cache: make(map[int]*list.Element),
    }
}


func (this *LRUCache) Get(key int) int {
    ele,ok:= this.cache[key]
    if ok{
        this.ll.MoveToFront(ele)
        kv := ele.Value.(*entry)
        return kv.value
        
    }else{
        return -1
    }
}

func (this *LRUCache) Put(key int, value int)  {
    if ele,ok:=this.cache[key];ok{
        this.ll.MoveToFront(ele)
        kv := ele.Value.(*entry)
        kv.value = value
    }else{
        ele := this.ll.PushFront(&entry{key,value})
        this.cache[key] = ele
    }
    if len(this.cache)>this.cap{
        this.removeOldest()
    }

}


func (this *LRUCache) removeOldest()  {
    ele := this.ll.Back()
    if ele!=nil{
        this.ll.Remove(ele)
        kv := ele.Value.(*entry)
        delete(this.cache,kv.key)
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

头插法


package main

type ListNode struct {
    Val  int
    Next *ListNode
}

/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    // write code here
    dummp := &ListNode{Next: head}
    pre := dummp
    for i := 1; i < m; i++ {
        pre = pre.Next
    }
    cur := pre.Next
    for i := m; i < n; i++ {
        temp := cur.Next
        cur.Next = temp.Next
        temp.Next = pre.Next
        pre.Next = temp
    }

    return dummp.Next
}

🤗 总结归纳

总结文章的内容

📎 参考文章

一些引用

引用文章

💡

有关Notion安装或者使用上的问题，欢迎您在底部评论区留言，一起交流~