[已解决]求公共前缀

bin554385863 · 发表于 2019-8-22 23:28:58

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""*/
string longestCommonPrefix(vector<string> &strs)
{
    string result;

    /*判定向量是否为空*/
    if (strs.empty())
    {
        result = {""};
    }
    else
    {
        if (strs.size() < 3)
        {
            /*构造三个向量元素,跳过对向量长度小于3时的判定*/
            string temp = strs[0] + "o0";
            string temp1 = strs[0] + "1o0";
            string temp2 = strs[0] + "2o0";
            strs.push_back(temp);
            strs.push_back(temp1);
            strs.push_back(temp2);
            size_t j = 0, s = strs.size();
            for (size_t i = 0; i < s / 2; i++)
            {
                for (;; j++)
                {
                    if (strs[i][j] != strs[s - 1 - i][j])
                    {
                        break;
                    }
                    result.push_back(strs[0][j]);
                }
            }
        }
        else
        {
            /*在首位和次位向量元素追加任意不同的字符,跳过对多个空字符串的判定*/
            strs[0].push_back('o');
            strs[1].push_back('z');
            size_t j = 0, s = strs.size();
            for (size_t i = 0; i < s / 2; i++)
            {
                for (;; j++)
                {
                    if (strs[i][j] != strs[s - 1 - i][j])
                    {
                        break;
                    }
                    result.push_back(strs[0][j]);
                }
            }
        }
    }
    string &res = result;
    return res;
}
int main(int argc, char const *argv[])
{
    vector<string> a = {"flower", "floor", "flight"};
    vector<string> b = {"c", "c", "c"};
    vector<string> c = {"flower"};
    vector<string> d = {"",""};
    vector<string> e = {
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
};
    cout << longestCommonPrefix(a) << endl;
    cout << longestCommonPrefix(b) << endl;
    cout << longestCommonPrefix(c) << endl;
    cout << longestCommonPrefix(d) << endl;
    cout << longestCommonPrefix(e) << endl;
    return 0;
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Microsoft Windows [版本 10.0.16299.1087]
(c) 2017 Microsoft Corporation。保留所有权利。

E:\Users\86184\Documents\Code>c:\Users\86184\.vscode\extensions\ms-vscode.cpptools-0.25.0\debugAdapters\bin\WindowsDebugLauncher.exe --stdin=Microsoft-MIEngine-In-5lylunsz.ufb --stdout=Microsoft-MIEngine-Out-dkysla5w.cuu --stderr=Microsoft-MIEngine-Error-a54rus54.jdx --pid=Microsoft-MIEngine-Pid-qmnfxem5.bad "--dbgExe=E:\My Program\MinGW\bin\gdb.exe" --interpreter=mi
fl
c
flower

瓠?瓠贺?═ floorz ?瓠?瓠吼?═ flight ?瓠?瓠韩? ?艭: ???铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪铪?婩: ╗ ? ╔ 粒冢
((((((((((((((((((((
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
为什么字符串e会输出乱码,应该怎么判定?
求解?

最佳答案

月排行榜 / 总排行榜

cplus

2019-8-23 16:12:32

用 Visual studio 运行，不会乱码

跳转到最佳答案楼层

cplus · 发表于 2019-8-23 16:12:32

用 Visual studio 运行，不会乱码

bin554385863 · 发表于 2019-8-24 01:47:17

#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
using namespace std;
/*编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""*/
string longestCommonPrefix(vector<string> &strs)
{
        string result;
        /*判定向量是否为空*/
        if (strs.empty())
        {
                result = {""};
        }
        else
        {
                size_t s = strs.size();
                if (s == 1)
                {
                        return strs[0];
                }
                else if (s > 1)
                {
                        /*构造向量字符串元素跳过对{"c", "c",...}和{"","",....}类似的向量元素的判定*/
                        strs[0] = strs[0] + "10lo";
                        strs[1] = strs[1] + "l01o";
                        /*初始化计数器*/
                        size_t count = 0;
                        /*定义数组,保存对比的计数结果*/
                        vector<int> arr;
                        for (size_t i = s - 1; i > 0; i--)
                        {
                                for (size_t j = 0;; j++)
                                {
                                        if (strs[0][j] != strs[i][j])
                                        {
                                                break;
                                        }
                                        count++;
                                }
                                arr.push_back(count);
                                /*重新初始化计数器*/
                                count = 0;
                        }
                        size_t sa = arr.size();
                        /*从小到大排序*/
                        sort(arr.begin(), arr.end());                
                        /*首位元素就是最终结果*/
                        if (arr[0] == 0)
                        {
                                result = {""};
                        }
                        else
                        {
                                for (size_t i = 0; i < arr[0]; i++)
                                {
                                        result.push_back(strs[1][i]);
                                }
                        }
                }
        }
        return result;
}
int main(int argc, char const *argv[])
{
        vector<string> a = {"boot", "boom", "boor", "boall"};
        vector<string> b = {"baac", "bacc", "b"};
        vector<string> c = {"flower"};
        vector<string> d = {"",""};
        vector<string> e =
                {
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                };
        cout << longestCommonPrefix(a) << endl;
        cout << longestCommonPrefix(b) << endl;
        cout << longestCommonPrefix(c) << endl;
        cout << longestCommonPrefix(d) << endl;
        cout << longestCommonPrefix(e) << endl;
        return 0;
}

账号		自动登录	找回密码
密码			立即注册