字节笔试 9.18 后端方向思路

金字塔累方块

• 数组保存一层可放置的方块左端点
• 放置新一层是，符合三种情况之一则可以放置
  • 地面层
  • 重心落于上一层的方块区间内
  • 左右端点同时落于上一层的方块区间内
• 由于每一层保存的端点为有序的，因此判断一点是否落于一层的区间用的二分
• 只过了92%，可能哪里没处理好

神奇序列

• dp0[i]保存以0结尾的最长神奇序列长度
• dp1[i]保存以1结尾的最长神奇序列长度

    if (s[i] == '1') {
        dp1 = dp0 + 1;
        dp0 = 0;
    }
    else {
        dp0 = dp1 + 1;
        dp1 = 0;
    }
    if (max(dp0, dp1) >= 3)
        ans = max(ans, max(dp0, dp1));

ASDF

假设字串长度为4n，则字频应该为n

• 遍历，计算ASDF四种字母出现的次数
• 替换字串满足的要求：
  • 对于出现超出n次的字母，需要在替换字串中包含(count() - n)个；未超过n次的字母没有要求
• 因此问题转化为找到满足出现给定次数字母的最短子串长度，用滑窗即可

书柜放书

• 我的思路是类似于*********239滑动窗口最大值，用两个窗口，其分别显示当前窗口内的最大和最小值，如果满足题目高度差要求，则这个窗口是一个符合题目的放置方法
• 按窗口大小降序进行尝试，如果存在至少一种放置方法，则直接输出答案
• 滑动窗口最大值的O(n)方法忘记怎么写了，用的优先队列；最后提交超时了只过了70%
• 感觉滑窗用O(n)处理也还是可能超，有无懂哥讲一下好的思路