在模拟面试中,我想到了这个问题。面试官先问这个问题,没有任何篇幅限制。然后他继续使用空间有限的版本。要在同一页面上。在问题中,给出了由定界符组成的字符串和容器类。这由您决定合适的容器类和响应语言。我认为样本输入和输出足以理解真正的问题是什么。
输入:
"Reverse#Strings Without%Changing-Delimiters"
输出:
"Delimiters#Changing Without%Strings-Reverse"
注意:"#"、"%"、"、"-"的位置不变
我想出了以下解决方案:
string ChangeOrderWithoutSpecial(string s, unordered_set<char> delimiter)
{
stack<string> words; // since last words outs first
queue<char> limiter; // since first delimiter outs first
string response =""; //return value
int index=-1; // index of last delimiter visited
int len=s.length();
for (int i =0 ; i <len;i++)
{
if(delimiter.find(s[i]) != delimiter.end()) // i-th char is a delimiter character
{
string temp=s.substr(index+1,i-index-1);
words.push(temp);
char t =s.at(i);
limiter.push(t);
index=i;
}
// i realized that part after interview under assumption starting with word and no double delimiters ie, each word followed by one delimiter
if(index!=s.length()-1)
{
string temp=s.substr(index+1,s.length()-index-1);//until the end;
cout<<temp<<endl;
words.push(temp);
}
while(!limiter.empty())
{
response+=words.top()+limiter.front();
words.pop();
limiter.pop();
}
response+=words.top();
return response;
}
但是我找不到 o(1) 空间的解决方案?任何人都知道如何?我也不知道是否有多个定界符,也适用。感谢大家花时间阅读。
最佳答案
找到第一个词和最后一个词。将字符串旋转 length(last_word)-length(first_word)
:这会将中间部分放在正确的位置。在示例中,这将产生
ersReverse#Strings Without%Changing-Delimit
然后按length(first_word)
旋转字符串的第一部分和最后一部分,跳过中间部分:
Delimiters#Strings Without%Changing-Reverse
对两个最外层定界符之间的子字符串重复此算法。
“旋转 m
”操作可以在 O(1)
空间和 O(n)
时间内执行,其中 n
是被旋转序列的长度。
关于c++ - 在 O(1) 空间限制中反转单词在字符串中的位置而不改变特殊字符的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52018854/