Daily Archives: March 17, 2013

Leetcode: Valid Number

Posted on by
Reply

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;
    }
FacebookTwitterGoogle+Share

Leetcode: Two Sum

Posted on by
Reply

Given an array of integers, 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 int[] twoSum(int[] numbers, int target) {
        //use hashmap to store <val,index> pairs of all the numbers
        //in this algorithm, we assume all the numbers are different
        //and we need to add one to the index as the final output as requried by this question
        int[] output = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<numbers.length;i++){
            map.put(numbers[i],i);
        }
        for(int i=0;i<numbers.length;i++){
            int val = target-numbers[i];
            if(map.containsKey(val)){
                int index = map.get(val);
                if(index!=i){
                    if(i<index){
                        output[0] = i+1;
                        output[1] = index+1;
                    }else{
                        output[0] = index+1;
                        output[1] = i+1;
                    }
                    return output;
                }
            }
        }
        return output;
    }

The time complexity is O(N). Since we only need constant time for each HashMap search operation.

Leetcode: Set Matrix Zeroes

Posted on by
Reply

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

public void setZeroes(int[][] matrix) {
        //to achieve constant space, we need to use the space of the first row and first col
        //to store information
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return;
        }
        
        //1. determine if the first row needs to be set zero because of itself
        //which means are there any zeros in the first row
        boolean zeroFirstRow = false;
        for(int i=0;i<matrix[0].length;i++){
            if(matrix[0][i]==0){
                zeroFirstRow=true;
                break;
            }
        }
        //2. determine if the first col needs to be set zero because of itself
        //which means are there any zeros in the first col
        boolean zeroFirstCol = false;
        for(int i=0;i<matrix.length;i++){
            if(matrix[i][0]==0){
                zeroFirstCol=true;
                break;
            }
        }
        //3. then we can use the first row and first col to store the information of 
        //the rest elements
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        //4. set the matrix to zero according to the information stored in the first row and first col
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[0][j]==0||matrix[i][0]==0){
                    matrix[i][j]=0;
                }    
            }
        }
        //set the first row
        if(zeroFirstRow){
            for(int i=0;i<matrix[0].length;i++){
                matrix[0][i]=0;
            }
        }
        //set the first col
        if(zeroFirstCol){
            for(int i=0;i<matrix.length;i++){
                matrix[i][0]=0;
            }
        }
    }