我在二月份参加一个编码比赛，我正在查看去年的问题集。我正在尝试执行的任务是这样的。作为输入，我得到一个整数 N(最大 10,000,000)和一个长度为 N 的字符串 S。字符串仅由字母"x"、"y"和"z"组成。
这些信都是"命令"。你从一个只由字母"A"组成的单词开始。如果你得到一个命令"x"，你会在你的单词后面添加一个"A"。
命令"y"将在单词的前面添加"B"。而"y"会翻转这个词。因此，输入 N = 3，S = "xyz"，将使单词成为"AAB"。x：添加"A"，y：添加"B"和z：翻转整个单词。 整个事情必须在 2 秒内完成，这对我来说似乎是一个问题。 我希望这一切都是可以理解的...
好吧，解决方案解释说双端队列将是最有效的方法，但我不能让它低于 10 秒多一点的执行时间。有人可以帮我找到优化此代码的方法吗？
using namespace std;
int main() {
int num = 10000000;
string commands = "";
bool reversed = false;
deque<char>word = { 'A' };
// just for generating the input. The real program would not need this
for (int i = 0; i < num / 5; i++) {
commands += "xyzxy'";
}
//cin >> num >> commands;
for (int i = 0; i < num; i++) {
if (commands.at(i) == 'x') { //If the command is 'x' add an A at the back
if (!reversed)
word.push_back('A');
else // if it the word is reversed, reverse the command
word.push_front('A');
}
else if (commands.at(i) == 'y') { //If the command is 'y', add a 'B' at the front
if (!reversed)
word.push_front('B');
else // if it the word is reversed, reverse the command
word.push_back('B');
}
else if (commands.at(i) == 'z') { // If the command is 'z' set the status to reversed/!reversed
reversed = !reversed;
}
}
if (reversed)
reverse(word.begin(), word.end());
for (int i = 0; i < word.size(); i++) { // print out the answer
cout << word.at(i);
}
system("pause");
return 0;
}
谢谢！
通常我们期望服务器每秒执行 10^6 个命令。
请记住 N=10,000,000 且时间限制为 2 秒，需要 O(n) 复杂性。
您可以使用以下技术来实现这一点：
使用双链表。
使用布尔变量，例如 flag，如果结果字符串从链表的前面开始，则给出 true，如果字符串从链表的后面开始，则给出 false。
对于输入字符串的每个字符push_back给定字符是否为 x，push_front给定字符是否为 y 并更改 flag 的值。
读取输入完成后，将字符串分别打印到标记值。
复杂度：O(n)
这个技巧有两个部分。
-
使用
std::deque，它针对容器两端的插入进行了优化。 -
不要翻转"z"输入的单词。相反，请跟踪读取"z"的次数，并更改添加
A和B的代码，以便在次数为奇数时，将字符添加到单词的另一端。
在输入结束时，如果最终计数为奇数，则只翻转字符串一次。
主要技巧是避免浪费时间一遍又一遍地翻转琴弦。您最多只需要翻转一次。
观察：向量上的push_back比 push_back 和 push_front 上的 deque 都快。
如果您使用两个向量(正面和背面)并将正面视为反转，那么您也可以消除所有"if(反向)..."。通过在 X 的反向向量上使用 push_back，在 Y 的前向量上使用push_back，并在点击 Z 时交换向量来填充。
然后在输出结果时，通过前向量进行反向迭代，通过后向量进行正向迭代。
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <chrono>
int main(int argc, char* argv[])
{
auto fileIn = std::ifstream{"flip.in"};
int commandSize;
std::string commands;
fileIn >> commandSize >> commands;
std::vector<char> wordFront;
std::vector<char> wordBack;
wordFront.push_back('A');
auto start = std::chrono::high_resolution_clock::now();
for (auto v : commands)
{
switch(v)
{
case 'x':
wordBack.push_back('A');
break;
case 'y':
wordFront.push_back('B');
break;
case 'z':
std::swap(wordFront, wordBack);
break;
}
}
auto finish = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = finish - start;
std::cout << "Elapsed time (secs): " << elapsed.count() << std::endl;
auto fileOut = std::ofstream{"flip.out"};
std::for_each(crbegin(wordFront), crend(wordFront), [&fileOut](auto v){ fileOut << v; });
std::for_each(cbegin(wordBack), cend(wordBack), [&fileOut](auto v){ fileOut << v; });
}
它在我的机器上并没有产生积极的影响，但在开始构建单词之前，您也可以在前后向量上保留一些空间。