[2018-Interview] Hamming Distance

Original question: https://leetcode.com/problems/hamming-distance/description/

My answer: similar logic as the question "Number of 1 Bits"

class Solution {
    public int hammingDistance(int x, int y) {
        if (x == y) {
            return 0;
        }
        int dist = 0;
        while (x!=0 || y!=0) {
            int xBit = x & 1;
            int yBit = y & 1;
            if (xBit != yBit) {
                dist ++;
            }
            x = x >>> 1;
            y = y >>> 1;
        }
        return dist;
    }
}

[2018-Interview] Number of 1 Bits

Original question: https://leetcode.com/problems/number-of-1-bits/description/

My answer:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        if (n == 0) {
            return 0;
        }
        int num1Bit = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                num1Bit ++;
            }
            n = n >>> 1;
        }
        return num1Bit;
    }
}

[2018-Interview] House Robber

Original question: https://leetcode.com/problems/house-robber/description/

My answer: The key point here is that we set up a new array, robbedMaxMoney, where the "i"th element in robbedMaxMoney indicated the max Money with "i"th house must be robbed. Thus, robbedMaxMoney[i] = max(robbedMaxMoney[i - 3], robbedMaxMoney[i - 2]) + nums[i];

The above equation means that the "i" the element must be the biggest value among "i - 3" and "i - 2" plus nums[i], because "i - 1" cannot be an option. Meanwhile, [i - 4] element can add both nums[i -2] and nums[i], so we don't need to worry about [i-4], aka no need to get the biggest value among "i - 4", "i - 3" and "i - 2", as robbedMaxMoney[i-4] must be already considered in robbedMaxMoney[i-2].

Finally, the end result should be the bigger of the last 2 elementss of robbedMaxMoney , aka robbedMaxMoney[end] and robbedMaxMoney[end - 1]

class Solution {
    public int rob(int[] nums) {
        int maxMoney = 0;
        if (nums == null || nums.length == 0) {
            return maxMoney;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] robbedMaxMoney = new int[nums.length];
        // the "i"th element in robbedMaxMoney indicated the max Money

        // can be robbed with "i"th house must be robbed
        robbedMaxMoney[0] = nums[0];
        robbedMaxMoney[1] = nums[1];
        if (nums.length == 2) {
            return Math.max(robbedMaxMoney[0], robbedMaxMoney[1]);
        }
        robbedMaxMoney[2] = nums[0] + nums[2];
        for (int i = 3; i < nums.length; i ++) {
            robbedMaxMoney[i] = Math.max(robbedMaxMoney[i - 2], 

                                         robbedMaxMoney[i - 3]) + nums[i];
        }
        return Math.max(robbedMaxMoney[nums.length - 2],

                        robbedMaxMoney[nums.length - 1]);
    }
}

[2018-Interview] Maximum Subarray

Original question: https://leetcode.com/problems/maximum-subarray/description/

My answer:

public class Solution {
    public int maxSubArray(int[] nums) {
        int globalMax = nums[0];
        int localMax = nums[0];
        for (int i = 1; i < nums.length; i ++) {
            // localMax is the bigger value which includes "i"th number, so that the globalMax can be the result of contiguous subarray
            localMax = Math.max(nums[i], localMax + nums[i]);
            globalMax = Math.max(globalMax, localMax);
        }
        return globalMax;
    }
}

[2018-Interview] Best Time to Buy and Sell Stock

Original question: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

My answer: basically, I think the key logic is to always looking for the best result by index i, i.e. best profit by day "i". Once i reaches the end of array prices, it becomes the best result for all. Let's say the best profit by day "i" is maxProfit, then for day "i + 1", the maxProfit should be MAX(maxProfit, prices[i + 1] - minPrice). The minPrice is the min price by day "i"

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        if (prices == null || prices.length < 2) {
            return maxProfit;
        }
        int minPrice = prices[0];
        for (int i = 1; i < prices.length ; i ++) {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            minPrice = Math.min(prices[i], minPrice);
        }
        return maxProfit;
    }
}

[2018-Interview] Climbing Stairs

Original question: https://leetcode.com/problems/climbing-stairs/description/

Answer: basic logic is Steps(n) = Steps(n - 1) + Steps(n - 2)

Copied from Jiuzhang:

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return n;
        }
        int last = 1, lastlast = 1;
        int now = 0;
        for (int i = 2; i <= n; i++) {
            now = last + lastlast;
            lastlast = last;
            last = now;
        }
        return now;
    }
}

// 记忆化搜索
// 九章硅谷求职算法集训营版本
public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    int[] result = null;

    void f(int X) {
         if (result[X] != -1) return;                                                 
         if (X == 0 || X == 1) {
            result[X] = 1;
            return;
         }
         
         f(X - 1);
         f(X - 2);
         result[X] = result[X - 1] + result[X - 2];
    }

    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        }
        
        result  = new int[n + 1];
        for (int i = 0; i <= n; ++i) {
            result[i] = -1;
        }
        
        f(n);
        return result[n];
    }
}

[2018-Interview] Convert Sorted Array to Binary Search Tree

Original question: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

My answer: find the root of left and right subtree, and then link them to root. Basically, it is converting each sub-array to a BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(nums[(0 + nums.length - 1) / 2]);
        helper(root, nums, 0, (0 + nums.length - 1) / 2 - 1, (0 + nums.length - 1) / 2 + 1, nums.length - 1);
        return root;
    }

    void helper(TreeNode root, int[] nums, int leftMin, int leftMax, int rightMin, int rightMax) {
        TreeNode leftRoot = null;
        TreeNode rightRoot = null;
        if (leftMin <= leftMax) {
            leftRoot = new TreeNode(nums[(leftMin + leftMax) / 2]);   
        }

        if (rightMin <= rightMax) {
            rightRoot = new TreeNode(nums[(rightMin + rightMax) / 2]);
        }
        root.left = leftRoot;
        root.right = rightRoot;
        if (leftRoot != null) {
            helper(leftRoot, nums, leftMin, (leftMin + leftMax) / 2 - 1, (leftMin + leftMax) / 2 + 1, leftMax);    
        }
        if (rightRoot != null) {
            helper(rightRoot, nums, rightMin, (rightMin + rightMax) / 2 - 1, (rightMin + rightMax) / 2 + 1, rightMax);
        }
    }
}