Word2Vec代码阅读
From tensorflow/tutorials
Posts by Collection
essays
Code Search Net说明
Overview
DeepWalk 代码阅读
main.py
主函数，执行入口
动态图表示学习综述
图表示学习，将节点从高维表示空间映射到低维向量空间，得到表示向量，作用于后续的分类、预测等任务。
然而在真实场景中，图是动态变化的（或者说流式存在的），因此研究动态图的表示学习是很有必要的，也是近些年的一个热门研究问题。
solutions
Back tracking
递归 / 回溯算法
Binary Search
二分查找的问题，往往关键是定义需要查找的结构是什么，且结构必须是排序的，然后查找过程是简单的，即通过三个指针left、right和middle迭代直至收敛。
Binary Tree
Binary Search Tree
Depth First Search (DFS) / Breadth First Search
753. Cracking the Safe
There is a box protected by a password. The password is a sequence of n digits where each digit can be one of the first k digits 0, 1, …, k-1.
Divide and Conquer
215. Kth Largest Element in an Array
Dynamic Programing
418. Sentence Screen Fitting
Graph
Topogolical Sort
Greedy Algorithm
1007. Minimum Domino Rotations For Equal Row
#45. Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
K Smallest
- Kth Largest Element in an Array：二分查找，类似快排
- Find K Closest Elements：二分查找（索引）
- Kth Smallest Element in a Sorted Matrix: 二分查找（值），二分查找（索引，逐行判定）
- Find K-th Smallest Pair Distance：二分查找（值），双指针判定
- Find K Pairs with Smallest Sums：堆，转换为merge k list
Graph
138. Copy List with Random Pointer
#32. Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Math
最小距离
Other
73. Set Matrix Zeroes
#33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
Segment Tree
NOTE
Sliding Window
滑动窗口的最大值/最小值数组
生成滑动窗口的最大值/最小值数组，可以直接作为题目，也可以间接作为预处理方法。 时间复杂度为$O(n)$。
Stack / Heap / Queue
Queue
String
271. Encode and Decode Strings
Subarray / Submatrix with Target
和子数组、子矩阵以及给定目标值相关的题型。
- 最简单的题型，返回子数组和为K的数量（560）/ 最大长度（325）：前缀和+哈希，时间复杂度O(n)
- 扩展到二维矩阵情况（1074）：在某一维上用sliding window的方法固定一个区间，转换为一维情况，注意需要提前对行之和进行前缀和预处理，时间复杂度O(m^2n)
- 扩展到子矩阵和不大于K的最大和：不能直接用哈希，而是采用有序结构存储+二分查找的方法，比如采用
set结构，对应insert和lower_bound函数，时间复杂度为O(m^2nlogn)
Trie
NOTE
Two Pointers
777. Swap Adjacent in LR String
Union Find
并查集，主要是两个函数unoin和find，并且可以分别在两个函数中加入优化：重量权衡分配和路径压缩。