[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. 정수 부분 과 소수 부분 으로 나 뉘 는데 중점 은 소수 부분의 처리 에 있다. 소수 부분 이 순환 할 수 있 기 때문이다.아래 나 누 기 관찰 하기:
나머지 가 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;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.