FractionAdditionAndSubtraction [source code]
public class FractionAdditionAndSubtraction {
static
/******************************************************************************/
public class Solution {
public String fractionAddition(String expression) {
int count = 0;
char[] chs = expression.toCharArray();
for (char c : chs)
if (c == '/')
count++;
int[][] nums = new int[count][2];
count = 0;
for (int i = 0; i < chs.length; i++) {
if (chs[i] == '/') {
nums[count][0] = Character.getNumericValue(chs[i - 1]);
if (i - 2 >= 0) {
if (chs[i - 2] == '-')
nums[count][0] = -nums[count][0];
else if (chs[i - 1] == '0' && chs[i - 2] == '1') {
nums[count][0] += 10;
if (i - 3 >= 0 && chs[i - 3] == '-')
nums[count][0] = -nums[count][0];
}
}
nums[count][1] = Character.getNumericValue(chs[i + 1]);
if (i + 2 < chs.length && chs[i + 1] == '1' && chs[i + 2] == '0')
nums[count][1] *= 10;
count++;
}
}
int[] res = nums[0];
for (int i = 1; i < nums.length; i++) {
res[0] = res[0] * nums[i][1] + res[1] * nums[i][0];
res[1] = res[1] * nums[i][1];
}
if (res[0] == 0)
return "0/1";
for (int i = Math.min(Math.abs(res[0]), Math.abs(res[1])); i >= 2; ) {
if (res[0] % i == 0 && res[1] % i == 0) {
res[0] /= i;
res[1] /= i;
} else i--;
}
return res[0] + "/" + res[1];
}
}
/******************************************************************************/
public static void main(String[] args) {
FractionAdditionAndSubtraction.Solution tester = new FractionAdditionAndSubtraction.Solution();
String[] inputs = {
"-1/2+1/2", "0/1",
"-1/2+1/2+1/3", "1/3",
"1/3-1/2", "-1/6",
"5/3+1/3", "2/1",
"-5/2+10/3+7/9", "29/18",
"-1/4-4/5-1/4", "-13/10",
"3/10+1/5-10/7-5/6-2/5", "-227/105",
};
for (int i = 0; i < inputs.length / 2; i++) {
String e = inputs[2 * i];
String ans = inputs[1 + 2 * i];
System.out.println(Printer.separator());
String res = tester.fractionAddition(e);
System.out.println(
Printer.wrapColor(e, "magenta") +
" -> " + res +
Printer.wrapColor(", expected: " + ans, ans.equals(res) ? "green" : "red")
);
}
}
}
这题目直接的笨办法也是很简单的, 就是分数计算, 然后最后约分就行了; 约分的过程可能稍微麻烦一点, 不过应该不是做不出来; 先这样写写看, 看写的过程中能不能通过分析人逻辑想出来什么优化;
大概就这么写出来了, 最后的速度是119ms (7%), 很不满意; 看了submission的分布图, 明显是做错了思路, 前面更快的有一整个梯队;
约分的步骤刚开始是这样写的, 不过后来发现这样写好像不对:
for (int i = 2; i <= (int) Math.sqrt(Math.min(Math.abs(res[0]), Math.abs(res[1]))); ) {
System.out.println("i: " + i + " > " + Printer.array(res));
if (res[0] % i == 0 && res[1] % i == 0) {
res[0] /= i;
res[1] /= i;
} else i++;
System.out.println("i: " + i + " > " + Printer.array(res));
}
这里是求公约数, 所以没有证据表明到了平方根就应该停止;
另外约分的过程最好从大的开始约, 因为比如你可以约8, 就省的你后面越两个2了;
而且从小到大约有一个问题, 一个i可能需要约多次, 所以这里i有一个conditional increment的操作; 我上面的ver1代码还是沿用了这个思路, 但是实际上, 如果是从上到下约, 就没有必要这样操作了;
改掉这个东西以后:
for (int i = Math.min(Math.abs(res[0]), Math.abs(res[1])); i >= 2; i--) {
if (res[0] % i == 0 && res[1] % i == 0) {
res[0] /= i;
res[1] /= i;
}
}
速度变成了100ms. 稍微好了一点, 不过看来还是不是关键问题;
当时写的时候想要用GCD的算法来求这个约分的上限, 但是感觉提升很大吗? 觉得有可能提升不大, 加上GCD算法本身我其实也不太熟悉, 就作罢了;
editorial给出了两个解法, 好像还是一个比较机械的做法;
editorial1的解法的基础是LCM; 首先拆分的时候他跟我的做法就不一样, 他split两次, 一次是正负号, 一次是用/. 并且sign他还专门用一个array来保存;
得到分数之后, 他把所有的分数都一起通分, 分母就是LCM; 对每一个分数计算出一个通分系数 = LCM / denominator;
LCM的计算方法:
- lcm(a,b,c) = lcm(lcm(a,b), c)
- lcm(a,b) = a * b / gcd(a,b)
这个还是值得学习一下的;
虽然解法本身并不让人觉得特别聪明;
另外约分这里, 他们给出了另外一个观点: GCD并不单纯是你约分的循环的上限, 而是唯一一个你需要约掉的因子! 感觉这个可能就是为什么我的做法这么慢; 当然话说回来了, 并不怪罪好吧, 我还是鼓励多写笨办法; //把我的做法改写成这种约分思路之后, 果然速度就上去了: 10(91). 好吧, 长了一智. 按说也应该是这样的, 我这里很多处理都是比他这个方法要好的, 包括split的做法;
通分的做法我其实也不认为他的做法就比我的好; 其实最后的是等价的两个做法;
public class Solution {
public String fractionAddition(String expression) {
List < Character > sign = new ArrayList < > ();
for (int i = 1; i < expression.length(); i++) {
if (expression.charAt(i) == '+' || expression.charAt(i) == '-')
sign.add(expression.charAt(i));
}
List < Integer > num = new ArrayList < > ();
List < Integer > den = new ArrayList < > ();
for (String sub: expression.split("\\+")) {
for (String subsub: sub.split("-")) {
if (subsub.length() > 0) {
String[] fraction = subsub.split("/");
num.add(Integer.parseInt(fraction[0]));
den.add(Integer.parseInt(fraction[1]));
}
}
}
if (expression.charAt(0) == '-')
num.set(0, -num.get(0));
int lcm = 1;
for (int x: den) {
lcm = lcm_(lcm, x);
}
int res = lcm / den.get(0) * num.get(0);
for (int i = 1; i < num.size(); i++) {
if (sign.get(i - 1) == '+')
res += lcm / den.get(i) * num.get(i);
else
res -= lcm / den.get(i) * num.get(i);
}
int g = gcd(Math.abs(res), Math.abs(lcm));
return (res / g) + "/" + (lcm / g);
}
public int lcm_(int a, int b) {
return a * b / gcd(a, b);
}
public int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
}
我刚开始也是想用split来parse的, 但是"split on 正负号"这样的逻辑总感觉好像必须用什么或逻辑的语法来做, 这个在regex我又不会, 所以就没有做了; 事实上也没有这么复杂, 直接两个嵌套的split就行了; 虽然这一题来说这种做法相对于我自己的手动做法并没有什么优势, 不过知道这么一个或逻辑*的实现, 还是有用的; 当然, 最好的肯定还是直接就知道怎么写对应的regex语法是最好的了;
另外他这里LCM的算法是完全用iteration来做的, 我怎么感觉这个好像用recursion好写一些? 当然实际上是差不多的, Bottom-Up和Top-Down的区别而已;
约分直接就是除一个GCD, 这个上面也说过了; GCD算法这个, 是Euclidean GCD algorithm, 以前好像见过, 但是没有记住; 复杂度是O(log(a.b)). 这个算法基本就是这么写了, 尝试了一下改写, 好像不太好改写;
editorial2好像就是跟我的做法很像了:
public class Solution {
public String fractionAddition(String expression) {
List < Character > sign = new ArrayList < > ();
if (expression.charAt(0) != '-')
sign.add('+');
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '+' || expression.charAt(i) == '-')
sign.add(expression.charAt(i));
}
int prev_num = 0, prev_den = 1, i = 0;
for (String sub: expression.split("(\\+)|(-)")) {
if (sub.length() > 0) {
String[] fraction = sub.split("/");
int num = (Integer.parseInt(fraction[0]));
int den = (Integer.parseInt(fraction[1]));
int g = Math.abs(gcd(den, prev_den));
if (sign.get(i++) == '+')
prev_num = prev_num * den / g + num * prev_den / g;
else
prev_num = prev_num * den / g - num * prev_den / g;
prev_den = den * prev_den / g;
g = Math.abs(gcd(prev_den, prev_num));
prev_num /= g;
prev_den /= g;
}
}
return prev_num + "/" + prev_den;
}
public int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
}
当然split等小细节的处理跟我还是有点区别;
另外这里展示了regex的或逻辑的用法;
这个做法的有时就是优化了空间, 只保存几个prev就行了, 有点像我的res; 另外一个就是他每一个数字处理的时候, 当时就已经在不停的约分, 来避免overflow; 总体来说不是什么特别出彩的解法;
discussion上面Stefan给出的解法:
public String fractionAddition(String expression) {
Scanner sc = new Scanner(expression).useDelimiter("/|(?=[-+])");
int A = 0, B = 1;
while (sc.hasNext()) {
int a = sc.nextInt(), b = sc.nextInt();
A = A * b + a * B;
B *= b;
int g = gcd(A, B);
A /= g;
B /= g;
}
return A + "/" + B;
}
private int gcd(int a, int b) {
return a != 0 ? gcd(b % a, a) : Math.abs(b);
}
一如既往的简短;
不过这个scanner的API好像确实是好用;
感觉大概了解一下就行了吧, 手动的做法还是要会, 真正要是面试的时候面试官不然你用这种API怎么办呢; 毕竟这个是面试, 不是你自己平时写代码;
注意他这里也是每一次加法都要进行一次约分;
另外他这里没有像editorial里面那样把sign还专门单独处理, 直接用API当成一个int整体处理了;
这个是关于scanner的一个解释:
The (?=) part is a zero-width positive lookahead. Since [-,+] means - or +, the regex (?=[-,+]) means the next element is either - or +.
Since | is logical or operator, "/|(?=[-+])" means the element is "/", or the next element is either - or +. For example, when expression = "-1/2+1/2-1/3",
Scanner sc = new Scanner(expression).useDelimiter("/|(?=[-+])")
generates [-1, 2, +1, 2, -1, 3 ]. Note that the signs - and + are preserved.
当然也可以避免每一个加法都算一次GCD:
public String fractionAddition1(String expression) {
Scanner s = new Scanner(expression).useDelimiter("/|(?=[-+])");
long num = 0, den = 1;
while (s.hasNext()) {
long a = s.nextLong(), b = s.nextLong();
num = num * b + a * den;
den *= b;
}
long gcd = gcd(num, den);
return (num / gcd) + "/" + (den / gcd);
}
private long gcd(long a, long b) {
if (b == 0)
return a < 0 ? -a : a; // always return positive gcd
return gcd(b, a % b);
}
用long来避免就行了,虽然实际上因为Test Case很小, 所以并没有碰到溢出的情况;
这个是一个类似的用了regex的解法:
public String fractionAddition(String expression) {
String[] fracs = expression.split("(?=[-+])"); // splits input string into individual fractions
String res = "0/1";
for (String frac : fracs) res = add(res, frac); // add all fractions together
return res;
}
public String add(String frac1, String frac2) {
int[] f1 = Stream.of(frac1.split("/")).mapToInt(Integer::parseInt).toArray(),
f2 = Stream.of(frac2.split("/")).mapToInt(Integer::parseInt).toArray();
int numer = f1[0]*f2[1] + f1[1]*f2[0], denom = f1[1]*f2[1];
String sign = "";
if (numer < 0) {sign = "-"; numer *= -1;}
return sign + numer/gcd(numer, denom) + "/" + denom/gcd(numer, denom); // construct reduced fraction
}
// Computes gcd using Euclidean algorithm
public int gcd(int x, int y) { return x == 0 || y == 0 ? x + y : gcd(y, x % y); }
The (?=) part is a zero-width positive lookahead. Since [-,+] means - or +, the regex (?=[-,+]) means the next element is either - or +.
Thus, expression.split("(?=[-,+])") is to split expression at the positions whose next element is either - or +. For example, when expression = "-1/2+1/2-1/3", expression.split("(?=[-,+])") generates an array of strings ["-1/2","+1/2", "-1/3"].
总体思路是类似的; 只不过做法上相对简洁一些. add本身的内容还是正常的分数加法, 而且每一个add都有一次约分操作;
注意这里GCD的算法是用recursion来写; 相对于iteration的写法好像更容易记忆一些;
这个是discussion给的一个奇葩解法, 是对上面这个算法的优化:
i think we can use the magic number "2520" instead of invoking gcd() multiple times:
```javapublic class Solution {
public String fractionAddition(String expression) {
if (expression.charAt(0) != '-') expression = "+" + expression;
int positive = expression.charAt(0) == '-' ? -1 : 1, num = 0;
ArrayList
for (char c : expression.toCharArray()) {
if (c == '+' || c == '-') {
denominators.add(num);
num = 0;
positive = c == '+' ? 1 : -1;
} else if (c == '/') {
numerators.add(positive num);
num = 0;
positive = 1;
} else {
num = num 10 + (c - 48);
}
}
denominators.add(num);
int sum = 0;
for (int i = 0; i < numerators.size(); i++) {
sum += numerators.get(i) * 2520 / denominators.get(i + 1);
}
int k = GCD(sum, 2520);
return k < 0
? "-" + String.valueOf(sum / k) + "/" + String.valueOf(-2520 / k)
: String.valueOf(sum / k) + "/" + String.valueOf(2520 / k);
}
private int GCD(int a, int b) {
return b == 0 ? a : GCD(b, a % b);
}
}
搜了一下这个所谓的2520:
At first sight, this number will be considered a normal number. But the strange thing is 2520 is able to be divided at even or odd number. Like 1=2520, 2=1260 , 3=840, 4=630, 5=504, 6=420, 7=360, 8=315, 9=280, and by 10=252, which is hard to find integers with the same characteristics.
Also, you can get this number by (7 * 30 * 12 = 2520) which I think is 7 days in the week, 30 days in a month and 12 months in a year! Nothing special, but it is a weird thing, right.
所以意思就是一个避免通分的操作, 直接转化成未一个整数(无论分母是多少, 上面乘一个2520之后, 都可以整除下来); 最后直接计算就行了;
另外他这里这个parse的操作其实是有点hackish的, 不过还是值得稍微看一下(配合一个简单的例子, 比如"1/2-1/2"). 他第一步首先是补齐开头的符号位; 然后后面的split的算法其实非常类似一个历史信息流的思路; 当然这个思路本身在这个问题上其实并没有太大的优势, 反而因为过于拘泥于这个思路模式, 在split问题上这个方法反而做的不是特别的高效; 这题的split最好的思路我认为还是我的做法, 就是针对"/"的位置, 直接前后探路就行了;
另外他这里这个recursion GCD的写法稍微简化了一点;
---
其他discussion好像没有什么特别好的解法了;
---
### Problem Description
Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.
Example 1:
Input:"-1/2+1/2"
Output: "0/1"
Example 2:
Input:"-1/2+1/2+1/3"
Output: "1/3"
Example 3:
Input:"1/3-1/2"
Output: "-1/6"
Example 4:
Input:"5/3+1/3"
Output: "2/1"
```
Note:
- The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
- Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
- The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
- The number of given fractions will be in the range [1,10].
- The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.
Difficulty:Medium
Total Accepted:4.2K
Total Submissions:9K
Contributor: fallcreek
Companies
ixl
Related Topics
math
Similar Questions
Solve the Equation