unsplash.com/@peterlaster
一些关于 C++ 语法的记录。
题目是:
力扣的示例代码确实是精准面向面试的,里面很多写作的风格还是很值得学习的。
我自己照着思路敲了一遍,并且附上了注释。
// dijkstra 求 dist 数组
// 根据 dist[i] - dist[j] == g[i][j] 为边建有向图
// 在这个有向图上用 DP 找 0 点到 n-1 点的路线数量
class Solution {
private:
static constexpr int mod = 1000000007; // private
public:
const int MOD = 1e9 + 7;
int countPaths(int n, vector<vector<int>>& roads) {
vector<vector<long long>> dist(n, vector<long long>(n, LLONG_MAX / 2));
// 经验: `LLONG_MAX` 常数是在 `climits` 标头中定义的宏常数,用于获取 `long long int` 对象的最大值
for (int i = 0; i < n; ++ i)
dist[i][i] = 0;
for (auto&& road: roads)
{
int x = road[0], y = road[1], z = road[2];
dist[x][y] = z;
dist[y][x] = z;
}
// 经验: C++ `auto &&` 知乎: https://zhuanlan.zhihu.com/p/25148592
// 1. 当你想要拷贝range的元素时,使用for(auto x : range).
// 2. 当你想要修改range的元素时,使用for(auto && x : range).
// 3. 当你想要只读range的元素时,使用for(const auto & x : range).
// dijkstra
vector<int> used(n); // 经验: C++ 中 vector<int> 可以当作 vector<bool> 用, 赋值时 `used[t] = true` 就行
for (int _ = 0; _ < n; ++ _) // 经验: C++ 中可以定义变量 `_`
{
int t = -1;
for (int j = 0; j < n; ++ j)
if (!used[j] && (t == -1 || dist[0][j] < dist[0][t])) t = j;
used[t] = true;
for (int j = 0; j < n; ++ j)
dist[0][j] = min(dist[0][j], dist[0][t] + dist[t][j]);
}
// 建有向图
vector<vector<int>> g(n);
for (auto&& road: roads)
{
int x = road[0], y = road[1], z = road[2];
if (dist[0][x] - dist[0][y] == z) g[y].push_back(x);
if (dist[0][y] - dist[0][x] == z) g[x].push_back(y);
}
// dfs
vector<int> f(n, -1);
function<int(int)> dfs = [&] (int u)
{
if (u == n - 1) return 1;
if (f[u] != -1) return f[u];
f[u] = 0;
for (auto v: g[u])
{
f[u] += dfs(v);
while (f[u] >= MOD) f[u] -= MOD;
}
return f[u];
};
return dfs(0);
}
};
**经验: **
LLONG_MAX
常数是在 climits
标头中定义的宏常数,用于获取 long long int
对象的最大值auto &&
知乎: https://zhuanlan.zhihu.com/p/25148592vector<int>
可以当作 vector<bool>
用, 赋值时 used[t] = true
就行_
:for (int _ = 0; _ < n; ++ _)