2024年最全《剑指offer》详解-Python(3)，2024年最新程序人生
https://img-blog.csdnimg.cn/img_convert/f1d6dc4d9d91747d7ae21f80b93af316.pnghttps://img-blog.csdnimg.cn/img_convert/cfb5c0a04385bbd941adfbd6fe3bb557.png
https://img-blog.csdnimg.cn/img_convert/52c84f471cc7039abe7dbf7aeb9e5883.png
既有得当小白学习的零底子资料，也有得当3年以上经验的小伙伴深入学习提拔的进阶课程，涵盖了95%以上Go语言开发知识点，真正体系化！
由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会连续更新
假如你需要这些资料，可以戳这里获取
文章目录
[*]
[*]
[*]1.二维数组中的查找
[*]2.替换空格
[*]3.从尾到头打印链表arrayList：
[*]4.两个栈实现一个队列：
[*]6.旋转数组的最小数字
[*]7.斐波那契数列
[*]8.跳台阶：
[*]9.变态跳台阶：
[*]10矩形覆盖：
[*]11. 二进制中1的个数：
[*]12.数值的整数次方
[*]13.调解数组顺序使奇数位于偶数前面
[*]14.链表中倒数第k个结点：
[*]15.反转链表：
[*]16.合并两个排序的链表：
[*]17.树的子布局：
[*]18.二叉树的镜像：
[*]20.包含min函数的栈：
[*]28.数组中出现次数凌驾一半的数字：
[*]29.最小的k个数：
[*]30.连续子数组的和：
[*]31.整数中1出现的次数：
[*]32.把数组排成最小的数：
[*]33.丑数：
[*]34.第一个只出现一次的字符：
[*]35.数组中的逆序对
[*]37.数字在排序数组中出现的次数：
[*]40.数组中只出现一次的数字:
[*]41.和为s的连续正数序列：
[*]42.和为s的两个数字
[*]43.左旋转字符串
[*]44.翻转单词顺序列：
[*]45.扑克牌顺子：
[*]46.孩子们的游戏(圆圈中最后剩下的数)
[*]47.求1+2+3+…+n:
[*]48.不用加减乘除做加法
[*]49.把字符串转换成整数
[*]50.数组中重复的数字
[*]51.构建乘积数组
[*]53.表现数值的字符串
[*]矩阵中的路径
[*]参考资料：
python刷《剑指offer》记录时间复杂度和多种做法。发起在
牛客网刷题，判断是否成功通过所有样例，看懂思路和自己写出来并AC，完全是两码事。如有错误欢迎指正。
标题难度复杂度解法备注1.二维数组的查找Easy O
(
n
2
)
,
O
(
n
)
O(n^2),O(n)
O(n2),O(n) | 遍历二维数组；从右上开始查找 | Done |
| 2.替换空格 | Easy |
O
(
n
)
O(n)
O(n) | 遍历然后直接替换 | Done |
| 3.从尾到头打印链表arrayList | Easy |
O
(
n
)
O(n)
O(n) | 遍历生存在list中 | Done |
| 4.重建二叉树 | | | | ToDo |
| 5.两个栈实现一个队列 | Easy | | 另一个栈作为中转 | Done |
| 6.旋转数组的最小数字 | Easy |
O
(
n
)
,
O
(
l
o
g
n
)
O(n),O(logn)
O(n),O(logn) | 遍历数组；二分法 | Done |
| 7.斐波那契数列 | Easy |
O
(
n
)
O(n)
O(n) | 递归；循环的方式实现递归 | Done |
| 8.跳台阶 | Easy | | 和第七题类似 | Done |
| 9.变态跳台阶 | Easy | | 数学归纳法 | Done |
| 10.矩形覆盖 | Easy | | 和第七题类似 | Done |
| 11.二进制中1的个数 | Medium | | 按位运算 | ToDo |
| 12.数值的整数次方 | Medium |
O
(
l
o
g
n
)
O(logn)
O(logn) | 接纳递归算法依次降幂即可，按位运算可以加速速度 | ToDo |
| 13.调解数组顺序使奇数位于偶数前面 | Medium | | python可以利用lambda | ToDo |
| 14.链表中倒数第k个结点 | Medium |
O
(
n
)
O(n)
O(n) | 双指针，一前一后 | Done |
| 15.反转链表 | Medium |
O
(
n
)
O(n)
O(n) | | ToDo |
| 16.合并两个排序链表 | Medium |
O
(
n
[*]
m
)
O(n+m)
O(n+m) | 递归，依次返回两个链表的最小值 | Done |
| 17.判断子布局 | Medium |
O
(
)
O()
O() | ToDo | |
| 18.二叉树的镜像 | Easy |
O
(
)
O()
O() | 递归依次交换左右子树即可 | Done |
| 20.包含min函数的栈 | Medium |
O
(
n
)
O(n)
O(n) | 建一个辅助栈，生存当前数的最小值 | ToDo |
| 28.数组中出现次数凌驾一半的数字 | Medium |
O
(
n
)
；
O
(
l
o
g
n
)
O(n)；O(logn)
O(n)；O(logn) | 遍历数组；从中间向两边展开 | Done |
| 29.最小的k个数 | Medium |
O
(
n
l
o
g
n
)
；
O
(
n
)
O(nlogn)；O(n)
O(nlogn)；O(n) | 排序然后输出；挑选替换 | Done |
| 30.连续子数组的最大和 | Easy |
O
(
n
2
)
；
O(n^2)；
O(n2)； | 暴力法，求解所有字符串的和； | Done |
| 31.整数1出现的次数 | Easy |
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) | 遍历，然后盘算个数 | Done |
| 32.把数组排成最小的数 | Medium |
O
(
n
2
)
;
O(n^2);
O(n2); | 字符串两两比较 | ToDo |
| 33.丑数 | Medium |
O
(
n
)
O(n)
O(n) | 依次生成 | Done |
| 34.第一个只出现一次的字符 | Easy |
O
(
n
)
O(n)
O(n) | 生存字典然后判断 | Done |
| 35.数组中的逆序对 | Medium |
O
(
n
2
)
;
O
(
n
l
o
g
n
)
O(n^2);O(nlogn)
O(n2);O(nlogn) | 暴力； | Done |
| 37.数字在排序数组中出现的次数 | Easy |
O
(
n
)
;
O
(
l
o
g
n
)
O(n);O(logn)
O(n);O(logn) | 遍历；二分查找 | Done |
| 40.数组中只出现一次的数字 | Easy |
O
(
n
)
O(n)
O(n) | 哈希表 | Done |
| 41.和为s的连续正数序列 | Easy |
O
(
n
2
)
,
O
(
n
)
,
O
(
l
o
g
n
)
O(n^2),O(n),O(logn)
O(n2),O(n),O(logn) | 双指针；遍历数组求另一个解；二分法 | Done |
| 42.和为S的两个数字 | Easy |
O
(
n
)
O(n)
O(n) | 双指针 | Done |
| 43.左旋转字符串 | Easy |
O
(
1
)
O(1)
O(1) | 好吧，太简朴 | Done |
| 44.翻转单词顺序列 | Easy |
O
(
n
)
O(n)
O(n) | 翻转组合 | Done |
| 45.扑克牌顺子 | Easy |
O
(
n
)
O(n)
O(n) | gap和大小王个数比较 | Done |
| 46.圆圈中最后剩下的数 | Easy |
O
(
n
)
O(n)
O(n) | 模拟这个过程 | Done |
| 47.求1+2+3+…+n | Easy |
O
(
n
)
O(n)
O(n) | 利用and实现递归终止 | Done |
| 48.不用加减乘除做加法 | Medium |
O
(
1
)
O(1)
O(1) | 利用位运算来实现 | ToDO |
| 49.把字符串转换成整数 | Easy |
O
(
n
)
O(n)
O(n) | 主要是负数和特殊环境 | Done |
| 50.数组中重复的数字 | Easy |
O
(
n
)
O(n)
O(n) | 哈希表生存次数然后输出 | Done |
| 51.构建乘积数组 | Medium |
O
(
n
)
O(n)
O(n) | 正反向遍历，依次生存之前的乘积值 | Done |
| 53.表现数值的字符串 | Easy |
O
(
1
)
O(1)
O(1) | 作弊式操作float | Done |
| 矩阵中路径 | Medium | 回溯法，关键是怎样写递归 | | |
1.二维数组中的查找
Q: 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入如许的一个二维数组和一个整数，判断数组中是否含有该整数。
A1： 遍历整个二维数组，
O
(
n
2
)
O(n^2)
O(n2)
A2: 从右上大概左下开始查找。从右上开始查找：假如数组中的数比这个整数大，向左移动一位，假如数组中的数比这个数小，向下移动一位，
O
(
n
)
O(n)
O(n)。
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if array == []:
return False
num_row = len(array)
num_col = len(array)
i,j = 0, num_col-1
while j >= 0 and i < num_row:
if array > target:
j -= 1
elif array < target:
i += 1
else:
return True
2.替换空格
Q: 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
A1： 先盘算最终需要给出的长度，然后建立两个指针p1,p2，p1指向原始字符串的末尾，p2指向替换后的字符串的末尾。同时移动p1,p2, 将p1指的内容逐个复制到p2, 当p1遇到空格时，在p2处插入 %20， p1向前移动一个位置，p2向前移动3个位置，当p1和p2位置重适时，全部替换完成。
# 30ms
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
if not isinstance(s, str) or len(s) <= 0 or s == None:
return ''
spaceNum = 0
for i in s:
if i == " ":
spaceNum += 1
newStrLen = len(s) + spaceNum \* 2
newStr = newStrLen \*
indexOfOriginal, indexOfNew = len(s) - 1, newStrLen - 1
while indexOfNew >= 0 and indexOfOriginal <= indexOfNew:
if s == ' ':
newStr = ['%', '2', '0']
indexOfNew -= 3
indexOfOriginal -= 1
else:
newStr = s
indexOfNew -= 1
indexOfOriginal -= 1
return ''.join(newStr)
A2： python中可以利用append() ，新建list，一次遍历，遇到空格就添加 %20，否则就添加原始字符串s内容。
# 27ms
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
if not isinstance(s, str) or len(s) <= 0 or s == None:
return ''
result = []
for char in s:
if char == ' ':
result.append('%20')
else:
result.append(char)
return ''.join(result)
def replaceSpace(self, s):
# write code here
result = ''
for char in s:
if char == ' ':
result += '%20'
else:
result += char
return result
3.从尾到头打印链表arrayList：
遍历链表，生存在list中，然后倒序输出.
# 运行时间：24ms
# 占用内存：5752k
class Solution:
# 返回从尾部到头部的列表值序列，例如
def printListFromTailToHead(self, listNode):
# write code here
if listNode == None:
return []
result = []
while listNode != None:
result.append(listNode.val)
listNode = listNode.next
return result[::-1]
同样利用list，但是将其插入在list的0位置处。
# 运行时间：23ms
# 占用内存：5728k
class Solution:
# 返回从尾部到头部的列表值序列，例如
def printListFromTailToHead(self, listNode):
# write code here
if not listNode:
return []
result =[]
while listNode:
result.insert(0, listNode.val)
listNode = listNode.next
return result
4.两个栈实现一个队列：
stack2作为中转stack，直接对stack1做push，pop的时候将stack1的pop到stack2中，便可以实现。stack：先入后出，queue：后入先出。
# 运行时间：25ms
# 占用内存：5724k
# -\*- 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 len(self.stack1) == 0 and len(self.stack2) == 0:
return
if len(self.stack2) == 0:
while len(self.stack1) != 0:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
6.旋转数组的最小数字
Q: 把一个数组最开始的多少个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
A1: 遍历数组；
A2: 二分查找的变形，旋转数组的首元素肯定不小于旋转数组的尾元素，找一个中间点，假如中间点比首元素大，说明最小数字在中间点后面，假如中间点比尾元素小，说明最小数字在中间点前面。然后循环。 但是在一次循环中，首元素小于尾元素，说明该数组是排序的，首元素就是最小数字，假如出现首元素、尾元素、中间值三者相等，则只能在此地区中顺序查找。
# -\*- coding:utf-8 -\*-
class Solution:
# 运行时间：1127ms
# 占用内存：5864k
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
result = rotateArray
for num in rotateArray:
if num < result:
result = num
return result
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
left,right = 0,len(rotateArray)-1
if rotateArray < rotateArray:
return rotateArray
else:
while (right - left) > 1:
middle = (left+right)//2
if rotateArray <= rotateArray:
right = middle
elif rotateArray >= rotateArray:
left = middle
elif rotateArray == rotateArray == rotateArray:
minval = rotateArray
for num in rotateArray:
minval = min(minval, num)
return minval
return rotateArray
7.斐波那契数列
class Solution:
def Fibonacci(self, n):
# write code here
num1 = 0
num2 = 1
target = 0
for i in range(1, n+1):
num1 = num2
num2 = target
target = num1 + num2
return target
8.跳台阶：
和第七题类似，跳第n阶有两种环境，由倒数第二阶直接跳到第n阶，倒数第一阶直接跳到第n阶。
# -\*- coding:utf-8 -\*-
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
elif number == 2:
return 2
num1 = 1
num2 = 2
target = num1 + num2
for i in range(2, number-1):
num1 = num2
num2 = target
target = num1 + num2
return target
9.变态跳台阶：
通过归纳法得出规律，然后直接由公式求解。
# -\*- coding:utf-8 -\*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 2\*\*(number - 1)
10矩形覆盖：
# -\*- coding:utf-8 -\*-
class Solution:
def rectCover(self, number):
# write code here
if number == 1:
return 1
elif number == 2:
return 2
elif number == 0:
return 0
num1 = 1
num2 = 2
target = num1 + num2
for i in range(2, number-1):
num1 = num2
num2 = target
target = num1 + num2
return target
11. 二进制中1的个数：
将
n
n
n和
n
−
1
n-1
n−1按位做与运算，会将最右边的1设置为0。n不为0不绝统计统计个数。
# -\*- coding:utf-8 -\*-
class Solution:
# 运行时间：27ms
# 占用内存：5728k
def NumberOf1(self, n):
# write code here
count = 0
if n < 0:
n = n & 0xffffffff
while n!= 0:
count += 1
n = (n-1)& n
return count
12.数值的整数次方
通过递归求解，假如幂次是偶数，直接除以2，假如是奇数，提取一个base后除以2。举例发现规律。注意点：幂次是否小于0，奇偶幂次的区分，幂次为0和1
# -\*- coding:utf-8 -\*-
class Solution:
# 运行时间：23ms
# 占用内存：5624k
def Power(self, base, exponent):
# write code here
try:
if exponent >= 0:
return self.Power_value(base, exponent)
else:
return 1/self.Power_value(base, abs(exponent))
except:
print('base == zero')
def Power\_value(self, base, exponent):
if exponent == 1:
return base
elif exponent == 0:
return 1
if exponent%2 == 0:
return self.Power(base, exponent>>1)\*\*2
else:
return base\*self.Power(base, exponent>>1)\*\*2
接纳位运算可以加速速度，除以2可以通过向右移1位来实现，判断奇偶可以通过与1按位与来实现。
13.调解数组顺序使奇数位于偶数前面
python利用lambda办理。
class Solution:
# 运行时间：28ms
# 占用内存：5752k
def reOrderArray(self, array):
# write code here
return sorted(array,key=lambda c:c%2,reverse=True)
14.链表中倒数第k个结点：
https://img-blog.csdnimg.cn/img_convert/deabeefb4692c7050f22d0054a3e8554.png
https://img-blog.csdnimg.cn/img_convert/2eedd475dba4ceb22ff5a042f4c28c11.png
https://img-blog.csdnimg.cn/img_convert/64c4491dbeead124e03200651865ee21.png
既有得当小白学习的零底子资料，也有得当3年以上经验的小伙伴深入学习提拔的进阶课程，涵盖了95%以上Go语言开发知识点，真正体系化！
由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会连续更新
假如你需要这些资料，可以戳这里获取
ile n!= 0:
count += 1
n = (n-1)& n
return count
#### 12.数值的整数次方
通过递归求解，如果幂次是偶数，直接除以2，如果是奇数，提取一个base后除以2。举例发现规律。**注意点：幂次是否小于0，奇偶幂次的区分，幂次为0和1**
-*- coding:utf-8 -*-
class Solution:
运行时间：23ms
占用内存：5624k
def Power(self, base, exponent):
# write code here
try:
if exponent >= 0:
return self.Power_value(base, exponent)
else:
return 1/self.Power_value(base, abs(exponent))
except:
print('base == zero')
def Power\_value(self, base, exponent):
if exponent == 1:
return base
elif exponent == 0:
return 1
if exponent%2 == 0:
return self.Power(base, exponent>>1)\*\*2
else:
return base\*self.Power(base, exponent>>1)\*\*2
采用位运算可以加快速度，**除以2可以通过向右移1位来实现，判断奇偶可以通过与1按位与来实现。**
#### 13.调整数组顺序使奇数位于偶数前面
python使用lambda解决。
class Solution:
运行时间：28ms
占用内存：5752k
def reOrderArray(self, array):
# write code here
return sorted(array,key=lambda c:c%2,reverse=True)
#### 14.链表中倒数第k个结点：
[外链图片转存中...(img-334RyVBa-1715404659658)]
[外链图片转存中...(img-YsuGhiN4-1715404659658)]
[外链图片转存中...(img-H7TpVkQw-1715404659659)]
**既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上Go语言开发知识点，真正体系化！**
**由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新**
**[如果你需要这些资料，可以戳这里获取](https://bbs.csdn.net/topics/618658159)**
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]