重建序列
题目
给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。
例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。
如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。
链接
题解
本质上也是一道拓扑排序的题目，从sequences中的子序列中提取数字之间的依赖关系，构建indegree以及outnodes的信息;
注意在用BFS进行拓扑排序的过程中就可以和nums进行比较，如果不一致立即可以返回false，同时，保持序列唯一性的重要条件，就是每次indegree唯一且没有遍历过的数字必须有且仅有一个；最后要确保生成的序列和nums长度一致
class Solution {
public:
bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
int n=nums.size();
vector<int>indegree(n+1,0);
vector<vector<int>>outnodes(n+1);
for(auto seq:sequences){
for(int i=1;i<seq.size();i++){
int a=seq[i-1];
int b=seq[i];
indegree[b]++;
outnodes[a].emplace_back(b);
}
}
queue<int>q;
bool flag=true;
for(int i=1;i<=n;i++){
if(indegree[i]==0){
q.emplace(i);
}
}
int cnt=0;
while(!q.empty()){
int size=q.size();
if(size!=1){
//存在多种可能
// printf("!");
return false;
}
for(int i=0;i<size;i++){
int u=q.front();
if(u!=nums[cnt]){
// printf("%d %d %d?",u,nums[cnt],cnt);
return false;
}
cnt++;
q.pop();
for(auto v:outnodes[u]){
indegree[v]--;
if(indegree[v]==0){
q.emplace(v);
}
}
}
}
if(cnt!=n){
return false;
}
return flag;
}
};
省份数量
题目
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
链接
题解
思路：基础的连通图，BFS和DFS都可以做，返回连通图的个数即可
class Solution {
public:
vector<bool>vis;
int n;
void dfs(int index,vector<vector<int>>& isConnected){
vis[index]=true;
for(int i=0;i<n;i++){
if(!vis[i]&&isConnected[index][i]){
dfs(i,isConnected);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
//连通图的个数
n=isConnected.size();
vis.resize(n);
int cnt=0;
for(int i=0;i<n;i++){
if(!vis[i]){
dfs(i,isConnected);
cnt++;
}
}
return cnt;
}
};
相似的字符串
题目
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给定一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个 字母异位词 。请问 strs 中有多少个相似字符串组？
字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。
链接
题解
思路：本质依然是在找连通图，需要自己构建图，由题意知道图的节点个数为字符串个数，节点对应字符串，字符串是否相似对应节点之间是否有边
class Solution {
public:
void dfs(int index,vector<vector<int>>&graph,vector<bool>&vis){
vis[index]=true;
for(auto v:graph[index]){
if(!vis[v]){
dfs(v,graph,vis);
}
}
}
int numSimilarGroups(vector<string>& strs) {
//相似字符串的对数
//暴力解法
int ans=0;
int n=strs.size();
int m=strs[0].size();
vector<vector<int>>graph(n);
vector<bool>vis(n,false);
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
//判断两个存在一条边与否
int cnt=0;
for(int k=0;k<m;k++){
if(strs[i][k]!=strs[j][k]){
cnt++;
if(cnt>2){
break;
}
}
}
if(cnt==0||cnt==2){
graph[i].emplace_back(j);
graph[j].emplace_back(i);
}
}
}
for(int i=0;i<n;i++){
if(!vis[i]){
ans++;
dfs(i,graph,vis);
}
}
return ans;
}
};