威海市建设工程协会网站,洛阳seo,大连网站建设外包公司,pc下载网站模板①这道题可以直接申请一个临时数组#xff0c;然后遍历字符串#xff0c;是空格则加入20%#xff0c;最后再把临时数组转化为字符串。 怎么把一个数组转化为字符串? 如数组arry[]#xff0c; string newstr new string(arry,0,arry.size()-1); return newstr; 而且临时数… ①这道题可以直接申请一个临时数组然后遍历字符串是空格则加入20%最后再把临时数组转化为字符串。 怎么把一个数组转化为字符串? 如数组arry[] string newstr new string(arry,0,arry.size()-1); return newstr; 而且临时数组的空间要申请大一些。 public String replaceSpace(String s) { int length s.length(); char[] array new char[length * 3]; int index 0; for (int i 0; i length; i) { char c s.charAt(i); if (c ) { array[index] %; array[index] 2; array[index] 0; } else { array[index] c; } } String newStr new String(array, 0, index); return newStr; }
②或者用栈只是出栈后结果是需要来个翻转吗有点不大会。 ③不过上面的这些方法都需要时间复杂度O(n)并且空间复杂度O(n)。 接下来有个时间复杂度O(n)但是空间复杂度O(1)的做法要是学会了也不难接下来说说这种解法。 这个解法就不需要申请新的空间。 第一步首先扩充数组到每个空格替换成%20之后的大小。 比如这道题每个空格要变成20%即一个空格变成了3个空格所以每个空格处要添加2个空格即先统计字符串中有多少个空格然后多少个空格*2。怎么添加字符串长度? //s.resize(n); resize将string类中有效字符改变到n个。 第二步从后向前替换空格也就是双指针法过程如下 i指向新长度的末尾j指向旧长度的末尾。 然后i,j往前如果s[j]不是空格则把s[j]赋给s[i]; 如果s[j]是空格则s[i]赋为0, s[i-1]赋为2, s[i-2]赋为%并且i往前移三格。然后继续ij一起往前移继续如此轮下去。 ④有同学问了为什么要从后向前填充从前向后填充不行么 从前向后填充就是O(n^2)的算法了因为每次添加元素都要将添加元素之后的所有元素向后移动。 ⑤其实很多数组填充类的问题都可以先预先给数组扩容带填充后的大小然后在从后向前进行操作。 这么做有两个好处 不用申请新数组。 从后向前填充元素避免了从前向后填充元素时每次添加元素都要将添加元素之后的所有元素向后移动的问题。 当ij时即说明扩充的空格都用完了说明前面已经没有空格要变成20%了所以就可以结束了所以循环结束条件就是ji而不是ji。
class Solution { public: string replaceSpace(string s) { int count 0; // 统计空格的个数 int sOldSize s.size(); for (int i 0; i s.size(); i) { if (s[i] ) { count; } } // 扩充字符串s的大小也就是每个空格替换成%20之后的大小 s.resize(s.size() count * 2); int sNewSize s.size(); // 从后先前将空格替换为%20 for (int i sNewSize - 1, j sOldSize - 1; j i; i--, j--) { if (s[j] ! ) { s[i] s[j]; } else { s[i] 0; s[i - 1] 2; s[i - 2] %; i - 2; } } return s; } };
