Leetcode -- Day 12

Question1

Power of Two

Given an integer, write a function to determine if it is a power of two.

This question is pretty simple. If a number is a power of two, keep it divide by 2, until the result is 1 and the mod of n%2 is always zero.

 1     public boolean isPowerOfTwo(int n) {
 2         if(n<=0)
 3             return false;
 4         while (n>1){
 5             if (n%2 != 0)
 6                 return false;
 7             n = n/2;
 8         }
 9         return true;
10     }

However I read another method using binary bit operation. If a number is power of two, it has only one non-zero number like 1000.

So we can use the & oeprator. This way is very smart and clean.

1     public boolean isPowerOfTwo(int n) {
2         return n > 0 && ((n & (n-1)) == 0);
3     }

Question 2

Pow(x, n)

Implement pow(x, n).

One thing you need to notice here is if you continue use result = v * v * v* v....then it will exceed the time limit. So remember to use the n/2. This method will reduce a lot of working time. And be careful to consider the n < 0 case.

 1 public double myPow(double x, int n) {
 2         if (x == 0)
 3             return 0;
 4         if (n == 0)
 5             return 1;
 6         
 7         if (n>0)
 8             return power(x,n);
 9         else
10             return 1/power(x,-n);
11         
12     }
13     
14     public double power(double x, int n){
15         
16         if (n == 0)
17             return 1;
18         
19         double v = power(x, n/2);
20         
21         if (n % 2 == 0)
22             return v*v;
23         else
24             return v*v*x;
25     }

Another method is more clear and shorter, but it use a little trick. It get it 1/x int the very fist time by using half/x*half. For example,

myPow(2, -4) -->

myPow(2, -2) -->

myPow(2, -1) = 1/2 then back up to

myPow(2, -2) and above it will always call half * half as n % 2 == 0 --> 1/2 * 1/2 * 1/2 * 1/2.

It does not use 1/ total Result but turn each opeartor to 1/half.

public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        double half = myPow(x, n/2);
        if (n%2 == 0)
        {
            return half*half;
        }
        else if (n>0)
        {
            return half*half*x;
        }
        else
        {
            return half/x*half;
        }
    }

Question 3

Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

The first direct method is use regular expression, which is cleaner and shorter. But it is not enough for interview. So I do another more complex method.

 1     public boolean isNumber(String s) {
 2         s = s.trim();
 3         if (s.length() == 0)
 4             return false;
 5         
 6         String regex = "[-+]?(\d+\.?|\.\d+)\d*(e[-+]?\d+)?";
 7         if (s.matches(regex))
 8             return true;
 9         else
10             return false;
11         
12     }

The below one is more complex but much more direct one way.

 1     public boolean isNumber(String s) {
 2         s = s.trim();
 3         int eIndex = -1;
 4         int dotIndex = -1;
 5         
 6         if (s.length()==0)
 7             return false;
 8         
 9         int i = 0;
10         
11         if (s.charAt(i) == '+' || s.charAt(i) == '-')
12             s = s.substring(1);
13             
14         for (i = 0; i < s.length(); i ++){
15             if (eIndex == -1 && s.charAt(i) == 'e'){
16                 eIndex = i;
17                 if (i + 1 < s.length() && (s.charAt(i+1) == '-' || s.charAt(i+1) == '+'))
18                     i ++;
19             }
20             else if (dotIndex == -1 && s.charAt(i) == '.')
21                 dotIndex = i;
22             else{
23                 if (Character.isDigit(s.charAt(i)))
24                     continue;
25                 else
26                     return false;
27             }
28         }
29         
30         String startString, midString, endString;
31         if (eIndex == -1 && dotIndex == -1){
32             startString = s;
33             if (startString.length() < 1)
34                 return false;
35         }
36         else if (eIndex == -1 && dotIndex != -1){
37             startString = s.substring(0, dotIndex);
38             endString = s.substring(dotIndex+1);
39             if (startString.length()<1 && endString.length() < 1)
40                 return false;
41         }
42         else if (dotIndex == -1 && eIndex != -1){
43             startString = s.substring(0, eIndex);
44             if (startString.length()<1)
45                 return false;
46             if (eIndex+1 < s.length() && (s.charAt(eIndex+1) == '+' ||s.charAt(eIndex+1) == '-'))
47                 endString = s.substring(eIndex + 2);
48             else
49                 endString = s.substring(eIndex + 1);
50             if (endString.length()<1)
51                 return false;
52         }
53         else{
54             if (dotIndex > eIndex)  return false;
55             else{
56                 startString = s.substring(0, dotIndex);
57                 midString = s.substring(dotIndex+1, eIndex);
58                 if (startString.length()<1 && midString.length()<1)
59                     return false;
60                 if (eIndex+1 < s.length() && (s.charAt(eIndex+1) == '+' ||s.charAt(eIndex+1) == '-'))
61                     endString = s.substring(eIndex + 2);
62                 else
63                     endString = s.substring(eIndex + 1);
64                 if (endString.length()<1 )
65                     return false;
66             }
67         }
68         return true;
69     }

Question 4

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Very clever is to use binary search. There are some tricks here:

1. r = x/2 + 1; the square root must lest than the n/2 +1; So we can ignore some number for checking.

2. use x/m<m rather thatn x < m*m, which may exceed the MAX_VALUE or time limit.

 1 public int mySqrt(int x) {
 2         if(x<0) return -1;
 3         if(x==0) return 0;
 4         int l=1;
 5         int r=x/2+1;
 6         while(l<=r)
 7         {
 8             int m = (l+r)/2;
 9             if(m<=x/m && x/(m+1)<m+1)
10                 return m;
11             if(x/m<m)
12             {
13                 r = m-1;
14             }
15             else
16             {
17                 l = m+1;
18             }
19         }
20         return 0;
21 }