博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
面试总结之 pslow pfast 方法
阅读量:6890 次
发布时间:2019-06-27

本文共 554 字,大约阅读时间需要 1 分钟。

题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”。
解决方法: 事实上,我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我们可以设想,当一个字符需要被删除的时候,我们把它所占的位置让它后面的字符来填补,也就相当于这个字符被删除了。在具体实现中,我们可以定义两个指针(pFast和pSlow),初始的时候都指向第一字符的起始位置。当pFast指向的字符是需要删除的字符,则pFast直接跳过,指向下一个字符。如果pFast指向的字符是不需要删除的字符,那么把pFast指向的字符赋值给pSlow指向的字符,并且pFast和pSlow同时向后移动指向下一个字符。这样,前面被pFast跳过的字符相当于被删除了。用这种方法,整个删除在O(n)时间内就可以完成。 pSlow是改变后的指针,pFast是改变前的指针,可以把pSlow想象成另外一个数组,如果pFast遍历的那个元素符合要求就拷贝到pSlow中,如果不符合就不拷贝;只不过这里用一个数组实现的

 

转载于:https://www.cnblogs.com/leetcode/p/3199777.html

你可能感兴趣的文章
《Unix网络编程》卷2 读书笔记 第3章- System V IPC
查看>>
命令导入证书
查看>>
Django-CBV
查看>>
NativeWindow_01
查看>>
【Flutter学习】基本组件之图片组件Image
查看>>
(转)工作之路---记录LZ如何在两年半的时间内升为PM
查看>>
CoreAnimation
查看>>
JS基础属性跟运算
查看>>
《转》精巧好用的DelayQueue
查看>>
Mongoose的模糊查询
查看>>
C#汉语转拼音,日文转假名
查看>>
[导入]WAP常见问题问答大全---七、关于WAP浏览器的常见问答
查看>>
无法使用此电子邮件地址。请选择其他电子邮件地址
查看>>
对接微信支付使用HMAC-SHA256使用签名算法实现方式
查看>>
Jenkins这种构建工具,一般都是内部使用,所以外部基本上不能访问
查看>>
php 慢配置文件
查看>>
mq和redis安装
查看>>
c# 字符串是否含有中文
查看>>
Bootstrap3基础 栅格系统 列中有行,行中有列
查看>>
按时间排序,查询不同类别各一个
查看>>