面试必会：剑指offer手撕代码（一）：第1~16题，详细题解python代码，建议熟练默写

清疚 2022-11-09 14:23 197阅读 0赞

> **根据我的大厂面试经验，剑指offer的题一定都要熟练掌握，面试时极有可能让我们手撕部分题的代码，当然这是最简单的情况，像BAT这类的大厂大部分时候让我们手撕 动态规划 题。总之，剑指offer的题目算法思路我们一定要会！！！**

## 1、二维数组中的查找 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]  
**题解python代码：**

# -*- coding:utf-8 -*-
    class Solution:
        # array 二维列表
        def Find(self, target, array):
            # write code here
            if not array[0]: return False
            l,r,n = 0,len(array)-1,len(array)
            for A in array:
                if self.binary(target, A, l, r):
                    return True
            return False
    
        def binary(self, t, array, l, r):
            while l<=r:
                m = (l+r)//2
                if array[m]<t: l = m+1
                elif array[m]==t: return True
                else: r = m-1
            return False

## 2、替换空格 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 1]  
**题解python代码：**

注：也可以将s拆成列表，然后在中间插入 “%20”

class Solution:
        def replaceSpace(self , s ):
            # write code here
            return s.replace(" ","%20")

## 3、从尾到头打印链表 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 2]  
**题解python代码：**

# -*- 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
            stack = []
            while listNode:
                stack.append(listNode.val)
                listNode = listNode.next
            return stack[::-1]

## 4、重建二叉树 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 3]  
**题解python代码：**

# -*- 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, tin):
            if len(pre)==0: 
                return 
            # write code here
            root = TreeNode(pre[0])
            root_index = tin.index(pre[0])
            root.left = self.reConstructBinaryTree(pre[1:root_index+1], tin[:root_index])
            root.right = self.reConstructBinaryTree(pre[root_index+1:], tin[root_index+1:])
            return root

## 5、用两个栈实现队列 ##

**题目描述：**

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

**题解python代码：**

注：我在题目的基础加入了 peek（查看队头元素），empty（是否为空），**init**（初始化），三种方法。

class MyQueue(object):
    
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
    
        def push(self, x):
            self.stack1.append(x)
    
        def pop(self):
            if not self.stack2:
                while self.stack1:
                    self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
    
        def peek(self):
            if not self.stack2:
                while self.stack1:
                    self.stack2.append(self.stack1.pop())
            return self.stack2[-1]
    
        def empty(self):
            return not self.stack1 and not self.stack2

## 6、旋转数组的最小数字 ##

**题目描述：**

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。  
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。  
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 4]  
**题解python代码：**

# -*- coding:utf-8 -*-
    class Solution:
        def minNumberInRotateArray(self, rotateArray):
            # 可以使用min()函数， 但是在不适用min函数的情况下，思路应该是二分查找
            # 下面使用 递归实现2分查找，其中递归的时候必须使用return！！！ 不然会返回none
            # write code here 
            start = 0
            end = len(rotateArray) - 1
            mid = int((start + end) / 2)
            if len(rotateArray) == 2:
                if rotateArray[0]>rotateArray[1]:
                    return rotateArray[1]
                else:
                    return rotateArray[0]
    
            elif rotateArray[mid] > rotateArray[end]:
                return self.minNumberInRotateArray(rotateArray[mid:end + 1])
            elif rotateArray[mid] < rotateArray[start]:
                return self.minNumberInRotateArray(rotateArray[start:mid + 1])

## 7、斐波那契数列 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 5]  
**题解python代码：**

注：递归会超时

# -*- coding:utf-8 -*-
    class Solution:
        def Fibonacci(self, n):
            if n<2: return n
            # write code here
            A = [0]*(n+1)
            A[1] = 1
            for i in range(2, n+1):
                A[i] = A[i-1]+A[i-2]
            return A[-1]

## 8、跳台阶 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 6]  
**题解python代码：**

注：递归会超时

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloor(self, number):
            # write code here
    #         if number<3: 
    #             return number
    #         return self.jumpFloor(number-1)+self.jumpFloor(number-2)
            if number <= 2:
                return number
            a, b = 1, 2
            for i in range(3,number+1):
                a, b = b, a + b
                print(b)
            return b

## 9、跳台阶扩展问题 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 7]

**题解python代码：**

注：找规律的题目

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloorII(self, number):
            # write code here
            return 2**(number-1)

## 10、矩形覆盖 ##

**题目描述：**

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

比如n=3时，2\*3的矩形块有3种覆盖方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 8]

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 9]  
**题解python代码：**

# -*- coding:utf-8 -*-
    class Solution:
        def rectCover(self, number):
            # write code here
            if number<4: return number
            A = [i for i in range(number+1)]
            for i in range(4, number+1):
                A[i] = A[i-1]+A[i-2]
            return A[-1]

## 11、二进制中1的个数 ##

**题目描述：**

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

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 10]  
**题解python代码：**

注：python32位二进制负数补码的表示[https://blog.csdn.net/weixin\_44414948/article/details/114809621][https_blog.csdn.net_weixin_44414948_article_details_114809621]

# -*- coding:utf-8 -*-
    class Solution:
        def NumberOf1(self, n):
            # write code here
            if n<0: n = n&0xffffffff
            count = 0
            temp = 0x00000001
            for i in range(64):
                if n&temp: count += 1
                temp = temp<<1
            return count

## 12、数值的整数次方 ##

**题目描述：**

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 11]  
**题解python代码：**

注：二分法中的倍增法

# -*- coding:utf-8 -*-
    class Solution:
        def Power(self, base, exponent):
            # write code here
            if base==0: return 0
            if exponent==0: return 1
            flag = 1
            if exponent<0:
                exponent = -exponent
                flag = -1
    #         exponent,flag = -exponent,-1 if exponent<0 else exponent,1
            temp = 1
            ans = base
            while exponent>1:
                if exponent%2==1:
                    temp *= base
                    exponent -= 1
                ans *= ans
                exponent /= 2
            return ans*temp if flag==1 else 1/(ans*temp)

## 13、调整数组顺序使奇数位于偶数前面 ##

**题目描述：**

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 12]  
**题解python代码：**

注：两个辅助栈

class Solution:
        def reOrderArray(self , array ):
            # write code here
            A,B = [],[]
            for a in array:
                if a%2==1: A.append(a)
                else: B.append(a)
            return A+B

## 14、链表中倒数第k个结点 ##

**题目描述：**

输入一个链表，输出该链表中倒数第k个结点。

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 13]  
**题解python代码：**

注：快慢指针法

class Solution:
        def FindKthToTail(self , pHead , k ):
            # write code here
            if not pHead: return None
            fast,slow = pHead, pHead
            while fast and k>0:   # fast、k同时往下一个滑动
                fast = fast.next
                k -= 1
            if k>0: return None   # fast滑到尾部时k仍然大于0，则k大于整个链表的长度
            while fast:  # 快慢指针同时往下滑动（两者相差k个长度），fast滑到尾部时，slow即为倒数第k个节点
                fast = fast.next
                slow = slow.next
            return slow

## 15、反转链表 ##

**题目描述：**

输入一个链表，反转链表后，输出新链表的表头。

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 14]  
**题解python代码：**

方法一、辅助栈法

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            # 1、辅助栈
            stack = []
            ans = temp = ListNode(0)
            while pHead:
                stack.append(pHead.val)
                pHead = pHead.next
            while stack:
                temp.next = ListNode(stack.pop())
                temp = temp.next
            return ans.next

方法二、指针倒转法

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            # 2、指针倒转
            if not pHead or not pHead.next: return pHead
            last = None
            while pHead:
                temp = pHead.next  # 保存next信息
                pHead.next = last  # 将pHead的next指针指向last
                last = pHead   # 将last变为pHead，准备变为pHead.next的下一个
                pHead = temp   # 更新pHead为其原本的下一个节点
            return last

## 16、合并两个排序的链表 ##

**题目描述：**

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

示例1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 15]  
**题解python代码：**

方法一、辅助栈法

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):
            # write code here
            # 1、辅助栈
            stack = []
            while pHead1 or pHead2:
                if pHead1: 
                    stack.append(pHead1.val)
                    pHead1 = pHead1.next
                if pHead2:
                    stack.append(pHead2.val)
                    pHead2 = pHead2.next
            stack.sort()
            ans = current = ListNode(0)
            for s in stack:
                current.next = ListNode(s)
                current = current.next
            return ans.next

方法二、直接添加

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):
            # write code here
            # 2、直接添加
            ans = temp = ListNode(0)
            while pHead1 and pHead2:
                if pHead1.val<pHead2.val:
                    temp.next = pHead1
                    pHead1 = pHead1.next
                else:
                    temp.next = pHead2
                    pHead2 = pHead2.next
                temp = temp.next
            if not pHead1:
                temp.next = pHead2
            if not pHead2:
                temp.next = pHead1
            return ans.next

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]: /images/20221023/bc2d1c7282024fc7a7c78dec29a655b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 1]: /images/20221023/d9f052f38a2c47859b84bcb304e1f846.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 2]: /images/20221023/e74419b52c7a4371a678c9e4331012a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 3]: /images/20221023/ee16e105b13f482abd630cd27f1d90a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 4]: /images/20221023/75f522ec9c67446393acf1ba9bfcd2dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 5]: /images/20221023/5aa55415baa1458a99adb3967abe373b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 6]: /images/20221023/4ab2b6ec558d48959f518b611186156a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 7]: /images/20221023/401a62d302f44cc2870c6d5fba943747.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 8]: /images/20221023/a98ec910d2fd42608d9413c276a1541a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 9]: /images/20221023/49a8b4262ba0484da25ff874448310a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 10]: /images/20221023/d89acd12d5054374ba44800c92f51f69.png
[https_blog.csdn.net_weixin_44414948_article_details_114809621]: https://blog.csdn.net/weixin_44414948/article/details/114809621
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 11]: /images/20221023/a47b67df7e4b4083bdd9a701de82d6d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 12]: /images/20221023/9d794486988341aa9676e815943328df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 13]: /images/20221023/429b2d2446dd41ec8224b0bccb86b146.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 14]: /images/20221023/7e7b87c9adf745429ecab3ea82c45c9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 15]: /images/20221023/2aa14520857341a786a25f82d3df1d9e.png