Posts Tagged ‘1WayDP’
- In: leetcode | summery
- Leave a Comment
- d[i][j]表示从(0, 0)到(i, j)有几种走法，因为只能从上面来或从左边来，所以每次计算只需要d[i – 1][j]和d[i, j – 1]，左上角的全都浪费了。
- f[i]表示从(0,0)到(当前row, j)有几种走法，上面来的就是自己，左边来的已经算好了，所以 f[j] = f[j] + f[j – 1];
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
// one way DP, f[i] means from (0, 0) to (currRow, i) has how many ways
int f[] = new int[n];
f[0] = obstacleGrid[0][0] > 0 ? 0 : 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) { //comes from above or left
if (obstacleGrid[i][j] > 0) {
f[j] = 0;
} else {
if (j == 0) //first col only from above
f[j] = f[j];
else
f[j] = f[j] + f[j - 1];
}
}
}
return f[n - 1];
}
[leetcode] Palindrome Partitioning 2 | 一个String最少切几刀能让分成的substring全是palindrome
Posted on: October 20, 2013
非常非常难，用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。
算法：
- 首先把每个substring是不是palindrome先二维dp的做出来，参见上一题的分析。其实这一步可以合在下一步里，但是下一步本身的logic就够难想了，所以这里分开来写。
- 一维dp（为神马是一维啊！！头一次看这样的一维啊！！一维dp却是两层循环啊卧槽！！！），d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
- 把d[i]先赋成最大值。
- i从后往前，然后j在每个i处从前往后。这样做就能保证在i处，i + 1…j – 1的所有两两combination（中间的小节substring）都已经算出来了，就能用了。如果str[i, j]是个palindrome，那么可以在j 和j + 1中间切一刀，这样的#就是d[j + 1] + 1（[i..j], 一刀, [j + 1..本来有几刀]）。这样切法可能就比之前算的d[i]小了，于是update。
public int minCut(String s) {
int n = s.length();
boolean[][] isPalin = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) { // i is always <= j
for (int j = i; j < n; j++) {
boolean isPalindrome = s.charAt(i) == s.charAt(j)
&& (j - i < 2 || isPalin[i + 1][j - 1]);
isPalin[i][j] = isPalindrome;
}
}
int[] d = new int[n];
// initialize as cut between every letter
for (int i = 0; i < n; i++) {
d[i] = n - 1 - i;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (isPalin[i][j]) {
if (j == n - 1)
d[i] = 0;
else
d[i] = Math.min(d[i], d[j + 1] + 1);
}
}
}
return d[0];
}
- In: leetcode
- 6 Comments
括号题也不是只用stack才能做，这题是算长度，所以stack那种一match就俩一起pop了的方式就不适合了。求极值，一维dp最好使。
- d[i]: 以i开头的最长valid parentheses有多长。
- d[i] =
- if (str[i] == ‘)’)，以右括号开头必定invalid，d[i] = 0
- if (str[i] == ‘(‘)，以左括号开头
- 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾，所以我们想catch((…))这种情况。j = i + 1 + d[i + 1]，正好就是str[i]后面越过完整sequence的下一个，若是右括号，d[i] = 2 + d[i + 1]
- 除此之外，还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况，如((..))()()()。所以d[i]还要再加上j后面那一段的d[j + 1]
这个定义和最长公共字串那题的定义类似，都是“以某个固定位置开始/结束”。看两头的方式又像palindrome。从后往前的一维dp也不常见。挺好玩的，一下复习好多东西。
public int longestValidParentheses(String s) {
if (s.length() == 0)
return 0;
int maxLen = 0;
int[] d = new int[s.length()];
// d[i] means substring starts with i has max valid lenth of d[i]
d[s.length() - 1] = 0;
for (int i = s.length() - 2; i >= 0; i--) {
if (s.charAt(i) == ')')
d[i] = 0;
else {
int j = (i + 1) + d[i + 1];
if (j < s.length() && s.charAt(j) == ')') {
d[i] = d[i + 1] + 2; //(()())的外包情况
if (j + 1 < s.length())
d[i] += d[j + 1];//()()的后面还有的情况
}
}
maxLen = Math.max(maxLen, d[i]);
}
return maxLen;
}
—————————-用stack的做法———————————–
- stack里面装的一直是“还没配好对的那些可怜的括号的index”
- 是'(‘的时候push
- 是’)’的时候，说明可能配对了；看stack top是不是左括号，不是的话，push当前右括号
- 是的话，pop那个配对的左括号，然后update res：i和top的（最后一个配不成对的）index相减，就是i属于的这一段的当前最长。如果一pop就整个栈空了，说明前面全配好对了，那res就是最大=i+1
public int longestValidParentheses(String s) {
int res = 0;
Stack<Integer> stack = new Stack<Integer>();
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(') {
stack.pop();
if (stack.isEmpty())
res = i + 1;
else
res = Math.max(res, i - stack.peek());
} else {
stack.push(i);
}
}
return res;
}
- In: leetcode
- 5 Comments
有点后悔，这个题当时看了就好了，T家真的就考了类似的。要是看了就不至于现场出现当天同时买卖那个bug；从后往前scan array也不会那么生疏。。G家也是，要是看了CC150那道题就不会挂在拓扑排序上。没事，记住教训就好了——题是不能越过去的，越是skip的越有考的可能。
这个题一开始是二分法做的，每次切一刀然后左边O(n)做一次右边O(n)做一次，整体是O(n^2)，超时。正确方法是一维dp从左到右扫一遍，再从右到左扫一遍，然后两次加和。
两个一维数组的定义一定要搞清，onsite的时候就栽在这上面了！
- d[i]: [0…i]这段时间的买卖一次的最大利润。所以i应该从1开始。
- f[i]: [i…n – 1]这段时间的买卖一次的最大利润。所以i应该最大n – 2。
- 然后就看出问题了——两个i不能同步，否则就当天买卖了。最后加和的时候要错开。
- 因为“最多买卖两次”， 所以还要包括买卖一次的情况。用d[n-1]就是[0…n-1]可以表达这种情况。
public int maxProfit(int[] prices) {
if (prices.length == 0)
return 0;
int[] d = buildMaxProfitFromStart(prices);
int[] f = buildMaxProfitFromEnd(prices);
int maxProfit = d[prices.length - 1];
for (int i = 0; i < prices.length - 1; i++) {
maxProfit = Math.max(maxProfit, d[i] + f[i + 1]);
}
return maxProfit;
}
private int[] buildMaxProfitFromEnd(int[] arr) {
int[] f = new int[arr.length];
f[arr.length - 1] = 0;
int max = arr[arr.length - 1];
int maxProfit = 0;
for (int i = arr.length - 2; i >= 0; i--) {
maxProfit = Math.max(maxProfit, max - arr[i]);
max = Math.max(max, arr[i]);
f[i] = maxProfit;
}
return f;
}
private int[] buildMaxProfitFromStart(int[] arr) {
int[] d = new int[arr.length];
d[0] = 0;
int min = arr[0];
int maxProfit = 0;
for (int i = 1; i < arr.length; i++) {
maxProfit = Math.max(maxProfit, arr[i] - min);
min = Math.min(min, arr[i]);
d[i] = maxProfit;
}
return d;
}
[leetcode] Climb Stairs | 小孩上楼梯
Posted on: October 8, 2013
- In: classic | leetcode
- Leave a Comment
这个经典题居然submit了4遍才过，给33.8%的通过率拖后腿了。原因是忘记d[i]表示什么了就开始瞎写。就算做过的经典题，当场再想一想又有什么不好的？
d[i]表示到第i级台阶有几种走法。d[0]必须是1，这个是用i=1试出来的。最后返回d[n]不是d[n – 1]！
public int climbStairs(int n) {
if (n == 0)
return 0;
int[] d = new int[n + 1];
d[0] = 1;
for (int i = 1; i <= n; i++) {
d[i] += d[i - 1];
if (i >= 2)
d[i] += d[i - 2];
}
return d[n];
}
只用三个变量，不用array的做法（既然只看d[i – 1], d[i -2]往前看两个，那keep三个变量就够了。
public int climbStairs(int n) {
if (n == 0)
return 0;
int prevPrev = 0;
int prev = 1;
for (int i = 1; i <= n; i++) {
int curr = 0;
curr += prev;
if (i >= 2)
curr += prevPrev;
prevPrev = prev;
prev = curr;
}
return prev;
}
Tags: 1WayDP
[leetcode] Candy | 给小孩子分糖
Posted on: October 8, 2013
- In: leetcode
- 4 Comments
一维DP。
- d[i] 是给第i个小孩最少几块糖
- rank[i] > rank[i – 1]，必须比前一个多给一块，d[i] = d[i – 1] + 1
- rank[i] == rank[i – 1]，两个排名一样，第二个就给一块就行了, d[i] = 1
- rank[i] < rank[i – 1]，比上一个排名低，应该少给一块，但是若上一个已经只给一块了，就得往前推一个一个多给。推到什么时候为止呢？若排名比下一个高，糖还一样多，就得再给；直到这个关系打破（排名一样或比下一个还低，或是糖已经满足关系）就不用再往前推了。
public int candy(int[] ratings) {
if (ratings.length == 0)
return 0;
int[] d = new int[ratings.length];
d[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] == ratings[i - 1])
d[i] = 1;
else if (ratings[i] > ratings[i - 1])
d[i] = d[i - 1] + 1;
else {// should give less candy than prev child
d[i] = 1;
if (d[i - 1] == 1) {
int j = i;
while (j > 0 && ratings[j - 1] > ratings[j] && d[j - 1] == d[j]) {
//only push backwards when ratings diff but candy are same
d[j - 1]++;
j--;
}
}
}
}
int sum = 0;
for (int i = 0; i < ratings.length; i++) {
sum += d[i];
}
return sum;
}
Tags: 1WayDP
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"], the solution is ["cats and dog", "cat sand dog"]
这题是cache里面存数组: Map<Integer, List<String>> cache，和上题思路一样，不过边界条件不好想：
- 找不到的时候是返回空list还是null?
- 找到结尾正好成功了(i == string.len)的时候，返回空还是null?
这两种情况必须区分。因为要在每个list entry里生成新的substring，所以还是找不到的时候返回空list比较好（空的正好不用进loop了）；而找到头的时候，刚好check null，然后把当前词尾返回，catch了最后一个词不用加” “的情况。
public ArrayList<String> wordBreak(String s, Set<String> dict) {
if (s == null || s.length() == 0)
return new ArrayList<String>();
HashMap<Integer, ArrayList<String>> cache = new HashMap<Integer, ArrayList<String>>();
return split(s, dict, 0, cache);
}
private ArrayList<String> split(String s, Set<String> dict, int i, HashMap<Integer, ArrayList<String>> cache) {
if (i == s.length())
return null;
if (cache.containsKey(i))
return cache.get(i);
ArrayList<String> result = new ArrayList<String>();
for (int j = i; j < s.length(); j++) {
String curr = s.substring(i, j + 1);
if (dict.contains(curr)) {
ArrayList<String> rest = split(s, dict, j + 1, cache);
if (rest == null) {
StringBuilder sb = new StringBuilder();
sb.append(curr);
result.add(sb.toString());
} else {
for (String tail : rest) {
StringBuilder sb = new StringBuilder();
sb.append(curr).append(" ").append(tail);
result.add(sb.toString());
}
}
}
}
cache.put(i, result);
return cache.get(i);
}
DP是O(n2)的解法。新开一个数列B，B[i]表示以A[i]结尾的LIS的最大长度。每次在i处往前看，若j<i，则以i结尾的就只少>=B[j] + 1。
public int getLIS(int[] A) {
int[] B = new int[A.length];
int max = 1;
B[0] = 1;
for (int i = 1; i < A.length; i++) {
B[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (A[i] > A[j]) {
B[i] = Math.max(B[i], B[j] + 1);
max = Math.max(B[i], max);
}
}
}
return max;
}
Decode Ways
Posted on: July 17, 2013
A message containing letters from A-Z is being encoded to numbers using the A=1, B=2.. Z=26 mapping， 问给一个全是digit的string，有几种decode成字母组合的方式。比如Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
这个题一开始是正常做的，然后就挂掉大的test case了。其实一维数组，问“几种ways”，肯定是要dp的。这题类似于小孩上楼梯，求d[i]有两种情况：
- 当前这个single digit arr[i]是在1~9之内，说明能组成一个字母，则当前的组合方式(d[i – 1], arr[i])成功，则d[i] = d[i – 1]。不成功，则以i结尾的string没有组合方式，d[i] = 0
- 当前这个arr[i]是能组成一个10~26的两位数的第二个digit。这样的话，当前的组合(d[i -2], “arr[i – 1]arr[i]”）成功，则d[i] += d[i – 2]。不成功也不归零，因为可能之前single digit的方式成了，所以不动这个d[i]就行了。
public int numDecodings(String s) {
if (s.length() == 0)
return 0;
int[] d = new int[s.length()];
if (s.charAt(0) - '0' != 0)
d[0] = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) - '0' != 0)
d[i] = d[i - 1];
else
d[i] = 0;
if (canFormTwo(s, i - 1, i + 1))
d[i] += i > 1 ? d[i - 2] : 1;
}
return d[s.length() - 1];
}
boolean canFormTwo(String s, int i, int j) {
if (j > s.length())
return false;
Integer firstTwo = Integer.valueOf(s.substring(i, j));
return firstTwo > 9 && firstTwo <= 26;
}
好像其实不用这么大的空间，应该两个变量就够了，一个prev, 一个prevprev，但是没想好，而且懒得想了。以后再说。
Tags: 1WayDP
Lexi's Leetcode solutions 