剑指offer-Python版答案

发表于 2017-09-09 | 阅读次数

最近在看剑指offer，原书都是用C++实现的，考虑用Python实现一遍所有问题答案。由于牛客网有剑指offer的在线评测，所以本文所有代码都基于牛客网上的问题（可能会和原书题目描述不同）实现。

字符串

替换空格

题目描述：在线编程

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

分析：

Python中直接使用字符串的replace函数即可。

代码：

# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
return s.replace(' ', '%20')

正则表达式匹配

题目描述：在线编程

请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

分析：

直接使用python中的正则表达式进行完全匹配即可解决此问题。

代码：

# -*- coding:utf-8 -*-
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
import re
        result = re.findall('^' + pattern + '$', s)
if result:
return True
else:
return False

表示数值的字符串

题目描述：在线编程

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

分析：

可以用float函数是否抛出ValueError异常来判断，或是直接写正则表达式。

代码：

# -*- coding:utf-8 -*-
class Solution:
# s字符串
def isNumeric(self, s):
try:
            float(s)
except ValueError:
return False
else:
return True

数组

数组中只出现一次的数字

题目描述：在线编程

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

分析：

每次从列表中pop出一个值，如果这个值在列表中还存在，则直接从列表中remove掉这个值，如果不存在则加入结果列表中。

代码：

# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
        result = []
while array:
            number = array.pop()
if number not in array:
                result.append(number)
else:
                array.remove(number)
return result

二维数组中的查找

题目描述：在线编程

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

分析1：

如果不考虑题目特点的话（每行每列都递增），直接迭代列表每一行，检测该值是否在每一行的列表即可。

代码1：

# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
for row in array:
if target in row:
return True

分析二：

由于题目特点，每行每列都递增，则可以每次比较最右上角的数字，如果相等则返回，输入的数大于右上角的数，则排除这一行，输入的数小于右上角的数，则排除这一列。

代码二：

# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
        row = 0
        col = len(array[0]) - 1
while row < len(array) and col >= 0:
if array[row][col] == target:
return True
elif array[row][col] < target:
                row += 1
else:
                col -= 1
return False

栈和队列

用两个栈实现队列

题目描述：在线编程

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

分析：

两个栈，一个作为队首，一个作为队尾，队列Push操作就是向队尾栈添加元素，队列Pop操作，需要先判断队首栈是否为空，如不空，则队首栈栈顶元素出栈，如为空，则将队尾栈所有元素依次pop出来，并push到队首栈，然后再队首栈顶元素出栈。

代码：

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
        self.front = []
        self.rear = []
def push(self, node):
        self.rear.append(node)
def pop(self):
if not self.front:
while self.rear:
                self.front.append(self.rear.pop())
return self.front.pop()

包含min函数的栈

题目描述：在线编程

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

分析：

借助一个辅助栈，存储当前栈中最小元值组成的栈，入栈时小于等于辅助栈顶值时则同时也入辅助栈，出栈时，如等于辅助栈栈顶值，则辅助栈同步出栈这个值。

代码：

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
        self.stack = []
        self.min_stack = []
def push(self, node):
if not self.min_stack or node <= self.min_stack[-1]:
            self.min_stack.append(node)
        self.stack.append(node)
def pop(self):
if self.top() == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()
def top(self):
return self.stack[-1]
def min(self):
return self.min_stack[-1]

栈的压入、弹出序列

题目描述：在线编程

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

分析：

借助一个辅助栈实际模拟入栈出栈，最后看辅助栈是否为空即可。

代码：

# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
        stack = []
        index = 0
for v in pushV:
            stack.append(v)
while stack and stack[-1] == popV[index]:
                stack.pop()
                index += 1
return len(stack) == 0

递归和循环

斐波那契数列

题目描述：在线编程

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

分析：

在数学上，斐波那契数列是用递归的方法定义的：
F（0）= 0 （n = 0）
F（1）= 1 （n = 1）
F（n）= F（n-1）+ F（n - 2）（n >= 2）
如果程序中采用递归的方法话，那必定会超时的，因此要用循环的方法。

代码：

# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
        prev, next = 0, 1
for _ in range(n):
            prev, next = next, prev+next
return prev

跳台阶

题目描述：在线编程

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

F（0）= 0
F（1）= 1
F（2）= 2
F（n）= F（n-1）+ F（n-2）（n > 2）

代码：

# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
if number <= 2:
return number
        prev, curr = 1, 2
for _ in range(3, number+1):
            prev, curr = curr, prev+curr
return curr

变态跳台阶

题目描述：在线编程

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

F（0）= 0
F（1）= 1
F（2）= 2
F（n）= F（n-1）+ F（n-2）+ … + F（2）+ F（1）+ 1 = 2 **（n-1）

代码：

# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
return 2**(number-1)

矩形覆盖

题目描述：在线编程

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

分析：

F（0）= 0
F（1）= 1
F（2）= 2
F（n）= F（n-1）+ F（n-2）（n > 2）

代码：

# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
if number <= 2:
return number
        prev, curr = 1, 2
for _ in range(3, number+1):
            prev, curr = curr, prev+curr
return curr

大师兄 wechat

欢迎关注我的微信公众号：Python大师兄