8. 字符串转换整数(atoi)
- 题目链接
自动机
思路
字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。
因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：
我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s'。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s' 的表格即可解决题目中的问题。
算法
-
本题可以建立如下图所示的自动机：
image.png
状态表（略）
接下来编程部分就非常简单了：我们只需要把状态转换表抄进代码即可。
另外自动机也需要记录当前已经输入的数字，只要在 s' 为 in_number 时，更新我们输入的数字，即可最终得到输入的数字。
代码
class Automaton {
string state = "start";
unordered_map<string, vector<string>> table = {
{"start", {"start", "signed", "in_number", "end"}},
{"signed", {"end", "end", "in_number", "end"}},
{"in_number", {"end", "end", "in_number", "end"}},
{"end", {"end", "end", "end", "end"}}
};
int get_col(char c) {
if (isspace(c)) return 0;
if (c == '+' or c == '-') return 1;
if (isdigit(c)) return 2;
return 3;
}
public:
int sign = 1;
long long ans = 0;
void get(char c) {
state = table[state][get_col(c)];
if (state == "in_number") {
ans = ans * 10 + c - '0';
ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
}
else if (state == "signed")
sign = c == '+' ? 1 : -1;
}
};
class Solution {
public:
int myAtoi(string str) {
Automaton automaton;
for (char c : str)
automaton.get(c);
return automaton.sign * automaton.ans;
}
};
403. 青蛙过河
- 题目链接
- 二维数组初始化
vector<vector<int>> dp(n, vector<int>(n));
07. 传递信息
- 题目链接
- DFS
- 等价于在有向图中寻找从节点 0 到节点 n-1的长度为 k 的路径数，同一条路径可以重复经过同一个节点。
- 从节点 0 出发做深度优先搜索，每一步记录当前所在的节点以及经过的轮数，当经过 k 轮时，如果位于节点 n-1，则将方案数加 1。搜索结束之后，即可得到总的方案数。
预处理
- 可以对传信息的关系进行预处理，使用列表存储有向边的关系，即可在 O(1)O(1) 的时间内得到特定节点的相邻节点（即可以沿着有向边一步到达的节点）。
- BFS
- 从节点 0 出发做广度优先搜索，当遍历到 k层时，如果位于节点 n-1，则将方案数加 1。搜索结束之后，即可得到总的方案数。
- 动态规划
- 定义动态规划的状态dp[i][j] 为经过i 轮传递到编号j 的玩家的方案数，其中0≤i≤k，0≤j<n。
- 由于从编号 0的玩家开始传递，当i=0 时，一定位于编号0 的玩家，不会传递到其他玩家。
