美团算法笔试 8.6
emm，比较简单的，4个题都ac了，要是面试也这么简单的就好了，最近面试天天手写网络快裂开了
第一题 两种糖，每次拿三个，要求每种至少一个，求最多取几次。
n = int(input().strip())
for _ in range(n):
x, y = list(map(int, input().strip().split()))
minx = min(x, y)
total = x + y
minx = min(minx, total//3 + 1)
while 3 * minx > total:
minx -= 1
print(minx)
print('AC') 话说这个题不把total/3和min比大小会超时
第二题
有一个数组由0，1，-1组成，找一个分割点，分割点左面>=0个数加上右面<=0个数最小
n = int(input().strip())
nums = list(map(int, input().strip().split()))
left = [0]*n
ans = n
for i in range(n):
if i:
left[i] = left[i-1]
if nums[i]>=0:
left[i] += 1
right = 0
for j in range(n-1, -1, -1):
if j==n-1:
ans = min(ans, left[j])
else:
if nums[j+1]<=0:
right += 1
ans = min(ans, left[j] + right)
print(ans)
print('AC') 第三题
魔法阵翻转，有n个硬币，开始时候都是正面，正面背面都有数字，要求翻转硬币达到正面相同数字个数大于等于n的一半，求最小翻转次数
import math
n = 6
tmp = [10,3,7,3,5,10]
tmp2 = [10,10,10,9,10,7]
table = dict()
table2 = dict()
count = int(n / 2 + 0.5)
for i in range(n):
if tmp[i] not in table:
table[tmp[i]] = {i}
else:
table[tmp[i]].add(i)
if len(table[tmp[i]]) >= count:
print(0)
exit()
ans = math.inf
for i in range(n):
if tmp2[i] not in table:
table[tmp2[i]] = {i}
if tmp2[i] not in table2:
table2[tmp2[i]] = 1
else:
table2[tmp2[i]] += 1
else:
if i in table[tmp2[i]]:
continue
else:
table[tmp2[i]].add(i)
if tmp2[i] not in table2:
table2[tmp2[i]] = 1
else:
table2[tmp2[i]] += 1
if len(table[tmp2[i]]) >= count:
ans = min(ans, table2[tmp2[i]])
if ans == math.inf:
print(-1)
else:
print(ans)
print('AC') 第四题
有n个样本，一共k个类别，按照样本序号给个数组，值是类别，要求划分训练测试集，训练集是类别样本个数/2，向上取整，要求输出训练验证集的序号，从小到大排列
from collections import defaultdict
n, k = list(map(int, input().strip().split()))
nums = list(map(int, input().strip().split()))
cla = defaultdict(int)
for i in range(n):
cla[nums[i]] += 1
for key in cla.keys():
cla[key] = int(cla[key]/2 + 0.5)
train = list()
test = list()
for i in range(n):
val = nums[i]
if cla[val]>0:
train.append(i+1)
cla[val] -= 1
else:
test.append(i+1)
print(' '.join(map(str, train)))
print(' '.join(map(str, test)))
print('AC') 投个票看看美团笔试难度
得物app公司福利 402人发布