递归是相似的。 注意在递归先后的操作造成的区别。
""" | |
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. |
""" | |
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 |
""" | |
'leetcode' | |
=> | |
'leetcode ' | |
when i points the last padding position. | |
dp[i]: if everything before i position can be contained in dictionary. |
New Topic:
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.
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.
""" | |
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. |
""" | |
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. |
""" | |
Output Format | |
Print an integer representing the number of distinct triplets. | |
Sample Input 0 | |
3 2 3 | |
1 3 5 | |
2 3 |
这个帖子主要记录,如果将matrix问题转化为graph的问题,并结合topological sort来解决:
- 遍历图中每个点,找到每个点的outgoing degree,和其neighbor相比较。
相关问题: