Lexi's Leetcode solutions

Archive for November 4th, 2013

算法:

  • arch代表穿过当前节点的路径(左边一支儿+自己节点+右边一支儿)。
  • 注意树的节点可以是负数,所以arch不一定是最长的。
  • 每次return以root(当前节点)开头最大的单只path sum。
  • res[]就是一个存result的reference object,java不支持c++那种直接&传reference,
    所以要么用个长度为一的数组,要么写个wrapper。还是用数组简单。
  • update res[0],用arch和以自己开头一支儿的比,谁大就把res[0] update成谁。
public int maxPathSum(TreeNode root) {
    int[] res = new int[1];
    res[0] = Integer.MIN_VALUE;
    maxPath(root, res);
    return res[0];
}
private int maxPath(TreeNode root, int[] res) {
    if (root == null)
        return 0;
    int left = maxPath(root.left, res);//左边一支儿(不算自己)
    int right = maxPath(root.right, res);
    int arch = left + right + root.val; //穿过自己
    int single = Math.max(root.val, Math.max(left, right) + root.val);
    //(算上自己)
    res[0] = Math.max(res[0], Math.max(arch, single));//update结果
    return single;
}
Tags: ,

这题太经典了,在amz wiki上见过解法,才知道可以把指数分一半,从O(n)改成O(logn)。有几个要注意的地方:

  1. 初中数学不会了。(-2)^(-3) = 1 / (-2)^3。所以正负号还是和指数是否是偶数有关。
  2. 不要分四种情况讨论,简洁的代码是如果n<0,则直接/x,因为前面算好half的也是1/something的!
  3. 要特别讨论x == 0的情况,因为后面要1/x,不想挂在这吧。
public double pow(double x, int n) {
    if (x == 0)
        return 0;
    return power(x, n);
}
private double power(double x, int n) {
    if (n == 0)
        return 1;
    double left = power(x, n / 2);
    if (n % 2 == 0) {
        return left * left;
    } else if (n < 0) {
        return left * left / x;
    } else {
        return left * left * x;
    }
}
Tags:

Blog Stats

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