剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入： s = “We are happy.”
输出： “We%20are%20happy.”

限制：

$0<=s的长度<=10000$

解法一：暴力解

使用StringBuilder，遇到字符就直接append到sb,遇到空格就append "%20"。

Java代码

class Solution {public String replaceSpace(String s) {//返回空串，返回null提交失败，因为题目没有指明，故无伤大雅if(s == null || s.length() == 0) return ""; StringBuilder sb = new StringBuilder();for(int i = 0;i < s.length();i++){if(s.charAt(i) == ' '){sb.append("%20");//StringBuilder的append方法的参数可以是字符，也可以是字符串}else{sb.append(s.charAt(i));}}return sb.toString();}
}

go代码一

func replaceSpace(s string) string {if s == "" || len(s) == 0 { return "" }temp := make([]string,0)//注意：// 1. go中无char类型，go中可用byte表示字符// 2. 此处不可用range遍历，因为go中range遍历字符串得到的是rune类型，而非byte类型for i := 0;i < len(s);i++ {c := s[i]if c == ' ' {temp = append(temp,"%20")}else{temp = append(temp,string(c))}}return strings.Join(temp,"")
}

go代码二

func replaceSpace(s string) string {if s == "" || len(s) == 0 { return "" }/*标准库 strings 中有个Builder 类型，该类型中 WriteString 方法和 String 方法配合使用，也可以实现字符串拼接，可以拼接字符串、字符和 Unicode，但是无法和Java中的stringbuilder一样混合拼接字符串和字符底层虽然涉及 string 和 []byte 之间的转换，但是，它使用 unsafe.Pointer 优化了 string 和 []byte 之间的转换，所以，在大量字符串拼接的场景，推荐使用该种方式。*/var sb strings.Builderfor i:= 0; i < len(s);i++ {c := s[i]if c == ' ' {sb.WriteString("%20")} else {sb.WriteString(string(c))}}return sb.String()
}

解法二：从后往前填充思想

这种从后往前填充的思想，很多题中都有用到，应该好好掌握，灵活运用。

① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。

② 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

③ 当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出。

Java代码

class Solution {public String replaceSpace(String s) {//返回空串，返回null提交失败，题目没有指明，故无伤大雅if(s == null || s.length() == 0) return ""; StringBuilder sb = new StringBuilder(s);for(int i = 0; i < s.length(); i++){if(s.charAt(i) == ' '){sb.append("  ");//在尾部添加两个空格}}int p1 = s.length() - 1;int p2 = sb.length() - 1;while(p2 > p1 && p1 >= 0){char c = sb.charAt(p1--);if(c == ' '){sb.setCharAt(p2--,'0');sb.setCharAt(p2--,'2');sb.setCharAt(p2--,'%');}else{sb.setCharAt(p2--,c);}}return sb.toString();}
}

go代码

func replaceSpace(s string) string {if s == "" || len(s) == 0 { return "" }//计算出最终结果字符串的长度length := 0for i:= 0; i < len(s);i++ {if s[i] != ' ' {length += 1}else{length += 3 //字符是空格时，一个字符将变成三个字符}}str := make([]byte,length)//建立和最终结果长度一致的byte切片p1 := len(s) - 1p2 := length - 1for p2 > p1 && p1 >= 0 {if s[p1] == ' ' {// go 中貌似无法使用str[p2--] = '0'，这样使用的时候编译不通过str[p2] = '0'p2--str[p2] = '2'p2--str[p2] = '%'p2--}else {str[p2] = s[p1]p2--}p1--}//退出上面for循环后，如果s中还有字符没有遍历完(即是p2=p1时退出了上面for循环)，但此时s[:p1]的所有字符也是需要放到str中的for p1 >= 0 {str[p2] = s[p1]p2--p1--}return string(str)
}

---

第五题的扩展题：合并两个有序数组 LeetCode 88

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出： [1,2,2,3,5,6]

示例 2：

输入： nums1 = [1], m = 1, nums2 = [], n = 0
输出： [1]

提示：

$nums1.length==m+n$
$nums2.length==n$
$0<=m,n<=200$
$1<=m+n<=200$
$-10^9<=nums1[i],nums2[i]<=10^9$

解法一：暴力解

暴力解法，将nums2的所有元素添加到nums1中，然后用快速排序即可。时间复杂度为$O((m+n)log(m+n))$。

Java代码

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for(int i = m,j = 0;i<nums1.length && j<n;i++,j++){nums1[i] = nums2[j];}Arrays.sort(nums1);}
}

go代码
貌似go语言中无法在for循环的最后一段使用逗号表达式，如下面写法编译不通过

而如下写法提交成功

func merge(nums1 []int, m int, nums2 []int, n int)  {for i,j := m,0;i < m + n; {nums1[i] = nums2[j]i++j++   }sort.Ints(nums1)
}

解法二：从后往前填充思想

用从后往前的双指针方法，类似上面第五题的解法。从尾到头比较两个数组中的数字，并将较大的数字复制到nums1中的合适位置。时间复杂度为遍历一次数组$O(m+n)$

Java代码

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {//由于两个数组是有序的，故我们可以从后往前的慢慢补全nums1，时间O(n),空间O(1)int p1 = m-1;//nums1的尾位置int p2 = n-1;//nums2的尾位置int p = m+n-1;//拼接后的尾位置while(p1>=0 && p2>=0){//有至少一个数组遍历完时退出循环nums1[p--] = nums1[p1] < nums2[p2] ? nums2[p2--] :nums1[p1--];}//不管是p1<0了(nums2中有剩余），还是p2<0了（nums1中有剩余），都可用下式System.arraycopy(nums2,0,nums1,0,p2+1);}
}

go代码

func merge(nums1 []int, m int, nums2 []int, n int)  {p1 := m - 1p2 := n - 1p := m + n - 1for p1 >= 0 && p2 >= 0 {if nums1[p1] > nums2[p2] {nums1[p] = nums1[p1]p--p1--} else {nums1[p] = nums2[p2]p--p2--}}//下面两个for只会有一个执行//如果是nums1还未往前遍历完for p1 >= 0 {nums1[p] = nums1[p1]p--p1--}//如果是nums2还未往前遍历完for p2 >= 0 {nums1[p] = nums2[p2]p--p2--}
}

举一反三

在合并两个数组 （包括字符串）时，如果从前往后复制每个数字（或字符）则需要移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率，且算法代码看着更清晰易懂。