美团8.16笔试 算法类 2.5/4

💻题目：8道单选（20分），4道编程（80分）

❓第一题思路：可以简单理解为把一个数二进制表示里的1，赋给数组里的二进制表示里同一位置的0，问最多能赋多少个1，换句话说，把数组里的数想象成带有插槽的数，二进制表示中的0就是插槽，比如5，二进制表示101，有1个插槽。那所有数一共有多少个插槽（同一个位置算一个）就是把所有数与起来，要求的最大值就是把插槽填满。

比如：nums = [2, 7, 6, 10]，与起来的结果是0010，那就需要1101来插，答案就是13

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    _sum = sum(nums)
    _max = max(nums)
    for i in range(1, n):
        nums[0] = nums[0] & nums[i]
    ans = (1 << _max.bit_length()) - 1 - nums[0]
    print(_sum + ans, ans)

❓第二题思路：按照题目给的流程走就行，用eval()函数可以直接转换输入

❓第三题：跳过，输出NO：7.41%

❓第四题：O(N^2)算法：50%，大概思路是从后往前找，记录更小值出现的次数

n = int(input())
nums = list(map(int, input().split()))
if n <= 2:
    print(0)
else:
    cnt = 0
    for i in range(3, n):
        smaller_before = 0
        for j in range(i-1, -1, -1):
            if nums[j] < nums[i]:
                smaller_before += 1
            elif nums[j] > nums[i]:
                cnt += smaller_before
    print(cnt)

AC：2.5/4，对于不刷题也没有竞赛经验的我，后面两道确实有点难做了