📗difficulty：Easy
🎯Tags：
请实现一个函数，把字符串 s 中的每个空格替换成 "%20" 。
样例：
输入：s = "We are happy."
输出："We%20are%20happy."
- 能做到在
O(n)时间复杂度内完成吗？
我们假定这样的字符串是以字符数组的形式存储下来的。在 Java 中，即为 char[] 。
一种思路是从前向后处理，由于数组的特性，对于插入操作，需要搬迁数据，这会带来很高的复杂度。
对于一个空格来说，对其进行处理，需要搬迁后面 O(n) 个字符，对于含有 O(n) 个空格字符的字符串，总的时间复杂度为 O(n ^ 2) 。这样的代价是很高的。
如果换一种思路，从后先前进行处理呢？
首先，对于一个空格字符来说，将其置换为 %20 ，需要额外的 2 个空间，那么最后的数组长度就需要增加 n * 2 个空间。而空格字符的总量，一次遍历即可，复杂度为 O(n) 。
设置 2 个指针，一个指针为 p，指向扩容前的最后一个字符，这里的字符数组长度以及扩充为 len(chars) + n * 2 了。一个指针为 q，指向扩容后的字符数组尾部。p 每次向前一个位置，如果字符不为空格，q 直接覆写 p 当前所指字符，q--；遇到空格，则写入 %20 ，q = q - 3。这样将复杂度下降为 O(n) 。
public String replaceSpace(String s) {
// 按照书本的思路指示，处理 s 按照 array 的方式来处理
if (s == null || s.length() == 0) {
return "";
}
int spaceCount = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '\u0020') { // 空格的 Unicode 编码
spaceCount++;
}
}
char[] chars = new char[s.length() + 2 * spaceCount];
int p = s.length() - 1;
int q = chars.length - 1;
while (p >= 0) {
if (s.charAt(p) != '\u0020') {
chars[q] = s.charAt(p);
q--;
} else {
chars[q] = '0';
chars[q - 1] = '2';
chars[q - 2] = '%';
q = q - 3;
}
p--;
}
return String.valueOf(chars);
}这里按照《剑指Offer》中给定的描述，输入为一个字符数组的形式。那么可以获得如下的复杂度。
- 时间复杂度
O(n)
- 空间复杂度
O(1)
数组的覆写具有一定的特性，修改其中的数据可能会需要大量的数据搬迁。
某些情况下，可以利用给定数组的特殊性质和操作情况，灵活进行操作。例如本道题目的情况，从后向前进行覆写，达到优化时间复杂度的目标。
依然使用从后向前的思路进行操作。注意最后处理剩余的数组元素。
public void insert(int[] a1, int size, int[] a2) {
int fullsize = size + a2.length;
int p = size - 1;
int q = fullsize - 1;
int z = a2.length - 1;
while (p >= 0 && z >= 0) {
if (a1[p] >= a2[z]) {
a1[q--] = a1[p--];
} else {
a1[q--] = a2[z--];
}
}
while (p >= 0) {
a1[q--] = a1[p--];
}
while (z >= 0) {
a1[q--] = a2[z--];
}
}在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）则需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样可以减少移动的次数，从而提高操作的效率。
以下资料来自 双指针技巧秒杀四道数组/链表题目 中的分析，感谢原作者的分析。
使用 2 个指针，一个 slow 指针，一个 fast 指针。当两个指针所指向的数字相同时，说明出现了重复的元素，那么 fast 指针向后移动，继续寻找不同的数字，当指针指向元素不相同时，此时 slow 指针指向的元素应该予以保留，而 slow ~ (fast - 1) 的元素是和 fast 元素相同的，应该予以“删除”。所以，先对 slow++，然后使用 fast 的进行覆写，这样可以使得 [0 ~ slow] 的元素都不相同。
public int removeDuplicates(int[] nums) {}
if (nums.length <= 1 ) {
return 1;
}
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[slow] != nums[fast]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}和上面26. 删除排序数组中的重复项 思路一致，区别是对链表指针进行操作。
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null) {
if (slow.val != fast.val) {
slow.next = fast;
slow = slow.next;
}
fast = fast.next;
}
slow.next = null;
return head;
}使用 2 个指针，一个 slow 指针，一个 fast 指针。当 fast 指针指向元素为 val 时，此时应该直接跳过该元素。当 fast 指针所指向的数字不为 val 时，说明还没有定位到了重复的元素，此时 fast 指针指向的元素应该予以保留，将 slow 元素覆写即可，然后进行 slow++ 操作，这样可以使得 [0 ~ slow - 1] 的元素都不相同。最后返回 slow，即为不相同的元素的字串长度。
public int removeElement(int[] nums, int val) {
int slow = 0;
int fast = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}题目让我们将所有 0 移到最后，其实就相当于移除nums中的所有 0，然后再把后面的元素都赋值为 0 即可。
那么就可以参考 27. 移除元素 ，将 0 元素进行覆盖，求出非 0 的长度即可。
public void moveZeroes(int[] nums) {
int n = nums.length;
int i = 0;
int j = 0;
while (j < n) {
if (nums[j] != 0) {
nums[i] = nums[j];
i++;
}
j++;
}
for (j = i; j < n; j++) {
nums[j] = 0;
}
}依旧是双指针的思想，一个头指针 left 和尾指针 right ，分别交换 2 个位置的元素，直到它们相遇。
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
char t;
while (left < right) {
t = s[left];
s[left] = s[right];
s[right] = t;
left++;
right--;
}
}- 考察应聘者对字符串的编程能力。
- 考察应聘者分析时间效率的能力。需要面试者能够清楚地计算不同算法的时间复杂度是多少。
- 考察应聘者对于内存覆盖是否具有很高的敏感性和高度的警惕性。在得知需要对字符串进行扩容的情况下，明白可能存在的问题，和面试官积极地进行沟通。
- 考察应聘者的思维能力。从初始的：从前向后替换的思路被否定，能否有反向思路，从后向前进行替换，这才是解决本题的关键所在。