972. Equal Rational Numbers
leetcode hard
Task
Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.
Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:
<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:
1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).
Пример:
Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.
C# solution
matched/originalpublic class Solution {
public bool IsRationalEqual(string S, string T) {
Fraction f1 = Convert(S);
Fraction f2 = Convert(T);
return f1.n == f2.n && f1.d == f2.d;
}
public Fraction Convert(string S) {
int state = 0;
Fraction ans = new Fraction(0, 1);
int decimal_size = 0;
foreach (string part in S.Split(new char[] { '.', '(', ')' })) {
state++;
if (string.IsNullOrEmpty(part)) continue;
long x = long.Parse(part);
int sz = part.Length;
if (state == 1) {
ans.Iadd(new Fraction(x, 1));
} else if (state == 2) {
ans.Iadd(new Fraction(x, (long)Math.Pow(10, sz)));
decimal_size = sz;
} else {
long denom = (long)Math.Pow(10, decimal_size);
denom *= (long)(Math.Pow(10, sz) - 1);
ans.Iadd(new Fraction(x, denom));
}
}
return ans;
}
}
public class Fraction {
public long n, d;
public Fraction(long n, long d) {
long g = Gcd(n, d);
this.n = n / g;
this.d = d / g;
}
public void Iadd(Fraction other) {
long numerator = this.n * other.d + this.d * other.n;
long denominator = this.d * other.d;
long g = Gcd(numerator, denominator);
this.n = numerator / g;
this.d = denominator / g;
}
public static long Gcd(long x, long y) {
return x != 0 ? Gcd(y % x, x) : y;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public bool IsRationalEqual(string S, string T) {
Fraction f1 = Convert(S);
Fraction f2 = Convert(T);
return f1.n == f2.n && f1.d == f2.d;
}
public Fraction Convert(string S) {
int state = 0;
Fraction ans = new Fraction(0, 1);
int decimal_size = 0;
foreach (string part in S.Split(new char[] { '.', '(', ')' })) {
state++;
if (string.IsNullOrEmpty(part)) continue;
long x = long.Parse(part);
int sz = part.size();
if (state == 1) {
ans.Iadd(new Fraction(x, 1));
} else if (state == 2) {
ans.Iadd(new Fraction(x, (long)Math.Pow(10, sz)));
decimal_size = sz;
} else {
long denom = (long)Math.Pow(10, decimal_size);
denom *= (long)(Math.Pow(10, sz) - 1);
ans.Iadd(new Fraction(x, denom));
}
}
return ans;
}
}
public class Fraction {
public long n, d;
public Fraction(long n, long d) {
long g = Gcd(n, d);
this.n = n / g;
this.d = d / g;
}
public void Iadd(Fraction other) {
long numerator = this.n * other.d + this.d * other.n;
long denominator = this.d * other.d;
long g = Gcd(numerator, denominator);
this.n = numerator / g;
this.d = denominator / g;
}
public static long Gcd(long x, long y) {
return x != 0 ? Gcd(y % x, x) : y;
}
}Java solution
matched/originalclass Solution {
public boolean isRationalEqual(String S, String T) {
Fraction f1 = convert(S);
Fraction f2 = convert(T);
return f1.n == f2.n && f1.d == f2.d;
}
public Fraction convert(String S) {
int state = 0;
Fraction ans = new Fraction(0, 1);
int decimal_size = 0;
for (String part: S.split("[.()]")) {
state++;
if (part.isEmpty()) continue;
long x = Long.valueOf(part);
int sz = part.length();
if (state == 1) {
ans.iadd(new Fraction(x, 1));
} else if (state == 2) {
ans.iadd(new Fraction(x, (long) Math.pow(10, sz)));
decimal_size = sz;
} else {
long denom = (long) Math.pow(10, decimal_size);
denom *= (long) (Math.pow(10, sz) - 1);
ans.iadd(new Fraction(x, denom));
}
}
return ans;
}
}
class Fraction {
long n, d;
Fraction(long n, long d) {
long g = gcd(n, d);
this.n = n / g;
this.d = d / g;
}
public void iadd(Fraction other) {
long numerator = this.n * other.d + this.d * other.n;
long denominator = this.d * other.d;
long g = Fraction.gcd(numerator, denominator);
this.n = numerator / g;
this.d = denominator / g;
}
static long gcd(long x, long y) {
return x != 0 ? gcd(y % x, x) : y;
}
}Python solution
matched/originalfrom math import gcd
class Fraction:
def __init__(self, n, d):
g = gcd(n, d)
self.n = n // g
self.d = d // g
def iadd(self, other):
numerator = self.n * other.d + self.d * other.n
denominator = self.d * other.d
g = gcd(numerator, denominator)
self.n = numerator // g
self.d = denominator // g
class Solution:
def isRationalEqual(self, S: str, T: str) -> bool:
f1 = self.convert(S)
f2 = self.convert(T)
return f1.n == f2.n and f1.d == f2.d
def convert(self, S: str) -> Fraction:
state = 0
ans = Fraction(0, 1)
decimal_size = 0
for part in S.split('.'):
state += 1
if not part:
continue
x = int(part)
sz = len(part)
if state == 1:
ans.iadd(Fraction(x, 1))
elif state == 2:
ans.iadd(Fraction(x, 10 ** sz))
decimal_size = sz
else:
denom = 10 ** decimal_size
denom *= 10 ** sz - 1
ans.iadd(Fraction(x, denom))
return ansGo solution
matched/originalpackage main
import (
"math"
"strconv"
"strings"
)
type Fraction struct {
n, d int64
}
func (f *Fraction) iadd(other Fraction) {
numerator := f.n*other.d + f.d*other.n
denominator := f.d * other.d
g := gcd(numerator, denominator)
f.n = numerator / g
f.d = denominator / g
}
func gcd(x, y int64) int64 {
if x != 0 {
return gcd(y%x, x)
}
return y
}
func isRationalEqual(S string, T string) bool {
f1 := convert(S)
f2 := convert(T)
return f1.n == f2.n && f1.d == f2.d
}
func convert(S string) Fraction {
state := 0
ans := Fraction{0, 1}
decimalSize := 0
parts := strings.FieldsFunc(S, func(r rune) bool {
return r == '.' || r == '(' || r == ')'
})
for _, part := range parts {
state++
if part == "" {
continue
}
x, _ := strconv.ParseInt(part, 10, 64)
sz := len(part)
if state == 1 {
ans.iadd(Fraction{x, 1})
} else if state == 2 {
ans.iadd(Fraction{x, int64(math.Pow(10, float64(sz)))})
decimalSize = sz
} else {
denom := int64(math.Pow(10, float64(decimalSize)))
denom *= int64(math.Pow(10, float64(sz)) - 1)
ans.iadd(Fraction{x, denom})
}
}
return ans
}
func main() {
// Test the function here
}Explanation
Algorithm
Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.
Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.
Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.
😎