Leetcode 292 Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Solution 1: if n%4!=0, you move to 4x for your friend, no matter what your friend move, next step you move 4-step(your friend) till win.

 public class Solution {  
   public boolean canWinNim(int n) {  
     return n%4!=0;  
   }  
 }  

Leetcode 273 Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Solution 1: coding skill.

 public class Solution {  
   public String numberToWords(int num) {  
     String[] ones={"Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};  
     String[] tens={"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};  
     String[] thousands={"Thousand","Million","Billion"};  
     int[] nums={1000,1000000,1000000000};  
     if (num<20) return ones[num];  
     if (num<100) return tens[num/10]+((num%10==0)?"":" "+ones[num%10]);  
     if (num<1000) return ones[num/100]+" Hundred"+((num%100==0)?"":" "+numberToWords(num%100));  
     for (int i=0; i<3; i++) {  
       if (i==2 || num<nums[i+1]) {  
         return numberToWords(num/nums[i])+" "+thousands[i]+((num%nums[i]==0)?"":" "+numberToWords(num%nums[i]));  
       }  
     }  
     return "";  
   }  
 }  

Leetcode 264 Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Solution 1: Use a array to store the ugly number array. Maintain the index f2, f3, f5. which nums[f2]*2, nums[f3]*3 and nums[f5]*5 is just above the current value, in other words, nums[i]=min{2*nums[f2], 3*nums[f3], 5*nums[f5]}.

 public class Solution {  
   public int nthUglyNumber(int n) {  
     if (n<=0) return 0;  
     int[] ugly=new int[n];  
     ugly[0]=1;  
     int f2=2, f3=3, f5=5;  
     int i=0, j=0, k=0;  
     for (int t=1; t<n; t++) {  
       int min=Math.min(f2,Math.min(f3,f5));  
       ugly[t]=min;//could be f2=f3=f5, if any of them equal min, need to move to next  
       if (min==f2) f2=ugly[++i]*2;  
       if (min==f3) f3=ugly[++j]*3;  
       if (min==f5) f5=ugly[++k]*5;  
     }  
     return ugly[n-1];  
   }  
 }  

Leetcode 263 Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Solution 1: Simple math

 public class Solution {  
   public boolean isUgly(int num) {  
     if (num<=0) return false;  
     while (num%2==0) num/=2;  
     while (num%3==0) num/=3;  
     while (num%5==0) num/=5;  
     return num==1;  
   }  
 }  

Leetcode 260 Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Solution 1:Use xor to get the value of num1 XOR num2, find a bit not zero. use this bit to seperate the array into 2 groups (bit=1 and bit=0). So num1 and num2 will be separate. Then do xor to each group to find the num 1 and num 2.

 public class Solution {  
   public int[] singleNumber(int[] nums) {  
     int xor=0;  
     for (int x: nums) xor^=x;  
     int i=0;  
     while ((xor>>i&1)==0) i++;  
     int[] res=new int[2];  
     for (int x: nums) {  
       if ((x>>i&1)==0) res[0]^=x;  
       else res[1]^=x;  
     }  
     return res;  
   }  
 }  

Leetcode 258 Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur, periodically or randomly?
4. You may find this Wikipedia article useful.

Solution 1: it is repeat every 9 nums.

 public class Solution {  
   public int addDigits(int num) {  
     if (num==0) return 0;  
     int k=num%9;  
     return k==0?9:k;  
   }  
 }  

Leetcode 248 Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

Solution 1: brute force dfs all possible combinations and count the once <max and >min

 public class Solution {  
   public int strobogrammaticInRange(String low, String high) {  
     int m=low.length();  
     int n=high.length();  
     if (m>n) return 0;  
     if (m==n && low.compareTo(high)>0) return 0;  
     int[] count=new int[1];  
     for (int i=m; i<=n; i++) {  
       String lo="L";  
       String hi="H";  
       if (i==m) lo=low;  
       if (i==n) hi=high;  
       char[] c=new char[i];  
       dfs(c,0,i-1,lo,hi,count);  
     }  
     return count[0];  
   }  
   private void dfs(char[] c, int i, int j, String lo, String hi, int[] count) {  
     if (i>j) {  
       String one=new String(c);  
       if (!lo.equals("L") && one.compareTo(lo)<0) return;  
       if (!hi.equals("H") && one.compareTo(hi)>0) return;  
       count[0]++;  
     }  
     else {  
       if (i>0 || (i==0 && i==j)) {  
         c[i]='0'; c[j]='0';  
         dfs(c,i+1,j-1,lo,hi,count);  
       }  
       if (i!=j) {  
         c[i]='6';c[j]='9';  
         dfs(c,i+1,j-1,lo,hi,count);  
         c[i]='9';c[j]='6';  
         dfs(c,i+1,j-1,lo,hi,count);  
       }  
       c[i]='1';c[j]='1';  
       dfs(c,i+1,j-1,lo,hi,count);  
       c[i]='8';c[j]='8';  
       dfs(c,i+1,j-1,lo,hi,count);  
     }  
   }  
 }  

Leetcode 233 Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Solution 1:  Iteravet the bits. for certain bit: [a1..aj]x[b1..bi]: a=[a1..aj], b=[b1..bi]. Depends on x>1, x=1 and x<1. Calculate the combinations add to result.

 public class Solution {  
   public int countDigitOne(int n) {  
     if (n<=0) return 0;  
     int res=0;  
     for (long w=1; w<=n; w*=10) {  
       int a=(int)(n/(w*10)), b=(int)(n%w), x=(int)(n%(w*10)/w);  
       if (x>1) res+=(a+1)*w;  
       else if (x==1) res+=a*w+b+1;  
       else res+=a*w;  
     }  
     return res;  
   }  
 }  

 public class Solution {  
    public int countDigitOne(int n) {
        int weight=1, res=0;
        while (true) {
            int t1=n/weight/10, t2=n%weight, dig=n/weight%10;
            res+=t1*weight;
            if (dig==1) res+=t2+1;
            else if (dig>1) res+=weight;
            if (t1==0) break;
            weight*=10;
        }
        return res;
    }
 }  

Leetcode 231 Power of Two

Given an integer, write a function to determine if it is a power of two.
Solution 1: count the binary bits, should be only 1.

 public class Solution {  
   public boolean isPowerOfTwo(int n) {  
     if (n<0) return false;  
     int count=0;  
     for (int i=0; i<32; i++)   
       if ((n>>i&1)==1) count++;  
     return count==1;  
   }  
 }  

Leetcode 227 Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Solution 1: O(n) complexity and O(1) space

 public class Solution {  
   public int calculate(String s) {  
     int n=s.length();  
     int pre=0, curr=1;   
     boolean blank=true; //if s only contains ' '  
     boolean preSign=true, sign=true; //preSign: + or -; sign: * or /  
     for (int i=0; i<n; i++) {  
       if (s.charAt(i)==' ') continue;  
       else if (s.charAt(i)=='*') sign=true;  
       else if (s.charAt(i)=='/') sign=false;  
       else if (s.charAt(i)=='+' || s.charAt(i)=='-') {  
         pre=preSign? pre+curr:pre-curr;  
         preSign=s.charAt(i)=='+';  
         curr=1;  
         sign=true;  
       }  
       else {  
         blank=false;  
         int j=i+1;  
         while (j<n && s.charAt(j)>='0' && s.charAt(j)<='9') j++;  
         curr=sign? curr*Integer.valueOf(s.substring(i,j)):curr/Integer.valueOf(s.substring(i,j));  
         i=j-1;  
       }  
     }  
     if (blank) return 0;  
     return preSign? pre+curr:pre-curr;  
   }  
 }  

Leetcode 223 Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Solution 1: simple geometric problem, give code directly.

 public class Solution {  
   public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {  
     int area=Math.abs(D-B)*Math.abs(C-A)+Math.abs(G-E)*Math.abs(H-F);  
     if (E>=C || A>=G || B>=H || F>=D) return area;  
     int[] x=new int[]{A,C,E,G};  
     int[] y=new int[]{D,B,H,F};  
     Arrays.sort(x);  
     Arrays.sort(y);  
     return area-(x[2]-x[1])*(y[2]-y[1]);  
   }  
 }  

Leetcode 204 Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Solution 1: close to O(n) time complex.

 public class Solution {  
   public int countPrimes(int n) {  
     boolean[] flag=new boolean[n+1];  
     for (int i=2; i*i<n; i++) {  
       if (!flag[i]) {  
         for (int j=i; j*i<n; j++) flag[i*j]=true;  
       }  
     }  
     int count=0;  
     for (int i=2; i<n; i++)  
       if (!flag[i]) count++;  
     return count;  
   }  
 }  

Leetcode 202 Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

Solution 1: use hash table to record if duplicate or not. If Duplication is 1 return true, else return zero.

 public class Solution {  
   public boolean isHappy(int n) {  
     Set<Integer> set=new HashSet<>();  
     while (!set.contains(n)) {  
       set.add(n);  
       n=next(n);  
     }  
     if (n==1) return true;  
     return false;  
   }  
   private int next(int x) {  
     int res=0;  
     while (x!=0) {  
       int t=x%10;  
       res+=t*t;  
       x=x/10;  
     }  
     return res;  
   }  
 }  

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.

Solution 1:  10=2*5, there is enough 2, just need to find how many "5" in the range of 1...n.

 public class Solution {  
   public int trailingZeroes(int n) {  
     int res=0;  
     for (int div=5; div<=n; div*=5) {  
       res+=n/div;  
       if (div>Integer.MAX_VALUE/5) break;  
     }  
     return res;  
   }  
 }  

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 

Solution 1: simple math problem.

 public class Solution {  
   public int titleToNumber(String s) {  
     int res=0;  
     for (int i=0; i<s.length(); i++) {  
       int num=s.charAt(i)-'A'+1;  
       res=res*26+num;  
     }  
     return res;  
   }  
 }  

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 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 149 Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution 1: Method is brute force, but use 2 layer of Hash table to store the slop (dy/dx) and deal with the corn case.

 public class Solution {  
   public int maxPoints(Point[] points) {  
     int n=points.length;  
     Map<Integer,Map<Integer,Integer>> map=new HashMap<>();  
     int res=0;  
     for (int i=0; i<n; i++) {  
       map.clear();  
       int overlap=0, max=0;  
       for (int j=i+1; j<n; j++) {  
         int x=points[j].x-points[i].x;  
         int y=points[j].y-points[i].y;  
         if (x==0) {  
           if (y==0) {  
             overlap++;  
             continue;  
           }  
           else y=1;  
         }  
         else if (y==0) x=1;  
         else {  
           int gcd=calGcd(x,y);  
           x=x/gcd;  
           y=y/gcd;  
         }  
         int count=1;  
         if (!map.containsKey(x)) {  
           Map<Integer,Integer> one=new HashMap<>();  
           one.put(y,1);  
           map.put(x,one);  
         }  
         else if (!map.get(x).containsKey(y)) {  
           map.get(x).put(y,1);  
         }  
         else {  
           count=map.get(x).get(y);  
           map.get(x).put(y,++count);  
         }  
         max=Math.max(max,count);  
       }  
       res=Math.max(res,max+overlap+1);  
     }  
     return res;  
   }  
   private int calGcd(int x, int y) {  
     while (y!=0) {  
       int temp=y;  
       y=x%y;  
       x=temp;  
     }  
     return x;  
   }  
 }  

Leetcode 69 Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution 1:  Pay attention to 0 and mid*mid may too big (>Integer.MAX_VALUE)

 public class Solution {  
   public int mySqrt(int x) {  
     if (x<=0) return x;  
     int lo=1, hi=x;  
     while (lo<=hi) {  
       int mid=lo+(hi-lo)/2;  
       if (x/mid==mid) return mid;  
       else if (x/mid<mid) hi=mid-1;  
       else lo=mid+1;  
     }  
     return hi;  
   }  
 }