求最小公约数
模版cpp版本 123int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);} python版本 12def gcd(a: int, b: int) -> int: return a if b == 0 else gcd(b, a % b); 补充求最小公倍数 123in...
最小栈
发表于
本文字数：
831
阅读时长 ≈
2 分钟
题目描述155 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取...
拓扑排序
基本步骤 创建一个indegree数组，用于记录各个节点的入度情况。以入度为0的节点作为拓扑排序的起点。 将起点压入队列中。 取队头元素，如果没有visited过，则visited[cur] = true。如果存在重复visited，则说明成环。 处理各边，依次对相邻节点的入度值-1，将入度为0的节点压入队列中 代码实现1234567891011121314...
字典树的定义和代码模版
字典树的定义和使用场景 定义 每个样本，从头结点开始，根据字符或者前缀数字构建出来的树，称之为前缀树 使用场景 当需要根据前缀信息查询时，可以使用字典树 字典树的实现用类描述最经典的描述，但是对于字符种类过多的情况，难以处理 1234567891011121314151617181920212223242526272829303132333435363738...
使用master公式分析递归的时间复杂度
适用场景所有子问题规模相同的递归才能用master公式 公式介绍T(n) = a * T(n/b) + O(n^c), 其中a, b, c都是常数, a为执行了几次相同规模的子问题，b为子问题的规模，O(n^c)为递归问题外的其他时间复杂度 如果log(b, a) < c 复杂度为O(n^c) 如果log(b, a) > c 复杂度为O(n^lo...