[leetcode 해시 표] 반복 소수점 에 대한 분수

2805 단어 LeetCode해시 시계
[leetcode 해시 표] 반복 소수점 에 대한 분수 
@author:wepon @blog:http://blog.csdn.net/u012162613
1. 제목
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
2. 분석
제목: 두 개의 정형 수, 하 나 는 분자 numerator, 하 나 는 분모 denominator 를 대표 하여 소수 로 결과 result 를 되 돌려 줍 니 다. 순환 소수 가 있 을 때 괄호 로 표시 합 니 다.예 를 들 어 5 / 3 = 1.666666... '1. (6)' 형식 으로 되 돌아 가 고 되 돌아 오 는 유형 은 문자열 입 니 다.
문제 풀이 요점:
1. 음수 의 처리
2、INT_MIN 의 처리, INTMIN 이 정수 로 바 뀌 면 넘 치기 때문에 long long int 로 계산 해 야 합 니 다.
3. 정수 부분 과 소수 부분 으로 나 뉘 는데 중점 은 소수 부분의 처리 에 있다. 소수 부분 이 순환 할 수 있 기 때문이다.아래 나 누 기 관찰 하기:
【leetcode 哈希表】Fraction to Recurring Decimal_第1张图片
나머지 가 4 일 때 순환 이 나타 나 기 때문에 우 리 는 해시 표를 설정 하여 매번 의 나머지 를 저장 하고 이 나머지 는 결과 result 의 아래 표 시 를 되 돌려 줄 수 있 습 니 다.매번 새로운 여 수 를 얻 을 때마다 이 나머지 가 해시 표 에 있 는 지 확인 합 니 다. 예, 순환 이 시작 되 었 음 을 설명 합 니 다. 그러면 result 에서 이 나머지 가 대응 하 는 위치 뒤에 '(', result 말미 에 ')' 를 삽입 하여 연산 을 끝 냅 니 다.하 쉬 표 에서 찾 지 못 하면 계속 정상 적 인 연산 을 한다.
3. 코드
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(numerator==0) return "0";
        string result;
        if(numerator<0 ^ denominator<0 ) result+='-';   //  ,numerator<0 denominator<0      
        //     ,INT_MIN        ,  long long。long long int n=abs(INT_MIN)   n     ,         。
        long long int n=numerator,d=denominator;
        n=abs(n);d=abs(d);              
        
        result+=to_string(n/d);  //    
        long long int r=n%d;    //  r
        if(r==0) return result;
        else result+='.';
        //        ,    
        unordered_map<int,int> map;
        while(r){
            //    r       ,         
            if(map.find(r)!=map.end()){
                result.insert(map[r],1,'(');   //http://www.cplusplus.com/reference/string/basic_string/insert/
                result+=')';
                break;
            }
            map[r]=result.size();    //       result     
            //    
            r*=10;
            result+=to_string(r/d);
            r=r%d;
        }
        return result;
    }
};

좋은 웹페이지 즐겨찾기