很经典的题目,DP和单调队列的思想都有用到,在这里做一个总结吧。
分类: LeetCode OJ
[LeetCode]Remove Invalid Parentheses
设计了一个状态,即搜索到pos位置时结果是str并且左右括号个数分别是nl和nr,这个状态在搜索的时候很方便转移并且能即时判断结果的合理性,但是有一个缺点就是状态数目太多了,搜索的时候去重比较麻烦,并且不剪枝也会T。// 我不知道怎么会写出这么恶心的程序。
[LeetCode]Nim Game
4个石子,后手总会赢。如果石子个数不是4的整数倍,那么先手可以取走一部分石子(1, 2, 3)使得剩下的石子数目是4的整数倍,接下来的博弈中先手变后手,总会赢。
[LeetCode]Multiply Strings
Classical problem, try to finish it within 10 mins... // Coding 10 mins, debugging 5mins!!! It took me nearly 15 mins to solve it, time is so cruel...
[LeetCode]Find Peak Element
For a random index , compare
with its neighbor, one of the answer belongs to the interval that the bigger element belongs to too, and we can optimize our program based on this.
[LeetCode]Add Digits
Notice the result( number) of the numbers is a periodic sequence...
[LeetCode]Binary Tree Paths
Depth-First-Search..
[LeetCode]Search a 2D Matrix II
Here is a direct solution: keep narrowing the scope of matrix, and at the end, either the target doesn't belong to the matrix or the target appears in the scope's right-up corner as well as left-down corner.
[LeetCode]Valid Anagram
Count numbers...
[LeetCode]Sliding Window Maximum
The data structure we selected in this problem should satisfy at least two conditions: 1) monotonicity, which guarantees in every sliding window we could always get the max element; 2) FIFO, which ensures the problem could be solved in linear time.