不忘初心，
牢记使命。

牛客网剑指offer专题python解答JZ1---JZ12持续刷题中

2021-10-02 大聪明 0评论 32 0喜欢

@[TOC]

JZ1二维数组中的查找

给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

解题思路
时间复杂度 O(M + N)，空间复杂度 O(1)
若逐行或逐列用二分法遍历,效率太慢了,我们希望可以以对角线的方向去遍历,
对角线方向有4种:

  1. 从左上角向右下角出发:往左往下的数都是比当前大的,不可用二分法,放弃;
  2. 从右上角向左下角出发: 往左的数变小,往下的数增大,可用二分法;
  3. 从左下角向右上角出发:往上的数变小,往右的数增大,可用二分法;
  4. 从右下角向左上角出发:往上的数变小,往左的数变小,不可用二分法,放弃;

这里实现第3种方法

img

# -*- 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}的链表如下图:

img

返回一个数组为[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}，则重建出如下图所示。

img

提示:

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种不同的覆盖方法(从同一个方向看)：

img

输入描述：

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

来了解下快速幂方法：

image-20210817172233565

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))

再来了解些非递归的快速幂：

image-20210817173412899

# -*- 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
© 著作权归作者所有,欢迎转载，转载请说明出处：大聪明,谢谢理解！
博客
最后编辑：2021-10-02
上一篇 下一篇

发表评论 取消回复

电子邮件地址不会被公开。

请输入正确格式的qq邮箱
请输入以http或https开头的URL,格式如:https://libo_sober.top