Lexi's Leetcode solutions

Archive for October 19th, 2013

这个题挺吓人的,后来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;
}

这个题是非常常见的面试题,自己试着implement了两种方法,一个O(logn),一个O(n),但是写起来都不是很简洁。

O(n)的方法:binary search by start,找到一个要insert的位置(start1<start<=start2),取那个大的start2(因为它肯定会被start给replace掉,start1则不一定)。插入这个新interval,然后从头到尾检查overlap(两个参数无论谁前谁后都能用这个helper查出来),有就merge,不断吞噬overlap的。代码写起来有点长,不过思路非常清晰,不用考虑任何边界条件(什么a.start <= b.end…那些都烦死人了)。interview的时候可以写这种,因为binary search那段可能都不让你写。

还有一个trick是用iterator可以直接修改正在iterate的list,不会报modification exception,第一次用,很方便。

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    int insertPosition = insertByStart(intervals, newInterval.start, 0, intervals.size() - 1);
    intervals.add(insertPosition, newInterval);
    Iterator<Interval> it = intervals.iterator();
    Interval prev = it.next();
    while (it.hasNext()) {
        Interval curr = it.next();
        if (overlap(prev, curr)) {
            prev.start = Math.min(prev.start, curr.start);
            prev.end = Math.max(prev.end, curr.end);
            it.remove();
        } else {
            prev = curr;
        }
    }
    return intervals;
}
private int insertByStart(ArrayList<Interval> intervals, int x, int p, int q) {
    if (p > q)
        return p;
    int mid = (p + q) / 2;
    if (intervals.get(mid).start < x) {
        return insertByStart(intervals, x, mid + 1, q);
    } else {
        return insertByStart(intervals, x, p, mid - 1);
    }
}
private boolean overlap(Interval a, Interval b) {
    return within(a.start, b) || within(a.end, b) || within(b.start, a) || within(b.end, a);
}
private boolean within(int v, Interval b) {
    return v >= b.start && v <= b.end;
}

另一种方法是binary search,找出要start属于的位置,end属于的位置。但是很不好写,需要判断那些this.start >=that.end之类的,就更长了。回头看看能不能写简洁点。

Tags: , ,

这题上来没法下手,咬牙看了半天用dfs写出了个差不多的,最后卡在两个list merge上。实在看不出规律(后来发现是自己例子都写错了!!),上网一查,大神回复:

假设有n-1的答案为:G0, G1, …, Gn,想得到n的答案,只需要在G0…Gn左边加上一个0,再把G0…Gn颠倒顺序,在左边加上一个1即可。比如n=3(在分界线上倒映):

000
001
011
010
---
110
111
101
100

用dfs可以每次求出左边是0,然后求出左边是1的,合一起就是了。两个教训:

  1. 这种数学题找规律,千万别自己把例子写错了。那样打死也看不出规律的。
  2. 拿到一题往死里想个10分钟总能想出点眉目的,别放弃。
public ArrayList<Integer> grayCode(int n) {
    if (n == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        return list;
    }
    return getGrayCode(n - 1);
}
private ArrayList<Integer> getGrayCode(int pos) {
    if (pos == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        return list;
    }
    ArrayList<Integer> result = new ArrayList<Integer>();
    ArrayList<Integer> startsWithZero = getGrayCode(pos - 1);
    ArrayList<Integer> startsWithOne = new ArrayList<Integer>();
    for (int i = startsWithZero.size() - 1; i >= 0; i--) {
        startsWithOne.add(startsWithZero.get(i) + (1 << pos));
    }
    result.addAll(startsWithZero);
    result.addAll(startsWithOne);
    return result;
}

不让用*, /, %号做整数除法。基本只能bit了。但是bit操作都是跟2有关的,所以到最后还得不断缩小范围,好能贴近结果。

算法:a / b

  1. a本来是想一直-b,然后减到<0了,算counter。但是这样慢,所以类似c++ vector的思路,每次发现还没减没,那减数就翻倍(b <<= 1)
  2. 然后到了一定程度,b实在太大了,大于a剩余的部分了,那么就停止。然后剩下的a再一点点开始减,b回归成最开始的值,重做这两步。

重点是一旦超过,b应该不要一下回到原始值,而是应该一点一点/2这样做。最刁钻的地方是test case全是各种Integer.MINVALUE之类的,搞得各种溢出,然后才发现Math.abs(MIN_VALUE)其实还是-2147483648(坑爹呢吧abs还是负数),而不是2147483648。

下面的解法是能跑过的。因为测试数据出现了-2147483648,还不能把它转成正的(2147483648就溢出了),所以直接全转换成long(64位),跑一遍就过了。

public int divide(int dividend, int divisor) {
    if (dividend == 0)
        return 0;
    if (divisor == 1)
        return dividend; //纯粹是为了防止超时
    boolean positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);
    long absDividend = dividend < 0 ? 0 - (long) dividend : (long) dividend;
    long absDivisor = divisor < 0 ? 0 - (long) divisor : (long) divisor;
    int result = dividePositive(absDividend, absDivisor, absDivisor);
    return positive ? result : 0 - result;
}
private int dividePositive(long p, long q, long originalDivisor) { // p / q
    if (p < q)
        return 0; //这个十分必要,否则会因为p > 0而直接下一层递归,pq永远不变,死循环了就。
    int result = 0;
    int e = 0;
    while (p >= q) { //等于应该也进去。
        result += 1 << e;
        p -= q;
        q = q << 1;
        e++;
    }
    return p > 0 ? result + dividePositive(p, originalDivisor, originalDivisor) : result;
 }
Tags: , ,

树的dfs变形,还是两个list来回倒。但是这题上来就写还不行,真心得在纸上画一画才能看出来规律。一开始觉得keep一个boolean,正常顺序就加后面,逆序就加前面呗,但是没注意到parent其实很可能已经不是原来顺序的了。画个四层的树就能看出来咋回事了。还有一个小bug就是最开始的boolean reverse应该是true,因为他代表了“parent下面一层要什么顺序”,而不是parent本身是什么顺序。所以还是,变量的物理意义一定要搞清再写!

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (root == null)
        return result;
    ArrayList<TreeNode> parents = new ArrayList<TreeNode>();
    boolean reverse = true;//first children line is reversed
    parents.add(root);
    while (!parents.isEmpty()) {
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        for (int i = parents.size() - 1; i >= 0; i--) {
            TreeNode parent = parents.get(i);
            if (!reverse) {// the children list wants to be normal order
                if (parent.left != null)
                    children.add(parent.left);
                if (parent.right != null)
                    children.add(parent.right);
            } else { //the children wants to be right to left
                if (parent.right != null)
                    children.add(parent.right);
                if (parent.left != null)
                    children.add(parent.left);
            }
        }
        result.add(convertToIntegerList(parents));
        reverse = !reverse;
        parents = children;
    }
    return result;
}
Tags: ,

有点后悔,这个题当时看了就好了,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;
	}