转的 同学阿里笔试

一共三道题 同学分享的 我没有做只提供思路正确性不保证

说下每道题的大致思路。

第一题优先队列迭代n次即可，每次更新小顶堆+t 和最大值比较 nlogn

第二题归并排序 找逆序对 拿逆序对左值下标的最小值 和右值的最大值 最后答案就是 (l+1)(n-r+1) 如果没有逆序对答案就是(n+1)n/2 整体复杂度也是排序的 nlogn

第三题 二分 从1 到 n/m 二分 寻找满足条件区间的最左值即可。每次check顺序遍历字符串遇到r直接把它和后面的k个全变红次数大于m则返回false 整体复杂度nlogn

今年的工作是真的难找