Oublie的Hugo博客
文章 标签 分类 关于
Oublie的Hugo博客

Contents

数据结构与算法-labuladong-第三章

oublie included in 数据结构与算法
   3616 words   8 minutes 

本系列笔记为作者在跟随labuladong的算法小抄学习的时候结合golang做的笔记。感谢东哥。另外根据东哥对算法的分类法，将自己平时记的笔记也写到这里面。

第三章：必知必会算法技巧

使用golang做题与使用其他语言做题有一些不同，golang原生的语法中的slice和map支持很多数据结构的简单构造如队列或栈，但是golang并没有提供C++ STL、Java Collection这样丰富的数据结构库，go标准库的container库仅提供了list，ring和heap（优先队列，必须掌握）。这三个库可以实现所有的数据结构但是过于复杂的数据结构实现过程会花很多时间。对于复杂的数据结构可以使用第三方库GODS来提高做题效率，比如红黑树。

解题函数通常分为两部分：数据初始化函数部分和solution函数部分，这两部分也可以内联到解题函数中

递归方法有两种减少空间复杂度的办法，使用全局变量或者在solution函数中定义递归函数。

OI Wiki官网

OI Wiki动态规划

其他算法

雪花算法和uuid

CSDN YmaxU

UUID

形式为8-4-4-4-12的32个16位字符

本地生成，没有网络消耗，入数据库的性能较差

雪花算法

Twitter提出

https://img-blog.csdnimg.cn/6597e40f6b444dc1bc1d4bc1f2b03abf.png

雪花算法为什么不用自增id

博客园 ZeroGirl

数据库自增id在数据库分库分表后，在数据流较大时容易冲突，UUid将机器id也加入进去就不存在这个问题了。

主键应越短越好，无序会造成每一次UUID数据的插入都会对主键地城的b+树进行很大的修改。

二维遍历复用逻辑代码

如果我们在遍历多维数组时不使用方向向量，那么对于每一个方向我们都需要写出单独的逻辑来进行处理，这样可能会出现代码冗余，我们可以使用方向向量加上循环逻辑来避免冗余，实现代码复用，在循环逻辑里面通过循环变量来添加不同方向上单独的逻辑。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

//方向向量
dirs:=[][]int{{0,1},{1,0},{0,-1},{-1,0}}

//循环逻辑
for i,v:=range dirs{
  ...
  if i==n{
    ...
  }
}

当每一个方向都是单独的逻辑的时候可以不使用这种方法。这种方法主要是为了复用相同的逻辑。

减少逻辑复杂度

当逻辑比较复杂时，可能是因为你考虑的逻辑粒度太细了，有的情况不会出现，那么我们就把逻辑粒度变大一点，不会出现的情况不要去管。

比如你寻找链表中点时，如果逻辑粒度太细，慢指针走一步后到了nil怎么办，快指针走一步后到了nil怎么办，快指针走两步后到了nil怎么办。这样就太复杂了。在这个场景下，只会出现慢指针走一步快指针走两步的情况，如果不满足则直接跳出循环即可。这样你的逻辑就只需要考虑这一种情况

1
2
3
4

for slow.Next!=nil&&fast.Next!=nil&&fast.Next.Next!=nil{
  slow=slow.Next
  fast=fast.Next.Next
}

添加虚拟头节点或者虚拟行列统一解题逻辑

对于一维的问题，因为有很多复杂的边界，为了统一解题逻辑，可以添加虚拟头节点，这样就可以忽略头部边界条件，统一解题逻辑，只考虑尾部的边界条件

对于二维的问题，可以在头部添加虚拟行和虚拟列

往后数n个节点可以这样，先将fast和slow都设置为dummy，然后将fast往后走n次即可

前缀和+哈希表解决子数组问题

CSDN 暗夜猎手-大魔王

主要用于解决连续子数组问题

前缀和快速计算子数组的和

通过哈希表优化查询前缀和时间复杂度为O(1)

leetcode 面试题 17.05. 字母与数字

 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

func findLongestSubarray(array []string) []string {
    l:=len(array)
    presum:=make([]int,l+1)
    sum:=0
    for i,v:=range array{
        if unicode.IsDigit(rune(v[0])){
            sum++
        }else{sum--}
        presum[i+1]=sum
    }

    //fmt.Println(presum)
    
    ans:=math.MinInt
    var ansi,ansj int
    m:=make(map[int]int)
    for j,v:=range presum{
        if i,has:=m[v];has{
            if ans<j-i{
                ans=j-i
                ansi=i
                ansj=j
            }
        }else{m[v]=j}
    }

    //fmt.Println(ans,ansi,ansj)

    if ans==math.MinInt{return nil} 
    return array[ansi:ansj]
}

序列中只有一个数字出现k次

CSDN CLthinking 数组中，一个（或者几个）数出现了k次，其余的数都出现了n次

除了一个数字出现k次外，其他数字出现n次

k为偶数，n为奇数

直接对所有值异或

n不可整除k，且n大于k，n不等于1

位运算，记录每个位出现1的次数，当次数mod n后除以k不能除尽时，对于目标数字在该位上为0，否则为1

二进制枚举子集

使用一个整数的二进制来表示问题的状态，每一位是否为1表示元素是否在当前状态。

这样可以直接通过将整数加1来枚举所有问题状态

1
2
3

for mask=1;mask<1<<n;mask++{
  ...
}

bilibili 灵茶山艾府

集合和二进制是一一对应的

要求空间复杂度为O(1)的数组题

为了不占用新的空间，通常这种题需要将数组索引到元素进行一个hash映射，比如41. 缺失的第一个正数，就是实现一个索引到元素的hash函数hash(i)=i+1

枚举子字符串

通常字串由两个端点确定，可以确定左端点位置枚举右端点或者确定右端点位置枚举左端点

查询热门的字符串

查询热门的字符串

字典法，trie树法

复制一倍，断环成链

1
2
3
4

l:=len(ring)
nums:=make([]int,l+l)
copy(nums,ring)
copy(nums[l:],ring)

随机算法

洗牌算法

随机打乱一个数组，将每个数和后面的某个值交换

1
2
3
4

l:=len(s)
for i:=0;i<l;i++{
  s.Swap(i,i+rand.Intn(l-i))
}

蓄水池抽样算法

抽样，将后面的数和前面的数交换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

l:=len(s)
ans:=make([]int,k)
for i:=0;i<k&&i<l;i++{
  ans[i]=s[i]
}

for i:=k;i<l;i++{
  r:=rand.Intn(i)
  if r<k{s.Swap(i,r)}
}

简书 邱simple

leetcode 你的发香散得匆忙

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。

  1. 将第1到第m个数据加入ans数组中。
  2. 从第m+1个数据开始，对每一个数据x随机获取一个1到m+1的数k，当k属于[1,m]时，使用x换出ans[k]
  3. ans数组为最后结果

任何一个数据被选择的概率时m/N

高效寻找素数

素数筛

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

var primes []bool

func countPrimes(n){
  primes=make([]bool,n+1)
  count:=0
  for i:=2;i<=n;i++{primes[i]=true}
  for i:=2;i<=n;i++{
    if primes[i]!=true{continue}
    count++
    tmp:=i
    for tmp<=n{
      primes[tmp]=false
      tmp+=i
    }
  }
  return count
}

高效进行模幂运算

如何处理 mod 运算

(a * b) % k = (a % k)(b % k) % k

如何高效求幂

快速幂

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

var base int

func mypow(a,k int)int{
  if k==0 {return 1}
  if k==1 {return a}

  a %= base
  if k&1==1{
    tmp:=mypow(a,k-1)%base
    return tmp*a
  }else{
    tmp:=mypow(a,k/2)%base
    return tmp*tmp
  }
}

多个关联数组的排序问题

多个数组，他们按下标一一对应，需要你按某一个数组值进行排序

直接新建一个数组index存下标，初始值为index[i]=i

然后使用sort.Slice()对下标数组进行排序，不要去动其他数组

例子：2418. 按身高排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func sortPeople(names []string, heights []int) []string {
    l:=len(heights)
    index:=make([]int,l)
    for i:=range index{index[i]=i}
    sort.Slice(index,func (i,j int)bool{
        return heights[index[i]]>heights[index[j]]
    })
    ans:=make([]string,l)
    for i,v:=range index{
        ans[i]=names[v]
    }
    return ans
}

循环左移和循环右移

循环左移和循环右移：x = (x << n) | (x >> (类型位数 - n))和x = (x >> n) | (x << (类型位数 - n))

确定唯一二叉树

  • 前序（后序）和中序
  • 带nil的各种序

go解题技巧

省略传参定义全局变量

直接在solution函数里面通过定义匿名函数来使用函数内的局部变量，从而避免自己再一次定义全局变量。

1
2
3
4
5
6

func solution(){
  fn:=func (){
    ...
  }
  ...
}

如果要定义递归函数

1
2
3
4
5
6
7
8
9

func solution(){
  var fn func()
  fn=func (){
    ...
    fn()
    ...
  }
  ...
}

工具函数

Max，Min工具函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func Max(s ...int)int{
    tmp:=math.MinInt
    for _,v:=range s{
        if tmp<v{tmp=v}
    }
    return tmp
}

func Min(s ...int)int{
    tmp:=math.MaxInt
    for _,v:=range s{
        if tmp>v{tmp=v}
    }
    return tmp
}

Gcd工具函数

辗转相除法求两数的最小公因数

1
2
3
4
5
6

func Gcd(a,b int)int{
    for a!=0{
        a,b=b%a,a
    }
    return b
}

AbsInt工具函数

防止覆盖math.Abs(float)函数

1
2
3
4

func AbsInt(i int)int{
  if i<0{i=-i}
  return i
}

工具变量

方向向量

1
2
3
4
5
6

var dir=[][]int{
    {1,0},
    {0,1},
    {-1,0},
    {0,-1},
}

尽量使用range写法

go range语法能减少很多代码，并实现和C++ for 三段式一样的效果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

for i:=0;i<len(xxx);i++{
  xxx[i]...
  ...
}

//很明显，当xxx比较长的时候range写法更简介，也更容易理解
for i,v:=range xxx{
  v...
  ...
}

//可以自定义起始点
for i,v:=range xxx[k:]{
  v...
  ...
}

for 三段式主要用于从后面往前遍历的过程，range语法只能进行顺序遍历。

对不存在的key查询

当map的key不存在的时候，它的返回值为这个类型的默认返回值。

由此可以引申出，对于查询kv对后在原来的基础上进行修改的map，可以不判断是否存在直接赋值

比如统计一串数字中每种数字的个数

1
2
3

m:=map[int]int

for _,v := range nums{m[v]++}

数组可以进行等号运算

数组元素可以进行相等比较时，数组也可以进行相等比较，且比较时间复杂度为O（1）

map不能直接比较相等，可以使用reflect.DeepEqual函数进行逐个元素比较，但时间复杂度为O(n)

所以对于一些计数问题，使用数组可以直接判断是否相等，比如leetcode 567. 字符串的排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func checkInclusion(s1 string, s2 string) bool {
    a1,a2:=[256]int{},[256]int{}
    l1,l2:=len(s1),len(s2)
    for _,v:=range s1{a1[v]++}
    for i:=0;i<l1&&i<l2;i++{a2[s2[i]]++}

    for i:=l1;i<l2;i++{
        if a1==a2{return true}
        a2[s2[i]]++
        a2[s2[i-l1]]--
    }

    if a1==a2{return true}

    return false
}

特别注意定义以数组为键的map时使用[xxx]int，xxx必须为确定值，不能为[...]int（定义数组时可以使用）

1

a := map[[26]int]int{}

ACM模式读取字符串输入

非常重要

使用bufio的Reader对象r来读取os.Stdin，通过ReadString(’\n’)方法获取一行字符串

使用fmt包的Fscan系列函数读取r（因为r也实现了io.Reader接口）来扫描值:fmt.Fscanf(r,"%d\n",&a)。推荐仅使用Fscanf函数和Fscan函数，Fscan函数会跳过空白符

上面的方法都可以通过err是否为EOF来判断是否读完输入

fmt包Scan打头的函数都不要用，因为和r一起使用后它的读写指针指向的是哪一个字节是不确定的

反转Slice

1
2
3

sort.SliceStable(s,func(i,j int)bool{
  return i>j
})

定义确定第二维的二维数组的快速方法

1

a:=make([][n]int,m)

详见go学习笔记 定义数组切片

扩容slice到cap

1

s=s[:cap(s)]

摩尔投票算法

知乎 涓涓清泉 数据结构与算法之摩尔投票算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int majorityElement(int[] nums) {
        //摩尔投票
        int count = 0;
        int candidate = nums[0];
        for(int num : nums){
            if(count == 0)
                candidate = num;
            if(candidate == num)
                count++;
            else
                count--; 
        }
        return candidate;
    }
}
Updated on 2022-12-30  views
 labuladong系列
Back | Home
 |