代码随想录算法训练营第十天|150.逆波兰表达式求值，239.滑动窗口最大值，347.前K个高频元素

150.逆波兰表达式求值看到题目的第一想法后序遍历嘛这很快就让我想到上一题也是找到特定的元素然后对栈进弹出只不过这次是弹出两个组装一下再加进去看完代码随想录的第一想法跟我想的也差不多确实是跟上一题差不多就是后序遍历这个概念需要去了解用自己的话描述遍历每一个字符遇到加减乘除就取数开始运算再返回结果入栈不断重复最后一个数就是结果代码classSolution{publicintevalRPN(String[]tokens){DequeIntegerstacknewLinkedList();for(Stringi:tokens){if(.equals(i)){stack.push(stack.pop()stack.pop());}elseif(-.equals(i)){intbstack.pop();intastack.pop();stack.push(a-b);}elseif(/.equals(i)){inttemp1stack.pop();inttemp2stack.pop();stack.push(temp2/temp1);}elseif(*.equals(i)){stack.push(stack.pop()*stack.pop());}else{stack.push(Integer.valueOf(i));}}returnstack.pop();}}实现过程中遇到哪些困难无今日收获记录一下自己的学习时长继续熟悉Deque stack new LinkedList();类型转换Integer.valueOf(x);12.00-12.23239.滑动窗口最大值看到题目的第一想法滑动窗口我看到就想着双指针但是一点思路都没有看完代码随想录的第一想法原来要构造队列这个内容我想不明白用自己的话描述就是先构造一个队列然后用这个特殊队列进行向右的移动即可所谓的向右移动就是遍历这个数组代码classSolution{publicint[]maxSlidingWindow(int[]nums,intk){MyQueuemyQueuenewMyQueue();for(inti0;ik;i){myQueue.add(nums[i]);}intlennums.length-k1;int[]resnewint[len];intnum0;res[num]myQueue.peek();num;for(intik;inums.length;i){myQueue.poll(nums[i-k]);myQueue.add(nums[i]);res[num]myQueue.peek();}returnres;}}classMyQueue{DequeIntegerdequenewLinkedList();//移除队尾所有小于等于当前值的元素保持单调递减voidadd(intval){while(!deque.isEmpty()valdeque.getLast()){deque.removeLast();}deque.add(val);}//弹出元素时比较当前弹出的元素是否是队首元素voidpoll(intval){if(!deque.isEmpty()deque.peek()val){deque.poll();}}intpeek(){returndeque.peek();}}实现过程中遇到哪些困难自定义队列这个做法也是前所未有于是总体觉得很难今日收获记录一下自己的学习时长学习了自定义队列的做法12.40-14.17347.前K个高频元素看到题目的第一想法找出现多的数我的想法就是将数组的数字转换成Map中的key每出现一次这个数其value就加1这样就是能解决了想不到其他方法了看完代码随想录的第一想法按我的想法随便进行排序就好了但是这个题目中代码随想录使用了堆这个数据结构可以做到不需要排序维护前k个元素即可这种想法是在这个数据结构出现之前前所未有的用自己的话描述找出现多的数我的想法就是将数组的数字转换成Map中的key每出现一次这个数其value就加1然后将这些Map先放入大小为k的小顶堆中之后的Map.value只有比堆顶大才能进入堆中最小的堆顶弹出不断这样做直到获得前k个最大的元素然后每次都取堆顶出来等于每次都取这个堆的最小值倒序遍历出来获得一个从大到小的数组代码classSolution{publicint[]topKFrequent(int[]nums,intk){// 统计频率MapInteger,IntegermapnewHashMap();for(intnum:nums){map.put(num,map.getOrDefault(num,0)1);}// 小顶堆维护前k个高频元素PriorityQueueint[]pqnewPriorityQueue((pair1,pair2)-pair1[1]-pair2[1]);for(Map.EntryInteger,Integerentry:map.entrySet()){if(pq.size()k){pq.add(newint[]{entry.getKey(),entry.getValue()});}else{if(entry.getValue()pq.peek()[1]){pq.poll();pq.add(newint[]{entry.getKey(),entry.getValue()});}}}// 取出结果int[]resnewint[k];for(intik-1;i0;i--){res[i]pq.poll()[0];}returnres;}}实现过程中遇到哪些困难说实话好久没接触堆了忘记堆的特性和其用法其Java的语法更是没有接触过今天学起来还真有点棘手今日收获记录一下自己的学习时长重温了一下堆的特性和其用法14.30-16.35