字节0918算法岗笔试题解
T1：金字塔石块掉落
思路：双指针模拟即可
T2：10101神奇序列，将1和0没有重复并且至少长度为3的为神奇序列，求序列中最长的神奇序列
思路：遍历一遍，碰到前后相同的让长度清零即可
T3：ASDF字符串转换成平衡字符串（各字符数目相等），求满足要求的最小子字符串
思路：先统计多出来的字符串，然后双指针去序列中找
from collections import Counter
## ASAFASAFADDD
strings = input()
len(strings)
n = len(strings) // 4
s_cnt = Counter(strings)
s_need = {}
need = 0
for s, cnt in s_cnt.items():
if cnt - n > 0:
s_need[s] = cnt - n
need += cnt - n
left = 0
ans = len(strings)
for i in range(len(strings)):
if strings[i] in s_need:
s_need[strings[i]] -= 1
if s_need[strings[i]] >= 0:
need -= 1
while need == 0:
ans = min(ans, i-left+1)
if strings[left] in s_need:
s_need[strings[left]] += 1
if s_need[strings[left]] > 0:
need += 1
left += 1
print(ans) T4：同组放书，同一组为相邻的（可理解为连续子串），要求同一组中最大值和最小值之差绝对值不超过k，求一组中最多能放多少本书。
思路：双指针+双端单调栈维护区间最大/最小值。入栈时的贪心思想：例如最大值栈中，若后进的元素比栈中早进的元素大，那么这些既比新元素小还会比新元素早过期的栈内元素是毫无意义的，可以全部弹出。
from collections import deque n, k = map(int, input().split()) nums = list(map(int, input().split())) left, maxlenth = 0, 0 ans = [] max_stack, min_stack = deque(), deque() for i in range(n): while max_stack and nums[i] >= nums[max_stack[-1]]: max_stack.pop() while min_stack and nums[i] <= nums[min_stack[-1]]: min_stack.pop() max_stack.append(i) min_stack.append(i) while nums[max_stack[0]] - nums[min_stack[0]] > k: if max_stack[0] <= left: max_stack.popleft() if min_stack[0] <= left: min_stack.popleft() left += 1 if i - left + 1 > maxlenth: ans = [(max_stack[0], min_stack[0])] elif i - left + 1 == maxlenth: ans.append((max_stack[0], min_stack[0])) maxlenth = max(maxlenth, i-left+1) print(maxlenth, len(ans)) for a in ans: print(a[0]+1, a[1]+1)
类似资料：