C++實現(xiàn)LeetCode(166.分數(shù)轉循環(huán)小數(shù))

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

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

[LeetCode] 166.Fraction to Recurring Decimal 分數(shù)轉循環(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.

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

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

您可能感興趣的文章:

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