本系列文集将记录我在牛客网上刷剑指Offer试题中的思考和解答。
1. 二维数组中的查找
直接遍历一遍数组是最容易想到的，代码如下：
def find(target, array):
for i in array:
if i and target <= i[-1]:
for j in i:
if target == j:
return True
return False
但既然是顺序数组，用二分查找应该比较好，代码如下：
#在本地测试没问题，牛客网上超时了……
def find(target, array):
m = len(array)
n = len(array[0])
high = m * n - 1
low = 0
while high >= low:
mid = (high - low) // 2
if array[mid // n][mid % n] == target:
return True
elif array[mid // n][mid % n] > target:
high = mid - 1
else:
low = mid
return False
2. 字符替换
一瞬间就想到了字符串的replace方法了,不过我觉得还用通用方法好一点
def replaceSpace(s):
result = ''
for i in s:
if i != ' ':
result += i
else:
result += '%20'
return result
# return s.replace(" ", "%20")用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):
result = []
while listNode:
result.append(listNode.val)
listNode = listNode.next
return result[::-1]
4.重建二叉树
根据二叉树的特点，我们可以知道在前序遍历中第一个元素是根节点如果根节点有左子叶的话那么第二个元素相当于是它的左子叶的根节点。在中序遍历中，根节点左边的所有元素都是它的左子叶，右边的都是它的右子叶
# -*- 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 pre and tin:
root = TreeNode(pre.pop(0))
index = tin.index(root.val)
root.left = self.reConstructBinaryTree(pre, tin[:index])
root.right = self.reConstructBinaryTree(pre, tin[index + 1:])
return root
return None
5. 用两个栈实现队列
栈是后进先出，队列是先进先出
# -*- 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):
# return xx
if self.stack2==[]:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
return self.stack2.pop()
6. 旋转数组的最小数字
可以用min()但没必要。
遍历一遍对比相邻两个数的大小。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 1:
return rotateArray[0]
for i in range(len(rotateArray)):
if rotateArray[i]>rotateArray[i+1]:
return rotateArray[i+1]
return 0
同时旋转数组可以看成一个顺序数组的变形，所以也可以用二分查找法
def minNumberInRotateArray(rotateArray):
# write code here
# return min(rotateArray)
high = len(rotateArray) - 1
low = 0
while rotateArray and high > low:
mid = (high + low) // 2
if rotateArray[mid] <= rotateArray[high]:
high = mid
else:
low = mid + 1
return rotateArray[low]
7. 斐波那契数列
看题目给出相关知识点是递归，于是用递归实现了一遍，但用递归实现的话时间复杂度直接爆炸应该是O(1.68^n), n=39时的话直接报超时了
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
result = [0, 1]
if n < len(result):
return result[n]
for i in range(n - 1):
result.append(result[-1] + result[-2])
return result[n]
8. 跳台阶
可以看成斐波那契数列的变种，不过这次用while实现一遍
class Solution:
def jumpFloor(self, number):
# write code here
#台阶数不应该<=0
res=[1,1]
while len(res)<=number:
res.append(res[-1]+res[-2])
return res[number]
不过还是觉得递归比较好理解一点
这道题可以看成
先跳一阶+f(n-1)的跳法+先跳二阶+f(n-2)的跳法
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
if number == 2:
return 2
return jumpFloor(number-1)+jumpFloor(number-2)
9. 变态跳台阶
又成了找规律的题了
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number <= 0:
return 0
else:
return 2**(number-1)
10. 矩阵覆盖
又是斐波那契变形题……
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number==0:
return 0
if number==1:
return 1
a,b=1,1
while number>1:
a,b=b,a+b
number-=1
return b
11. 二进制数中1的个数
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
return sum([(n>>i & 1) for i in range(0,32)])
