Я работал над проблемой кода leetcode, чтобы перевернуть строку таким образом, чтобы при входном значении The boy is mad
результат был mad is boy The
. Я решил это, но решение казалось плохим, так как я много раз пробежал по струне. При отправке кода время, затрачиваемое на вычисление всех тестовых примеров, составляло ~ 250 мс, и я поверил этому, поскольку знал, что это худший из возможных кодов. Я посмотрел один из ответов и запустил этот код, он работал примерно за 4 мс. Я снова написал тот же код, но на этот раз я использовал a = a + b;
вместо a += b;
, и контрольные примеры снова заняли около 250 мс. Итак, я хочу знать, в чем разница между этими двумя и почему это занимает много времени на одном по сравнению с другим.
PS - В моем исходном (плохом) коде при изменении a = a + b
на a += b
код работал примерно 8 мс.
Вот коды: 1. медленный код (время выполнения - ~ 250 мс)
string reverseWords(string s) {
if(s.length() == 0)
{
return s;
}
int itr = 0;
// Remove white spaces from front
while(s[itr] == ' ')
{
itr++;
}
s = s.substr(itr,s.length()-itr);
if(s.length() == 0)
{
return s;
}
// Remover white spaces from back
for(int i = s.length()-1; i>= 0 ;i--)
{
while(s[i] == ' ')
{
s = s.substr(0,i);
i--;
//cout << s << endl;
}
break;
}
if(s.length() == 0)
{
return s;
}
cout << s << endl;
// Remove more than one space in the middle
for(int i = 0;i<s.length()-1;i++)
{
if(s[i] == ' ' && s[i+1] == ' ')
{
string temp;
temp = s.substr(0,i);
s = s.substr(i+1,s.length());
s = temp + s;
i--;
//cout << s <<endl;
}
}
string res = "";
reverse(s.begin(),s.end());
int start = 0;
for(int i = 0;i <s.length();i++)
{
start = i;
if(s[i] == ' ')
continue;
while(s[i] != ' ' && i < s.length())
{
i++;
// cout << i << " ";
}
// cout << endl;
string temp = s.substr(start,i-start);
reverse(temp.begin(),temp.end());
if(i != s.length())
res = res + temp + " ";
else
res = res + temp;
//cout << temp << endl;
}
return res;
}
Быстрый код (4 мс)
string reverseWords(string s)
{
stack<string> elements;
std::istringstream stream(s);
std::string word;
while (stream >> word)
{
elements.push(word);
}
string strReturn("");
int stackSize = elements.size();
int i = 0;
while( !elements.empty())
{
i++;
strReturn += elements.top();
elements.pop();
if( i != stackSize)
{
strReturn += " ";
}
}
return strReturn;
}
Переписан быстрый код (250 мс)
string reverseWords(string s) {
// Check the first available Accepted solution to see the shitiest solution for the code
stack<string> availableWords;
istringstream stream(s);
string word;
while(stream >> word)
{
availableWords.push(word);
}
int len = availableWords.size();
string res = "";
int i = 0;
while(!availableWords.empty())
{
res += availableWords.top();
availableWords.pop();
i++;
if(i != len)
{
res += " ";
}
}
return res;
}