正方形中的最多点数

代码实现:

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

相关推荐

  1. 221. 正方形

    2024-05-12 23:20:04       30 阅读

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-12 23:20:04       0 阅读
  2. QT--气泡框的实现

    2024-05-12 23:20:04       1 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-12 23:20:04       0 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-12 23:20:04       0 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-12 23:20:04       0 阅读
  6. C 语言设计模式(结构型)

    2024-05-12 23:20:04       0 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-12 23:20:04       0 阅读
  8. kafka防止消息丢失配置

    2024-05-12 23:20:04       0 阅读

热门阅读

  1. 物联网系统

    2024-05-12 23:20:04       3 阅读
  2. Linux学习笔记3

    2024-05-12 23:20:04       4 阅读
  3. 十二届蓝桥杯Python组3月中/高级试题 第三题

    2024-05-12 23:20:04       2 阅读
  4. 数据库知识初步汇总

    2024-05-12 23:20:04       3 阅读
  5. 什么股指期货滚IC的意思?

    2024-05-12 23:20:04       2 阅读
  6. PostgreSQL自带的命令行工具14- pg_test_timing

    2024-05-12 23:20:04       5 阅读
  7. socket编程 学习笔记 理解

    2024-05-12 23:20:04       3 阅读
  8. Android RadioButton,定制按钮样式

    2024-05-12 23:20:04       3 阅读