剑指offer——02替换空格(Python3)
2024-08-26 05:18:56
思路:Python列表中实现字符串的替换,涉及到频繁的插入操作,在数据结构中线性表分为顺序表和链表,顺序表的适合频繁的查询,链表适合频繁的插入和删除。综上所述,本题使用链表来实现。
我们从字符串的后面开始复制和替换,设置P1和P2指针,其中P1指向原来字符串的尾部,P2指向替换后字符串的尾部。移动P1指针,依次将P1指向的字符复制到P2,直到遇到第一个空格,在P2之前插入%20,同时P2指针向前移动三次。直到P1和P2指针相遇,则表示替换完毕。
所有的字符都复制一次,时间复杂度为O(n)。
代码:
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
str_array = list(s) # 将字符串转为列表
origin_str_length = len(str_array)#列表长度
origin_index = origin_str_length - 1#尾指针
new_str_array = []
while origin_index >= 0:#终止条件
if str_array[origin_index] != ' ':
new_str_array.insert(0, str_array[origin_index])
else:
new_str_array.insert(0, '%20')
origin_index -= 1
return "".join(new_str_array) # 将列表转为字符串
最新文章
- VIM教程
- Django进阶(三)
- C语言-纸牌计算24点小游戏
- 及时取消代码中的AsyncTask
- Python先合并再排序
- sqoop笔记
- 【SQL】姗姗来迟的SQL Server 安装图解
- POJ2253 Frogger
- 剑指offer--面试题12
- 初探 插头DP
- Solidity基础
- css3实现切片动画
- EF学习和使用综合
- 深度学习-tensorflow学习笔记(1)-MNIST手写字体识别预备知识
- openerp7.0接收邮件时别名区分大小写问题,以及处理非别名域邮件问题解决方法
- Maven:Generating Project in Batch mode 卡住问题
- Redis C#入门
- 亚马逊MWS开发套路演示
- 浅谈HTML5中canvas中的beginPath()和closePath()的重要性
- linux查找进程id端口占用和杀死进程