蚂蚁0915算法岗笔试题解
T1：一个整数x，小红小紫每次可以选择x的一个因子k（要求k为素数）。小红先手，谁先不能操作谁输，问谁赢谁输？
思路：求x的所有质因子个数
import math
def divide(n):
res = 0
for i in range(2, int(math.sqrt(n))+1):
while n % i == 0:
res += 1
n = n // i
if n > 1:
res += 1
return res
x = int(input())
ans = divide(x)
if ans % 2:
print('xiaohong')
else:
print('xiaozi') T2：给定一个长度为n的数组，对于每个k，k∈[1, n]，求有多少个长度为k的连续上升子数组？
eg：2 3 4 4 2， 长度为1的有[2], [3],...,[2]共5个，长度为2的有[2,3], [3,4]共2个，长度为3的有[2,3,4]共1个，没有长度为4和为5的。返回[5,2,1,0,0]
思路：dp求出以每个元素为结尾的最长连续上升子数组长度l。那么长度为 [1, l ] 的子数组个数都要+1。得到所有长度集合后，用双指针+dp的技巧计算长度数组可以将o(n^2)复杂度降为o(nlogn)。
from collections import Counter
n = int(input())
nums = list(map(int, input().split()))
ans = [0]*n
dp = [1]*n
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
dp[i] += dp[i-1]
count = Counter(dp)
count = sorted([(k,v) for k,v in count.items()], reverse=True)
ans = [0]*(n+1)
i, j = 0, n
while i < len(count) and j >= 0:
while j >= count[i][0]:
j -= 1
ans[j] = ans[j+1] + count[i][1]
i += 1
print(' '.join(map(str, ans[:-1]))) T3：定义字符串中每个字母出现的次数是偶数为好串，问对于一个字符串，有多少子序列是好串（子序列可以不连续）？
eg："ababa"有"aa"4个，"bb"1个，"abab"1个，"abba"1个，"baba"1个
思路：统计字符串中的各字母数，然后排列组合算所有可能数。例如a有5个，那么可以选择4个a，2个啊，0个a，对应是C54+C52+C50的总可能数，其他字母也一样，然后相乘就行。
拓展：可以思考一下如果子串为连续串的做法，状态前缀+动态哈希能搞定[之前微软笔试碰到过]
from collections import Counter from functools import reduce import math MOD = 10**9+7 strings = input() scount = Counter(strings) cntlist = [v for k, v in scount.items()] computelist = [] for cnt in cntlist: p = cnt if cnt % 2: p -= 1 comp = 0 for i in range(p, -1, -2): comp += math.comb(cnt, i) ## compute C cnt i computelist.append(comp) ans = (reduce((lambda x, y: x*y), computelist) - 1) % MOD print(ans)
，校友加油
