⽜客⽹编程题python,⽜客⽹【剑指Offer_编程题】
（Python2.7.3）
1. ⼆维数组中的查
题⽬描述
在⼀个⼆维数组中(每个⼀维数组的长度相同)，每⼀⾏都按照从左到右递增的顺序排序，每⼀列都按照从上到下递增的顺序排序。请完成⼀个函数，输⼊这样的⼀个⼆维数组和⼀个整数，判断数组中是否含有该整数。
代码
# -*- coding:utf-8 -*-
class Solution:
# array ⼆维列表
def Find(self, target, array):
# write code here
rows = len(array) - 1
cols = len(array[0]) - 1
i = rows
j = 0
while i >= 0 and j <= cols:
if target < array[i][j]:
i -= 1
elif target > array[i][j]:
j += 1
else:
return Truepython 定义数组
return False
思路
2. 替换空格
题⽬描述
请实现⼀个函数，将⼀个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为
We%20Are%20Happy。
代码
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
r = ''
for i in range(len(s)):
if s[i] == ' ':
r = r + '%20'
else:
r = r + s[i]
return r
思路
3. 从尾到头打印链表
题⽬描述
输⼊⼀个链表，按链表值从尾到头的顺序返回⼀个ArrayList。
代码
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
l = []
head = listNode
while head:
l.insert(0, head.val)
head =
return l
思路
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:
return None
if len(pre) == 1:
return TreeNode(pre[0])
else:
flag = TreeNode(pre[0])
flag.left = ConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])]) flag.right = ConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:] ) return flag
思路
5. ⽤两个栈实现队列
题⽬描述
⽤两个栈来实现⼀个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
代码
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
if self.stack2==[]:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
return self.stack2.pop()
思路
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
if len(rotateArray) == 0:
return 0
pre = 0
for num in rotateArray:
if num < pre :
return num
pre = num
return rotateArray[0]
思路
7. 斐波那契数列
题⽬描述
⼤家都知道斐波那契数列，现在要求输⼊⼀个整数n，请你输出斐波那契数列的第n项(从0开始，第0项为0)。
n<=39
代码
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
return 0
s = []
s.append(1)
s.append(1)
for i in range(2, n):
s.append(s[i-1] + s[i-2])
return s[n-1]
思路
8. 跳台阶
题⽬描述
⼀只青蛙⼀次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上⼀个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。代码
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
s = []
s.append(1)
s.append(1)
for i in range(2, number+1):
s.append(s[i-1] + s[i-2])
return s[number]
思路
9. 变态跳台阶
题⽬描述
⼀只青蛙⼀次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上⼀个n级的台阶总共有多少种跳法。
代码
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
s = []
s.append(1)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。