剑指Offer【Python实现】
2022/1/18 20:08:01
本文主要是介绍剑指Offer【Python实现】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
剑指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]
输出描述：
1
代码如下：
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 说明： 青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为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)\)
输入描述：
3
输出描述：
4
代码如下：
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
输出描述：
5
代码如下：
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) = 2f(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)
思路
-
- 遍历父结构
-
- 判断子结构是否相同
这篇关于剑指Offer【Python实现】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-02Python编程基础
- 2024-11-01Python 基础教程
- 2024-11-01用Python探索可解与不可解方程的问题
- 2024-11-01Python编程入门指南
- 2024-11-01Python编程基础知识
- 2024-11-01Python编程基础
- 2024-10-31Python基础入门：理解变量与数据类型
- 2024-10-30Python股票自动化交易资料详解与实战指南
- 2024-10-30Python入行：新手必读的Python编程入门指南
- 2024-10-30Python入行：初学者必备的编程指南
