LeBlanc’s law: "Later equals never".
Summary In this post, I will introduce some problems related to palindrome and dynamic programming. A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome. OJ Details LC 1278 Palindrome Partitioning III Difficulty: 6-7 points Given a string s containing lowercase letters and an integer k….
Summary In this post, I will introduce some problems using the merge sort technique. These problems often ask, for an element at index , how many are there which satisfies a formula. OJ Details The Master Theorem If is of complexity , then is of complexity So in these problems, a key point…
Summary Some problems require returning real result not just a number. To do this, a good method is that we create another table to store the optimal choices we made on each state. To return any optimal result, the choice table will be as large as the alg table. The result can we achieved by…
Summary In this post, I will introduce some common techniques related to divisors and factors. Details Number of Divisors GCD
Summary In this post, I will introduce some problems related to KMP. OJ Details Pi is the length of the longest prefix of substring , such that this prefix is also the suffix of . Note that this prefix excludes itself. By the definition, we have . For example, we have, Please refer…
Summary In this post, I will introduce problems related to bit manipulation. Before that, you may want to learn the std::bitset<> class template. Detials LC 1386. Cinema Seat Allocation The problem is not difficult. But it is tricky to write a clean code. The hint is that all valid patterns can be presented by the…
Summary I will introduce some pure Monotonic Queue problems in this post. Details Sword to Offers Problem 59 Max Queue Mantain a special queue so that you can do max_value, push_back, and pop_front in amortized O(1) time. LC 456. 132 Pattern It is not difficult to get an O(n^2) or even an O(nlogn) solution: we…
Summary In this post, I will introduce several templates for the Segment Tree. Compared to the binary index tree, segment tree is easy to understand, though the codes are longer. I will not introduce 2D Segment Tree in this post. Some OJ problems are listed below. LC 1157: query range majority; update single node; LC…
Summary Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed. Details Minimum Cost to Merge Stones I There are N…