我想学习 LeetCode,在此之前我需要做些什么?
大家好,我是吴师兄。
平时挺多人问我类似的问题:吴师兄,我是非计算机专业的学生,想刷 LeetCode ,请问在此之前需要做什么准备?
一般我的回答都是这样的:只有你会基础的语法,比如知道数组、链表怎么初始化,再加上了解一些基础的数据结构,比如栈、队列、链表、二叉树这些,就足以开始你的刷题之旅。
绝大部分情况下,LeetCode 算法题的代码就是基础语法+基础数据结构就能解决的。
不信的话,你可以往前看看我最近写的那些文章,里面涉及的代码来来回回就那些关键字。
但是,如果你连基础的数据结构都没有掌握,那刷起题可就费劲了,基础不牢,地动山摇!
比如,来看这样一道算法题,如果你连栈的先入后出的特点都不了解,不可能做出来的。
题目描述如下:
给定 pushed
和 popped
两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true
;否则,返回 false
。
我来给大家翻译一下题目意思。
给定了两个数组 pushed
和 popped
,从头到尾的遍历 pushed
,在遍历的过程中将 pushed
中的元素添加到一个栈中,加入之后,有两个操作:
- 1、继续添加
pushed
后面的元素到栈中,比如加入 1 之后,继续加入 2 。 - 2、把栈中的栈顶元素取出来(可重复操作)
按照这样的规则进行操作,判断一下,pushed
数组能否借助这个栈输出为 poped
数组这样的排序。
比如:pushed
数组为 1 2 3 4 5
,那么它可以输出为 4 5 3 2 1
这样的排序数组。
但是,pushed
数组为 1 2 3 4 5
,它不能输出为 4 5 3 1 2
这样的排序数组。
理解清楚题意之后,操作点实际上就是在这个栈上面了,只需要每次都借助先入后出的特点即可。
具体操作如下:
- 1、设置一个索引 index 表示 popped 数组中元素的下标,判断该索引指向的元素能否正常的出栈
- 2、遍历 pushed 数组中的每个元素,在遍历 pushed 数组时,把当前遍历的元素加入到栈中
- 3、加入完之后,不断的执行以下的判断
- 3.1、栈中是否有元素
- 3.2、栈顶元素是否和 popped 当前下标的元素相同
- 4、如果同时满足这两个条件,说明这个元素可以满足要求,即可以在最初空栈上进行推入 push 和弹出 pop 操作
- 5、遍历完 pushed 数组中的每个元素之后,如果发现栈不为空,那么说明出栈序列不合法,返回 false
- 6、遍历完 pushed 数组中的每个元素之后,如果发现栈为空,那么说明出栈序列合法,返回 true
这样,这道题目也就做出来了,是不是感觉很简单,只需要掌握栈的先入后出的特点就能解决。
再来看看代码:
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// 利用栈来模拟入栈和出栈操作
Stack<Integer> s = new Stack<Integer>();
// index 表示 popped 数组中元素的下标
// 比如 popped 是 [4,5,3,2,1]
// 那么第 0 个下标元素是 4 这个数字
// 先去判断这个数字能否正常的出栈
int index = 0;
// 遍历 pushed 数组中的每个元素
for(int i = 0 ; i < pushed.length; i ++){
// 在遍历 pushed 数组时,把当前遍历的元素加入到栈中
s.push(pushed[i]);
// 加入完之后,不断的执行以下的判断
// 1、栈中是否有元素
// 2、栈顶元素是否和 popped 当前下标的元素相同
// 如果同时满足这两个条件
// 说明这个元素可以满足要求,即可以在最初空栈上进行推入 push 和弹出 pop 操作
while(!s.isEmpty() && popped[index] == s.peek()){
// 那么就把栈顶元素弹出
s.pop();
// 同时 index++,观察 popped 下一个元素
index++;
}
}
// 遍历完 pushed 数组中的每个元素之后,如果发现栈不为空
if(!s.isEmpty()){
// 那么说明出栈序列不合法,返回 false
return false;
}
// 否则返回 true
return true;
}
}
是不是认同我的回答:只有你会基础的语法,比如知道数组、链表怎么初始化,再加上了解一些基础的数据结构,比如栈、队列、链表、二叉树这些,就足以开始你的刷题之旅。
上一篇: 新手入门 Java 基础
下一篇: 基础不牢,地动山摇
推荐阅读
-
我想学习 LeetCode,在此之前我需要做些什么?
-
计算机视觉中,究竟有哪些好用的目标跟踪算法(下)-快速变形主要因为CF是模板类方法。容易跟丢这个比较好理解,前面分析了相关滤波是模板类方法,如果目标快速变形,那基于HOG的梯度模板肯定就跟不上了,如果快速变色,那基于CN的颜色模板肯定也就跟不上了。这个还和模型更新策略与更新速度有关,固定学习率的线性加权更新,如果学习率太大,部分或短暂遮挡和任何检测不准确,模型就会学习到背景信息,积累到一定程度模型跟着背景私奔了,一去不复返。如果学习率太小,目标已经变形了而模板还是那个模板,就会变得不认识目标。(举个例子,多年不见的同学,你很可能就认不出了,而经常见面的同学,即使变化很大你也认识,因为常见的同学在你大脑里面的模型在持续更新,而多年不见就是很久不更新) 快速运动主要是边界效应(Boundary Effets),而且边界效应产生的错误样本会造成分类器判别力不够强,下面分训练阶段和检测阶段分别讨论。 训练阶段,合成样本降低了判别能力。如果不加余弦窗,那么移位样本是长这样的: 除了那个最原始样本,其他样本都是“合成”的,100*100的图像块,只有1/10000的样本是真实的,这样的样本集根本不能拿来训练。如果加了余弦窗,由于图像边缘像素值都是0,循环移位过程中只要目标保持完整那这个样本就是合理的,只有目标中心接近边缘时,目标跨越边界的那些样本是错误的,这样虽不真实但合理的样本数量增加到了大约2/3(padding= 1),即使这样仍然有1/3(3000/10000)的样本是不合理的,这些样本会降低分类器的判别能力。再者,加余弦窗也不是“免费的”,余弦窗将图像块的边缘区域像素全部变成0,大量过滤掉分类器本来非常需要学习的背景信息,原本训练时判别器能看到的背景信息就非常有限,我们还加了个余弦窗挡住了背景,这样进一步降低了分类器的判别力(是不是上帝在我前遮住了帘。不是上帝,是余弦窗)。 检测阶段,相关滤波对快速运动的目标检测比较乏力。相关滤波训练的图像块和检测的图像块大小必须是一样的,这就是说你训练了一个100*100的滤波器,那你也只能检测100*100的区域,如果打算通过加更大的padding来扩展检测区域,那样除了扩展了复杂度,并不会有什么好处。目标运动可能是目标自身移动,或摄像机移动,按照目标在检测区域的位置分四种情况来看: 如果目标在中心附近,检测准确且成功。 如果目标移动到了边界附近但还没有出边界,加了余弦窗以后,部分目标像素会被过滤掉,这时候就没法保证这里的响应是全局最大的,而且,这时候的检测样本和训练过程中的那些不合理样本很像,所以很可能会失败。 如果目标的一部分已经移出了这个区域,而我们还要加余弦窗,很可能就过滤掉了仅存的目标像素,检测失败。 如果整个目标已经位移出了这个区域,那肯定就检测失败了。 以上就是边界效应(Boundary Effets),推荐两个主流的解决边界效应的方法,但速度比较慢,并不推荐用于实时场合。