python 剑指offer
python数据结构与算法 讲解牛客网剑指offer66题
斐波那契数列
题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39
分析:斐波那契数列,形如:1、1、2、3、5、8、13…后一个数为前两位的和;
| n | num |
|---|---|
| n = 0 | num = 0 |
| n = 1 | num = 1 |
| n = 2 | num = 1 |
| n = 3 | num = 2 |
| …… | …… |
| n = k | f(k) = f(k-1)+f(k-2) |
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
''' 递归做法,复杂度太大,2^n,算法复杂度过大不饿能通过测试
# 但是逻辑实现上是没有问题的,也就是说用递归思路可以解决
if n == 0:
return 0
if n == 1:
return 1
if n>1:
# f(n)=f(n-1)+f(n-2)
num = self.Fibonacci(n-1)+self.Fibonacci(n-2)
return num
return None
'''
# 循环方式,时间复杂度n
if n == 0:
return 0
if n == 1:
return 1
if n>1:
a = 1
b = 0
ret = 0
# 总结斐波那契数列的规律为,两个数a、b的和ret
# 此时ret为这几个数中较大的数,然后令原来两个数中较大的a为b,然后,继续进行相加。依次类推。
for i in range(0, n-1):
ret = a + b
# 将和作为较大数,另原来的较大数为较小数,再进行加和
b = a
a = ret
return ret
return None
解析:
斐波那契的递推公式:F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)

如果按照递归来写,时间复杂度随着n的变化:1,2,4,8,…2的n次方,这也就意味着当n较大的时候运算量很大,可能会出现运算超时、内存超出的现象。
循环的方式思路:求a、b的和,将a、b和作为新的较大数,另原来的较大数为新的较小数,再进行加和,依次类推。
跳台阶
题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
分析:很容易想到递归方式,第一次跳1个台阶,则剩下的跳法f(n-1);第一次跳2个台阶,则剩下的跳法f(n-2);所以总的跳法有f(n)=f(n-1)+f(n-2)。(n>=3)
另外,可以通过观察发现,跳台阶的过程就是斐波那契数列,
| num台阶数 | 跳法总类 | 方式 |
|---|---|---|
| num = 0 | 0 | none |
| num = 1 | 1 | 1 |
| num = 2 | 2 | 11、2 |
| num = 3 | 3 | 111、12、21 |
| num = 4 | 5 | 1111、112、121、211、22 |
| …… | …… | …… |
通过找规律发现,num = n时, f(n) = f(n-1)+f(n-2) (n>=3)
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
# n = 0 没有
# n = 1 一种
# n = 2 两种
# n = 3 3种
# n = 4 5种
# 通过找规律发现f(n) = f(n-1)+f(n-2),当n>2的时候。满足Fabonacci,
# n = 2, f(2) = 2
# n = 1, f(1) = 1
# 或者倒推:设一共有f(n)种跳法,
# 从后往前,第一步跳1级台阶,剩下有f(n-1)种跳法;
# 第一步跳2级台阶,剩下有f(n-2)种跳法;但是n必须大于等于3(即f(n-1)和f(n-2)存在
if number < 1:
return 0
if number == 1:
return 1
if number == 2:
return 2
ret = 0
a = 1
b = 2
for i in range(3, number+1):
ret = a+b
a = b
b = ret
return ret

变态跳台阶
题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析:
| num台阶数 | 跳法总类 | 方式 |
|---|---|---|
| num = 0 | 0 | none |
| num = 1 | 1 | 1 |
| num = 2 | 2 | 11、2 |
| num = 3 | 4 | 111、12、21、3 |
| num = 4 | 8 | 1111、112、121、211、22、13、31、4 |
| …… | …… | …… |
num=n时,共有2^(n-1)跳法
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
# number = 0,没有
# number = 1,1
# number = 2,2
# number = 3,4
# number = 4,8种。
# number = n,2^(n-1)
# 因为f(n)=f(n-1)+f(n-2)+...+f(2)+f(1),
# 有f(n-1)=f(n-2)+...+f(2)+f(1)
# f(n) = 2*f(n-1)
# ......
# 其中f(1)=1,f(2)=2
# 所以f(n)= 2^(n-1)
if number == 1:
return 1
ret = 1
a = 1
for i in range(2, number+1):
ret = 2 * a
a = ret
return ret
# 或者直接一步:
# return pow(2, number-1)
解析:第一次跳1个台阶,剩下f(n-1)跳法;第一次跳2个台阶,剩下f(n-2)跳法;……第一次跳n-2个台阶,剩下f(2)种跳法;第一次跳n-1个台阶,剩下f(1)种跳法。其中f(1)=1,f(2)=2。所以有f(n)=f(n-1)+f(n-2)+…+f(2)+f(1),有f(n-1)=f(n-2)+…+f(2)+f(1),所以 f(n) =f(n-1)+f(n-1)= 2 * f(n-1)。所以f(n)=2^(n-1),其中(n>1),f(1)=1。
丑数
题目描述 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
分析:考点(数组)。
数组的概念,所谓数组,是有序的元素序列 。 若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种形式。 这些无序排列的同类数据元素的集合称为数组。(索引值从0开始)在内存中连续的空间。
数组是长度固定的,列表是可变长度的,元组也是长度固定的,但是元组的元素值不可变,数组的元素值可变,列表元素值和长度都可以改变。
栈不同于数组,不可以随意访问,只可以访问栈顶,一次只能取一个。先进后出的结构。在python中也是用列表实现。追加用append()(其他语言是push()压入)、获取栈顶用list[-1]、弹出用pop()或delete()

队列:对于栈只可以从栈顶压入或弹出。对于队列来说,可以从一边添加,另一边取出。先入先出的结构,在python中队列也使用列表实现。添加使用insert()或append()、取出使用list[-1]、pop()。

二维数组中的查找
题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
'''# 方法一:使用循环遍历查找;
# 时间复杂度:O(m*n)
for i in range(len(array)): # len(array)为二维数组行
for j in range(len(array[0])): # len(array[0])二位数组的列
if target == array[i][j]:
return True
return False'''
# 1 2 3 4
# 3 4 5 6
# 4 6 8 10
# 9 11 13 14
# 第二种:考虑右上角4,构成长方形,比较值的大小
# 时间复杂度O(m+n)
# 右上角array[i][j]的值为:value
row_count = len(array) # 行
i = 0
column_count = len(array[0]) # 列
j = len(array[0])-1
while i<row_count and j>=0:
value = array[i][j] # 依次取每行的最后一个(每行中的最大值)
if value == target:
return True
elif value>target:
j -= 1 # 如果大了就在同一列减少一点
else:
i += 1 # 如果小了就取下一行的最后一位(该行的最大值)
return False
解析:查找除了采用常规时间复杂度为m*n的遍历方法,还可以根据题目的提示进行灵活取值。
替换空格
题目描述 请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
分析:对于python字符串的替换,可以转换成列表list,直接遍历、替换列表元素的方式,使用.join()函数可以将列表转换成字符串。
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
s = list(s)
count=len(s)
for i in range(0,count):
if s[i]==' ':
s[i]='%20'
return ''.join(s) # join()可以使列表转换成字符串
用两个栈实现队列
题目描述 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
分析:考虑栈和队列的取数据方式:栈是遵循“先入后出,后入先出”的原则,队列遵循“先入先出”的规则。

# -*- coding:utf-8 -*-
class Solution:
# 定义两个栈一个用于接收一个用于输出
def __init__(self):
# 定义一个栈用于接收
self.acceptStack=[]
# 定义一个栈用于输出
self.outputStack=[]
def push(self, node):
# write code here
# push操作就是在acceptStack上append
self.acceptStack.append(node)
def pop(self):
# return xx
# 判断是否为空(必须先判断是否为空)
if self.outputStack == []:
# 如果outputStack为空就将从acceptStack中pop出的值添加到outputStack,直到acceptStack为空
while self.acceptStack != []:
self.outputStack.append(self.acceptStack.pop())
if self.outputStack != []:
# 如果outputStack不为空,那么就可以直接对outputStack做pop操作
return self.outputStack.pop()
else:
# 如果outputStack和acceptStack都为空,则返回None
return None
旋转数组的最小数字
** 题目描述** 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
分析:可以使用遍历,复杂度为O(N);或者考虑二分查找法:
二分查找法:二分查找算法(英语:binary search algorithm),也称折半搜索算法(英语:half-interval search algorithm)、对数搜索算法(英语:logarithmic search algorithm),是一种在
有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。二分查找算法在情况下的复杂度是对数时间,进行O(log n)次比较操作(n在此处是数组的元素数量,O是大O记号,log 是对数)。二分查找算法使用常数空间,无论对任何大小的输入数据,算法使用的空间都是一样的。除非输入数据数量很少,否则二分查找算法比线性搜索更快,但数组必须事先被排序。

# 二分查找代码实现
# 有序的数组就用二分查找法
def bSearch(array, target):
left = 0
right = len(array) - 1
while left <= right:
mid = (left+right)//2 # mid = (left+right) >> 1 位运算,在底层语言中移位运算比除法速度快
if array[mid] == target:
return mid
elif array[mid] < target:
left = mid + 1
else:
right = mid -1
return None
解题代码:
# 由题意可以得出,|a[mid]-a[left]|<|a[mid|-a[right]|,则有left = mid
# 或者有 a[right]>a[mid],说明最小值在左边
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
# 判断数组是否为空
if not rotateArray:
return 0
left = 0
right = len(rotateArray) - 1
while left <= right:
mid = (left + right) >> 1
if rotateArray[mid] < rotateArray[mid - 1]:
# 比左边小
return rotateArray[mid]
elif rotateArray[mid] < rotateArray[right]:
right = mid - 1
else:
left = mid + 1
return None
调整数组顺序使奇数位于偶数前面
题目描述 输入一个整数数组,实现一个函数来调整该数组中数字得顺序,使得所有得奇数位于数组得前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
分析:
方法一:新建一个空白列表用于存储计数值和偶数值,分别添加奇数项和偶数项。 方法二:考虑使用冒泡排序。
冒泡排序:它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。(时间复杂度 O(n²))

上图为冒泡排序示意图。需要遍历的数组长度每次减去1。
冒泡排序代码
def maopaoSort(array):
# 一共需要n此的循环,每一个都要找到没排好序的最大值
for i in range(len(array)):
# 将 没有排好序的数组找最大值(没排好序的数组长度每次减少1),并一直将最大值放到最顶端
for j in range(len(array) - i -1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return array
if __name__ == '__main__':
array = [9, 8, 10, 15, 7, 3, 20, 14, 2]
maopaoSort(array)
print(array)
解题代码
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
# 第一种方法
# 时间复杂的都O(n),空间复杂度O(n)
ret = []
# 先奇数添加
for i in array:
if i % 2 == 1:
ret.append(i)
# 后添加偶数
for i in array:
if i % 2 == 0:
ret.append(i)
return ret
包含min函数的栈
题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。
分析:

解题代码
# -*- coding:utf-8 -*-
class Solution:
# 定义一个栈
def __init__(self):
self.stack = []
# 新建一个数组用来保存最小值数组
self.minValue = []
# Push和pop同时对两个数组操作
def push(self, node):
# write code here
self.stack.append(node)
if self.minValue:
if self.minValue[-1] > node:
self.minValue.append(node)
else:
self.minValue.append(self.minValue[-1])
else:
self.minValue.append(node)
def pop(self):
# write code here
if self.stack == []:
return None
self.minValue.pop()
return self.stack.pop()
def top(self):
# write code here
if self.stack == []:
return None
return self.stack[-1]
def min(self):
# write code here
if self.minValue == []:
return None
return self.minValue[-1]
栈的压入、弹出序列
题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序,假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

分析:
首先按需要有一个栈(列表) 按照pushV的方式压入栈 弹出的时候需要循环判断是否需要弹出 判断需要弹出的情况的条件,压入栈的顶部和弹出栈的数据相等
解题代码
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
# 首先按需要有一个栈,列表
# 按照pushV的方式压入栈
# 弹出的时候需要循环判断是否需要弹出
# 判断需要弹出的情况的条件,压入栈的顶部和弹出栈的数据相等
if pushV == [] or len(pushV) != len(popV):
return None
stack = []
index = 0
for item in pushV:
stack.append(item)
# 循环判断是否弹出,以及stack是否为空
while stack and stack[-1] == popV[index]:
stack.pop()
index += 1
if stack == []:
return True
else:
return False
# return True if stack == [] else False
从头到尾打印链表
题目描述
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
分析:
聊表可以存储非连续、非顺序、不定长度的数据 。指针位可以指向下一个元素的地址;链表的最后一个元素是None;链表分为:单链表、循环链表、双链表。python的


解题代码:
class Solution:
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# 返回从尾部到头部的列表值序列,例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
ret = []
pTmp = listNode
while pTmp:
# 使用insert(0)往0的索引位置添加元素
ret.insert(0, pTmp.val)
pTmp = pTmp.next
return ret
链表中到数第k个结点
题目描述
输入一个链表,输出该链表中倒数第k个结点。
分析:
判断边界条件:如果k比链表长度大,直接返回None
如果k小于链表的长度,我们可以定义两个变量,这两个变量中间间隔k,一个存储长度为k的头部指针,一个存储为尾的指针。当k的值小于链表长度的时候,头部指针不为None的时候,头部指针依次取链表head的next,尾部指针也要取head的next,当头部指针firstPoint到达链表head的末尾的None的时候,这时的尾部指针secondPoint就是链表head中的倒数第k个结点;当k的值大于链表长度的时候,当头部指针依次增加到None的时候再next就会报错,这时要在头部指针firstPoint为None的时候集时返回None。
解题代码
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
# 判断边界条件:如果k比链表长度大,直接返回None
# 如果k小于链表的长度,我们可以定义两个变量,这两个变量中间间隔k
# 定义两个变量,一个存储长度为k的头部指针,一个存储为尾的指针
# head为链表结构
firstPoint = head
secondPoint = head
for i in range(k):
# 先判断是否等于None
if firstPoint == None:
return None
firstPoint = firstPoint.next
while firstPoint != None:
firstPoint = firstPoint.next
secondPoint = secondPoint.next
return secondPoint
反转链表
题目描述
输入一个链表,反转链表后,输出新链表的表头。
分析:将现有的头换成尾,尾部的next为空,从第二个node开始时,循环将next指向前一个

解题代码
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
# 将现有的头换成尾,尾部的next为空,从第二个node开始时,循环将next指向前一个
# 需要一直有一个指针指向还没有反转的链表的头部
if pHead == None:
# 空链表
return None
if pHead.next == None:
# 只有一个结点的链表
return pHead
# 定义正向的链表中3个连续结点
leftPointer = pHead
midPointer = pHead.next
rightPointer = midPointer.next
# 定义反向特殊结点
leftPointer.next = None
while rightPointer != None:
# 相当于依次取连续3个结点,直到结束rightPointer为空
# 这时应该返回midPointer才是新链表的表头
midPointer.next = leftPointer
# midPointer成为新的leftPointer,在这里的原mid.next也成为left.next
leftPointer = midPointer
# rightPointer成为新的midPointer,在这里的原right.next也成为mid.next
midPointer = rightPointer
# 新rightPointer.next的指向为先前的rightPointer
rightPointer = rightPointer.next
# 这里为rightPointer为2个结点的的情况,交换前两个节点
midPointer.next = leftPointer
return midPointer
合并两个排序的链表
题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
分析:
情况分为:
1、当两个链表有一个为空的时候,直接返回另一个;
2、当链表不为空的时候,合并后的链表指针为原来排序的两个链表中的较小的那个,然后依次比较较小的next指针的val和较大的对应的val,取较小的那个作为合并链表的新指针。循环指导两个排序后的链表指向None,这时,将非空的那个链表添加到新的合并链表即可。

解题代码
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
# 一个新的链表表头指针,取值为两个排序的链表表头中较小的一个
newHead = pHead1 if pHead1.val < pHead2.val else pHead2
# pHead1和pHeead2的临时指针
pTmp1 = pHead1
pTmp2 = pHead2
if newHead == pHead1:
# 如果pHead1为较小的一个,那么则指向pHead1的next为临时指针pTmp1
pTmp1 = pHead1.next
else:
# 如果pHead2为较小的一个,那么则指向pHead2的next为临时指针pTm篇
pTmp2 = pHead2.next
# 一共四个指针,第四个为当前临时指针的前一个
previousPointer = newHead
# 当pTmp1和pTmp2都不为空的时候进行循环
while pTmp2 and pTmp1:
if pTmp1.val <= pTmp2.val:
previousPointer.next = pTmp1
# 向next方向取值
previousPointer = pTmp1
pTmp1 = pTmp1.next
else:
previousPointer.next = pTmp2
previousPointer = pTmp2
pTmp2 = pTmp2.next
# 当pTmp1先变为空的时候,将剩余的pTmp2都放在后面排序
if pTmp1 == None:
previousPointer.next = pTmp2
# 当pTmp2先变为空的时候,将剩余的pTmp1都放在后面排序
else:
previousPointer.next = pTmp1
return newHead
复杂链表的复制
题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
分析:
1、边界条件 if pHead == None: return None
2、如果链表不为空:
如下图,复制一个node,实现复制体node的next指向,使原始链表头pTmp=pHead和node 同时指向pTmp.next,断开pTmp对于pTmp.next的指向,将pTmp指向复制体node,然后然后指定新的pTmp,pTmp = node.next。向后依次循环。
接下来实现复制体node的random的指向:因为pTmp.next.random = pTmp.random.next实现复制体node的random指向;向后移动两次pTmp = pTmp.next.next。
最后,断开原来的node和新的node之间的链接

解题代码
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
# import copy
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# 方法一:深拷贝
# ret = copy.deepcopy(pHead) # 深拷贝可以
# ret = copy.copy(pHead) # 浅拷贝不行
# 方法二:链表拷贝
if pHead == None:
return None
# 以下是pHead非空的情况
pTmp = pHead
while pTmp:
# 复制一个一样的node结点,并且添加到之前链表的每一个node后面
node = RandomListNode(pTmp.label)
# 指向同一个next
node.next = pTmp.next
# 断开前一个本体的pTmp结点指针指向复制体node
pTmp.next = node
# 指向下一个需要复制的结点node
pTmp = node.next
#########################################
# A.next.random = a.random.next
# 实现新建的node的random的指向
pTmp = pHead
while pTmp:
if pTmp.random:
# pTmp.random不为空的时候,为空的时候结束指向设定循环
pTmp.next.random = pTmp.random.next
pTmp = pTmp.next.next
########################################
# 断开原来的node和新的node之间的链接
pTmp = pHead
newHead = pHead.next
pNewTmp = pHead.next
while pTmp:
# print(pTmp.label)
pTmp.next = pTmp.next.next
if pNewTmp.next:
pNewTmp.next = pNewTmp.next.next
# 取下一个结点
pNewTmp = pNewTmp.next
# 取下一个结点
pTmp = pTmp.next
# 返回复制链表的head
return newHead