Lexi's Leetcode solutions

Archive for the ‘leetcode’ Category

遇见这种matrix题就腿发软,bf给讲了个四条边bound的方法,立刻15分钟bug free了。高兴够呛。

public int[][] generateMatrix(int n) {
    int[][] res = new int[n][n];
    int k = 1;
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    while (left < right && top < bottom) {
        for (int j = left; j < right; j++) {
            res[top][j] = k++;
        }
        for (int i = top; i < bottom; i++) {
            res[i][right] = k++;
        }
        for (int j = right; j > left; j--) {
            res[bottom][j] = k++;
        }
        for (int i = bottom; i > top; i--) {
            res[i][left] = k++;
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    if (n % 2 != 0)
        res[n / 2][n / 2] = k;
    return res;
}
Advertisements
Tags:

思路:

  1. 因为没有random access,所以用in order的方式,一个一个遍历element,然后assign给parent
  2. 平时正常array convert bst都是用pre order的方式,root算好,然后left=.., right =…
  3. 一般你做树的bottom up是post order,left做出来,right做出来,root取决于这两个值
  4. 这里为什么要in order呢? 左,中,右的方式,正好是sorted。所以每次做完子树,然后下一个节点就是下一个位置。但是什么时候是个头呢,因为h.next会一直存在的,但是你的子树怎么知道什么时候返回到上一层?所以就要用p, q两个指针了,p代表当前sub list的头,q是尾。但是不要真的用他们来random access,就是用来stop就行了。
public TreeNode sortedListToBST(ListNode head) {
    int len = 0;
    ListNode dummy = head;
    while (dummy != null) {
       len++;
    dummy = dummy.next;
    }
    ListNode[] curr = new ListNode[1];
    curr[0] = head;
    return convert(curr, 0, len - 1);
}
private TreeNode convert(ListNode[] curr, int p, int q) {
    if (p > q)
        return null;
    int mid = (p + q) / 2;
    TreeNode left = convert(curr, p, mid - 1);
    TreeNode root = new TreeNode(curr[0].val);
    curr[0] = curr[0].next;
    TreeNode right = convert(curr, mid + 1, q);
    root.left = left;
    root.right = right;
    return root;
}
Tags: , , ,

这就是典型的try and fail,尼玛谁知道什么算是数什么不算啊?让我用眼睛看我也不知道啊!总之,试出来的规则是这样的:

  • AeB代表A * 10 ^ B
  • A可以是小数也可以是整数,可以带正负号
  • .35, 00.神马的都算valid小数;就”.”单独一个不算
  • B必须是整数,可以带正负号
  • 有e的话,A,B就必须同时存在

算法就是按e把字符串split了,前面按A的法则做,后面按B做。

public boolean isNumber(String s) {
    s = s.trim(); 
    if (s.length() > 0 && s.charAt(s.length() - 1) == 'e')
        return false; //avoid "3e" which is false
    String[] t = s.split("e");
    if (t.length == 0 || t.length > 2)
        return false;
    boolean res = valid(t[0], false);
    if (t.length > 1)
        res = res && valid(t[1], true);
    return res;
}
private boolean valid(String s, boolean hasDot) {
    if (s.length() > 0 && (s.charAt(0) == '+' || s.charAt(0) == '-')) //avoid "1+", "+", "+."
    s = s.substring(1);
    char[] arr = s.toCharArray();
    if (arr.length == 0 || s.equals("."))
        return false;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == '.') {
            if (hasDot)
                return false;
            hasDot = true;
        } else if (!('0' <= arr[i] && arr[i] <= '9')) {
            return false;
        }
    }
    return true;
}
Tags:

这个题要用反证法来理解。算法:

  1. 从i开始,j是当前station的指针,sum += gas[j] – cost[j] (从j站加了油,再算上从i开始走到j剩的油,走到j+1站还能剩下多少油)
  2. 如果sum < 0,说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢?假设能从k (i <=k<=j)走,那么i..j < 0,若k..j >=0,说明i..k – 1更是<0,那从k处就早该断开了,根本轮不到j。
  3. 所以一旦sum<0,i就赋成j + 1,sum归零。
  4. 最后total表示能不能走一圈。
  5. 这个题算法简单,写起来真是够呛。对数组一快一慢双指针的理解还是不行。注意千万不能出现while (i < 0) { i++, A[i]}这种先++然后取值的情况,必须越界。
public int canCompleteCircuit(int[] gas, int[] cost) {
    int i = 0, j = 0;
    int sum = 0;
    int total = 0;
    while (j < gas.length) {
        int diff = gas[j] - cost[j];
        if (sum + diff < 0) {
            i = j + 1;
            sum = 0;
        } else {
            sum += diff;
        }
        j++;
        total += diff;
    }
    return total >= 0 ? i : -1;
}

 

这题其实和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: ,

给一个String[] L,里面可以有重复,在S里找能包括所有L且都只出现一次的window的start。比如foobarthebarfooman, L={foo, bar}, return 0, 9.
这题正经做了一段时间。

public ArrayList<Integer> findSubstring(String S, String[] L) {
    final Map<String, Integer> need = new HashMap<String, Integer>();
    for (int i = 0; i < L.length; i++) {
        need.put(L[i], need.get(L[i]) == null ? 1 : need.get(L[i]) + 1);
    }
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < L[0].length(); i++) {
        populateResult(result, S, L, i, need);
    }
    return result;
}
private void populateResult(ArrayList<Integer> result, String S, String[] L, 
                            int start, final Map<String, Integer> need) {
    int k = L[0].length();
    HashMap<String, Integer> has = new HashMap<String, Integer>();
    for (int end = start; end <= S.length() - k; end += k) {
        String sub = S.substring(end, end + k);
        if (need.containsKey(sub)) {
            while (has.get(sub) == need.get(sub)) {
                String tmp = S.substring(start, start + k);
                has.put(tmp, has.get(tmp) - 1);
                start += k;
            }
            has.put(sub, has.get(sub) == null ? 1 : has.get(sub) + 1);
            if (end - start + k == L.length * L[0].length())
                result.add(start);
        } else {
            has.clear();
            start = end + k;
        }
    }
}
Tags: ,