Skip to content

Latest commit

 

History

History
 
 

README.md

学习笔记

前言:

image-20200830224004795

训练环境设置、编码技巧和Code Style

时间和空间复杂度

1. 数组,链表,调表

数组:在内存中开辟连续的内存地址,存储元素

链表:当前Node对象存储当前节点值与下一节点内存地址

调表:带有调表索引的链表,只能用于元素有序的情况下,用来取代平衡树二分查找

左append 右append 查询 插入 删除
数组 O(1) O(1) O(1) O(n) O(n)
普通链表 O(1) O(1) O(n) O(1) O(1)
调表 O(1) O(1) O(log n) O(log n) O(log n)

空间复杂度上,数组最少,普通链表第二,跳表最高,但,都是O(n)。

链表应用:LRU Cache

跳表应用:Redis

2.栈和队列

栈(stack):先入后出(LIFO/FILO)

队列(Queue):先入先出(FIFO)

左append 右append 查询 插入 删除
- O(1) O(n) - O(1)
队列 - O(1) O(n) - O(1)

Array 实战题目

  • 盛最多水的容器(腾讯、百度、字节跳动在近半年内面试常考)

  • 移动零(华为、字节跳动在近半年内面试常考)

  • 爬楼梯(阿里巴巴、腾讯、字节跳动在半年内面试常考)

  • 三数之和(国内、国际大厂历年面试高频老题)

  • 盛最多水的容器(腾讯、百度、字节跳动在近半年内面试常考)

  • 移动零(华为、字节跳动在近半年内面试常考)

  • 爬楼梯(阿里巴巴、腾讯、字节跳动在半年内面试常考)

  • 三数之和(国内、国际大厂历年面试高频老题)

  • 两数之和(近半年内,字节跳动在面试中考查此题达到 152 次)

  • 盛最多水的容器(腾讯、百度、字节跳动在近半年内面试常考)

  • 移动零(华为、字节跳动在近半年内面试常考)

  • 爬楼梯(阿里巴巴、腾讯、字节跳动在半年内面试常考)

  • 三数之和(国内、国际大厂历年面试高频老题)

Linked List 实战题目

参考链接

栈参考链接

栈和队列实战题目

  • 有效的括号(亚马逊、JPMorgan 在半年内面试常考)

  • 最小栈(亚马逊在半年内面试常考)

  • 柱状图中最大的矩形(亚马逊、微软、字节跳动在半年内面试中考过)

  • 滑动窗口最大值(亚马逊在半年内面试常考)

  • 用 add first 或 add last 这套新的 API 改写 Deque 的代码

  • 分析 Queue 和 Priority Queue 的源码

  • 设计循环双端队列(Facebook 在 1 年内面试中考过)

  • 接雨水(亚马逊、字节跳动、高盛集团、Facebook 在半年内面试常考)

说明:改写代码和分析源码这两项作业,同学们需要在第 1 周的学习总结中完成。如果不熟悉 Java 语言,这两项作业可选做。