4月12日字节跳动笔试

笔试成绩还行,四道题磕磕绊绊全都做出来了。

HINT : 以下样例部分为自己原创,非题目所给样例。

A题

给你两个长度相等的数组$a$,$b$,问是否能够在数组$a$中找到一个区间$[ l , r ]$,将区间内的所有数字均加上$k>=0$,可以将数组$a$变为数组$b$?

样例输入
5
1 1 1 1 1
1 2 2 2 1

样例输出
YES

样例输入
5
1 1 1 1 1
1 2 1 2 1

样例输出
NO

暴力即可,从前往后找到第一个$b[ i ] - a[ i ] ! =0$的位置$L$,同理从后往前找位置$R$,那么只需要判断区间$[L,R]$内$b[i]-a[i]$是否完全相等且不小于0即可。复杂度$O(n)$。

B题

给你$n(1\leq n\leq 3000)$根长为$a[i](1\leq a[i] \leq 3000)$小木棍排成一列,现在你可以进行如下操作:
将某根小木棍折成两份,每份长度均为整数,然后将其放回原位置,此时一共有$n+1$根小木棍。
问在最少经过多少次重复操作后,可以使得所有的小木棍长度非递减排列。

样例输入
3
4 9 4

样例输出
3

样例解释
4 9 4 -> 2 2 3 3 3 4

$dp[i][j]$表示将棍子$i$切割成$j$份的信息簇(结构体),里面存储切成$j$份后所有棍子的最大值和最小值,要保证最大值尽可能小,最小值尽可能大。同时初始化一个切割次数$cost=j$。然后$n^2$循环,对于第$i$根棍,我们要在第$i-1$根棍的所有方案中找到满足$dp[i-1][j].maxx<=dp[i][k].minn$的所有$cost$,然后去最小值加到$dp[i][j].cost$中。这个可以用两个指针来求,因为可以知道对于第$i$根棍,$j$递增,则$maxx,minn$递减。 复杂度$O(n^2)$。

C题

给你$n$张优惠券,每张优惠券均有一个金额,可以无条件无限次使用。现有$m$件商品,每件商品可使用一次优惠券,并且使用的优惠券的金额必须不超过商品金额,问最少需要多少钱才能够买下所有商品。

样例输入
3 4
50 100 200
99 199 200 300

样例输出
248

样例解释
(99-50)+(199-100)+(200-200)+(300-200)=248

结构体存下所有商品,按照优惠券和商品进行标记,然后按照金额大小进行排序。

接下来$for$循环,如果当前物品是优惠券,那么就更新当前可用优惠券的最大值(初始为0),否则当前物品为商品,那么买下它所需要的花费即为其价格减去可用优惠券最大值。复杂度$O(nlogn)$

D题

现有$n(1\leq n \leq 10^5)$个房子排成一排,每个房子有个高度$a[i](1\leq a[i]\leq 10^8)$从每个房子上向左向右看,可以看到高度不超过自己的房子,如果遇到高度超过自己的房子,那么该房子后面的房子也将被阻挡住无法看见。问从每个房子向左向右看,能看到的房子的最大数量为多少。

样例输入
4
1 4 3 3

样例输出
0 3 2 2

单调栈裸题,从前向后扫一遍,从后向前扫一遍,然后输出结果即可。复杂度$O(n)$。

感谢您的支持
-------------本文结束感谢您的阅读-------------