字节笔试 字节跳动软件算法笔试5-12

公号：嵌入式未来

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《嵌入式软件笔试-2023年真题汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

题目1：竞技场

曾经的我不过是一个草民，混迹市井，默默无名。直到我被罗马的士兵从家乡捉走丢进竞技场....

对手出现了，我架紧盾牌想要防御，只觉得巨大的冲击力有如一面城墙冲涌而来，击碎了我的盾牌，我两眼发管，沉重的身躯轰然倒地。

—我好想逃

但罗马最大的竞技场，哪有这么容易逃得掉。工程师们早就在地上装了传送机关，虽不会伤人，却会将站在上面的人传到它指向的位置。若是几个传送机关围成一个环，不小心踩在上面的人就会被一圈圈的反复传送...想到这里，我不由得打了个寒颤。必须避开这些危险的地方!

输入描述

第一行输入两个整数 n 和 m，表示迷宫的长和宽。

接下来 n 行，每行 m 个字符，用于描述迷宫构造，每个字符可能为以下几种.(小数点) 表示空地，玩家在空地时可以选择往[上,下,左,右] 中的某个方向移动一格

U,D,L,R 分别表示朝向[上,下,左,右]的传送带，站在传送带上的人会被强制移动到其指向的下一个位置

如果下一个位置还是传送带，会被继续传下去

如果传送带指向迷宫外，玩家会撞在墙上昏过去，游戏结束，无法再到达出口

O表示迷宫出口

输出描述

输出一个数字，表示迷宫中有多少个位置，当玩家位于此处时，无论接下来如何移动都无法再到达出口(传送带、空地、出口都算一个位置)

示例1

输入

5 5

.....

..PRD

.U.DR

.ULL.

....O

输出

10

备注

1<=n,m <= 10^5

1<=n*m<=10^5

保证每个迷宫中有且仅有一个出口

题目2：数组和的最大值

给定整数数组，我们称其中连续的0个或多个整数为一个子数组，求删除任一元素后，新数组中长度为k的子数组的和的最大值

输入描述

第一行输入为N和K，N代表数组长度，K代表子数组长度

第二行输入为N个整数，依次为数组的每个元素

输出描述

一个整数S，代表所有可能新数组中长度为K的子数组的和的最大值

示例1

输入

5 3

2 1 3 -1 4

输出

8

说明

选择删除第四个元素，新数组为2 1 3 4，其长度为3的子数组的和是8

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main() {
    int N, k;
    cin >> N >> k;

    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }

    int res = 0;
    deque<int> q;
    int curSum = 0;

    for (int i = 0; i < N; i++) {
        curSum += nums[i];

        if (!q.empty() && i - k > q.front()) {
            q.pop_front();
        }

        if (i >= k + 1) {
            curSum -= nums[i - k - 1];
        }

        while (!q.empty() && nums[q.back()] > nums[i]) {
            q.pop_back();
        }

        q.push_back(i);

        if (i >= k) {
            res = max(res, curSum - nums[q.front()]);
        }
    }