Skip to content

Instantly share code, notes, and snippets.

View chocoluffy's full-sized avatar
🎯
Focusing

Luffy Yu chocoluffy

🎯
Focusing
View GitHub Profile
@chocoluffy
chocoluffy / note.md
Created September 26, 2018 01:05
[【Union-Find】并查集的常见用法]
@chocoluffy
chocoluffy / note.md
Created September 25, 2018 21:01
[【DFS】DFS总结] #dfs #review

递归是相似的。 注意在递归先后的操作造成的区别。

@chocoluffy
chocoluffy / solution.py
Last active September 25, 2018 15:21
[【DFS\BFS\Union-Find】friends cycle] #dfs #bfs #union_find #python
"""
DFS version straigtforward.
BFS version:
for i in range(n):
if not visited:
add to queue.
while queue not empty:
for loop append all connected points to queue.
@chocoluffy
chocoluffy / solution.py
Last active September 17, 2018 02:00
[【DP】longest palindrome] #string #palindrome #dp
"""
dp思路, T: O(n^2), S: O(n^2), 总结一下这一类型叫做中心往边缘扩散类型。特别适用于一种情况下的动态规划:每个问题和其周围边缘的子问题相关。转换为子问题的方式是向四周扩散或者向中心缩小。
"""
class Solution(object):
def longestPalindrome(self, s):
if len(s) == 0:
return ""
if len(s) == 1:
return s
max_len = 1
@chocoluffy
chocoluffy / solution.py
Created September 16, 2018 10:54
[【DP\BFS】word break] #dp #bfs #string
"""
'leetcode'
=>
'leetcode '
when i points the last padding position.
dp[i]: if everything before i position can be contained in dictionary.
@chocoluffy
chocoluffy / note.md
Last active September 15, 2018 15:27
[【review】机器学习常见面试知识点] #review #machine_learning

New Topic:

Encoder-Decoder Network

A potential issue with this encoder–decoder approach is that a neural network needs to be able to compress all the necessary information of a source sentence into a fixed-length vector. This may make it difficult for the neural network to cope with long sentences, especially those that are longer than the sentences in the training corpus.

Attention

Each time the proposed model generates a word in a translation, it (soft-)searches for a set of positions in a source sentence where the most relevant information is concentrated. The model then predicts a target word based on the context vectors associated with these source positions and all the previous generated target words.

… it encodes the input sentence into a sequence of vectors and chooses a subset of these vectors adaptively while decoding the translation. This frees a neural translation model from having to squash all the information of a source sentence, regardless of its length, into a fixed-length vector.

@chocoluffy
chocoluffy / solution.py
Last active September 12, 2018 02:08
[【DP】matrix chain multiplication ~ burst balloons] #dp
"""
We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:
(ABC)D = (AB)(CD) = A(BCD) = ....
However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Clearly the first parenthesization requires less number of operations.
@chocoluffy
chocoluffy / solution.py
Last active September 9, 2018 19:36
[【DFS】graph relations find one node every nodes follows] #python #dfs #graph
"""
Input:
3
3
1 2 2 1 2 3
N people
M pairs of following relations
M pairs of (i, j), meaning i follows j.
@chocoluffy
chocoluffy / solution.py
Last active September 6, 2018 15:49
[【python】find triplets on three arrays] #python
"""
Output Format
Print an integer representing the number of distinct triplets.
Sample Input 0
3 2 3
1 3 5
2 3
@chocoluffy
chocoluffy / note.md
Created September 6, 2018 01:49
[【DFS on Matrix】longest increasing path in matrix, topological sort] #dfs #matrix #dp

这个帖子主要记录,如果将matrix问题转化为graph的问题,并结合topological sort来解决:

  • 遍历图中每个点,找到每个点的outgoing degree,和其neighbor相比较。

相关问题: