Sunday, January 11, 2015

12. Integer to Roman Leetcode Java

Given an integer, convert it to a roman numeral.

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

Solution:
The idea is straightforward. For each digit of the given number, find the corresponding roman letters.
3 cases:(a):1-3; (b): 4/9; (c) 5-8
I will provide two ways to process the number (1) from right-->left

 public String intToRoman(int num) {  
     String res="";  
     if(num==0) return res;  
     StringBuilder sb=new StringBuilder();  
     String[] rome={"I","V","X","L","C","D","M"};  
     int count=0;  
     while(num>0){  
       int dig=num%10;  
       count++;  
       if(dig==4 || dig==9){  
         sb.append((dig==4)? rome[2*count-1]:rome[2*count]);  
         sb.append(rome[2*count-2]);  
       }   
       else if(dig<5){  
         for(int i=0;i<dig;i++) sb.append(rome[2*count-2]);  
       }  
       else{  
         for(int i=0;i<dig-5;i++) sb.append(rome[2*count-2]);  
         sb.append(rome[2*count-1]);  
       }  
       num=num/10;  
     }  
     return sb.reverse().toString();  
   }  

(2) from left-->right

 public String intToRoman(int num) {  
    StringBuilder result= new StringBuilder();  
    char[] roman={'I','V','X','L','C','D','M'};  
    int div=1000;  
    int i=6;  
    while(div!=0){  
      int dig=num/div;  
      switch(dig){  
        case 9: result.append(roman[i]).append(roman[i+2]); break;  
        case 8: result.append(roman[i+1]).append(roman[i]).append(roman[i]).append(roman[i]); break;  
        case 7: result.append(roman[i+1]).append(roman[i]).append(roman[i]); break;  
        case 6: result.append(roman[i+1]).append(roman[i]); break;  
        case 5: result.append(roman[i+1]); break;  
        case 4: result.append(roman[i]).append(roman[i+1]); break;  
        case 3: result.append(roman[i]).append(roman[i]).append(roman[i]); break;  
        case 2: result.append(roman[i]).append(roman[i]); break;  
        case 1: result.append(roman[i]); break;  
        case 0: break;  
        default: break;  
      }  
      num=num%div;  
      div=div/10;  
      i=i-2;  
    }  
    return result.toString();  
   }  

No comments:

Post a Comment