知识点哈希
描述
小红有一个 n 颗宝石构成的环形宝石手串，即第一颗和最后一颗宝石相连，其中第 i 个宝石的属性为 si ；若两个宝石的属性相同，那么这两个宝石会相互排斥，导致断开。
小红可以从手串中摘掉一些宝石，每次摘掉后，这个宝石左右的两个宝石会相接，手串依旧是环形。
小红想要破坏这个手串。她想要知道，最少还需要摘掉多少个宝石才会导致手串断开。特别的，当手串上剩余的宝石数量恰好为 2 而依旧没能断开时，视为破坏失败，直接输出 −1 。
输入描述：
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦100) 代表数据组数，每组测试数据描述如下：
第一行输入一个整数 n(2≦n≦105)代表手串初始的宝石数量。
第二行输入一个长度为 n 、仅由小写字母构成的字符串，代表手串上每个宝石的属性。
除此之外，保证单个测试文件的 n 之和不超过 105 。
输出描述：
对于每一组测试数据，如果手环无法破坏，直接输出 −1 ；否则，在一行上输出一个整数，代表手串断开需要的最少操作次数。
示例1
输入：
2
2
ac
3
aac
输出：
-1
0
题意理解：
在环形字符串中找到两个相同字符（全小写）之间的最小间隔距离。如果存在这样的间隔，返回最小间隔值；否则返回 `-1`。
cc方法0：// 暴力枚举
/hj110_rock_00_vio_00.cc
// 算法：// 暴力枚举
// ### 核心思想
// 1. **环形处理**：将字符串视为首尾相连的环形结构，计算间隔时需考虑绕回的情况。
// 2. **暴力枚举**：通过双重循环枚举所有可能的间隔距离 `len` 和起始位置 `i`，检查是否存在满足条件的字符对。
// 3. **贪心选择**：外层循环从小到大枚举间隔距离 `len`，确保首次找到的 `len` 是最小值并立即退出。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int GetRes(const string str)
{
int n = str.size();
// 为什么要先遍历间隔len？因为从小到大找到最小间隔就可以立即退出，最大间隔为 n – 2，最小间隔为0
for (int len = 0; len <= n – 2; ++len) {
// i表示元素起点，查找间隔为len的下一个元素是否一致
for (int i = 0; i < n; ++i) {
// str[i + len + 1]为什么要+1,因为len是两个下标之间的间隔
// 从i开始往后查找间隔len的元素是否相等，其中已经包含环形反转绕回查找
if (i + len + 1 < n && str[i] == str[i + len + 1]
|| i + len + 1 >= n && str[i] == str[i + len + 1 – n]) {
return len; // 找到后立即退出
}
}
}
return -1;
}
int main()
{
int n = 0;
while (cin >> n) {
for (int i = 0; i < n; ++i) {
int num = 0;
cin >> num;
string s = "";
cin >> s;
cout << GetRes(s) << endl;
}
}
return 0;
}
cc方法1：// 哈希表(使用vector)
/hj110_rock_01_hash_00.cc
// 算法：// 哈希表(使用vector)
// ### 核心思想
// 1. **预处理字符位置**：使用哈希表（`vec`）记录每个字符的所有出现位置。
// 2. **环形间隔计算**：对每个字符的位置列表，先计算第1个和最后一个位置的反向间隔，再逐一计算相邻位置的正向间隔。
// 3. **贪心选择最小间隔**：遍历所有字符的位置列表，维护全局最小间隔。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int GetRes(const string str)
{
int n = str.size();
vector<vector<int>> vec(26, vector<int>(0));
for (int i = 0; i < n; ++i) {
vec[str[i] – 'a'].push_back(i);
}
int minLen = n;
for (int i = 0; i < 26; ++i) {
// 没有这个字符或只有一个这样的字符，则表示不可以通过这个字符进行拆除，直接跳过
if (vec[i].empty() || vec[i].size() == 1) {
continue;
} else {
const vector<int> curVec = vec[i];
// 先计算第一个与最后一个的间隔
int left = curVec.front();
int right = curVec.back();
// 这里的正向间隔其实不需要计算，因为下文的循环遍历中会从第0个开始一直计算到最后一个相邻2个数之间的正向间隔
// minLen = min(minLen, right – left – 1); // 正向间隔
minLen = min(minLen, n – (right – left) – 1); // 反向间隔
// 同一个字符从出现的第二个坐标开始不需要在计算反向间隔，因为第1个和最后一个的反向间隔最小
for (int j = 1; j < curVec.size(); ++j) {
// 正向间隔计算，从下标0开始右移，计算两两相邻数据之间的间隔
// 必须从j – 1开始进行计算，因为上文获取第一个数只是计算反向间隔
left = curVec[j – 1];
right = curVec[j];
minLen = min(minLen, right – left – 1);
}
}
}
return minLen == n ? -1 : minLen;
}
int main()
{
int n = 0;
cin >> n;
int num = 0;
while (cin >> num) {
string s = "";
cin >> s;
cout << GetRes(s) << endl;
}
return 0;
}
cc方法2：// 哈希表(使用unordered_map)
/hj110_rock_01_hash_01.cc
// 算法：// 哈希表(使用unordered_map)
// ### 核心思想
// 1. **环形处理**：通过将字符串复制一份拼接到末尾（`s = s + s`），将环形问题转化为线性问题。
// 2. **滑动窗口**：利用哈希表记录字符最近出现的位置，实时计算相同字符之间的间隔。
// 3. **贪心选择**：维护全局最小间隔 `minLen`，遍历过程中动态更新。
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
int GetRes(int n, string s)
{
if (s.size() < 2 || s.size() == 2 && s[0] != s[1]) {
return -1;
}
// – 将环形字符串展开为线性结构，使得绕回开头的字符对可以通过线性遍历处理。
// `s + s`将原字符串复制一份拼接到末尾（环形展开为线性）
s = s + s;
unordered_map<char, int> pos; // 哈希表
int minLen = s.size();
for (int i = 0; i < s.size(); ++i) {
// 如果发现前面已经有同样字符，则和pos中最近位置pos[s[i]]进行间隔计算
if (pos.find(s[i]) != pos.end()) {
minLen = min(minLen, i – pos[s[i]] – 1); // 计算间隔
}
pos[s[i]] = i; // 更新字符的最新位置
}
return minLen == n – 1 ? -1 : minLen;
}
int main()
{
int n = 0;
while (cin >> n) {
for (int i = 0; i < n; ++i) {
int num;
string s;
cin >> num >> s;
cout << GetRes(num, s) << endl;
}
}
return 0;
}
