剑指offer【10~19】
剑指offer【10~19】
echobingo
发布于 2019-12-20 11:57:23
发布于 2019-12-20 11:57:23
题目链接：
剑指offer 10-19
Python 实现：
10.1 斐波那契数列
只需要两个变量记录前两个状态即可，不需要递归和大小为 n 的数组保存。
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0 or n == 1:
return n
pre1, pre2, ans = 0, 1, 0 # pre1 和 pre2 分别记录前两个状态
for i in range(2, n + 1):
ans = pre1 + pre2
pre1 = pre2
pre2 = ans
return ans10.2 矩形覆盖
实际上就是斐波那契数列。注意 f(1) = 1，f(2) = 2
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number <= 2:
return number
pre1, pre2, ans = 1, 2, 0
for i in range(3, number + 1):
ans = pre1 + pre2
pre1 = pre2
pre2 = ans
return ans10.3 跳台阶
实际上就是斐波那契数列，代码和 10.2 一模一样。
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number <= 2:
return number
pre1, pre2, ans = 1, 2, 0
for i in range(3, number + 1):
ans = pre1 + pre2
pre1 = pre2
pre2 = ans
return ans10.4 变态跳台阶
f(n) = f(n-1) + f(n-2) + ... + f(0)，其中 f(i) 表示从第 i 层跳到第 n 层的跳法。化简的 f(n) = 2 * f(n-1)，故为公比为 2 的等比数列，总跳法为 2 ^ (n-1)。
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 2 ** (number - 1)11. 旋转数组的最小数字
二分查找，每次 mid 和上界 hi 去比较。注意数组可以有重复，如 3,3,3,1,2,3 这种，判断一下等号应该放在哪个条件上。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if not rotateArray:
return 0
lo, hi = 0, len(rotateArray) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if rotateArray[mid] >= rotateArray[hi]: # 非递减，所以取等号
lo = mid + 1
elif rotateArray[mid] < rotateArray[hi]:
hi = mid
return rotateArray[lo]12. 矩阵中的路径
DFS 回溯法。注意如果先搜索 b，需要将 b 标记为已经使用，防止重复使用。在这一次搜索（上下左右）结束之后，需要将 b 的原来状态改回来，并搜索 c。
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
def judgePath(i, j, path):
if not path:
return True
tmp = matrix2[i][j] # 先用 tmp 记录 matrix[2] 的状态
matrix2[i][j] = None
for p in pos:
if 0<=i+p[0]<rows and 0<=j+p[1]<cols and matrix2[i+p[0]][j+p[1]] != None and matrix2[i+p[0]][j+p[1]]==path[0]:
if judgePath(i+p[0], j+p[1], path[1:]):
return True
matrix2[i][j] = tmp # 将 matrix[2] 位置的状态改回来
return False
if not path:
return True
matrix2 = [[''] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
matrix2[i][j] = matrix[i*cols+j]
pos = [[-1,0], [1,0], [0,-1], [0,1]] # 上下左右
for i in range(rows):
for j in range(cols):
if matrix2[i][j] == path[0]:
if judgePath(i, j, path[1:]):
return True
return False13. 机器人的运动范围
DFS 回溯法。先构造矩阵，将能到达的坐标置为 1，不能到达的坐标置为 0，就可以将此题转化为从 (0, 0) 点开始求连通面积问题。和 Leetcode 【DFS】695. Max Area of Island 类似。注意这题和上面 12 题的区别在于探索到一个点，回溯过程不需要改回去原来的状态。
# -*- coding:utf-8 -*-
class Solution:
def movingCount(self, threshold, rows, cols):
# 转化为从 (0, 0) 点开始求连通面积问题
def count(i, j):
ans = 1
matrix[i][j] = 0 # 不需要改回去
for p in pos:
if 0<=i+p[0]<rows and 0<=j+p[1]<cols and matrix[i+p[0]][j+p[1]]==1:
ans += count(i+p[0], j+p[1])
return ans
# write code here
if threshold < 0:
return 0
matrix = [[0] * cols for _ in range(rows)]
for i in range(rows): # 将能到达的坐标位置改为 1
for j in range(cols):
if sum([int(num) for num in list(str(i))]) + sum([int(num) for num in list(str(j))]) <= threshold:
matrix[i][j] = 1
pos = [[-1,0], [1,0], [0,-1], [0,1]]
return count(0, 0)14. 剪绳子
找规律，含有越多因子 3 的乘积越大。
class Solution:
def integerBreak(self, n: int) -> int:
if n <= 3: return n - 1
div, mod = divmod(n, 3)
if mod == 0: return 3 ** div
if mod == 1: return 3 ** (div - 1) * 4
if mod == 2: return 3 ** div * 215. 二进制中 1 的个数
刚开始写的代码如下，但是出错了。因为下面代码无法处理负整数的情况。比如 n = -3，-3 的补码是 101，>> 1 变成 110，110 表示 -2，再 >> 1 会变成 111，111 表示 -1，之后会陷入死循环，一直是 -1）
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
cnt = 0
while n:
if n & 1:
cnt += 1
n = n >> 1 # 除以 2
return cnt发现新大陆之使用 n & (n-1)，可以去除 n 的位级表示中最低的那一位 1。正确的代码如下。注意：while 判断条件是 n & 0xffffffff，因为 Python 的整数类型是没有范围限制的，比如 -1 会表示成 11111111...(都是符号位)1，n & (n-1)每次只会消掉末尾的一个 1，所以如果不加 & 0xffffffff，还是会无限循环。但是 C++ 和 Java 就可以不用加，因为它们对整数的定义就是 int 为 4 个字节（最大数就是 0xffffffff），不会死循环。
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
cnt = 0
while n & 0xffffffff: # python 对整数没有取值范围限制，因此对负数会无限循环
cnt += 1
n = n & (n - 1) # 删去末尾的 1
return cnt16. 数值的整数次方
快速幂算法，注意负指数的处理。
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
isNegative = False
if exponent < 0: # 将指数转化为正数
isNegative = True
exponent *= -1
ans = 1
while exponent:
if exponent & 1:
ans *= base
base *= base
exponent >>= 1
return ans if isNegative == False else (1 / ans) # 负指数是 ans 的倒数17. 打印从 1 到最大的 n 位数
因为可能 n 很大，因此数字要用数组存储。可以使用 DFS 回溯法构造每个数字，打印出来。回溯深度为 n，每一个位置有 0~9 这10种算符选择。
# -*- coding:utf-8 -*-
class Solution:
def print1toN(self, n):
# write code here
def search(k): # k 为深度
if k == n:
printNum()
return
for i in range(10): # 算符种数
nlist[k] = str(i)
search(k + 1)
def printNum(): # 打印结果
ans, flag = "", True
for ch in nlist:
if ch == '0' and flag: # 去除前导 0
continue
else:
flag = False
ans += ch
if ans: # 不为 ""
print(ans, end=" ")
nlist = ['0'] * n # 字符列表存储各个数字
search(0) # 回溯法构造每个数字
Solution().print1toN(3) # 结果为 1 2 3 ... 99918.1 在 O(1) 时间内删除链表节点
分两种情况：（1）删除的结点是尾结点；（2）删除的结点不是尾结点。
- ① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
- ② 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 None，时间复杂度为 O(N)。
综上，如果进行 N 次操作，那么大约需要操作节点的次数为 O(1) * (N-1) + O(N) * 1 ，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，**N* 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。因此该算法的平均时间复杂度为 **`[O(1) (N-1) + O(N) * 1] / N = O(1)`**。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNone(self, phead, delnode): # delnode 为要删除的结点的指针
# write code here
if not phead or not delnode: # 都为空
return phead
if delnode.next: # 待删除的结点不是尾结点，O(1)
last = delnode.next
delnode.val = last.val
delnode.next = last.next
else: # 待删除的结点是尾结点
if phead == delnode: # 只有一个结点
phead = None
else:
pre = phead # O(n)
while pre.next != delnode:
pre = pre.next
pre.next = None # 令倒数第二个结点的下一个结点指向 None
return phead18.2 删除链表中重复的结点
方法1：使用三个指针，每次进行交换和移动。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
if not pHead:
return None
dummy = ListNode(-1) # 头节点
dummy.next = pHead
pHead = dummy
# pre为cur的前一个结点，便于删除操作，cur指向相同元素的第一个结点，last为工作指针
pre, cur, last = pHead, pHead.next, pHead.next.next
isDup = False # 标记某一段是否有重复
while last:
if cur.val == last.val and isDup == False: # last 往后移即可
isDup = True
elif cur.val != last.val and isDup == True: # 有重复
pre.next = last
cur = last
isDup = False
elif cur.val != last.val and isDup == False: # 无重复
pre = cur
cur = last
last = last.next
if isDup == True: # [1,1] or [1,2,2] 这种
pre.next = None # [1,2,2]
return pHead.next # 注意去掉头部的空结点方法2：递归，比较好理解。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
if not pHead or not pHead.next:
return pHead
cur = pHead.next
if pHead.val != cur.val: # [1,2,3,3,4]
pHead.next = self.deleteDuplication(pHead.next)
return pHead
else: # [1,1,1,1,2]
while cur and pHead.val == cur.val:
cur = cur.next
return self.deleteDuplication(cur)19. 正则表达式匹配
递归。分为四种情况：
- s 和 p 均为空：返回
True - s 不为空，p 为空：返回
Fasle - s 为空，p 不为空：
（1）如果 p 的第二个字符为
***：，递归调用返回match(s, p[2:])（2）否则**返回False - s 不为空，p 不为空：
（1）如果 p 的第二个字符为
***：如果 s0 和 p0 匹配，递归调用返回mathc(s, p[2:]) || match(s[1:], p)；否则递归调用返回match(s, p[2:])（2）否则：**如果 s0 和 p0 匹配，递归调用返回mathc(s[1:], p[1:])；否则返回False
# -*- coding:utf-8 -*-
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# write code here
if not s and not pattern: # 均为空
return True
if s and not pattern: # s 不为空，pattern 为空
return False
if not s and pattern: # s 为空，pattern 不为空
if len(pattern) > 1 and pattern[1] == '*': # pattern 的第二个字符为 *
return self.match(s, pattern[2:])
else:
return False
if s and pattern: # s 不为空，pattern 不为空
if len(pattern) > 1 and pattern[1] == '*': # pattern 的第二个字符为 *
if s[0] == pattern[0] or pattern[0] == '.':
# 前者为 "ab" -> "a*ab" 这种，后者为 ab" -> "a*b" 这种
return self.match(s, pattern[2:]) or self.match(s[1:], pattern)
else: # "ab" -> "c*ab" 这种
return self.match(s, pattern[2:])
else: # pattern 的第二个字符不为 *
if s[0] == pattern[0] or pattern[0] == '.': # "ab" -> "ab" 这种
return self.match(s[1:], pattern[1:])
else:
return False剑指 offer 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录