Introduction to Kaggle Machine Learning - Titanic Competition

Have you wonder how the fancy Machine Learning engineers complete their analysis and model training?

How they pick a good model and deploy all those predictions?

Well you are in the right place.

The big picture:

a simple pipeline begins with data massage.

then you will pick an algorithm and train on the data.

deploy your model online and support your business decisions.



So long story short, let's dive in:

1. First of all the Titanic dataset have a bunch of missing data.

so we filled it with NAN or Age.median.

If that a numerical column like the age, fill with median.
If that's a categorical column you can fill in female, or even UNKNOWN.

def fill_NAN(data):
    data_copy = data.copy(deep=True)
    #0, median, max, mean
    data_copy.loc[:, 'Age'] = data_copy.Age.fillna(data_copy.Age.median())
    data_copy.loc[:, 'Fare'] = data_copy.Fare.fillna(data_copy.Fare.median())
    data_copy.loc[:, 'Pclass'] = data_copy.Pclass.fillna(data_copy.Pclass.median())
    data_copy.loc[:, 'Sex'] = data_copy.Sex.fillna('female')
    data_copy.loc[:, 'Embarked'] = data_copy.Embarked.fillna('S')
    return data_copy
 
data_no_nan = fill_NAN(train)
data_no_nan

2. Then since we are using KNN today,

it would be great to change the male to 0, the female to 1. For the sake of the algorithm requirement.

def transfer_sex(data):
    data_copy = data.copy(deep=True)
    data_copy.loc[data_copy.Sex == 'female', 'Sex'] = 0
    data_copy.loc[data_copy.Sex == 'male', 'Sex'] = 1
    return data_copy
 
data_after_sex = transfer_sex(data_no_nan)
data_after_sex


def transfer_embarked(data):
    data_copy = data.copy(deep=True)
    data_copy.loc[data_copy.Embarked == 'S', 'Embarked'] = 0
    data_copy.loc[data_copy.Embarked == 'Q', 'Embarked'] = 1
    data_copy.loc[data_copy.Embarked == 'C', 'Embarked'] = 2
    return data_copy
 
data_after_embarked = transfer_embarked(data_after_sex)
data_after_embarked

3. remove the names since they contribute nothing to the probability. And also remove the cabin since the PClass is a better metric.
# Remove Ticket, Cabin
# type(data_after_embarked)
# np_array = data_after_embarked.values
# type(np_array)
data_after_dropped = data_after_embarked.drop('Ticket', 1)
print(data_after_dropped.shape)
data_after_dropped = data_after_dropped.drop('Cabin', 1)
print(data_after_dropped.shape)
data_after_dropped = data_after_dropped.drop('Name', 1)
print(data_after_dropped.shape)
data_after_dropped

4. Now you can simple run KNN
from sklearn.neighbors import KNeighborsClassifier
def KNN(train_X, train_y, test_X):
    k = 3
    knn = KNeighborsClassifier(n_neighbors = k)
    knn.fit(train_X, train_y)
    pred_y = knn.predict(test_X)
    return pred_y

pred_y = KNN(train_X, train_y, test_X)

print(train.shape)
# train_X = train[:, :]
# train_y = train[:, :]
print(train_X.shape,
     train_y.shape,
     test_X.shape,
      test_y.shape,
     pred_y.shape)

from sklearn.metrics import accuracy_score
from sklearn.metrics import confusion_matrix
from sklearn.metrics import classification_report
print(accuracy_score(test_y, pred_y))
print(confusion_matrix(test_y, pred_y))
print(classification_report(test_y, pred_y))

5. Or instead I recommend using a 5-fold cross validation:
from sklearn.model_selection import cross_val_score
for k in range(1, 6):
    knn = KNeighborsClassifier(n_neighbors = k)
    print(k, cross_val_score(knn, train_X, train_y, cv= 5))

1 [ 0.65921788  0.68715084  0.7247191   0.69662921  0.66666667]
2 [ 0.66480447  0.69273743  0.71910112  0.69662921  0.68361582]
3 [ 0.65921788  0.7150838   0.7247191   0.74157303  0.72316384]
4 [ 0.67039106  0.70391061  0.69101124  0.70786517  0.70056497]
5 [ 0.65921788  0.67597765  0.69662921  0.7247191   0.72316384]

form which we can see that the k = 3 is the best parameter.

6. Finally adopt the best parameter from your previous experiments, then generate result and submit.

Ok so here are some tricks to speed you up/ avoid some pitfalls:
1. leave id alone, then combine the training and testing data together. So you don't need to apply the same data massage twice.

2. pick the id up at last and put it in the first column of final result.


To sum up,
A. PreProcess:
1. read data
2. Visualization: Heatmap of Correlation
0. Combine for a single pass massaging
1. Feature Selection - drop irrelevant
2. fill NaN
3. white hot encoding
Feature Engineering
Visualization - 'Pearson Correlation of Features'
4. Split back into training and testing
optional 5. chop as you see fit

optional: matplotlib
optional: feature engineering
optional:dropna - X_train=X_train.dropna(axis=1, how='all')

B:
1. cross validation, grid search
1. Generating our Base First-Level Models
2. Second-Level Predictions from the First-level Output

C:
1. final prediction and submit

LintCode 970. Big Business - Weekly13

Big Business, lol

O(n) loop and execute a trade if and only if you can afford it, and also you can gain profit from it.

For any profitable but not yet affordable Business, put them in a minimum Heap.

Finally, check the heap for anything that you can afford and execute anything that's possible.

At last, you can no longer possibly afford anything else, thus return the latest K right away.

	int bigBusiness(int[] A, int[] B, int k) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int len = A.length;
	PriorityQueue<Entry> minHeap = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
	for (int i = 0; i < len; i++) {
	if (A[i] >= B[i]) {
	continue;
	}
	// System.out.println("i = " + i + "; A[i] = " + A[i]);
	if (k > A[i]) {
	k += B[i] - A[i];
	} else {
	minHeap.add(new Entry(A[i], B[i] - A[i]));
	}
	}
	while (!minHeap.isEmpty()) {
	if (minHeap.peek().cost > k) {
	break;
	}
	Entry entry = minHeap.poll();
	k += entry.profit;
	}
	// return the final result
	return k;
	}
	private class Entry {
	int cost;
	int profit;
	public Entry(int cost, int profit) {
	this.cost = cost;
	this.profit = profit;
	}
	@Override
	public String toString() {
	return "Entry{" +
	"cost=" + cost +
	", profit=" + profit +
	'}';
	}
	}

view raw LintCode 970. Big Business - Weekly13 - LintCode.java hosted with ❤ by GitHub

LintCode 972. Deliver The Message - Weekly13

http://www.lintcode.com/en/problem/deliver-the-message/

Given the information of a company's personnel. The time spent by the ith person passing the message is t[i] and the list of subordinates is list[i]. When someone receives a message, he will immediately pass it on to all his subordinates. Person numbered 0 is the CEO. Now that the CEO has posted a message, find how much time it takes for everyone in the company to receive the message?

 Notice

• The number of employees is n，n <= 1000.
• Everyone can have multiple subordinates but only one superior.
• Time t[i] <= 10000。
• -1 represent no subordinates.

Use a queue to mark this level, and do a BFS search.
Keep updating the shortest time for each employee.
Stop the search whenever everybody's covered.

Then O(n) loop for each employees to get the maximum time and return.

	int deliverMessage(int[] A, int[][] subordinate) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int len = A.length;
	HashSet<Integer> set = new HashSet<>();
	HashMap<Integer, Integer> map = new HashMap<>();
	set.add(0);
	map.put(0, 0);
	Queue<Integer> queue = new ArrayDeque<>();
	queue.add(0);
	while (!queue.isEmpty()) {
	Integer i = queue.poll();
	// if (set.size() == len) {
	// break;
	// }
	if (subordinate[i].length <= 1 && subordinate[i][0] == -1) {
	continue;
	}
	int subTime = map.get(i) + A[i];
	for (int sub : subordinate[i]) {
	set.add(sub);
	queue.add(sub);
	if (!map.containsKey(sub)) {
	map.put(sub, subTime);
	} else {
	map.put(sub, Math.min(map.get(sub), subTime));
	}
	}
	}
	int time = Integer.MIN_VALUE;
	// System.out.println(map);
	for (int i = 0; i < len; i++) {
	// System.out.println("i = " + i);
	time = Math.max(time, map.get(i));
	}
	// return the final result
	return time;
	}

view raw LintCode 972. Deliver The Message - Weekly13 - LintCode.java hosted with ❤ by GitHub

Machine Learning notes

Supervised Machine Learning (providing labels)

Regression v.s. Classification:
one for the continuous data, the other for the discrete data.

LintCode 897. Island City - Weekly9

http://www.lintcode.com/en/problem/island-city/

You could use UnionFind, I just don't bother doing it.

As the islands are not dynamic UnionFind is unnecessary.

Just use plain old DFS, trigger it with a simple scan for cities that's not visited, then paint all visited cities with 2(or maybe not, it doesn't matter now).

Then count the number of triggers.

Boom!

	public class Solution {
	/**
	* @param grid: an integer matrix
	* @return: an integer
	*/
	int numIslandCities(int[][] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	this.m = A.length;
	this.n = A[0].length;
	this.A = A;
	this.visited = new boolean[m][n];
	int counter = 0;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (A[i][j] == 2 && !visited[i][j]) {
	dfs(i, j);
	counter++;
	}
	}
	}
	// return the final result
	return counter;
	}
	int[][] A;
	boolean[][] visited;
	int m;
	int n;
	private void dfs(int i, int j) {
	if (i < 0 || j < 0 || i >= m || j >= n) {
	return;
	}
	if (A[i][j] == 0) {
	return;
	}
	if (visited[i][j]) {
	return;
	}
	visited[i][j] = true;
	A[i][j] = 2;
	dfs(i - 1, j);
	dfs(i + 1, j);
	dfs(i, j - 1);
	dfs(i, j + 1);
	}
	}

view raw LintCode 897. Island City - Weekly9 - LintCode.java hosted with ❤ by GitHub

LintCode 898. Leftmost One - Weekly9

http://www.lintcode.com/en/problem/leftmost-one/

An interesting questions, i find it sufficient applying binary search.

	public class Solution {
	/**
	* @param arr: The 2-dimension array
	* @return: Return the column the leftmost one is located
	*/
	int getColumn(int[][] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	this.m = A.length;
	this.n = A[0].length;
	int min = A.length - 1;
	for (int i = 0; i < m; i++) {
	int index = binarySearch(A[i]);
	min = Math.min(min, index);
	}
	// return the final result
	return min;
	}
	int m;
	int n;
	int binarySearch(int[] A) {
	int left = 0;
	int right = A.length - 1;
	while (left + 1 < right) {
	int mid = (right - left) / 2 + left;
	if (A[mid] == 1) {
	right = mid;
	} else {
	left = mid;
	}
	}
	if (A[left] == 1) {
	return left;
	} else {
	return right;
	}
	}
	}

view raw LintCode 898. Leftmost One - Weekly9 - LintCode.java hosted with ❤ by GitHub

LintCode 895. Friend Request - Weekly9

http://www.lintcode.com/en/problem/friend-request/

It's a stupid question. Don't bother optimize with sorting or anything.

Just brute force is more than sufficient.

Nothing more to say...sigh...

	public class Solution {
	/**
	* @param ages: The ages
	* @return: The answer
	*/
	public int friendRequest(int[] ages) {
	// Write your code here
	if (ages == null || ages.length == 0) {
	return 0;
	}
	// Arrays.sort(ages);
	int answer = 0;
	for (int b = 0; b < ages.length; b++) {
	int delta = 0;
	if (ages[b] >= 100) {
	for (int a = 0; a < ages.length; a++) {
	if (a == b) {
	continue;
	}
	// System.out.println("a, b = " + a + ", " + b + "; ages[a], ages[b] = " + ages[a] + ", " + ages[b]);
	if (ages[a] < ages[b] || ages[a] / 2 + 7 >= ages[b]) {
	} else {
	delta++;
	}
	}
	} else {
	for (int a = 0; a < ages.length; a++) {
	if (a == b) {
	continue;
	}
	// System.out.println("a, b = " + a + ", " + b + "; ages[a], ages[b] = " + ages[a] + ", " + ages[b]);
	if (ages[a] > 100 || ages[a] < ages[b] || ages[a] / 2 + 7 >= ages[b]) {
	} else {
	delta++;
	}
	}
	}
	// System.out.println(delta);
	answer += delta;
	}
	return answer;
	}
	}

view raw LintCode 895. Friend Request - Weekly9 - LintCode.java hosted with ❤ by GitHub

LintCode 896. PrimeProduct - Weekly9

http://www.lintcode.com/en/problem/prime-product/

it's a tricky question if you are trying to if-else for 2 to 9 for-loops.

but we can simply use the DFS search.

Then eliminate duplication, and apply ordering.

	public class Solution {
	/**
	* @param arr: The prime array
	* @return: Return the array of all of prime product
	*/
	int[] getPrimeProduct(int[] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return new int[0];
	}
	this.A = A;
	this.set = new HashSet<>();
	helper(0, 1, 0);
	TreeSet<Integer> treeSet = new TreeSet<>(set);
	int[] answer = new int[treeSet.size()];
	for (int i = 0; i < answer.length; i++) {
	answer[i] = treeSet.pollFirst();
	}
	// return the final result
	return answer;
	}
	private void helper(int index, int product, int counter) {
	if (index == A.length) {
	if (counter > 1) {
	set.add(product);
	}
	} else {
	helper(index + 1, product * A[index], counter + 1);
	helper(index + 1, product, counter);
	}
	}
	int[] A;
	HashSet<Integer> set;
	}

view raw LintCode No896_PrimeProduct - Weekly9 - LintCode.java hosted with ❤ by GitHub

LeetCode 794. Valid Tic-Tac-Toe State - Weekly Contest 74

https://leetcode.com/contest/weekly-contest-74/problems/valid-tic-tac-toe-state/




It's a simulation, just be patient and careful.

think of all the possibilities. Classified them. use | stand for the column strike, use - for the row strike.

use the \ and / for the diagonals.

	class Solution {
	boolean validTicTacToe(String[] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return false;
	}
	int XCount = 0;
	int OCount = 0;
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	if (A[i].charAt(j) == 'X') {
	XCount++;
	} else if (A[i].charAt(j) == 'O') {
	OCount++;
	}
	}
	}
	int XWinCount = 0;
	int OWinCount = 0;
	if (A[1].charAt(1) != ' ') {
	if (A[1].charAt(1) == 'X') {
	// * / \
	if (A[2].charAt(0) == 'X' && A[0].charAt(2) == 'X') {
	XWinCount++;
	}
	if (A[2].charAt(2) == 'X' && A[0].charAt(0) == 'X') {
	XWinCount++;
	}
	// + - |
	if (A[1].charAt(0) == 'X' && A[1].charAt(2) == 'X') {
	XWinCount++;
	}
	if (A[2].charAt(1) == 'X' && A[0].charAt(1) == 'X') {
	XWinCount++;
	}
	} else {
	// * / \
	if (A[2].charAt(0) == 'O' && A[0].charAt(2) == 'O') {
	OWinCount++;
	}
	if (A[2].charAt(2) == 'O' && A[0].charAt(0) == 'O') {
	OWinCount++;
	}
	// + - |
	if (A[1].charAt(0) == 'O' && A[1].charAt(2) == 'O') {
	OWinCount++;
	}
	if (A[2].charAt(1) == 'O' && A[0].charAt(1) == 'O') {
	OWinCount++;
	}
	}
	}
	if (A[0].charAt(0) != ' ') {
	if (A[0].charAt(0) == 'X') {
	// | -
	if (A[2].charAt(0) == 'X' && A[1].charAt(0) == 'X') {
	XWinCount++;
	}
	if (A[0].charAt(1) == 'X' && A[0].charAt(2) == 'X') {
	XWinCount++;
	}
	} else {
	// | -
	if (A[2].charAt(0) == 'O' && A[1].charAt(0) == 'O') {
	OWinCount++;
	}
	if (A[0].charAt(1) == 'O' && A[0].charAt(2) == 'O') {
	OWinCount++;
	}
	}
	}
	if (A[2].charAt(2) != ' ') {
	if (A[2].charAt(2) == 'X') {
	// | -
	if (A[0].charAt(2) == 'X' && A[1].charAt(2) == 'X') {
	XWinCount++;
	}
	if (A[2].charAt(0) == 'X' && A[2].charAt(1) == 'X') {
	XWinCount++;
	}
	} else {
	// | -
	if (A[0].charAt(2) == 'O' && A[1].charAt(2) == 'O') {
	OWinCount++;
	}
	if (A[2].charAt(0) == 'O' && A[2].charAt(1) == 'O') {
	OWinCount++;
	}
	}
	}
	// System.out.println(XCount);
	// System.out.println(OCount);
	if (XCount != OCount && XCount != (OCount + 1)) {
	return false;
	}
	if (XWinCount + OWinCount > 1) {
	return false;
	}
	if (XWinCount == 1) {
	return XCount == OCount + 1;
	} else if (OWinCount == 1) {
	return XCount == OCount;
	}
	return true;
	}
	}

view raw LC 794. Valid Tic-Tac-Toe State - Weekly Contest 74 - LeetCode.java hosted with ❤ by GitHub

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

LeetCode 771. Jewels and Stones - Weekly Contest 69

https://leetcode.com/contest/weekly-contest-69/problems/jewels-and-stones/

	class Solution {
	public int numJewelsInStones(String J, String S) {
	if (S == null || S.length() < 1 || J == null || J.length() < 1) {
	return 0;
	}
	int[] L = new int[500];
	for(int i = 0; i < J.length(); i++) {
	L[J.charAt(i)] = 1;
	}
	int count = 0;
	for(int i = 0; i < S.length(); i++) {
	if(L[S.charAt(i)] == 1) {
	count++;
	}
	}
	return count;
	}
	}

view raw LC 771. Jewels and Stones - Weekly Contest 69 - LeetCode.java hosted with ❤ by GitHub

LeetCode 775. Global and Local Inversions - Weekly Contest 69

https://leetcode.com/contest/weekly-contest-69/problems/global-and-local-inversions/

	class Solution {
	public boolean isIdealPermutation(int[] A) {
	if (A == null || A.length < 3) {
	return true;
	}
	int len = A.length;
	for (int i = 0; i < len - 1; i++) {
	if (A[i] == i) {
	continue;
	} else if (A[i] == i+1 && A[i + 1]== i) {
	i++;
	} else {
	return false;
	}
	}
	return true;
	// int globalInversions = 0;
	// for(int i = 0; i < len - 1; i++) {
	// for(int j = i + 1; j < len; j++) {
	// if (A[i] > A[j]) {globalInversions++;}
	// }
	// }
	// int localInversions = 0;
	// for(int i = 0; i < len - 1; i++) {
	// if (A[i] > A[i+1]) {localInversions++;}
	// }
	// return globalInversions == localInversions;
	}
	}

view raw LC 775. Global and Local Inversions - Weekly Contest 69 - LeetCode.java hosted with ❤ by GitHub

LeetCode 159. Longest Substring with At Most Two Distinct Characters - Google - HashMap, Two Pointers, String

The main idea is to maintain a sliding window with 2 unique characters. 

The key is to store the last occurrence of each character as the value in the hashmap.

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/

	class Solution {
	public int lengthOfLongestSubstringTwoDistinct(String s) {
	// filter abnormal inputs
	if (s == null) {
	return 0;
	}
	if (s.length() < 3) {
	return s.length();
	}
	// core logic
	int start = 0;
	int end = 0;
	int maxLength = Integer.MIN_VALUE;
	HashMap<Character, Integer> map = new HashMap<>();
	for(int i = 0; i < s.length(); i++) {
	Character key = s.charAt(i);
	if (!map.containsKey(key) && map.size() == 2) {
	// situation 3
	int leftMost = Integer.MAX_VALUE;
	for(int value: map.values()) {
	leftMost = Math.min(leftMost, value);
	}
	start = leftMost + 1;
	map.remove(s.charAt(leftMost));
	}
	map.put(key, end);
	maxLength = Math.max(maxLength, end - start + 1);
	end++;
	}
	return maxLength;
	}
	}

view raw LC 159. Longest Substring with At Most Two Distinct Characters - LeetCode - Google - HashMap, Two Pointers, String.java hosted with ❤ by GitHub

LeetCode 768. Max Chunks to Make Sorted (ver. 2) - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/max-chunks-to-make-sorted-ver-2/

	class Solution {
	/**
	* @param arr an array of Integer
	* @return an integer
	*/
	public int maxChunksToSorted(int[] arr) {
	// filter abnormal cases
	if (arr == null || arr.length == 0) {
	return 1;
	}
	// core logic
	int max = arr[0];
	int cutCounter = 1;
	int[] copy = Arrays.copyOf(arr, arr.length);
	Arrays.sort(copy);
	// System.out.println(Arrays.toString(copy));
	// System.out.println(Arrays.toString(arr));
	HashMap<Integer, Integer> map = new HashMap<>();
	for (int i = 0; i < arr.length - 1; i++) {
	// System.out.println("i = " + i);
	// System.out.println("map = " + map);
	if (stepAndIsEmpty(copy[i], arr[i], map)) {
	// System.out.println("Got a cut! i = " + i);
	// System.out.println("copy[i] = " + copy[i]);
	// System.out.println("arr[i] = " + arr[i]);
	cutCounter++;
	}
	}
	// return the final result
	return cutCounter;
	}
	private boolean stepAndIsEmpty(int keyToAdd, int keyToKill, HashMap<Integer, Integer> map) {
	if (keyToAdd != keyToKill) {
	if (map.containsKey(keyToAdd)) {
	if (map.get(keyToAdd) + 1 == 0) {
	map.remove(keyToAdd);
	} else {
	map.put(keyToAdd, map.get(keyToAdd) + 1);
	}
	} else {
	map.put(keyToAdd, 1);
	}
	if (map.containsKey(keyToKill)) {
	if (map.get(keyToKill) - 1 == 0) {
	map.remove(keyToKill);
	} else {
	map.put(keyToKill, map.get(keyToKill) - 1);
	}
	} else {
	map.put(keyToKill, -1);
	}
	}
	return map.isEmpty();
	}
	}

view raw LC 768. Max Chunks to Make Sorted (ver. 2) - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub

LeetCode 769. Max Chunks To Make Sorted (ver. 1) - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/max-chunks-to-make-sorted-ver-1/

	class Solution {
	/**
	* @param arr
	* @return
	*/
	public int maxChunksToSorted(int[] arr) {
	// filter abnormal cases
	if (arr == null || arr.length == 0) {
	return 1;
	}
	// core logic
	int[] map = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
	map[arr[i]] = i;
	}
	int minCut = 0;
	int cutCounter = 1;
	for (int i = 0; i < arr.length - 1; i++) {
	int tmpRquire = Math.max(map[arr[i]], arr[i]);
	minCut = Math.max(minCut, tmpRquire);
	if (minCut <= i) {
	// System.out.println("Got a cut!! minCut = " + minCut);
	// System.out.println("cutCounter = " + cutCounter);
	// System.out.println("tmpRquire = " + tmpRquire);
	// System.out.println("i = " + i);
	minCut = i + 1;
	cutCounter++;
	}
	}
	// return the final result
	return cutCounter;
	}
	}

view raw LC 769. Max Chunks To Make Sorted (ver. 1) - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub

LeetCode 766. Toeplitz Matrix - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/toeplitz-matrix/

	class Solution {
	/**
	* @param matrix
	* @return
	*/
	public boolean isToeplitzMatrix(int[][] matrix) {
	// filter abnormal cases
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
	return true;
	}
	// core logic
	int m = matrix.length;
	int n = matrix[0].length;
	if (MyLogger.isDebugging) {
	for (int[] aMatrix : matrix) {
	System.out.println(Arrays.toString(aMatrix));
	}
	for (int T = m - 1; T >= 0; T--) {
	int i = T;
	int j = 0;
	final int target = matrix[i][j];
	System.out.println("Shu: " + matrix[i][j]);
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	System.out.println("Shu: " + matrix[i][j]);
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	for (int T = 1; T < n; T++) {
	int i = 0;
	int j = T;
	final int target = matrix[i][j];
	System.out.println("heng: " + matrix[i][j]);
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	System.out.println("heng: " + matrix[i][j]);
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	}
	for (int T = m - 1; T >= 0; T--) {
	int i = T;
	int j = 0;
	final int target = matrix[i][j];
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	for (int T = 1; T < n; T++) {
	int i = 0;
	int j = T;
	final int target = matrix[i][j];
	i++;
	j++;
	while (isValid(i, j, m, n)) {
	if (matrix[i][j] != target) {
	return false;
	}
	i++;
	j++;
	}
	}
	// return the final result
	return true;
	}
	private boolean isValid(int x, int y, int m, int n) {
	return x >= 0 && y >= 0 && x < m && y < n;
	}
	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 LC 766. Toeplitz Matrix - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub

LCS - Longest Common Subsequence - Dynamic Programming

https://practice.geeksforgeeks.org/problems/longest-common-subsequence/0/?ref=self

	/*package whatever //do not write package name here */
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	class GFG {
	public static void main(String[] args) {
	//code
	Scanner scanner = new Scanner(System.in);
	int T = scanner.nextInt();
	for (int t = 0; t < T; t++) {
	int m = scanner.nextInt();
	int n = scanner.nextInt();
	if (m < 1) {
	System.out.println(n);
	} else if (n < 1) {
	System.out.println(m);
	}
	String string1 = scanner.next();
	String string2 = scanner.next();
	int[][] dp = new int[m][n];
	int globalMax = 0;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (string1.charAt(i) == string2.charAt(j)) {
	int localMax = 0;
	for (int x = 0; x < i; x++) {
	for (int y = 0; y < j; y++) {
	localMax = Math.max(localMax, dp[x][y]);
	}
	}
	dp[i][j] = localMax + 1;
	globalMax = Math.max(globalMax, dp[i][j]);
	}
	}
	}
	// System.out.println(Arrays.toString(dp));
	System.out.println(globalMax);
	}
	}
	}

view raw LCS - Longest Common Subsequence - Dynamic Programming.java hosted with ❤ by GitHub

LIS - Longest Increasing Subsequence - Dynamic Programming

https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence/0

	/*package whatever //do not write package name here */
	import java.util.*;
	import java.lang.*;
	import java.io.*;
	class GFG {
	public static void main(String[] args) {
	//code
	Scanner scanner = new Scanner(System.in);
	int T = scanner.nextInt();
	for (int t = 0; t < T; t++) {
	int N = scanner.nextInt();
	if (N < 1) {
	System.out.println(0);
	continue;
	}
	int[] A = new int[N];
	for (int i = 0; i < N; i++) {
	A[i] = scanner.nextInt();
	}
	// DP
	int[] dp = new int[N];
	dp[0] = 1;
	int globalMax = 1;
	for (int i = 1; i < N; i++) {
	dp[i] = 1;
	int max = 0;
	for (int j = 0; j < i; j++) {
	if (A[j] < A[i]) {
	max = Math.max(max, dp[j]);
	}
	}
	dp[i] += max;
	globalMax = Math.max(globalMax, dp[i]);
	}
	// System.out.println(Arrays.toString(dp));
	System.out.println(globalMax);
	}
	}
	}

view raw LIS - Longest Increasing Subsequence - Dynamic Programming.java hosted with ❤ by GitHub

HR Hash Tables: Ice Cream Parlor - HackerRank Cracking the Coding Interview Challenges

https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem

	import java.io.*;
	import java.util.*;
	import java.text.*;
	import java.math.*;
	import java.util.regex.*;
	public class Solution {
	/**
	* @param arr
	* @param money
	*/
	static void solve(int[] arr, int money) {
	// Complete this function
	if (arr == null || arr.length < 1) {
	System.out.println(-1 + " " + -1);
	return;
	}
	// core logic
	HashMap<Integer, Integer> hashMap = new HashMap<>();
	for (int i = 0; i < arr.length; i++) {
	if (arr[i] < money) {
	if (hashMap.containsKey(money - arr[i])) {
	int index = hashMap.get(money - arr[i]);
	System.out.println((index + 1) + " " + (i + 1));
	return;
	}
	if (!hashMap.containsKey(arr[i])) {
	hashMap.put(arr[i], i);
	}
	}
	}
	}
	public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int t = in.nextInt();
	for(int a0 = 0; a0 < t; a0++){
	int money = in.nextInt();
	int n = in.nextInt();
	int[] arr = new int[n];
	for(int arr_i = 0; arr_i < n; arr_i++){
	arr[arr_i] = in.nextInt();
	}
	solve(arr, money);
	}
	in.close();
	}
	}

view raw HR Hash Tables: Ice Cream Parlor - HackerRank Cracking the Coding Interview Challenges.java hosted with ❤ by GitHub

LC 375. Guess Number Higher or Lower II - LeetCode Google DynamicProgramming MinMax

https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/

	class Solution {
	/**
	* @param n
	* @return
	*/
	public int getMoneyAmount(int n) {
	if (n < 2) {
	return 0;
	}
	// core logic
	table = new int[n + 1][n + 1];
	return dp(1, n);
	}
	private int[][] table;
	private int dp(int start, int end) {
	if (start >= end) {
	return 0;
	}
	if (table[start][end] != 0) {
	return table[start][end];
	}
	int min = Integer.MAX_VALUE;
	for (int i = start; i <= end; i++) {
	int res = i + Math.max(dp(start, i - 1), dp(i + 1, end));
	min = Math.min(min, res);
	}
	table[start][end] = min;
	return min;
	}
	}

view raw LC 375. Guess Number Higher or Lower II - LeetCode Google DynamicProgramming MinMax.java hosted with ❤ by GitHub

LC 374. Guess Number Higher or Lower - LeetCode Google BinarySearch

https://leetcode.com/problems/guess-number-higher-or-lower/description/

	/* The guess API is defined in the parent class GuessGame.
	@param num, your guess
	@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
	int guess(int num); */
	public class Solution extends GuessGame {
	public int guessNumber(int n) {
	if (n < 2) {
	return n;
	}
	// core logic
	int start = 1;
	int end = n;
	while(start + 1 < end) {
	int mid = (end - start) / 2 + start;
	int tmpResult = guess(mid);
	if (tmpResult == -1) {
	end = mid;
	} else if (tmpResult == 1) {
	start = mid;
	} else {
	return mid;
	}
	}
	if (guess(start) == 0) {
	return start;
	} else {
	return end;
	}
	}
	}

view raw LC 374. Guess Number Higher or Lower - LeetCode Google BinarySearch.java hosted with ❤ by GitHub

LC 278. First Bad Version - LeetCode Facebook BinarySearch

https://leetcode.com/problems/first-bad-version/description/

	/* The isBadVersion API is defined in the parent class VersionControl.
	boolean isBadVersion(int version); */
	public class Solution extends VersionControl {
	public int firstBadVersion(int n) {
	if (n < 2) {
	return n;
	}
	// core logic
	int start = 1;
	int end = n;
	while(start + 1 < end) {
	int mid = (end - start) / 2 + start;
	if (isBadVersion(mid)) {
	end = mid;
	} else {
	start = mid;
	}
	}
	if (isBadVersion(start)) {
	return start;
	} else {
	return end;
	}
	}
	}

view raw LC 278. First Bad Version - LeetCode Facebook BinarySearch.java hosted with ❤ by GitHub

LC 683. K Empty Slots - LeetCode Hard Google TreeSet

https://leetcode.com/problems/k-empty-slots/description/

	class Solution {
	public int kEmptySlots(int[] flowers, int k) {
	if (flowers == null || flowers.length < 1) {
	return -1;
	}
	// core logic
	TreeSet<Integer> bloomingTreeSet = new TreeSet<>();
	int day = 0;
	for(int flower: flowers) {
	day++;
	bloomingTreeSet.add(flower);
	Integer higher = bloomingTreeSet.higher(flower);
	Integer lower = bloomingTreeSet.lower(flower);
	if (higher != null && higher - flower - 1 == k ||
	lower != null && flower - lower - 1 == k ) {
	return day;
	}
	}
	return -1;
	}
	}

view raw LC 683. K Empty Slots - LeetCode Hard Google TreeSet.java hosted with ❤ by GitHub

LC 35. Search Insert Position - LeetCode

This question requires a straightforward scan.
We can't help but notice there's only two situations:
0. empty array, so go ahead and insert into 0;
1. if you see nums[i] equal to the target, congratulations and return the i! Also, if you see nums[i] larger, go ahead and return the i because it will be inserted into i.
2. If you can't find such a fit in the Rule No.1. Go ahead and append it to the very end of the Array. And that would be nums.length;

So my clever reader now you can go ahead and give it a try yourself.
:)

	class Solution {
	public int searchInsert(int[] nums, int target) {
	if (nums == null || nums.length < 1) {
	return 0;
	}
	// O(n) traverse
	for(int i = 0; i < nums.length; i++) {
	if (target <= nums[i]) {
	return i;
	}
	}
	return nums.length;
	}
	}

view raw LC 35. Search Insert Position - LeetCode.java hosted with ❤ by GitHub

LC 102. Binary Tree Level Order Traversal - LeetCode

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	/**
	* @param root
	* @return
	*/
	public List<List<Integer>> levelOrder(TreeNode root) {
	// filter abnormal cases
	if (root == null) {
	return new LinkedList<>();
	}
	// core logic
	Queue<Entry> queue1 = new LinkedList<>();
	Queue<Entry> queue2 = new LinkedList<>();
	queue1.add(new Entry(root, 1));
	List<List<Integer>> resultList = new LinkedList<>();
	while (true) {
	if (queue1.isEmpty()) {
	return resultList;
	}
	List<Integer> row = new LinkedList<>();
	rowProcessing(queue1, queue2, row);
	resultList.add(row);
	Queue<Entry> tmp = queue1;
	queue1 = queue2;
	queue2 = tmp;
	}
	}
	private void rowProcessing(Queue<Entry> queue1, Queue<Entry> queue2, List<Integer> row) {
	while (!queue1.isEmpty()) {
	Entry currentEntry = queue1.remove();
	row.add(currentEntry.node.val);
	if (currentEntry.node.left != null) {
	queue2.add(new Entry(currentEntry.node.left, currentEntry.depth + 1));
	}
	if (currentEntry.node.right != null) {
	queue2.add(new Entry(currentEntry.node.right, currentEntry.depth + 1));
	}
	}
	}
	class Entry {
	TreeNode node;
	int depth;
	public Entry(TreeNode node, int depth) {
	this.node = node;
	this.depth = depth;
	}
	@Override
	public String toString() {
	return "Entry{" +
	"node=" + node +
	", depth=" + depth +
	'}';
	}
	}
	}

view raw LC 102. Binary Tree Level Order Traversal - Weekly Contest 67 - LeetCode.java hosted with ❤ by GitHub

LC 765. Couples Holding Hands - Weekly Contest 67 - LeetCode

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
Note:

len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0...len(row)-1.

	class Solution {
	/**
	* @param row
	* @return
	*/
	public int minSwapsCouples(int[] row) {
	// filter abnormal cases
	if (row == null || row.length == 0) {
	return 0;
	}
	// core logic
	int swapCounter = 0;
	HashMap<Integer, Integer> lookup = new HashMap<>();
	for (int i = 0; i < row.length; i++) {
	lookup.put(row[i], i);
	}
	for (int i = 0; i < row.length; i += 2) {
	if (!isPair(row[i], row[i + 1])) {
	swap(row, i + 1, lookup.get(getPartner(row[i])), lookup);
	swapCounter++;
	}
	}
	// return the final result
	return swapCounter;
	}
	private int getPartner(int i) {
	if (i % 2 == 0) {
	return i + 1;
	} else {
	return i - 1;
	}
	}
	private void swap(int[] row, int i, int j, HashMap<Integer, Integer> lookup) {
	int tmp = row[i];
	lookup.put(row[i], j);
	lookup.put(row[j], i);
	row[i] = row[j];
	row[j] = tmp;
	}
	private boolean isPair(int a, int b) {
	return a / 2 == b / 2;
	}
	}

view raw LC 765. Couples Holding Hands.java hosted with ❤ by GitHub

LC 764. Largest Plus Sign - Weekly Contest 67 - LeetCode

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000
Example 1:

Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.
Example 2:

Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.
Example 3:

Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.
Note:

N will be an integer in the range [1, 500].
mines will have length at most 5000.
mines[i] will be length 2 and consist of integers in the range [0, N-1].
(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)


首先是把十字架的需求分解成四个方向。
这样理解就有思路了。
接着一看可以上动归。
四个方向分别开个dp数组，动态规划，全是O(N^N)的时空复杂度。
最后扫一遍得出结果，最边缘的地方特殊情况放最后处理。

最终时空复杂度O(N^N)

	class Solution {
	/**
	* @param N
	* @param mines
	* @return
	*/
	public int orderOfLargestPlusSign(int N, int[][] mines) {
	// filter abnormal cases
	if (mines == null || mines.length == 0) {
	return (N + 1) / 2;
	}
	// core logic
	int m = mines.length;
	int[][] matrix = new int[N][N];
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	matrix[i][j] = 1;
	}
	}
	for (int[] mine : mines) {
	matrix[mine[0]][mine[1]] = 0;
	}
	int[][] dpUp = new int[N][N];
	int[][] dpDown = new int[N][N];
	int[][] dpLeft = new int[N][N];
	int[][] dpRight = new int[N][N];
	for (int i = 1; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (matrix[i - 1][j] == 0) {
	dpUp[i][j] = 0;
	} else {
	dpUp[i][j] = dpUp[i - 1][j] + 1;
	}
	}
	}
	for (int i = N - 2; i >= 0; i--) {
	for (int j = 0; j < N; j++) {
	if (matrix[i + 1][j] == 0) {
	dpDown[i][j] = 0;
	} else {
	dpDown[i][j] = dpDown[i + 1][j] + 1;
	}
	}
	}
	//left
	for (int j = 1; j < N; j++) {
	for (int i = 0; i < N; i++) {
	if (matrix[i][j - 1] == 0) {
	dpLeft[i][j] = 0;
	} else {
	dpLeft[i][j] = dpLeft[i][j - 1] + 1;
	}
	}
	}
	//right
	for (int j = N - 2; j >= 0; j--) {
	for (int i = 0; i < N; i++) {
	if (matrix[i][j + 1] == 0) {
	dpRight[i][j] = 0;
	} else {
	dpRight[i][j] = dpRight[i][j + 1] + 1;
	}
	}
	}
	// Final Scan
	int maxK = 0;
	for (int i = 1; i < N - 1; i++) {
	for (int j = 1; j < N - 1; j++) {
	if (matrix[i][j] == 1) {
	maxK = Math.max(maxK, 1 + Math.min(Math.min(dpUp[i][j], dpDown[i][j]), Math.min(dpLeft[i][j], dpRight[i][j])));
	}
	}
	}
	if (maxK < 1) {
	for (int i = 0; i < N; i++) {
	if (matrix[i][0] == 1 || matrix[i][N - 1] == 1) {
	maxK = 1;
	return maxK;
	}
	}
	for (int j = 1; j < N - 1; j++) {
	if (matrix[0][j] == 1 || matrix[N - 1][j] == 1) {
	maxK = 1;
	return maxK;
	}
	}
	}
	// return the final result
	return maxK;
	}
	}

view raw LC 764. Largest Plus Sign.java hosted with ❤ by GitHub

LC 762. Prime Number of Set Bits in Binary Representation - Weekly Contest 67 - LeetCode

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)
Example 2:

Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
Note:

L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

	class Solution {
	/**
	* @param L
	* @param R
	* @return
	*/
	public int countPrimeSetBits(int L, int R) {
	if (L > R) {
	return 0;
	}
	// core logic
	int counter = 0;
	for (int i = L; i <= R; i++) {
	if (isPrime(numberOfBits(i))) {
	counter++;
	}
	}
	return counter;
	}
	private int numberOfBits(int i) {
	int counter = 0;
	while (i > 0) {
	counter += i % 2;
	i /= 2;
	}
	return counter;
	}
	private static HashSet<Integer> primeSet = new HashSet<>();
	static {
	{
	primeSet.add(2);
	primeSet.add(3);
	primeSet.add(5);
	primeSet.add(7);
	primeSet.add(11);
	primeSet.add(13);
	primeSet.add(17);
	primeSet.add(19);
	primeSet.add(23);
	primeSet.add(29);
	primeSet.add(31);
	}
	}
	private boolean isPrime(int i) {
	return primeSet.contains(i);
	}
	}

view raw 762. Prime Number of Set Bits in Binary Representation.java hosted with ❤ by GitHub

LC 763. Partition Labels - Weekly Contest 67 - LeetCode

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Note:

S will have length in range [1, 500].
S will consist of lowercase letters ('a' to 'z') only.


这题要求最多的partition。
那么我们从左到右遍历一遍，用贪心算法。
能分马上分。除非这个字母在后边还出现而不可分离。
那么聪明的读者可能想到了，我怎么知道这个/些字符在后边还有没有，有的话在多后？
我这里采用的是先扫一遍用HashMap把每个char的起始坐标给缓存起来，
第二遍直接查缓存，进而得出结果。

时间复杂度就是O(n)

	class Solution {
	/**
	* @param S
	* @return
	*/
	public List<Integer> partitionLabels(String S) {
	if (S == null) {
	return new LinkedList<>();
	}
	// core logic
	HashMap<Character, Pair> lookup = new HashMap<>();
	for (int i = 0; i < S.length(); i++) {
	if (lookup.containsKey(S.charAt(i))) {
	lookup.get(S.charAt(i)).end = i;
	} else {
	lookup.put(S.charAt(i), new Pair(i, i));
	}
	}
	LinkedList<Integer> ends = new LinkedList<>();
	for (int i = 0; i < S.length(); ) {
	int end = Math.max(i, lookup.get(S.charAt(i)).end);
	while (i < end) {
	i++;
	end = Math.max(end, lookup.get(S.charAt(i)).end);
	}
	ends.add(end + 1);
	i++;
	}
	LinkedList<Integer> results = new LinkedList<>();
	results.add(ends.get(0));
	for (int i = 1; i < ends.size(); i++) {
	results.add(ends.get(i) - ends.get(i - 1));
	}
	return results;
	}
	private class Pair {
	int start;
	int end;
	public Pair(int start, int end) {
	this.start = start;
	this.end = end;
	}
	@Override
	public String toString() {
	return "Pair{" +
	"start=" + start +
	", end=" + end +
	'}';
	}
	}
	}

view raw LC 763. Partition Labels.java hosted with ❤ by GitHub