打起精神来,今天有比昨天更好一点!
这题,我对他的解释是,现在有未知的图,我有些node跟node之间的线索,用线索去把这个图的全貌拼凑出来(讲得好像在解谜一样XD)。
简单讲就是现在这张图,只有它送过来指定的node配对中,两点的公因数有大於threshold,两点之间就有连线。
感觉这题是在图的基础上,问你怎麽找两数的公因数。
因为题目问的是:请问我指定的配对有没有path可以连通,所以两点之间即使没有直达的edge,也可能有path存在,所以不能单单只是找最大公因数。
所以思路会改为,先判断公因数,更新图,如果没有符合条件的公因数,再用traversal找一遍。
class Solution {
public:
vector<int> parent ;
vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
vector<bool> answer(queries.size());
if (!threshold) {
fill(answer.begin(), answer.end(), true);
return answer;
}
parent = vector<int>(n+1) ;
for (int i = 0; i < parent.size(); i++) parent[i] = i;
for (int z = threshold + 1; 2*z <= n; z++)
for (int x = 2; x*z <= n; x++)
unionfunc(z, x*z);
for (int i = 0; i < queries.size(); i++)
answer[i] = find(queries[i][0]) == find(queries[i][1]);
return answer;
}
private:
int find(int u) {
if (parent[u] != u)
return find(parent[u]);
return u;
}
void unionfunc(int u, int v) {
parent[find(v)] = parent[find(u)];
}
};
这题跟第一天Graph-Tree: uva 615 Is It A Tree?一样使用并查集,也体会到我还没有很熟这种资料结构,至少我没办法像adj list那样熟练。
并查集是了解了没错,但是参不透中间那两个for是干啥用的!
Line 30: Char 10: error: declaration of anonymous union must be a definition
void union(vector& parent, int u, int v) {
union是保留字
参考:
https://leetcode.com/problems/graph-connectivity-with-threshold/discuss/899462/Extremely-useful-Union-Find-class-Feel-Free-to-Reuse
https://www.youtube.com/watch?v=ayW5B2W9hfo
<<: Day19 - 使用Django进行自动化测试 (1)
前面有介绍过 Module 的一些基本使用方式,然而有一项非常强大的功能没有被提及,就是 动态模组(...
CPU 是以 clock cycle 为单位,每一小段时间做一点事 等等!我们一开始就没提到过时间啊...
session 简单来说就是可以在多个页面存取同一位使用者连线资料。他其实和 cookie 很像 但...
动态模型我们会使用 LSTM-based 架构,并分成两种: Basic LSTM Last-fra...
Compare and contrast CPU, MCU, and embedded syste...