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