C++Python Greedy DP速解Leetcode 1014 Best Sightseeing Pair算是貪婪演算還是動態規劃,其實都算解法類似Kadane演算法。
-----------
Leetcode 1014. Best Sightseeing Pair is considered greedy algorithm or dynamic programming, but it is actually both. It's similar to Kadane's Algorithm
C++BFS走訪 level排序與DFS cycle長度計數解Leetcode 2471 Minimum Number of Operations to Sort a Binary Tree by Level
解圖論問題Leetcode 2471. Minimum Number of Operations to Sort a Binary Tree by Level,這不算稀奇,但當中還用到置換群(permutation group)的概念就比較特別。
------
Solve the graph theory problem Leetcode 2471. Minimum Number of Operations to Sort a Binary Tree by Level. This is not unusual, but the concept of permutation group is also used in it, which is quite special.
Python C++使用prefix sum mod k + hash map解Leetcode523 Continuous Subarray Sum。模k,前綴和 (mod k) 總共有 k 個可能,為 0,1,...k-1。
對於這個條件 1 less eq nums.length less eq 10^5 O(n^2) 解可能會導致 TLE。
對於此條件 1 less leq k less eq 2^31 - 1,陣列版本解決方案可能會導致 MLE。
然而,注意使用前綴和 mod k 的hash映射是一個有效解法。
modulo k there are 0,1,...k-1 totally k possible for prefix sum (mod k).
For this constraint 1 less eq nums.length less eq 10^5 an O(n^2) solution may lead to TLE.
For this constraint 1 less leq k less eq 2^31 - 1, an array version solution might lead to MLE.
Leetcode問題1642. Furthest Building You Can Reach也是用Greedy演算,有梯子、有磚塊,要訣就是高度差大的用梯子,高度差小的用磚塊,至於容器,C++可用priority_queue或用make_heap,當然也可用multiset,用heap的解答當然很快速,千萬不要誤入歧途採用DP動態規劃,先看constraints就知。
python C++遞迴邁向dp動態規劃解Leetcode 1143 Longest Common Subsequence. LCS之類的問題其實跟 DNA 序列的比對問題密切關聯。非常經典的DP動態規劃問題,有的人會TLE,請注意不是只設cache就好,尤其是C++,字串不要call-by-value