Showing posts with label LeetCode. Show all posts
Showing posts with label LeetCode. Show all posts

Tuesday, January 13, 2015

LeetCode 179: Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
public class Solution {
    public String largestNumber(int[] num) {
        // Adopt modified LSD (Least-Significant-Digits) algorithm
        // MSD algorithm is not suitable here
        // However, LSD requires identical length of every element (String format)
        // Suppose that the longest length of element is 4, we append any element by itself until the length is 4*2:
        // "123" ---> "123"+"123"+"12" ---> "12312312"
        // We can define a "charAt()" function to implement that without actually append the string.
        int n = num.length;
        int R = 10; // Only 10 digits: 0, 1, 2, ..., 9
        int len = 0; // Max length of elements
        String[] a = new String[n];
        String[] aux = new String[n];
        
        // Convert 'num' to 'a'
        for (int i = 0; i < n; i++)
        {
            a[i] = String.valueOf(num[i]);
            
            if (len < a[i].length())
                len = a[i].length();
        }
        
        // Original num: [3, 30, 34, 5, 9]
        // Result: [30, 3, 34, 5, 9]
        for (int d = len*2-1; d >= 0; d--)
        {
            int[] count = new int[R+1];
            
            // Compute frequency counts
            for (int i = 0; i < n; i++)
                count[charAt(a[i], d)+1]++;
                
            // Transform counts to indices
            for (int r = 0; r < R; r++)
                count[r+1] += count[r];
                
            // Distribute the data
            for (int i = 0; i < n; i++)
                aux[count[charAt(a[i], d)]++] = a[i];
                
            // Copy back
            for (int i = 0; i < n; i++)
                a[i] = aux[i];
        }
        
        String result = "";
        
        for (int i = n-1; i >= 0; i--)
            result += a[i];
        
        // Note: Maybe exist special case: "0000"    
        if (result.length()>1 && result.charAt(0)=='0')
            result = "0";

        return result;
    }
    
    private int charAt(String s, int d)
    {
        d = d%s.length();
        
        return s.charAt(d)-'0';
    }
}

Sunday, January 11, 2015

LeetCode 174: Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

Notes:
  • The knight's health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // DP problem
        // Let minHP[i][j] denotes the least HP when the knight reached dungeon[i][j].
        // Note: This question should consider backward induction.
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] minHP = new int[m][n];
    
        // Note: Supposed only one cube that imorisoned princess.
        minHP[m-1][n-1] = (dungeon[m-1][n-1] > 0) ? 1 : (1 - dungeon[m-1][n-1]);
    
        // 1. In the last column, from up to bottom.
        for(int i = m-2; i >= 0; i--)
        {
            int down = minHP[i+1][n-1] - dungeon[i][n-1];
            minHP[i][n-1]  = down > 0 ? down : 1;
        }
    
        // 2. In the last row, from left to right.
        for (int j = n-2; j >= 0; j--)
        {
            int right = minHP[m-1][j+1] - dungeon[m-1][j];
            minHP[m-1][j]  = right > 0 ? right : 1;
        }
    
        // 3. In other areas, from up to bottom and from left to right.
        for(int i = m-2; i >= 0; i--)
        {
            for(int j = n-2; j >= 0; j--)
            {
                int down = (minHP[i+1][j]-dungeon[i][j] > 0) ? minHP[i+1][j]-dungeon[i][j] : 1;
                int right = (minHP[i][j+1]-dungeon[i][j] > 0) ? minHP[i][j+1]-dungeon[i][j] : 1;
                
                minHP[i][j] = Math.min(down, right);
            }
        }
        
        return minHP[0][0];
    }
}

LeetCode 173: Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
    // Adopt inorder traversal
    Queue<TreeNode> queue;
    
    public BSTIterator(TreeNode root) {
        queue = new LinkedList<>();
        inorder(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if (!queue.isEmpty())
            return true;
        else
            return false;
    }

    /** @return the next smallest number */
    public int next() {
        return queue.remove().val;
    }
    
    private void inorder(TreeNode root)
    {
        if (root == null)
            return;
            
        inorder(root.left);
        queue.add(root);
        inorder(root.right);
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

LeetCode 172: Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
public class Solution {
    public int trailingZeroes(int n) {
        // http://en.wikipedia.org/wiki/Trailing_zero
        
        // Non-negative number doesn't have factorial.
        // The factorial of 0 is 1.
        if (n <= 0)
            return 0;
        
        // Find k so that pow(5, k+1) > n.
        // Add 0.1 to n in case pow(5, k+1) = n.
        int k = (int)Math.ceil(Math.log(n+0.1)/Math.log(5.0)-1);
        
        if (k < 1)
            return 0;
        
        // The number of trailing zeros
        int ntz = 0;
        
        for (int i = 1; i <= k; i++)
            ntz += n/Math.pow(5, i);
        
        return ntz;
    }
}

LeetCode 171: Excel Sheet Column Number

Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
public class Solution {
    public int titleToNumber(String s) {
        // BAC -> 2*26*26+1*26+3
        // Note: Character.getNumericValue(ch) is used for convert number (e.g, '3' -> 3)
        // (int) is used to get ASCII code (e.g., 'A' -> 65; '3' -> 51)
        int n = s.length();
        int result = 0;
        int nA = 'A';
        
        for (int i = n-1; i >= 0; i--)
            result += Math.pow(26, n-i-1)*(s.charAt(i)-nA+1);
            
        return result;
    }
}

LeetCode 170: Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false
public class TwoSum {
    // <Number, Appearing Times of Number>
    private Map<Integer, Integer> map = new HashMap<>();

    public void add(int number) {
        if (map.containsKey(number))
	    map.put(number, map.get(number)+1);
	else
	    map.put(number, 1);
    }
    
    public boolean find(int value) {
	for (int i : map.keySet())
	{
	    int rest = value - i;
	        
	    if (map.containsKey(rest))
	    {
	        if (i != rest)
	            return true;
	                
	        if (i==rest && map.get(rest)>=2)
	            return true;
	    }
	}
	    
	return false;
    }
}

LeetCode 169: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
public class Solution {
    public int majorityElement(int[] num) {
        // Adopt HashMap to save the number and corresponding apear times
        int n = num.length;
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++)
        {
            if (!map.containsKey(num[i]))
                map.put(num[i], 1);
            else
                map.put(num[i], map.get(num[i])+1);
        }
        
        int maxNum = 0;
        int maxTimes = 0;
        
        for (int number : map.keySet())
        {
            if (map.get(number) > maxTimes)
            {
                maxNum = number;
                maxTimes = map.get(number);
            }
        }
        
        return maxNum;
    }
}

LeetCode 168: Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
public class Solution {
    public String convertToTitle(int n) {
        String result = "";
        
        while (n > 0)
        {
            int m = (n-1)%26;
            
            result = (char)('A'+m) + result;
            
            n = (n-1)/26;
        }
        
        return result;
    }
}

LeetCode 167: Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // Two pointer run from left and right, respectively.
        int n = numbers.length;
        
        if (n <= 1)
            return null;
            
        int[] result = new int[2];
        result[0] = 1;
        result[1] = n;
        int sum;
        
        while (result[0] < result[1])
        {
            sum = numbers[result[0]-1] + numbers[result[1]-1];
            
            if (sum < target)
                result[0]++;
            else if (sum > target)
                result[1]--;
            else
                break;
        }
        
        return result;
    }
}

LeetCode 166: Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
  • Given numerator = 1, denominator = 2, return "0.5".
  • Given numerator = 2, denominator = 1, return "2".
  • Given numerator = 2, denominator = 3, return "0.(6)".
public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        // http://blog.csdn.net/ljiabin/article/details/42025037
        if (numerator == 0)
            return "0";
            
        if (denominator == 0)
            return "";  
          
        String ans = "";  
          
        // If different signs 
        if ((numerator < 0) ^ (denominator < 0))
            ans += "-";
          
        // Converto to 'long' type in case of overflow 
        long num = Math.abs((long)numerator);  
        long den = Math.abs((long)denominator);  
          
        // Get integer quotient
        long res = num/den;
        ans += String.valueOf(res);  

        // (Remainder*10) / denominator in case of integer division
        long rem = (num % den) * 10;
        
        // Check if there is remainder
        if (rem == 0)
            return ans;  
          
        // Fractional part --- <Remainder, Index>  
        HashMap<Long, Integer> map = new HashMap<>();
        
        ans += ".";  
        
        while (rem != 0)
        {  
            // If this remainder has already appeared, it indicates loop.
            if (map.containsKey(rem))
            {
                // Obtain index of loop remainder
                int id = map.get(rem);
                
                String nonLoop = ans.substring(0, id);  
                String loop = ans.substring(id, ans.length());
                
                ans = nonLoop + "(" + loop + ")";  
                return ans;  
            }  
              
            // Continue division 
            map.put(rem, ans.length());
            
            res = rem / den;  
            ans += String.valueOf(res);  
            rem = (rem % den) * 10;  
        }  
          
        return ans;        
    }
}

LeetCode 165: Compare Version Numbers

Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37
public class Solution {
    public int compareVersion(String version1, String version2) {
        // Note: Many special cases, e.g., "1" vs. "1.0.25"
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        
        int n1 = v1.length;
        int n2 = v2.length;
        
        int ver1, ver2;
        
        for (int i = 0; i < Math.max(n1, n2); i++)
        {
            if (i < n1)
                ver1 = Integer.valueOf(v1[i]);
            else
                ver1 = 0;
                
            if (i < n2)
                ver2 = Integer.valueOf(v2[i]);
            else
                ver2 = 0;
                
            if (ver1 > ver2)
                return 1;
            else if (ver1 < ver2)
                return -1;
        }
        
        return 0;
    }
}

LeetCode 164: Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
public class Solution {
    public int maximumGap(int[] num) {
        // Suppose there are N elements and they range from A to B.
        // Then the maximum gap will be no smaller than ceiling[(B - A) / (N - 1)]
        // Let the length of a bucket to be len = ceiling[(B - A) / (N - 1)]
        // Then we will have at most num = (B - A) / len + 1 of bucket (num = (B - A) / len + 1 = N)
        
        // for any number K in the array, we can easily find out which bucket it belongs by calculating loc = (K - A) / len
        // and therefore maintain the maximum and minimum elements in each bucket.
        // Since the maximum difference between elements in the same buckets will be at most len - 1
        // So the final answer will not be taken from two elements in the same buckets.
        // For each non-empty buckets p, find the next non-empty buckets q
        // Then q.min - p.max could be the potential answer to the question. Return the maximum of all those values.        
        int n = num.length;
        
        if (n < 2)
            return 0;
            
        // Find the max and min value in the array
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        for (int value: num)
        {
            min = Math.min(min, value);
            max = Math.max(max, value);
        }
        
        int gap = (int)Math.ceil((double)(max-min) / (n-1)); // maxGap should be no smaller than gap (gap = len)
        
        int[] minNums = new int[n-1]; // Store the min value in the bucket
        int[] maxNums = new int[n-1]; // Store the max value in the bucket
        
        Arrays.fill(minNums, Integer.MAX_VALUE);
        Arrays.fill(maxNums, Integer.MIN_VALUE);
        
        for (int value : num)
        {
            if (value != min && value != max)
            {
                // min and max will be considered as two special buckets
                int i = (value - min) / gap; // Calc the bucket index
                minNums[i] = Math.min(minNums[i], value);
                maxNums[i] = Math.max(maxNums[i], value);
            }
        }
        
        // Scan the buckets for the max gap
        int maxGap = Integer.MIN_VALUE;
        int prevMax = min; // last non-empty bucket max value
        
        for (int i = 0; i < num.length - 1; ++i)
        {
            if (minNums[i]!=Integer.MAX_VALUE && maxNums[i]!=Integer.MIN_VALUE)
            {
                // non-empty bucket
                maxGap = Math.max(maxGap, minNums[i] - prevMax);
                prevMax = maxNums[i];
            }
        }
        
        maxGap = Math.max(maxGap, max - prevMax); 
                
        return maxGap;
    }
}

LeetCode 163: Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
public class Solution {
    public List<String> findMissingRanges(int[] A, int lower, int upper) {
        List<String> result = new LinkedList<>();
        
        int n = A.length;
        
        if (n == 0)
        {
            findMissingPart(result, lower, upper);
            return result;
        }
        
        // Process the starting section
        findMissingPart(result, lower, A[0]-1);
        
        // Process the middle section
        for (int i = 0; i < n-1; i++)
            findMissingPart(result, A[i]+1, A[i+1]-1);
            
        // Process the ending section
        findMissingPart(result, A[n-1]+1, upper);
        
        return result;
    }
    
    private void findMissingPart(List<String> result, int lo, int hi)
    {
        if (lo == hi)
        {
            String ret = Integer.toString(lo);
            result.add(ret);
        }
        else if (lo < hi)
        {
            String ret = Integer.toString(lo);
            ret += "->";
            ret += Integer.toString(hi);
            result.add(ret);
        }        
    }
}

LeetCode 162: Find Peak Element

A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
Note: Your solution should be in logarithmic complexity.
public class Solution {
    public int findPeakElement(int[] num) {
        // Adopt binary search
        int n = num.length;
        
        int lo = 0, hi = n-1;
        
        while (lo < hi)
        {
            int mid = lo + (hi-lo)/2;
            
            if (num[mid] < num[mid+1])
                lo = mid+1;
            else
                hi = mid;
        }
        
        return lo;
    }
}