220918 字节后端笔试 金字塔 神奇数列 ASDF 书柜

卧槽 节！

第一题 AC

金字塔

方块的宽和高都是1，单位是m；不存在重叠的方块

输入：

n表示金字塔的层数，接下来n行，第 i 行表示第 i 层

第一个数m，表示这行有m个方块的左边缘的起始位置p[j] 单位是cm 默认递增

输出：

剩余的方块个数

方块存在至少要满足一个条件：

• 在第一层
• 重心在之前一层的方块上
• 左边缘和右边缘都在之前一层的方块上

不满足条件的方块可认为直接消失

数据范围：

1 < n <10 ^ 5

方块的总数量不超过10^5

方块的坐标不超过10 ^ 9

样例：

输入：

3

2 100 280

2 190 360

2 150 360

输出：

4

解释：

第一层 100 280 第一层默认保留

第二层

190的左边缘190在100这个方块[100,200]

190的右边缘290在280这个方块[280,380]，保留

第三层

150的重心200在190方块上，保留

输出 4

Solution

看懂了就会做了

由于都是有序的

用二分分别找两种情况是否满足即可

from bisect import *

n = int(input())
pre = list(map(int, input().split()[1:]))
res = len(pre)

def check(y):
    tn = len(pre)
    idx = bisect_left(pre, y + 50)
    if idx > 0 and pre[idx - 1] < y + 50 < pre[idx - 1] + 100:
        return True
    l = bisect_left(pre, y)

    if l > 0 and l < tn and y < pre[l - 1] + 100 and y + 100 > pre[l]:
        return True
    return False

for _ in range(n - 1):
    nums = list(map(int, input().split()[1:]))
    if not pre:
        continue
    cur = []
    for y in nums:
        if check(y):
            cur.append(y)
            res += 1
    pre = cur
print(res)

第二题 AC

神奇数列

神奇数列是指01数列，长度不小于3，且相邻两个字符不重复

输入：

s 表示一个01字符串，长度不超过10^5

输出

最长的神奇数列

Solution

唯一一道送分题

s = input().strip()
res = 0
pre = -1
cnt = 0
for v in s:
    if pre != v:
        pre = v
        cnt += 1
        res = max(res, cnt)
    else:
        cnt = 1
        pre = v

res = max(res, cnt)
print(res if res >= 3 else 0)

第三题 AC

ASDF

给定一个长度为4的倍数的ASDF字符串

你可以把任意子串换成一个新的ASDF字符串 使ASDF字符的数量相等

求这个子串的最小长度

样例

输入 s = “ADDF”

输出 1

把”D”换成”S“ 即可

Solution

其实这题一开始是用二分写的，但是只过70%，其余超时

先讲讲二分的思路，l=0, r = n

然后用滑动窗口去检查，满足的条件是剩下的字符个数全部小于等于n/4

这题的思路就是 我们要换掉 个数超过n/4的字符

这种字符最多有两个， 我称它为key

比如”FFFF“ 就是换掉3个f

比如”AASS” 就是换掉一个a 一个s

那我们就用滑动窗口去滑 当key字符的个数都不超过n/4 就是满足条件的窗口

from collections import Counter

s = input().strip()

def f():
    n = len(s)
    base = n // 4
    cnt = Counter(s)

    k = max(cnt.values()) - base
    if k <= 1:
        return k
    key = {}
    for i, v in cnt.items():
        if v > base:
            key[i] = v
    res = 10 ** 9

    l = 0
    for i, v in enumerate(s):
        if v not in key:
            continue
        else:
            key[v] -= 1
            while all(val <= base for val in key.values()):
                res = min(i - l + 1, res)
                if s[l] in key:
                    key[s[l]] += 1
                l += 1
    return res

print(f())

第四题 寄

书柜放书

这题总感觉做过，但是前面几题搞心态，最后没时间了

第一行，n，k

n表示书的个数

然后给你n本书的高度，一组书需要满足连续 且 最大高度差不超过k

输出

第一行 一组数最多有多少本 （假设为max）， 有多少种方案能实现max

然后输出你的方案

solution

用两个单调双端队列维护最大最小

然后滑动窗口滑

只过了10% 之后有机会再补

from collections import defaultdict, deque

n, k = map(int, input().split())
h = list(map(int, input().split()))
# n, k = 3, 3
# h = [14, 12, 10]
dic = defaultdict(list)
mq = deque()  # 越后越小
Mq = deque()  # 越后越大
# 实时维护当前组的最大最小值

# max_len = 0
# l = 0
# for i in range(n):

#     while mq and mq[-1][0] > h[i]:
#         mq.pop()
#     mq.append((h[i], i))

#     while Mq and Mq[-1][0] < h[i]:
#         Mq.pop()
#     Mq.append((h[i], i))
#     while Mq[0][0] - mq[0][0] > k:
#         if h[l] == mq[0][0]:
#             mq.popleft()
#         if h[l] == Mq[0][0]:
#             Mq.popleft()
#         l += 1
#     tn = max(i + 1 - mq[0][1], i + 1 - Mq[0][1])
#     if tn >= max_len:
#         max_len = tn
#         dic[tn].append(list(range(i + 2 - tn, i + 2)))

# print(max_len, len(dic[max_len]))
# for q in dic[max_len]:
#     print(" ".join(str(e) for e in q))