Nemo
Nemo
极客时间-算法训练营随堂笔记
极客时间-算法训练营随堂笔记

数据结构与算法总览

精通一个领域

  1. Chunk it up 切碎知识点
    • 庖丁解牛
    • 脉络链接
  2. Deliberate Practicing 刻意练习
  3. Feedback 反馈

数据结构

  • 一维:
    • 基础:数组 array (string),链表 linked list
    • 高级:栈 stack,队列 queue,双端队列 deque,集合 set,映射 map (hash or map),etc
  • 二维:
    • 基础:树 tree,图 graph
    • 高级:二叉搜索树 binary search tree (red-black tree,AVL),堆 heap,并查集 disjoint set,字典树 Trie,etc
  • 特殊:
    • 位运算 Bitwise,布隆过滤器 BloomFilter
    • LRU Cache

    https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/09/0f430b128ada4.png

算法

  • if-else,switch ——> branch
  • for,while loop ——> literation
  • 递归 Recursion (Divide & Conquer ,Backtrace)

所有高级算法或数据结构最后都会转换成以上三种

  • 搜索 Search:深度优先搜索 Depth first search, 广度优先搜索 Breadth first search,A*,etc

  • 动态规划 Dynamic Programming

  • 二分查找 Binary Search

  • 贪心 Greedy

  • 数学 Math,几何 Geometry

    https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/09/29f740cc6d689.png

    职业化运动

  • 基本功是区别业余和职业化选手的根本

  • 基础动作的分解训练和反复练习 ——> 最大的误区

Deliberate Practicing

  • 刻意练习 —— 过遍数(五毒神掌)
  • 练习缺陷、弱点地方

    Feedback

  • 即时反馈

  • 主动型反馈(自己去找)
    • 高手代码(Github,Leetcode,etc)
    • 第一视角直播
  • 被动式反馈(高手给你指点)
    • code review

切题四件套

  • Clarification
  • Possible Solutions
    • compare (time/space)
    • optimal (加强)
  • Coding(多写)
  • Test cases

五毒神掌

第一遍

  • 五分钟:读题 + 思考
  • 直接看解法:多看几种,比较解法优劣
  • 背诵、默写好的解法

第二遍

  • 马上自己写 ——> Leetcode提交
  • 多种解法比较、体会 ——> 优化!

第三遍

  • 过了一天后,再重复做题
  • 不同解法的熟练程度——>专项练习

第四遍

  • 过了一周后:反复回来练习相同的题目

第五遍

  • 面试前一周恢复性训练

小结

  • 职业训练:拆分知识点、刻意练习、反馈
  • 五步刷题法
  • 做算法题最大的误区:只做一遍

训练准备和复杂度分析

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

  • 上国际站看解答

‘’自顶向下‘’的编程方式

时间复杂度和空间复杂度

Big O notation

  • O(1):Constant Complexity 常数复杂度
  • O(log n):Logarithmic Complexity 对数复杂度
  • O(n):Linear Complexity 线性时间复杂度
  • O(n^2):N Square Complexity 平方
  • O(n^3):N Square Complexity 立方
  • O(2^n):Exponential Growth 指数
  • O(n!):Factorial 阶乘

注意:只看最高复杂度的运算

O(1)

# 看代码执行了1次
n = 1000
print(n) # 不管n为多少,print只执行一次

# 代码执行了三次,O(3),还是O(1)
m = 1000
print(m)
print(m)
print(m)

O(N)

# 代码执行了n次
for i in range(n):
    print('执行了:',i)

O(N^2)

for i in range(n):
    for j in range(m):
        print('执行了:',i+j)

O(log(n))

for i*i in range(n):
    print(i)

O(k^n):

def fib(n):
    if n <= 2 :
        return n
    else:
        return fib(n-1) + fib(n-2)

https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/10/54e68c8a3cb48.png

计算:1+2+…+n:

  • 方法一:
    # O(n)
    y = 0
    for i in range(1,n+1):
      y += i
    
  • 方法二:
    python
    # O(1)
    y = n * (n+1) / 2

更复杂的情况:递归

试着画出递归树(状态树)

Fib:0,1,1,2,3,5,8,13,21,…

  • F(n) = F(n-1) + F(n-2)

  • 最简单的写法,直接用递归

    def fib(n):
      if n <= 2:
          return n
      return fib(n-1)+fib(n-2)
    

    https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/10/0bba7e118e90d.jpg

    • 两个’灾难’:
      1. 每展开一层,运行的节点数就是上层的两倍,按指数级递增
      2. 存在重复计算的节点

Master Theorem

主定理

https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/10/ea5a32bf821d6.png

  • 一维数组二分查找:每次排除一半,故为O(log n)
  • 二叉树的遍历:可以理解成每个节点被访问且仅访问一次,故为O(n)
  • 二维矩阵的二分查找:O(n)
  • 归并排序:O(n logn)

思考

  1. 二叉树遍历:前序、中序、后序的时间复杂度是多少?
  • O(n)
  1. 图的遍历:时间复杂度是多少?
  • O(n)
  1. 搜索算法:DFS、BFS的时间复杂度是多少?
  • O(n)

    1-3中因为每个节点访问且只访问一次

  1. 二分查找:时间复杂度是多少?
  • O(log n)

数组、链表、跳表的基本实现和特性

哈希表、映射、集合

Hash table

  • 哈希表(Hash table),也叫散列表,是根据关键码值(Keyvalue)而直接进行访问的数据结构。
  • 它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
  • 这个映射函数叫作散列函数(Hash Function),存放记录的数组叫作哈希表(或散列表)

    Python – Hash Table

工程实践

  • 电话号码簿
  • 用户信息表
  • 缓存(LRU Cache)
  • 键值对存储(Redis)

Hash Function

https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/28/0f10a0d4703e1.jpg

好的哈希函数可以让数值尽量分散,不会出现哈希碰撞

Hash Collisions

https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/28/8c73175e18b3b.jpg

  • 发生哈希碰撞解决办法就是在碰撞的地方存一个链表——拉链式解决冲突法

  • Hash表查询O(1),最坏发生碰撞,退化为O(n)

https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/28/66b990abbb2e9.jpg

复杂度分析

https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/28/163fb8ed82104.jpg

Map、Set

  • Map : key-value对,key不重复
  • Set : 不重复元素的集合

廖雪峰:使用dict和set

list_x = [1,2,3,4]

map_x = {
    'jack':100,
    '张三':80,
    'selina':90,
    ...
}

set_x = {'jack','selina','Andy'}
set_y = set(['jack','selina','jack'])

要会去查看Python实现的源代码

复杂度分析

https://kanghaov-img-1256185664.file.myqcloud.com/2019/10/28/b4f583f97102d.jpg

Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://kanghaov.com/428.html
没有标签
首页      算法笔记      算法知识      极客时间-算法训练营随堂笔记
https://secure.gravatar.com/avatar/9fd8359b8faa6f7789f9623ba6041e4a?s=256&d=identicon&r=g

kanghaov

文章作者

发表评论

textsms
account_circle
email

Nemo

极客时间-算法训练营随堂笔记
数据结构与算法总览 精通一个领域 Chunk it up 切碎知识点 庖丁解牛 脉络链接 Deliberate Practicing 刻意练习 Feedback 反馈 数据结构 一维: 基础:数组 array (string),…
扫描二维码继续阅读
2019-10-27