DSA.dataStructure.algorithm 数据结构

作者: daydaygo | 来源:发表于2024-08-25 13:20 被阅读0次

IOS开发_数据结构
py基础
思维导图之数据结构+算法
数据结构与算法分析：大纲]
数据结构：数组
数据结构—概述
OVS 源码分析整理
01. 数据结构与算法绪论
数据结构与算法 - 查找
C#之数据结构（上）

思路: 枚举/暴力(规范/协议)->子问题/状态压缩/剪枝->最优解
- 多画图
方法
- dimension.维度 scope.范围 classify.分类 field.domain.领域 boundary.边界 interval.区间: 左闭(0/1开始)右开? 边界=Layer层=规范=协议= $O(mn) > O(m+n)$ 环/假溢出? 连续?
- 协=2+参与者议=行为约定与规范
- 中间层 -> 问题复杂度 $M*N \rightarrow M+N$ -> 社会分工越来越细, 各行各业制定标准
- 有序.sort
  - 二分法: 快/慢左/右 order.正/逆/倒序前/后; 二分->四分
- 递归=base+recursive=栈优化=循环/尾递归
pl
- py: array bisect collections sortedcontainers(Map TreeMap)
- java: HashMap HashSet
name.命名.参数: ans/res ij kv pqr mn-len-Node Tmp Flag-Fn-Func Left-Right Start-End First-Last Fast-Slow small-big high-mid-low Row-Cloumn-Box visited
ADT.abstractDataType DFA.DeterministicFiniteAutomaton.有限自动机面试编程.PREP.parametersReturnExamplePseudocode.IO.TDD

DS

存储=链式+顺序逻辑=线性(arr/link/stack)+非线性(tree/graph) op=CRUD.Retrieve.查 traversal.遍历=iteration.迭代+recursion.递归 RandomAccess.随机访问 SequentialAccess.顺序访问
arr.array.数组.线性表 vec.vector.向量.顺序线性表 slice.切片 list.列表 prefixSum.前缀和.连续问题
- 空间压缩环形数组.取模
- mat.matrix.二维.棋盘状态 symmetricMatrix.对称矩阵 sparseMatrix.稀疏矩阵三维.魔方类游戏
stack.栈 LIFO pop.push DFS
- op: polishNotation.波兰表达式.前缀.中缀.后缀括号匹配.栈匹配栈实现队列
- monotoneStack.单调栈: 下一个大于/小于边界-哨兵法; 广义栈
queue.队列 FIFO.FistInFirstOut front/back enqueue/dequeue BFS
- monotonicQueue.单调队列
- deque.双端队列.pool
- ring.环.循环.固定长度缓冲区读写.io缓冲区
linkedList.链表
- 画图迭代操作(head+pre+cur+next) 固定头结点.表头节点.哑结点dummyNode.哨兵节点
- op: reverse.反转中值奇偶快慢相交.环
- singleLinkedList.单链表 doubleLinkedList.双向链表 LinearList.线性链表 staticList.静态链表
hash.哈希.散列 hashTable dict.字典 map.映射 kv.keyValuePair.键值对 symbolTable.符号表 assocArray.关联数组
- hashFunction.散列函数解决碰撞.填充因子 conflict.冲突.抽屉原理 separateChain.链地址法.拉链法开放地址=linearProbing线性探查+线性补偿探测+随机探测
- rehash 渐进式rehash
- consistentHash.一致性hash DHT.分布式hash
  - uint32环 node(真实节点)/replica(虚拟节点) 顺时针查找第一个
  - judge: balance monotonous.单调 spread load
- MurmurHash: 规律输入依然可以给出很好的随机分布+计算速度
- xxHash: https://xxhash.com
string.字符串匹配
- KMP FSM.FiniteStateMachine.有限状态机模式匹配有限状态机 BM BM-KMP BF RK
- approximate/fuzzy.模糊匹配 suffixArr.后缀数组
- trie.字典树.前缀树动态路由.查找.词频统计路由=restful/fixed/regex/custom/auto/annotation+param.:id+method.GET+namespace.v1
  - radixTree.基数树
tree 度.根.叶.兄弟.高度无序.有序二叉.多叉 大部分算法技巧本质上都是树的遍历问题
- binaryTree.二叉树满 complete.完全 Serialization.序列化
  - op: 遍历(pre前.in中.after后层次.bfs) create(前序+中序树状数组) depth(min max) lca.leastCommonAncestors.最近公共祖先
  - BST.binarySearchTree.搜索.查找 -> binarySortTree.退化为链表的性能问题 -> Balance.平衡/AVL/RBT.redBlackTree.红黑树 -> 区间树.区间查询.区间重叠判断-> 线段树.叶子节点区间范围之和.区间重叠判断.统计学(大区间+小区间)
  - binaryIndexedTree.二叉索引树.树状数组 segmentTree.线段树.区间树 HuffmanTree.哈夫曼树 b+.数据库索引
  - doubleChainedTree.双链树
- 多叉: B.文件管理.数据库.多路+有序 B+.终端节点处理不同 2-3 2-3-4
- Huffman_coding.霍夫曼编码 merkleTree.哈希二叉树.区块链
- k-dTree(游戏中碰撞检测 4维/8维) DOM/HTML/AST/XML
set hashSet treeSet DisjointSet
map hashMap treeMap
heap.堆
- array实现: 极大堆/极小堆/极大极小堆/优先级队列.priorityQueue.os线程调度双端堆.Deap d叉堆
- tree实现: binaryHeap.二叉堆左堆扁堆二项式堆 fibHeap pairingHeap.配对堆
find.查找 unionFind.并查集
- 路径压缩+秩优化实现每个集合元素个数+最大集合元素个数实现并查集是一种思想特殊节点.地图/砖块/网格
- hash binarySortTree.排序二叉树 AVL/B/B+/B*/AA/RBT/splay/DCT/R binaryHeap
- skipList.跳表
graph.图 graphTheory.图论 seen-vis-visted
- 权向入度出度连通/强连通 DirectedGraph有向图 DAG.DirectedAcyclicGraph.有向无环图.任务编排
- op: 遍历(dfs bfs) create.邻接表-稀疏.邻接矩阵-矩阵运算
- algo: dijkstra.最短路径.非负权边 Bellman-Ford最短路径.负权边 Floyd 最小生成树(Kruskal&Prim) 二分图(染色法) 拓扑排序 fordFulkerson最大流 A*搜索.A星寻路.启发式搜索图匹配网络流
other: LFU LRU.LRU-K.LRU-2Q 分桶

algo

NP完全: bigO.时间/空间所有组合必须考虑所有情况序列.旅行商问题集合.广播台集合
math.bit位操作
binarySearch.二分查找思路很简单细节是魔鬼闭区间+边界检查
- 经典解法.low<=high 4个变种.^= $= ^>= $<= 最大化最小化问题
sort.排序
- 类型: 交换(冒泡快排.qsort.quickSort.pdqsort) 插入(直插 shell希尔) 选择(简选 quickSelectSort.快选堆) mergeSort.归并(二路多路) 基数计数(计数信息=排序结果) 桶线性自省间接
- 外部: k路归并败者树最佳归并树
暴力=枚举=打表法状态/不重不漏/效率
- 排列组合子集映射 $2^n$
DC.分治
- RC.ReduceConquer.减治.小问题只解决一个大问题就解决了: 二分查找 randomizedSelect.随机选择
DP.动态规划=状态+状态转移方程+边界情况
- 暴力递归->带memo递归->DP状态->memo状态压缩->状态间关系 memo.备忘录->status.状态压缩 trim.剪枝最优解子问题离散&不依赖其他子问题网格
- 最优二叉搜索树
  - Knapsack.背包 subKnapsack.子集背包 completeknapsack.完全背包 01knapsack
  - subsequence.子序列 LCS.LongestCommonSubsequence.最长公共子序列
greedy.贪心.贪婪每步最优解>全局最优 scheduleProblem.调度问题 jumpGame.跳跃游戏 gameProblem.博弈问题
backtracking.回溯迷宫
search.搜索
- 枚举.迷宫 DFS.deepFirstSearch.深度优先 BFS.BreadthFirstSearch.seen 启发式搜索
分支定界法
大数据
- BF.bloomFilter.布隆过滤器: 概率型数据结构概率型算法替代.Cuckoo/Hyperloglog
- ai
security安全: bcrypt.目前最安全密码散列 sha.局部不敏感=局部变化散列值完全不同 simhash.局部敏感.网页是否搜集+论文是否抄袭+版权检查
other
- LB.LoadBalance: rand roundRobin.取余 weightRoundRobin p2c
- limit: 滑动窗口(频率/并发上限) tokenBucket(令牌桶瞬时流量)
- timingWheel.时间轮: 延迟操作
- 2point.双指针: 快慢指针+左右指针
  - SlidingWindow.滑动窗口: 连续问题快慢指针/固定间距指针
精选题解: 字典序列删除前缀和二叉树序列化最长上升子序列最长公共子序列最大子序列和股票买卖打家劫舍
topk: qsort全局排序.分治->冒泡.局部排序->heap->rc减治.rs随机选择.只排序k个元素的区
InvertedIndex倒排索引: 搜索引擎
epoll: readBlackTree+doubleList

bit Bit_numbering Category:Binary_arithmetic

进制进制转换: bin oct hex(n&15 n>>=4 n%16 n//=16) 11 0b11 011 0x11
- binary 二进制; decimal 十进制; hex 十六进制; octal 8进制
int
- uint8 byte ascii: chr ord 'a'^' '='A' 'A'|' '='a' 'a'&'_'='A'
- signed/unsigned 机器数&真值 trueForm.原码反码=除符号位按位取反 Complement.补码=反码+1
- str2int int2str
op &.and |.or ^.xor ~.not << >> 算术右移逻辑右移.最高位补0 移位与除法奇偶n&1 n>>1 %2 末位n&1
- 幂等律a|a=a 交换律a|b=b|a 结合律a&b&c=a&(b&c) 分配律a&(b|c)=(a&b)|(a&c)
- 德摩根~(a&b)=(~a)&(~b) 取反-a=~(a-1) 异或^ i^0=i i^i=0 4i^(4i+1)^(4i+2)^(4i+3)=0
- lsb.最低有效位消除n&(n-1) 只保留n&-n n&(~(n-1)) msb oneCnt
- add divide hammingDistance
bitmap.位图.bitset 32/64k,v:=n/64,n%64 str2biti|=1<<(v-'a')
dp.状态压缩: 只有2种状态&n<=20
mask 右n位清零x&(~0<<n) n位bit(x>>n)&1 n位幂值x&(1>>(n-1)) n位设为1.n1x|(1<<n) n位设为0.n0x&(~(1<<n))

math

进制转换阶乘素数快速幂杨辉三角裴蜀定理斜率 fib
最大公约数: 辗转相除法=欧几里得算法更相减损术(九章算术)-位运算(奇偶)
排列组合 $C_{n+m-2}^{m-1}$
约瑟夫环dp[i]=(dp[i-1]+m)%i
快速幂求余 $x^a \odot p=(x^2 \odot p)^{a/2} \odot p$
算术几何不等式 $\dfrac{n_1+n_2+...+n_a}{a}>=\sqrt[a]{n_1n_2...n_a}$
公式推导 $f(n)=\dfrac{1}{n}x1.0+\dfrac{1}{n}x0.0+\dfrac{1}{n}\sum\limits_{i=2}^{n-1}f(n-i+1)$

// 减法变加法
a + ^(b-1) // a-b

leetcode

leetcode lintcode acmcoder.赛码 Hackerrank 牛客网 codetop.企业题库 codewars vjudge geeksforgeeks oi-wiki.信息奥林匹克 the-algorithms javascript-algorithms
LeetCode题解src/go: // id https://leetcode.cn/problems/{title} 题解=tag+思路 题解.多语言代码块.java [] 专题/模板
- 题解: 自己读题 -> 15分钟还没思路 -> 看题解 -> 完全不会才看代码/记笔记 -> coding/debug
- lucifer.力扣加加.91algo.leetcode-solution
- labuladong/fucking-algorithm 算法有套路.算法小抄
- halfrost/LeetCode-go leetcode-cookbook 阿里霜神
- LeetCodeAnimation LeetCode101.c++.谷歌师兄刷题笔记

leetbook

位运算与数学
数据结构
- 数组和字符串数组类算法
  - 基本概念+操作方式; 二维数组; 字符串概念+特性; KMP算法; 双指针
- 链表
- 哈希表查找表类算法
- 队列和栈
- 二叉树二叉搜索树前缀树 N叉树
- 图解数据结构
算法
- 初级算法中级算法高级算法
- 递归二分查找
AI数学基础
漫画算法

leetcode tool

leetcode web
- problemset题库
  - 分类: 算法剑指offer 程序员面试金典6 hot100 top200
  - 标签tag: 学了一个知识后, 按标签刷, 快速巩固: bit-manipulation.位运算
  - session.设置-进度管理
- circle社区: 题解
- code题目页面: 模拟面试快捷键(⌘' ⌘↩︎) 使用上一次的编辑还原 playground调试测试用例可视化收藏中心
leetcode app
- 摇一摇切换中英文描述/随机一题
- 学习分析
help
- plus: 付费精选题目和内容; 企业题库; 企业模拟面试(免费可随机); 题目热度; 极速判题; playground(调试)
  - 模拟面试: 1-3题, 30-90分钟
- 竞赛: 报名 -> AC +1分, 每次错误 +5min 罚时
- 个人主页: 做题进度 收藏/笔记/积分订单账号
- 技术问题
  - 各语言对应版本和环境: phpinfo() => 7.2
  - 全局变量和类内静态变量 -> 手动初始化
  - stdout 打印: debug + 增加耗时
  - 二叉树序列化
  - timeout.leetcode的锅 TLE.TimeLimitExceeded.代码的锅
力扣刷题插件.lucifer
- 题解模板/查看题解
- 代码: 一键复制所有测试用例禅定模式
- 代码模板: 前缀和(一维二维) 二分法(baisc+4变种) BFS(是否带层信息) 堆(最小堆) 滑动窗口(固定窗口/可变窗口) 回溯(标准笛卡尔积优化) 前缀树并查集(是否带权) 线段树(区间和计数)
- 数据结构可视化
- 复杂度速查
- 学习路线: 动态规划树链表二分
如何刷题
- 题解: 自己读题 -> 15分钟还没思路 -> 看题解 -> 完全不会才看代码/记笔记 -> coding/debug
- 按专题(tag)刷 -> 模板/笔记/多题同解
  - 构建知识体系/框架/套路
- 广度优先而非深度(死磕某一个知识)
- 掌握编程语言
- 模拟面试: 时间观念+一次AC
- 训练目标: AC数量 AC速度 AC通过率竞赛排名前100 beats-CPU/mem-100%
  - bug-free: 基础数据结构+算法形成肌肉记忆单测+调试
- code: 命名name(简洁&一致性) 小心全局变量提交后查看排名->分段->看100%的代码直接使用系统api
- debug: 批量测试数据可视化
- 锁定使用哪种算法: 记忆/题感/暴力解(暴力+剪枝大力出奇迹) 关键字限制条件+复杂度速查分治思维
九章算法
- 企业题库领扣lintcode题库（Java c++ py）
- 免费课：ai 企业题库/面试算法
- 发现：求职面试学习笔记上班摸鱼
- 消息
- 我：发布收藏学分学习记录

leetcode.tag

Fundamentals 基本
- Array 数组
- Matrix 矩阵
- String 字符串
- StringMatching 字符串匹配
- Sorting 排序
- BucketSort 桶排序
- CountingSort 计数排序
- RadixSort 基数排序
- Simulation 模拟
- Enumeration 枚举
Algorithms 算法
- DynamicProgramming 动态规划
- Depth-FirstSearch 深度优先搜索
- Breadth-FirstSearch 广度优先搜索
- Greedy 贪心
- BinarySearch 二分查找
- Backtracking 回溯
- Recursion 递归
- DivideandConquer 分治
- Memoization 记忆化搜索
- Quickselect 快速选择
- MergeSort 归并排序
CommonDataStructures 基础数据结构
- HashTable 哈希表
- Tree 树
- BinaryTree 二叉树
- Stack 栈
- Heap(PriorityQueue) 堆（优先队列）
- Graph 图
- LinkedList 链表
- BinarySearchTree 二叉搜索树
- MonotonicStack 单调栈
- Queue 队列
- OrderedSet 有序集合
- TopologicalSort 拓扑排序
- ShortestPath 最短路
- Doubly-LinkedList 双向链表
- MonotonicQueue 单调队列
- MinimumSpanningTree 最小生成树
- StronglyConnectedComponent 强连通分量
- EulerianCircuit 欧拉回路
- BiconnectedComponent 双连通分量
AdvancedDataStructures 高级数据结构
- UnionFind 并查集
- Trie 字典树
- SegmentTree 线段树
- BinaryIndexedTree 树状数组
- SuffixArray 后缀数组
Techniques 技巧
- TwoPointers 双指针
- BitManipulation 位运算
- SlidingWindow 滑动窗口
- PrefixSum 前缀和
- Counting 计数
- Bitmask 状态压缩
- HashFunction 哈希函数
- RollingHash 滚动哈希
- LineSweep 扫描线
Math 数学
- Math 数学
- Geometry 几何
- GameTheory 博弈
- Randomized 随机化
- Combinatorics 组合数学
- NumberTheory 数论
- ProbabilityandStatistics 概率与统计
- ReservoirSampling 水塘抽样
- RejectionSampling 拒绝采样
Other 其他
- Database 数据库
- Design 设计
- DataStream 数据流
- Interactive 交互
- Brainteaser 脑筋急转弯
- Iterator 迭代器
- Concurrency 多线程
- Shell

# fetch/xhr grphql questionTagTypeWithTags
a = json.loads(s)
a = a['data']['questionTagTypeWithTags']
for i in a:
    print("-", i['name'].replace(" ", ""), i['transName'])
    for j in i['tagRelation']:
        j = j['tag']
        print("  -", j['name'].replace(" ", ""), j['nameTranslated'])

mark

example.业务: 人羊狼草过河.状态图正则/订单状态.自动机 api设计.二部图线段切割法-抢红包
- React hooks: not magic, just arrays
可视化 https://visualgo.net https://algorithm-visualizer.org https://www.bigocheatsheet.com https://www.cs.usfca.edu/~galles/visualization
浙江大学.左程云

算法帝国算法之美
算法通关之路 2021.8 LeetCode题解
剑指offer 名企面试官精讲典型编程题专项突破版; 2021.8
大话数据结构; 程杰 2020.12
CTCI Cracking the coding interview 程序员面试金典6 2019.9; 程序员面试金典ed5 2013.11
漫画算法: 小灰的算法之旅; 2019.5
程序员的算法趣题
- 2 2023.5; 内存优化+动态规划
- 1 2017.7
grokking algorithms 算法图解; 2017.3; 入门佳作
妙趣横生的算法; C++语言实现 2014.10; C语言实现2 2015.3
算法的乐趣; 王晓华.orbit 2015.3
Programming Pearls 编程珠玑; 2014.12
挑战程序设计竞赛ed2; 2013.7
数据结构与算法分析 java语言描述; 邓俊辉 2013
Introduction to Algorithms 算法导论 ed3; 2012.12; 2层, 一层培养算法思维+使用现有的结论, 一层深入算法的数学证明(这层可选择); MIT算法导论.bilibili
TAOCP theArtOfComputerProgramming 计算机程序设计艺术 ed3; 1基本算法 2半数值算法 3排序与查找 4A组合算法
Algorithms 算法ed4; 2012.10; 阅读计划.ituring-wechat
程序员实用算法 2009.9
编程之美微软技术面试心得; 刘铁锋 2008.3

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。-- Leigh Caldwell
Haskell 等函数式编程语言就没有循环，因此你只能使用递归来编写这样的函数。如果你对递归有深入的认识，函数式编程语言学习起来将更加容易。如果你喜欢递归或者想学习一门新语言，可以研究一下 Haskell
数据结构是典型的面向对象思维算法是典型的面对过程思维
学习算法是非常有趣和令人激动的; 但是算法, 就是解决问题时的那份「优雅」.
算法4特征.Knuth: 确定有穷可行 IO; 程序=算法+数据结构; 问题的数学模型->IO->算法
算法与解释: 清单.算法的生活化解读算法自身是没有任何企图的.算法不是道德主体.可接受vs不可接受不同表达方式.解释算法一切皆有可能vs无限可能透明性.可计算.可判断.可靠.安全
算法与现实: 书写符号.字典查找/加减法打孔卡片制表机.鼓浪屿风琴博物馆 data.gov