C++ 笔试算法实战：打怪模拟、字符串分类与连通分量

二、字符串分类

题目描述

给定 t 个字符串，定义两个字符串属于同一类，如果它们可以通过交换任意位置字符互相变换。求共有多少类字符串。

解题思路

两个字符串如果能通过交换字符变成对方，意味着它们的字符种类和每个字符出现的频次完全一致。最直观的判断方法是将字符串排序，如果排序后的结果相同，则属于同一类。

利用哈希集合（unordered_set）存储排序后的字符串，集合的大小即为类别的数量。这种方法避免了复杂的频次统计，代码简洁高效。

代码实现

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

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

三、城市群数量

题目描述

给定一个 n 阶矩阵，dp[i][j] == 1 表示城市 i 和城市 j 相连。若 a 连 b，b 连 c，则 a 与 c 也视为连通。求有多少个城市群（连通分量）。

解题思路

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

遍历每个城市，如果该城市未被访问过，则从它开始进行一次 DFS，标记所有与其连通的城市。每启动一次新的 DFS，就代表发现了一个新的城市群。统计 DFS 启动的次数即可得到答案。

代码实现

#include <vector>
using namespace std;

class Solution {
public:
    bool vis[201];
    
    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();
        // 初始化访问数组
        for(int i=0; i<n; ++i) vis[i] = false;
        
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ret++;
                dfs(m, i, n);
            }
        }
        return ret;
    }
};

以上三道题涵盖了面试中常见的数学推导、字符串处理及图搜索场景，建议结合具体输入输出格式多加练习。