正方形中的最多点数

本文主要是介绍正方形中的最多点数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码实现：

方法一：遍历——超时

int maxPointsInsideSquare(int **points, int pointsSize, int *pointsColSize, char *s) {int a = 0;int flag = 1;int num, pre_num = 0;while (flag) {num = pre_num;pre_num = 0;int hash[26] = {0};for (int i = 0; i < pointsSize; i++) {if (abs(points[i][0]) <= a && abs(points[i][1]) <= a) {if (hash[s[i] - 'a']) {flag = 0;break;}pre_num++;hash[s[i] - 'a']++;}}if (pre_num == pointsSize) {num = pre_num;break;}if (flag) {a++;}}return num;
}

方法二：二分法

int func(int mid, int n, int **points, char *s) {int ret = 0;bool vis[26] = {0};for (int i = 0; i < n; i++) {if (abs(points[i][0]) <= mid && abs(points[i][1]) <= mid) {int c = s[i] - 'a';if (vis[c]) {return -1;}ret++;vis[c] = true;}}return ret;
}
int maxPointsInsideSquare(int **points, int pointsSize, int *pointsColSize, char *s) {int n = pointsSize;int head = 0, tail = 1e9;while (head < tail) {int mid = (head + tail) / 2;if (func(mid, n, points, s) >= 0) {head = mid + 1;} else {tail = mid;}}return func(head - 1, n, points, s);
}

这篇关于正方形中的最多点数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---