Leetcode 447. Number of Boomerangs JAVA語言

1

2

3

4

<code>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 iand j equals the distance between i and k (the order of the tuple matters).</code>

<code>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).</code>

<code>Example:</code>

<code>Input:[[0,0],[1,0],[2,0]]Output:2Explanation:The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]</code>

題意：給出n個點的坐标，找到ijk三個點，使得i到j和k的距離相等。

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

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>public</code> <code>int</code> <code>numberOfBoomerangs(</code><code>int</code><code>[][] points) {</code>

<code>        </code><code>////還有負數。。。。。hehe....坐标軸。。。。并不是隻有x軸</code>

<code>        </code><code>// int length=points.length;</code>

<code>        </code><code>// int m;</code>

<code>        </code><code>// int count=0;</code>

<code>        </code><code>// for(int i=0;i&lt;length;i++){</code>

<code>        </code><code>//     m=1;</code>

<code>        </code><code>//     while(i+m&lt;=length-1 &amp;&amp; i-m&gt;=0){</code>

<code>        </code><code>//         if(points[i][0]-points[i-m][0]==points[i+m][0]-points[i][0]){</code>

<code>        </code><code>//             count=count+2;</code>

<code>        </code><code>//         }</code>

<code>        </code><code>//         m++;</code>

<code>        </code><code>//     }</code>

<code>        </code><code>// }</code>

<code>        </code><code>// // System.out.println(length);</code>

<code>        </code><code>// return count;</code>

<code>        </code><code>//http://blog.csdn.net/MebiuW/article/details/53096120</code>

<code>        </code><code>//  int length=points.length;</code>

<code>        </code><code>//  int count=0;</code>

<code>        </code><code>//  for(int i=0;i&lt;length;i++){</code>

<code>        </code><code>//      HashMap&lt;Integer,Integer&gt; map=new HashMap&lt;Integer,Integer&gt;();</code>

<code>        </code><code>//      for(int j=0;j&lt;length;j++){</code>

<code>        </code><code>//          int dist=(points[i][0]-points[j][0])*(points[i][0]-points[j][0])+(points[i][1]-points[j][1])*(points[i][1]-points[j][1]);</code>

<code>        </code><code>//          if(!map.containsKey(dist)){</code>

<code>        </code><code>//              map.put(dist,0);</code>

<code>        </code><code>//          }</code>

<code>        </code><code>//          count+=map.get(dist)*2;</code>

<code>        </code><code>//          map.put(dist,map.get(dist)+1);</code>

<code>        </code><code>//      }</code>

<code>        </code><code>//  }</code>

<code>        </code><code>//  return count;</code>

<code>        </code><code>//也是周遊，求與其距離相同的點的個數，最後就是個數（個數-1）</code>

<code>        </code><code>///感覺還是這個好了解一些~</code>

<code>        </code><code>int</code> <code>length=points.length;</code>

<code>        </code><code>int</code> <code>count=</code><code>0</code><code>;</code>

<code>        </code><code>int</code> <code>dist=</code><code>0</code><code>;</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;length;i++){</code>

<code>            </code><code>HashMap&lt;Integer,Integer&gt; map=</code><code>new</code> <code>HashMap&lt;Integer,Integer&gt;();</code>

<code>            </code><code>for</code><code>(</code><code>int</code> <code>j=</code><code>0</code><code>;j&lt;length;j++){</code>

<code>                </code><code>if</code><code>(i==j){</code>

<code>                    </code><code>continue</code><code>;</code>

<code>                </code><code>}</code><code>else</code><code>{</code>

<code>                    </code><code>dist=(points[i][</code><code>0</code><code>]-points[j][</code><code>0</code><code>])*(points[i][</code><code>0</code><code>]-points[j][</code><code>0</code><code>])+(points[i][</code><code>1</code><code>]-points[j][</code><code>1</code><code>])*(points[i][</code><code>1</code><code>]-points[j][</code><code>1</code><code>]);</code>

<code>                    </code><code>if</code><code>(!map.containsKey(dist)){</code>

<code>                        </code><code>map.put(dist,</code><code>1</code><code>);</code>

<code>                    </code><code>}</code><code>else</code><code>{</code>

<code>                        </code><code>map.put(dist,map.get(dist)+</code><code>1</code><code>);    </code>

<code>                    </code><code>}</code>

<code>                </code><code>}</code>

<code>                </code> 

<code>            </code><code>}</code>

<code>        </code><code>Iterator it = map.keySet().iterator();  </code>

<code>        </code><code>while</code><code>(it.hasNext()) {  </code>

<code>            </code><code>int</code> <code>key = (</code><code>int</code><code>)it.next();  </code>

<code>            </code><code>count+=map.get(key)*(map.get(key)-</code><code>1</code><code>);</code>

<code>            </code><code>// System.out.println("value:" + hashMap.get(key));  </code>

<code>            </code><code>} </code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>count;</code>

<code>    </code><code>}</code>

<code>}</code>

PS：第一次以為隻有x軸正半軸，然後才發現其實是x,y軸4個空間。

最後的思想是周遊所有點，找到所有點距其距離相等的點的個數n，那麼就有n(n-1)個，不斷累加即可。

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1891285