代碼隨想錄算法訓練營|第六十一天|503.下一个更大元素II、42. 接雨水。刷题心得(c++)

本文主要是介绍代碼隨想錄算法訓練營|第六十一天|503.下一个更大元素II、42. 接雨水。刷题心得(c++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

讀題

503.下一个更大元素II

看完代码随想录之后的想法

42. 接雨水

看完代码随想录之后的想法

503.下一个更大元素II - 實作

思路

Code

42. 接雨水 - 實作

思路

原思路錯誤點

雙指針縱向運算思路

單調棧橫向運算思路

Code

原思路 - 錯誤 (縱向運算)

雙指針縱向運算思路

單調棧橫向運算思路

總結

自己实现过程中遇到哪些困难

今日收获,记录一下自己的学习时长

相關資料

503.下一个更大元素II

42. 接雨水


讀題

503.下一个更大元素II

看完代码随想录之后的想法

一開始看到環形數列的時候有點矇,但是在聽完卡哥的講解後,終於理解了,原來可以使用取mod的做法來模擬環形數列,在影片講解當中,最後有提到一個問題,假設在一個遞減的數列當中,比如說是[4, 3, 2] 那環形則會變成 [4,3,2,4,3,2]對應到的result則會是[-1, 4, ,4, -1, -1] 有提到後面的值會不會覆蓋到前面,我想說的是不會,因為只有當遇到了比較大的值才會觸發更新,那3, 2唯一會碰到也只會是在第二個4才會觸發更新,假設改為[1,4,3,2,1,4,3,2] 也一樣,最終1還是會更新到他的右邊第一個最大的數值。

42. 接雨水

看完代码随想录之后的想法

我原本的思路是縱向運算,但是使用到錯誤的方法,應該是要找左邊最大的以及右邊最大的,我的作法少了這點,看完隨想錄的講解後,才豁然開朗,使用橫向運算比較直覺一點,在理解上也比較清晰,如果遇到右邊比較大的元素,那就是右節點減去當前棧頂的下一個元素,再減去1就會是中間的的寬度,高度則是棧頂的左右元素取最小的減去棧頂對應的数組,兩者相乘,加到result當中就好了,用這個思路去理解就清晰很多了。

503.下一个更大元素II - 實作

思路

  1. 單調棧存放的是數組下標
  2. 單調棧性質為遞增
  3. 將遍歷大小擴為兩倍數組大小,並將i進行取mod運算。

Code

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {stack<int> st;vector<int> results(nums.size(), -1);for(int i = 0; i < (nums.size() * 2) ; i++) {while(!st.empty() && nums[st.top()] < nums[i % nums.size()]) {results[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}return results;}
};

 

42. 接雨水 - 實作

思路

原思路錯誤點

原思路如果改變作法就會對了,因為是做縱向的運算,所以要找到左邊最大以及右邊最大的柱子,如果使用單調棧,則只會找到左邊以及右邊第一個比當前大的元素,而不是最大的,因此會少計算了一些面積。

雙指針縱向運算思路

  1. 使用兩個數組紀錄左邊最高以及右邊最高
  2. maxLeft 由左向右遍歷 maxLeft當前高度 max(當前高度,maxLeft前一個高度)
  3. maxRight 由右向左遍歷 maxRight當前高度 max(當前高度,maxRight前一個高度)
  4. 求和,遍歷数組,左右最高取最小,並減去當前高度
  5. 假設大於0,則加入到結果當中

單調棧橫向運算思路

  1. 單調棧存放元素為數組下標
  2. 單調棧性質為遞增
  3. 當前元素對應的数組值與棧頂元素對應的数組值比較與處理
    1. 小於
      1. 將當前元素放入棧頂
    2. 等於
      1. pop棧頂元素
      2. 將當前元素放入棧頂
      3. 因為相等的話,如果比較最小值時,當前元素與棧頂元素相減 = 0 無論如何相乘都只會是0
    3. 大於
      1. 儲存棧頂元素
      2. pop棧頂
      3. 高度是
        1. 當前元素與目前棧頂元素對應的数組數值取最小減去之前儲存棧頂元素對應的数組數值
      4. 寬度是
        1. 當前元素減去目前棧頂元素再減去1
      5. sum += h * w
      6. 儲存當前元素到單調棧中
  4. return sum.

Code

原思路 - 錯誤 (縱向運算)

class Solution {
public:int trap(vector<int>& height) {stack<int> st;vector<int> water(height.size(), 0);vector<int> leftH(height.size(), 0);int water = 0;for(int i = 0; i < height.size() ; i++) {while(!st.empty() && height[st.top()] < height[i]) {rightH[st.top()] = height[i];st.pop();}st.push(i);}while (!st.empty()) st.pop();for(int i = height.size() - 1; i >= 0; i--) {while(!st.empty() && height[st.top()] < height[i]) {leftH[st.top()] = height[i];st.pop();}st.push(i);}for(int i = 0; i < height.size(); i++) {if(min(rightH[i], leftH[i]) - height[i] >= 0)water += min(rightH[i], leftH[i]) - height[i];}return water;}
};

雙指針縱向運算思路

class Solution {
public:int trap(vector<int>& height) {vector<int> maxLeft(height.size(), 0);vector<int> maxRight(height.size(), 0);int size = height.size();maxLeft[0] = height[0];for (int i = 1; i < size; i++) {maxLeft[i] = max(height[i], maxLeft[i - 1]);}maxRight[size - 1] = height[size - 1];for (int i = size - 2; i >= 0; i--) {maxRight[i] = max(height[i], maxRight[i + 1]);}int sum = 0;for (int i = 0; i < size; i++) {int count = min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}
};

單調棧橫向運算思路

class Solution {
public:int trap(vector<int>& height) {stack<int> st;st.push(0);int sum = 0;for(int i = 1; i < height.size() ; i++) {if(height[st.top()] > height[i]){st.push(i);}else if(height[st.top()] == height[i]){st.pop();st.push(i);} else {while(!st.empty() && height[st.top()] < height[i]) {int mid = st.top();st.pop();if(!st.empty()) {int h = min(height[i], height[st.top()]) - height[mid];int w = i - st.top() - 1;sum += h * w;}}st.push(i);}}return sum;}
};

 

總結

自己实现过程中遇到哪些困难

困難點主要是接雨水沒有想到可以這樣利用單調棧的性質,以及自己一開始在做接雨水題目時思路想成縱向運算,看完影片後才比較知道自己為甚麼做錯了。

今日收获,记录一下自己的学习时长

今天大概學習2hr,主要是了解了如何處理環形數列以及單調棧如何在接雨水這個題目中運用

相關資料

● 今日学习的文章链接和视频链接

503.下一个更大元素II

https://programmercarl.com/0503.下一个更大元素II.html

42. 接雨水

https://programmercarl.com/0042.接雨水.html

这篇关于代碼隨想錄算法訓練營|第六十一天|503.下一个更大元素II、42. 接雨水。刷题心得(c++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/356107

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名