新鲜出炉巨硬哦阿

ptopenny 发表于 2020-6-12 15:28
那是未改的时候，我把currentsum=0从 if 移出来。每一次只要遇到负数就要reset currentsum成零，而不是当 ...

谢谢。请问下新题有什么思路可以分享下吗？

麻倉枼 发表于 2020-6-13 04:30
谢谢。请问下新题有什么思路可以分享下吗？

直接暴力搜索，枚举全部可能的分数对。写个函数检查一对分数和是否等于一。直接用了long来避免溢出。O(n^2)
但网上有人建议可以用gcd。不知道还能不能再优化。

ptopenny 发表于 2020-6-12 15:36
直接暴力搜索，枚举全部可能的分数对。写个函数检查一对分数和是否等于一。直接用了long来避免溢出。O(n^ ...

好的谢谢。不过range 100000的话暴力应该会TLE吧？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我求分数和等于1的写法。把两个数的分母变成一样，保证分子的和和分母相等就可以了。然后用long保持不overflow。

1. public class FractionsSumToOne {
   
2.     private int solution(int[] X, int[] Y) {
   
3.         long count = 0;
   
4.         for (int i = 0; i < X.length - 1; i++) {
   
5.             for (int j = i + 1; j < X.length; j++) {
   
6.                 long divident = X[i] * Y[j] + X[j] * Y[i];
   
7.                 long divisor = Y[i] * Y[j];
   
8.                 if (divident == divisor) {
   
9.                     count++;
   
10.                 }
    
11.             }
    
12.         }
    
13. 
    
14.         return (int) (count % 1000000007);
    
15.     }
    
16. 
    
17.     public static void main(String[] args) {
    
18.         FractionsSumToOne solution = new FractionsSumToOne();
    
19.         System.out.println(solution.solution(new int[]{1, 1 , 1}, new int[]{2, 2, 2}));
    
20.         System.out.println(solution.solution(new int[]{1, 2 , 3, 1, 2, 12, 8, 4}, new int[]{5, 10, 15, 2, 4, 15, 10, 5}));
    
21.         System.out.println(solution.solution(new int[]{500000000, 500000000}, new int[]{1000000000, 1000000000}));
    
22.     }
    
23. }

复制代码

oumizx 发表于 2020-6-13 17:13
我求分数和等于1的写法。把两个数的分母变成一样，保证分子的和和分母相等就可以了。然后用long保持不overf ...

这题数组长度N ＝ 10^5, 暴力法不行，时间复杂度会变成10^10。

拿上面的java代码改了个O(n)解法：

1. public class TestMS {
   
2.     private final static int MOD = 1_000_000_007;
   
3.     public TestMS() {
   
4.     }
   
5.    
   
6.     private int GCD(int a, int b) {
   
7.       if (a == 0 || b == 0) return a + b;
   
8.       return GCD(b, a%b);
   
9.     }
   
10.      
    
11.     private int solution(int[] X, int[] Y) {
    
12.         Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    
13.         for (int i = 0; i < X.length; i++) {
    
14.           int gcd = GCD(X[i], Y[i]);
    
15.           Map<Integer, Integer> subMap = map.getOrDefault(Y[i] / gcd, new HashMap<Integer, Integer>());
    
16.           subMap.put(X[i] / gcd, subMap.getOrDefault(X[i] / gcd, 0) + 1);
    
17.           map.putIfAbsent(Y[i] / gcd, subMap);
    
18.         }
    
19.         
    
20.         long count = 0L;
    
21.         for (Map.Entry<Integer, Map<Integer, Integer>> entry: map.entrySet()) {
    
22.           int denominator = entry.getKey();
    
23.           Map<Integer, Integer> subMap = entry.getValue();
    
24.           for (int numerator: subMap.keySet()) {
    
25.             int target = denominator - numerator;
    
26.             if (!subMap.containsKey(target)) continue;
    
27.             int c1 = subMap.get(numerator);
    
28.             int c2 = subMap.get(target);
    
29.             count += (target == numerator) ? (long)c1 * (c2 - 1) : (long)c1 * c2;
    
30.           }
    
31.         }
    
32.         return (int)((count / 2) % MOD);
    
33.     }
    
34.    
    
35.     private int bruteForce(int[] X, int[] Y) {
    
36.         long count = 0;
    
37.         for (int i = 0; i < X.length - 1; i++) {
    
38.             for (int j = i + 1; j < X.length; j++) {
    
39.                 long divident = (long)X[i] * Y[j] + (long)X[j] * Y[i];
    
40.                 long divisor = (long)Y[i] * Y[j];
    
41.                 if (divident == divisor) {
    
42.                     count++;
    
43.                 }
    
44.             }
    
45.         }
    
46.         return (int) (count % MOD);
    
47.     }
    
48. 
    
49.     public static void main(String args[]) {
    
50.       TestMS test = new TestMS();
    
51.       System.out.println(test.solution(new int[]{1, 1 , 1}, new int[]{2, 2, 2}));
    
52.       System.out.println(test.bruteForce(new int[]{1, 1 , 1}, new int[]{2, 2, 2}));
    
53.       System.out.println(test.solution(new int[]{1, 2 , 3, 1, 2, 12, 8, 4}, new int[]{5, 10, 15, 2, 4, 15, 10, 5}));
    
54.       System.out.println(test.bruteForce(new int[]{1, 2 , 3, 1, 2, 12, 8, 4}, new int[]{5, 10, 15, 2, 4, 15, 10, 5}));
    
55.       System.out.println(test.solution(new int[]{500000000, 500000000}, new int[]{1000000000, 1000000000}));
    
56.       System.out.println(test.bruteForce(new int[]{500000000, 500000000}, new int[]{1000000000, 1000000000}));
    
57.       
    
58.       int maxLength = 100000;
    
59.       int[] x = new int[maxLength];
    
60.       int[] y = new int[maxLength];
    
61.       int nx = 1, ny = 2;
    
62.       for (int i = 0; i < maxLength; i++) {
    
63.         x[i] = nx; nx++;
    
64.         y[i] = ny; ny += 2;
    
65.       }
    
66.       long startTime = System.currentTimeMillis();
    
67.       System.out.println(test.solution(x, y) + ", time:" + (System.currentTimeMillis() - startTime));
    
68.       startTime = System.currentTimeMillis();
    
69.       System.out.println(test.bruteForce(x, y) + ", time:" + (System.currentTimeMillis() - startTime));
    
70.     }
    
71. }

复制代码

楼主今天遇到了一模一样的题目啊，最后一题分数题没写完。。。

楼主我也要参加这个event， 交流下？