跳转至

每日必练

零 技巧性算法（面试常问）

  • 十大排序：应用情况，稳定性，基准数，时间复杂度
  • 两个变量实现值的交换：a= a+b,b = a - b,a = a-b 缺点是值会溢出
  • 百万数据的TopK
  • 洗牌算法：怎样进行随机洗牌，各个位置概率均等。
  • 快速判断2的幂次方（典型位运算）：n&n-1=0

一.写题技巧

1.1 优化手段

  • 多重循环优化：存哈希表

1.2 字符串处理

  • 字符串s分割,string t = s.substr(l,r-l+1);注意后面是长度
  • 从含字母的字符串中分割数字：遍历，num = num* 10 + s{i} - 1;

1.3 ACM输入

  • 忽略空格读一整行数据 abc ab cccc 
    string s;
getline(cin,s);
isstringstream str(s);      //字符串流
while(str >> s)             //根据空格进行分割
{
}
  • 单行挨着读 aabb00 
    string s;
getline(cin,s);
遍历该字符串
  • 忽略换行符 
    cin.ignore();
  • 解释器 如insert 1 7 
    cin >> command;
if(command == "insert")
    cin >> a >> b;

1.4 哨兵技巧

  • 正整数，哨兵置0
  • 非负整数，哨兵为-1或n

1.5 反转思维

求出问题的另一面，再用总和减去

1.6 浮点数转字符串

二. 数组

  • [ ] 二分查找
  • [ ] 双指针-快慢指针
  • [ ] 左右指针
  • [ ] 滑动窗口
    • [ ] 子串覆盖：哈希+匹配计数
    • [ ] 单调队列：
  • [ ] 前缀和数组：数据索引第一位一定要存0，有时并非全部都要记，一个计全部综合，一个计符合目标的前缀和就够了。
  • [ ] 差分数组
  • [ ] 环形数组技巧（TODO）
  • [ ] 二维数组遍历（TODO）
  • [ ] 十大排序算法（非常重要）

回文串

  • 验证回文串：传入左右范围，双指针遍历。适合查找以某个下标开头后的回文串
  • 子回文串：从中间往外扩，适合以最少复杂度找到回文串。

三 链表

  • [ ] 双指针--合并/分解链表
  • [ ] 双指针--快慢指针
  • [ ] 双指针--交错指针
  • [ ] 判断回文单链表
  • [ ]

四 二叉树（多叉树）

3. Trie树设计

五. 回溯类型(所有题思想一致)

前提：（任意顺序）要求所有的多个答案（路径），路径深 做法：回溯函数-- 1.路径达到条件装入答案返回。 1. 循环路径节点：装入路径，递归，退回路径。 N皇后和数独问题：

六 二分查找类型

关键词：有序，部分有序 前提：有序，单目标 做法：循环迭代-找中点，比较，选择下一个遍历的容器部分。 - 注意判断为目标左右区域的条件是什么

七 贪心

  • 最简单-贪心选择：局部最优解可直接推导出全局最优解
  • 最优子结构：已经把所有子问题的最优解都求出来了，然后可以推导出原问题最优解
  • 举反例。最难的其实就是子问题推导出原问题，可以考虑举反例 跳跃游戏类型（每一格存储自己能跳下的距离）：最优子结构（当前最远距离） 区间调度类型： 1.记录区间：map存（首）尾 2.遍历首部，（最优子结构）记录当前最远端，直到抵达当前最远端，视为一个区间。 股票买卖（买、卖、保持）：遍历，顺便更新minprice

八 栈

单调栈（并非单调队列那种新的数据结构）

  • 只解决特定类型问题：上一个最小元素，下一个最大元素
  • 面积问题（找到最小/最大的边界+哨兵技巧（-1和n+1））
  • 注意：入栈和出栈是分别对应左右边界的

九 图论

1. 岛屿问题:

DFS/BFS，并查集--遍历图，遇到岛屿，用DFS，BFS将其全部“淹没”，置为海水（grid（x）（y）== 0），不需要维护visited数组

2. 环检测与拓补排序

环检测：构建邻接表，path的bool数组记录路径，visited的bool数组优化避免重复遍历 拓补排序：判无环，后序遍历倒转

3.名流问题

4.二分图判断算法

5. 并查集

6. Dijkstra

作用：用来解决单源最短路径问题，可以获得所有最短路径，路径大小>=0。

本质是BFS，队列换成优先队列，添加一个备忘录distTo记录每个可达节点的最短路径权重和。 细节很多： - 建图：可以建成稀疏nxn的图，优化的话就是将==值和目标点==一起存到==pair==里变成稠密图。 - State记录节点、深度（其实就是个pair），并重载比较运算符 - dist初始化为INT_MAX，并且disr【Start】初始化为1 - 如果dist变小了，再去将下一个节点装入优先队列。

7.A*

也是BFS改造，优先队列为开节点，闭合节点为（路径+父节点），确保构成通路。

数据结构实现

最小栈，单调队列，最值数据结构

  • 这种类型的问题，多半需要辅助的数据结构
  • 最小栈：建立辅助栈记录最值

Trie树（字典树，前缀树）设计

功能：前序搜索功能、前缀相同不单独占据内存、通配符、字典序遍历键。本质是多叉树 思想：树枝为键，节点为值（如果有的话）。本质其实就是256叉树或者26叉树。每个键结束末尾要打个标记用于检索键值。

动态规划

1. 股票买卖问题（一天买下，另一天卖出）

dp[i][k][0 or 1]=max(buy,sell,rest)

  • 三种状态：买、卖、无操作
  • 三维dp：当前下标，最大购买次数，是否持有 通解是动态规划，不过部分题也有贪心思路的做法。

2.子序列类型

  • 对于两个字符串求子序列的问题，都是用两个指针 i 和 j 分别在两个字符串上移动，大概率是动态规划思路。

2.1 编辑距离（多决策求最佳问题）

  • 以编辑距离为例：主要分为插、删、改以及相等（跳过）。
  • 决策选择：怎么选都很难确定最终情况，那就全都要。
  • dp的初始化：0的部分代表一边字符串为空，所以起码要删除所有的字符才行

2.2

2.3.LCS最长公共子序列

俩种情况：s1和s2字符串做比较 - 相等：则当前dp的值=前面i-1和j-1的dp值+1 - 不相等：说明要么i-1不在子序列里，要么j-1不在子序列里，取他们当前dp的最大值咯。

3.背包类型

4.动态规划玩游戏

技巧性题目

1.数学技巧之位运算

- 1-只有一个只出现一次的数字，其他都为两个，找到TA：利用a^ a=0的特性。

2.数学技巧之找众数（多数元素）

  • 类似于电子，众数为正电，其他数为负电：利用nums计算当前电荷，正负相抵。
  • 设置一个目标数，一个计数器。为当前目标就+1，否则-1。如果到了0，说明前面的数都在前面数组里都还不算正数，重新设置