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作为修改后的目标，贪心两侧搜索，最终改写时对于可能使得字符串变大的情况：右侧改写优先否则左侧改写优先

2020 4.10 拼多多笔试

全站热榜