leetcode.md

计划

• 第一阶段：打基础

  • 3个月，每天两道题，按照算法类型来刷，每个类型花1-2周，在每个类型下按照频率由大到小进行刷题
  • 对于每一道题，先思考5分钟，5分钟没有思路，可以看讨论区的答案，问题是如何分析的
  • 可以查看leetcode视频讲解，，YouTube 【back to back SWE】
  • 写成解题报告：解题思路+代码
    • 哪些知识点，正确的思路是怎样的，别人是怎么想到的，代码是怎么写的，代码有什么小技巧
  • 周末复习总结：
    • 重新做一遍本周的题目，做几道新题，看书

• 第二阶段：拓展思路

  • 1.5月，复习第一阶段的题目，并做100道新题
    • 工作日，复习题目
    • 周末，模拟考试，做新题，限定时间

• 第三阶段：面试

  • mock interview
  • 参加leetcode contest
  • 刷题顺序，安装公司分类来刷
  • 再刷100道题

• 3个资料：

  • 按国内公司分类：https://github.com/afatcoder/LeetcodeTop
  • 按照算法类型分类：https://github.com/wisdompeak/LeetCode
  • Leetcode 1-919 题的解析：https://github.com/grandyang/leetcode

数组

• 存储方式
  • 数组是存放在连续内存空间上的相同类型数据的集合。
  • 正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址
  • 时间复杂度为O(n)，所以数组不适合做频繁的增删操作
  • 二维数组中其实是一个线性数组存放着 其他数组的首地址。
    • 二维数据在内存中不是 3*4 的连续地址空间，而是4条连续的地址空间组成!
• 二分法
  • 用于有序数组
  • 要求时间复杂度为O(logn)
  • 第k小的数（寻找中位数）
• 双指针：
  • 分别从一个数组的头尾，向中间进行遍历，知道左指针大于（等于）右指针
  • 分别从一个数组的头尾，向中间进行遍历，左指针为当前数组的右边一个，右指针在左指针的右边（从后往前进行遍历）
  • 分别从两个数组的尾部向头部进行遍历，比较大小
  • 升序降序互换
• 第k小的数

链表

• 通过指针串联在一起的线性结构，每一个节点是由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）

• 类型

  • 单链表：链接的入口点称为列表的头结点也就是head
  • 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。可向前查询，也可以向后查询
  • 循环链表：链表首尾相连，可以用来解决约瑟夫环问题。

• 存储方式：

  • 不是连续分布，而是通过指针域的指针链接在内存中各个节点，即节点之间通过指针串联到一起。

• 定义：

  • 链表节点方式

    // 单链表
    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
                
    // 双链表
    class ListNode:
        def __init__(self, x):
            self.val = x
            self.prev = None
            self.next = None      

• 操作：

  • 删除节点操作：更改指针指向，C++ 需要手动释放删除节点的内存，时间复杂度为O(1)
  • 增加节点操作：更改指针指向，时间复杂度为O(1)
  • 查找节点操作：时间复杂度O(n)

• 性能分析：

  	插入/删除（时间复杂度）	查询（时间复杂度）	适用场景
  数组（长度固定）	O(n)	O(1)	数据量固定，频繁查询，较少增删
  链表（长度不固定）	O(1)	O(n)	数据量不固定，频繁增删，较少查询

字符串

• 字符串也是一种数组，所以元素在内存中是连续分布，但是不能改变，需要转化为列表后再进行赋值操作