Lexi's Leetcode solutions

Archive for November 23rd, 2013

[leetcode] Spiral Matrix | 把一个2D matrix用螺旋方式打印

Posted by: on: November 23, 2013

遇见这种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;
}
Tags:

Convert Sorted List to Binary Search Tree

Posted by: on: November 23, 2013

思路：

  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: , , ,

[leetcode] Valid Number

Posted by: on: November 23, 2013

这就是典型的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:

Blog Stats

  • 222,835 hits

Search

November 2013
M T W T F S S
 123
45678910
11121314151617
18192021222324
252627282930  

Blog at WordPress.com.