Dungeon Game

Keys:

  1. Health point must be at a minimum of 1, cannot be zero, otherwise the knight dies immediately.
  2. The dp matrix has to be filled from bottom right.

https://github.com/fishercoder1534/fishercoderLeetcode/blob/master/HARD/src/hard/DungeonGame.java

Advertisements

Russian Doll Envelopes

354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

 

Looked at this post: https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation

[TODO] completely understand it.

public int maxEnvelopes(int[][] envelopes) {
if(envelopes == null || envelopes.length == 0
|| envelopes[0] == null || envelopes[0].length != 2)
return 0;
Arrays.sort(envelopes, new Comparator<int[]>(){
public int compare(int[] arr1, int[] arr2){
if(arr1[0] == arr2[0])
return arr2[1] - arr1[1];
else
return arr1[0] - arr2[0];
}
});
int dp[] = new int[envelopes.length];
int len = 0;
for(int[] envelope : envelopes){
int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
if(index < 0)
index = -(index + 1);
dp[index] = envelope[1];
if(index == len)
len++;
}
return len;
}

 

[Leetcode] Palindrome Partitioning II

132. Palindrome Partitioning II QuestionEditorial Solution My Submissions

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

 

Looked at this post: https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36

[TODO] completely understand it.


public int minCut(String s) {
char[] c = s.toCharArray();
int n = c.length;
int[] cut = new int[n];
boolean[][] pal = new boolean[n][n];

for(int i = 0; i < n; i++) {
int min = i;
for(int j = 0; j <= i; j++) {
if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true;
min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
}
}
cut[i] = min;
}
return cut[n - 1];
}

[Leetcode] Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV QuestionEditorial Solution My
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

 

Looked at this post: https://discuss.leetcode.com/topic/8984/a-concise-dp-solution-in-java

[TODO] completely understand it.

public int maxProfit(int k, int[] prices) {
int len = prices.length;
if (k >= len / 2) return quickSolve(prices);

int[][] t = new int[k + 1][len];
for (int i = 1; i <= k; i++) {
int tmpMax = -prices[0];
for (int j = 1; j < len; j++) {
t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
tmpMax = Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
}
}
return t[k][len - 1];
}

private int quickSolve(int[] prices) {
int len = prices.length, profit = 0;
for (int i = 1; i < len; i++)
// as long as there is a price gap, we gain a profit.
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;
}