Open
Description
回顾
算法
复杂度分析
复杂度分析就是用来分析算法执行效率与数据规模之间增长关系的方法。
Big O notation：
- O(1)：常数复杂度
- O(log n)：对数复杂度
- O(n)：线性时间复杂度
- O(n²)：平方复杂度
- O(n^3)：立方复杂度
- O(2^n)：指数复杂度
- O(n!)：阶乘复杂度
从时间复杂度的分析情况可以区分为：
- 最好情况时间复杂度：在理响的情况下，执行一段代码的时间复杂度。
- 最坏情况时间复杂度：在最糟糕情况下，执行一段代码的时间复杂度。
- 平均情况时间复杂度：因为在推到过程中，要把各种情况发生的概率考虑进去，需要使用加权平均值的概念，所以也可以称为加权平均时间复杂度。
以上三种情况在大多数情况不需要区分，只要求出一个复杂度就足矣。只有在同一块代码在不同情况下，出现数量级的差别，才会具体进行区别分析。
- 均摊时间复杂度：把一组连续的操作的耗时平均分摊到所有元素上得到的时间复杂度。可以列季尾是一种特殊的平均时间复杂度。
常见到的空间复杂度：
- O(1)
- O(n)
- O(n²)
递归
写递归代码的关键时找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和重值条件翻译成代码。
使用递归算法解决问题的三个条件：
- 一个问题的解可以分解成几个子问题
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
模板公式：
def recursion(...):
# recursion terminator
...
# process logic in current level
...
# drill down
...
# reverse the current level status if needed
...避免递归过程中重复计算：
- 使用一个数据结构，保存已经求结果的f(k)；
- 当递归调用f(k)的时候，先看下是否已经求解；
- 如果时就直接从数据结构中取数据，返回结果；
- 否则就继续执行逻辑并下钻。
分治
分治算法的核心思想是分而治之，将原问题划分成n个规模较小，并且结构和原问题相似的子问题，递归地解决这些字问题，然后再合并其结果，得到原问题地解。
分治和递归之间的区别：
- 分治算法是一种处理问题的思想。
- 递归是一种编程技巧。
分治每一层的递归都涉及3种操作：
- 分解：将原问题分解成一系列子问题；
- 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
- 合并：将子问题的结果合并成原问题。
模板公式：
def divide_conquer(...):
# recursion terminator
...
# prepare data
...
# conquer subproblems
...
# process and generate the final result
...分治算法能解决的问题，一般需要满足的条件：
- 原问题与分解成的小问题具有相同的模式；
- 原问题分解成的子问题可以独立求解，子问题之间没有相关性（这一点是分治算法和动态规划的明显区别）；
- 具有分解终止条件，当问题足够小时，可以直接求解；
- 可以将子问题合并成原问题，这个合并操作的负责督不能过高，否则起不到减小算法总体复杂度的效果。
二分查找
二分查找的核心思想是每次都通过根区间中的中间元素对比，将待查找的区间缩小位一半，知道找到要查找的元素，或者区间被缩小到0。有点类似分治思想。
二分的时间复杂度是O(logn)。
二分查找中最简单的情况，在有序数组中不存在重复元素，找到给定值。可以通过递归和非递归来实现：
- 递归实现：
class Solution {
public int bsearch(int[] a, int n, int val) {
return bsearchInternally(a, 0, n - 1, val);
}
private int bsearchInternally(int[] a, int low, int high, int value) {
if (low > high) {
return -1;
}
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
}
if (a[mid] < value) {
return bsearchInternally(a, mid+1, high, value);
}
return bsearchInternally(a, low, mid-1, value);
}
}- 非递归实现：
class Solution {
public int bsearch(int[] a, int n, int value) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
}
if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}求mid值的时候如果使用mid = (low + high) / 2的方式是有问题的。如果low和right比较大的话，会出现溢出的情况。
- 所以应该使用mid = (low - high) / 2 + low。
- 而进一步的优化是使用位运算mid = low + ((high - low) >> 1)
二分查找应用场景的局限性
- 依赖顺序表结构，或者说是数组：算法需要按照下标随机访问元素，如果使用类似链表的非顺序表结构，这种随机访问数据的时间复杂度就是O(n)而不是O(1)，从而导致时间复杂度变高。
- 只针对有序数据：如果数据是无序的，使用二分查找前要先排序。如果应用场景中频繁进行插入、删除的操作，导致每次查找前都需要进行排序，那么维护有序的成本会很高。
- 不适合数据量太小的场景：因为没有这个必要，直接顺序遍历就可以了。
- 不适合数据量太大的场景：局限性第二条提到二分查找依赖数组，如果如果过大的数据，类似1G，那么就需要1GB的连续内存空间，这种连续空间很难在内存中申请到。
遍历和搜索
树的定义
节点之间的关系
- A节点是B节点的父节点
- B节点是A节点的子节点
- B、C、D的父节点都是A，它们是兄弟节点
- 没有父节点的E是根节点
- 没有子节点的节点是叶子节点，如G、H、I、J
树中的相似概念
- 节点的高度：节点到叶子节点的最长路径(边数)
- 节点的深度：根节点到这个节点所经历的边的个数
- 节点的层数：节点的深度+1
- 树的高度：根节点的高度
树的遍历
- 前序遍历：当前节点 -> 左子树 -> 右子树
- 中序遍历：左子树 -> 当前节点 -> 右子树
- 后序遍历：左子树 -> 右子树 -> 当前节点
深度优先搜索 DFS
- 递归代码：
def dfs(node, visited):
visited.add(node)
# process current node here
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)- 非递归代码：
def dfs(self, tree):
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other process work广度优先搜索 BFS
- 非递归代码：
dfs bfs(tree, start, end):
queue = []
queue.append([start])
visited.add(start)
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
queue.push(nodes)
# other processing work动态规划
动态规划适合用来求最优解问题，例如最大值、最小值。它可以显著降低时间复杂度、提高代码的执行效率。
思路
- 将问题分成多个阶段
- 每个阶段对应一个策略
- 记录每一个阶段科大的状态集合
- 通过当前阶段的状态集合，推导下一个阶段的状态集合
动态规划的大部分问题都能够通过回溯算法来解决，但是时间复杂度会是指数级的。而动态规划的效率会高很多，采用的是一种空间换时间的算法思想。
概念
- 状态的定义：opt[n]
- 最优子结构：opt[n] = best_of(opt[n-1], opt[n-2], ...)
- 状态转移方程：DP方程
案例：斐波那契数列
fib[n] = fib[n-1] + fib[n-2]
fib(0) = 0
fib(1) = 1
class Solution {
public void fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}案例：Count the Path
paths(start, end) = paths(A, end) + paths(B, end)
notValidSquare => return 0
anEnd => return 1
class Solution {
public int count(boolean[][] grid, int row, int col) {
if (!validSquare(grid, row, col)) {
return 0;
}
if (atEnd(grid, row, col)) {
return 1;
}
return count(grid, row + 1, col) + count(grid, row, col + 1);
}
}数据结构
数组
数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。(回顾一下，二分搜索使用排序后的数组)
概念
- 线性表：数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方法。
- 数组
- 队列
- 链表
- 栈
- 非线性表：数据之间并不是简单前后的关系。
- 二叉树
- 堆
- 图
- 连续的内存空间和相同的数据：
- 因为这两种特性，数组才能够做到随机访问。时间复杂度O(1)。
- 因为这两种特性，数组的插入删除，为了保持连续性，需要大量的数据搬移工作。时间复杂度O(n)。
有趣的问题
为什么数组的下标是从0而不是从1开始？
从数组存储的内存模型上看，"下标"最确切的定义是偏移offset。如果a表示数组的首地址，a[0]就是偏移位0的位置，也就是首地址，如果用1开始计数，每次随机访问就多了一次减法运算，对CPU来说就多了一条减法指令。
链表
链表通过指针将一组零散的内存块串联起来使用。
种类
- 单链表：节点除了存储数据外，还会通过next指针存储下一个节点的地址。
- 循环链表：一种特殊的单链表。单链表的尾节点指向空地址，循环链表尾节点指向头节点。
- 双向链表：支持两个方向，不仅有next指针指向下一个节点，还有prev指针指向前一个节点。
- 双向循环链表：循环链表和双向链表的结合。
操作
- 删除操作：只需要改变指针，时间复杂度O(1)。如果算上遍历查找的过程，时间复杂度是O(n)。
- 新增操作：和删除操作同理。
- 访问操作：数组可以做到随机访问的时间复杂度为O(1)，链表因为要指针遍历搜索，所以时间复杂度是O(n)。
常见的链表操作(代码待补充)
- 单链表反转
- 链表中环检测
- 两个有虚的链表合并
- 删除链表倒数第n个节点
- 求链表的中间节点
注意点
写链表的时候，很多地方会出现小问题，需要很仔细：
- 指针的操作
- 边界条件
栈
栈是一种操作受限的线性表(回顾下，线性表概念数组中有)，呈现后进者先出，先进者后出的特性。
使用场景
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，可以首选栈这个数据结构。
如何实现
- 通过数组实现，称为顺序栈
class ArrayStack {
private Object[] datas;
private int count;
private int n;
public ArrayStack(int n) {
this.datas = new Object[n];
this.n = n;
}
public boolean push(Object data) {
if (count == n) {
return false;
}
datas[count++] = data;
return true;
}
public Object pop() {
if (count == 0) {
return null;
}
return datas[--count];
}
}- 通过链表实现，称为链式栈
存取的时间复杂度：O(1)
队列
队列和栈一样，是一种操作受限的线性表数据结构，呈现先进新出，后今后出的特性。
特性扩展
- 循环队列
- 阻塞队列
- 并发队列
- Disruptor
- Linux环形缓存
- ArrayBlockingQueue(实现公平锁)
实现
- 顺序队列：使用数组来实现
public class ArrayQueue {
private Object[] datas;
private int n;
private int head;
private int tail;
public ArrayQueue(int capacity) {
items = new Object[capacity];
n = capacity;
}
public boolean enqueue(Object data) {
if (tail == n) {
return false;
}
items[tail++] = data;
return true;
}
public Object dequeue() {
if (head == tail) {
return null;
}
Object ret = items[++head];
return ret;
}
}- 链式队列：使用链表来实现
图
图是非线性表数据结构，在图中的元素被称为顶点，顶点与顶点之间建立的关系叫做边。
- 边是有方向的图称为有向图。
- 反之没有方向的叫做无向图。
图中度的概念是指一个顶点有多少条边，而有向图中：
- 入度的概念表示有多少条边指向这个顶点
- 出度的概念代表有多少条边是以这个顶点为起点指向其他顶点的。
微博的粉丝数就是当前顶点的入度，关注数就是顶点的出度。
图的存储方式
- 邻接矩阵存储方式：邻接矩阵底层依赖二维数组
- 缺点是浪费空间，需要多存储至少一倍的数据。
- 优点是因为基于数组，所以在获取连个顶点关系的时候非常高效，而且计算简单。
- 邻接表存储方式：类似散列表，每个顶点对应一条链表，链表中存储与顶点相连接的其他顶点。
- 优点是省空间
- 缺点是因为是链式的，所以查询两个顶点之间关系的时候就很耗时间
感受
感性角度
整一个月，线上线下的学习过程，我觉得很充实，也很幸福。
- 充实在：
- 课程安排的紧凑，题目量大且分类明确，学习的过程因为知识点安排的顺序而有了一种循序渐进的感觉，不会毫无方向。
- 在实际学习过程中，每周的解题，提交，review的cycle，如同不断向前滚动的车轮，给我切实在积累进步的体验。
- 期间穿插覃超老师的视频讲解，对当时的一些类型题目的解法也有很有效的帮助。
- 幸福在：
- 因为有这么多志同道合的好伙伴，当知道有这么多人和自己一样在认真解题，并且之后还会一起分享的时候，就算再困难的题目，解题的时候也不觉得苦了，反而希望能做出来，或者至少想到一些思路，然后等review的时候可以和大家一起分享。
- 而且，每周都会迫不及待地想看其他同学有没有某道题的好的解法，如果有看到，就好似如获至宝，开心的不行，然后赶紧吸收学习，自己也写下来。而当别人review自己的时候，尤其是夸奖的时候(班里的同学review时都特别友好)，心里也会很开心。
理性角度
我觉得参加这个训练营，有如下的几点收获：
- 收获到志同道合的同伴：平时实际生活中很少碰到愿意潜心学习、讨论算法等问题的朋友，而通过这个训练营认识了这么多的伙伴，这是一个很大很大的收获！
- 了解了很多学习方法：无论是覃超老师的五毒神掌，还是极客时间提交作业的这种学习方式，或者我们组的笙南同学的学习方法等，都非常有借鉴和学习的价值。
- 拿到了学习算法的路线图：我原本学习算法的体验，就犹如行走在迷宫，兜兜转转，不着要领。而通过课程的学习，就仿佛拿到了迷宫的路线图，虽然不是任意门，可以让我直接抵达终点，但至少有了明确的方向，只要一步步走下去，一定能抵达终点。
目标
课程虽然结束了，没有了课程安排中制定的任务计划，但希望这一个月来的这种不断push自己的感觉不会流失。
所以我给自己制定了2个小目标：
- leetcode题目达到300题：按照目前平均1.5题的解题速度，大概需要200天的时间。但是，我认为整个过程不应该是线性的，随着解题数量的增加，熟练度应该也会提升，我希望自己能在接下去的100天，大概3个月的时间里，把这个目标达成！
- 工作小组做一次学习分享：这一个月的收获满满，我希望通过对过去一个月学习经历的梳理、消化，（在不侵犯版权的前提下）能整理出一份可以分享的学习资料，在组内做一次学习分享。
结尾
在这里，我想摘抄一句个人最喜欢的作家和哲学家纳西姆·塔勒布的书《Skin in the Game》中的一句话：
你天然会捍卫属于你的东西，但只有你能捍卫的东西，它们才真正属于你。
为了能配得上自己想要获得的，坚持吧！努力吧！
Metadata
Metadata
Assignees
Labels
No labels