动态规划

from 算法导论（CLRS）

动态规划算法通常用于求解最优值，一般步骤如下：

1. 刻画最优解结构
2. 递归地定义最优解的值
3. 自底向上计算最优解的值
4. 利用计算出的信息构造最优解（构造解本身，可选）

分治策略

from 算法导论（CLRS）

分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：

• 分解：将问题划分为形式相同、规模更小的子问题。
• 解决：递归求解子问题。
• 合并：将子问题的解组合成原问题的解。

递归式与分治法是紧密相关的，使用递归式可以很自然地刻画分治算法的运行时间。一个递归式就是一个等式或不等式，它通过更小的输入上的函数值来描述一个 函数，例如：

本章将介绍三种求解递归式的方法：

• 代入法：猜测一个界，利用数学归纳法证明该界正确。
• 递归树法：将递归式转换成一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
• 主方法：求解形如 $T(n) = aT(n/b) + f(n)$ 的递归式的界。

在声明、求解递归式时，我们常常忽略向下取整、向上取整及边界条件等细节。

最小生成树

from 算法导论（CLRS）

在本章中，我们将讨论两种最小生成树的贪心算法 —— Kruskal 算法和 Prim 算法。对于最小生成树问题来说，我们可以证明，某些贪心策略确实能够找到一个全局最优的解决方案。

自然语言处理与深度学习（1）

—— CS224n 2019年冬 课程笔记

第一讲 词向量（I）

关键词：Natural Language Processing, Word Vectors, Singular Value Decomposition (SVD), Skip-gram, Continuous Bag of Words (CBOW), Negative Sampling, Hierarchical Softmax, Word2Vec

本讲首先介绍自然语言护理与自然语言处理面对的问题，之后将讨论用以将词表示为向量的相关概念，最后，我们将讨论设计词向量的常见方法。

LeetCode 题解（5）：二叉树-遍历

learn from cyc2018 and LeetCode

1
2
3
4
5
6
7

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

二叉树的遍历方式有：

• 广度遍历：层次遍历
• 深度遍历：前序、中序、后序遍历

LeetCode 题解（4）：二叉树-递归法

learn from cyc2018 and LeetCode

1
2
3
4
5
6
7

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

类似于链表，二叉树的很多问题也可以利用递归的方法简单地实现。

LeetCode 题解（3）：链表

learn from cyc2018 and LeetCode

1
2
3
4
5
6

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

LeetCode 题解（2）：排序

learn from cyc2018 and LeetCode

利用随机化快速排序的 RANDOMIZED_PARTITION 求解 Kth Element 问题。参考材料：CLRS笔记：快速排序

快速排序

快速排序是一种最坏情况时间复杂度为 $\Theta(n^2)$ 的排序算法，但是快速排序在实际排序应用中通常是最好的选择，因为它的平均性能非常好，期望时间复杂度是 $\Theta(n\lg n) $。

LeetCode 题解（1）：双指针法

learn from cyc2018 and LeetCode

双指针法指的是：在遍历对象的过程中，不使用单个指针进行访问，而是用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。双指针问题的本质是由于两个或者多个元素有相互作用或者相关联。