@[TOC]
JZ1二维数组中的查找
给定一个二维数组,其每一行从左到右递增排序,从上到下也是递增排序。给定一个数,判断这个数是否在该二维数组中。
解题思路
时间复杂度 O(M + N),空间复杂度 O(1)
若逐行或逐列用二分法遍历,效率太慢了,我们希望可以以对角线的方向去遍历,
对角线方向有4种:
- 从左上角向右下角出发:往左往下的数都是比当前大的,不可用二分法,放弃;
- 从右上角向左下角出发: 往左的数变小,往下的数增大,可用二分法;
- 从左下角向右上角出发:往上的数变小,往右的数增大,可用二分法;
- 从右下角向左上角出发:往上的数变小,往左的数变小,不可用二分法,放弃;
这里实现第3种方法

# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
line = len(array)
col = len(array[0])
i = line - 1
j = 0
while i >= 0 and j < col:
if array[i][j] == target:
return True
elif array[i][j] < target:
j += 1
else:
i -= 1
JZ2 替换空格
简单 通过率:54.61% 时间限制:1秒 空间限制:256M
描述
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
示例1
输入:
"We Are Happy"
返回值:
"We%20Are%20Happy"
str.replace(old_str, new_str) -> new_str
# -*- 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
return s.replace(' ', '%20')
python3函数注释:
def foo(a: expression, b: expression = 5) -> expression:
...
JZ3 从尾到头打印链表
描述
输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。
如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]
0 <= 链表长度 <= 10000
示例1
输入:
{1,2,3}
返回值:
[3,2,1]
示例2
输入:
{67,0,24,58}
输出
[58,24,0,67]
# -*- 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
arr = []
head = listNode
while head:
arr.append(head.val)
head = head.next
arr.reverse()
return arr
JZ4 重建二叉树
描述
给定某二叉树的前序遍历和中序遍历,请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。

提示:
1.0 <= pre.length <= 2000
2.vin.length == pre.length
3.-10000 <= pre[i], vin[i] <= 10000
4.pre 和 vin 均无重复元素
5.vin出现的元素均出现在 pre里
6.只需要返回根结点,系统会自动输出整颗树做答案对比
示例1
输入:
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值:
{1,2,3,4,#,5,6,#,7,#,#,8}
说明:
返回根节点,系统会输出整颗二叉树对比结果
示例2
输入:
[1],[1]
返回值:
{1}
示例3
输入:
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值:
{1,2,5,3,4,6,7}
递归:
# -*- 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, vin):
# write code here
if len(pre) == 0:
return None
root = TreeNode(pre[0])
pos = vin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:pos+1], vin[:pos])
root.right = self.reConstructBinaryTree(pre[pos+1:], vin[pos+1:])
return root
JZ5 用两个栈实现队列
描述
用两个栈来实现一个队列,分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。
示例:
输入:
["PSH1","PSH2","POP","POP"]
返回:
1,2
解析:
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素,先进先出=>返回1
"POP“:代表删除一个元素,先进先出=>返回2
示例1
输入:
["PSH1","PSH2","POP","POP"]
返回值:
1,2
# -*- 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:
return self.stack2.pop()
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
if self.stack2:
return self.stack2.pop()
JZ6 旋转数组的最小数字
描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
示例1
输入:
[3,4,5,1,2]
返回值:
1
主要考二分查找,暴力的话很简单
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
return min(rotateArray)
二分查找
JZ7 斐波那契数列
描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。
n\leq 39n≤39
示例1
输入:
4
返回值:
3
递归超时:
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
if n == 1 or n == 2:
return 1
return self.Fibonacci(n-1) + self.Fibonacci(n-2)
for遍历通过:
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n < 2:
return n
f0 = 0
fn = 1
for i in range(2,n+1):
fn = f0 + fn
f0 = fn - f0
return fn
JZ8 跳台阶
描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
示例1
输入:
2
返回值:
2
示例2
输入:
7
返回值:
21
排列组合:
3个1和2个2的不同组合数为:
(3+2)! / (3! * 2!) = 10个
# -*- coding:utf-8 -*-
class Solution:
def f(self, n):
res = 1
for i in range(2, n+1):
res *= i
return res
def jumpFloor(self, number):
# write code here
total = 1
two = 0
while number - 2 >= 0:
number -= 2
two += 1
total += self.f(number+two) // (self.f(number) * self.f(two))
return total
上边的虽然也过了,但不是面试官想要的,其实这也是一个斐波那契数列问题:
假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶,下一步有2中可能,一种走到第n-1个台阶,一种是走到第n-2个台阶。所以f[n] = f[n-1] + f[n-2].
那么初始条件了,f[0] = f[1] = 1。
所以就变成了:f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1,目标求f[n]
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number == 0 or number == 1:
return number
a = 1
n = 1
for i in range(2,number+1):
n = a + n
a = n - a
return n
JZ9 跳台阶扩展问题
描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
示例1
输入:
3
返回值:
4
每个台阶可以看作一块木板,让青蛙跳上去,n个台阶就有n块木板,最后一块木板是青蛙到达的位子,
必须存在,其他 (n-1) 块木板可以任意选择是否存在,则每个木板有存在和不存在两种选择,(n-1) 块木板
就有 [2^(n-1)] 种跳法,可以直接得到结果。
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 2 ** (number-1)
JZ10 矩形覆盖
描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,从同一个方向看总共有多少种不同的方法?
比如n=3时,2*3的矩形块有3种不同的覆盖方法(从同一个方向看):

输入描述:
2*1的小矩形的总个数n
返回值描述:
覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)
示例1
输入:
0
返回值:
0
示例2
输入:
1
返回值:
1
示例3
输入:
4
返回值:
5
仍然是寻找递推公式,和斐波那契数列几乎无差别:
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0 or number == 1 or number == 2:
return number
f1 = 1
fn = 2
for i in range(3, number+1):
fn = f1 + fn
f1 = fn - f1
return fn
JZ11 二进制中1的个数
描述
输入一个整数,输出该数32位二进制表示中1的个数。其中负数用补码表示。
示例1
输入:
10
返回值:
2
python中负数的补码:
n = 2 ** 32 + n
正数和0都很好处理,32位加前导也是0,没有1在影响。负数就不好办了,原码32位加了前导0后变补码就为1了,要记录下来个数,所以要用上边的负数补码方式处理一下
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
if n == 0:
return 0
elif n > 0:
return bin(n).count('1')
else:
n = 2 ** 32 + n
return bin(n).count('1')
JZ12 数值的整数次方
描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0。不得使用库函数,同时不需要考虑大数问题,也不用考虑小数点后面0的位数。
示例1
输入:
2.00000,3
返回值:
8.00000
复制
示例2
输入:
2.10000,3
返回值:
9.26100
示例3
输入:
2.00000,-2
返回值:
0.25000
说明:
2的-2次方等于1/4=0.25
python直接解,当然达不到做题的目的
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
return base ** exponent
来了解下快速幂方法:

def q_power(base, n):
if n == 0:
return 1.0
res = q_power(base, n//2)
if n & 1: # 奇数
return res * res * base
else:
return res * res
def power(base, n):
if n < 0:
n = -n
base = 1 / base
return q_power(base, n)
print(power(2.1000, 3))
再来了解些非递归的快速幂:

# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
if exponent < 0:
exponent = -exponent
base = 1/base
x = base
res = 1.0
while exponent:
if exponent & 1:
res *= x
x *= x
exponent >>= 1
return res