时间轴

2025-09-24

init

题目：

P166 分数到小数

https://leetcode.cn/problems/fraction-to-recurring-decimal/description/?envType=daily-question&envId=2025-09-26

我采用模拟的方法，拼尽全力终于战胜，特殊情况太多了，最好是用 gdb 一次次调试发现代码中没有考虑到的地方再完善。
注意不要先除以最大公因数，因为最大公因数的计算时间复杂度要高于长除法。
此外最好先计算整数部分，再计算小数部分，我的这个解法没有考虑这个导致代码有点复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <numeric>
#include <string>
#include <unordered_map>
#include <vector>

using std::string;
using std::unordered_map;
using std::vector;

class Solution {
public:
  string fractionToDecimal(int numerator, int denominator) {

    unsigned long long dividend;
    unsigned long long divisor;
    unsigned long long quotient;
    unsigned long long reminder;
    int dot = -1;
    int bracket = -1;
    // 记录结果
    vector<int> res_vec;
    // 记录numerator的每一位
    vector<int> numerator_vec;
    // 记录所有被除数
    unordered_map<unsigned long long, unsigned long long> div_map;
    string res;
    int i = 0;
    int n;
    bool negative = false;

    // 0除以任何数都为0
    if (numerator == 0) {
      return "0";
    }
    if ((numerator < 0 && denominator > 0) ||
        (numerator > 0 && denominator < 0)) {
      negative = true;
    }
    // 不用abs主要是因为abs返回的是unsigned int存在范围问题
    dividend = std::llabs((long long)numerator);
    divisor = std::llabs((long long)denominator);

    // 先都除以最大公因数
    // n = std::gcd(dividend, divisor);
    // dividend /= n;
    // divisor /= n;

    // 将numerator每一位放入numerator_vec中
    while (dividend != 0) {
      numerator_vec.insert(numerator_vec.begin(), dividend % 10);
      dividend /= 10;
    }
    dividend = 0;
    // 高精度除法

    // 第一个被除数
    n = numerator_vec.size();
    while (i < n && dividend < divisor) {
      dividend = dividend * 10 + numerator_vec[i];
      i++;
    }

    do {
      // 记录被除数
      if (div_map.find(dividend) != div_map.end() && dot > 0) { // 重复了
        bracket = div_map[dividend];                            // 重复的位置
        break;
      } else {
        div_map[dividend] = res_vec.size();
      }
      // 商 = 被除数/除数
      quotient = dividend / divisor;
      // 余数 = 被除数/除数
      reminder = dividend % divisor;
      res_vec.push_back(quotient);

      if (i < numerator_vec.size()) {
        dividend = reminder * 10 + numerator_vec[i];
        i++;
        reminder = 1; // 防止退出循环
      } else {
        dividend = reminder * 10;
        if (dot < 0)
          dot = res_vec.size();
      }

    } while (reminder != 0);

    if (bracket >= 0 && dot > 0 && bracket < dot) {
      n = dot - bracket;
      for (i = 0; i < n; i++) {
        res_vec.push_back(res_vec[i + bracket]);
      }
      bracket = dot;
    }

    n = res_vec.size();
    // 构建字符串
    if (negative) {
      res += '-';
    }

    for (i = 0; i < n; i++) {
      if (i == dot) {
        res += '.';
      }
      if (i == bracket) {
        res += '(';
      }

      res += '0' + res_vec[i];
    }

    if (bracket > 0) {
      res += ')';
    }

    return res;
  }
};

int main() {
  Solution s;
  printf("%s\n", s.fractionToDecimal(420, 226).c_str());
  printf("%s\n", s.fractionToDecimal(-22, -2).c_str());
  printf("%s\n", s.fractionToDecimal(500, 10).c_str());
  printf("%s\n", s.fractionToDecimal(4, 333).c_str());
  printf("%s\n", s.fractionToDecimal(50, 8).c_str());
}

官方方法也是模拟长除法，但不同的是我是记录了被除数，这个解法记录的是余数从而判断是否产生了循环小数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long numeratorLong = numerator;
        long denominatorLong = denominator;
        if (numeratorLong % denominatorLong == 0) {
            return to_string(numeratorLong / denominatorLong);
        }

        string ans;
        if (numeratorLong < 0 ^ denominatorLong < 0) {
            ans.push_back('-');
        }

        // 整数部分
        numeratorLong = abs(numeratorLong);
        denominatorLong = abs(denominatorLong);
        long integerPart = numeratorLong / denominatorLong;
        ans += to_string(integerPart);
        ans.push_back('.');

        // 小数部分
        string fractionPart;
        unordered_map<long, int> remainderIndexMap;
        long remainder = numeratorLong % denominatorLong;
        int index = 0;
        while (remainder != 0 && !remainderIndexMap.count(remainder)) {
            remainderIndexMap[remainder] = index;
            remainder *= 10;
            fractionPart += to_string(remainder / denominatorLong);
            remainder %= denominatorLong;
            index++;
        }
        if (remainder != 0) { // 有循环节
            int insertIndex = remainderIndexMap[remainder];
            fractionPart = fractionPart.substr(0,insertIndex) + '(' + fractionPart.substr(insertIndex);
            fractionPart.push_back(')');
        }
        ans += fractionPart;

        return ans;
    }
};