专栏首页ACM金牌选手讲解LeetCode算法ACM金牌选手讲解LeetCode算法《线性表》
原创

ACM金牌选手讲解LeetCode算法《线性表》

线性表

LeetCode刷题过程中,常常用到的线性表主要包括以下四个重要的数据结构: 数组、链表、栈、队列。

下面将分别讲解数组、链表、栈和队列。

线性表概述

线性: 这里的线性是逻辑上的连续,而非物理存储的连续。

存储的数据: 线性表是一个有n个相同类型数据的有序序列。

数组array

介绍

数组是物理存储连续的线性表,其常见的形式为 a[0]、a[1] ... a[n-1]a[i-1]a[i] 的前驱,a[i+1]a[i] 的后继。

基本操作

插入

插入元素,要将插入位置后的元素全部向后移动一位。

下图以数组长度为6,数据为0、1、2、3、4、5,在位置3插入一个元素X举例。

删除

删除元素,要讲删除位置后的元素全部向前移动一位。

下图以数组长度为6,数据为0、1、2、3、4、5,删除位置3上的元素X举例。

反转

翻转数组,本质是将数组存储的数据进行反转。

下图以数组长度为6,数据为0、1、2、3、4、5,反转整个数组举例。

例题

LeetCode 27. 移除元素

题意

删除数组中所有等于 val 的元素,返回移除后数组的新长度。要求不使用额外的空间。

示例

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]

题解

数组的删除操作,但如何不使用额外的空间呢?因为删除val后的数组的长度小于等于原数组的长度,因此可以一边将不等于val的数组放入原数组中,同时判断原数组的数是否等于val

代码

class Solution {
    public int removeElement(int[] nums, int val) {
        // left 存当前nums数组中不等于val的数字数量
        int left = 0; 
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

习题推荐

LeetCode 35. 搜索插入位置

链表

介绍

链表的出现是为了解决数组插入、删除带来的线性开销。

区别于数组,链表中的元素可以不连续存储,每一个元素包含该 元素的数据指向链表下一个节点的指针

基本操作

插入

插入元素,要将插入元素前一个位置的指针指向插入元素本身,将插入元素的指针指向前一个位置。

删除

删除元素,要将 删除元素前一个元素的指针 指向 删除元素后一个元素,代码实现上需要将 删除元素指针指向的位置 记录下来。

下图是以长度为5的链表,删除位置3上的元素为例子。

翻转

翻转链表,可以一边遍历一边用一个临时变量记录当前元素的下一个元素指针所指向的位置,然后再将当前元素的下一个元素指针指向自己。

下图是以长度为5的链表,翻转链表为例子。

例题

1. LeetCode 206. 反转链表

题意

给单链表的头节点 head ,请反转链表,并返回反转后的链表。

示例

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

题解

按上述链表翻转操作思路实现代码。

代码

public ListNode reverseList(ListNode head) {
	  // pre 存的是当前节点的上一个节点
    ListNode prev = null;
    // curr 存的是当前链表遍历到节点
    ListNode curr = head;
    while (curr != null) {
        // next 存的是当前节点下一个节点
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

习题推荐

  1. LeetCode237. 删除链表中的节点
  2. LeetCode 21. 合并两个有序链表
  3. LeetCode 160. 相交链表

栈和队列

栈介绍

栈被限定必须在栈顶进行插入和删除操作,因此其特点为是后进先出

下图是栈的插入(入栈)、删除(出栈)示意图。

队列介绍

队列被限定在队头进行删除操作,队尾进行插入操作,因此其特点为先进先出

下图是队列的插入(入队)、删除(出队)示意图。

基本操作

栈和队列的插入和删除操作上图已解释。

例题

LeetCode 155. 最小栈

题意

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

题解

新建辅助栈,辅助栈的栈顶表示原栈所有数字最小值,下面分别讨论题目要求的四种操作,分别如何实现。

  • push(x): 若插入的数字小于等于辅助栈的栈顶元素,则这个数字在原栈是最小值(之一),我们将其插入辅助栈中。
  • pop(): 若原栈删除的数字等于辅助栈的栈顶元素,则这个数字在原栈是最小值(之一),我们同时原栈和辅助栈的栈顶元素;反之,只删除原栈栈顶元素。
  • top(): 返回原栈的栈顶元素。
  • getMin(): 返回辅助栈的栈顶元素。

代码

class MinStack {
    public Stack<Integer> s, min_s;
    public MinStack() {
        s = new Stack<>();
        min_s= new Stack<>();
    }
    public void push(int x) {
        s.push(x);
        if(min_s.isEmpty() || x <= min_s.peek())
            min_s.push(x);
    }
    public void pop() {
        if(s.pop().equals(min_s.peek()))
            min_s.pop();
    }
    public int top() {
        return s.peek();
    }
    public int getMin() {
        return min_s.peek();
    }
}

习题推荐

LeetCode 20. 有效的括号

下面是粉丝福利

【计算机学习核心资源】: 涵盖了所有计算机学习核心资源,学完进大厂问题不大。

【github宝藏仓库】: 对学习和面试都非常有帮助,超过99%同龄人。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 想去硅谷、BAT工作?算法面试通关攻略在这里

    一整套视频还是很有价值的,我这几天也看了最新的几集,对于新手比较友好,对于有一定经验的可能觉得简单。

    ACM算法日常
  • Facebook面试官:如何突围大厂算法面试?

    作为一名程序员,你肯定想过:编程最本质的知识是什么?很多人都会说是算法与数据结构。

    谭庆波
  • 如何应对“智力型”的算法面试题?

    “给你a、b两个文件,他们各存放50亿条URL,其中每条URL各占用64字节,内存限制是4G,请你编写代码找出a、b文件中相同的URL”。这是某家大公司在201...

    ACM算法日常
  • 计算机领域有哪些常见的比赛

    入了计算机这一行,写代码便是我们安身立命的本领,夜以继日勤学苦练,希望早日成为编程高手。

    五分钟学算法
  • 计算机领域有哪些常见的比赛?各个比赛的含金量?

    入了计算机这一行,写代码便是我们安身立命的本领,夜以继日勤学苦练,希望早日成为编程高手。

    帅地
  • 计算机领域有哪些常见的比赛?各个比赛的含金量?

    入了计算机这一行,写代码便是我们安身立命的本领,夜以继日勤学苦练,希望早日成为编程高手。

    良月柒
  • 计算机领域有哪些常见的比赛

    入了计算机这一行,写代码便是我们安身立命的本领,夜以继日勤学苦练,希望早日成为编程高手。

    AI算法与图像处理
  • 计算机领域有哪些常见的比赛

    入了计算机这一行,写代码便是我们安身立命的本领,夜以继日勤学苦练,希望早日成为编程高手。

    GitHubDaily
  • 【比赛】计算机领域有哪些常见的比赛

    入了计算机这一行,写代码便是我们安身立命的本领,夜以继日勤学苦练,希望早日成为编程高手。

    zenRRan
  • 聊聊算法在面试中的地位

    前段时间,有一位好友找到我,向我打听阿里社招笔试是否看重算法题的考察,我给予了肯定的答复。他表现的有些沮丧,表示自己工程底子很扎实,框架源码也研究地很透彻,唯独...

    kirito-moe
  • 【非广告】三千字干货经验分享,新手怎么学好算法和数据结构?

    今天和大家聊聊算法和数据结构的提升问题,因为很多小伙伴找到我说自己即将面临面试或者是考研的机试,但是对于自己的实力没有信心,想问一问有没有什么提升的方法。所以今...

    黄鸿波
  • 一个关于仰望,崇拜和梦想的故事

    从我接触程序竞赛到现在应该有十多年了,单说ACM竞赛,从第一次非正式参赛到现在也差不多有7年多的样子。有太多的故事,想说的话,却一直没能有机会写...

    ACM算法日常
  • 刷了 1000 多道算法题,一点心得

    开个玩笑,其实,算法题目已经成为了公司筛人的一种方式,大厂的每一轮面试基本都会有几道算法题,甚至有的公司笔试全部都是算法题。其他题目答的都差不多,那你算法题做不...

    程序员鱼皮
  • 算法八股,简历项目,在校小白如何冲击大厂?快上车,我有!

    上海 985 计算机专业大三在读,有 acm 经验,无牌子,有一些算法竞赛和数模小奖,写在简历上的都是课程项目。

    ACM算法日常
  • 有哪些好的刷题网站?2017年最受欢迎的编程挑战网站

    编程几乎已经成为了人类所知每个行业的必要组成部分,如今有越来越多的人开始了他们的编程之旅。 ? 如果你正在在学习编程,那么我可以告诉你一个提高技能的好方法,那就...

    企鹅号小编
  • 塔秘 | 最受欢迎的编程难题网站列表汇总

    前言 编程几乎已经成为了人类所知每个行业的必要组成部分,如今有越来越多的人开始了他们的编程之旅。 ? 本文列举了一些非常受欢迎的编程难题网站列表,并且做了简单介...

    灯塔大数据
  • 【NLP 算法岗】提前批暑期实习面(试)经(历)

    某不知名末流 985 本硕,三无 FW :无实习经历,无比赛经历,无项目经历。本科水过一段时间 ACM ,4 月份侥幸中了一篇 ACL ,方向很基础、很冷门,对...

    godweiyang
  • 北大主场夺金ACM-ICPC全球总决赛,总教练罗国杰分享背后“秘笈”

    昨天(4月19日)下午,第42届ACM-ICPC国际大学生程序设计竞赛全球总决赛,在北京大学邱德拔体育馆举行,这也是2005年上海、2010年哈尔滨之后,中国第...

    量子位
  • ACM-ICPC 国际大学生程序设计竞赛亚洲区数据分析:Part 1

    在刚刚结束的第43届ACM国际大学生程序设计竞赛亚洲区总决赛(Asia-East Continent Final)中,由中山大学数据科学与计算机学院的三名本科生...

    用户1621951

扫码关注云+社区

领取腾讯云代金券