牛客网:剑指Offer_编程题python2.7

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
row = len(array)
col = len(array[0])
i = 0
j = col-1
while i<row and j>(-1):
if array[i][j] == target:
return True
elif array[i][j] > target:
j = j-1
else:
i = i+1
return False

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


1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
l = s.split(' ')
if len(l) == 1:
return s
s = l[0]
for i in range(1,len(l)):
s = s+'%20'+l[i]
return s

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- 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
l = []
while listNode:
l.insert(0, listNode.val)
listNode = listNode.next
return l

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- 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:
res = TreeNode(pre[0])
res.left =self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[: tin.index(pre[0])])
res.right = self.reConstructBinaryTree(pre[tin.index(pre[0]) + 1: ], tin[tin.index(pre[0]) + 1: ])
return res

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stock1 = []
self.stock2 = []
def push(self, node):
self.stock1.append(node)
# write code here
def pop(self):
if self.stock2 == []:
if self.stock1 == []:
return None
else:
for i in range(len(self.stock1)):
self.stock2.append(self.stock1.pop())
return self.stock2.pop()

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

方法一:直接遍历,时间复杂度大,没通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
else:
sum = 0
for i in range(len(rotateArray)):
if rotateArray[i] >= rotateArray[i+1]:
break
else:
sum = sum+1
return rotateArray[sum+1]

方法二:采用二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
else:
p1 = 0
p2 = len(rotateArray)-1
mid = p1
while rotateArray[p1]>=rotateArray[p2]:
if p2 - p1 ==1:
mid = p2
break
mid =(p1+p2)>>1 #
if rotateArray[mid]>=rotateArray[p1]:
p1 = mid
elif rotateArray[mid] <= rotateArray[p2]:
p2 =mid
return rotateArray[mid]

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

递归,时间复杂度大

1
2
3
4
5
6
7
8
9
10
11
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n <= 0:
return 0
elif n == 1:
return 1
else:
s = self.Fibonacci(n-1)+self.Fibonacci(n-2)
return s

循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
a = 0
b = 1
if n <= 0:
return a
elif n == 1:
return b
else:
while n > 1:
a, b = b, a+b
n = n-1
return b

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

这种问题一般是有规律的,跳1级台阶,只有1种方法;跳2级台阶,有2种方法;跳3级台阶,有3种方法;跳4级台阶,有5种方法,依次下去,跳一个n级的台阶的方法数是跳n-1级台阶的方法数与跳n-2阶台阶的方法数的总和。这种思路可以用逆推去想,要跳上一个n级台阶,可以从n-1级台阶跳1级,也可以从n-2级台阶跳2级,这就相当于跳上n-1级台阶的方法加上跳上n-2级台阶的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
elif number == 2:
return 2
else:
a = 1
b = 2
for i in range(3,number+1):
a, b = b, a+b
return b

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

跳n级台阶,可以从n-1级跳上来,也可以从n-2级跳上来,从n-3级跳上来,依次下去,从第1级跳上去,或直接跳上去,所以,跳n级台阶的方法数相当于其它所有台阶数的方法的总和再加上从0级跳上去,表达式为 f(n) = f(n-1) + f(n-2) +…+ f(2) + f(1) + 1 = 2*f(n-1)。

1
2
3
4
5
6
7
8
9
class Solution:
def jumpFloorII(self, number):
# write code here
if number == 0:
return 1
elif number == 1:
return 1
else:
return 2*self.jumpFloorII(number-1)

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

类似于斐波那契数列

1
2
3
4
5
6
7
8
9
10
class Solution:
def rectCover(self, number):
# write code here
if number <3:
return number
else:
a, b = 1, 2
for i in range(3,number+1):
a, b = b, a+b
return b

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

1
2
3
4
5
6
7
8
class Solution:
def NumberOf1(self, n):
# write code here
if n>=0:
number = bin(n).count('1')
return number
else:
return bin(n & 0xffffffff).count('1')