请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：
0 <= s 的长度 <= 10000
思路1：新建一个字符串，用于拼接，是空格则拼接"%20" 否则就拼接本身
时间：O(n);
空间：O(n)
public static string ReplaceSpace(string s)
{
string temp_string = "";
for (int i = 0; i < s.Length; i++)
{
temp_string += (s[i] == ' ') ? "%20" : s[i];
}
return temp_string;
}
思路2：直接更改原先的字符串
更改原先的字符串，那么摆在前面的就两个路
首先原先的字符串肯定不够装的，一个空格对应三个char字符，
We are happy. -----> We are happy.____
所以需要先进行检测字符串内一共有多少个空格，有多少就在字符串后面加多少个 __
只是为了占位置,一个空格对应三个，因为本身算一个，所以扩2个 __
1、见到空格，就往那个地方塞进去一个%20，其他的往后移动（这样太麻烦了，而且时间复杂度立马就上去了）
2、从后往前（注意遇到换位置的最好都是从后往前）
双指针，
一个指针p指向原来的字符串的位置（用来表示老字符串遍历到哪了），p指向 .
一个指针q指向最后面（应该把前面的字符串放到后面的哪）q指向 _
'.' 不是 空格，所以直接把他放到q的位置上,We are happy.___.
We are happy.___. > We are happy.__y. > We are happy.__y. > We are happhappy.
遇到了空格,We are happhappy. > We are h%20happy.
We are e%20happy.
反正就这样
简单理解就是：遇到不是空格的，直接往后放，遇到了是空格的，就往后放%20，就这样一直循环，直到结束
时间：O(n);
空间：O(1)，（没有新建，只是扩容了）
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。 这么做有两个好处：
不用申请新数组。
从后向前填充元素，避免了从前先后填充元素要来的每次添加元素都要将添加元素之后的所有元素向后移动。
public static string ReplaceSpace2(string s)
{
int space_count = 0;
foreach (var v in s)
{
space_count += (v == ' ') ? 1 : 0;
}
if (space_count == 0)
{
return s;
}
int p = s.Length - 1;
for (int i = 0; i < space_count; i++)
{
s += "__";
}
int q = s.Length - 1;
while (p>=0)
{
if (s[p] != ' ')
{
// s[q] = s[p];
q--;
}
else
{
// s[q] = '0';
// s[q--] = '2';
// s[q--] = '%';
}
p--;
}
return s;
}
*C#中的string为不可变的，只能开辟新的堆内存去放，所以上面那种实现方法不行
* 只能去改成char[]数组实现
public static string ReplaceSpace3(string s)
{
int space_count = 0;
foreach (var v in s)
{
space_count += (v == ' ') ? 1 : 0;
}
if (space_count == 0)
{
return s;
}
int p = s.Length - 1;
for (int i = 0; i < space_count; i++)
{
s += "__";
}
// Array.Resize(ref arr, s.Length + space_count * 2);// 扩充字符串的长度的另外一种方法
char[] arr = s.ToCharArray();// C++可以直接使用字符串，C#就必须转换一下类型，这里可能就不省空间了，但是思路最重要
int q = arr.Length - 1;
while (p>=0)
{
if (arr[p] != ' ')
{
arr[q--] = s[p];
}
else
{
arr[q--] = '0';
arr[q--] = '2';
arr[q--] = '%';
}
p--;
}
return new string(arr) ;
}
static void Main(string[] args)
{
string num = ReplaceSpace3("We are happy.");
Console.WriteLine(num);
}
}
