剑指Offer【Python实现】

2023-11-24 20:57:34

剑指Offer笔记 [Python描述]

二维数组中的查找

题目描述：

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。
给定 target = 3，返回 false。

数据范围: 矩阵的长宽满足 \(0 \leq n, m \leq 500\) ，矩阵中的值满足 \(0 \leq v a l \leq 10^{9}\) 进阶：空间复杂度 \(O(1)\) ，时间复杂度 \(O(n+m)\)

输入描述：

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

输出描述：

true

代码如下：

def find(target, array):
    i = 0
    j = len(array[0]) - 1
    while i < len(array) and j >= 0:
        base = array[i][j]
        if target == base:
            return True
        elif target > base: 
            i += 1
        else:
            j -= 1
    return False

print(find(4,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]))

替换空格

题目描述：

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

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

数据范围: \(0 \leq \operatorname{len}(s) \leq 1000\) 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。进阶：时间复杂度 \(O(n)\),空间复杂度 \(O(n)\)

输入描述：

"We Are Happy"

" "

输出描述：

"We%20Are%20Happy"

"%20"

代码如下：

def replaceSpace(s):
    # write code here
    s_len = len(s)
    space_count = 0
    for i in s:
        if i == ' ':
            space_count += 1
    s_len += 2 * space_count
    new_array = [' '] * s_len
    j = 0
    for i in range(len(s)):
        if s[i] == ' ':
            new_array[j] = '%'
            new_array[j+1] = '2'
            new_array[j+2] = '0'
            j += 3
        else:
            new_array[j] = s[i]
            j += 1
    return ''.join(new_array)
print(replaceSpace('We Are Happy'))

从尾到头打印链表

题目描述：

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

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

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

0 <= 链表长度 <= 10000

输入描述：

{67,0,24,58}

输出描述：

[58,24,0,67]

代码如下：

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

# 解法1：用辅助栈存储
def printListFromTailToHead(listNode):
    # write code here
    stack = []
    result_array = []
    node_p = listNode
    while node_p:
        stack.append(node_p.val)
        node_p = node_p.next 
    while stack:
        result_array.append(stack.pop(-1))
    return result_array


# 解法2：本身栈调用
result_array = []
def printListFromTailToHead(listNode):
    # write code here
    if listNode:
        printListFromTailToHead(listNode.next)
        result_array.append(listNode.val)
    return result_array

重建二叉树

题目描述：

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

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

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

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

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

数据范围: \(n \leq 2000\) ，节点的值 \(-10000 \leq\) val \(\leq 10000\) 要求：空间复杂度 \(O(n)\), 时间复杂度 \(O(n)\)

输入描述：

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

输出描述：

{1,2,3,4,#,5,6,#,7,#,#,8}

说明：
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示

代码如下：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# 返回构造的TreeNode根节点
def reConstructBinaryTree(pre, tin):
    # write code here
    if not pre:
        return None
    root_val = pre[0]
    root = TreeNode(root_val)
    for i in range(len(tin)):
        if tin[i] == root_val:
            break
    root.left = reConstructBinaryTree(pre[1:1+i], tin[:i])
    root.right = reConstructBinaryTree(pre[1+i:], tin[i+1:])
    
    return root

def preorder(root):
    if root:
        preorder(root.left)
        print(root.val)
        preorder(root.right)
preorder(reConstructBinaryTree([1,2,3,4,5,6,7],[3,2,4,1,6,5,7]))

用两个栈实现队列

题目描述：

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

数据范围: \(n \leq 1000\) 要求: 存储 \(n\) 个元綁的空间复杂度为 \(O(n)\) ，揷入与删除的时间复杂度都是 \(O(1)\)

输入描述：

["PSH1","PSH2","POP","POP"]

输出描述：

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

代码如下：

class CQueue(object):

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value):
        self.stack1.append(value)
    
    def deleteHead(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop(-1))
        if len(self.stack2) == 0: 
            return -1
        return self.stack2.pop(-1)

思路
一个栈用来存储，pop时弹出stack2，stack2为空，pop出stack1存储在stack2中。

旋转数组的最小数字

题目描述：

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

数据范围: \(1 \leq n \leq 10000\) ，数组中任意元龶的值: \(0 \leq\) val \(\leq 10000\) 要求: 空间复杂度: \(O(1)\) ，时间复杂度: \(O(\operatorname{logn})\)

输入描述：

[3,4,5,1,2]

输出描述：

代码如下：

class Solution(object):
    def minArray(self, numbers):
        low, high = 0, len(numbers) - 1
        while low < high:
            mid = (high+low) / 2
            if numbers[mid] > numbers[high]:
                low = mid + 1
            elif numbers[mid] < numbers[high]:
                high = mid
            else:
                if (numbers[high - 1] > numbers[high]):  # 确保正确的下标
                    low = high
                    break
                high -= 1  # 如果numbers[hign-1]=numbers[high]的情况
        return numbers[low]

思路

总体二分：

if mid大于high, low = mid - 1
if mid小于high, high = mid
直到mid=high，取此位置的数

斐波那契数列

题目描述：

大家都知道斐波那契数列，现在要求输入一个正整数 \(n\) ，请你输出斐波那契数列的第 \(n\) 项。韭波那契数列是一个满足 \(f i b(x)=\left\{\begin{array}{rc}1 & x=1,2 \\ f i b(x-1)+f i b(x-2) & x>2\end{array}\right.\)

数据范围: \(1 \leq n \leq 39\)
要求: 空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\) ，本题也有时间复杂度 \(O(\operatorname{logn})\) 的解法

输入描述：

一个正整数n
4

输出描述：

输出一个正整数。
3
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为4。

代码如下：

def Fibonacci(n):
    # write code here
    f1 = 0
    f2 = 1
    if n == 0: return f1
    elif n == 1: return f2
    for _ in range(n-1):
        f2, f1 = f1+f2, f2
    return f2
print(Fibonacci(3))

跳台阶

题目描述：

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

数据范围: \(0 \leq n \leq 40\)
要求: 时间复杂度: \(O(n)\) ，空间复杂度: \(O(1)\)

输入描述：

输出描述：

2

说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

代码如下：

class Solution(object):
    def numWays(self, n):
        if n == 0: return 1
        f1 = 1
        f2 = 2
        if n == 1: return f1
        if n == 2: return f2
        for _ in range(n-2):
            f2, f1 = f1+f2, f2
        return f2 % 1000000007

思路

假设对于第n级台阶，总共有f(n)种跳法.

那么f(n) = f(n-1) + f(n-2)，其中f(1)=1,f(2)=2

跳台阶扩展问题

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围: \(1 \leq n \leq 20\)
进阶：空间复杂度 \(O(1) ，\) 时间复杂度 \(O(1)\)

输入描述：

输出描述：

代码如下：

def jumpFloorII(number):
    # write code here
    f1 = 1
    if number == 1: return f1
    for _ in range(number-1):
        f1 = 2*f1
    return f1

思路

f(1)=1, f(2)=2, f(3)=4, f(4)=8 设n+1级f(n+1),有

f(n+1) = f(1) + f(2) + ... + f(n)

f(n+2) = f(1) + f(2) + ... + f(n+1)

f(n+2)= 2f(1) + 2f(2) + ... + 2f(n)

故得f(n+2) = 2f(n+1)

矩形覆盖

题目描述：

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

数据范围: \(0 \leq n \leq 38\)
进阶：空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

注意：约定 n == 0 时，输出 0

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：

输入描述：

//2*1的小矩形的总个数n

4

输出描述：

代码如下：

def rectCover(number):
    # write code here
    f1 = 1
    f2 = 2
    if number == 1: return f1
    if number == 2: return f2
    for _ in range(number-2):
        f2, f1 = f1 + f2, f2
    return f2

print(rectCover(3))

思路

f(1) = 1
f(2) = 2

f(n) = f(n-1) + f(n-2)

二进制中1的个数

题目描述：

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

数据范围: \(-2^{31}<=n<=2^{31}-1\)
即范围为: \(-2147483648<=n<=2147483647\)

输入描述：

10

-1

输出描述：

2

32
说明：
1. 十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。  

2. 负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1

代码如下：


def Power(base, exponent):
    # write code here
    if exponent == 0: return 1
    flag = 1
    if exponent < 0:
        exponent *= -1
        flag = 0
    temp = base
    res = 1
    while(exponent):
        if exponent & 1:
            res *= temp
        temp *= temp
        exponent = exponent >> 1

    return res if flag else 1.0/res

print(Power(2, 1))

思路

如果n!=0，n的二进制中至少有一个1

如果1在最低位，n-1 & n 得到的数正好将这个1，变成0。
如果1不在最低位，n-1 & n 得到的数正好将这个1，变成0。

因此我们判断n-1 & n 能够循环运行的次数就可以判断二进制中有多少个1了。

在python中需要使用c_int()函数，不然负数不会变成0。

数值的整数次方

题目描述：

实现函数 double Power(double base, int exponent)，求base的exponent次方。

数据范围: \(\mid\) base \(|\leq 100,\), exponent \(\mid \leq 100\),保证最终结果一定满足 \(|v a l| \leq 10^{4}\) 进阶：空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

输入描述：

2.00000,-2

输出描述：

0.25000
2的-2次方等于1/4=0.25

代码如下：

from ctypes import *
def NumberOf1(n):
    # write code here
    cnt = 0
    while c_int(n).value:
        n = n & (n-1)
        cnt += 1
        print(c_int(n), n)
    return cnt
print(NumberOf1(-3))

调整数组顺序使奇数位于偶数前面(一)

题目描述：

输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围: \(0 \leq n \leq 5000\) ，数组中每个数的值 \(0 \leq\) val \(\leq 10000\)
要求: 时间复杂度 \(O(n)\) ，空间复杂度 \(O(n)\)
进阶：时间复杂度 \(O\left(n^{2}\right)\) ，空间复杂度 \(O(1)\)

输入描述：

[2,4,6,5,7]

输出描述：

[5,7,2,4,6]

代码如下：

def reOrderArray(array):
    # write code here
    odd_cnt = 0
    res = [0] * len(array)
    # 统计个数
    for n in array:  
        if n % 2 != 0:
            odd_cnt += 1
    # 填坑
    odd_i = 0
    even_i = odd_cnt
    for i in range(len(array)):
        if array[i] % 2 != 0:  
            res[odd_i] = array[i]
            odd_i += 1
        else:
            res[even_i] = array[i]
            even_i += 1
    return res

链表中倒数最后k个结点

题目描述：

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

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

数据范围: \(0 \leq n \leq 10^{5} ， 0 \leq a_{i} \leq 10^{9} ， 0 \leq k \leq 10^{9}\)
要求: 空间复杂度 \(O(n)\) ，时间复杂度 \(O(n)\)
进阶: 空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

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

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

输入描述：

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

输出描述：

{4,5}
说明：
返回倒数第2个节点4，系统会打印后面所有的节点来比较。

代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def FindKthToTail(head, k):
    # write code here
    if not head: return None
    fast_p = head
    slow_p = head
    for _ in range(k):
        if fast_p:
            fast_p = fast_p.next
        else:
            return None
    while fast_p:
        fast_p = fast_p.next
        slow_p = slow_p.next
    return slow_p

思路

用快慢指针，快指针比慢指针快k步，到尾结点了慢指针就是倒数第k个结点。

反转链表

题目描述：

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

数据范围: \(n \leq 1000\) 要求: 空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

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

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

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

输入描述：

{1,2,3}

输出描述：

{3,2,1}

代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def ReverseList(pHead):
    # write code here

    if not pHead: return None
    head = ListNode(0)
    head.next = pHead
    p = pHead
    while(p.next):
        tp = p.next
        p.next = p.next.next
        tp.next = head.next
        head.next = tp
    return head.next

思路

假设翻转1->2->3->4->5，步骤如下：

head->4->3->2->1->5
               p  tp

1.我们将p的next指向tp的next
2.将tp的next指向head的next
3.将head的next指向tp

合并有序链表

题目描述：

输入两个递增的链表，单个链表的长度为 \(n\) ，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围: \(0 \leq n \leq 1000 ，-1000 \leq {\text { 节点值 } \leq 1000}{}\)
要求：空间㚉杂度 \(O(1) ，\) 时间复杂度 \(O(n)\)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

输入描述：

{-1,2,4},{1,3,4}

输出描述：

{-1,1,2,3,4,4}

代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def Merge(pHead1, pHead2):
    # write code here
    res = ListNode(0)
    head = res
    while pHead1 and pHead2:
        if pHead1.val <= pHead2.val:
            head.next = pHead1
            head = head.next
            pHead1 = pHead1.next
        else:
            head.next = pHead2
            head = head.next
            pHead2 = pHead2.next
            
    if pHead1:
        head.next = pHead1
    if pHead2:
        head.next = pHead2
    return res.next

树的子结构

题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

数据范围:

0 <= A的节点个数 <= 10000

0 <= B的节点个数 <= 10000

输入描述：

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

输出描述：

true

代码如下：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def helper(treeA, treeB):
    if not treeB:
        return True
    elif not treeA:
        return False
    elif treeA.val != treeB.val:
        return False
    else:
        return helper(treeA.left, treeB.left) and helper(treeA.right, treeB.right)


def HasSubtree(pRoot1, pRoot2):
    # write code here
    if not pRoot1 or not pRoot2: return False
    # 2 是不是 1的子树
    res = False
    if pRoot1.val == pRoot2.val:
        res = helper(pRoot1, pRoot2)
    if res: 
        return True
    else:
        return HasSubtree(pRoot1.left, pRoot2) or HasSubtree(pRoot1.right, pRoot2)

思路

1. 遍历父结构
1. 判断子结构是否相同

码农公寓

剑指Offer笔记 [Python描述]

二维数组中的查找

题目描述：

输入描述：

输出描述：

代码如下：

替换空格

题目描述：

输入描述：

输出描述：

代码如下：

从尾到头打印链表

题目描述：

输入描述：

输出描述：

代码如下：

重建二叉树

题目描述：

输入描述：

输出描述：

代码如下：

用两个栈实现队列

题目描述：

输入描述：

输出描述：

代码如下：

旋转数组的最小数字

题目描述：

输入描述：

输出描述：

代码如下：

思路

斐波那契数列

题目描述：

输入描述：

输出描述：

代码如下：

跳台阶

题目描述：

输入描述：

输出描述：

代码如下：

思路

跳台阶扩展问题

题目描述：

输入描述：

输出描述：

代码如下：

思路

矩形覆盖

题目描述：

输入描述：

输出描述：

代码如下：

思路

二进制中1的个数

题目描述：

输入描述：

输出描述：

代码如下：

思路

数值的整数次方

题目描述：

输入描述：

输出描述：

代码如下：

调整数组顺序使奇数位于偶数前面(一)

题目描述：

输入描述：

输出描述：

代码如下：

链表中倒数最后k个结点

题目描述：

输入描述：

输出描述：

代码如下：

思路

反转链表

题目描述：