Press "Enter" to skip to content

Posts published in “SP”

Fast Power for DP SP20

Iterative DP usually takes O(n) to compute dp[n] from dp[0], we could do better if the problem can be written as matrix multiplication. With fast power, dp[n] can be computed in O(logn)

KMP Algorithm SP19

KMP Algorithm, KMP 字符串搜索算法

Time complexity: O(m+n)
Space complexity: O(m)

Implementation

C++

Python3

Applications

LeetCode 28. strStr()

C++

LeetCode 459. Repeated Substring Pattern

C++

1392. Longest Happy Prefix

C++

花花酱 Minimum Spanning Tree (MST) 最小生成树 SP18

Prim’s Algorithm

Time complexity: O(ElogV)
Space complexity: O(V+E)

C++

Python

Kruskal’s Algorithm

Time complexity: O(ElogV)
Space complexity: O(V+E)

C++

Python

LeetCode 进入千题时代该如何刷题?



题目列表:https://bit.ly/2E8yBHq

总结一下:

  • 大家的刷题经验都比我丰富,找到最适合自己的方法就好了
  • 200~300题刷2-3边,至少100+小时的投入
  • 同一类型题目一起刷,总结规律和差异
  • 多看别人的(优秀)代码
  • 完整的手写实现,不要copy代码,增强肌肉记忆(视频中没提到)
  • 培养代码风格