创建网站的步骤是,响应式网站模板 视差,江门移动网站建设报价,福田企业网站建设题目描述
题目链接
问题分析
这道体的思路非常简单和好理解#xff0c;找出字符串中的元音字符#xff0c;然后按照ASSIC值进行排序#xff0c;然后插入回对应的位置#xff0c;解题步骤为#xff1a;
使用一个set#xff08;可以快速查找的容器#xff09;#x…题目描述
题目链接
问题分析
这道体的思路非常简单和好理解找出字符串中的元音字符然后按照ASSIC值进行排序然后插入回对应的位置解题步骤为
使用一个set可以快速查找的容器建立元音字符集合遍历整个字符串s挨个匹配是否在set中然后使用一个数组记录元音字符在字符串中的位置将s中的对应位置的元素提取出来按照ASSIC进行排序挨个插入回字符串中
简单模拟的解法
class Solution {setchar s_set{A,E,I,O,U,a,e,i,o,u};
public:string sortVowels(string s) {string S(s);//遍历字符串并查找元音字符的位置vectorint v;for(int i0;iS.size();i){if(s_set.find(S[i])!s_set.end()){v.push_back(i);}}if(v.size()1) return s; vectorint v_copy(v);//提取元婴字符进行排序sort(v.begin(),v.end(),[S](int a,int b){return S[a] S[b];});//插入回字符串中对应的位置string ret(s);for(int i0;iv.size();i){ret[v_copy[i]] s[v[i]];}return ret;}
};这个代码可以跑通大部分的测试用例2214 / 2216但是在字符串超长的时候就会超时所以需要进行优化
优化后
因为总共就10个元音字符大小写可以使用一个数组或者map记录每个字符在字符串中出现的次数。数组的话就需要消耗58个单元map需要消耗10个单元
int v[58]{0};//根据ASSIC码表的顺序ch-A
unordered_mapchar,int s_set{{A,0},{E,0},{I,0},{O,0},{U,0},{a,0},{e,0},{i,0},{o,0},{u,0}};然后使用一个只读的数组或者字符串来设置好元音字符的顺序,也就是待会插入元音字符的顺序根据ASSIC码值
vectorchar sv {A,E,I,O,U,a,e,i,o,u};挨个遍历字符串s,统计出元音字符出现的次数不能少同时可以统计出现的位置也可以不统计在第4步直接从头遍历并判断统计是为了优化第四步的时间对于排序元音字符通过设置sv也已经做好使用一个index作为一个双指针挨个遍历到需要插入的元音字符统计次数不为0挨个遍历到s中元音字符的位置然后使用Index按顺序插入元音字符
class Solution {unordered_mapchar,int s_set{{A,0},{E,0},{I,0},{O,0},{U,0},{a,0},{e,0},{i,0},{o,0},{u,0}};vectorchar sv {A,E,I,O,U,a,e,i,o,u};
public:string sortVowels(string s) {vectorint v;int i0;for(auto e: s){if(s_set.find(e)!s_set.end()){s_set[e] 1;v.push_back(i);}i;}if(v.size()1) return s; int index 0;for(auto e:sv)//最多遍历9次{if(s_set[e] 0){break;}index;}for(int i0;iv.size();i){s[v[i]] sv[index];s_set[sv[index]]--;while(index sv.size()s_set[sv[index]]0){index;}}return s;}
};该问题主要是需要优化不必要的耗时思路并不难
