Skip to content

Latest commit

 

History

History
335 lines (204 loc) · 9.45 KB

Algorithm.md

File metadata and controls

335 lines (204 loc) · 9.45 KB
Raw

Leetcode知识点速通

Time complexity

使用环境

通过数据范围确定需要选取的算法。

时间复杂度 数据范围 常见算法
$O(logn)$ n < 1e32 二分法、GCD
$O(\sqrt{n}))$ n < 1e16 判断素数
$O(n)$ n < 10000000 素数筛、DP、双指针
$O(nlogn)$ n < 500000 二分法、排序、Kruskal、Dijkstra
$O(n\sqrt{n}))$ n < 50000 分块（不常见）
$O(n^2)$ n < 5000 DP
$O(n^3)$ n < 300 DP
$O(2^n)$ n < 30 二进制枚举
$O(n!)$ n < 11 搜索

Array

使用环境

对序列进行修改和查询时使用。（增加和删除的时间复杂度较高）

例题

Leetcode 26

Enumeration

使用环境

需要不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。

要点

给出解空间

  • 建立简洁的数学模型。
  • 枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？

减少枚举的空间

  • 枚举的范围是什么？是所有的内容都需要枚举吗？
  • 在用枚举法解决问题的时候，一定要想清楚这两件事，否则会带来不必要的时间开销。

选择合适的枚举顺序

  • 根据题目判断。比如例题中要求的是最大的符合条件的素数，那自然是从大到小枚举比较合适。

例题

Leetcode 401

Design

使用环境

需要创造支持某些操作的数据结构。

要点

根据已知的数据结构的操作做修改和组合。

例题

Leetcode 225、232

Bit Manipulation

使用环境

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

位运算一般有三种作用：

  1. 高效地进行某些运算，代替其它低效的方式。
  2. 表示集合。
  3. 题目本来就要求进行位运算

要点

获取一个数二进制的某一位

// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }

将一个数二进制的某一位设置为0

// 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

将一个数二进制的某一位设置为1

// 将 a 的第 b 位设置为 1 ，最低位编号为 0
int setBit(int a, int b) { return a | (1 << b); }

将一个数二进制的某一位取反

// 将 a 的第 b 位取反 ，最低位编号为 0
int flapBit(int a, int b) { return a ^ (1 << b); }

取出一个数二进制的最后一个1

// 取出 a 的二进制的最后一个 1
int getLastBit(int a) { return a & -a; }

例题

Leetcode 136、191

Braineaser

使用环境

通常为博弈问题。

要点

我们可以将当前的信息视为状态。如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。

定义 必胜状态 为 先手必胜的状态 ，必败状态 为 先手必败的状态 。

通过推理，我们可以得出下面三条定理：

  • 定理 1：没有后继状态的状态是必败状态。
  • 定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
  • 定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

例题

Leetcode 292

DFS/BFS

使用环境

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

要点

DFS 最显著的特征在于其 递归调用自身 。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次 。符合以上两条规则的函数，便是广义上的 DFS。

具体地说，DFS 大致结构如下：

DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
  在 v 上打访问标记
  for u in v 的相邻节点
    if u 没有打过访问标记 then
      DFS(u)
    end
  end
end

BFS 算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

具体地说，BFS 大致结构如下：

BFS(s) 
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) 
    u = q.pop()
    for each edge(u, v) 
      if (!visited[v]) 
        q.push(v)
        visited[v] = true
      end
    end
  end
end

例题

Leetcode 100、101

DP

使用环境

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

要点

对于一个能用动态规划解决的问题，一般采用如下思路解决：

  1. 将原问题划分为若干 阶段 ，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态 ）；
  2. 根据 状态定义，得到 初始状态 和 目标状态；
  3. 寻找每一个状态的可能 决策 ，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程 ）。
  4. 按顺序求解每一个阶段的问题。

例题

Leetcode 62、120、139、221

Graph

使用环境

如果题目显式的给出图结构，那就去思考图上经典算法，例如最短路、生成树等。

如果没有显式的给出图结构，那就看看有没有可供进行图论建模的语句，比如「xx课程 依赖 xx课程」（这里的 依赖 可以理解为图上的有向边，课程可以理解为图上节点）

例题

Leetcode 207

Hash Table

使用环境

哈希表又称散列表，一种以「key-value」形式存储数据的数据结构。

所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。

例题

Leetcode 1、202

Math

使用环境

涉及数学问题、找规律、计算素数、约数、最大公约数等。

要点

判断素数时，只需要枚举$[1,sqrt(x)]$即可。

遇到最大公约数的题目，可以考虑使用$gcd(a,b) = gcd(b, a%b)$进行化简。

例题

Leetcode 204、1447

Linked List

使用环境

对序列进行增加和删除时使用。

例题

Leetcode 21、83

String

使用环境

需要操作字符串时使用。

要点

熟悉字符串的基本操作函数。

例题

Leetcode 58

Two Pointer

使用环境

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。

要点

当题目中存在如下要求时，可以考虑使用双指针。

  • 维护区间信息
  • 子序列匹配
  • 利用序列有序性
  • 在单向链表中找环

例题

Leetcode 713、524、167

Labuladong刷题笔记

第一周

Algorithm Array Sliding window Binary search Bracket match Design (LRU)
Prob.ID 167、283 3 34、74 20、1541 146

第二周

Algorithm Expression Binary Tree Binary Tree 2 BST BST 2
Prob.ID 227 226、543 654、105 1038 701、450

第三周

Algorithm Graph Bipartite Graph Flood Fill MST Shortest Path
Prob.ID 797 785[图解] 130 1584[图解] 1514[图解]

第四周

Algorithm Backtrack Backtrack 2 Backtrack 3 Backtrack 4 BFS
Prob.ID 46 51 698 39 752

第五周

Algorithm Math Math 2 Math 3 Greedy Greedy 2
Prob.ID 384 204 172 134 1024

第六周

Algorithm DP DP 2 DP 3 DP 4 DP 5
Prob.ID 300 1143 172 72 198