RTTO WEEK4

Posted on Edited on In

WEEK 4

27.移除元素（e）

slow用于赋值符合条件的fast位置数据，fast碰到不与val相等的则赋值，碰到与val相等的则++

344.反转字符串（e）

上周做过了

236.滑动窗口最大值（h）

需要重写单调队列（由于是求max，入队元素必须遵从单调递减）

三个功能 由STL中deque双端队列容器构造

front() 查询当前单调队列中最大值，由于构造的是单调递减，所以最大值为队首元素 直接front

pop() 查询当前单调队列中需要弹出的值是否是队首的值，若是则pop_front

push() 将不满足单调递减要求的数 pop_back出；若满足单调递减要求，循环push_back直至不满足要求————即要保持单调队列中元素始终单调

使用单调队列时

首先将前k个元素放进队列，res中记录前k个最大值；

后遍历k个后的元素，单调队列pop出首部元素，push入新元素，后进行front计算最大值push_back入res vector直至循环结束；

347.前k个高频元素（m）

涉及到STL库优先队列

1
priority_queue<Type, Container, Functional>

Type 是数据类型，Container 是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 是比较的方式。

当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

1
2
3
4
5
6
//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

71.简化路径（m）

使用栈

image-20230222104900412