Ugly Number I & II

Ugly Number I

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.

public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        if (num == 1) {
            return true;
        }
        int[] factors = {2, 3, 5};
        for (int i = 0; i < factors.length; i++) {
            while (num % factors[i] == 0) {
                num = num / factors[i];
            }
        }
        return num == 1;
    }

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.

https://leetcode.com/discuss/52716/o-n-java-solution

Solution:

O(n) time, one pass solution. O(n) space.

The idea of this solution is from this page:http://www.geeksforgeeks.org/ugly-numbers/

The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5.

Then we use similar merge method as merge sort, to get every ugly number from the three subsequence.

Every step we choose the smallest one, and move one step after,including nums with same value.

    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for (int i = 1; i < n; i++) {
            int min = Math.min(Math.min(factor2, factor3), factor5);
            ugly[i] = min;
            if (factor2 == min) {
                index2++;
                factor2 = 2 * ugly[index2];
            }
            if (factor3 == min) {
                index3++;
                factor3 = 3 * ugly[index3];
            }
            if (factor5 == min) {
                index5++;
                factor5 = 5 * ugly[index5];
            }
        }
        return ugly[n - 1];
    }
FacebookTwitterGoogle+Share

Hash Function

Hash Function

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to “hash” the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:

hashcode(“abcd”) = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE

= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE

= 3595978 % HASH_SIZE

here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).

Given a string as a key and the size of hash table, return the hash value of this key.f

Example

For key=”abcd” and size=100, return 78

Clarification

For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.

Solution: Use a helper to avoid overflow.  To calculate a*33%HASH_SIZE, instead of multiply by 33, we add a to itself 33 times. if(result+num>mod) we only add num-mod it to the result, otherwise, just need to add num to result. In this case, we are either adding or removing HASH_SIZE from the final result so it won’t overflow.

public int hashCode(char[] key, int HASH_SIZE) {
    int result = 0;
    for (int i = 0; i < key.length; i++) {
        result = helper(result, 33, HASH_SIZE);
        result += key[i];
        result %= HASH_SIZE;
    }
    return result;
}

int helper(int num, int base, int mod) {
    int result = 0;
    for (int i = 0; i < base; i++) {
        if (result + num > mod) {
            result += num - mod;
        } else {
            result += num;
        }
    }
    return result;
}

Leetcode: 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.

 

public boolean isNumber(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s==null||s.length()==0){
            return false;
        }
        //continuous zeros from beginning since begin is true
        int cont = 0;
        boolean hasDot = false;
        boolean begin = false;
        boolean end = false;
        boolean hasSign = false;
        boolean hasE = false;
        
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            
            
            if(c=='+'||c=='-'){
                if(hasSign||begin){
                    return false;
                }else{
                    hasSign = true;
                }
                continue;
            }
            
            if(c=='e'){
                if(hasE||!begin){
                    return false;
                }else{
                    return isInteger(s.substring(i+1));
                    //return true;
                }
            }
            
            if(c=='.'){
                if(hasDot||end){
                    return false;
                }else{
                    hasDot = true;
                }
                continue;
            }
            
            if(c==' '){
                if((begin ||hasSign) && !end){
                    end=true;
                }
                continue;
            }
            
            if(!(isDigit(s,i))){
                return false;
            }else{
                if(end){
                    return false;
                }else{
                    if(!begin){
                        begin=true;
                    }
                }
            }
            
            
        }
        
        if(!begin){
            return false;
        }
        return true;
        
        
    }
    public boolean isInteger(String s){
        if(s==null||s.length()==0){
            return false;
        }
        if(s.length()==1 && isDigit(s,0)){
            return true;
        }
        char c = s.charAt(0);
        if(c=='0'){
            return ifAllSpace(s.substring(1));
        }
        int zeors = 0;
        for(int i=0;i<s.length();i++){
            if(i==0){
                if(c=='+'||c=='-'){
                    return isIntegerWithoutSign(s.substring(i+1));
                }else
                if(!isDigit(s,i)){
                    return false;
                }
            }else
            if(!isDigit(s,i)){
                if(c==' '){
                    return ifAllSpace(s.substring(i+1));
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean ifAllSpace(String s){
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!=' '){
                return false;
            }
        }
        return true;
    }
    
    public boolean isIntegerWithoutSign(String s){
        if(s==null||s.length()==0){
            return false;
        }
        if(s.length()==1 && isDigit(s,0)){
            return true;
        }
        char c = s.charAt(0);
        if(c=='0'){
            return false;
        }
        for(int i=0;i<s.length();i++){
            if(!isDigit(s,i)){
                if(c==' '){
                    return ifAllSpace(s.substring(i));
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean isDigit(String s,int index){
        char c = s.charAt(index);
        if(c<(int)'0' || c>(int)'9'){
            return false;
        }
        return true;
    }

Leetcode: Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

 

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

public String getPermutation(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> nums = new ArrayList<Integer>();
        for(int i=1;i<=n;i++){
            nums.add(i);
        }
        k--;//k originally starts from 1
        int index=0;
        while(k!=0){
            int frac = frac(n-index-1);
            int targetNumIndex = k/frac+index;
            int targetNum = nums.remove(targetNumIndex);
            nums.add(index,targetNum);
            index++;
            k=k%frac;
        }
        String output = "";
        for(Integer num:nums){
            output+=num;
        }
        return output;
    }
    
    public int frac(int n){
        int sum = 1;
        for(int i=1;i<=n;i++){
            sum*=i;
        }
        return sum;
    }

 

Leetcode: Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

public int romanToInt(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Character> oneLetters = new ArrayList<Character>();
        oneLetters.add('I');
        oneLetters.add('X');
        oneLetters.add('C');
        oneLetters.add('M');
        ArrayList<Character> fiveLetters = new ArrayList<Character>();
        fiveLetters.add('V');
        fiveLetters.add('L');
        fiveLetters.add('D');

        int num=0;
        for(int i=0;i<s.length();i++){
            int bit = fiveLetters.indexOf(s.charAt(i));
            //if the current letter is in fiveLetters
            if(bit!=-1){
                num+=5*(int)Math.pow(10,bit);
            }else{
                bit = oneLetters.indexOf(s.charAt(i));
                //if the current letter is in oneLetters && there is a bigger number afterwards
                if( i+1<s.length() && 
                  (fiveLetters.indexOf(s.charAt(i+1))>=bit ||
                   oneLetters.indexOf(s.charAt(i+1))>bit)){
                    num-=(int)Math.pow(10,bit);
                }
                //else, just add this num
                else{
                    num+=(int)Math.pow(10,bit);
                }
            }

        }
        return num;
    }

Leetcode: Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

public String intToRoman(int num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        String[] oneLetters = {"I","X","C","M"};
        String[] fiveLetters = {"V","L","D",""};
        String numStr = num+"";
        String output = "";
        for(int i=numStr.length()-1;i>=0;i--){
            String tmp = "";
            int bit = (int)num%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
            switch (bit){
                case 1: tmp = oneLetters[i];
                        break;
                case 2: tmp = oneLetters[i]+oneLetters[i];
                        break;
                case 3: tmp = oneLetters[i]+oneLetters[i]+oneLetters[i];
                        break;
                case 4: tmp = oneLetters[i]+fiveLetters[i];
                        break;
                case 5: tmp = fiveLetters[i];
                        break;
                case 6: tmp = fiveLetters[i]+oneLetters[i];
                        break;
                case 7: tmp = fiveLetters[i]+oneLetters[i]+oneLetters[i];
                        break;
                case 8: tmp = fiveLetters[i]+oneLetters[i]+oneLetters[i]+oneLetters[i];
                        break;
                case 9: tmp = oneLetters[i]+oneLetters[i+1];
                        break;
                default: tmp = "";
                        break;
            }
            output+=tmp;
        }
        return output;
    }

Leetcode: Pow(x, n)

Implement pow(xn).

public double pow(double x, int n) {
    // Start typing your Java solution below
    // DO NOT write main() function
    boolean positive = n >= 0 ? true : false;

    int nabs = n == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(n);

    double product = n == Integer.MIN_VALUE ? powHelp(x, nabs) * x : powHelp(x, nabs);

    return positive ? product : 1 / product;

}

public double powHelp(double base, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return base;
    }

    double tmp = powHelp(base, n / 2);
    return tmp * tmp * powHelp(base, n % 2);
}

O(logN)

Version with no helper function

public double myPow(double x, int n) {
        if(n==0){
            return 1;
        }
        int n_abs = Math.abs(n);
        if(n_abs==1){
            return n>0?x:1/x;
        }
        double tmp =  myPow(x, n/2);
        return tmp*tmp*myPow(x, n%2);
    }

Leetcode: String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

public class Solution {
    public int atoi(String str) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> validBits = new ArrayList<Integer>();
        int sign=0;
        if(str==null||str.length()==0){
            return 0;
        }
        int index = 0;
        while(str.charAt(index)==' '){
            index++;
        }
        if(!(isNum(str, index) || str.charAt(index)=='+' || str.charAt(index)=='-')){
            return 0;
        }
        if(str.charAt(index)=='-'){
            sign = -1;
            index++;
        }else{
            sign = 1;
            if(str.charAt(index)=='+'){
                index++;
            }
        }
        //now find the first non-zero bit
        while(str.charAt(index)=='0'){
            index++;
        }
        while(index<str.length() && isNum(str,index)){
            int asc = (int)str.charAt(index);
            int bit = asc-'0';
            validBits.add(bit);
            index++;
        }

        int length = validBits.size();
        if(length==0){
            return 0;
        }

        double sum =0;
        for(int i=0;i<length;i++){
            sum+=validBits.get(i)*Math.pow(10,length-i-1);
        }
        if(sign<0){
            if(sum*sign<(double)Integer.MIN_VALUE){
                return Integer.MIN_VALUE;
            }else{
                return (int)(sum*sign);
            }
        }else{
            if(sum>(double)Integer.MAX_VALUE){
                return Integer.MAX_VALUE;
            }else{
                return (int)sum;
            }
        }

    }

    public boolean isNum(String str, int index){
        int asc = (int)str.charAt(index);
        if(asc>='0' && asc<='9'){
            return true;
        }
        return false;
    }
}