剑指offer:Python代码(持续更新)
题目的罗列顺序依据的是牛客网上的题库:https://www.nowcoder.com/ta/coding-interviews。
代码是我刷题时的答案,均已在牛客网上运行通过。
目录
1. 数组:二维数组中的查找
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
# -*- coding:utf-8 -*-
# import numpy as np
class Solution:
# array 二维列表
# def Find(self, target, array):
def Find(self, target, array):
# write code here
self.target = target
self.array = array
c = 0
# for i in range(obj.array.shape[0]):
# for j in range(obj.array.shape[1]):
for i in range(len(self.array)):
for j in range(len(self.array[0])):
if self.array[i][j] == self.target:
c += 1
if c == 0:
return False
else:
return True
2. 字符串:替换空格
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy。则经过替换之后的字符串为We%20Are%20Happy。
方法1:
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self,s):
# write code here
self.s = s
s_replace = ''
for i in range(len(self.s)):
if self.s[i] == ' ':
s_replace = s_replace + '%20'
else:
s_replace = s_replace + self.s[i]
return s_replace
方法2:
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self,s):
# write code here
self.s = s
s_replace = self.s.replace(' ', '%20')
return s_replace
3. 从头到尾打印链表
输入一个链表,从尾到头打印链表每个节点的值。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回从尾部到头部的列表值序列,例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
list_t2h = []
head = listNode
while head:
list_t2h.append(head.val)
head = head.next
list_t2h.reverse()
return list_t2h
4 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
二叉树的遍历的基本知识见文章。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0 or len(tin) == 0:
return None
else:
root = TreeNode(pre[0])
p_root = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:p_root+1], tin[:p_root])
root.right = self.reConstructBinaryTree(pre[p_root+1:], tin[p_root+1:])
return root
5 用两个栈实现队列
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
栈与队列的区别见文章。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node): # 堆栈与队列的push是一致的,都在顶部操作
# write code here
self.stack1.append(node)
def pop(self): # 堆栈的POP也在顶部操作,但是队列的POP在底部操作部
# return xx
while len(self.stack1)!=0: # 先把栈1的内容压入栈2
self.stack2.append(self.stack1.pop()) # 这里调用的是python自带的pop函数,不是递归
pop_out = self.stack2.pop() # 弹出栈2的顶
while len(self.stack2)!=0: # 最后把栈2的内容再折回到栈1,栈2空
self.stack1.append(self.stack2.pop())
return pop_out
6 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
self.rotateArray = rotateArray
if len(self.rotateArray) == 0:
return 0
else:
self.rotateArray = sorted(self.rotateArray)
return self.rotateArray[0]
7 斐波那契数列
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
elif n == 1:
return 1
else:
p1 = 0
p2 = 1
for i in range(2, n+1): # 依次取2,3,4,5,...,n
out = p1+p2
p1 = p2
p2 = out
return out
8 跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
# -*- coding:utf-8 -*-
import math
class Solution:
def jumpFloor(self, number):
# write code here
n = number
if n % 2 != 0:
count = 1
for i in range(1, int(math.floor(n / 2))+1):
n2 = i
n1 = n - i * 2
# a = n1!
a = 1
for j in range(1, n1 + 1):
a = a * j
# b = n2!
b = 1
for k in range(1, n2 + 1):
b = b * k
# c = (n1+n2)!
c = 1
for w in range(1, n1 + n2 + 1):
c = c * w
count += int(c/(a*b))
return count
else:
count = 2
for i in range(1, int(n/2)):
n2 = i
n1 = n - i * 2
# a = n1!
a = 1
for j in range(1, n1 + 1):
a = a * j
# b = n2!
b = 1
for k in range(1, n2 + 1):
b = b * k
# c = (n1+n2)!
c = 1
for w in range(1, n1 + n2 + 1):
c = c * w
count += int(c / (a * b))
return count
看了剑指offer书之后,发现这就是一个菲波那切数列问题:
上一篇: 剑指Offer题解(持续更新)
下一篇: 剑指offer(持续更新)
推荐阅读
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
【Python】剑指offer 14:剪绳子
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
剑指Offer编程题(python)——链表
-
【剑指 Offer-python】 03. 数组中重复的数字
-
剑指 offer代码最优解析——面试题35第一个只出现一次的字符
-
leetcode 160剑指offer面试题52. 两个链表的第一个公共节点(python3)
-
leetcode 面试题32 (剑指offer)- II. 从上到下打印二叉树 II(python3)
-
leetcode 113 剑指offer 面试题34. 二叉树中和为某一值的路径(python3)
-
剑指offer面试题68 - I. 二叉搜索树的最近公共祖先(python)