C++找位置问题案例代码-QQ沐编程

问题描述

小猪佩奇和小兔苏西在森林中散步，走着走着突然迷路了！他们走到了一条小路上，路上有 N 个房子，每个房子有一个彩色的气球。

不幸的是，房子没有门牌号，让小猪佩奇和小兔苏西很难确定他们在小路上的位置。

不过，每个房子的气球都有不同的颜色，所以小猪佩奇和小兔苏西希望只要观察连续的若干个气球颜色，他们就可以确定自己在小路上的位置。

每个气球的颜色由字母 A..Z 表示，因此沿着小路的N个气球的序列可以用长度为 N 的字符串表示，其中每个字符都是 A..Z 范围内的字母。

一些气球的颜色可能与其他气球的颜色相同。

如果小猪佩奇和小兔苏西观察到任何长度为 K 的连续气球的颜色在 N 个气球中是唯一的，他们就可以确定自己在小路上的位置。

请你编程计算出 K 的最小值，使得他们可以观察到任何长度为 K 的连续的气球颜色，就可以唯一地确定自己在小路上的位置。

例如，假设沿着小路的气球序列是 ABCDABC 。小猪佩奇和小兔苏西无法设置 K=3 ，因为如果他们看到 ABC，这个连续的颜色序列可能在小路上有两个位置。

实际上，对于气球序列 ABCDABC，最小的 K 值是 K=4，因为如果他们观察任何连续的 4 个气球，这个颜色序列就可以唯一地确定他们在小路上的位置。

输入

第一行包含 N（1≤N≤100）第二行包含一个长度为 N 的字符串，每个字符都是A..Z 范围内的字母。

输出

打印一行，包含一个整数，指定解决小猪佩奇和小兔苏西的问题的最小值 K。

答案解析

解题思路

为了解决这个问题，我们需要找到一个最小的整数 K，使得对于给定的字符串（表示气球的颜色序列），任意长度为 K 的子串都是唯一的。换句话说，我们需要找到最短的子串长度 K，使得所有可能的长度为 K 的子串都不重复。

我们可以使用滑动窗口的方法来解决这个问题，并且利用哈希表（或者集合）来跟踪我们遇到的每个长度为 K 的子串。如果在增加 K 的过程中，我们发现所有长度为 K 的子串都是唯一的，那么我们就找到了答案。

完整代码

下面是用 C++ 实现该算法的代码：

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

int findMinK(const string& balloons) {
    int N = balloons.size();
    
    // 如果路径上的房子数量小于等于1，则直接返回N即可
    if (N <= 1) return N;
    
    // 尝试从最小可能的K值开始，即1，直到N
    for (int K = 1; K <= N; ++K) {
        unordered_set<string> seen;
        bool unique = true;
        
        // 检查所有长度为K的子串是否唯一
        for (int i = 0; i <= N - K; ++i) {
            string sub = balloons.substr(i, K);
            if (seen.find(sub) != seen.end()) {
                unique = false;
                break;
            }
            seen.insert(sub);
        }
        
        // 如果所有长度为K的子串都是唯一的，则返回K
        if (unique) return K;
    }
    
    // 理论上不会到达这里，因为当K=N时，整个字符串作为一个子串总是唯一的
    return N;
}

int main() {
    int N;
    cin >> N;
    string balloons;
    cin >> balloons;
    
    cout << findMinK(balloons) << endl;
    
    return 0;
}

代码解释

函数 findMinK:
- 接收一个字符串 balloons 作为参数。
- 首先检查如果字符串长度小于等于1，则直接返回其长度。
- 使用一个循环尝试不同的 K 值，从1开始到 N 结束。
- 对于每一个 K 值，创建一个 unordered_set 来存储已经看到的所有长度为 K 的子串。
- 再次使用一个内部循环遍历字符串中所有的长度为 K 的子串，并检查这些子串是否已经在 seen 集合中存在。
- 如果发现了重复的子串，则设置标志 unique 为 false 并跳出循环。
- 如果没有发现重复的子串，则当前的 K 是满足条件的最小值，函数返回这个 K。
主函数 main:
- 读取输入数据：首先是整数 N 表示字符串的长度，然后是字符串本身。
- 调用 findMinK 函数并输出结果。