2024年最全《剑指offer》详解-Python(3)，2024年最新程序人生 ...

千千梦丶琪 · 2024-8-26 12:39:07

既有得当小白学习的零底子资料，也有得当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.表现数值的字符串
    - 矩阵中的路径
    - 参考资料：

class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if array == []:
return False
num_row = len(array)
num_col = len(array[0])
i,j = 0, num_col-1
while j >= 0 and i < num_row:
if array[i][j] > target:
j -= 1
elif array[i][j] < 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 \* [None]
indexOfOriginal, indexOfNew = len(s) - 1, newStrLen - 1
while indexOfNew >= 0 and indexOfOriginal <= indexOfNew:
if s[indexOfOriginal] == ' ':
newStr[indexOfNew - 2: indexOfNew + 1] = ['%', '2', '0']
indexOfNew -= 3
indexOfOriginal -= 1
else:
newStr[indexOfNew] = s[indexOfOriginal]
indexOfNew -= 1
indexOfOriginal -= 1
return ''.join(newStr)

复制代码

A2： python中可以利用append() [O(1)]，新建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:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
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:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
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[0]
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[left] < rotateArray[right]:
return rotateArray[left]
else:
while (right - left) > 1:
middle = (left+right)//2
if rotateArray[middle] <= rotateArray[right]:
right = middle
elif rotateArray[middle] >= rotateArray[left]:
left = middle
elif rotateArray[middle] == rotateArray[right] == rotateArray[left]:
minval = rotateArray[0]
for num in rotateArray:
minval = min(minval, num)
return minval
return rotateArray[right]

复制代码

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个结点：

既有得当小白学习的零底子资料，也有得当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企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

2024年最全《剑指offer》详解-Python(3)，2024年最新程序人生 ...

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云