C++實(shí)現(xiàn)LeetCode(166.分?jǐn)?shù)轉(zhuǎn)循環(huán)小數(shù))

更新時(shí)間：2021年07月31日 16:41:11 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(166.分?jǐn)?shù)轉(zhuǎn)循環(huán)小數(shù))

[LeetCode] 166.Fraction to Recurring Decimal 分?jǐn)?shù)轉(zhuǎn)循環(huán)小數(shù)

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.

這道題還是比較有意思的，開(kāi)始還擔(dān)心萬(wàn)一結(jié)果是無(wú)限不循環(huán)小數(shù)怎么辦，百度之后才發(fā)現(xiàn)原來(lái)可以寫(xiě)成分?jǐn)?shù)的都是有理數(shù)，而有理數(shù)要么是有限的，要么是無(wú)限循環(huán)小數(shù)，無(wú)限不循環(huán)的叫無(wú)理數(shù)，例如圓周率pi或自然數(shù)e等，小學(xué)數(shù)學(xué)沒(méi)學(xué)好，汗！由于還存在正負(fù)情況，處理方式是按正數(shù)處理，符號(hào)最后在判斷，那么我們需要把除數(shù)和被除數(shù)取絕對(duì)值，那么問(wèn)題就來(lái)了：由于整型數(shù)INT的取值范圍是-2147483648～2147483647，而對(duì)-2147483648取絕對(duì)值就會(huì)超出范圍，所以我們需要先轉(zhuǎn)為long long型再取絕對(duì)值。那么怎么樣找循環(huán)呢，肯定是再得到一個(gè)數(shù)字后要看看之前有沒(méi)有出現(xiàn)這個(gè)數(shù)。為了節(jié)省搜索時(shí)間，我們采用哈希表來(lái)存數(shù)每個(gè)小數(shù)位上的數(shù)字。還有一個(gè)小技巧，由于我們要算出小數(shù)每一位，采取的方法是每次把余數(shù)乘10，再除以除數(shù)，得到的商即為小數(shù)的下一位數(shù)字。等到新算出來(lái)的數(shù)字在之前出現(xiàn)過(guò)，則在循環(huán)開(kāi)始出加左括號(hào)，結(jié)束處加右括號(hào)。代碼如下：

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;
    }
};

您可能感興趣的文章:

相關(guān)文章

解析之C++的列表初始化語(yǔ)法
有朋友在使用std::array時(shí)發(fā)現(xiàn)一個(gè)奇怪的問(wèn)題：當(dāng)元素類(lèi)型是復(fù)合類(lèi)型時(shí)，編譯通不過(guò)。按說(shuō)std::array和原生數(shù)組的行為幾乎是一樣的，可為什么當(dāng)元素類(lèi)型不同時(shí)，初始化語(yǔ)法還會(huì)有差別？這篇文章會(huì)介紹這個(gè)問(wèn)題的原理，以及正確的解決方式。
2021-05-05
關(guān)于C/C++內(nèi)存管理示例詳解
這篇文章主要給大家介紹了C/C++內(nèi)存管理的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2021-05-05
基于C++的攝像頭圖像采集及拼接程序的簡(jiǎn)單實(shí)現(xiàn)
本程序是在?ubuntu14.04?平臺(tái)下實(shí)現(xiàn)的，在本項(xiàng)目目錄下，已經(jīng)有編譯生成的可執(zhí)行程序，其中Camera_to_Frmae.cpp是我們從雙攝像頭實(shí)時(shí)抓取單幀圖像的源碼，對(duì)基于C++的攝像頭圖像采集及拼接程序的實(shí)現(xiàn)感興趣的朋友一起看看吧
2022-01-01
Qt基礎(chǔ)開(kāi)發(fā)之Qt文件操作類(lèi)QFile讀寫(xiě)文件的詳細(xì)方法與實(shí)例及QDataStream的使用方法
這篇文章主要介紹了Qt基礎(chǔ)開(kāi)發(fā)之Qt文件操作類(lèi)QFile讀寫(xiě)文件的詳細(xì)方法與實(shí)例,需要的朋友可以參考下
2020-03-03
C++實(shí)現(xiàn)LeetCode(25.每k個(gè)一組翻轉(zhuǎn)鏈表)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(25.每k個(gè)一組翻轉(zhuǎn)鏈表),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
C++實(shí)現(xiàn)LeetCode(150.計(jì)算逆波蘭表達(dá)式)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(150.計(jì)算逆波蘭表達(dá)式),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
C++?超詳細(xì)示例講解list的使用
list是一種序列式容器。list容器完成的功能實(shí)際上和數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表是極其相似的，list中的數(shù)據(jù)元素是通過(guò)鏈表指針串連成邏輯意義上的線(xiàn)性表，也就是list也具有鏈表的主要優(yōu)點(diǎn)，即：在鏈表的任一位置進(jìn)行元素的插入、刪除操作都是快速的
2022-07-07
C語(yǔ)言中如何獲取函數(shù)內(nèi)成員的值你知道嗎
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言中如何獲取函數(shù)內(nèi)成員的值的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助
2022-03-03
C++?Boost?CircularBuffer算法超詳細(xì)精講
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù)，作為標(biāo)準(zhǔn)庫(kù)的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開(kāi)發(fā)引擎之一，是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)
2022-11-11
C語(yǔ)言創(chuàng)建數(shù)組實(shí)現(xiàn)函數(shù)init,empty,reverse
這篇文章主要介紹了C語(yǔ)言創(chuàng)建數(shù)組實(shí)現(xiàn)函數(shù)init,empty,reverse,文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
2022-07-07