字节 5.6 后端笔试思路
T1
思路:
简单模拟, 类似区间合并
T2
由于数据量较小, 选择直接排序, 比较相邻字符串是否前一个字符串是后一个的前缀, 优化可以选择字典树
T3
贪心, 先选择前两个, 如果时间不够直接返回 0. 从第三个开始, 判断其价值与选择的两物品的价值, 若价值更大且有足够时间替换, 优先选择价值小的进行替换, 最后价值就是答案
T4
预处理,fp[i]: 以 i 结尾最长连续递增子数组长度, fs[i]: 以 i 开头最长连续递增子数组长度
答案等于 max(fp[i] + fs[j]) ( 1<= i < j <= n)
枚举每一个 j, 使用树状数组优化查找 i (维护子数组(1 -> j-1)中最长的连续递增子数组的值), 由于数值太大, 需要对数值进行离散化处理