devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

python剑指offer整理（自用）_有一个长度n的数组,里面的数都是[0,n]的整数。只有一个数字出现了多次,找出这

作者：很楠不爱3 | 2024-06-09 16:49:26

赞

踩

有一个长度n的数组,里面的数都是[0,n]的整数。只有一个数字出现了多次,找出这

剑指offer—python

数组

JZ3数组中重复的数字(简单)

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000 0≤n≤10000

进阶：时间复杂度O(n) ，空间复杂度O(n)

示例1

输入：

[2,3,1,0,2,5,3]

  • 1

返回值：

2

  • 1

说明：

方法1

#step 1: 遍历数组，遇到数组元素与下标相同的不用管
#step 2: 遇到数组元素与下标不同，就将其交换到属于它的位置，交换前检查那个位置是否有相同的元素，若有则重复。
#step 3:遍历结束完全交换也没重复，则返回-1.
class solution:
    def swap(self, numbers: List[int], a: int, b: int):
        temp = numbers[a]
        numbers[a] = numbers[b]
        numbers[b] = temp
        
    def duplicate(self , numbers: List[int]) -> int:
        L = len(numbers)
        for i in L:
            if numbers[i] == i:
                continue
            else:
                if numbers[i] == numbers[numbers[i]]:
                    return numbers[i]
                else:
                    self.swap(numbers, i, numbers[i])
                    i -= 1
        return -1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

JZ4二维数组中的查找(简单)

描述

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

[ [1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤5000≤n,m≤500 ， 矩阵中的值满足 0≤val≤1090≤val≤109
进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)

示例1

输入：

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

  • 1

返回值：

true

  • 1

说明：

存在7，返回true   

  • 1

方法1

class Solution:
    def Find(self, target:int, array: List[List[int]]) -> bool:
        if not array:
            return False
        row, col = 0, len(array[0])-1
        
        while row <= len(array)-1 and col >= 0:
            if array[row][col] == target:
                return True
            elif array[row][col] <= target:
                row += 1
            else:
                col -= 1
        return False

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

JZ5替换空格(简单)

描述

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。

例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

数据范围:0≤len(s)≤1000 0≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。

示例1

输入：

"We Are Happy"

  • 1

返回值：

"We%20Are%20Happy"

  • 1
class Solution:
    def replaceSpace(self , s: str) -> str:
        res = ""
        for _ in s:
            if _ != ' ':
                res += _
            else:
                res += "%20"
        return res


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

JZ6从尾到头打印链表(简单)

描述

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

img

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

示例1

输入：

{1,2,3}

  • 1

返回值：

[3,2,1]

  • 1

方法1

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        if not listNode:
            return []
        
        stack = []
        res = []
        
        #入栈
        while listNode:
            stack.append(listNode.val)
            listNode = listNode.next
        #出栈
        while stack:
            res.append(stack.pop())
        
        return res   
        

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

方法2

class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        res = []
        while listNode:
            res.append(listNode.val)
            listNode = listNode.next
        return res[::-1]

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

JZ7 重建二叉树(中等)

描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

img

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围：n≤2000n≤2000，节点的值 −10000≤val≤10000−10000≤val≤10000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例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}
说明：
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示    

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

方法1

0901

JZ9用两个栈实现队列(简单)

描述

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： n≤1000n≤1000

要求：存储n个元素的空间复杂度为 O(n)，插入与删除的时间复杂度都是 O(1)

示例1

输入：
["PSH1","PSH2","POP","POP"]
返回值：
1,2
说明：
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP":代表删除一个元素，先进先出=>返回1
"POP":代表删除一个元素，先进先出=>返回2   

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

方法1

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def pop(self):
        self.stack1.append(node)
        
    def push(self):
        # 将第一个栈中的内容弹出放入第二个栈中
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        # 第二个栈栈顶就是最先进来的元素，即队首
        res = self.stack2.pop()
        # 再将第二个栈的元素放回第一个栈
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        return res

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

JZ11旋转数组的最小数字(简单)

描述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤100001≤n≤10000，数组中任意元素的值: 0≤val≤100000≤val≤10000

要求：空间复杂度：O(1) ，时间复杂度：O(logn)

示例1

输入：
[3,4,5,1,2]
返回值：
1

  • 1
  • 2
  • 3
  • 4

方法1

class Solution:
    def minNumberInRotateArray(self , nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        # 两个指针
        l,r = 0, len(nums)-1
        while l<r:
            mid = (l+r)//2
            if nums[mid] > nums[r]:
                l = mid + 1
            elif nums[mid] < nums[r]:
                r = mid
            else:
                r -= 1
        return nums[l]

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

0903

JZ15二进制中1的个数(简单)

描述

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

数据范围：−231<=n<=231−1

即范围为:−2147483648<=n<=2147483647

示例1

输入：
10
返回值：
2
说明：
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。     

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
题目的主要信息：
  • 统计32位整型有符号数二进制中1的个数
  • 因负数用补码表示，故不能用连除法
方法一：循环按位比较法（推荐使用）

知识点：位运算

计算机的数字由二进制表示，我们平常的运算是对整个数字进行运算，但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。

思路：

我们可以检查该数字的二进制每一位是否为1，如果遍历二进制每一位呢？可以考虑移位运算，每次移动一位就可以。至于怎么统计到1呢？我们都只知道数字1与数字相位与运算，其实只是最后一位为1就是1，最后一位为0就是0，这样我们只需要将数字1移位运算，就可以遍历二进制的每一位，再去做位与运算，结果为1的就是二进制中为1的。

具体做法：

  • step 1：遍历二进制的32位，通过移位0-31次实现。
  • step 2：将移位后的1与数字进行位与运算，结果为1就记录一次。\

方法一

class Solution:
    def NumberOf1(self , n: int) -> int:
        # write code here
        res = 0
        for i in range(32):
            # 按位比较，按位与,只有两个二进制位均为1时结果才为1,其余皆为0。
            # 1<<i表示将1的二进制每位左移动i位，末位补0。左移运算符(<<)
            if (n & (1<<i)) != 0:
                res += 1
        return res

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

方法二

简单循环遍历

class Solution:
    def hammingWeight(self, n):
        n = bin(n)
        cnt = 0
        for i in str(n):
            if i == '1':
                cnt = cnt + 1
        return cnt

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

JZ17 打印从1到最大的n位数

描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

  1. 用返回一个整数列表来代替打印
  2. n 为正整数，0 < n <= 5

示例1

输入：

1

  • 1

返回值：

[1,2,3,4,5,6,7,8,9]

  • 1

方法一

class Solution:
    def printNumbers(self , n: int) -> List[int]:
        a = n % 10
        #pow()函数 python的内置函数,它计算并返回x的y次方的值。
        b = pow(b, 10)
        res = [i for i in range(b)]
        res = res[1:]
        return res
        
            

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

JZ18删除链表的节点

描述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

1.此题对比原题有改动

2.题目保证链表中节点的值互不相同

3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

数据范围:

0<=链表节点值<=10000

0<=链表长度<=10000

示例1

输入：

{2,5,1,9},5

  • 1

返回值：

{2,1,9}

  • 1

说明：

给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 2 -> 1 -> 9   

  • 1

方法一

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
class Solution:
    def deleteNode(self , head: ListNode, val: int) -> ListNode:
        # 加入一个头节点
        res = ListNode(0)
        res.next = pre
        # 前序节点
        pre = res
        # 当前节点
        cur = head
        # 遍历列表
        while cur is not None:
            if cur.val == val:
                pre.next = cur.next
                break
            pre = cur
            cur = cur.next
        return res.next
        

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

JZ22 链表中倒数最后k个结点

描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤1050≤n≤105，0≤ai≤1090≤ai≤109，0≤k≤1090≤k≤109

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

img

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1

输入：

{1,2,3,4,5},2

  • 1

返回值：

{4,5}

  • 1

说明：

返回倒数第2个节点4，系统会打印后面所有的节点来比较。 

  • 1

方法一

#class ListNode:
#    def __init__(self, x):
#        self.val = x
#        self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        n = 0
        p = pHead
        while p:
            n = n + 1
            p.next
        # 长度太小，返回空列表
        if k > n:
            return None
        p = p.head
        # 遍历n-k次
        for i in range(n-k):
            p.next
        return p

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

JZ24 反转链表

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤10000≤n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

img

示例1

输入：

{1,2,3}

  • 1

返回值：

{3,2,1}

  • 1

方法一

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        cur = head
        head = None
        while cur:
            node = ListNode(cur.val)
            node.next = head
            head = node
            cur = cur.next
        return head

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

[外链图片转存中…(img-A4QvpN0U-1693744978675)]

示例1

输入：

{1,2,3}

  • 1

返回值：

{3,2,1}

  • 1

方法一

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        cur = head
        head = None
        while cur:
            node = ListNode(cur.val)
            node.next = head
            head = node
            cur = cur.next
        return head

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/694985
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号