面试题 01.03. URL化

news/2024/10/30 11:30:06/

URL化

URL化。编写一种方法,将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的“真实”长度。(注:用Java实现的话,请使用字符数组实现,以便直接在数组上操作。)

示例 1:

输入:"Mr John Smith ", 13
输出:“Mr%20John%20Smith”
示例 2:

输入:" “, 5
输出:”%20%20%20%20%20"

提示:

字符串长度在 [0, 500000] 范围内。

题解1

新建一个字符串,遍历原来的,直接按要求添加即可
需要额外的空间,并且时间都集中在添加上

class Solution {
public:string replaceSpaces(string S, int length) {string s;for(int i=0;i<length;i++){if(S[i]==' ')s+="%20";else s+=S[i];} return s;}
};

题解2:

先计算有多少个空格
注意:假定该字符串尾部有足够的空间存放新增字符
这意味着可能有多余空格(测试点20)
然后调整空间,成为合适的空间大小
最后双指针算法,线性时间下改变

class Solution {
public:string replaceSpaces(string S, int length) {int kong = 0;for(int i=0;i<length;i++)if(S[i]==' ')kong ++;int j = length + 2 * kong -1;S.resize(j+1);for(int i=length-1;i>=0;i--,j--){if(S[i]==' '){S[j]='0';S[j-1]='2';S[j-2]='%';j-=2;}else S[j]=S[i];}return S;}
};

题解3:

对题解2的优化,直接按照一样的方法往后放,最后取字串即可

class Solution {
public:string replaceSpaces(string S, int length) {int j = S.size()-1;for(int i=length-1;i>=0;i--,j--){if(S[i]==' '){S[j]='0';S[j-1]='2';S[j-2]='%';j-=2;}else S[j]=S[i];}return S.substr(j+1,string::npos);}
};

当然还有一个纯 O ( N 2 ) O(N^2) O(N2)的算法写法,就是找到空格就把后面的字符往后放,然后再添加。


http://www.ppmy.cn/news/104136.html

相关文章

stackqueue

这篇主要讲栈(stack)和队列(queue)&#xff0c;实际要学习的数据结构有三个&#xff1a;stack、queue、priority_queue 这些数据结构已经不属于容器了&#xff0c;而是容器适配器。 list的第二个参数是空间配置器&#xff0c;支持申请空间&#xff1b;而list和queue的第二个参…

目标检测复盘 -- 6. YOLOv4

Backbone YOLOv4的骨干是CSPDarknet53 CSP结构的作用&#xff1a;1. 增强CNN的学习能力 2. 移出计算瓶颈 3. 减少内存开销 CSP首先将输入的特征层分成两个部分&#xff0c;这里以densenet为例&#xff0c;part2分支经过denseblock后&#xff0c;进过一个transition&#xff0c…

Python打包成EXE

一、使用Pyinstaller pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pyinstaller 1.2Pyinstaller打包步骤 Pyinstaller -F -w -i apple.ico py_word.py 结果&#xff1a; 运行结果&#xff1a; 二、使用Auto-py-to-exe auto-py-to-exe 是一个用于打包 python 程序…

智警杯赛前学习1.1---excel基本操作

修改默认设置 步骤一&#xff1a;打开“Excel选项”窗口&#xff0c;打开“文件”菜单&#xff0c;选择“选项”标签 步骤二&#xff1a;在“Excel选项”窗口中&#xff0c;选择“常规与保存”标签&#xff0c;在“常规与保存”标签中&#xff0c;可以修改录入数据时的默认字体…

【Web服务器集群】Apache配置与应用

文章目录 一、构建虚拟web主机1.概述2.httpd服务支持的虚拟主机类型3.构建虚拟Web主机3.1基于域名的虚拟主机3.2基于IP地址的虚拟主机3.3基于端口的虚拟主机 4.Apache连接保持5.Apache访问控制 二、Apache日志管理rotatelogs分隔工具 三、总结1.Web虚拟主机部署步骤2.网页根目录…

java程序员找工作经验之谈,聊聊需要做好哪些关键点才能获得认可

我是18年本科毕业于双飞一本的交互设计&#xff0c;因为喜欢编程所以快考的计算机。当时初试过了复试没有过&#xff0c;被调剂到一个211大学的相关专业。这个专业从名称上来看跟计算机没有任何关系&#xff0c;但是他实际做的事情&#xff0c;或者说我在我导师那边做的事情&am…

算法当中的时间、空间复杂度?

1.究竟什么是时间复杂度 时间复杂度是一个函数&#xff0c;它定性描述该算法的运行时间 时间复杂度就是用来方便开发者估算出程序运行的答题时间。 通常会估算算法的操作单元数量来代表程序消耗的时间&#xff0c;这里默认CPU的每个单元运行消耗的时间都是相同的。 假设算法的…

K8s in Action 阅读笔记——【6】Volumes: attaching disk storage to containers

K8s in Action 阅读笔记——【6】Volumes: attaching disk storage to containers 在前三章中&#xff0c;我们介绍了Pods以及它们与ReplicationControllers、ReplicaSets、DaemonSets、Jobs和Services等Kubernetes资源的交互。现在&#xff0c;我们将回到Pod内部&#xff0c;…