程式隨筆
0%

【LeetCode】Fraction to Recurring Decimal

Posted on Edited on In Disqus:

#題目

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.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”

Example 2:

Input: numerator = 2, denominator = 1
Output: “2”

Example 3:

Input: numerator = 2, denominator = 3
Output: “0.(6)”

1
2
3
4
5
public class Solution {
    public string FractionToDecimal(int numerator, int denominator) {
        
    }
}

#解題

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_1_denominator_2()
{
    //arrange
    var sut = new Solution();
    var numerator = 1;
    var denominator = 2;

    var expected = "0.5";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(expected);
}
1
2
3
4
5
6
public string FractionToDecimal(int numerator, int denominator)
{
    decimal result = Convert.ToDecimal(numerator) / Convert.ToDecimal(denominator);

    return result.ToString();
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_2_denominator_1()
{
    //arrange
    var sut = new Solution();
    var numerator = 2;
    var denominator = 1;

    var expected = "2";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(expected);
}

直接通過測試

案例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_2_denominator_3()
{
    //arrange
    var sut = new Solution();
    var numerator = 2;
    var denominator = 3;

    var expected = "0.(6)";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(expected);
}
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
public string FractionToDecimal(int numerator, int denominator)
{
    StringBuilder sb = new StringBuilder();
    sb.Append(numerator / denominator);

    //餘數
    var Remainder = (numerator % denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<int, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / denominator);
        Remainder = (Remainder * 10) % denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

關鍵在找出餘數相同時的那一刻，餘數開始重複代表規律產生了，因為餘數乘10等於下次的被除數，除數永遠不變的情況下將開始循環。

記錄下每次餘數當下字串的長度，當下次產生相同餘數，則從Dictionary取得上一次出現的位置補上括號即可

#解析

溢位問題

LeetCode測試錯誤

/images/20180627/leetcode/1.jpg

/images/20180627/leetcode/2.jpg

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_負2147483648_denominator_負1()
{
    //arrange
    var sut = new Solution();
    var numerator = -2147483648;
    var denominator = -1;

    var expected = "2147483648";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(expected);
}
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
public string FractionToDecimal(int numerator, int denominator)
{
    StringBuilder sb = new StringBuilder();

    var _numerator = Convert.ToInt64(numerator);
    var _denominator = Convert.ToInt64(denominator);
    sb.Append(_numerator / _denominator);

    //餘數
    var Remainder = (_numerator % _denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<Int64, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / denominator);
        Remainder = (Remainder * 10) % denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

負數問題

/images/20180627/leetcode/3.jpg

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_負50_denominator_8()
{
    //arrange
    var sut = new Solution();
    var numerator = -50;
    var denominator = 8;
    
    var expected = "-6.25";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(expected);
}

如果運算之中有正負號時，則可能組出來的字串為 -6.-2-5，顯然這不是我們要的，要將負號在最前面優先處理，接著後面的計算都用正數來處理

結果為負數，只有在兩個數為一正一負時，當兩正或兩負算出來的皆還是會正值，可以用^(XOR)來判別

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
public string FractionToDecimal(int numerator, int denominator)
{
    StringBuilder sb = new StringBuilder();

    //考慮負數
    sb.Append((numerator >= 0) ^ (denominator >= 0) ? "-" : string.Empty);

    //只取正數
    var _numerator =Math.Abs(Convert.ToInt64(numerator));
    var _denominator = Math.Abs(Convert.ToInt64(denominator));
    sb.Append(_numerator / _denominator);

    //餘數
    var Remainder = (_numerator % _denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<Int64, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / _denominator);
        Remainder = (Remainder * 10) % _denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

被除數為0問題

當被除數為0時，回傳結果應為0且無關正負

補上案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod]
public void FractionToDecimalTest_輸入numerator_0_denominator_負5()
{
    //arrange
    var sut = new Solution();
    var numerator = 0;
    var denominator = -5;

    var expected = "0";
    //act
    var actual = sut.FractionToDecimal(numerator, denominator);

    //assert
    actual.Should().Be(expected);
}
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
public string FractionToDecimal(int numerator, int denominator)
{
    if (numerator == 0)
    {
        return "0";
    }

    StringBuilder sb = new StringBuilder();

    //考慮負數
    sb.Append((numerator >= 0) ^ (denominator >= 0) ? "-" : string.Empty);

    //只取正數
    var _numerator =Math.Abs(Convert.ToInt64(numerator));
    var _denominator = Math.Abs(Convert.ToInt64(denominator));
    sb.Append(_numerator / _denominator);

    //餘數
    var Remainder = (_numerator % _denominator);
    if (Remainder == 0)
    {
        return sb.ToString();
    }

    sb.Append(".");
    var Map = new Dictionary<Int64, int>();
    Map.Add(Remainder, sb.Length);
    while (Remainder != 0)
    {
        sb.Append((Remainder *10) / _denominator);
        Remainder = (Remainder * 10) % _denominator;
        if (Map.ContainsKey(Remainder))
        {
            var Index = Map[Remainder];
            //開始重複
            sb.Insert(Index, "(");
            sb.Append(")");
            break;
        }

        Map.Add(Remainder, sb.Length);
    }

    return sb.ToString();
}

/images/20180627/leetcode/5.jpg