剑指offer刷题(1-10) python-python黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

听爸爸的话

1123

文章

884217

访问

+关注

分类

暂无分类

日期归档

2023-05(2)

2023-06(3)

剑指offer刷题(1-10) python

发布于2019-12-01 12:25 阅读(1214) 评论(0) 点赞(16) 收藏(2)

在线做题链接牛客网点击进入

面试题1.二维数组中查找

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

class Solution:
    # array 二维列表
    def Find(self, target, array):
        '''
        python中可以直接用in来进行逐行判断
        :param target: 
        :param array: 
        :return: True or False
        '''
        for i in array:
            if target in i:
                return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13

面试题2.替换空格

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

# 直接使用python中的字符串替换方法replace即可
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        return s.replace(" ","%20")
1
2
3
4
5

面试题3.从尾到头打印链表

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

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

面试题4.重建二叉树

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if len(pre) == 0:
            return None
        root = TreeNode(pre[0])
        x = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:x+1],tin[0:x])
        root.right = self.reConstructBinaryTree(pre[x+1:],tin[x+1:])
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

面试题5.用两个栈实现队列

# 思路，用两个列表模拟栈,后进先出，栈1用来取数据，栈2用来添加数据，
# 当栈1没有数据时，将栈2全部数据添加到栈1中
# 注意，一定要在栈1没有数据时才将栈2添加
class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        self.stack2.append(node)
    def pop(self):
        if self.stack1:
            return self.stack1.pop()
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        return self.stack1.pop()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

面试题6.旋转数组的最小数字

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

# 题目意思就是在一个数组中找最小的值，一个min()就能出结果，
#但是很明显这个数组是一个局部有序的数组，考察的肯定没有这么简单，
#所以用二分法
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        left=0
        right=len(rotateArray)-1
        while left<right:
            if rotateArray[left]<rotateArray[right]:
                return rotateArray[left]
            mid = left+(right-left)//2
            if rotateArray[left]<rotateArray[mid]:     # 左边有序取右边
                left = mid+1
            elif rotateArray[mid]<rotateArray[right]:  # 右边有序取左边
                right = mid
            else:
                left+=1
        return rotateArray[left]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

面试题7.斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

# 两种方法，方法一:递归求，方法二:使用斐波那契通项公式
class Solution:
    def Fibonacci(self, n):
        x = 1/(5**0.5)
        x2 = ((1+5**0.5)/2)**n-((1-5**0.5)/2)**n
        return int(x*x2)
1
2
3
4
5
6

补充斐波那契通项公式

F(n) = $\frac{\sqrt{5}}{5}[\big(\frac{1+\sqrt{5}}{5}\big)^n-\big(\frac{1-\sqrt{5}}{5}\big)^n]$

面试题8.跳台阶

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

# 思路：1级时1种，2级时2种，当n>2时，每次跳法有两种不同的选择，
# 一是第一次跳了1级，故后面的跳法为f(n-1)，二是第一次跳了2级，
# 故后面的跳法为f(n-2)。，所以本题也是斐波那契数列，第一个数字为1
class Solution:
    def jumpFloor(self, number):
        # write code here
        x = 1/(5**0.5)
        x2 = ((1+5**0.5)/2)**(number+1)-((1-5**0.5)/2)**(number+1)
        return int(x*x2)
1
2
3
4
5
6
7
8
9

面试题9.变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路
f(1) = 1
f(2) = f(2-1) + f(2-2) // 第一次跳一阶，第一次跳二阶
f(3) = f(3-1) + f(3-2) + f(3-3) // 第一次跳一阶，第一次跳二阶，第一次跳三阶
f(n) = f(n-1) + f(n-2) +…+f(n-n)
转换为数学公式为
f(1) = $2^0$
f(2) = $2^0$ +1 = $2^0$ + $2^0$ = $2^1$
f(3) = $2^1$ + $2^0$ + 1 = $2^1$ + $2^0$ + $2^0$ = $2^1$ + $2^1$ = $2^2$
…
f(n) = $2^{n-2}$ + $2^{n-3}$ +… $2^{n-n}$ +1 = $2^{n-1}$

class Solution:
    def jumpFloorII(self, number):
        return 2**(number-1)
1
2
3

面试题10.矩形覆盖

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

# 仍旧是斐波那契额数列
class Solution:
    def rectCover(self, number):
        # write code here
        if number == 0:
            return 0
        x = 1/(5**0.5)
        x2 = ((1+5**0.5)/2)**(number+1)-((1-5**0.5)/2)**(number+1)
        return int(x*x2)
1
2
3
4
5
6
7
8
9