大佬教程收集整理的这篇文章主要介绍了6.24_直线上最多的点数_给数组赋值,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
6.24_直线上最多的点数:
给你一个数组 points
,其中 points[i] = [xi, yi]
表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
输入:points = [[1,1],[2,2],[3,3]] 输出:3
输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出:4
提示:
1 <= points.length <= 300points[i].length == 2-104 <= xi, yi <= 104points 中的所有点 互不相同
链接:https://leetcode-cn wangt.cc /problems/max-points-on-a-line
1、c
#include <stdlib.h> // NULL, abs #include <math.h> // fmax #include ".libuthash-mastersrcuthash.h" /* UT_hash_handle */@H_450_62@ #include "stdio.h" struct@H_450_62@ HashTable { int@H_450_62@ key, val; UT_hash_handle hh; }; int gcd(int a, int@H_450_62@ b) { return b ? gcd(b, a %@H_450_62@ b) : a; } int maxPoints(int** points, int pointsSize, int*@H_450_62@ pointsColSizE) { int n =@H_450_62@ pointsSize; if (n <= 2@H_450_62@) { return@H_450_62@ n; } int ret = 0@H_450_62@; for (int i = 0; i < n; i++@H_450_62@) { if (ret >= n - i || ret > n / 2@H_450_62@) { break@H_450_62@; } struct HashTable* hashTable =@H_450_62@ NULL; for (int j = i + 1; j < n; j++@H_450_62@) { int x = points[i][0] - points[j][0@H_450_62@]; int y = points[i][1] - points[j][1@H_450_62@]; if (x == 0@H_450_62@) { y = 1@H_450_62@; } else if (y == 0@H_450_62@) { x = 1@H_450_62@; } else@H_450_62@ { if (y < 0@H_450_62@) { x = -@H_450_62@x; y = -@H_450_62@y; } int gcdXY =@H_450_62@ gcd(abs(X), abs(y)); x /= gcdXY, y /=@H_450_62@ gcdXY; } struct HashTable*@H_450_62@ tmp; int val = y + x * 20010@H_450_62@; HASH_FIND_INT(hashTable, &@H_450_62@val, tmp); if (tmp ==@H_450_62@ NULL) { tmp = @H_419_70@malloc(sizeof(struct@H_450_62@ HashTablE)); tmp->key =@H_450_62@ val; tmp->val = 1@H_450_62@; HASH_ADD_INT(hashTable, key, tmp); } else@H_450_62@ { tmp->val++@H_450_62@; } } int maxn = 0@H_450_62@; struct HashTable *iter, *@H_450_62@tmp; HASH_ITER(hh, hashTable, iter, tmp) { maxn = fmax(maxn, iter->val + 1@H_450_62@); HASH_DEL(hashTable, iter); free@H_450_62@(iter); } ret =@H_450_62@ fmax(ret, maxn); } return@H_450_62@ ret; } int@H_450_62@ main() { // int points[3][2] = {{1,1}, {2,2}, {3,3}}; int points[3][2] = {1,1, 2, 2, 3,3@H_450_62@}; // c语言这个大小怎么输入?? int pointsSize = sizeof(points) / sizeof(points[0@H_450_62@]); int pointsColSize = sizeof(points[0]) / sizeof(points[0][0@H_450_62@]); printf("%d", maxPoints((int **) points, pointsSize, (int *@H_450_62@) pointsColSizE)); }
2、java
import@H_450_62@ java.util.HashMap; import@H_450_62@ java.util.Map; class@H_450_62@ Solution { public int maxPoints(int@H_450_62@[][] points) { int n =@H_450_62@ points.length; if (n <= 2@H_450_62@) { return@H_450_62@ n; } int ret = 0@H_450_62@; for (int i = 0; i < n; i++@H_450_62@) { if (ret >= n - i || ret > n / 2@H_450_62@) { break@H_450_62@; } Map<Integer, Integer> map = new HashMap<Integer, Integer>@H_450_62@(); for (int j = i + 1; j < n; j++@H_450_62@) { int x = points[i][0] - points[j][0@H_450_62@]; int y = points[i][1] - points[j][1@H_450_62@]; if (x == 0@H_450_62@) { y = 1@H_450_62@; } else if (y == 0@H_450_62@) { x = 1@H_450_62@; } else@H_450_62@ { if (y < 0@H_450_62@) { x = -@H_450_62@x; y = -@H_450_62@y; } int gcdXY =@H_450_62@ gcd(Math.abs(X), Math.abs(y)); x /=@H_450_62@ gcdXY; y /=@H_450_62@ gcdXY; } int key = y + x * 20001@H_450_62@; map.put(key, map.getOrDefault(key, 0) + 1@H_450_62@); } int maxn = 0@H_450_62@; for (Map.Entry<Integer, Integer>@H_450_62@ entry: map.entrySet()) { int num =@H_450_62@ entry.getValue(); maxn = Math.max(maxn, num + 1@H_450_62@); } ret =@H_450_62@ Math.max(ret, maxn); } return@H_450_62@ ret; } public int gcd(int a, int@H_450_62@ b) { return b != 0 ? gcd(b, a %@H_450_62@ b) : a; } } public class@H_450_62@ Main { public static void@H_450_62@ main(String[] args) { int[][] points = {{1,1}, {2,2}, {3,3@H_450_62@}}; // Solution res = new Solution(); // System.out.println(res.maxPoints(points)); System.out.println(new@H_450_62@ Solution().maxPoints(points)); } }
3、c++
#include "iostream"@H_450_62@ #include "vector"@H_450_62@ #include "unordered_map"@H_450_62@ using namespace std; class@H_450_62@ Solution { public@H_450_62@: int gcd(int a, int@H_450_62@ b) { return b ? gcd(b, a %@H_450_62@ b) : a; } int maxPoints(vector<vector<int>>&@H_450_62@ points) { int n =@H_450_62@ points.size(); if (n <= 2@H_450_62@) { return@H_450_62@ n; } int ret = 0@H_450_62@; for (int i = 0; i < n; i++@H_450_62@) { if (ret >= n - i || ret > n / 2@H_450_62@) { break@H_450_62@; } unordered_map<int, int>@H_450_62@ mp; for (int j = i + 1; j < n; j++@H_450_62@) { int x = points[i][0] - points[j][0@H_450_62@]; int y = points[i][1] - points[j][1@H_450_62@]; if (x == 0@H_450_62@) { y = 1@H_450_62@; } else if (y == 0@H_450_62@) { x = 1@H_450_62@; } else@H_450_62@ { if (y < 0@H_450_62@) { x = -@H_450_62@x; y = -@H_450_62@y; } int gcdXY =@H_450_62@ gcd(abs(X), abs(y)); x /= gcdXY, y /=@H_450_62@ gcdXY; } mp[y + x * 20001]++@H_450_62@; } int maxn = 0@H_450_62@; for (auto&@H_450_62@ [_, num] : mp) { maxn = max(maxn, num + 1@H_450_62@); } ret =@H_450_62@ max(ret, maxn); } return@H_450_62@ ret; } }; int@H_450_62@ main() { // 报错的?? // vector<vector<int>> points = {{1,1}, {2,2}, {3,3}}; vector<vector<int>> points = {{1,1}, {2,2}, {3,3@H_450_62@}}; // vector<vector<int>> points = { {0,0}, {1,2}, {2,4}, {3,6},{4,8}}; cout << Solution().maxPoints(points) <<@H_450_62@ endl; }
以上是大佬教程为你收集整理的6.24_直线上最多的点数_给数组赋值全部内容,希望文章能够帮你解决6.24_直线上最多的点数_给数组赋值所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。