Lexi's Leetcode solutions

Posts Tagged ‘EndWith

这个题挺吓人的,后来bf给讲明白了然后记得葫芦半片的,今天自己重新想了想,还是做出来了也通过了。不过是O(M * M * N的速度,没有网上说的O(M*N),忍了,反正也能pass oj.

算法:

  1. 先用dp求一个新矩阵,d[i][j]表示以(i, j)结尾有几个连续1(在当前row)。
  2. 然后遍历这个新矩阵,在每个cell,都看看“宽度是d[i][j]的矩阵最多能有多高?“,也就是往上expand到宽度变窄为止,往下expand到宽度变窄为止,然后总高度×当前宽度就是d[i][j]所属于的矩阵的最大面积。这就是个O(M * N) * O(M)。

当时给讲的时候觉得这怎么是人类能想出来的呢?然后bf说你把二维降成一维怎么做,不也是找以当前结束的1有多长吗。然后恍然大悟,这题还是有救的。题目本身写起来细节不多,不容易出bug,两遍就过了很开心~

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0)
        return 0;
    int res = 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] d = new int[m][n];
    for (int i = 0; i < m; i++) {
        d[i][0] = matrix[i][0] - '0';
        for (int j = 1; j < n; j++) {
            d[i][j] = matrix[i][j] == '1' ? d[i][j - 1] + 1 : 0;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res = Math.max(res, expand(d, i, j));
        }
    }
    return res;
}
private int expand(int[][] d, int I, int J) {
    int height = 0;
    int width = d[I][J];
    //go up
    for (int i = I - 1; i >= 0; i--) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    //go down
    for (int i = I; i < d.length; i++) {
        if (d[i][J] >= width) {
            height++;
        } else {
            break;
        }
    }
    return width * height;
}
Advertisements

括号题也不是只用stack才能做,这题是算长度,所以stack那种一match就俩一起pop了的方式就不适合了。求极值,一维dp最好使。

  • d[i]: 以i开头的最长valid parentheses有多长。
  • d[i] =
    • if  (str[i] == ‘)’),以右括号开头必定invalid,d[i] = 0
    • if (str[i] == ‘(‘),以左括号开头
      1. 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾,所以我们想catch((…))这种情况。j = i + 1 + d[i + 1],正好就是str[i]后面越过完整sequence的下一个,若是右括号,d[i] = 2 + d[i + 1]
      2. 除此之外,还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况,如((..))()()()。所以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的做法———————————–

  1. stack里面装的一直是“还没配好对的那些可怜的括号的index”
  2. 是'(‘的时候push
  3. 是’)’的时候,说明可能配对了;看stack top是不是左括号,不是的话,push当前右括号
  4. 是的话,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;
}

比如abcdefg, defmnabs,最长公共subtring是def。

又是二维DP求String的最优解。居然还是算法课作业做过,真是一点印象也木有了。

  • d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
  • d[i][j] =
    1. A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
    2. A[i] != B[j] : d[i][j] = 0//断开了,无公共后缀了

总结一下二维DP解String题的做法:

  • 一个String, d[i][j]表示A[i…j]的某个最优解
  • 两个String, d[i][j]表示A[0…i], B[0…j]的某个比较方式的最优解