leetcode

Link: 数据结构和算法学习指南 (qq.com)

  • 手把手刷链表题目

(学完一段时间之后,需要再回过头来再看一遍)

数据结构的存储方式

  • 数组(顺序存储):紧凑连续存储,可以随机访问,通过索引快速找到对应元素,而且相对节约存储空间。但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以保持连续,时间复杂度 O(N)。
  • 链表(链式存储):元素不连续,而是靠指针指向下一个元素的位置,所以不存在数组的扩容问题;如果知道某一元素的前驱和后驱,操作指针即可删除该元素或者插入新元素,时间复杂度 O(1)。但是正因为存储空间不连续,你无法根据一个索引算出对应元素的地址,所以不能随机访问;而且由于每个元素必须存储指向前后元素位置的指针,会消耗相对更多的储存空间。

刷题方法

数据结构的基本存储方式就是链式和顺序两种,基本操作就是增删查改,遍历方式无非迭代和递归。

刷算法题建议从「树」分类开始刷,结合框架思维,把这几十道题刷完,对于树结构的理解应该就到位了。这时候去看回溯、动规、分治等算法专题,对思路的理解可能会更加深刻一些。

  • 手把手刷链表题目

    • 递归反转链表:如何拆解复杂问题
    • 单链表的六大解题套路
      • Leetcode21 合并两个有序链表
        • 虚拟头节点
      • Leetcode23 合并k个升序链表
        • 关键在于如何在迭代过程中找到k个链表中最小的节点:可使用优先级队列(二叉堆),每次提取出最小的节点,也就是最小堆,并维护这个最小堆( O(NlogN) )
      • Leetcode19 删除链表的倒数第N个节点
        • 双指针 p and p+N
      • Leetcode876 单链表的中点
        • 双指针
      • Leetcode141 判断链表是否包含环
        • 双指针 slow and fast
        • 如何找到环的起点
      • Leetcode160 判断两个链表是否相交
作者

Xie Pan

发布于

2021-08-22

更新于

2021-09-14

许可协议

评论