代码实现:
方法一:遍历——超时
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); }