Java日记2018-05-23

今天算是个里程碑了

第一题 股票的最大利润
使用贪心策略，假设第 i 轮进行卖出操作，买入操作价格应该是 i 之前并且价格最低

public class maxProfit {
    public static int max(int[] arr) {
        if(arr.length==0) return 0;
        int maxprofit=0;
        int min = arr[0];
        //循环从1开始，因为要使用最低的买入策略arr[0]
        for(int i=1;i<arr.length;i++) {
            //找到i-1次前的最小买入点，与当前的买入点
            min = Math.min(min, arr[i]);
            //找到i-1次前的最大买入，与当前的买入的比较
            maxprofit=Math.max(maxprofit, arr[i]-min);
        }
        
        return maxprofit;
    }
    
    public static void main(String[] args) {
        int[] arr={3,2,5,7,9,1,0,3,5,12,7};
        max(arr);
        System.out.println(max(arr));
    }

}

第二题 求 1+2+3+...+n

条件与 && 具有短路原则，即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。利用这一特性，将递归的返回条件取非然后作为 && 的第一个条件语句，递归的主体转换为第二个条件语句，那么当递归的返回条件为 true 的情况下就不会执行递归的主体部分，递归返回。

以下实现中，递归的返回条件为 n <= 0，取非后就是 n > 0，递归的主体部分为 sum += Sum_Solution(n - 1)，转换为条件语句后就是 (sum += Sum_Solution(n - 1)) > 0。

public static int sumf(int n) {
        int sum=n;
        boolean b = (n>0)  && ((sum+=sumf(n-1))>0);
        return sum;
    }

第三题 不用加减乘除做加法

a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。

递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。

第四题 构建乘积数组
给定一个数组 A[0, 1,..., n-1], 请构建一个数组 B[0, 1,..., n-1], 其中 B 中的元素 B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

第五题 把字符串转换成整数

第六题 树中两个节点的最低公共祖先

image.png

二叉查找树中，两个节点 p, q 的公共祖先 root 满足 p.val <= root.val && root.val <= q.val，只要找到满足这个条件的最低层节点即可。换句话说，应该先考虑子树的解而不是根节点的解，二叉树的后序遍历操作满足这个特性。在本题中我们可以利用后序遍历的特性，先在左右子树中查找解，最后再考虑根节点的解。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return root;
    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    return root;
}

image.png

在左右子树中查找两个节点的最低公共祖先，如果在其中一颗子树中查找到，那么就返回这个解，否则可以认为根节点就是最低公共祖先。

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);
    return left == null ? right : right == null ? left : root;
}