线段树（Segment Tree）是一种二叉搜索树，与区间树相似，他将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶子节点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 O(logN)。而未优化的空间复杂度为 2N ，实际应用时一般还要开 4N 的数组以免越界，因此有时需要离散化让空间压缩。 —— 百度百科*
2023/2/21大约 5 分钟
树状数组（英语：Binary Indexed Tree）又称为二元索引树，由 Fenwick 于 1994年发明，故又称为 Fenwick 树，其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和、区间和。它支持在 O(logn) 的时间复杂度内得到任意前缀和和区间和，同时支持在 O(logn) 的时间复杂度内动态修改单点的值，空间复杂度为 O(n)。 —— wikipedia
树状数组中的精妙操作 —— lowbit（int x）
借助于位运算的lowbit操作（获取整数二进制表示最低位的1），树状数组得以实现其精妙的功能，其精妙之处请看下文。
2023/2/21大约 4 分钟
基本结构
字典树，即 Trie 树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引 擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
基本性质
1.结点本身不存完整单词；
2.从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；
3.每个结点的所有子结点路径代表的字符都不相同。
核心思想
Trie 树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
2021/3/18大约 3 分钟
递归
通过函数体来进行的循环
通过参数进行传递变量 Python递归模板：
def recursion(level, param1, param2, ...):
#recursion terminator
if level > MAX_LEVEL:
process_result
return
#process logic current level
process(level, data...)
#drill down
self.recursion(level + 1, p1, ...)
#reverse the current level status if needed
2021/3/18大约 1 分钟
动态规划
不同路径2状态转移方程
//i,j > 0
dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
2021/3/18小于 1 分钟
一、位运算
运算符及含义
| 运算符 | 含义 |
|---|---|
| << | 左移 |
| >> | 右移 |
| >>> | 无符号右移 |
| & | 按位与 |
| | | 按位或 |
| ~ | 按位取反 |
| ^ | 按位异或 |
2021/3/18大约 4 分钟
动态规划
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）
共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解
关键点
1.最优子结构
2.定义状态空间
3.DP方程
2021/3/18小于 1 分钟
深度优先搜索DFS
递归模板
visited = set()
def dfs(node, visited):
# terminator
if node in visited:
return
visited.add(node)
# process current node here.
...
for next_node in node.children():
if next_node not in visited:
dfs(next_node, visited)
2021/3/18大约 1 分钟
数组 Array
在内存中开辟出的一块连续空间
| 操作 | 复杂度 |
|---|---|
| 查找 | O(1) |
| 插入 | O(n) |
| 删除 | O(n) |
| prepend | O(1) |
| append | O(1) |
2021/3/16大约 1 分钟
题目如下：
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example 1:
Input: 6
Output: true
Explanation: 6 = 2 × 3
Example 2:
Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2
Example 3:
Input: 14
Output: false
Explanation: 14 is not ugly since it includes another prime factor 7.
Note:
1.1 is typically treated as an ugly number.
2.Input is within the 32-bit signed integer range: [−231, 231 − 1].
2020/3/16小于 1 分钟