百面机器学习笔记

包括机器学习和算法2部分 课程地址

Week 1

机器学习

分类算法

• 逻辑回归
  • 极大似然估计
    • 似然：通过样本猜测总体
  • 梯度下降法推导
  • 逻辑回归推导
    • 在线性回归外层套一个sigmoid
• 决策树
  • ID3 信息增益 仅离散属性
  • C4.5 信息增益比 = 信息增益/划分前熵 连续值
  • CART Gini指数（集合的不确定性） 仅二叉树
  • 剪枝（防止过拟合）
    • 预剪枝
    • 后剪枝（剪掉叶结点较少的分支）

算法

• 快速排序
  • 挖坑法（双指针）
  • 指针交换法（交换数据）
• 堆排序
• 双指针
  • 对撞指针
  • 快慢指针
  • 滑动窗口

题目

算法刷题重点题型

• [x] 双指针（167）：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

• [ ] 快速选择、堆排序、归并排序（215）：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

• [ ] 桶排序（347）：https://leetcode-cn.com/problems/top-k-frequent-elements

• [x] 滑动窗口（209）：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

  • 长度最小的连续子数组

• [x] 滑动窗口（438）：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

  • 找到字符串中所有字母异位词

• [ ] 滑动窗口（76）：https://leetcode-cn.com/problems/minimum-window-substring/

  • 最小覆盖子串

算法刷题课后作业

• [ ] 数组中重复的数字：https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8

• [ ] 构建乘积数组：https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46

• [ ] 二维数组中的查找：https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e

Week 2

机器学习

• SVM
  • 线性可分
  • 超平面 最大间隔超平面（最近的样本点到平面的距离）
  • 支持向量（距离超平面最近的点）
  • SVM的最优化问题
  • 对偶问题
    • 构造拉格朗日函数
    • （强对偶关系）
    • KKT约束条件（强对偶性的充要条件）
    • SMO（序列最小优化）算法求
  • 软间隔（允许个别样本点出现在间隔带里）
    • 松弛变量
  • 核函数（线性不可分）
    • 非线性SVM（映射到更高维度）
    • 减少映射的计算量
    • 常用核函数
      • 线性核函数
      • 多项式核（不平稳，数据已归一化）
      • RBF核（高斯核）（最常用）
• 降维 PCA和LDA
  • PCA
    • 最大化投影的方差
  • LDA（Linear Discriminant Analysis）有监督
    • 最大化类间距离以及最小化类内距离

算法

• KMP算法
  • 字符串匹配
  • 空间换时间
  • 部分匹配表PMT：记录字符串前缀集合和后缀集合交集中最长元素长度（子字符串p）
    • 向右移动一位得到next数组，0位填-1
    • 根据p求解next
• 二分搜索
  • while left <= right if right = str.len - 1
  • mid = lower + (upper - lower) // 2 防止溢出
  • 目标有多个重复
    • 最左侧
      • left = 0 right = str.len # [)
      • while left < right # [left, left)
      • mid = (left + right) // 2
      • if str[mid] == target: right = mid
      • if str[mid] < target: left = mid + 1
      • if str[mid] > target: right = mid
      • return left
    • 最右侧
      • left = 0 right = str.len # [)
      • while left < right # [right, right)
      • mid = (left + right) // 2
      • if str[mid] == target: left = mid + 1
      • if str[mid] < target: left = mid + 1
      • if str[mid] > target: right = mid
      • return left - 1
• 哈希表

题目

算法刷题重点题型

• [ ] 替换空格：https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423

• [ ] 正则表达式匹配：https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c

• [ ] 表示数值的字符串：https://www.nowcoder.com/practice/6f8c901d091949a5837e24bb82a731f2

• [ ] 字符流中第一个不重复的字符：https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720

• [ ] 二分搜索（69）：https://leetcode-cn.com/problems/sqrtx/

• [ ] 哈希表（1）：https://leetcode-cn.com/problems/two-sum/

• [ ] 旋转数组的最小数字：https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

算法刷题课后作业

• [ ] 左旋转字符串：https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec

• [ ] 字符串的排列：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7

• [ ] 第一个只出现一次的字符：https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c

• [ ] 在排序数组中查找元素的第一个和最后一个位置（34）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

• [ ] 找到 K 个最接近的元素（658）：https://leetcode-cn.com/problems/find-k-closest-elements/

• [ ] 长度最小的子数组（209）：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

• [ ] 有序矩阵中第 K 小的元素（378）：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

Week 3

机器学习

• K-means
  • EM（Expectation Maximum）算法
  • 收敛性证明

算法

• 虚拟头结点
• 删除链表中重复的结点
  • 3指针：基准、快、慢
• 链表中环的入口结点
  • 哈希表
  • 快慢指针
• 栈和队列
  • 由链表实现 [].pop(0) [].pop()

题目

算法刷题重点题型

• [ ] 删除链表中重复的结点：https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef

• [ ] 链表中环的入口结点：https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

• [ ] 用两个栈实现队列：https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6

• [ ] 滑动窗口的最大值：https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788

算法刷题课后作业

• [ ] 从尾到头打印链表：https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035

• [ ] 相交链表（160）：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

• [ ] 用栈实现队列（232）：https://leetcode-cn.com/problems/implement-queue-using-stacks/

Week 4

机器学习

• HMM
  • 概率模型
    • 生成模型 联合概率分布
    • 判别模型 条件概率分布
  • 基本假设
    • 齐次马尔可夫假设
    • 观测独立性检测
  • 基本问题
    • 概率计算：计算观测值的概率
      • 直接计算
      • 前向、后向算法（DP）
    • 预测/解码：通过观测序列求状态序列
      • 维特比算法（DP）Viterbi
    • 学习/训练：计算
      • 有监督
      • 无监督：仅观测序列
        • Baum-Welch算法
    • 实例
      • from hmmlearn import hmm
• CRF 条件随机场
  • 基础概念
    • 概率有向图模型 HMM 贝叶斯网络
    • 概率无向图模型 马尔可夫网络 马尔可夫随机场（MRF）（生成式模型）
    • 团Clique：图中节点的子集，其中任意2个节点有边直接连接
    • 势函数：非负实函数
    • Hammersley-Clifford定理
      • MRF表达为正概率分布
    • 分离 分离集
    • 特征函数
  • CRF 判别式模型 有条件的MRF
    • 线性链CRF
      • 指数势函数
    • 三个问题
      • 概率计算
      • 预测
      • 学习

算法

• DFS和BFS
  • BFS (279)
    • 队列
    • 邻接表
    • 临界矩阵
  • DFS (695)
    • 递归
    • 栈-非递归
    • 树的前序遍历
• 最短路径
  • Dijkstra (743)
    • 1点到其它，每次确定一个结点
    • 记录上一个结点可得到路径
    • 权值非负
    • 稀疏图
  • Bellman-Ford
    • 权值可以为负（负环）
    • 循环遍历所有边，直到所有值不改变（最多N-1）
• 最小生成树 图的最小连通子图
  • 并查集 用集合中的一个元素代表集合（帮会）(684)
  • Kruskal (1135)
    • 对边排序，从小到大并查集
  • Prim
    • 从某顶点开始，每次吸纳1个结点
• 二叉树的遍历（stack非递归较复杂）
  • 前序
  • 中序
  • 后序
  • 层次（queue）
• 二叉搜索树和平衡二叉树
  • |左右子树高度之差|<=1
  • 搜索
  • 插入
    • 平衡（只调整失衡的第一个结点）
      • 左-左
        • 右旋
      • 右-右
      • 左-右
        • 左旋（产生左-左）->右旋
      • 右-左
  • 删除
    • 结点不存在
    • 叶子节点
    • 有1个孩子
    • 有2个孩子
    • 平衡

题目

算法刷题重点题型

树类问题：

• [ ] 平衡二叉树（110）：https://leetcode-cn.com/problems/balanced-binary-tree

• [ ] 找树左下角的值（513）：https://leetcode-cn.com/problems/find-bottom-left-tree-value

• [ ] 二叉树展开为链表（114）：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

• [x] 二叉搜索树中第K小的元素（230）：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

• [ ] 实现 Trie (前缀树)（208）：https://leetcode-cn.com/problems/implement-trie-prefix-tree

• [ ] 序列化二叉树：https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84

• [ ] 重建二叉树：https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

图类问题：

• [ ] 判断二分图（785）：https://leetcode-cn.com/problems/is-graph-bipartite

• [ ] 拓扑排序（207）：https://leetcode-cn.com/problems/course-schedule

• [ ] 并查集（684）：https://leetcode-cn.com/problems/redundant-connection

• [ ] 岛屿的最大面积（695）：https://leetcode-cn.com/problems/max-area-of-island/

  • DFS或BFS

算法刷题课后作业

• [ ] 对称的二叉树：https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb

• [ ] 把二叉树打印成多行：https://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288

• [ ] 二叉树的下一个结点：https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

• [ ] 数据流中的中位数：https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

• [ ] 二叉搜索树的第k个结点：https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a

• [ ] 按之字形顺序打印二叉树：https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

• [ ] 完全平方数（279）：https://leetcode-cn.com/problems/perfect-squares/

  • 从n到0每个数字表示1个结点，相差1个完全平方数的结点有边，找0到n的最短路径

• [ ] 电话号码的字母组合（17）：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

Week 5

机器学习

• 前向神经网络
  • 前向传播
  • 反向传播
• 序列数据中常用的循环神经网络
  • RNN
  • GRU和LSTM

算法

• 递归
  • 记忆化搜索
  • 跳台阶 (509)
  • 变态跳台阶 (牛客)
• 回溯法（反向递归树）
  • 递归一定会发生回溯 暴力搜索
  • 全排列 (46) 恢复标志位
  • 机器人运动范围 (面试题13)
• 动态规划DP
  • 保存子问题的答案
  • 自下而上（与记忆化搜索相反）
  • 0/1背包问题 (416. 分割等和子集)
    • 挑选的物品只有一个
    • 该物品可选可不选
      • 状态
    • dp[i][j] 挑选第i个物品放入j容量的最大价值
      • 状态转移方程
      • 空间：$O(nC)O(2C)O(C)$（倒序更新）
      • 时间：$O(nC)$ 物品数量背包容量
  • 最长上升子序列LIS (300)
    • dp[i] 以第i个数字结尾的LIS长度
    • dp[i] = max([dp[j] + 1 for j in range(i) if nums[i] > nums[j]] + [1])
  • 最长公共子序列LCS (1143)
    • dp[i][j] s1的前i个字符和s2的前j的字符的LCS的大小
    • dp[i][j] = dp[i-1][j-1]+1 s1[i] == s2[j]
    • dp[i][j] = max(dp[i-1][j], dp[i][j-1]) s1[i] != s2[j]

题目

算法刷题重点题型

递归、回溯问题：

• [ ] 斐波那契数列：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

• [ ] 跳台阶：https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

• [ ] 变态跳台阶：https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387

• [x] 全排列（46）：https://leetcode-cn.com/problems/permutations/

• [ ] 机器人的运动范围：https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8

动态规划问题：

• [x] 斐波那契数列（用DP方法再写一下）（70）：https://leetcode-cn.com/problems/climbing-stairs

• [x] 0-1 背包（416）：https://leetcode-cn.com/problems/partition-equal-subset-sum

• [x] 最长递增子序列（300）：https://leetcode-cn.com/problems/longest-increasing-subsequence

• [x] 最长公共子序列（1143）：https://leetcode-cn.com/problems/longest-common-subsequence/

算法刷题课后作业

• [ ] 矩阵中的路径：https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc

• [ ] 矩形覆盖：https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6

• [ ] 矩阵路径（64）：https://leetcode-cn.com/problems/minimum-path-sum

• [ ] 股票交易（309）：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

• [ ] 字符串编辑（583）：https://leetcode-cn.com/problems/delete-operation-for-two-strings

• [ ] 数组区间（303）：https://leetcode-cn.com/problems/range-sum-query-immutable

• [ ] 分割整数（343）：https://leetcode-cn.com/problems/integer-break

Week 6

机器学习

• 集成学习
  • Bagging
    • 随机森林
  • Boosting
    • 梯度提升树 GBDT
      • 残差：真实值 - 预测值
      • 基分类器：回归树CART
      • 加法模型：决策树相加
        • 求解：前向分布算法
      • 用负梯度代替残差
        • 泰勒一阶展开
      • 问题（不同的损失函数）
        • 二分类
          • 对数损失函数
          • 初始值求解
          • Newton-Raphson一步迭代
        • 多分类
          • 交叉熵损失函数
        • 回归
          • huber损失函数
          • 平方损失函数
    • XGBoost
      • 预备知识
        • 泰勒二阶展开
        • 结构风险极小化：正则化
      • 结构分