ライン合計の最大ポイントのLeetCode



Leetcode Max Points Line Total



1.問題の説明

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

2.翻訳



For the N points in a plane, find the largest number of points in the same line

3.アイデアの分析

私たちが知っている中学校では、2つの点が直線を形成する可能性があることを知っています。線上の点までは同じ勾配である必要があります。ほとんどのポイントを把握するのはより簡単なので、これらのポイントをトラバースするようになっている限り、ポイントの数と同じ勾配を記録し、必要な最大勾配に対応する値の最大数は、また、勾配を格納するために使用されるキーであるHashMapが必要なので、値はレコード数を指します。そのため、最大値の最終値を考え出す必要があります。ハッシュを使用する基礎となるHashMapが達成するため、効率を探す過程で比率はまだ比較的高いです。



4.実装コード

Solution.java()(実装プロセスは他の人の実現を利用しますが、自分自身を解決するという考え)

package maxPoints import java.util.HashMap public class Solution { public int maxPoints(Point[] points) { if (points.length <= 2) {// if the number of points is less than or equal to 2, then the straight line is the length of an array of points return points.length } double k = 0.0 // slope int maxPointNum = 0 int tempMaxPointNum = 0 // number of identical coordinate points int samePointNum = 0 int parallelPointNum = 0 // parallel to the x-axis HashMap slopeMap = new HashMap() for(int i=0itempMaxPointNum) { tempMaxPointNum = number } } } } if(parallelPointNum > 1) { if(parallelPointNum>tempMaxPointNum) { tempMaxPointNum = parallelPointNum } } tempMaxPointNum + = samePointNum // add the starting point and the point having the same coordinates if(tempMaxPointNum>maxPointNum) { maxPointNum = tempMaxPointNum } } return maxPointNum } }

SoultionTest.java



package maxPoints import java.util.Random public class SolutionTest { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Point []pointArr = new Point[100] for(int index = 0index <100index++){ Point point = new Point(index,new Random(index).nextInt()) pointArr[index] = point System.out.println('Point('+point.x+','+point.y+')') } System.out.println(new Solution().maxPoints(pointArr)) } }

結果:

Point(0,-1155484576) Point(1,-1155869325) Point(2,-1154715079) Point(3,-1155099828) Point(4,-1157023572) Point(5,-1157408321) Point(6,-1156254074) Point(7,-1156638823) Point(8,-1158562568) Point(9,-1158947317) Point(10,-1157793070) Point(11,-1158177819) Point(12,-1160101563) Point(13,-1160486312) Point(14,-1159332065) Point(15,-1159716814) Point(16,-1149328594) Point(17,-1149713343) Point(18,-1148559096) Point(19,-1148943845) Point(20,-1150867590) Point(21,-1151252339) Point(22,-1150098092) Point(23,-1150482841) Point(24,-1152406585) Point(25,-1152791334) Point(26,-1151637087) Point(27,-1152021836) Point(28,-1153945581) Point(29,-1154330330) Point(30,-1153176083) Point(31,-1153560832) Point(32,-1167796541) Point(33,-1168181290) Point(34,-1167027043) Point(35,-1167411792) Point(36,-1169335537) Point(37,-1169720286) Point(38,-1168566039) Point(39,-1168950788) Point(40,-1170874532) Point(41,-1171259281) Point(42,-1170105035) Point(43,-1170489784) Point(44,-1172413528) Point(45,-1172798277) Point(46,-1171644030) Point(47,-1172028779) Point(48,-1161640559) Point(49,-1162025308) Point(50,-1160871061) Point(51,-1161255810) Point(52,-1163179554) Point(53,-1163564303) Point(54,-1162410057) Point(55,-1162794806) Point(56,-1164718550) Point(57,-1165103299) Point(58,-1163949052) Point(59,-1164333801) Point(60,-1166257546) Point(61,-1166642295) Point(62,-1165488048) Point(63,-1165872797) Point(64,-1180108506) Point(65,-1180493255) Point(66,-1179339008) Point(67,-1179723757) Point(68,-1181647502) Point(69,-1182032251) Point(70,-1180878004) Point(71,-1181262753) Point(72,-1183186497) Point(73,-1183571246) Point(74,-1182416999) Point(75,-1182801748) Point(76,-1184725493) Point(77,-1185110242) Point(78,-1183955995) Point(79,-1184340744) Point(80,-1173952524) Point(81,-1174337273) Point(82,-1173183026) Point(83,-1173567775) Point(84,-1175491519) Point(85,-1175876268) Point(86,-1174722021) Point(87,-1175106770) Point(88,-1177030515) Point(89,-1177415264) Point(90,-1176261017) Point(91,-1176645766) Point(92,-1178569510) Point(93,-1178954259) Point(94,-1177800013) Point(95,-1178184762) Point(96,-1192420471) Point(97,-1192805220) Point(98,-1191650973) Point(99,-1192035722) 6

ポイント6を通るラインの結果出力からわかるように。

この問題の解決策は非常に暴力的ですが、勾配がゼロである、状況の勾配が存在しない、一致点の場合など、注意が必要な詳細がたくさんあります。