C++LeetCode 구현(166.점수 순환 소수)

[LeetCode]166.Fraction to Recurring 소수점 순환 소수
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)".
  • Credits:
    Special thanks to @Shangrila for adding this problem and creating all test cases.
    이 문 제 는 비교적 재 미 있 습 니 다.만약 에 결과 가 무한 순환 소수 라면 어떻게 해 야 할 지 걱정 했 습 니 다.바 이 두 후에 야 점수 로 쓸 수 있 는 것 은 모두 유리수 라 는 것 을 알 게 되 었 습 니 다.유리 수 는 유한 하거나 무한 순환 소수,무한 순환 소수 라 고 부 릅 니 다.예 를 들 어 원주율 pi 나 자연수 e 등 초등학교 수학 을 잘 배우 지 못 해서 땀 이 납 니 다!플러스 와 마이너스 상황 이 존재 하기 때문에 처리 방식 은 정수 에 따라 처리 하고 기 호 는 마지막 으로 판단 한다.그러면 우 리 는 나 누 기와 피 나 누 기 를 절대 치 로 해 야 한다.그러면 문 제 는 바로 문제 이다.정형 수 INT 의 수치 범 위 는-2147483648~21474483647 이 고-2147483648 에 대해 절대 치 를 취하 면 범 위 를 초과 하기 때문에 우 리 는 먼저 long 형 으로 전환 한 다음 에 절대 치 를 취해 야 한다.그렇다면 어떻게 순환 을 찾 을 것 인가?분명 한 숫자 를 하나 더 얻 은 후에 그 전에 이 숫자 가 나 왔 는 지 살 펴 봐 야 한다.검색 시간 을 절약 하기 위해 서 우 리 는 해시 표를 이용 하여 모든 작은 숫자 에 있 는 숫자 를 저장 합 니 다.또 하나의 작은 기교 가 있 습 니 다.우 리 는 소수 각 자 를 계산 해 야 하기 때문에 취 하 는 방법 은 매번 나머지 를 10 으로 곱 한 다음 에 나 누 는 것 입 니 다.얻 은 상 은 바로 소수 의 다음 숫자 입 니 다.새로 계 산 된 숫자 가 이전에 나타 나 면 순환 에서 왼쪽 괄호 를 넣 고 끝 에 오른쪽 괄호 를 넣는다.코드 는 다음 과 같 습 니 다:
    
    class Solution {
    public:
        string fractionToDecimal(int numerator, int denominator) {
            int s1 = numerator >= 0 ? 1 : -1;
            int s2 = denominator >= 0 ? 1 : -1;
            long long num = abs( (long long)numerator );
            long long den = abs( (long long)denominator );
            long long out = num / den;
            long long rem = num % den;
            unordered_map<long long, int> m;
            string res = to_string(out);
            if (s1 * s2 == -1 && (out > 0 || rem > 0)) res = "-" + res;
            if (rem == 0) return res;
            res += ".";
            string s = "";
            int pos = 0;
            while (rem != 0) {
                if (m.find(rem) != m.end()) {
                    s.insert(m[rem], "(");
                    s += ")";
                    return res + s;
                }
                m[rem] = pos;
                s += to_string((rem * 10) / den);
                rem = (rem * 10) % den;
                ++pos;
            }
            return res + s;
        }
    };

    좋은 웹페이지 즐겨찾기