C++ 笔试算法实战：打怪、字符串分类与城市群计数

二、字符串分类

题目描述

给定 t 个字符串，要求对它们进行分类。若字符串 A 可以通过交换任意位置字符变换到 B（即互为变位词），则属于同一类。

例如：abcd、abdc、dcba 属于同一类。

解题思路

判断两个字符串是否属于同一类，本质是检查它们的字符种类及出现频次是否一致。

直接比较频次较为繁琐。换个角度思考：如果将字符串排序，互为变位词的字符串排序后必然相同。例如 abcd 和 dcba 排序后均为 abcd。

因此，策略非常清晰：

1. 遍历所有输入字符串。
2. 对每个字符串进行排序。
3. 使用哈希集合（unordered_set）存储排序后的结果，自动去重。
4. 最终集合的大小即为分类数量。

参考实现

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

int main() {
    int t;
    cin >> t;
    unordered_set<string> hash;
    while (t--) {
        string str;
        cin >> str;
        sort(str.begin(), str.end());
        hash.insert(str);
    }
    cout << hash.size() << endl;
    return 0;
}

三、城市群数量

题目描述

给定一个 n 阶矩阵，元素为 0 或 1。若 dp[i][j] == 1，表示第 i 个城市和第 j 个城市相连。连通关系具有传递性（若 a 连 b，b 连 c，则 a 连 c）。求共有多少个独立的城市群。

解题思路

这是一个典型的图论问题，求解连通分量的数量。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）解决。

核心逻辑如下：

1. 维护一个访问标记数组 vis。
2. 遍历每一个城市节点，若该节点未被访问过，则计数器加一，并从该点出发执行 DFS。
3. DFS 过程中，将所有可达且未访问的节点标记为已访问。
4. 遍历结束后，计数器的值即为城市群总数。

参考实现

#include <vector>
using namespace std;

class Solution {
public:
    bool vis[201] = {false};

    void dfs(vector<vector<int>>& m, int pos, int n) {
        vis[pos] = true;
        for (int i = 0; i < n; i++) {
            if (m[pos][i] == 1 && !vis[i]) {
                dfs(m, i, n);
            }
        }
    }

    int citys(vector<vector<int>>& m) {
        int n = m.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ret++;
                dfs(m, i, n);
            }
        }
        return ret;
    }
};