Leetcode 236, 43 @ Java－CONY的世界

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

這題其實當初我想得太複雜了.....（注意！其實很多題目都是這樣，看清楚題目給的條件，有時候題目加上限制後會變得非常簡單）

如果今天是要找不知道存不存在的兩個node 那這個解法一定不行，但是這題因為是確定存在樹上的兩點node，所以就變得非常簡單

只要思考這兩個node會在樹上存在的可能組合就能找出這組的答案了

一種就是分別在左右subtree，一種就是都在同一個subtree，

左右的情形就是都存在時，那個node就是root了，而當在同一個subtree時，就是第一個相等的那個node開始return就好

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return (left != null)?left:right;
    }
}

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

這題其實一開始又想得太複雜了，一直想用很optimize的方式解，但是其實直接用array 就好了

每個digit 用 char array表示的話，就不用擔心像是overflow的問題了

注意這邊比較麻煩的是最後轉string的地方，array 的存法是index越大，代表的位元越小，所以跟直覺相反是要注意的地方

然後也因此 num1[inedx1] * num2[index2] ＝ ans[index1+index2+1] ，因為ans[index1+index2] 是拿來存進位的

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int l1 = num1.length(), l2 = num2.length(), l = l1+l2;
        char[] ans = new char[l];
        for(int index1 = l1-1; index1 >= 0; index1--) {
            for(int index2 = l2-1; index2 >=0; index2--) {
                ans[index1+index2+1] += (num1.charAt(index1) - '0')* (num2.charAt(index2) - '0'); 
               // System.out.println((index1+index2)+" "+ (num1.charAt(index1) - '0')* (num2.charAt(index2) - '0'));
            }
        }
        int index = l-1;
        while(index > 0){
            if(ans[index] > 9) {
                ans[index-1] += ans[index]/10;
                ans[index] %= 10;
            }       
            index--;
        }
        StringBuilder s = new StringBuilder();
        index=0;
        while(ans[index] == 0) index++;
        for(; index < l; index++)
            s.append((char)(ans[index]+'0'));
        return s.toString();
    }
}