第2篇 空格替换&列表逆序输出

字符串——替换空格
链表——逆序输出链表

替换空格

要求
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路
如果用Python或者java等高级点的语言，直接调replace是最简单的写法了，或者开一个新字符串，从前往后读原字符串，读到其他字符就直接追加，读到空格就追加%20。

如果用C语言，字符串以char[]来存，就要考虑更多的东西，比如数组的容量，挪动各个char，最后的\0等。

一种思路是从前往后读，碰到空格，就先把后面的全部内容往后挪两格，加入%20。这样会导致很多内容被多次挪动，O(n^2)效率。
另一种思路是，预先扫一遍看有多少个空格，从而知道最终结果的长度，然后从后往前进行替换，预留出恰好的空间。这样每个字符只需要挪动一次，O(n)效率即可。

需要特别注意\0、空指针、容量不足以及数组边界的问题。

# python第一印象这样写，但是，字符串是不可变的！！！！
rep = '%20'
def solution(str):for i in range(len(str)):if str[i] == ' ':str[i] = str[i].replace(' ', rep)return str
if __name__ == '__main__':str = 'We Are Happy'print(solution(str))# 所以可以考虑使用列表存储字符串
rep = '%20'
list1 = []
def solution(str):global list1for i in str:list1.append(i)for i in range(len(str)):if list1[i] == ' ':list1[i] = list1[i].replace(' ', rep)return list1
if __name__ == '__main__':str = 'We Are Happy'print(solution(str))# 进一步可以写为rep = '%20'
list1 = []
def solution(str):global list1for i in range(len(str)):list1.append(str[i])if list1[i] == ' ':list1[i] = list1[i].replace(' ', rep)return list1if __name__ == '__main__':str = 'We Are Happy'print(solution(str))

在线版本

# -*- coding:utf-8 -*-
class Solution:# s 源字符串def replaceSpace(self, s):# write code herelist1 = []for i in range(len(s)):list1.append(s[i])if list1[i] == ' ':list1[i] = '%20'return "".join(list1)

# 使用c的解答
class Solution {
public:void replaceSpace(char *str,int length) {//length是字符数组的总容量大小，而不是字符串的长度。//遍历一遍字符串找出空格的数量if(str==NULL||length<0)return ;int i=0;int oldnumber=0;//记录以前的长度int replacenumber=0;//记录空格的数量while(str[i]!='\0'){oldnumber++;if(str[i]==' '){replacenumber++;}i++; }int newlength=oldnumber+replacenumber*2;//插入后的长度if(newlength>length)//如果计算后的长度大于总长度就无法插入return ;int pOldlength=oldnumber; //注意不要减一因为隐藏个‘\0’也要算里int pNewlength=newlength;while(pOldlength>=0&&pNewlength>pOldlength)//放字符{if(str[pOldlength]==' ') //碰到空格就替换{str[pNewlength--]='0';str[pNewlength--]='2';str[pNewlength--]='%';}else //不是空格就把pOldlength指向的字符装入pNewlength指向的位置{str[pNewlength--]=str[pOldlength];}pOldlength--; //不管是if还是elsr都要把pOldlength前移}}
};

这里感觉值得一提的是书中特别写出了测试用例：

• 输入的字符串中包含空格：空格在开头、最末、中间、连续多个空格
• 输入的字符串中没有空格
• 输入空指针、空串、只有一个空格、全为空格等特殊情况

在写代码时感觉 应该先想好这些各种情况，保证对各种特殊情况都考虑到了，才能使得写出的代码尽可能正确。

依据首字母将单词表进行归类

# 通过起始字母，将一个列表中的单词分类
words = ['apple', 'bat', 'bar', 'atom', 'book']
by_letter = {}
for word in words:letter = word[0]if letter not in by_letter:by_letter[letter] = [word]else:by_letter[letter].append(word)
print(by_letter)# 或者
# 使用setdefault()方法
for word in words:letter = word[0]by_letter.setdefault(letter, []).append(word)
by_letter

逆序输出列表

# 编写函数实现列表的逆序输出
def reverse01(list1):return list1[::-1]
if __name__ == '__main__':list1 = [0,1,2,3,4]print(reverse01(list1))# 或者使用reversed()
# 测试reversed函数
list1 = ['x','y',1,2,2,3,4,5,6]
list2 = list(reversed(list1))
print(list2)

倒序输出链表

class Solution:# 返回从尾部到头部的列表值序列，例如[1,2,3]def printListFromTailToHead(self, listNode):# write code herels = []head = listNodewhile head:ls.insert(0, head.val)head = head.nextreturn ls

题目描述
输入一个链表，从尾到头打印链表每个节点的值。

思路
1）倒置指针——会改变原始输入信息，需注意是否允许改变原数据
2）基于递归实现——先输出内层的，注意当链表很长时会导致调用栈溢出
3）基于栈，用循环实现

code

class Solution:# 返回从尾部到头部的列表值序列，例如[1,2,3]def printListFromTailToHead(self, listNode):# write code hereif not listNode:return []stack = []current = listNodewhile(current is not None):stack.append(current.val)current = current.nextresult = []# 注意range的使用for i in range(len(stack)-1, -1, -1):result.append(stack[i])return result

---