LeetCode JS 题解: https://github.com/ufresh2013/-algorithm015

1. 时间复杂度、空间复杂度

O(1): 哈希表(JS 对象)，根据 key 就可以直接拿到 val
O(n): 大多数遍历，比如数数，从 1 数到 100
O(n²):双重循环，比如排序(冒泡、选择)，每个元素都需要其他元素比较放置
O(logn): 二分查找/二叉树搜索，每次查找的范围都/2
O(nlogn): 快排
O(2^n): 递归

2. 数据结构与相关题目

2.1 一维

  • 数组 array
  • 链表 linked list,
  • 栈 stack
  • 队列 queue
  • 集合 set
  • 映射 map

2.2 二维

  • 树 tree
  • 图 graph
  • 二叉搜索树 binary search tree
  • 堆 heap
  • 并查集 disjoint set
  • 字典树 trie

2.3 特殊

  • 位运算 bit manipulation,
  • LRU 缓存 LRU cache

3. 解题思路

  • 双指针
  • 滑动窗口
  • 深度优先搜索 DFS
  • 广度优先搜索 BFS
  • 二分查找
  • 贪心算法
  • 动态规划

参考资料