设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 求公共前缀
返回列表 发新帖
查看: 1549|回复: 2

[已解决]求公共前缀

[复制链接]
bin554385863
发表于 2019-8-22 23:28:58 | 显示全部楼层 |阅读模式

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

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

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

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

  12.     /*判定向量是否为空*/
  13.     if (strs.empty())
  14.     {
  15.         result = {""};
  16.     }
  17.     else
  18.     {
  19.         if (strs.size() < 3)
  20.         {
  21.             /*构造三个向量元素,跳过对向量长度小于3时的判定*/
  22.             string temp = strs[0] + "o0";
  23.             string temp1 = strs[0] + "1o0";
  24.             string temp2 = strs[0] + "2o0";
  25.             strs.push_back(temp);
  26.             strs.push_back(temp1);
  27.             strs.push_back(temp2);
  28.             size_t j = 0, s = strs.size();
  29.             for (size_t i = 0; i < s / 2; i++)
  30.             {
  31.                 for (;; j++)
  32.                 {
  33.                     if (strs[i][j] != strs[s - 1 - i][j])
  34.                     {
  35.                         break;
  36.                     }
  37.                     result.push_back(strs[0][j]);
  38.                 }
  39.             }
  40.         }
  41.         else
  42.         {
  43.             /*在首位和次位向量元素追加任意不同的字符,跳过对多个空字符串的判定*/
  44.             strs[0].push_back('o');
  45.             strs[1].push_back('z');
  46.             size_t j = 0, s = strs.size();
  47.             for (size_t i = 0; i < s / 2; i++)
  48.             {
  49.                 for (;; j++)
  50.                 {
  51.                     if (strs[i][j] != strs[s - 1 - i][j])
  52.                     {
  53.                         break;
  54.                     }
  55.                     result.push_back(strs[0][j]);
  56.                 }
  57.             }
  58.         }
  59.     }
  60.     string &res = result;
  61.     return res;
  62. }
  63. int main(int argc, char const *argv[])
  64. {
  65.     vector<string> a = {"flower", "floor", "flight"};
  66.     vector<string> b = {"c", "c", "c"};
  67.     vector<string> c = {"flower"};
  68.     vector<string> d = {"",""};
  69.     vector<string> e = {
  70.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  71.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  72.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  73.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  74.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  75.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  76.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  77.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  78.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  79.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  80.     "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  81. };
  82.     cout << longestCommonPrefix(a) << endl;
  83.     cout << longestCommonPrefix(b) << endl;
  84.     cout << longestCommonPrefix(c) << endl;
  85.     cout << longestCommonPrefix(d) << endl;
  86.     cout << longestCommonPrefix(e) << endl;
  87.     return 0;
  88. }
复制代码

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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 运行，不会乱码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

cplus
发表于 2019-8-23 16:12:32 | 显示全部楼层    本楼为最佳答案   
用 Visual studio 运行，不会乱码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

bin554385863
 楼主| 发表于 2019-8-24 01:47:17 | 显示全部楼层
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include<algorithm>
  5. using namespace std;
  6. /*编写一个函数来查找字符串数组中的最长公共前缀。

  8. 如果不存在公共前缀，返回空字符串 ""*/
  9. string longestCommonPrefix(vector<string> &strs)
  10. {
  11.         string result;
  12.         /*判定向量是否为空*/
  13.         if (strs.empty())
  14.         {
  15.                 result = {""};
  16.         }
  17.         else
  18.         {
  19.                 size_t s = strs.size();
  20.                 if (s == 1)
  21.                 {
  22.                         return strs[0];
  23.                 }
  24.                 else if (s > 1)
  25.                 {
  26.                         /*构造向量字符串元素跳过对{"c", "c",...}和{"","",....}类似的向量元素的判定*/
  27.                         strs[0] = strs[0] + "10lo";
  28.                         strs[1] = strs[1] + "l01o";
  29.                         /*初始化计数器*/
  30.                         size_t count = 0;
  31.                         /*定义数组,保存对比的计数结果*/
  32.                         vector<int> arr;
  33.                         for (size_t i = s - 1; i > 0; i--)
  34.                         {
  35.                                 for (size_t j = 0;; j++)
  36.                                 {
  37.                                         if (strs[0][j] != strs[i][j])
  38.                                         {
  39.                                                 break;
  40.                                         }
  41.                                         count++;
  42.                                 }
  43.                                 arr.push_back(count);
  44.                                 /*重新初始化计数器*/
  45.                                 count = 0;
  46.                         }
  47.                         size_t sa = arr.size();
  48.                         /*从小到大排序*/
  49.                         sort(arr.begin(), arr.end());               
  50.                         /*首位元素就是最终结果*/
  51.                         if (arr[0] == 0)
  52.                         {
  53.                                 result = {""};
  54.                         }
  55.                         else
  56.                         {
  57.                                 for (size_t i = 0; i < arr[0]; i++)
  58.                                 {
  59.                                         result.push_back(strs[1][i]);
  60.                                 }
  61.                         }
  62.                 }
  63.         }
  64.         return result;
  65. }
  66. int main(int argc, char const *argv[])
  67. {
  68.         vector<string> a = {"boot", "boom", "boor", "boall"};
  69.         vector<string> b = {"baac", "bacc", "b"};
  70.         vector<string> c = {"flower"};
  71.         vector<string> d = {"",""};
  72.         vector<string> e =
  73.                 {
  74.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  75.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  76.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  77.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  78.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  79.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  80.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  81.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  82.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  83.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  84.                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
  85.                 };
  86.         cout << longestCommonPrefix(a) << endl;
  87.         cout << longestCommonPrefix(b) << endl;
  88.         cout << longestCommonPrefix(c) << endl;
  89.         cout << longestCommonPrefix(d) << endl;
  90.         cout << longestCommonPrefix(e) << endl;
  91.         return 0;
  92. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-2 12:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表