My java solution with explanation,second version


  • 3
    N

    my trick:

    1. use long to avoid overflow
    2. use StringBuffer to build String

      3.use class pair to keep track of numerator and denominator,if I find the same pair in the map,it means the fractional part is repeating.
    3. using res=numeratorl/denominatorl;numeratorl=(numeratorl%denominatorl)*10; to simulate division,res is the value to append to buffer.
     public class Solution {
            public String fractionToDecimal(int numerator, int denominator) {
        	//to avoid overflow
        	long numeratorl=numerator, denominatorl=denominator;
            StringBuffer buffer=new StringBuffer();
            //handle negatives 
            if(numeratorl<0&&denominatorl>0)buffer.append('-');
            else if(numeratorl>0&&denominatorl<0)buffer.append('-');
            numeratorl=Math.abs(numeratorl);denominatorl=Math.abs(denominatorl);
            //map,key:pair to hold numerator and denominator;value:position of numerator/denominator 
            HashMap<pair, Integer>map=new HashMap<>();
            //handle integer part
            long res=numeratorl/denominatorl;
            numeratorl=(numeratorl%denominatorl)*10;
    		buffer.append(res);
    		if(numeratorl!=0)buffer.append('.');
    		//handle float part
    		while(numeratorl != 0){
    			res=numeratorl/denominatorl;
    			pair p=new pair(denominatorl,numeratorl);
    			if(map.get(p)!=null)
    			{
    				//handle repaeting part
    				buffer.insert(map.get(p).intValue(), '(');
    				buffer.append(')');
    				break;
    			}
    			map.put(p, buffer.length());
    			numeratorl=(numeratorl%denominatorl)*10;
    	        buffer.append(res);
    		}
            return buffer.toString();
        }
        //this class is used to hold numerator and denominator,override hashcode\equals
        private static class pair{
        	public long d;
        	public long n;
        	public pair(long d,long n) {
        		this.d=d;this.n=n;
    		}
        	@Override
        	public int hashCode() {
        		return Arrays.hashCode(new long[]{d,n});
        	}
        	@Override
        	public boolean equals(Object obj) {
        		pair p = (pair) obj;
        		return p.d==d&&p.n==n;
        	}
         }
        }
    

    I make this problem complicated,because if numerator repeating,the fractional part is repeating.so class pair is not needed.I give my second version

    public class Solution {
    	    public String fractionToDecimal(int numerator, int denominator) {
    	    	//to avoid overflow
    	    	long numeratorl=numerator, denominatorl=denominator;
    	        StringBuffer buffer=new StringBuffer();
    	        //handle negetives 
    	        if(numeratorl<0&&denominatorl>0)buffer.append('-');
    	        else if(numeratorl>0&&denominatorl<0)buffer.append('-');
    	        numeratorl=Math.abs(numeratorl);denominatorl=Math.abs(denominatorl);
    	        //map,key:  numerator ,because denominator never changes;value:position of numerator/denominator 
    	        HashMap<Long, Integer>map=new HashMap<>();
    	        //handle integer part
    	        long res=numeratorl/denominatorl;
    	        numeratorl=(numeratorl%denominatorl)*10;
    			buffer.append(res);
    			if(numeratorl!=0)buffer.append('.');
    			//handle flaot part
    			while(numeratorl != 0){
    				res=numeratorl/denominatorl;
    				if(map.get(numeratorl)!=null)
    				{
    					//handle repaeting part
    					buffer.insert(map.get(numeratorl).intValue(), '(');
    					buffer.append(')');
    					break;
    				}
    				map.put(numeratorl, buffer.length());
    				numeratorl=(numeratorl%denominatorl)*10;
    		        buffer.append(res);
    			}
    	        return buffer.toString();
    	    }
    	}

  • 0
    A

    I think you do not need use long type here, since the numerator and the denominator are both int type.


  • 0
    A

    Oh, I'm wrong! The absolute of the Integer may be overflow within int type.


  • 0
    N

    long type is used to avoid overflow


  • 0
    R

    did your code pass the online judge finding the first index of occurrence is not always right.


  • 0
    G

    It is not adding that repeating integer but that repeating fraction to the map


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.