请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 ：
输入：s = “We are happy.” 输出：“We%20are%20happy.”
限制：
0 <= s 的长度 <= 10000
from ast import literal_eval from collections import deque class Solution: def replaceSpace(self, s: str) -> str: """ 算法思想： (1) 开辟一个新字符数组new_s，size为旧字符串长度+空格数的2倍 (2) 设置两个下标指针q_old和p_new，起始q_old指向旧字符串最后与p_new指向新字符数组最后 (3) 判断q_old所指位置元素是否是空格。若是则在新字符数组中使用p_new依次加入0、2、%；否则将s[q_old] 赋值给new_s[p_new]，更新p_new。随后更新q_old。 (4) 继续(3),直到不符合循环条件退出循环。当q_old = p_new 时，旧字符串前部剩余部分已无空格 (5) 将旧字符串中前部剩余无空格的字符串依次赋值给新字符数组。 算法时间复杂度： O(len(s)) 空间复杂度： O(len(s)) :param s: :return: """ space_num = 0 # 字符串空格数 for i in s: if i == ' ': space_num += 1 # 字符串中空格数+1 old_len = len(s) # 旧字符串长度 new_len = (space_num << 1) + old_len # 新字符串长度 new_s = deque([' ']*new_len) # 新字符数组 q_old = old_len - 1 # 旧字符串最后一个位置 p_new = new_len - 1 # 新字符串数组最后一个位置 while q_old != p_new: # 构建新字符串数组 if s[q_old] == ' ': # 旧字符串中当前位置为空格时，为新字符数组相应位置存入"%20" new_s[p_new] = '0' p_new -= 1 new_s[p_new] = '2' p_new -= 1 new_s[p_new] = '%' p_new -= 1 else: # 旧字符串中当前位置不为空格时，将旧字符串当前位置的字符赋值到新字符数组相应位置 new_s[p_new] = s[q_old] p_new -= 1 q_old -= 1 # 旧字串下标-1 while q_old >= 0: # 将旧字符串中前部剩余无空格的字符串依次赋值给新字符数组 new_s[q_old] = s[q_old] q_old -= 1 new_s = ''.join(new_s) # 将字符数组拼接成字符串 return new_s # 返回新字符串 def replaceSpace_(self, s: str) -> str: """ 算法思想： 使用re模块 :param s: :return: """ import re s = re.sub(' ', '%20', s) return s if __name__ == '__main__': solution = Solution() # s = literal_eval(input('s: ').strip()) s = "We are happy." result = solution.replaceSpace(s) print(result) result = solution.replaceSpace_(s) print(result) """ 运行结果： We%20are%20happy. We%20are%20happy. Process finished with exit code 0 """[题目来源于Leetcode剑指offer]
