互诺 网站好吗,重庆梁平网站建设公司,wordpress 网站暂停,微信平台APP网站建设怎么样题目引用 逆波兰表达式求值滑动窗口最大值前k个高频元素
1.逆波兰表达式求值 给你一个字符串数组 tokens #xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意#xff1a;
有效的算符为 ‘’、‘-’、‘*’ 和…题目引用 逆波兰表达式求值滑动窗口最大值前k个高频元素
1.逆波兰表达式求值 给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意
有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。 每个操作数运算对象都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1 输入tokens [“2”,“1”,“”,“3”,“*”] 输出9 解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9 示例 2 输入tokens [“4”,“13”,“5”,“/”,“”] 输出6 解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6 示例 3 输入tokens [“10”,“6”,“9”,“3”,“”,“-11”,““,”/“,””,“17”,“”,“5”,“”] 输出22 解释该算式转化为常见的中缀算术表达式为 ((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22 这道题目就很简单我们只需要定义一个栈st然后遍历一遍数组不是符号的话就入栈遇到符号的话就从栈中取出两个元素进行加减乘除运算再压入栈中。最后返回栈中元素。
来看代码
int evalRPN(vectorstring tokens) {stacklong long st; for (int i 0; i tokens.size(); i) {if (tokens[i] || tokens[i] - || tokens[i] * || tokens[i] /) {long long num1 st.top();st.pop();long long num2 st.top();st.pop();if (tokens[i] ) st.push(num2 num1);if (tokens[i] -) st.push(num2 - num1);if (tokens[i] *) st.push(num2 * num1);if (tokens[i] /) st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result st.top();st.pop(); // 把栈里最后一个元素弹出其实不弹出也没事return result;}这里需要注意栈中元素进行运算时可能会溢出所以使用long long来定义中间值。
2.滑动窗口最大值 给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1 输入nums [1,3,-1,-3,5,3,6,7], k 3 输出[3,3,5,5,6,7] 解释 滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 | 3 1 [3 -1 -3] 5 3 6 7 | 3 1 3 [-1 -3 5] 3 6 7 | 5 1 3 -1 [-3 5 3] 6 7 | 5 1 3 -1 -3 [5 3 6] 7 | 6 1 3 -1 -3 5 [3 6 7] | 7 示例 2 输入nums [1], k 1 输出[1] 这道题比较难实现如果是第一次刷题的话遇到这种题目就可以直接跳过了。 我们来看题目题目要求我们找到每次滑动窗口滑动时的最大值那么我们就可以想一下可不可以创建一个自动找到最大值或者说第二大的数据结构呢可能很多人会想到优先级队列。优先级队列是一种思路可是我们再仔细想想我们一开始就要入一些元素进来而只有优先级队列的top()是我们需要的其他的我们都可以丢弃那这就造成了空间的浪费而且随着滑动窗口向后移动遇到比原来top()小比其他值大的数时就可能产生混乱无法判断这个值什么时候该弹出或者早该弹出却因为其他值比它大而没有弹出导致后续的结果出现问题。 所以我们需要一种方便我们进行弹入弹出又能便于维护的数据结构是什么呢没有~ 但是我们可以造一个而底层我们就用deque这种便于头插头删尾插尾删的数据结构。当我们滑动窗口向前滑动时我们要把即将进入的值与已经在队列中的值一一比对只要比即将要插入的值小那么就直接pop_back()直到找到比自己大的数或者队列清空。同时队列头部与将要滑出窗口的值进行比较如果等于就大胆pop_front()然后再将尾插头删后的队列的front()插入结果数组中,如此循环就得到了每一轮的最大值。 这样说大概大家还是云里雾里那么来看代码吧 class Myqueue{private:dequeint que;public:void push(int x){while(!que.empty()xque.back()) que.pop_back();que.push_back(x);}void pop(int x){if(!que.empty()xque.front()) que.pop_front();}int front(){return que.front();}};vectorint maxSlidingWindow(vectorint nums, int k) {Myqueue que;vectorint result;for (int i 0; i k; i) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i k; i nums.size(); i) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}3.前k个高频元素 给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2: 输入: nums [1], k 1 输出: [1] 这题相较于上一题来说就稍微简单一点了我们直接说思路吧他要找前k频率的元素那么我们就要先使用unordered_map将每个元素出现的频率统计一下然后再用小根堆来记录为什么是小根堆因为是前k高频率使用小根堆的话当堆中元素大于k个时就可以直接将出现频率最小的弹出堆中便于维护更新。 最后将堆中元素倒序输出即可
struct compare{bool operator()(const pairint,int lhs,const pairint,int rhs){return lhs.secondrhs.second;}};vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int map;for(int i0;inums.size();i){map[nums[i]];}priority_queuepairint,int,vectorpairint,int,compare que;for(unordered_mapint,int::iterator itmap.begin();it!map.end();it){que.push(*it);if(que.size()k){que.pop();}}vectorint res(k);for(int ik-1;i0;i--){res[i]que.top().first;que.pop(); }return res;}总结
今天的题目普遍比较难大家下去一定要自己敲一下感受感受。
