予辰 level
获赞
76
粉丝
6
关注
3
看过 TA
24
男
门头沟学院
2022
算法工程师
IP属地：未知
暂未填写个人简介
私信
关注
发布(18) 评论 刷题 收藏
2021-09-25 19:09
门头沟学院 算法工程师
0 点赞 评论 收藏
分享
2021-03-24 11:55
已编辑
门头沟学院 算法工程师
0 点赞 评论 收藏
分享
2020-11-16 21:49
已编辑
门头沟学院 算法工程师
单调栈问题集中详解
一、单调栈的定义及特点所谓的单调栈，就是在栈先进后出的特性之外再添加一个单调的特性，使得栈中元素是递增或者递减的。其具有以下几个小特点：1、栈内元素保持单调；2、每个元素都会入栈并且仅仅入栈一次；3、栈当中可以直接存储元素本身，也可以存放元素的下标索引(存放索引时是指索引对应的元素是单调的)；4、对栈的维护工作(以单调递减栈为例，递增栈类似):设当前遍历到的元素是e，如果e大于或者等于栈顶元素，那么就一直弹栈，直到栈顶元素大于e或者栈为空时，再将e入栈；如果小于的话就直接将e入栈即可。举个简单的小例子，数组如下{3,9,5,2,7,4,6},现在我们维护一个升序栈结构，我们使用0(3)来表示栈...
0 点赞 评论 收藏
分享
2020-10-30 22:54
门头沟学院 算法工程师
0 点赞 评论 收藏
分享
2020-09-19 17:38
已编辑
门头沟学院 算法工程师
动态规划与贪婪算法
动态规划与贪婪算法简记一 动态规划算法应用范围如果是要求一个问题的最优解（通常是求最大值或最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决该问题。我们在应用动态规划之前要分析能否把大问题分解成小问题，分解后的每个小问题也存在最优解。如果小问题的最优解组合起来能够得到整个问题的最优解，那么我们就可以应用动态规划解决这个问题。可以应用动态规划求解的问题的四个特点1.求一个问题的最优解；2.整体问题的最优解是依赖各个子问题的最优解；3.把大问题分解成若干个小问题，这些小问题之间还有相互重叠的更小的子问题；4.由于子问题在分解大问题的过程中重...
0 点赞 评论 收藏
分享
2020-07-22 20:28
已编辑
门头沟学院 算法工程师
给定一组矩形求能够形成的最大面积
题目描述给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积。图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位例如：给出的高度 =[2,1,5,6,2,3],返回10.思路分析可以依次遍历数组中的元素，可以知道较小的元素会成为矩形高的限制条件，比如遍历到1时，前一个数字是2,1会成为2、1这两个数字形成的矩形高度的限制条件，如果要形成宽度为2（也就是包含1和2的两部分）的矩形，其高度只能是1和2中的较小元素。遍历过程中遇到较大的元素不会成为其高度的限制条件。因此可以维护一个升序栈，当前遍历的元素如果大于栈顶指示的元素就直接将其入栈，小于栈顶元素的话就将...
0 点赞 评论 收藏
分享
2020-07-12 21:53
门头沟学院 算法工程师
寻找给定排列的下一个更大的排列
题目描述实现函数next permutation（下一个排列）：将排列中的数字重新排列成字典序中的下一个更大的排列。将排列中的数字重新排列成字典序中的下一个更大的排列。如果不存在这样的排列，则将其排列为字典序最小的排列（升序排列）。需要使用原地算法来解决这个问题，不能申请额外的内存空间。下面有几组样例，左边是输入的数据，右边是输出的答案：1,2,3→1,3,23,2,1→1,2,31,1,5→1,5,1思路分析要寻找给定的已知排列的下一个更大的排列，我们可以把给定的排列分为两个部分：从最后一个数往前的一个降序子序列和剩下的序列部分，由于后半部分是降序的了，就那么些个数字排列已经得到了最大的排列...
0 点赞 评论 收藏
分享
2020-07-09 21:46
门头沟学院 算法工程师
数据能够形成的最大容器
题目描述给定n个非负整数a1，a2，…，an，其中每个数字表示坐标(i, ai)处的一个点。以（i，ai）和（i，0）（i=1,2,3...n）为端点画出n条直线。你可以从中选择两条线与x轴一起构成一个容器，最大的容器能装多少水？例如：输入 [1,8,6,2,5,4,8,3,7]输出: 49思路分析与方法要求选择两条线与x轴一起构成一个容器，问能够形成的最大容量。我们可以依次遍历数据，分别把第i个数据当做最短边，然后在前面(从第一个数据向后寻找)和后面(从最后一个数据向前寻找)的数据中找出大于等于该数据的最长的边，这样就可以在O(n^2)复杂度下得到最大的面积，代码如下。 int maxAre...
0 点赞 评论 收藏
分享
2020-07-08 23:50
门头沟学院 算法工程师
求给定字符串中的最长回文串
题目描述找出给出的字符串S中最长的回文子串。假设S的最大长度为1000，并且只存在唯一解。思路分析首先要弄清楚回文串的概念，回文串就是正着顺序和反着顺序是一样的字符串，有aba和abba两种类型。现在我们怎么判断给定的字符串中的回文串呢？开始想着的是依次遍历字符串，然后从字符串的末尾和当前位置之间的字符串是否为回文串来寻找最长的回文串，比如给定字符串"abcbaba"，当前字符为'a'时，先'a'和字符串的末尾字符一致，然后相向缩小，得到'b'和'b'，然后继续缩小，得到'c'和'a'，没有匹配上；接着就让当前字符'a'和倒数第二个继续进行比较判断，一直到挨着的后一个字符，这样的方式复杂度过高...
0 点赞 评论 收藏
分享
关注他的用户也关注了：
牛客网
牛客企业服务