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.

Solution 1:  sort and find the middle. O(nlogn) which is actually faster than Solution 2

 public class Solution {  
   public int majorityElement(int[] nums) {  
     Arrays.sort(nums);  
     return nums[nums.length/2];  
   }  
 }  

Solution 2:  bit count, O(n) which is not actually fast than solution 1. as logn normally will be less than 32.

 public class Solution {  
   public int majorityElement(int[] nums) {  
     int n=nums.length;  
     int[] count=new int[32];  
     for (int x: nums)  
       for (int i=0; i<32; i++)  
         if ((x>>i&1)==1) count[i]++;  
     int res=0;  
     for (int i=0; i<32; i++)  
       if (count[i]>n/2) res|=1<<i;  
     return res;  
   }  
 }  

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 

Solution 1:  A-weight 1, B-weight 2.....Z weight 26

 public class Solution {  
   public String convertToTitle(int n) {  
     StringBuilder sb=new StringBuilder();  
     while (n>0) {  
       sb.insert(0,(char)((n-1)%26+'A'));  
       n=(n-1)/26;  
     }  
     return sb.toString();  
   }  
 }  

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

Solution 1: simple two pointers.

 public class Solution {  
   public int[] twoSum(int[] numbers, int target) {  
     int i=0, j=numbers.length-1;  
     while (i<j) {  
       int sum=numbers[i]+numbers[j];  
       if (sum<target) i++;  
       else if (sum>target) j--;  
       else return new int[]{i+1,j+1};  
     }  
     return new int[]{0,0};  
   }  
 }  

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)".

Solution 1: Integer part is relatively easy. Fractional part: use a hash table to record to find the duplication numerator which mean fractional part will repeat, or if numerator part is zero, which means end of the fractional part.

 public class Solution {  
   public String fractionToDecimal(int numerator, int denominator) {  
     boolean pos=true;  
     if (numerator==0) return "0";  
     if (numerator<0) pos=!pos;  
     if (denominator<0) pos=!pos;  
     StringBuilder res=new StringBuilder();  
     if (!pos) res.append('-');  
     long n=Math.abs((long)numerator);  
     long d=Math.abs((long)denominator);  
     res.append(String.valueOf(n/d));  
     n%=d;  
     if (n==0) return res.toString();  
     res.append('.');  
     Map<Long,Integer> map=new HashMap<>();  
     StringBuilder sb=new StringBuilder();  
     int i=0;  
     while (n!=0) {  
       if (map.containsKey(n)) {  
         sb.insert((int)map.get(n),'(');  
         sb.append(')');  
         break;  
       }  
       else {  
         map.put(n,i++);  
         sb.append((char)(n*10/d+'0'));  
         n=n*10%d;  
       }  
     }  
     res.append(sb);  
     return res.toString();  
   }  
 }  

Leetcode 165 Compare Version Numbers

Compare two version numbers version1 and version2.
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

Solution 1: Two pointers for s and t. compare the numbers before it reach '.' or end of string. If one pointer go beyond the end of string, use default value of 0.

 public class Solution {  
   public int compareVersion(String version1, String version2) {  
     int i=0, j=0;  
     int m=version1.length(), n=version2.length();  
     while (i<m || j<n) {  
       int p1=i;  
       while (p1<m && version1.charAt(p1)!='.') p1++;  
       int num1=(p1>i)?Integer.valueOf(version1.substring(i,p1)):0;  
       int p2=j;  
       while (p2<n && version2.charAt(p2)!='.') p2++;  
       int num2=(p2>j)?Integer.valueOf(version2.substring(j,p2)):0;  
       if (num1>num2) return 1;  
       if (num1<num2) return -1;  
       i=++p1;  
       j=++p2;  
     }  
     return 0;  
   }  
 }  

Solution 2: Similar

 public class Solution {  
   public int compareVersion(String version1, String version2) {  
     String[] v1=version1.split("\\.");  
     String[] v2=version2.split("\\.");  
     for (int i=0; i<v1.length || i<v2.length; i++) {  
       int num1=i<v1.length?Integer.valueOf(v1[i]):0;  
       int num2=i<v2.length?Integer.valueOf(v2[i]):0;  
       if (num1>num2) return 1;  
       else if (num1<num2) 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.

Solution 1: As request for O(n) time and O(n) space. Use bracket. The max gap must be greater than gap=(max-min)/(n-1). So we can create n bracket: [min,min+gap), [min+gap,min+2gap).... the result must be value between brackets instead of within bracket. So first step is allocate all numbers into the bracket, then iterate the bracket to find max inter-bracket value.

 public class Solution {  
   public int maximumGap(int[] nums) {  
     int n=nums.length;  
     if (n<2) return 0;  
     int max=Integer.MIN_VALUE, min=Integer.MAX_VALUE;  
     for (int x: nums) {  
       max=Math.max(max,x);  
       min=Math.min(min,x);  
     }  
     int gap=(max-min)/(n-1);  
     if (gap*(n-1)<max-min) gap++;  
     if (gap==0) return 0;  
     int[] minBracket=new int[n];  
     int[] maxBracket=new int[n];  
     Arrays.fill(minBracket, Integer.MAX_VALUE);  
     Arrays.fill(maxBracket, Integer.MIN_VALUE);  
     for (int x: nums) {  
       int i=(x-min)/gap;  
       maxBracket[i]=Math.max(maxBracket[i],x);  
       minBracket[i]=Math.min(minBracket[i],x);  
     }  
     int res=0;  
     int lo=maxBracket[0];//bracket[0] is not blank, at least min will be there  
     for (int i=1; i<n; i++) {  
       if (maxBracket[i]!=Integer.MIN_VALUE) {  
         res=Math.max(res,minBracket[i]-lo);  
         lo=maxBracket[i];  
       }  
     }  
     return res;  
   }  
 }  

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"].

Solution 1: iterate the array, O(n) solution below:

 public class Solution {  
   public List<String> findMissingRanges(int[] nums, int lower, int upper) {  
     int n=nums.length;  
     List<String> res=new ArrayList<>();  
     for (int i=0; i<n; i++) {  
       if (nums[i]<lower) continue;  
       else if (nums[i]==lower) lower++;  
       else {  
         int hi=Math.min(nums[i]-1,upper);  
         if (lower==hi) res.add(String.valueOf(lower));  
         else if (lower<hi) res.add(String.valueOf(lower)+"->"+String.valueOf(hi));  
         lower=nums[i]+1;  
       }  
       if (lower>upper) break;  
     }  
     if (lower==upper) res.add(String.valueOf(lower));  
     else if (lower<upper) res.add(String.valueOf(lower)+"->"+String.valueOf(upper));  
     return res;  
   }  
 }