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.

這道題還是比較有意思的，開始還擔(dān)心萬一結(jié)果是無限不循環(huán)小數(shù)怎么辦，百度之后才發(fā)現(xiàn)原來可以寫成分?jǐn)?shù)的都是有理數(shù)，而有理數(shù)要么是有限的，要么是無限循環(huán)小數(shù)，無限不循環(huán)的叫無理數(shù)，例如圓周率pi或自然數(shù)e等，小學(xué)數(shù)學(xué)沒學(xué)好，汗！由于還存在正負(fù)情況，處理方式是按正數(shù)處理，符號(hào)最后在判斷，那么我們需要把除數(shù)和被除數(shù)取絕對(duì)值，那么問題就來了：由于整型數(shù)INT的取值范圍是-2147483648～2147483647，而對(duì)-2147483648取絕對(duì)值就會(huì)超出范圍，所以我們需要先轉(zhuǎn)為long long型再取絕對(duì)值。那么怎么樣找循環(huán)呢，肯定是再得到一個(gè)數(shù)字后要看看之前有沒有出現(xiàn)這個(gè)數(shù)。為了節(jié)省搜索時(shí)間，我們采用哈希表來存數(shù)每個(gè)小數(shù)位上的數(shù)字。還有一個(gè)小技巧，由于我們要算出小數(shù)每一位，采取的方法是每次把余數(shù)乘10，再除以除數(shù)，得到的商即為小數(shù)的下一位數(shù)字。等到新算出來的數(shù)字在之前出現(xiàn)過，則在循環(huán)開始出加左括號(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++的列表初始化語法
有朋友在使用std::array時(shí)發(fā)現(xiàn)一個(gè)奇怪的問題：當(dāng)元素類型是復(fù)合類型時(shí)，編譯通不過。按說std::array和原生數(shù)組的行為幾乎是一樣的，可為什么當(dāng)元素類型不同時(shí)，初始化語法還會(huì)有差別？這篇文章會(huì)介紹這個(gè)問題的原理，以及正確的解決方式。
2021-05-05
關(guān)于C/C++內(nèi)存管理示例詳解
這篇文章主要給大家介紹了C/C++內(nèi)存管理的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-05-05
基于C++的攝像頭圖像采集及拼接程序的簡單實(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ǔ)開發(fā)之Qt文件操作類QFile讀寫文件的詳細(xì)方法與實(shí)例及QDataStream的使用方法
這篇文章主要介紹了Qt基礎(chǔ)開發(fā)之Qt文件操作類QFile讀寫文件的詳細(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)鏈表),本篇文章通過簡要的案例,講解了該項(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á)式),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
C++?超詳細(xì)示例講解list的使用
list是一種序列式容器。list容器完成的功能實(shí)際上和數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表是極其相似的，list中的數(shù)據(jù)元素是通過鏈表指針串連成邏輯意義上的線性表，也就是list也具有鏈表的主要優(yōu)點(diǎn)，即：在鏈表的任一位置進(jìn)行元素的插入、刪除操作都是快速的
2022-07-07
C語言中如何獲取函數(shù)內(nèi)成員的值你知道嗎
這篇文章主要為大家詳細(xì)介紹了C語言中如何獲取函數(shù)內(nèi)成員的值的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-03-03
C++?Boost?CircularBuffer算法超詳細(xì)精講
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱
2022-11-11
C語言創(chuàng)建數(shù)組實(shí)現(xiàn)函數(shù)init,empty,reverse
這篇文章主要介紹了C語言創(chuàng)建數(shù)組實(shí)現(xiàn)函數(shù)init,empty,reverse,文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
2022-07-07