剑指offer--algorithm
2018-04-11 本文已影响0人
strive鱼
眼勤、手勤、脚勤 ，方成大事--了不起的匠人第三季年画
智者，上善若水，海纳百川，仁者，高山仰止，厚德载物--了不起的匠人第三季年画
题三--替换空格
we are happy 输出 we%20are%20happy
上述题目的一些说明：
image.png
下面开始解题：
该题的解题关键在于是在原来的字符串上修改，还是创建新的字符串在新的字符串上做修改，如果在原来字符串上作修改，就必须使得空格后的每个字符向后移动两个字节，否则会被覆盖，如果创建新的字符串，则不存在该问题，可以创建足够多的内存
- O(n2)时间复杂度思路--正向思路：简单来讲，碰到一个空格，就把空格后面的部分后移，该例子中有两个空格，可以发现，“happy" 移动了两次，时间复杂度为O（n2)，该思路为从前往后移动的思路
- O(n1)时间复杂度思路--逆向思路： 逆向思维，简单来讲就是先计算好将空格替换后的字符串的长度，然后设定两个指针，一个指向替换之前的字符串的末尾，另一个指向替换后字符串的末尾，这样一来，每一个原先的字符都只移动一次，时间复杂度问为O（n1),该思路本质是一个从后往前的思路，因此较思路1更具优势
其中，关于O(n1)思路，书中已经说的非常完美，只能盗用膜拜
image.png
下面为代码：
方法一：该方法实际上是创建了一个新的字符串，占用了新的内存，看似十分简单，但不是最佳选择
class method1(object):
def __init__(self,s):
self.s=s
def replace1(self):
l=[]
sl=list(self.s)#将字符串转化为列表,即拆分为['w','e',' ',.....]
for item in sl:
if item==' ':#如果为空格
l.append('%20')
else:
l.append(item)
return ''.join(l)#利用Join方法把内容穿起来
def main():
s='we are happy'
m=method1(s)
print (m.replace1())
if __name__=='__main__':
main()
方法二：最狗血，但是这肯定不是本题的意义所在
class method2(object):
def __init__(self,s):
self.s=s
def replace2(self):
return self.s.replace(' ','%20')
def main():
s='we are happy'
m=method2(s)
print (m.replace2())
if __name__=='__main__':
main()
方法三：书中的 O(n1)思路，本题的意义所在
class method3(object):
def __init__(self,s):
self.s=s
def news(self):#用来计算新的空格的长度
sl=list(self.s)
l=len(self.s)#原先字符串的长度
count=0#用来计算空格的个数
for item in sl:
if item==' ':
count+=1
l=l+count*2
return l
def replace3(self,l):#l为上述的news方法得到的
newl=int(l)*[None]#生成一个全为None 的列表
indexoriginal=len(self.s)-1#即将指针放在源字符串的最后一个字母位置
indexnew=int(l)-1#将另一个指针放在新生成的字符串长度的最后一个字节
while indexnew>=0 and indexnew>=indexoriginal:#进行判断
if self.s[indexoriginal]==' ':
newl[indexnew-2:indexnew+1]=['%','2','0']#就将空格的替代符号依次插入到新的空列表中
indexoriginal-=1#更新指针的位置，上前挪动一个字节位
indexnew-=3#同样另一个指针向前挪动三个字节位
else:
newl[indexnew]=self.s[indexoriginal]#如果判断不是空格的话，就将原先的字母传递给新生成的列表，进行存储
indexoriginal-=1#指针向前移动一位
indexnew-=1#紧跟上一个指针向前移动，目的是找到插入%20的位置
return ''.join(newl)#最后粘合该序列
def main():
s='we are happy'
m=method3(s)
l=m.news()
print (m.replace3(l))
if __name__=='__main__':
main()
至次该题解答完毕，上述代码亲写有效
题四--从尾到头打印列表
输入一个链表的头节点，从尾到头反过来打印每一个节点的值
下面开始解题:
- 思路一：就是先改变指针的方向，然后得到一个原来链表的反向链表，然后逐一地从头获得链表的内容-----但是该方法正如书中所说改变了题目原先的链表结构
- 思路二：就是不改变原先链表的结构，先遍历到的数据后输出（pop),后遍历到的数据先输出，有没有很熟悉这个概念----对，正是栈的基本原理
在进行代码编写之前，还是必须把链表结构搞清楚，常见的链表构造和基本操作如下代码：
#单项列表它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
class node(object):
def __init__(self,item):
"""
单项列表的节点构造（一个信息域，一个链接域）
"""
self.item=item
self.next=None
def getitem(self):
return self.item
def getnext(self):
return self.next#本质上把它理解为跳到下一个节点
def setitem(self,newitem):
self.item=newitem
def setnext(self,newnext):
self.next=newnext#增加一个新节点
class singlelinklist(object):
def __init__(self):
self.head=None#定义了表头
self.size=0
def is_empty(self):
return self.head==None#判断表头是否为空，这是一个布尔型的返回值
def add(self,item):#添加节点，实现相互链接
temp=node(item)#实例化
temp.setnext(self.head)#更改其原先的指针
self.head=temp#自己变为了表头，且表头指向None
#return temp
def append(self,item):#在链表的尾部添加元素
temp=node(item)#首先实例化一个要添加的节点
if self.is_empty():#如果表头为空，就在这个位置上添加
self.head=temp#就把这个新元素作为表头
else:
current=self.head
while current!=None:
current=current.getnext()#此时往下移动一个节点，下一个节点变为表头
current.setnext(temp)#把这个节点加入到末尾，它自己temp本身也是指向None
def search(self,item):#检查元素是否在队列里面
current=self.head#将表头实例化
verify=False#用于flag,判断要搜寻的元素是否在所有的节点里面
while current!=None and not verify:
if current.getitem()==item:
verify=True
else:
current=current.getnext()#移动到下一个节点
return verify
def index(self,item):#输出所搜索的元素的索引的位置
current=self.head
count=0
verify=False
while current!=None and not verify:
count+=1
if current.getitem()==item:
verify=True
else:
current=current.getnext()
if verify:
return count
else:
return 'item not in this singlelinklist'
def remove(self,item):#从队列中删除一个数值
current=self.head
prone=None
while current!=None:
if current.getitem()==item:
if not prone:
self.head=current.getnext()
else:
prone.setnext(current.getnext())
break
else:
current=current.getnext()
prone=current
def insert(self,pos,item):#第一个参数是要插入的索引值
if pos<=1:
self.add(item)#就将其插入在最前边
if pos>self.size:
self.append(item)
else:
temp=node(item)#先把其狗造成节点
count=1
pre=None
current=self.head
while pos>count:
count+=1
pre=current#先将原来的表头进行复制
current=current.getnext()#跳到表头的下一个节点
pre.setnext(temp)#插入新的节点
temp.setnext(current.getnext())#使该节点与后续的节点再链接起来
def main():
demo=singlelinklist()
demo.add(2)
demo.add(3)
print (demo)
if __name__=='__main__':
main()
明白了上述的代码，链表的代码写法根据每个人的理解，也会有所不同，这道题的解答代码如下，尝试采用不同的方式：
class node(object):
def __init__(self,element=None):
self.element=element
self.next=None #指向None
"""
实现一个单链表的链接
"""
n1=node(1)
n2=node(2)
n3=node(3)
n4=node(4)
n1.next=n2
n2.next=n3
n3.next=n4
def log(node):#日志打印,这样就可以清楚的看到链表的结构
while node is not None:
print ('element', node.element)
node=node.next#实现层层嵌套打印，很巧妙
class peek(object):#栈的结构
def __init__(self):
self.head=node()#声明一个表头节点
def push(self,element):#进栈
n=node(element)#声明一个实例
n.next=self.head.next
self.head.next=n#至此就将表头与新的节点串联起来，没有返回值
def pop(self):#出栈,先入的后出
n=self.head.next
self.head.next=n.next
return n.element
def main():
#log(n1)可打印出所有的链表结构
p=peek()
p.push('a')
p.push('b')
p.push('c')
"""
链表的结构为c--b--a,而非a--b--c,请格外注意，这是栈结构不同于
链表结构的特点
"""
print (p.pop())
print (p.pop())
print (p.pop())
"""
打印结果为
c
b
a
"""
if __name__=='__main__':
main()
- 不过分追求外在的十五，而追寻内心的力量---了不起的匠人紫砂壶
- 劝成殆事，美成在久，知世事之艰，仍定心磨练自我，即仰宇宙之大，也怀有日用器皿之心
- 欣于所遇，快然自足，繁华在心，安宁也心
晚安
