Lexi's Leetcode solutions

Archive for November 18th, 2013

这题其实和robot一样,每个点取决于从上到自己和从左上角到自己哪个小,但是一变成一维dp就做了好久。主要是因为这个不是取决于头顶和左边了,而是头顶和左上角,于是需要一个临时数组。

public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
    int res = Integer.MAX_VALUE;
    int[] d = new int[triangle.get(triangle.size() - 1).size()];
    d[0] = triangle.get(0).get(0);
    for (int i = 1; i < triangle.size(); i++) {
        int rowSize = triangle.get(i).size();
        int[] tmp = new int[rowSize];
        for (int j = 0; j < rowSize; j++)
            tmp[j] = d[j];
        for (int j = 0; j < triangle.get(i).size(); j++) {
            int fromAbove = j < rowSize - 1 ? d[j] : Integer.MAX_VALUE;
            int fromUpperLeft = j > 0 ? tmp[j - 1] : Integer.MAX_VALUE;
            d[j] = Math.min(fromAbove, fromUpperLeft) + triangle.get(i).get(j);
        }
    }
    for (int i = 0; i < d.length; i++) {
        res = Math.min(res, d[i]);
    }
    return res;
}
Tags:

还是两个map,一个want, 一个has,i指当前window的开头,j指结尾;want满足了的时候就试试能不能从i处删点什么。写了25分钟然后各种debugger,这题还得重做。

public String minWindow(String S, String T) {
    Map<Character, Integer> has = new HashMap<Character, Integer>();
    Map<Character, Integer> want = new HashMap<Character, Integer>();
    String res = S + S;
    char[] s = S.toCharArray();
    char[] t = T.toCharArray();
    for (int i = 0; i < t.length; i++) {
        want.put(t[i], want.get(t[i]) == null ? 1 : want.get(t[i]) + 1);
        has.put(t[i], 0);
    }
    int i = 0;
    for (int j = i; j < s.length; j++) {
        if (want.containsKey(s[j])) {
            has.put(s[j], has.get(s[j]) + 1);
            if (satisfy(has, want)) {// satisfies everything nows, try move i
                while (!want.containsKey(s[i]) || has.get(s[i]) > want.get(s[i])) { //move i until not movable
                    if (want.containsKey(s[i]) && has.get(s[i]) > want.get(s[i]))
                        has.put(s[i], has.get(s[i]) - 1); 
                    i++;
                }
                String currWindow = S.substring(i, j + 1);
                res = res.length() > currWindow.length() ? currWindow : res;
            }
        }
    }
    return res.length() > S.length() ? "" : res;
}
private boolean satisfy( Map<Character, Integer> has, Map<Character, Integer> want) {
    for (Character c : want.keySet()) {
        if (has.get(c) < want.get(c))
            return false;
    }
    return true;
}
Tags: ,

如果两个field没关系,可以生成两个锁,这样update c1必须是synchronized, c2也是。但是要是直接synchronize两个函数,说明update c1的时候c2也得干瞅着,浪费了。就跟reader writer类似,read的时候另一个reader明明也可以read的,但要是完全上锁,则read, write都要等别人了。

public class Foo {
ReentrantLock L1 = new ReentrantLock();
ReentrantLock L2 = new ReentrantLock();
int c1, c2;

public void incrementC1 {
synchronized(L1) {
c1++;
}
}

public void incrementC2 {
L2.lock();
c2++;
L2.unlock();
}
}

 

一种用lock,一种用synchronized object的区别就是,用lock的可以手动处理c2++ throw exception的情况,而用synchronized出了scope索就自动丢了。


Blog Stats

  • 222,235 hits
November 2013
M T W T F S S
 123
45678910
11121314151617
18192021222324
252627282930