LeetCode 403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog’s last jump was k units, then its next jump must be either k – 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

思路:这个题目可以看作是动态规划。青蛙的一个状态可以表示为{当前的k,当前的位置(可以用stone的索引表示)},最初的时候状态就是{ 1, 0 }。在某一个状态下,青蛙可以尝试向前移动{k-1, k, k+1}步,如果能成功跳到那就进入了下一个状态。要注意的是这种状态的遍历是有重复的,所以需要一个东西记录已经尝试过(当然是尝试失败的,不然直接return true)的状态们,不然很容易超时。



654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.



C++ Template: Handle mutual (circular) dependencies

Sometimes we have two classes that need to call each other’s somewhat function, for example

but as you can see A depends on B’s type to initialize and vise versa. If we declare the types as above we’ll not get a chance to create any instance.

There are at least two ways to resolve the issue.

I.Template template

A quick introduction about template template can be found here.

Declare either of {A, B} with template of template which accepts the other’s template argument.

II.Type traits

The other resolution is create a type trait struct which acts like a bridge that links the type of each other.


Some of the best answers to LeetCode questions

Here I gathered some of (what I thought are) best answers to LeetCode questions:

  • https://leetcode.com/problems/wiggle-subsequence/discuss/84887/C++-0ms-O(N)-dynamic-programming-solution
    • an O(n) solution
  • https://leetcode.com/problems/trapping-rain-water/description/
    • an O(n) solution of a similar (but harder) question, found in the book <算法竞赛入门经典(第二版) pp249例8-18
    • basic idea is to find a maximal height which can reserve the water for each position i, if the max height equals to the unit then no rain can be collected at i
    • (vice versa, from right to left)

LeetCode 89. Gray Code

Divide and conquer!

Add a leading 0 or 1 bit to your existing results so here comes two sub-results: 0{xxxxx} and 1{xxxxx}. How to merge them? Just keep the first sub group and append the second group items reversely so that there is only a 1-bit difference between the end of group 0 and “start” of group 2.


LeetCode 402. Remove K Digits


如果直接用DFS做的话轻轻松松就会stack overflow。


贪心法之所以能用是因为我们去尽量保证了a1<a2< …< x< y,如果这些个数字里要选一个删掉的话,肯定是删掉y带来的结果最好。


LeetCode 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Example 2:

Example 3:


  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.



The solution is to build a directed map and find the topological ordering of the characters. Once the map is built, we can always find the “terminal” character which has no succeeding, i.e. the out-degree of that node would be zero. The we remove the character (the node and its edges) from the map and try to find the next such character, so on so forth.

For example,  the map built will be:



LeetCode 611. Valid Triangle Number



时间复杂度是O(n*log(n) + n^2) = O(n^2)



LeetCode 523. Continuous Subarray Sum


这道题跟https://leetcode.com/problems/subarray-sum-equals-k/description/ 其实是很像的,但本题的特点就是corner case非常多…