美团8.6笔试思路和python题解

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

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

2. 给一组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)

3. 给定两个代表正面和反面的数组，目标是通过反转将至少一半相同数字的面朝上，初始状态为全部朝上，求最少需要翻转多少次，无法达到目标输出-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)

4. 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])