FriendsOfAppropriateAges [source code]

public class FriendsOfAppropriateAges {
static
/****************************************************************************/
class Solution {
    public int numFriendRequests(int[] ages) {
        int res = 0;
        int[] counts = new int[121];
        for (int age : ages)
            counts[age]++;
        for (int a_age = 1; a_age <= 120; a_age++) {
            for (int b_age = a_age; b_age >= 1; b_age--) {
                if (b_age <= 0.5 * a_age + 7)
                    continue;
                if (b_age > 100 && a_age < 100)
                    continue;
                res += counts[a_age] * counts[b_age];
                if (a_age == b_age)
                    res -= counts[b_age];
            }
        }
        return res;
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        FriendsOfAppropriateAges.Solution tester = new FriendsOfAppropriateAges.Solution();
        int[][] inputs = {
            {16,16}, {2},
            {16,17,18}, {2},
            {73,106,39,6,26,15,30,100,71,35,46,112,6,60,110}, {29},
            {98,60,24,89,84,51,61,96,108,87,68,29,14,11,13,50,13,104,57,8,57,111,92,87,9,59,65,116,56,39,55,11,21,105,57,36,48,93,20,94,35,68,64,41,37,11,50,47,8,9}, {439},
            {100,94,106,82,2,48,16,110,76,48,10,39,78,69,99,27,109,82,72,44,77,23,53,78,100,6,84,117,25,115,82,31,55,51,72,3,108,27,6,32,78,114,97,79,68,43,86,14,102,5}, {512},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            int[] ages = inputs[2 * i];
            int ans = inputs[2 * i + 1][0], output = tester.numFriendRequests (ages);
            System.out.printf ("%s\n%s\n%s\n", 
                Printer.array (ages), Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

一开始拿到这个题目以为他们出错了, 感觉2和3两个条件是等价的; 但是仔细想了一下之后, 发现不是这样的;

最后真的是被后面这几个全都是差个1或者2的例子给搞崩溃了, 没有做出来了;

也不准备研究我自己的算法了, 本来就很蠢首先, 是比较粗暴的做法, 真正面试的时候估计也是不达标; 这个算法保存在这里:

class Solution {  
    public int numFriendRequests(int[] ages) {  
        Arrays.sort (ages);  
        int N = ages.length;  
        int count = 0;  
        for (int a = N - 1; a >= 0; a--) {  
            for (int b = a - 1; b >= 0; b--) {  
                if (ages[b] == ages[a] && !(ages[b] <= 0.5 * ages[a] + 7 || (ages[b] > 100 && ages[a] < 100))) {  
                    count += a - b;  
                }  
                if (!(ages[b] <= 0.5 * ages[a] + 7 || (ages[b] > 100 && ages[a] < 100))) {  
                    count++;  
                }  
            }  
        }  
        return count;  
    }  
}

这个算法稍微有点技术含量的部分也就是第一个if这个处理的是加入有一个平台(a和b相等)的时候, 直接用以前做过的一个count end at this的思路来数一个排列组合的结果(这里实际上数的是length beginning at this (b)).

这个算法最后的问题就是出在多几个少几个, 这个bug没有什么好办法去检查了;

最后上面的算法是参考editorial做出来的一个解法, 相比于awice的解法, 一个优化就是利用条件2直接进行一个对称性的处理; 最后代码本身还是很简单的; 当a和b的age相等的时候, 这个减少overcount的操作还是无法避免的; 速度最后是16 (NA).

另外这个三角形处理, 并不需要我用sort, 因为一开始就用了一个bucket操作, 所以这个sort也就省下来了;

UNFINISHED

editorial

Approach #1: Counting [Accepted]

Intuition

Instead of processing all 20000 people, we can process pairs of (age, count) representing how many people are that age. Since there are only 120 possible ages, this is a much faster loop.

.... 这个题目最后的downvote不少, 可能就跟这个有关系吧. 这个优化是有点不讲道理的;
不过这个好像还真的是第一次用数据的reallife内涵来帮助简化问题的案例;

不过这里实际上最后也给了这个age的限制, 所以或许是一个提示? 但是真正在面试当中, 这个年龄范围的提示估计不会这么明显;

Algorithm

For each pair (ageA, countA), (ageB, countB), if the conditions are satisfied with respect to age, then countA * countB pairs of people made friend requests.

用上面的分析, 最后整个复杂度就被O(N) + O(120)给bound住了;

If ageA == ageB, then we overcounted: we should have countA * (countA - 1) pairs of people making friend requests instead, as you cannot friend request yourself.

还是向下看代码, awice的algorithm部分的解释就是这样, 实际上讲着讲着就变成在解释代码了;

class Solution {  
    public int numFriendRequests(int[] ages) {  
        int[] count = new int[121];  
        for (int age: ages) count[age]++;  

        int ans = 0;  
        for (int ageA = 0; ageA <= 120; ageA++) {  
            int countA = count[ageA];  
            for (int ageB = 0; ageB <= 120; ageB++) {  
                int countB = count[ageB];  
                if (ageA * 0.5 + 7 >= ageB) continue;  
                if (ageA < ageB) continue;  
                if (ageA < 100 && 100 < ageB) continue;  
                ans += countA * countB;  
                if (ageA == ageB) ans -= countA;  
            }  
        }  

        return ans;  
    }  
}

除了上面这个age bucket的技巧, 几乎就没有其他的技巧了; 我希望通过对题目的解读来完成一个greedy的优化, 他最后也是懒得做了, innerloop完全就是对三个条件的直接判断;

uwi: 3分钟:

class Solution {  
    public int numFriendRequests(int[] ages) {  
        int[] f = new int[121];  
        for(int v : ages){  
            f[v]++;  
        }  
        int ret = 0;  
        for(int i = 0;i <= 120;i++){  
            for(int j = 0;j <= 120;j++){  
                if(j*2 <= i+14 || j > i || j > 100 && i < 100){  
                }else{  
                    if(i == j){  
                        ret += f[i] * (f[i]-1);  
                    }else{  
                        ret += f[i]*f[j];  
                    }  
                }  
            }  
        }  
        return ret;  
    }  
}

Problem Description

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

• age[B] <= 0.5 * age[A] + 7
• age[B] > age[A]
• age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

Input: [16,16]  
Output: 2  
Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18]  
Output: 2  
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120]  
Output:   
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:

• 1 <= ages.length <= 20000.
• 1 <= ages[i] <= 120.

Difficulty:Medium
Total Accepted:632
Total Submissions:4.4K
Contributor:awice

Companies
facebook
Related Topics
array