美团8.6笔试思路和python题解

ab两种点心，每个礼盒放3个点心，a、b至少各有一个，求最多能包多少个礼盒

签到题直接print就行，输出a、b、(a+b)//3的最小值

给一组0，-1，1数组，分割点k左大于等于0、右侧小于等于0的为异常数据，求最乐观情况下有多少个异常数据
类似接雨水问题，设定两个n+1的数组，分别代表k左侧和右侧异常数据个数，初始化为0，对原数组进行遍历，最后取left[i]+right[i]的最小值即可。
时间复杂度o(n)，空间复杂度o(n)
```
n = int(input())
nums = [int(i) for i in input().split()]
left = [0]*(n+1)
right = [0]*(n+1)
cur = 0
for i in range(1, n+1):
 if nums[i-1] >= 0:
     cur += 1
 left[i] = cur
cur = 0
for i in range(0, n):
 if nums[n-i-1] <= 0:
     cur += 1
 right[n - i - 1] = cur
ans = n
for i in range(n):
 ans = min(ans, left[i] + right[i])
# print(left, right)
print(ans)
```

给定两个代表正面和反面的数组，目标是通过反转将至少一半相同数字的面朝上，初始状态为全部朝上，求最少需要翻转多少次，无法达到目标输出-1
(1) 记录一个字典，key是数字，value是一个数组，对应数字的index，如果在反面数组中，取负
(2) 对该字典进行遍历，找出value的长度大于n/2，并且用绝对值+set排除正反都在value里的情况
(3) 因为要翻到正面，所以记录max(0, math.ceil(n/2)-正数的数量)即可

import math
n = int(input())
pos = [int(i) for i in input().split()]
neg = [int(i) for i in input().split()]
dic = {}
for i in range(n):
 if pos[i] in dic:
     dic[pos[i]].add(i)
 else:
     dic[pos[i]] = {i}
 if neg[i] in dic:
     dic[neg[i]].add(-i)
 else:
     dic[neg[i]] = {-i}
def rev(stone_set, n):
 count = 0
 for item in stone_set:
     if item > 0:
         count += 1
 return max(0, math.ceil(n/2)-count)
flag = False
ans = n
# print(dic)
for key, value in dic.items():
 tmp_list = [abs(i) for i in list(value)]
 tmp_set = set(tmp_list)
 if len(tmp_set) >= n/2:
     flag = True
     ans = min(ans, rev(value, n))
if flag:
 print(ans)
else:
 print(-1)

n个样本，k个类，每类假设m个样本，按照输入顺序，取m/2为训练集，剩下的为测试集。按照样本编号升序输出所有训练集样本及训练集样本

(1) 记录一个字典，key是类别，value是index数组
(2) 遍历字典，分别将每个index数组小于math.ceil(len(value)/2)的加入训练集，大于的加入测试集
(3) 训练集测试集排序输出

import math
n, k = [int(i) for i in input().split()]
classes = [int(i) for i in input().split()]
dic = {}
for i in range(n):
    if classes[i] in dic:
        dic[classes[i]].append(i)
    else:
        dic[classes[i]] = [i]
train = []
test = []
for key, value in dic.items():
    value = sorted(value)
    for i in range(len(value)):
        if i < math.ceil(len(value)/2):
            train.append(value[i]+1)
        else:
            test.append(value[i]+1)
train = sorted(train)
test = sorted(test)
for i in range(len(train)):
    if i != len(train)-1:
        print(train[i], end=' ')
    else:
        print(train[i])
for i in range(len(test)):
    if i != len(test)-1:
        print(test[i], end=' ')
    else:
        print(test[i])

#美团笔试#