vlambda博客
学习文章列表

想刷 LeetCode ,在此之前需要做什么准备?

 关注
脚本之家
,与百万开发者在一起
想刷 LeetCode ,在此之前需要做什么准备?
出处:吴师兄学算法 (ID:CXYxiaowu)

平时挺多人问我类似的问题:吴师兄,我是非计算机专业的学生,想刷 LeetCode ,请问在此之前需要做什么准备?

一般我的回答都是这样的:只有你会基础的语法,比如知道数组、链表怎么初始化,再加上了解一些基础的数据结构,比如栈、队列、链表、二叉树这些,就足以开始你的刷题之旅。

绝大部分情况下,LeetCode 算法题的代码就是基础语法+基础数据结构就能解决的。

不信的话,你可以往前看看我最近写的那些文章,里面涉及的代码来来回回就那些关键字。

但是,如果你连基础的数据结构都没有掌握,那刷起题可就费劲了,基础不牢,地动山摇!

比如,来看这样一道算法题,如果你连栈的先入后出的特点都不了解,不可能做出来的。

题目描述如下:

给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

我来给大家翻译一下题目意思。

想刷 LeetCode ,在此之前需要做什么准备?

给定了两个数组 pushed 和 popped ,从头到尾的遍历 pushed ,在遍历的过程中将  pushed 中的元素添加到一个栈中,加入之后,有两个操作:

  • 1、继续添加   pushed 后面的元素到栈中,比如加入 1 之后,继续加入 2 。
  • 2、把栈中的栈顶元素取出来(可重复操作)
想刷 LeetCode ,在此之前需要做什么准备?

按照这样的规则进行操作,判断一下,pushed 数组能否借助这个栈输出为 poped 数组这样的排序。

比如:pushed 数组为 1 2 3 4 5,那么它可以输出为 4 5 3 2 1 这样的排序数组。

想刷 LeetCode ,在此之前需要做什么准备?

但是,pushed 数组为 1 2 3 4 5,它不能输出为 4 5 3 1 2 这样的排序数组。

想刷 LeetCode ,在此之前需要做什么准备?

理解清楚题意之后,操作点实际上就是在这个栈上面了,只需要每次都借助先入后出的特点即可。

具体操作如下:

  • 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;

    }
}

是不是认同我的回答:只有你会基础的语法,比如知道数组、链表怎么初始化,再加上了解一些基础的数据结构,比如栈、队列、链表、二叉树这些,就足以开始你的刷题之旅。

<END>

程序员专属T恤

商品直购链接  👇

想刷 LeetCode ,在此之前需要做什么准备? 脚本之家严选 交易担保 放心买 程序员极客短袖T恤

  推荐阅读: