正方形中的最多点数

代码实现:

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/617759.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

通过linux花里胡哨的控制台,学习linux基础命令

今天这个B我装定了&#xff01; 前言命令集 开始1、cowsay &#xff08;让牛说话&#xff0c;够无聊的&#xff0c;但牛说的话是你输入的&#xff0c;细思极恐&#xff01;&#xff09;Debian/Ubuntu 安装命令&#xff1a;RHEL/CentOS/Fedora 安装&#xff1a;运行解释 2、fort…

基于51单片机的多路温度检测调节串口传输系统

基于51单片机的多路温度检测调节 &#xff08;仿真&#xff0b;程序&#xff09; 功能介绍 具体功能&#xff1a; 1.采用四个DS18B20温度传感器测温,LCD1602显示四路温度值; 2.三个按键可以设置温度上下限; 3.当每路温度值超过设定的上或下限时,蜂鸣器报警,对应的指示灯亮;…

代数结构:5、格与布尔代数

16.1 偏序与格 偏序集&#xff1a;设P是集合&#xff0c;P上的二元关系“≤”满足以下三个条件&#xff0c;则称“≤”是P上的偏序关系&#xff08;或部分序关系&#xff09; &#xff08;1&#xff09;自反性&#xff1a;a≤a&#xff0c;∀a∈P&#xff1b; &#xff08;2…

【刷题篇】滑动窗口(二)

文章目录 1、水果成篮2、找到字符串中所有字母异位词3、串联所有单词的子串4、最小覆盖子串 1、水果成篮 你正在探访一家农场&#xff0c;农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示&#xff0c;其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多…

景源畅信:抖音小店的商品怎么同步到橱窗?

在数字营销的海洋中&#xff0c;抖音小店与橱窗的同步操作无疑是商家们关注的焦点。这不仅能增加商品的曝光度&#xff0c;还能提高交易的可能性。那么&#xff0c;如何将抖音小店的商品同步到橱窗呢? 一、核心步骤解析 要实现商品从抖音小店同步到橱窗&#xff0c;你需要确保…

程序员工作中常见问题,你遇到过几个?

在赛博朋克2077玩后感中&#xff0c;我提到&#xff0c;即便是在严谨的机制下&#xff0c;依然可能出现让人匪夷所思或是贻笑大方的问题。 那么今天&#xff0c;就以后端程序员的视角&#xff0c;盘点下从设计开发到上线的常见问题&#xff0c;看看大家中过几个。 01 设计与开…

栈和队列讲解

文章目录 栈栈的实现栈的初始化压栈出栈获取栈顶元素获取栈内有效元素个数检查是否为空销毁栈栈的使用 栈全部代码队列的初始化队尾入队列队头出队列获取队列头部元素获取队列队尾元素获取队列中有效元素个数检测队列是否为空&#xff0c;如果为空返回非零结果&#xff0c;如果…

Java设计模式-工厂

Java设计模式中&#xff0c;工厂模式主要包括普通工厂模式以及抽象工厂模式&#xff0c;普通工厂模式是用于制造输出不同类型的对象&#xff0c;抽象工厂模式是用于制造输出不同类型的普通工厂&#xff0c;本文主要描述工厂模式的基本用法。 如上所示&#xff0c;使用普通工厂模…

HCIP(BGP综合实验)--8

一&#xff1a;实验要求 二&#xff1a;实现过程 &#xff08;一&#xff09;配置IP地址&#xff1a; AR1: [AR1]int g0/0/0 [AR1-GigabitEthernet0/0/0]ip add 12.1.1.1 24 [AR1-GigabitEthernet0/0/0]int l0 [AR1-LoopBack0]ip add 172.16.0.1 32 [AR1-LoopBack0]int l1 […

C++异常详解

文章目录 前言一、回顾C语言二、异常的概念三、异常的使用1.异常的抛出和捕获2.异常的重新捕获 三.异常安全与异常规范1.异常安全2.异常规范 四.自定义异常体系五.C标准库的异常体系六.异常优缺点练习题总结 前言 在本篇文章中&#xff0c;我们将会详细介绍一下有关C异常的讲解…

Redis数据结构扩容源码分析

1 Redis数据结构 redis的数据存储在dict.中&#xff0c;其数据结构为(c源码) ypedef struct dict { dictType *type; //理解为面向对象思想&#xff0c;为支持不同的数据类型对应dictType抽象方法&#xff0c;不同的数据类型可以不同实现 void *privdata; //也可不同的数据类…

C++中vector的简单实现

文章目录 一、主要任务1. 查看文档的网站的链接2.内部模拟的函数 二、本人的模拟实现过程1. 所需模拟实现的函数a.构造、拷贝构造b. reverse()扩容c.insert()、push_back()插入数据d. erase()、pop_back()删除数据e. swap()交换f. begin()、end()非const与const迭代器g. 完善构…

【ARM 嵌入式 C 入门及渐进 16.1 -- C 代码实现CRC32校验函数】

请阅读【嵌入式开发学习必备专栏】 文章目录 CRC32校验函数CRC32 表与函数CRC32 测试函数测试结果 对比测试结果 CRC32校验函数 在C语言中&#xff0c;实现CRC32计算的函数需要一个CRC算法的实现。以下是一个使用查表法实现CRC32的简单例子。这种方法通过预先计算好的CRC表来快…

六级翻译笔记

理解加表达 除了专有名词不能自己理解翻译&#xff0c;其它都可以 时态一般唯一 题目里出现有翻译为 客观存在&#xff1a; there be 单词结尾加er和ee的区别&#xff1a;er是主动&#xff0c;ee是被动 中文句子没有被动&#xff0c;也可以英文翻译为被动 中文的状语可以不是…

python代码实现TF-IDF

1、TF-IDF解释 TF-IDF&#xff08;Term frequency–inverse document frequency&#xff09;&#xff0c;中文翻译就是词频 - 逆文档频率&#xff0c;是一种用来计算关键词的传统方法。 TF&#xff08;Term Frequency&#xff09;&#xff1a;TF 的意思就是词频&#xff0c;是…

图片批量管理迈入智能新时代:一键输入关键词,自动生成并保存惊艳图片,轻松开启创意之旅!

在数字化时代&#xff0c;图片已成为我们表达创意、记录生活、传递信息的重要工具。然而&#xff0c;随着图片数量的不断增加&#xff0c;如何高效、便捷地管理这些图片&#xff0c;却成为了一个令人头疼的问题。 第一步&#xff0c;进入首助编辑高手主页面&#xff0c;在上方…

Vagrant + docker搭建Jenkins 部署环境

有人问&#xff0c;为什么要用Jenkins&#xff1f;我说下我以前开发的痛点&#xff0c;在一些中小型企业&#xff0c;每次开发一个项目完成后&#xff0c;需要打包部署&#xff0c;可能没有专门的运维人员&#xff0c;只能开发人员去把项目打成一个war包&#xff0c;可能这个项…

(动画详解)LeetCode面试题 02.04.分割链表

&#x1f496;&#x1f496;&#x1f496;欢迎来到我的博客&#xff0c;我是anmory&#x1f496;&#x1f496;&#x1f496; 又和大家见面了 欢迎来到动画详解LeetCode系列 用通俗易懂的动画的动画使leetcode算法题可视化 先来自我推荐一波 个人网站欢迎访问以及捐款 推荐阅读…

3D 生成重建010-SyncDreamer从单视图生成一致性的多视图

3D 生成重建010-SyncDreamer从单视图生成一致性的多视图 文章目录 0论文工作1论文方法2 效果 0论文工作 在zero123中&#xff0c;首先探索了给2d图像扩散模型注3d空间感知能力。可以将原图输入模型&#xff0c;通过相机位置的相对偏移生成对应的新视图。 这篇论文就是在zero1…

PAD如何实现在用RJ45上网的同时还能保证PAD的续航?|边充电边上网

在数字化时代&#xff0c;手机已经成为我们生活、工作的得力助手。当提及手机边上网边充电时&#xff0c;或许您会想&#xff1a;“这不是常态吗&#xff1f;”但今天&#xff0c;我们要探讨的是一个更为特殊而重要的场景——有线网络直连手机。对于那些需要稳定网络连接、不能…