数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找可删除的最小子列表的长度，以使列表和能被k整除
假设我们有一个包含正值的列表，称为nums，还有一个正数k。我们需要找到可以从nums中删除的最短子列表（可以为空）的长度，使得剩余元素的和能被k整除。但是我们不能删除整个列表。如果没有这样的子列表可以删除，则返回-1。
因此，如果输入类似于nums = [5,8,6,3] k = 8，则输出将为1，因为[5,8,6,3]的元素的当前和为22。如果我们删除长度为1的子列表[6]，则和为16，它可以被8整除。
为了解决这个问题，我们将遵循以下步骤：
- rem := (nums中所有元素的和 + k) mod k
- 如果rem等于0，则
- 返回0
- n := nums的大小
- presum := 0
- mp := 一个字典，最初为键0存储-1
- res := n
- 对于i从0到n - 1，执行以下操作：
- presum := presum + nums[i]
- m :=(presum + k) mod k
- mp[m] := i
- 如果(m - rem + k) mod k存在于mp中，则
- res := res和(i - mp[(m - rem + k) mod k])的最小值
- 如果res不等于n，则返回res，否则返回-1
示例
让我们看看以下实现以获得更好的理解：
def solve(nums, k):
rem = (sum(nums) + k) % k
if rem == 0:
return 0
n, presum = len(nums), 0
mp = {0: -1}
res = n
for i in range(n):
presum += nums[i]
m = (presum + k) % k
mp[m] = i
if (m - rem + k) % k in mp:
res = min(res, i - mp[(m - rem + k) % k])
return res if res != n else -1
nums = [5,8,6,3]
k = 8
print(solve(nums, k))输入
[5,8,6,3], 8
输出
1
更新于： 2021年10月18日
155 次浏览
广告