LintCode 622. Frog Jump

http://www.lintcode.com/en/problem/frog-jump/


Suitable for the bottom-up DP approach:
the first jump must be 1 unit.
the other jumps can be multiple units.

That mean a if-else clause is needed inside the loop.
Then the multiple units call for a collection, and we don't want duplication, so a HashSet would be ideal.

There you go:

LeetCode 791. Custom Sort String - Weekly Contest 73

https://leetcode.com/contest/weekly-contest-73/problems/custom-sort-string/


First I tried to use lambda for Arrays.sort(T[]), but it doesn't work that way.

So I come up with 3 arrays of the length of 27 which covers all the chars.

the
count: char -> occurrence
map:   char -> i index
seq:     index i -> char

this way, you can easily assemble the answer.

From their sorted sequence, with given char and the respective occurrence. all within your reach in O(1).

That's crazily fast! So let's do it!

LeetCode 789. Escape The Ghosts - Weekly Contest 73

https://leetcode.com/contest/weekly-contest-73/problems/escape-the-ghosts/


Come to think of it, I realize no matter which location they are locating, the distance to the target is what really matters.

So naturally we come up with a helper function to getDistance,

then, naturally we will compare the distances and see if any ghosts are dangerously close.

That's it.

LeetCode 788. Rotated Digits - Weekly Contest 73

https://leetcode.com/contest/weekly-contest-73/problems/rotated-digits/

Quite Straight Forward,
in case of 25, 69 they change to something beautiful.
in case of 0, 1, 8, they just don't mean anything,
in case of the 3, 4, 7 they are pretty much deal breaker.

the conditions are messy so I speed them up with an array.

LintCode 89. k Sum

http://www.lintcode.com/en/problem/k-sum/

/**
 * dynamic programming
 * DP Elements:
 * 1. state:
 * dp ijt means the combinations, of picking j numbers, from the first i numbers. that sum to the t.
 *
 * 2. Init
 * dp 0j mean no number to pick, target 0 would meet, otherwise haha
 * dp i0 mean pick 0 numbers, same as above.
 *
 * 3. Func
 * dp ijt = no pick -> dp i - 1, j, t
 * pick   -> dp i - 1, j - 1, t - A[i]
 *
 * 4. Answer
 * dp len, k
 */

LintCode 154. Regular Expression Matching

http://www.lintcode.com/en/problem/regular-expression-matching/



A classic Google Problem.

A classic matching dp.

the Dynamic Programming Elements:

1. state
dp i, j means first i of A matching with first j of B.

2. Init
dp i, 0 -> i == 0;
dp 0, j -> isEmpty(j)

3. Func
dp i, j =
if(B.chatAt(j) == '*') {
  check if the Ai matches, then |= helper(i - 1, j)
  and always we can do without Bj, so |= helper(i, j - 2)
} else {
  Bj match Ai? then |= helper(i - 1, j - 1);
  else false;
}

4. Answer
dp m, n

PS: dp size m + 1 by n + 1.

LintCode 476. Stone Game

http://www.lintcode.com/en/problem/stone-game/


Game Theory problems are classified as DP problems.

And this is a classic one. Because there are two players gaming and so many possible moves,

that comes with a huge searching space with a lot of overlaps.

So overlaps must be eliminated by Memoization.

And let's see the 4 Elements of the DP:

1. initialization: (or termination)
dp[i][i] = 0;

2. transfer formula:
dp[i][j] = sum[i][j] + (for all the possible k) min(dp(i, k) + dp(k, j));

3. Result:
dp(0, length - 1);

LeetCode 780. Reaching Points - Weekly Contest 71

https://leetcode.com/contest/weekly-contest-71/problems/reaching-points/

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

LeetCode 781. Rabbits in Forest - Weekly Contest 71

https://leetcode.com/contest/weekly-contest-71/problems/rabbits-in-forest/

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

LeetCode 783. Minimum Distance Between BST Nodes - Weekly Contest 71

https://leetcode.com/contest/weekly-contest-71/problems/minimum-distance-between-bst-nodes/
Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

LintCode 401. Kth Smallest Number in Sorted Matrix

http://www.lintcode.com/en/problem/kth-smallest-number-in-sorted-matrix/



Find the kth smallest number in at row and column sorted matrix.
Example
Given k = 4 and a matrix:
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
return 5

LeetCode 779. K-th Symbol in Grammar - Weekly Contest 70

https://leetcode.com/contest/weekly-contest-70/problems/k-th-symbol-in-grammar/