笔试题——有理数不可约和【0001】

大家好，我是指北君，技术面试搞定了，你们代码能力过关了吗？是不是被大厂的笔试给挡在了门外，不要灰心指北君将陆续为大家带来超强的习题练习。

题目

计算有理数的不可约结果

输入

输入一组分数，通过二维整数数组表示：[ [n_1, d_1]，[n_2, d_2], …, [n_n, d_n] ], 表示n_1/d_1, n_2/d_2, … 分子分母都为正整数，计算分数之和，并且结果必须是不可约。

输出

1. “[N, D]”
2. 如果结果可以被整除，则返回整数：”N”
3. 如果输入为空，或者不合法，返回null

输出样例

[ [1, 2], [1, 3], [1, 4] ] –> [13, 12]

代码模板

1 2 3 4 5

public class SumFractions { public static String sumFracts(int[][] input) { //todo 实现代码 } }

测试用例样例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

import static org.junit.Assert.*; import java.util.Arrays; import org.junit.Test; public class SumFractionsTest { private static void testing(String actual, String expected) { assertEquals(expected, actual); } @Test public void test1() { System.out.println("Fixed Tests sumFracts"); int[][] a = new int[][] { {1,2}, {2,9}, {3,18}, {4,24}, {6,48} }; String r = "[85, 72]"; testing(SumFractions.sumFracts(a), r); a = new int[][] { {1, 2}, {1, 3}, {1, 4} }; r = "[13, 12]"; testing(SumFractions.sumFracts(a), r); a = new int[][] { {1, 3}, {5, 3} }; r = "2"; testing(SumFractions.sumFracts(a), r); a = new int[][] {}; r = null; } }

题目分析

1.分数之和，需要计算两个分数的分母的最小公倍数，分母相同后，分子进行相加。 2.求最小公倍数，需要求两个数的最大公约数，然后两个数的乘积除以最大公约数。 3.求最大公约数的方法很多，最容易理解的就是分解质因数，然后将相同的质因数相乘

代码验证（在线）

预留

代码示例

初级实现

实现逻辑基本按照前面的题目分析，最大公约数方式有：【质因数分解法】【短除法】【*辗转相除法】【更相减损法】，这里选用的短除法

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

import java.util.Arrays; public class SumFractions { public static String sumFracts(int[][] input) { String result = null; if (input.length == 0) { return result; } for (int[] e : input) { if (e.length != 2 || e[1] == 0) { return result; } } // 计算分母最小公倍数 int minCommMultiple = input[0][1]; for (int i = 1; i < input.length; i++) { minCommMultiple = minCommMultiple(minCommMultiple, input[i][1]); } // 计算分子之和 int num = 0; for (int i = 0; i < input.length; i++) { int elemnet = minCommMultiple / input[i][1]; num += input[i][0] * elemnet; } // 如果能够整除，需要整除 if (num % minCommMultiple == 0) { result = num / minCommMultiple + ""; return result; } // 坑 int maxCommDivisor = maxCommDivisor(num, minCommMultiple); if (maxCommDivisor > 1) { num /= maxCommDivisor; minCommMultiple /= maxCommDivisor; } result = "[" + num + ", " + minCommMultiple + "]"; return result; } /** * 计算两个数的最小公倍数 * * @param a * @param b * @return */ public static int minCommMultiple(int a, int b) { int c = a * b; int maxCommDivisor = maxCommDivisor(a, b); // 数学之美：最小公倍数 * 最大公约数 = 两个数的乘积 c = c / maxCommDivisor; // System.out.println("最小公倍数：" + a + "," + b + "=>" + c); return c; } /** * 计算两个数的最大公约数 * * @param a * @param b * @return */ public static int maxCommDivisor(int a, int b) { int mid1, mid2, mid3; mid1 = a; mid2 = b; mid3 = 0; // 数学之美：最大公约数 =》 【质因数分解法】【短除法】【*辗转相除法】【更相减损法】 while (true) { mid3 = mid1 % mid2; if (mid3 == 0) break; else { mid1 = mid2; mid2 = mid3; } } // System.out.println("最大公约数：" + a + "," + b + "=>" + mid2); return mid2; } }

中级实现

中级版本实现，优化代码，引入Stream流处理

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

import java.util.stream.Stream; public class SumFractions2 { public static String sumFracts(int[][] input) { String result = null; if (input.length == 0) return result; for (int[] e : input) { if (e.length != 2 || e[1] == 0) return result; } // 计算分母最小公倍数 int minCommMultiple = Stream.of(input).mapToInt(a->a[1]).reduce(1, (a, b)->a*b/maxCommDivisor(a, b)); int num = Stream.of(input).mapToInt(a->a[0]*(minCommMultiple/a[1])).sum(); // 如果能够整除，需要整除 if (num % minCommMultiple == 0) { result = num / minCommMultiple + ""; return result; } int maxCommDivisor = maxCommDivisor(num, minCommMultiple); num /= maxCommDivisor; int den = minCommMultiple / maxCommDivisor; result = "[" + num + ", " + den + "]"; return result; } public static int maxCommDivisor(int a, int b) { int mid1, mid2, mid3; mid1 = a; mid2 = b; mid3 = 0; while (true) { mid3 = mid1 % mid2; if (mid3 == 0) break; else { mid1 = mid2; mid2 = mid3; } } return mid2; } }

高阶实现

中级版的实现是不是已经很精简了呢？还不够，我们来看看高级版实现，

1. 引入BigInteger.gcd方法计算最大公约数，
2. 过程中不再转换（好处是逻辑的简单，坏处是有可能乘积越界）。

最后看到代码是不是很震撼！

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

import java.math.BigInteger; import java.util.Arrays; public class SumFractions3 { public static String sumFracts(int[][] l) { if (l.length == 0) return null; final int D = Arrays.stream(l).mapToInt(ar -> ar[1]).reduce(1, (a, b) -> a * b); final int N = Arrays.stream(l).mapToInt(ar -> ar[0] * D / ar[1]).sum(); int gcd = BigInteger.valueOf(D).gcd(BigInteger.valueOf(N)).intValue(); return (D == gcd) ? String.valueOf(N / D) : String.format("[%d, %d]", N / gcd, D / gcd); } }

完整验证用例

因为在线练习没有开通，所有这里临时将完整验证用例附上，小伙伴可以用这些用例来验证自己的实现。

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

SumFractions input：[ [1, 2], [2, 9], [3, 18], [4, 24], [6, 48], ] --> [85, 72] SumFractions input：[ [1, 2], [1, 3], [1, 4], ] --> [13, 12] SumFractions input：[ [1, 3], [5, 3], ] => 2 SumFractions input：[ [12, 3], [15, 3], ] => 9 SumFractions input：[ [2, 7], [1, 3], [1, 12], ] --> [59, 84] SumFractions input：[ [69, 130], [87, 1310], [3, 4], ] --> [9177, 6812] SumFractions input：[ [77, 130], [84, 131], [60, 80], ] --> [67559, 34060] SumFractions input：[ [6, 13], [187, 1310], [31, 41], ] --> [949861, 698230] SumFractions input：[ [8, 15], [7, 111], [4, 25], ] --> [2099, 2775] SumFractions input：[ ] => null SumFractions input：[ [1, 8], [1, 9], ] --> [17, 72] SumFractions input：[ [2, 8], [1, 9], ] --> [13, 36] ------------ SumFractions input：[ [91, 92], [91, 93], ] --> [16835, 8556] SumFractions input：[ [195, 196], [195, 197], ] --> [76635, 38612] SumFractions input：[ [125, 126], [125, 127], ] --> [31625, 16002] SumFractions input：[ [127, 128], [127, 129], ] --> [32639, 16512] SumFractions input：[ [167, 168], [167, 169], ] --> [56279, 28392] SumFractions input：[ [102, 103], [102, 104], ] --> [10557, 5356] SumFractions input：[ [49, 50], [49, 51], ] --> [4949, 2550] SumFractions input：[ [179, 180], [179, 181], ] --> [64619, 32580] SumFractions input：[ [98, 99], [98, 100], ] --> [9751, 4950] SumFractions input：[ [16, 17], [16, 18], ] --> [280, 153] SumFractions input：[ [74, 75], [74, 76], ] --> [5587, 2850] SumFractions input：[ [192, 193], [192, 194], ] --> [37152, 18721] SumFractions input：[ [181, 182], [181, 183], ] --> [66065, 33306] SumFractions input：[ [91, 92], [91, 93], ] --> [16835, 8556] SumFractions input：[ [17, 18], [17, 19], ] --> [629, 342] SumFractions input：[ [180, 181], [180, 182], ] --> [32670, 16471] SumFractions input：[ [175, 176], [175, 177], ] --> [61775, 31152] SumFractions input：[ [183, 184], [183, 185], ] --> [67527, 34040] SumFractions input：[ [81, 82], [81, 83], ] --> [13365, 6806] SumFractions input：[ [87, 88], [87, 89], ] --> [15399, 7832] SumFractions input：[ [26, 27], [26, 28], ] --> [715, 378] SumFractions input：[ [118, 119], [118, 120], ] --> [14101, 7140] SumFractions input：[ [80, 81], [80, 82], ] --> [6520, 3321] SumFractions input：[ [133, 134], [133, 135], ] --> [35777, 18090] SumFractions input：[ [116, 117], [116, 118], ] --> [13630, 6903] SumFractions input：[ [113, 114], [113, 115], ] --> [25877, 13110] SumFractions input：[ [148, 149], [148, 150], ] --> [22126, 11175] SumFractions input：[ [47, 48], [47, 49], ] --> [4559, 2352] SumFractions input：[ [42, 43], [42, 44], ] --> [1827, 946] SumFractions input：[ [11, 12], [11, 13], ] --> [275, 156] SumFractions input：[ [29, 30], [29, 31], ] --> [1769, 930] SumFractions input：[ [34, 35], [34, 36], ] --> [1207, 630] SumFractions input：[ [125, 126], [125, 127], ] --> [31625, 16002] SumFractions input：[ [44, 45], [44, 46], ] --> [2002, 1035] SumFractions input：[ [37, 38], [37, 39], ] --> [2849, 1482] SumFractions input：[ [8, 9], [8, 10], ] --> [76, 45] SumFractions input：[ [119, 120], [119, 121], ] --> [28679, 14520] SumFractions input：[ [183, 184], [183, 185], ] --> [67527, 34040] SumFractions input：[ [153, 154], [153, 155], ] --> [47277, 23870] SumFractions input：[ [41, 42], [41, 43], ] --> [3485, 1806] SumFractions input：[ [68, 69], [68, 70], ] --> [4726, 2415] SumFractions input：[ [151, 152], [151, 153], ] --> [46055, 23256] SumFractions input：[ [88, 89], [88, 90], ] --> [7876, 4005] SumFractions input：[ [199, 200], [199, 201], ] --> [79799, 40200] SumFractions input：[ [83, 84], [83, 85], ] --> [14027, 7140] SumFractions input：[ [166, 167], [166, 168], ] --> [27805, 14028] SumFractions input：[ [181, 182], [181, 183], ] --> [66065, 33306] SumFractions input：[ [59, 60], [59, 61], ] --> [7139, 3660] SumFractions input：[ [116, 117], [116, 118], ] --> [13630, 6903] SumFractions input：[ [46, 47], [46, 48], ] --> [2185, 1128] SumFractions input：[ [137, 138], [137, 139], ] --> [37949, 19182] SumFractions input：[ [127, 128], [127, 129], ] --> [32639, 16512] SumFractions input：[ [68, 69], [68, 70], ] --> [4726, 2415] SumFractions input：[ [20, 21], [20, 22], ] --> [430, 231] SumFractions input：[ [93, 94], [93, 95], ] --> [17577, 8930] SumFractions input：[ [34, 35], [34, 36], ] --> [1207, 630] SumFractions input：[ [55, 56], [55, 57], ] --> [6215, 3192] SumFractions input：[ [31, 32], [31, 33], ] --> [2015, 1056] SumFractions input：[ [11, 12], [11, 13], ] --> [275, 156] SumFractions input：[ [199, 200], [199, 201], ] --> [79799, 40200] SumFractions input：[ [149, 150], [149, 151], ] --> [44849, 22650] SumFractions input：[ [184, 185], [184, 186], ] --> [34132, 17205] SumFractions input：[ [136, 137], [136, 138], ] --> [18700, 9453] SumFractions input：[ [37, 38], [37, 39], ] --> [2849, 1482] SumFractions input：[ [191, 192], [191, 193], ] --> [73535, 37056] SumFractions input：[ [106, 107], [106, 108], ] --> [11395, 5778] SumFractions input：[ [147, 148], [147, 149], ] --> [43659, 22052] SumFractions input：[ [110, 111], [110, 112], ] --> [12265, 6216] SumFractions input：[ [8, 9], [8, 10], ] --> [76, 45] SumFractions input：[ [4, 5], [4, 6], ] --> [22, 15] SumFractions input：[ [193, 194], [193, 195], ] --> [75077, 37830] SumFractions input：[ [105, 106], [105, 107], ] --> [22365, 11342] SumFractions input：[ [26, 27], [26, 28], ] --> [715, 378] SumFractions input：[ [193, 194], [193, 195], ] --> [75077, 37830] SumFractions input：[ [119, 120], [119, 121], ] --> [28679, 14520] SumFractions input：[ [179, 180], [179, 181], ] --> [64619, 32580] SumFractions input：[ [30, 31], [30, 32], ] --> [945, 496] SumFractions input：[ [30, 31], [30, 32], ] --> [945, 496] SumFractions input：[ [128, 129], [128, 130], ] --> [16576, 8385] SumFractions input：[ [9, 10], [9, 11], ] --> [189, 110] SumFractions input：[ [126, 127], [126, 128], ] --> [16065, 8128] SumFractions input：[ [80, 81], [80, 82], ] --> [6520, 3321] SumFractions input：[ [112, 113], [112, 114], ] --> [12712, 6441] SumFractions input：[ [22, 23], [22, 24], ] --> [517, 276] SumFractions input：[ [65, 66], [65, 67], ] --> [8645, 4422] SumFractions input：[ [198, 199], [198, 200], ] --> [39501, 19900] SumFractions input：[ [163, 164], [163, 165], ] --> [53627, 27060] SumFractions input：[ [21, 22], [21, 23], ] --> [945, 506] SumFractions input：[ [67, 68], [67, 69], ] --> [9179, 4692] SumFractions input：[ [46, 47], [46, 48], ] --> [2185, 1128] SumFractions input：[ [35, 36], [35, 37], ] --> [2555, 1332] SumFractions input：[ [70, 71], [70, 72], ] --> [5005, 2556] SumFractions input：[ [178, 179], [178, 180], ] --> [31951, 16110] SumFractions input：[ [96, 97], [96, 98], ] --> [9360, 4753] SumFractions input：[ [3, 4], [3, 5], ] --> [27, 20] SumFractions input：[ [145, 146], [145, 147], ] --> [42485, 21462] SumFractions input：[ [170, 171], [170, 172], ] --> [29155, 14706] SumFractions input：[ [165, 166], [165, 167], ] --> [54945, 27722] SumFractions input：[ [2, 3], [2, 4], ] --> [7, 6] SumFractions input：[ [16, 17], [16, 18], ] --> [280, 153]

总结

如果对指北君的习题练习感兴趣，也希望在面临大厂笔试时更有信心，可以在公众号中回复：笔试 或者 笔试-编号

我是指北君，操千曲而后晓声，观千剑而后识器。感谢各位人才的：点赞、收藏和评论，我们下期更精彩！