Number of Boomerangs || Linked List Cycle Series

发表于

Number of Boomerangs

Question

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

1
2
3
4
5
6
7
8
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Analysis

For every i, we capture the number of points equidistant from i. Now for this i, we have to calculate all possible permutations of (j,k) from these equidistant points.

Total number of permutations of size 2 from n different points is nP2 = n!/(n-2)! = n * (n-1).

Code

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
public class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res=0;
        Map<Integer,Integer> table=new HashMap<>();
        for(int i=0;i<points.length;i++){
            for(int j=0;j<points.length;j++){
                if(i==j)
                    continue;
                int d=caldis(points[i],points[j]);
                table.put(d,table.getOrDefault(d,0)+1);
            }
            for(int values:table.values()){
                res+=values*(values-1);   
            }
            table.clear();
        }
        return res;
    }
    
    private int caldis(int[] a, int[] b){
        int x=a[0]-b[0];
        int y=a[1]-b[1];
        return x*x+y*y;
    }
}

Linked List Cycle Series

Question

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Analysis

链表环解决方案

Code

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)
            return null;
        ListNode walker=head;
        ListNode runner=head;
        boolean hasCycle=false;
        while(runner.next!=null&&runner.next.next!=null){
            walker=walker.next;
            runner=runner.next.next;
            if(walker==runner){
                hasCycle=true;
                break;
            }
        }
        if(!hasCycle)
            return null;
        walker=head;
        while(walker!=runner){
            walker=walker.next;
            runner=runner.next;
        }
        return walker;
    }
}