分类 Algorithm 中的文章

多个集合，取交集

| 字数 1138
 | Algorithm
1 Preface 最近在一直采用 go 语言进行项目开发，遇到一个比较有意思的问题： 多个集合，计算交集，哪种计算方法最高效？ 假定集合采用 HashMap 来实现，那么每次查询的时间复杂度为 O(1) 考虑最简单的情况，假定有2个集合A和B，A 的元素个数为2, B 的元素个数为10。 计算A和B的交集有 2 个方案： 方案一：先遍历A，在B中查找是否存在，时间复杂度为 2*O(1) 方案二：时间复杂度为 10*O(1) 于是得出结论： 每次遍历最小的集合去计算交集，总的时间复杂度最小。 2 寻找已有的轮子 由于 go 标准库，并不提供 set 数据结构；先尝试用 google 搜索，fatih/set 出镜率比较高。 于是……

阅读全文

多模匹配之AC自动机

| 字数 3705
 | Algorithm

1 Preface

Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。

AC自动机算法分为3步：(1)构造一棵Trie树，(2)构造Fail指针, (3) 模式匹配过程。

ac-automation

……

阅读全文

双蛋问题(动态规划)

| 字数 2220
 | Algorithm
1 问题描述 有 T 层楼，n个鸡蛋，鸡蛋是相同的，临界楼层是指从某个楼层之上抛下来，都会碎，但从这个楼层之下抛下来，都不会碎。没有碎的鸡蛋可以重复使用。试假设能找到这个临界楼层需要抛投的最少次数。 T层，n个鸡蛋, 总是先要任选一层k, 扔下一个鸡蛋；扔下之后有两个结果： 没碎: 则需要在高层求解 F(T-k, n) 碎了: 则在k层以下求解 F(k-1, n-1) 假设我们在第 k 层扔下第一个鸡蛋，最坏的情况下，我们需要扔多少次： cost(k, T, n) = max{F(T-k, n), F(k-1, n-1)} + 1 我们把每一层，遍历一下最坏情况下所有方案的，最少扔鸡蛋的次数： F(T, n) = min{cost(1, T, n), cost(2, T, n), …, cost(k, T, n), …, cost(T, T, n)} 2 实现 简……

阅读全文

Red Black Tree (01)

| 字数 2039
 | Algorithm
1 BST BST (Binary Search Tree) 二叉搜索树, 在key 恰好有序的时候，会退化成链表。 Conclusion BST 的查询复杂度取决于树的高度, 树的高度即最大比较次数。 一棵具有 N 个 node 的 BST 树高(height)取值范围为：logN ≤ height ≤ N 因此，BST越平衡，在树中查找的时间就越短，连带地插入，删除也会变得效率更高。 红黑树的特征 红黑树（RBT）是节点涂了「颜色」的二分搜索树（BST），借助颜色控制，能够保证在 RBT 中，最长路径(path)不会超过最短路径的2倍（若最短的路径是5，最长的路径至多只能是10），如此，RBT便能够近似地视为平衡，如下图： 上图：……

阅读全文

关于博弈论

| 字数 329
 | Algorithm
大学的时候，我主要钻研的方向就有博弈论。博弈论挺有意思的，而且生活中处处有博弈， 趣味性的小游戏更是如此，比如斗地主，围棋，三国杀，狼人杀。当然如果在和几个朋友一起玩，你可能还需要人物的心理，语气分析来 enhance 你的判断。 博弈论有几个比较经典的表征，一个是对抗性，还有一个是态势(必胜态，必败态) 。态势是可以转移的，一般可以用「状态转移方程」来描述。在学习博弈论的过程中，可采用周伯通的左右互博的方式来思考！ 程序员面试过程中，面试官也会通过一些博弈题来考察一个程序员的思维应变能力，入门级的就是分石子游戏，经典……

阅读全文

背包九讲01-关于常数的优化

| 字数 1903
 | Algorithm
Preface 01背包容量为V，在求能装入物品的获得最大价值dp[V]时，有一个常数优化。（也适用于恰好装满容量为V的01背包问题） 说明:大写字母V表示背包的容量。 关于一个常数优化的问题 前提：如果我们最后只想计算出dp[V]的值，根据动归方程： 1 dp[v]=max(dp[v], dp[v-ci]+wi);//i表示第i个物品 当计算到第n个物品时，我们只需要知道dp[V-cn]的值是多少，也就是说计算第n-1个物品的时候，正常for循环下标 v 应该递减至第n-1件物品的cost，但是下一步得到答案只需要知道dp[V-cn]，我们一旦到达下标 V……

阅读全文

最近文章

分类

友情链接

标签

-Wall(1) 2017(1) 2023(1) about(1) AC自动机(1) algorithm(2) atomic(1) BigData(1) blog(1) busy(1) C++11(3) cache(3) chrome(1) cluster(1) CMake(2) Code Review(1) communication(1) core(1) CPA(1) CPC(1) CPM(1) CPP(8) CPS(1) CPU(1) CR(1) CS(4) Diary(3) Docker(1) DP(1) duck-type(1) epoll(1) etcd(1) Eureka(1) event(1) eventfd(1) Feeling(1) future(2) Gerrit(1) git(5) go(3) go-cmp(1) Golang(1) hardware(1) Hundsun(2) intersection(1) Java(1) kafka(1) lambda(1) Languages(2) Library(6) Life(13) LinkList(1) LogReplay(1) lua(3) MySQL(1) mysqldump(1) narrow cast(1) nullptr(1) OKR(1) oneof(1) OpenTelemetry(1) owners(1) pkg(2) plan(1) plugin(2) plugins(1) poll(1) promise(1) proto3(1) rb-tree(1) Reactive(1) ReadingNotes(7) ready_future(1) rebase(1) recommend(2) recursive(1) reflection(2) Registry Center(1) Release(1) resume(1) rpm(2) seastar(4) select(2) set(1) shared_ptr(1) SIGABRT(1) sql(2) std::thread(1) syscall(1) tcp(1) timeout(1) TodoList(1) Tools(3) tracing(1) Travel(2) unique_ptr(1) unwound stack(1) weak_ptr(1) Web(5) Wireshark(4) Work(9) zeromq(1) zookeeper(2) zsh(1) 个人旅游(1) 企微机器人(1) 优点(1) 全麻(1) 动态规划(1) 在线广告(1) 多模匹配(1) 工作总结(1) 总结(2) 扔鸡蛋问题(1) 文本消息指令(1) 智齿(1) 流量录制回放(1) 用户标签(1) 缺点(1) 群收款(1) 背包问题(1) 香港签注(1) 鼻炎(1)

其它