蚂蚁笔试0509，思路分享

这次蚂蚁笔试感觉比阿里简单点，选择就不说了，随缘选。

编程本人：2.9/3，主要卡在第二题，下面分享个思路吧：

1.找第i个不带重复数字的16进制数字

解法：直接暴力找即可。

注意：16进制里的字母要大写，刚开始弄成小写，只能过40%，改成大写就100%了

2.对于一组数字，有些数字的某些位置被“？”覆盖了，“？”可以是任意数字，找极差最大情况。

解法：分享个暴力思路：先把没“？”的存起来，找最大最小值，然后在把有“？”的数字字符串存起来，根据字符串大小排序。

比如：[1, 12, ??8, ?, 1?], 改成 [1, 12]+[??8, ?, 1?]

则最大数为？？8改成998，最小数为？改成0，输出极差998

注意：这里有个问题没考虑，就是对于带？的数字，他只能变最大值，或者变最小值，变一次就不能再变了。刚开始没注意这种情况，最后没时间改了，只通过90%。

3.定义好串，当且仅当每个字母出现的次数均为偶数。计算该字符串有多少子序列是好串？（子序列在原串中可以不连续）。例如，"arcaea"的子序列有"aaa"、"ace"等等。

解法：排列组合问题。

1.对于一个字符串 ，先计算出每个字符出现的个数。

2.让每个字符出现偶数次的组合相乘（0次，2次，4次，……）就是答案。

也就是说：ans =（字符1出现0次+字符1出现2次+...)*(字符2出现0次+字符2出现2+...)*……*（字符n……）

3. 对应字符a，他的个数为n，可以用组合公式写为：ans = C(n,0)+C(n,2)+C(n,4)+...+C(n,n) * 其他字符组合数

4.由于二项式定理：C(n,0)+C(n,2)+C(n,4)+...+C(n,n)（如果n是奇数，这里就是n-1）=2^(n-1)

5 综上所述，令n为字符个数的列表，则 ans = 2^(n[i]-1)

s = "arcaea"
M = 10*9+7
dic = {}
for i in s:
  dic[i] = dic.get(i,0) + 1
ans = 1
for k, v in dic.items():
    ans *= 2**(v-1)
    ans %= M
# 保证结果大于0
print((ans - 1 + M) % M)