不忘初心,
牢记使命。

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

2021-10-02 大聪明 0评论 36 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

发表评论 取消回复

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

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