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:

	public class Solution {
	/*
	* @param stones: a list of stones' positions in sorted ascending order
	* @return: true if the frog is able to cross the river or false
	*/
	boolean canCross(int[] stones) {
	// filter abnormal cases
	if (stones == null || stones.length == 0) {
	return true;
	}
	int len = stones.length;
	boolean[] dp = new boolean[len];
	ArrayList<HashSet<Integer>> ksList = new ArrayList<>(len + 1);
	for (int i = 0; i < len; i++) {
	ksList.add(new HashSet<>());
	}
	for (int i = 0; i < len; i++) {
	if (i == 0) {
	dp[0] = true;
	} else {
	if (i == 1) {
	if (stones[1] - stones[0] == 1) {
	dp[1] = true;
	ksList.get(1).add(1);
	} else {
	return false;
	}
	}
	for (int to = i + 1; to < len; to++) {
	int require = stones[to] - stones[i];
	if (ksList.get(i).contains(require - 1) || ksList.get(i).contains(require) || ksList.get(i).contains(require + 1)) {
	dp[to] = true;
	ksList.get(to).add(require);
	}
	}
	}
	}
	// return the final result
	return dp[len - 1];
	}
	}

view raw LintCode 622. Frog Jump - LintCode.java hosted with ❤ by GitHub

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!

	class Solution {
	String customSortString(String S, String T) {
	// filter abnormal cases
	if (T == null || T.length() == 0) {
	return T;
	}
	if (S == null || S.length() == 0) {
	return T;
	}
	map = new int[27];
	sequence = new int[27];
	for (int i = 0; i < 27; i++) {
	map[i] = -1;
	sequence[i] = -1;
	}
	for (int index = 0; index < S.length(); index++) {
	map[S.charAt(index) - 'a'] = index;
	sequence[index] = S.charAt(index) - 'a';
	}
	count = new int[27];
	for (int i = 0; i < T.length(); i++) {
	count[T.charAt(i) - 'a']++;
	}
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = 0; i < T.length() && sequence[i] != -1; i++) {
	int index = sequence[i];
	char currentChar = (char) (index + 'a');
	for (int times = 0; times < count[index]; times++) {
	stringBuilder.append(currentChar);
	}
	count[index] = 0;
	}
	for (int i = 0; i < count.length; i++) {
	if (count[i] > 0) {
	for (int j = 0; j < count[i]; j++) {
	stringBuilder.append((char) (i + 'a'));
	}
	}
	}
	// return the final result
	return stringBuilder.toString();
	}
	int[] map;
	int[] sequence;
	int[] count;
	}

view raw LC 791. Custom Sort String - Weekly Contest 73 - LeetCode.java hosted with ❤ by GitHub

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.

	class Solution {
	boolean escapeGhosts(int[][] ghosts, int[] target) {
	// filter abnormal cases
	// if (A == null || A.length == 0) {
	// return 0;
	// }
	if (ghosts == null || ghosts.length == 0) {
	return true;
	}
	int myDistance = getDistance(new int[]{0, 0}, target);
	int m = ghosts.length;
	for (int i = 0; i < m; i++) {
	int tmpDistance = getDistance(ghosts[i], target);
	if (tmpDistance <= myDistance) {
	return false;
	}
	}
	// return the final result
	return true;
	}
	int getDistance(int[] source, int[] target) {
	return Math.abs(source[0] - target[0]) + Math.abs(source[1] - target[1]);
	}
	}

view raw LC 789. Escape The Ghosts - Weekly Contest 73 - LeetCode.java hosted with ❤ by GitHub

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.

	class Solution {
	public int rotatedDigits(int N) {
	// filter abnormal cases
	int count = 0;
	this.N = N;
	for (int i = 1; i <= N; i++) {
	if (isGood(i)) {
	count++;
	}
	}
	// return the final result
	return count;
	}
	int N;
	int[] change = new int[]{0, 0, 5, -1, -1, 2, 9, -1, 0, 6};
	private boolean isGood(int i) {
	boolean isChange = false;
	while (i > 0) {
	int digit = i % 10;
	i /= 10;
	if (change[digit] == -1) {
	return false;
	} else if (change[digit] != 0) {
	isChange = true;
	}
	}
	return isChange;
	}
	}

view raw LC 788. Rotated Digits - Weekly Contest 73 - LeetCode.java hosted with ❤ by GitHub

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
 */

	public class Solution {
	public int kSum(int[] A, int k, int target) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return target == 0 ? 1 : 0;
	}
	dp = new int[A.length + 1][k + 1][target + 1];
	flag = new boolean[A.length + 1][k + 1][target + 1];
	this.A = A;
	// return the final result
	helper(A.length, k, target);
	for (int i = 0; i <= A.length; i++) {
	for (int j = 0; j <= k; j++) {
	System.out.println(Arrays.toString(flag[i][j]));
	}
	}
	for (int i = 0; i <= A.length; i++) {
	for (int j = 0; j <= k; j++) {
	System.out.println(Arrays.toString(dp[i][j]));
	}
	}
	return dp[A.length][k][target];
	}
	int[][][] dp;
	boolean[][][] flag;
	int[] A;
	public int helper(int i, int j, int t) {
	if (flag[i][j][t]) {
	return dp[i][j][t];
	}
	flag[i][j][t] = true;
	if (i < j) {
	dp[i][j][t] = 0;
	} else if (i == 0 || j == 0) {
	dp[i][j][t] = t == 0 ? 1 : 0;
	} else {
	dp[i][j][t] = helper(i - 1, j, t);
	if (t - A[i - 1] >= 0) {
	dp[i][j][t] += helper(i - 1, j - 1, t - A[i - 1]);
	}
	}
	return dp[i][j][t];
	}
	}

view raw LintCode 89. k Sum - LintCode.java hosted with ❤ by GitHub

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.

	public class Solution {
	public boolean isMatch(String A, String B) {
	// filter abnormal cases
	if (A == null) {
	return B == null;
	}
	if (A.equals(B)) {
	return true;
	}
	int m = A.length();
	int n = B.length();
	flag = new boolean[m + 1][n + 1];
	dp = new boolean[m + 1][n + 1];
	if (MyLogger.isDebugging) {
	System.out.println("m = " + m + "; n = " + n);
	}
	boolean answer = helper(m, n, A, B);
	if (MyLogger.isDebugging) {
	System.out.println("flag = ");
	for (int i = 0; i <= m; i++) {
	System.out.println(Arrays.toString(flag[i]));
	}
	System.out.println("dp = ");
	for (int i = 0; i <= m; i++) {
	System.out.println(Arrays.toString(dp[i]));
	}
	}
	return answer;
	}
	boolean[][] flag;
	boolean[][] dp;
	boolean helper(int i, int j, String A, String B) {
	if (flag[i][j]) {
	return dp[i][j];
	}
	flag[i][j] = true;
	if (j == 0) {
	dp[i][j] = i == 0;
	return dp[i][j];
	}
	if (i == 0) {
	dp[i][j] = isEmpty(j - 1, B);
	return dp[i][j];
	}
	if (B.charAt(j - 1) == '*') {
	if (j == 1) {
	dp[i][j] = helper(i, j - 1, A, B);
	} else {
	dp[i][j] |= helper(i, j - 2, A, B);
	if (B.charAt(j - 2) == '.' || B.charAt(j - 2) == A.charAt(i - 1)) {
	dp[i][j] |= helper(i - 1, j, A, B);
	}
	}
	} else {
	dp[i][j] = (B.charAt(j - 1) == '.' || B.charAt(j - 1) == A.charAt(i - 1)) && helper(i - 1, j - 1, A, B);
	}
	return dp[i][j];
	}
	boolean isEmpty(int j, String B) {
	if (j % 2 == 0) {
	return false;
	}
	for (int i = 1; i <= j; i += 2) {
	if (B.charAt(i) != '*') {
	return false;
	}
	}
	return true;
	}
	private static class MyLogger {
	static boolean isDebugging = false;
	static boolean isInfoing = true;
	static void debug(Object message) {
	if (isDebugging) {
	System.out.println("MyLogger.Debugging = " + message);
	}
	}
	static void info(Object message) {
	if (isInfoing) {
	System.out.println("MyLogger.Debugging = " + message);
	}
	}
	}
	}

view raw LintCode 154. Regular Expression Matching - LintCode.java hosted with ❤ by GitHub

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);

	public class Solution {
	/*
	* @param A: An integer array
	* @return: An integer
	*/
	public int stoneGame(int[] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int len = A.length;
	dp = new int[len][len];
	sum = new int[len][len];
	flag = new boolean[len][len];
	for (int i = 0; i < len; i++) {
	sum[i][i] = A[i];
	for (int j = i + 1; j < len; j++) {
	sum[i][j] = A[j] + sum[i][j - 1];
	}
	}
	// return the final result
	return helper(0, len - 1, A);
	}
	int[][] dp;
	int[][] sum;
	boolean[][] flag;
	int helper(int i, int j, int[] A) {
	if (flag[i][j]) {
	return dp[i][j];
	}
	if (i >= j) {
	return 0;
	}
	flag[i][j] = true;
	int min = Integer.MAX_VALUE;
	for (int k = i; k < j; k++) {
	min = Math.min(min, helper(i, k, A) + helper(k + 1, j, A));
	}
	dp[i][j] = sum[i][j] + min;
	return dp[i][j];
	}
	}

view raw LintCode 476. Stone Game - LintCode.java hosted with ❤ by GitHub

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.

	class Solution {
	public boolean reachingPoints(int sx, int sy, int tx, int ty) {
	// filter abnormal cases
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	if (Math.min(sx, sy) > Math.min(tx, ty)) {
	System.out.println(1);
	return reachingPoints1(sx, sy, tx, ty);
	} else {
	System.out.println(2);
	return reachingPoints2(sx, sy, tx, ty);
	}
	}
	private int sx;
	private int sy;
	HashSet<Entry> isVisited2 = new HashSet<>();
	public boolean reachingPoints2(int sx, int sy, int tx, int ty) {
	// filter abnormal cases
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited2.clear();
	this.sx = sx;
	this.sy = sy;
	return helper2(tx, ty);
	}
	public boolean helper2(int tx, int ty) {
	if (isVisited2.contains(new Entry(tx, ty))) {
	return false;
	}
	if (this.sx == tx && this.sy == ty) {
	return true;
	}
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited2.add(new Entry(tx, ty));
	return helper2(tx - ty, ty) || helper2(tx, ty - tx);
	}
	private int tx;
	private int ty;
	HashSet<Entry> isVisited = new HashSet<>();
	public boolean reachingPoints1(int sx, int sy, int tx, int ty) {
	// filter abnormal cases
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited.clear();
	this.tx = tx;
	this.ty = ty;
	return helper(sx, sy);
	}
	public boolean helper(int sx, int sy) {
	if (isVisited.contains(new Entry(sx, sy))) {
	return false;
	}
	if (sx == this.tx && sy == this.ty) {
	return true;
	}
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited.add(new Entry(sx, sy));
	return helper(sx + sy, sy) || helper(sx, sx + sy);
	}
	class Entry {
	int x;
	int y;
	public Entry(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	}

view raw LC 780. Reaching Points - Weekly Contest 71 - LeetCode.java hosted with ❤ by GitHub

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.

	class Solution {
	public int numRabbits(int[] answers) {
	// filter abnormal cases
	if (answers == null || answers.length == 0) {
	return 0;
	}
	if (answers.length == 1) {
	return answers[0] + 1;
	}
	int answer = 0;
	HashMap<Integer, Integer> map = new HashMap<>();
	for (int key : answers) {
	if (!map.containsKey(key)) {
	map.put(key, 1);
	} else {
	map.put(key, map.get(key) + 1);
	}
	}
	for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
	int key = integerIntegerEntry.getKey();
	int val = integerIntegerEntry.getValue();
	if (val % (key + 1) == 0) {
	answer += val;
	} else {
	answer += (val / (key + 1) + 1) * (key + 1);
	}
	}
	// return the final result
	return answer;
	}
	}

view raw LC 781. Rabbits in Forest - Weekly Contest 71 - LeetCode.java hosted with ❤ by GitHub

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.

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public int minDiffInBST(TreeNode root) {
	// filter abnormal cases
	if (root == null) {
	return 0;
	}
	nodes = new LinkedList<>();
	helper(root);
	// return the final result
	int answer = Integer.MAX_VALUE;
	int slow = nodes.getFirst();
	for (int i = 1; i < nodes.size(); i++) {
	int fast = nodes.get(i);
	answer = Math.min(answer, Math.abs(fast - slow));
	slow = fast;
	}
	return answer;
	}
	LinkedList<Integer> nodes;
	public void helper(TreeNode root) {
	if (root == null) {
	return;
	}
	helper(root.left);
	nodes.add(root.val);
	helper(root.right);
	}
	}

view raw LC 783. Minimum Distance Between BST Nodes - Weekly Contest 71 - LeetCode.java hosted with ❤ by GitHub

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

	public class Solution {
	/**
	* @param matrix: a matrix of integers
	* @param k: an integer
	* @return: the kth smallest number in the matrix
	*/
	public int kthSmallest(int[][] matrix, int k) {
	// write your code here
	// handle extreme cases
	if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
	return -1;
	}
	if (k == 0) {
	return -1;
	}
	int n = matrix.length;
	int m = matrix[0].length;
	PriorityQueue<Cell> heap = new PriorityQueue<Cell>(n, cellComparator);
	for (int i = 0; i < n; i++) {
	heap.add(new Cell(matrix[i][0], i, 0));
	}
	for (int i = k; i > 1; i--) {
	Cell poll = heap.poll();
	if (poll.y < m - 1) {
	heap.add(new Cell(matrix[poll.x][poll.y + 1], poll.x, poll.y + 1));
	}
	}
	if (heap.isEmpty()) {
	return -1;
	} else {
	return heap.poll().val;
	}
	}
	Comparator<Cell> cellComparator = new Comparator<Cell>() {
	public int compare(Cell o1, Cell o2) {
	return o1.val - o2.val;
	}
	};
	private class Cell {
	int val;
	int x;
	int y;
	public Cell() {
	}
	public Cell(int val, int x, int y) {
	this.val = val;
	this.x = x;
	this.y = y;
	}
	}
	}

view raw LintCode 401. Kth Smallest Number in Sorted Matrix.java hosted with ❤ by GitHub

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

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

	boolean[] a = new boolean[]{false, true, true, false};
	public int kthGrammar(int N, int K) {
	// filter abnormal cases
	if (K <= 4) {
	if (a[K - 1]) {
	return 1;
	} else {
	return 0;
	}
	}
	int k = K;
	boolean isReversed = false;
	while (k > 4) {
	if (k % 2 == 1) {
	k += 1;
	isReversed = !isReversed;
	k /= 2;
	isReversed = !isReversed;
	} else {
	k /= 2;
	isReversed = !isReversed;
	}
	}
	if (a[k - 1]) {
	return isReversed ? 0 : 1;
	} else {
	return isReversed ? 1 : 0;
	}
	}

view raw LC 779. K-th Symbol in Grammar - Weekly Contest 70 - LeetCode.java hosted with ❤ by GitHub