Python 刷题笔记：数组专项练习一
Python 刷题笔记：数组专项练习一
昨天是刷题的第 25 天，基本保持了每天一两道，同步分享了其中前 35 题的记录。通过二十多天的摸索，慢慢熟悉 LeetCode 平台，为了提高刷题学习效率，我决定要改变刷题方式：由之前的按顺序做题改为通过标签分类的专项刷题。
可以看到，LeetCode 中对题目会有标签分类，昨天我们恰巧碰到 33-35 题三个连续的二分查找题目，经过整合练习，会有很明显地感觉到通过一系列地练习会更快捷掌握该算法的核心。所以今天起，我们也将按照专题来继续后面的刷题。今天就来数组专题，至于刷的题目，应该会比之前大大增多，看看能刷几道吧。
专题简介
❝数组是在程序设计中，为了处理方便，把具有相同类型的若干元素按有序的形式组织起来的一种形式。抽象地讲，数组即是有限个类型相同的元素的有序序列。若将此序列命名，那么这个名称即为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素。而用于区分数组的各个元素的数字编号则被称为下标，若为此定义一个变量，即为下标变量。链接：https://leetcode-cn.com/tag/array/ ❞
我们是 Python 来刷题，数组可以对应到 Python 中的列表，有限个类型相同的有序列表，又能够自由变换调整。至于下标，我们通常称为索引。
题目一
「第 1010 题：总持续时间可被 60 整除的歌曲」
难度：简单
在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1：
输入：[30,20,150,100,40]
输出：3
解释：这三对的总持续时间可被 60 整数：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60
示例 2：
输入：[60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。
#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60题目分析
题目题目中要求是歌曲对，即要对时间列表中的元素两两组合，和被 60 整除便算符合要求的一对。通常首先想到的算法就是循环遍历：
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
size = len(time)
count = 0
for i in range(size):
for j in range(i+1,size):
if (time[i]+time[j])%60==0:
count+=1
return count通过两层 for 循环，找到所有满足题意的组合，简单直接，但一旦提供的时间列表数据繁杂，这解法就会超时：
当数据量巨大时，我们的 for 循环嵌套导致过程太繁琐，导致超时无法通过测试。所以，我们要避开这个循环遍历的思路，重新设计。
思路尝试
回归题意中的要求：和被 60 整除。我们分析满足条件的数字规律，20 + 40 可以，80 + 40 也可以，20 和 80 等效、其相同点是整除 60 后结果是相同的。所以，关键点来了，时间列表中每个数字可能差异极大，但对题目生效的只有该数整除 60 的余数结果：余数为 1 的和余数为 59 的组合必然满足题意要求。
拿到所有余数后，其范围是 0 到 59。假设余数为 1 的有 10 个，余数为 59 的有 5 个，那么我们可以算出它们可以生成 10x5 = 50 对有效结果；但这里特殊的是余数为 0 和 30 的，假设余数为 30 的数字有 10 个，那么产生的不重复有效结果为 10x9/2 = 45 对。
整理一遍思路：先对时间列表中元素每个都整除拿到余数，对每个余数的个数进行一番统计，从统计结果出发，计算可以组合出 60 的结果个数。
代码实现
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
# 字典用来统计余数及出现次数
dic={}
for i,t in enumerate(time):
r = t%60
# 若字典中没有余数 r 记录，初始化为 0
dic.setdefault(r,0)
dic[r]+=1
# count 用来统计所有符合题意的组合数
count = 0
# 遍历 0 到 30，通过 60-i 便可拿到整除 60 后所有余数可能
for i in range(31):
# 如果余数为 0 或 30，单独处理
if i in [0,30]:
num = dic.get(i)
if num and num>1:
count+=num*(num-1)//2
# 正常组合为 60 的余数组，取到互配的余数个数，计算结果
else:
num1 = dic.get(i)
num2 = dic.get(60-i)
if num1 and num2:
count+=num1*num2
return count提交测试表现：
执行用时 : 304 ms, 在所有 Python3 提交中击败了 40.53% 的用户
内存消耗 : 17.3 MB, 在所有 Python3 提交中击败了 100.00% 的用户第一次能内存消耗击败 100%，笑得合不拢嘴啊！
观摩题解
总有更优的解在等着我们，题解中看到一份在遍历时间列表过程中通过两行代码实现计算过程的代码：
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
n = 0;
temp = [0]*60
for i in range(len(time)):
n += temp[(60 - time[i] % 60) % 60]
temp[time[i] % 60] += 1
pass
return n
#作者：zsq-9
#链接：https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/solution/py3jie-fa-by-zsq-9-34/- 先是对 0-59 这 60 种余数个数都默认为 0，并用 temp 列表存储
- 遍历时间列表时，查找 temp 列表中与该时间元素匹配的余数个数，计入到结果中
- 将该时间元素整除 60 的余数次数添加到 temp 结果中
思路非常巧妙地将记录余数个数、计算匹配对数放到了遍历时间列表过程中。至于这种思路如何设计，在理解了其设计的思路后，我觉得可能来源于向时间列表中加入新元素后如何基于之前直接得出结果的考虑。新加入一个元素，能与它匹配的就是余数和为 60 的，查找该余数的个数加到最终结果中，这样整个过程就可以同步到遍历时间列表中来实现了。
题目二
「第 1011 题：在 D 天内送达包裹的能力」
难度：中等
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1:
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3:
输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days题目分析
题目很绕，不同解读方式会导致完全不一样的思路。
先说下我最初的理解，看示例 1，给定重量列表 [1,2,3,4,5,6,7,8,9,10] 和天数 5，就是要生成一个新列表，其中 5 个元素，每个元素代表每天搬运的总重量，新列表中最大值即船舶最小运载能力。我们的任务就变成了将重量列表中的元素合并，直至其长度与天数一致。
现在重量列表有 10 个元素，最大值 10 假设为每天搬运上限的话，我们可以合并前 4 个元素求和得到 10 ，这样列表就变成了 7 个元素，即我们合并出一个 7 天完成搬运任务的方案。但仍达不到我们 5 天的目标，继续合并，具体过程如图：
最终合并出的 5 个元素代表 5 天完成任务的情况下每天运载的重量，最小的船舶运载能力即其最大值 15。
依照这个思路，可以写出一版操作列表的代码：
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
# 获取重量列表长度
length = len(weights)
# 每天重量上限，先设置为列表中最大值
limit = max(weights)
# 如果列表长度与天数相等，则每天一个元素，返回最大值
if length ==D:
return max(weights)
# while 循环通过列表长度与天数来比较，对重量列表不断合并子元素以缩减长度
while length>D:
# 记录合并完元素的列表lst，可以理解为记录每天搬运重量的列表
lst = []
r = 0
# 用于记录累计元素求和最小值，初始值设置大一些为 limit*2
add_min = limit*2
# 遍历重量列表
for w in weights:
# 如果之前重量r + 当前重量w 没有超过当天重量限制，将 w 加到当前重量中
if r + w <= limit:
r+=w
# 如果加了当前重量超限制
else:
# 记录超限的累计求和的最小值
add_min=min(add_min,r+w)
# 把之前重量（有可能是合并完的）存到列表中
lst.append(r)
# 将当前重量更新成 r
r = w
# 将 for 循环最后生成的 r 添加到记录中
lst.append(r)
# lst 即合并完的列表，其长度代表所需天数
length = len(lst)
limit = add_min
# 若 while 循环结束，则 lst 即合并后在目标天数完成的每天重量列表，返回其最大值
return max(lst)然而，由于可能遇到特别长的测试列表，while 循环中套了 for 循环遍历来一直合并元素生成列表，导致提交测试超时了：
没辙，这个分析不靠谱，换个思路重新来。
思路尝试
在上面我们对列表元素合并过程中，合并的标准就是累加和不超过当日重量限制。题目要求解的船舶最低运载能力其实也是当日重量限制的最小值。刚超时的思路关注点一直在重量列表上，现在我们把注意力转移到这个重量限制上来。还是看示例 1 最初重量列表为 [1,2,3,4,5,6,7,8,9,10] ，那么每天重量限制最低也是 10，我们以此为限制即可得出 7 天完成搬运的方案（对应刚我们分析过程中的第一波合并）。要想缩短天数，就要提高限制，那么每天搬运的上限是多少呢？那就是我们一天把所有重量全部搬运完，上限也就是重量列表求和结果 55。
现在问题就变成了，我们要在 [10，55] 中找一个最小值，使得搬运天数为 5。我们需要制定有重量限制求出相应搬运天数的方法，此时这问题便可以通过二分法来不断缩小重量范围，直到找到搬运天数为 5 的最小值。
最初没看题解时，我看到有个“二分查找”的标签还很诧异，重量列表无序的，怎么应用二分查找？考虑半天没头绪，看到题解中提示对重量进行二分求解，豁然开朗！
刚我们超时的方案，在 while 循环中不断探索这个重量限制，虽然也是不断接近目标值，但二分法明显会效率更高。
代码实现
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
# 定义由重量列表、重量限制，求搬运天数的方法
def get_days(lst,limit):
r = 0
record = []
# 遍历重量列表
for w in lst:
# 若加完当前重量仍未超限制，将当前重量加起来
if r+w<=limit:
r+=w
# 若加完超限，则将超限前的重量加入结果列表中
else:
record.append(r)
r = w
record.append(r)
# record 即记录每天搬运重量的列表，长度为天数
return len(record)
# 二分法查找重量限制
# 左边界，重量限制最小值，重量列表最大值
left = max(weights)
# 右边界，重量限制最大值，重量列表求和
right = sum(weights)
# 如果二者相等，说明列表就一个元素
if left==right:
return left
# while 循环控制移动左右边界
while left<right:
# 取中点
mid = (left+right)//2
# 通过定义的方法获取天数
result = get_days(weights,mid)
# 如果天数大于目标，说明重量限制偏小，移动左边界
if result>D:
left = mid+1
# 否则移动右边界
else:
right = mid
# 最终将跳出 while 循环的结果返回
return left提交测试结果：
执行用时 : 604 ms, 在所有 Python3 提交中击败了 70.18% 的用户
内存消耗 : 16.8 MB, 在所有 Python3 提交中击败了 33.33% 的用户看题解中基本也都是直接应用的二分查找法，然而我却陷在怎么将二分查找与题目联系起来的坑里。先自行尝试了超时的那版代码，又看题解中提示对重量进行二分查找，才完成了这一版代码。不过还好，之前分析过程中许多思路都被用到了求天数的过程中，也不算白费功夫。
结论
按专题看，今天应该是数组类题目，原本想多刷几道，奈何卡在了第二个题。不过幸运的是，昨天刚专门集中练习了二分查找法，今天又碰到了其应用，可惜没能反应过来、借助提示才完成题目。可见对二分法的使用可能掌握了，但对题目的分析与判断还需继续练习。
数组类题呢，数组只是个数据类型，并没有限定算法，很多其它类题目只要带着数组的也都会被分到此标签下。解决过程中针对数组，要掌握其数据规律，注意其遍历过程的设计。目前加上之前刷的三十多道，我们已经做过 16 道数组类题目了，所以明天会先换偏特定算法练习的专题来练习，之后再继续对数组类题目的探索。
今天算是开启专项练习的第二天，昨天碰巧是二分查找的专项练习，之后计划先把所有标签都接触一遍，对题目种类有整体概念。有想一起刷题的小伙伴也可以来多多交流哈！