Posted at 2021-04-26Updated at 2021-05-19 面筋面筋

计算机算法

https://github.com/sunnyandgood/StoreRoom

# 快速排序

# 找第K大数

# 捡石头

# 100盏灯

# 红黑树

# AVL树

# N个数取M个

# 两数之和

哈希法

双指针法：
https://segmentfault.com/a/1190000023552474

不增加额外空间旋转方阵
递归大树乘法
拿苹果图论，顺序限制
二分排序
str归属集合
数字大序数减去小序数的最大值
N个人围圈报数，求顺序
abcd*4=dcba
33.搜索旋转排序数组
dp，n个物品，每个基础价值ai，第k个拿会减去（k-1）*bi的价值，要拿m个使总价值最大（卡了，面试官给了提示过了

背包容量为n，价值a[i]，第k个拿价值减(k - i) * b[i]，物品重量为1
dp为第k个拿物品时的最大价值

dp := make([]int, m + 1)
for i := 0; i < len(items); i++ {
  for j := m; j >= i; i-- {
    dp[j] = max(dp[j], dp[j - 1] + a[i] - i * b[i])
  }
}
return dp[m]

贪心，n个怪物，每个怪物有攻击ai，勇者防御初始为d，每打一只防御+1，防御 < ai的话直接受到bi的伤害。问最优打怪顺序。（没做出来，给了个n=1000的网络流做法，面试官表示n是10w也能贪心做

策略：
如果有能不吃伤害打的，直接打
如果没有能不吃伤害打的，直接打破防最强的

二叉树序列化和反序列化+校验

BFS，层序遍历重建二叉树

行列都是有序的二维数组，查找k是否存在,时间复杂度

二分查找：O(log2（max(m,n)))

有序数组，有2N+1个数，其中N个数成对出现，仅1个数单独出现，找出那个单独出现的数.,时间复杂度

O(log2（2N))二分查找，查找中间位置的数相等值是在左边还是右边？左边则再左子数组继续查找，右边则在右子数组继续查找。

100亿个数求top100,时间复杂度

分组查找或bitmap

100亿个数和100亿个数求交集，时间复杂度

全排列问题，自己找去

hash算法实现(类似crc32或者murmur)，保证随机性和均匀性，减少哈希冲突

考的是hash算法的了解，需要知道一些经典哈希算法实现。

动规 100个球，一次只能拿2-5个，你先拿，我后拿，怎么保证你能拿到最后一个球

一次2-5，去掉先手，最后回合剩余7个即可保证拿到最后一个球。因此，先手拿2个，每一回合保证拿掉球的总数为7，即可。（100-2）/7=14回合。

正整数数组，求和为sum的组合换零钱，1,5,10元都很充足，给你N元去换零钱，多少种换法

算法题给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数，动态规划法。

# 图的最短路径

迪杰斯特拉（Dijkstra）算法

https://www.cxyxiaowu.com/1172.html

# 链表有环

给定一个链表如何判断一个有环

快慢指针相遇

# TOPK

给定一个长度为n的数组，让求第K大的数，我说用维护最小堆，以及最小堆如何维护的

# 回文数

给定一个数字，求是否是回文数？

# 接雨水

# topK，100万，找钱100

# 求第K大的数

# 给定两个无序集合，求其中一个集合中所有元素与另一个集合中所有元素差距的绝对值的最小值（sort+二分）

# 反转链表

# 三数之和

# 链表求和

# 最小覆盖子串

# 最大交换

# 把一个方程式设计成树

# LRU缓存

# 从无限的字符流中, 随机选出 10 个字符

终于要讲到蓄水池采样算法（Reservoir Sampling）了。先说一下算法的过程：

假设数据序列的规模为 𝑛，需要采样的数量的为 𝑘。

首先构建一个可容纳 𝑘 个元素的数组，将序列的前 𝑘 个元素放入数组中。

然后从第 𝑘+1 个元素开始，以 $$\frac{k}{n} $$ 的概率来决定该元素是否被替换到数组中（数组中的元素被替换的概率是相同的）。当遍历完所有元素之后，数组中剩下的元素即为所需采取的样本。

# 最短路径

https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

Dijkstra

S, U

# 数字转中文

https://github.com/Tnze/go.num/blob/master/zh/num.go

http://data.biancheng.net/view/146.html

# 多线程

# 多线程打印ABC

https://www.cnblogs.com/xiaoxi/p/8035725.html

JAVA通过一个ReentrantLock和三个conditon实现
JAVA通过一个锁和一个状态变量来实现

https://www.jianshu.com/p/838465fe2933

GO通过channel管线，A->B->C

package main

import (
  "fmt"
)

func main() {
  N := 100
  chs := make([]chan bool, 0, N)
  for i := 0; i <= N; i++ {
    chs = append(chs, make(chan bool))
  }
  for i := 1; i <= N; i++ {
    go print(i, chs[i-1], chs[i])
  }
  chs[0] <- true
  select {
  case <-chs[N]:
  }
}

func print(n int, i, o chan bool) {
  select {
  case <-i:
  }

  fmt.Println(n)
  o <- true
}

GO通过atmoic

package main

import (
  "fmt"
  "sync"
  "sync/atomic"
)

func main() {
  N := int64(100)
  a := int64(1)
  wg := &sync.WaitGroup{}

  for i := int64(1); i <= N; i++ {
    wg.Add(1)
    go func(i int64) {
      for a != i {
        time.Sleep(time.Microsecond) // 减少竞争
      }
      fmt.Println(i)
      atomic.AddInt64(&a, 1)
      wg.Done()
    }(i)
  }
  wg.Wait()
}

Go不一定打印顺序要和线程一致，先拿先得

package main

import (
  "fmt"
  "sync"
)

func main() {
  N := 100
  a := 0
  l := sync.Mutex{}
  wg := &sync.WaitGroup{}

  for i := 1; i <= N; i++ {
    wg.Add(1)
    go func(i int) {
      l.Lock()
      defer l.Unlock()
      a += 1
      fmt.Println(a)
      wg.Done()
    }(i)
  }
  wg.Wait()
}

C++顺序打印

#include<iostream>
#include<thread>
#include<mutex>

template<typename T, typename... Ts>
std::unique_ptr<T> make_unique(Ts&&... params)
{
    return std::unique_ptr<T>(new T(std::forward<Ts>(params)...));
}

class Solution {
public:
    Solution(int count = 0) : count(count) {}

    void print(int i) {
        std::unique_lock<std::mutex> l(m);
        count++;
        std::cout << count << std::endl;
    }
private:
  std::mutex m;
  int count;
};

int main(int argc, char** argv) {
    auto s(std::make_unique<Solution>());
    int N = 3;
    for (int i = 0; i < N; ++i) {
        std::thread t(&Solution::print, s.get(), i);
        t.join();
    }
    return 0;
}

# 轮流打印

#include<iostream>
#include<thread>
#include<mutex>
#include<vector>

const int N = 3;

class Solution {
public:
    Solution(int count = 0) : count(count) {}

    void print(int num) {

        for (int i = 0; i < repeat; i++) {
            std::unique_lock<std::mutex> l(m);
            cvar.wait(l, [num, this] { return num == count; });
            std::cout << num << std::endl;
            count += 1;
            count %= 3;
            l.unlock();
            cvar.notify_all();
        }
    }
private:
    std::mutex m;
    int count;
    std::condition_variable cvar;
    const int repeat = 3;
};

int main(int argc, char** argv) {
    auto s(std::make_unique<Solution>());
    std::vector<std::thread> threads;
    for (int i = 0; i < N; ++i) {
        threads.emplace_back(&Solution::print, s.get(), i);
    }

    std::for_each(threads.begin(), threads.end(), std::mem_fn(&std::thread::join));

    return 0;
}

# 统计词频

排序数组，统计词频

非排序数组统计词频

无限长数组统计词频

package main

import (
  "fmt"
  "runtime"
  "sync"
)

func main() {
  a := []int{1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
  size := 3
  N := 3
  inter := make(chan map[int]int, 10)

  wg := &sync.WaitGroup{}
  for i := 0; i < len(a); i += size {
    wg.Add(1)
    l := i
    r := i + size
    if r > len(a) {
      r = len(a)
    }
    go count(a, l, r, inter, wg)
  }

  wg.Wait()

  for i := 0; i < N; i++ {
    wg.Add(1)
    go reduce(inter, wg)
  }

  wg.Wait()

  out := <-inter
  if len(inter) > 0 {
    for m := range inter {
      fmt.Println(m)
      fmt.Println("go:", runtime.NumGoroutine())
      for k, v := range m {
        fmt.Println(k)
        out[k] = v
      }
      if len(inter) == 0 {
        close(inter)
      }
    }
  }

  fmt.Println(out)
}

func count(a []int, l, r int, o chan map[int]int, wg *sync.WaitGroup) {
  m := make(map[int]int)
  for i := l; i < r; i++ {
    m[a[i]]++
  }
  o <- m
  wg.Done()
}

func reduce(i chan map[int]int, wg *sync.WaitGroup) {
  for {
    if len(i) <= 1 {
      wg.Done()
      return
    }
    select {
    case map1 := <-i:
      if len(map1) == 0 {
        continue
      }
      map2 := <-i
      if len(map2) == 0 {
        i <- map1
      }
      for k, v := range map2 {
        map1[k] = v
      }
      i <- map1
    }
  }
}

# 生产者消费者

#include <iostream>
#include <thread>
#include <mutex>
#include <queue>
#include <memory>

const int N = 100;

class Channel
{
public:
    Channel(int count = 0) : count(count) {}

    void produce(int i)
    {
        std::unique_lock<std::mutex> l(m);
        pvar.wait(l, [this]
                  { return q.size() < count; });
        std::cout << " <- " << i << std::endl;
        q.push(i);

        cvar.notify_all();
    }

    void consume()
    {
        std::unique_lock<std::mutex> l(m);
        cvar.wait(l, [this]
                  { return q.size() != 0; });
        std::cout << q.front() << " <- " << std::endl;
        q.pop();
        pvar.notify_all();
    }

    int size()
    {
        return q.size();
    }

private:
    std::mutex m;
    int count;
    std::condition_variable pvar, cvar;
    std::queue<int> q;
};

int main(int argc, char **argv)
{
    auto s(std::make_unique<Channel>(10));
    std::vector<std::thread> threads;
    for (int i = 0; i < N; ++i)
    {
        threads.emplace_back(&Channel::produce, s.get(), i);
        threads.emplace_back(&Channel::consume, s.get());
    }

    std::for_each(threads.begin(), threads.end(), std::mem_fn(&std::thread::join));

    return 0;
}

# 读者写者


#include <iostream>
//std::unique_lock
#include <mutex> 
#include <shared_mutex>
#include <thread>
 
class ThreadSafeCounter {
public:
  ThreadSafeCounter() = default;
 
  // 多个线程/读者能同时读计数器的值。
  unsigned int get() const {
    std::shared_lock<std::shared_mutex> lock(mutex_);
    return value_;
  }
 
  // 只有一个线程/写者能增加/写线程的值。
  void increment() {
    std::unique_lock<std::shared_mutex> lock(mutex_);
    value_++;
  }
 
  // 只有一个线程/写者能重置/写线程的值。
  void reset() {
    std::unique_lock<std::shared_mutex> lock(mutex_);
    value_ = 0;
  }
 
private:
  mutable std::shared_mutex mutex_;
  unsigned int value_ = 0;

# 计算阶乘

# 计算N次方

func pow(x, n int) int {
    ret := 1 // 结果初始为0次方的值，整数0次方为1。如果是矩阵，则为单元矩阵。
    for n != 0 {
        if n%2 != 0 {
            ret = ret * x
        }
        n /= 2
        x = x * x
    }
    return ret
}

func main() {
    x := pow(2, 10) // 2^10
    println(x)      // 1024
}

# 排序数组去重，还是哈希表去重

多线程情况下，排序数组可以分段并行，哈希表会冲突

单线程情况下，数组cache空间局部性更好

Previous post: 算法基础 - 贪心法 Next post: 烤面筋 - 通用

吹拉弹唱