免费ftp 网站wordpress怎么更改首页海报轮播图

当前位置： 首页 > news >正文

免费ftp 网站,wordpress怎么更改首页海报轮播图,flash网站引导页面制作,工业设计网站官网leetcode 经典题分类 链表数组字符串哈希表二分法双指针滑动窗口递归/回溯动态规划二叉树辅助栈 本系列专栏#xff1a;点击进入 leetcode题目分类 关注走一波 前言#xff1a;本系列文章初衷是为了按类别整理出力扣#xff08;leetcode#xff09;最经典题目#xff0c…leetcode 经典题分类 链表数组字符串哈希表二分法双指针滑动窗口递归/回溯动态规划二叉树辅助栈 本系列专栏点击进入 leetcode题目分类 关注走一波 前言本系列文章初衷是为了按类别整理出力扣leetcode最经典题目一共100多道题每道题都给出了非常详细的解题思路、算法步骤、代码实现。很多同学刚开始刷题都是按照力扣顺序刷题其实这样对新手不太适用刷题效果也很不好。因为力扣题目顺序是随机的并没有按照算法分类导致同一类型的算法强化训练不够最后刷完也是迷迷糊糊的。所以本系列文章就是来帮你完成算法分类针对每种算法做强化训练保证让你以后遇到题目直接秒杀 文章目录 leetcode 经典题分类有效的括号最长有效括号接雨水柱状图中最大的矩形 有效的括号 【题目描述】 给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串s判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合 左括号必须以正确的顺序闭合 每个右括号都有一个对应的相同类型的左括号。
【输入输出实例】 示例 1 输入s “()” 输出true 示例 2 输入s “()[]{}” 输出true 示例 3 输入s “(]” 输出false 【算法思路】 先来分析一下这里有三种不匹配的情况 字符串里左方向的括号多余了所以不匹配 括号没有多余但是括号的类型没有匹配上 字符串里右方向的括号多余了所以不匹配
针对三种不匹配情况的代码 第一种情况已经遍历完了字符串但是栈不为空说明有相应的左括号没有右括号来匹配所以return false 第二种情况遍历字符串匹配的过程中发现栈里没有要匹配的字符所以return false 第三种情况遍历字符串匹配的过程中栈已为空没有匹配的括号说明右括号没有找到对应的左括号所以return false。
匹配成功的情况 ​ 字符串遍历完之后栈是空的就说明全都匹配了。 技巧 在遇到左括号时不要让左括号本身入栈而让相应的右括号入栈。则在遇到右括号匹配时就只需要比较当前右括号和栈顶元素相不相等就可以了比左括号入栈代码实现更简单。 【算法描述】 //括号匹配是使用辅助栈解决 bool isValid(string s) {stackchar sta; //辅助栈for(char ch : s) //遍历给定的括号字符串{switch(ch){//技巧遇到左括号就入栈其对应的右括号case (:sta.push());break;case [:sta.push(]);break;case {:sta.push(});break;default: //遇到右括号就检查是否匹配检查本身与栈顶元素是否一样if(sta.empty() || sta.top() ! ch) //栈为空 或 本身与栈顶元素不一样都说明括号不匹配{return false;}sta.pop(); //若一样则出栈}}return sta.empty(); //最后若有未出栈的元素说明有不匹配的项 }最长有效括号 【题目描述】 给你一个只包含 ‘(’ 和 ‘)’ 的字符串找出最长有效(格式正确且连续)括号子串的长度。 【输入输出实例】 示例 1 输入s “(()” 输出2 示例 2 输入s “)()())” 输出4 示例 3 输入s “()(()” 输出2 示例 4 输入s “” 输出0 【算法思路】 创建一个大小为len的容器来表示各个括号的是否可匹配。用栈模拟一遍括号匹配将所有无法匹配的括号的位置全部置1。例如()(()“对应为[0, 0, 1, 0, 0]再例如”)()((())的对应为[1, 0, 0, 1, 0, 0, 0, 0]。 经过这样的处理后此题就变成了寻找最长的连续0的长度 【算法描述】 int longestValidParentheses(string s) {int len s.size();vectorint v(len); //用来表示该位置的括号是否可匹配无法匹配的括号的位置全部置1stackint stk; //栈内存放括号下标int maxLong 0; //记录括号匹配的最大长度for(int i 0; i len; i){if(si //遇到左括号就入栈{stk.push(i);}else //遇到右括号就判断{if(stk.empty()) //多余的右括号是不需要的标记1{v[i] 1;}else //匹配成功{stk.pop();}}}while(!stk.empty()) //未匹配的左括号是不需要的标记1{v[stk.top()] 1;stk.pop();}// 寻找标记与标记之间的最大长度即找最长的连续的0的长度int num 0;for(int i 0; i len; i){if(v[i] 0){num;}else{maxLong max(maxLong, num);num 0;}}maxLong max(maxLong, num); return maxLong; }接雨水 【题目描述】 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 【输入输出实例】 示例 1 输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6 示例 2 输入height [4,2,0,3,2,5] 输出9 【算法思路】 首先要知道单调栈是按照行方向来计算雨水如图 单调栈内元素的顺序从栈头到栈底的顺序应该是从小到大的顺序。因为一旦发现要添加的柱子高度大于栈顶元素此时就出现凹槽了栈头元素就是凹槽底部的柱子栈头第二个元素就是凹槽左边的柱子而添加的元素就是凹槽右边的柱子。如图 因为长就是通过柱子的高度来计算宽是通过柱子之间的下标来计算通过长*宽来计算雨水面积所以栈中应该存放下标计算的时候用下标对应的柱子高度即可。 算法过程就是用单调栈不断入栈每个柱子对应的下标当要入栈的柱子高度大于栈顶元素时要先将元素出栈保留即为凹槽的底部bottom。此时的栈顶元素为凹槽左边的柱子left要入栈的柱子为凹槽右边的柱子right。则可算出这个凹槽中盛放水的高度 rainHeight min(height[left], height[right]) - height[temp]; 宽度为rainWidth right - left - 1; 则可算出该凹槽中盛放水的体积根据上述操作遍历(不断入栈出栈)完每根柱子将得到的雨水量相加起来即可。 【算法描述】 //双指针法(超时) int trap(vectorint height) {int len height.size(); int sum 0; //记录接的雨水for(int i 1; i len - 1; i) //遍历每列(除第一列和最后一列因为它们不会接雨水){int maxLeft 0; //左边最高柱子的高度int maxRight 0; //右边最高柱子的高度for(int left i - 1; left 0; left–) //找左边最高柱子{maxLeft max(maxLeft, height[left]);}for(int right i 1; right len; right) //找右边最高柱子{maxRight max(maxRight, height[right]);if(maxRight maxLeft) //因为最后要取两者最小所以只要超过左边最高柱子直接退出{break;}}int rainHeight min(maxLeft, maxRight) - height[i]; //计算雨水高度sum (rainHeight 0) ? rainHeight : 0;}return sum; }//动态规划——相当于双指针法只是用动态规划来提前求出每个柱子的最大左边柱子和最大右边柱子 int trap(vectorint height) {int len height.size(); int sum 0; //记录接的雨水vectorint maxLeft(len); //记录第i列左边柱子最大高度vectorint maxRight(len); //记录第i列右边柱子最大高度maxLeft[0] height[0]; //初始化maxRight[len-1] height[len-1];//记录每个柱子左边柱子最大高度for(int i 1; i len-1; i){maxLeft[i] max(maxLeft[i-1], height[i]);}//记录每个柱子右边柱子最大高度for(int i len-2; i 0; i–){maxRight[i] max(maxRight[i1], height[i]);}//遍历每列算雨水量再求和for(int i 1; i len - 1; i){int rainHeight min(maxLeft[i-1], maxRight[i1]) - height[i];sum (rainHeight 0) ? rainHeight : 0;}return sum; }//单调栈 int trap(vectorint height) {int sum 0; //记录接的雨水stackint s; //单调栈s.push(0);for(int i 1; i height.size(); i){//如果栈不空并且当前指向的高度大于栈顶高度就一直循环while(!s.empty() height[i] height[s.top()]){int temp height[s.top()]; //取出要出栈的元素s.pop(); //出栈if(!s.empty()) //出栈一个后如果栈不为空就开始算雨水{int rainHeight min(height[i], height[s.top()]) - temp; //计算雨水高度-temp相当于是减去i和s.top()两列构成容器的底部柱子的高度int rainWidth i - s.top() - 1; //雨水宽度sum rainHeight * rainWidth; //雨水量}}s.push(i); //每根柱子要入栈}return sum; }柱状图中最大的矩形 【题目描述】 给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为1。 求在该柱状图中能够勾勒出来的矩形的最大面积。 【输入输出实例】 示例 1: 输入heights [2,1,5,6,2,3] 输出10 示例 2 输入heights [2,4] 输出4 【算法思路】 本题目与42、接雨水非常相似也是有三种方法如下 (1)双指针法和动态规划 接雨水是找每列中左侧最高的柱子和右侧最高的柱子。找到后该列的雨水高度可得到宽度为1就可得到该列的雨水量再把每列的雨水累加起来即可 本题是找每个柱子左右两侧最后一个大于等于该柱子高度的柱子。找到后勾勒出来的矩形的宽度为左右两侧这两列的下标差高度就是本列柱子的高度则可计算出本列勾勒出来最大矩形的面积再把每列勾勒出来的矩形面积求出来再找最大。 (2)单调栈 接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子而本题是找每个柱子左右两边第一个小于该柱子的柱子。所以从栈头到栈底的顺序应该是从大到小的顺序。 如上图可知只有栈里从大到小的顺序才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。 其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度。其中栈顶元素为矩形高度栈顶的下一个元素以及要入栈的元素的下标构成了矩阵的宽度。 其实可以把这个过程想象成锯木板如果木板都是递增的那我很开心不用管。如果突然遇到一块木板 i 矮了一截那我就先找之前最戳出来的一块其实就是第 i-1 块计算一下这个木板单独的面积然后把它锯成次高的这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发现次高的仍然比现在这个 i 木板高那我继续单独计算这个次高木板的面积应该是第 i-1 和 i-2 块组成的木板再把它俩锯短。直到发现不需要锯就比第 i 块矮了那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的所以可以在最后加一块高度为0的木板。 这个算法的关键点是把那些戳出来的木板早点单独拎出来计算然后就用不着这个值了。 【算法描述】 //双指针法——超时 int largestRectangleArea(vectorint heights) {int n heights.size();int maxArea 0; //记录矩形的最大面积for(int i 0; i n; i) //遍历每根柱子{int left i - 1;int right i 1;//找左边最后一个大于等于heights[i]的下标for(; left 0; left–){if(heights[left] heights[i]){break;}}//找右边最后一个大于等于heights[i]的下标for(; right n; right){if(heights[right] heights[i]){break;}}int height heights[i]; //矩形高度int width right - left - 1; //矩形宽度maxArea max(maxArea, height*width); //计算最大面积}return maxArea; }//动态规划 int largestRectangleArea(vectorint heights) {int n heights.size();int maxArea 0; //记录矩形的最大面积vectorint left(n);vectorint right(n);left[0] -1; //初始化right[n-1] n;//记录每个柱子左边第一个高度小于该柱子的下标for(int i 1; i n; i){int index i - 1;while(index 0 heights[i] heights[index]){index left[index]; //动态规划更新上一次已经求过不用重复求}left[i] index;}//记录每个柱子右边第一个高度小于该柱子的下标for(int i n - 2; i 0; i–){int index i 1;while(index n heights[i] heights[index]){index right[index]; //动态规划更新上一次已经求过不用重复求}right[i] index;}//计算矩形的最大面积for(int i 0; i n; i){int height heights[i]; //矩形高度int width right[i] - left[i] - 1; //矩形宽度maxArea max(maxArea, height*width); //计算最大面积}return maxArea; }//单调栈 int largestRectangleArea(vectorint heights) {heights.insert(heights.begin(), 0); //数组头部加入元素0heights.push_back(0); //数组尾部加入元素0int maxArea 0; //记录矩形的最大面积stackint s; //单调栈(递减)s.push(0);for(int i 1; i heights.size(); i) //遍历各柱子{while(heights[i] heights[s.top()]){int height heights[s.top()]; //矩形高度//int width i - s.top(); //这时得到的矩形宽度没有把之前出栈的柱子宽度算上因为之前出栈的柱子高度肯定大于它后面的柱子高度所以才被出栈那么要把前面已出栈的柱子宽度也要算上s.pop();int width i - s.top() - 1; //矩形宽度把前面已出栈的宽度也要算上 maxArea max(maxArea, height*width); //计算最大面积}s.push(i);}return maxArea; }恭喜你全部读完啦古人云温故而知新。赶紧收藏关注起来用之前再翻一翻吧~ 推荐阅读 C/C后端开发面试总结点击进入 后端开发面经 关注走一波 C重点知识点击进入 C重点知识 关注走一波 力扣leetcode题目分类点击进入 leetcode题目分类 关注走一波