2020 4.10 拼多多笔试
两个小时，4道编程题， AC3.3， 记录一下
第一题比较简单、第四题不会，所以只贴二三题
2. 给定一个数组大小为N， 求能整除M的连续子数组的数量
N, M = map(int, input().split()) nums = list(map(int, input().split())) sums = [0] for i in range(N): sums.append(sums[-1]+nums[i]) cnt = 0 from collections import defaultdict dic = defaultdict(list) for i in range(0, len(sums)): dic[sums[i]%M].append(i) for i in range(M): cnt += len(dic[i]) * (len(dic[i])-1) // 2 print(cnt)此题最直观的解决方案是穷举所有的(i, j)， 但只能AC 50%, 使用余数字典可以大大简化时间复杂度
leetcode上有原题: 974 https://leetcode.com/problems/subarray-sums-divisible-by-k/
3. 给定字符串长度为N，字符串只会包括'0'-'9'， 要求修改字符串使得至少有一个字符出现K次， 修改每个字符的代价为对应数字的变化大小，求最小代价，并输出最小代价下的最小字符串
例如： 对于字符串 '787855', K = 5， 则最小代价应该为4， 并且输出最小字符串'777757'（不能是'777775'， 因为不满足最小字符串）
N, K = map(int, input().split())
nums = [int(x) for x in list(input())]
from collections import defaultdict
dic = defaultdict(int)
for x in nums: dic[x] += 1
if max(dic.values()) >= K: #没什么用貌似
print(0)
print(''.join([str(x) for x in nums]))
else:
cost_final = float('inf')
need_final = defaultdict(int)
final_i = 0 #记录最终的target，即满足count(target) >= K
for i in range(0, 10): #穷举所有可能的target
cost = 0 #记录代价
needs = defaultdict(int) #needs[i]表明最后需要改写i->target的次数
j = 1 #贪心两侧搜索， 使用i+j&nbs***bsp;i-j 改写为i
need = K - dic[i]
while need > 0:
if i+j < 10 and dic[i+j] > 0: #先 贪心向上探索
if dic[i + j] >= need:
cost += need*j
needs[i+j] = need
need = 0
else:
cost += dic[i+j]*j
needs[i+j] = dic[i+j]
need -= dic[i + j]
if i-j >= 0 and need and dic[i-j] > 0: #后 贪心向下探索
if dic[i - j] >= need:
cost += need * j
needs[i-j] = need
need = 0
else:
cost += dic[i-j] * j
need -= dic[i-j]
needs[i-j] = dic[i-j]
j += 1
if cost < cost_final:
cost_final = cost
need_final = needs
final_i = i
# print(cost_final, need_final, final_i)
print(cost_final)
for i in range(len(nums)):
if need_final[nums[i]] > 0:
if nums[i] > final_i: #改写成更小的数字， 左边优先
need_final[nums[i]] -= 1
nums[i] = final_i
else:
if dic[nums[i]] > need_final[nums[i]]: #改写成更大的数字， 右边优先
dic[nums[i]] -= 1
continue
need_final[nums[i]] -= 1
dic[nums[i]] -= 1
nums[i] = final_i
print(''.join([str(x) for x in nums]))
解决方案：穷举0-9作为修改后的目标， 贪心两侧搜索， 最终改写时对于可能使得字符串变大的情况：右侧改写优先 否则左侧改写优先
