20221011 蚂蚁笔试

第一题 好数

好数是指[0,99999]中每个数位都不相同的数，其中不足五位补前导零

例如02346，98765是好数，00001,99999不是

输入一个k，要求输出第k大的好数

题解

这题是唯一一个我没有ac的题，只过了66%，我想不到为什么暴力做法都过不了

q = []
for i in range(1234, int(1e5)):
    s = str(i)
    d = 5 - len(s)
    s = "0" * d + s
    if len(set(s)) == 5:
        q.append(int(s))
q.sort(reverse=True)
k = int(input())
print(k, q[k - 1])

第二题 丢桃子

输入一个n，范围[1,1e5],表示接下来有n行数据

输入x，y 表示第i个桃子坐标，范围[-1e9,1e9]

任意两个不同下标的桃子，只要横坐标相同或者纵坐标相同，可以得1分

就算是相同，也只能得1分。

题解

哈希表计算同一列和同一行的桃子数，还有一个哈希表计算重复坐标的桃子数

from collections import defaultdict
n = int(input())
row = defaultdict(int)
col = defaultdict(int)
seen = defaultdict(int)
res = 0
for i in range(n):
    x, y = map(int, input().split())
    res += row[x] + col[y] - seen[(x, y)]
    seen[(x, y)] += 1
    row[x] += 1
    col[y] += 1
print(res)

第三题

给定一个字符串s，长度[1,3e5]

好序列：长度为3，有两个字母相同，另外一个不同

求s有多少个子序列是好序列，结果需要对1e9+7取余

题解

从a到z枚举，当cnt[a]大于2的时候，我们从中间挑选2个，然后可以和其余任意字符搭配

即 cnt[ch] * (n-cnt[ch)

from collections import  Counter
from math import  comb
mod = int(1e9) + 7
s = input().strip()
n = len(s)
cnt = Counter(s)
res = 0
for i in range(ord('a'),ord('z')+1):
    ch = chr(i)
    if (v:=cnt[ch]) < 2:
        continue
    res += comb(v,2) * (n-v)
    res %= mod
print(res)

总结

挺简单的，就是第一题没过，很难接受