作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
一段时间以来,我一直试图解决这个看似非常简单的问题。给定字符串 k,我们必须找到将字符串 k 拆分为 3 个子串 k1、k2、k3 的最佳方法,例如 k1 + k2 + k3 = k。当且仅当通过反转每个子串并将它们重新连接在一起,我们得到尽可能按字典顺序排列的最小结果时,拆分才是最佳的。
例如,以字符串 k = "anakonda"为例。拆分它的最佳方法是 k1 = "a", k2 = "na", k3 = "konda"因为在反转 (k1 = "a", k2 = "an", k3 = "adnok") 之后我们得到 k1 + k2 + k3 = "aanadnok"这是字典序最小的可能结果。
我的第一种方法是始终在下一个字典序最小的字符处结束子字符串。
std::string str = "anakonda"
int first = find_min(str, 0, str.size() - 3); // Need to have at least 3 substrings so cannot search to the end
std::reverse(str.begin(), str.begin() + first + 1);
...
然而,这种方法存在缺陷,因为给定字符串 k = "ggggffffa"算法不起作用。
最佳答案
该算法解决了问题,但可能需要优化:
#include <iostream>
#include <string>
std::string foo(std::string* ss)
{
std::string res;
for (int i = 0; i < 3; i++)
for (int j = ss[i].size()-1; j >= 0; j--)
res.push_back(ss[i][j]);
return res;
}
int main()
{
std::string s = "ggggffffa";
std::string res = "";
for (unsigned int i = 1; i < s.size() - 1; i++)
for (unsigned int j = 0; j < i; j++)
{
std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};
std::string r = foo(ss);
if (r < res || res == "") res = r;
}
std::cout << res << std::endl;
}
描述:
for (unsigned int i = 1; i < s.size() - 1; i++)
for (unsigned int j = 0; j < i; j++)
i
, j
并在字符串数组中写入三个子字符串; std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};
foo
它反转每个子字符串,连接三个部分并返回结果字符串。 if (r < res || res == "") res = r;
关于string - 算法:最佳地将字符串拆分为 3 个子字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62624493/
我是一名优秀的程序员,十分优秀!