tags: 字符串
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
这道题有几个条件没有说:
- str的大小默认足够大,可以容纳替换空格后的字符创
- length是str的原长度,不包括'0'
- 不许额外分配内存空间
空格是一个字符,%20是三个字符,依次替换后字符串长度会变长。
这道题的简单思路就是两层循环,第一层循环从字符串开始处寻找空格,找到空格后进入到第二层循环,替换空格后,将空格后的字符串依次后移。
这种做法理解起来简单,但时间复杂度为O(n^2),并且后面的字符要移动多次,耗费时间
这道题其实是典型的两指针移动问题。可以先统计出原始字符串中空格的个数,之后计算新的字符串长度。
使两个指针分别指向新旧字符串的最后一个字符,遇见空格就替换并移动指针,否则复制后移动指针。
涉及到指针的问题,要避免越界或者访问空指针,所以要判断字符串是否为空
从后向前替换空格过程 ## 编程知识 ### python #### [python里快速创建指定大小的list的方法](https://bbs.pku.edu.cn/v2/post-read.php?bid=1360&threadid=14398267)a=[None]*n
a=list(range(n))
a=[None for i in range(n)]
这里第三种形式有用的原因是,Python 里的乘法创建的是实例的引用。也就是说,[list()] * 3 里的(作为元素的)列表,实际是一个实例:修改其中之一,会同步修改到剩余所有的引用。
比如a=[set()]*n,创建出的list中所有元素会指向同一个set()
优先级关系:or<and<not,同一优先级默认从左往右计算
Python中不是用\0来判断字符串结尾, 每个字符串都存有字符串的长度,通过计数来判断是否到达结尾
type()不会认为子类是一种父类类型。 isinstance()会认为子类是一种父类类型。
需要注意的是,旧式类跟新式类的type()结果是不一样的。旧式类都是<type 'instance'>。
class A:
pass
class B:
pass
class C(object):
pass
print 'old style class',type(A())
print 'old style class',type(B())
print 'new style class',type(C())
print type(A()) == type(B())
输出 old style class <type 'instance'> old style class <type 'instance'> new style class <class 'main.C'> True
class Solution {
public:
void replaceSpace(char *str,int length) {
//这道题里的str,默认在替换空格后足够大,length是str的原长度,不包括最后的'0'
if (str==NULL&&length<=0)
return;
int num=0;
for (int i=0;i<length;i++){
if (str[i]==' ')
num++;
}
int len=length+num*2;
for (int i=length-1,j=len-1;i>=0&&j>=0;i--){
if (str[i]==' '){
str[j--]='0';
str[j--]='2';
str[j--]='%';
}else
str[j--]=str[i];
}
str[len]='0';
}
};
这里的python代码其实效率并不高,这样写的目的是为了实现书中的思路。最简单的思路就是直接调用字符串类型的replace方法
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
if not isinstance(s,str) or len(s) <=0 or s==None:
return ""
num=0
for i in s:
if i==' ':
num+=1
newLen=len(s)+num*2
newStr=[None for i in range(newLen)]
oIdx,nIdx=len(s)-1,newLen-1
while oIdx>=0 and nIdx>=0:
if s[oIdx]==' ':
newStr[nIdx-2:nIdx+1]=['%','2','0']
oIdx-=1
nIdx-=3
else:
newStr[nIdx]=s[oIdx]
oIdx-=1
nIdx-=1
return "".join(newStr)