新鲜出炉巨硬哦阿

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吧？

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

我的理解是：
1.遍历一遍数组，用GCD把能约分的都约掉。由于约分之后，对于分母不一样的两个数一定不可能相加得1，只用考虑分母相同的数就行了。2.把约分之后的数字放入Map。Map<Intger (分母), Map<Integer (分子), Integer (个数)>>， 遍历Map得解。
时间复杂度O(n),空间复杂度O(n)

djmiss 发表于 2020-6-12 16:28
我的理解是：
1.遍历一遍数组，用GCD把能约分的都约掉。由于约分之后，对于分母不一样的两个数一定不可 ...

不知道有没有遗漏，不过花了我几个小时去解，太虐了        

/*
                NOTE:
                - N is an integer within the range [0, 100,000] inclusive
                - Each element of arrays X, Y is an integer within the range
                  [1, 1,000,000,000]
        */
        class Solution
        {
        public:
                int getNumberOfPairs(vector<int>& numerators,
                                                         vector<int>& denominators)
                {
                        if (numerators.empty() ||
                                denominators.empty())
                        {
                                return 0;
                        }

                        if (numerators.size() != denominators.size())
                        {
                                return 0;
                        }

                        /*
                                Key = denominator
                                Value = a map of pair<numerator, frequency>
                        */
                        unordered_map<int, unordered_map<int,int>> frequency_map;
                        const int SIZE = numerators.size();

                        /*
                                Create the frequency map,
                                each pair of numerator and denominator has been simplified.
                        */
                        for (int i = 0; i < SIZE; ++i)
                        {
                                int denominator = denominators;
                                int numerator = numerators[i];

                                update_denominator_numerator(denominator, numerator);
                                ++frequency_map[denominator][numerator];
                        }

                        int numWays = 0;[/i][i]
                        // Denominator
                        // pair<denominator, numerator map>
                        for (pair<int, unordered_map<int,int>> denominator_entry : frequency_map)
                        {
                                int denominator = denominator_entry.first;
                                
                                // Numerator
                                // pair<numerator, frequency>                 
                                unordered_map<int, int>::iterator iter = frequency_map[denominator].begin();

                                while (!frequency_map[denominator].empty() &&
                                           iter != frequency_map[denominator].end())
                                {
                                        // (denominator - numerator)
                                        int cur_numerator = iter->first;
                                        int diff_numerator = (denominator - cur_numerator);

                                        /*
                                                NOTE:
                                                If the diff is found in the numerator map,
                                                that means we can find the pair that sum up to 1.
                                        */
                                        if (frequency_map[denominator].count(diff_numerator))
                                        {
                                                int cur_frequency = iter->second;
                                                
                                                /*
                                                        Special Case:
                                                        1/2 + 1/2 = 1.
                                                */
                                                if (cur_numerator == diff_numerator)
                                                {
                                                        int final_frequency = 0;

                                                        int count = (cur_frequency -1);

                                                        while (count > 0)
                                                        {
                                                                final_frequency += count;
                                                                --count;
                                                        }
                                                        // Update result.
                                                        numWays += final_frequency;

                                                        frequency_map[denominator].erase(cur_numerator);
                                                        continue;
                                                }

                                                int diff_frequency = frequency_map[denominator][diff_numerator];

                                                // Update both frequencies.
                                                int final_frequency = (cur_frequency * diff_frequency);
                                                frequency_map[denominator].erase(cur_numerator);
                                                frequency_map[denominator].erase(diff_numerator);

                                                // Update result.
                                                numWays += final_frequency;
                                        }
                                        else
                                        {
                                                ++iter;
                                        }
                                }
                        }
                        return numWays;
                }

        private:
                void update_denominator_numerator(int& denominator, int& numerator)
                {
                        int gcd = get_greatest_common_divisor(denominator, numerator);

                        denominator /= gcd;
                        numerator   /= gcd;
                }

                /*
                        Reference:
                        - https://www.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/
                */
                int get_greatest_common_divisor(int denominator, int numerator)
                {
                        if (denominator == 0)
                        {
                                return numerator;
                        }
                        if (numerator == 0)
                        {
                                return denominator;
                        }

                        // Base Case
                        if (denominator == numerator)
                        {
                                return denominator;
                        }

                        if (denominator > numerator)
                        {
                                return get_greatest_common_divisor((denominator - numerator), numerator);
                        }
                        return get_greatest_common_divisor(denominator, (numerator - denominator));
                }
        };[/i]

我求分数和等于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， 交流下？