LeetCode575——分糖果

     题目链接:. - 力扣(LeetCode)

   

        这道题比较简单,但我还是花费了将近四个小时的时间去解答,AC的那一刻,终于全身舒畅,这道题的思路就是先求出糖果的种数,然后我们从题中可以得出,Alice最少吃一种糖果,最多吃n/2种糖果,我们可以用二分法来写,下面来看代码:

//求出糖果种数,哈希的方式
int typecount(int* a, int size)
{
    //开辟空间注意数据范围,题上给的a[i]的数据范围是-100000到100000
    int* hx = calloc(200010,sizeof(int));//calloc开辟出来的空间初始都为0
    int count = 0;
    for (int i = 0; i < size; i++)
    {
        hx[a[i]+100000]++;//因为题上给的a[i]的数据范围是-100000到100000,所以
    }                     //hx[a[i]+100000]可以避免数组下标是负数
    for (int i = 0; i < 200010; i++)
    {
        if (hx[i] != 0)//ha[i]不为0,就说明是一种糖果类型,count++
        {
            count++;
        }
    }
    free(hx);//释放calloc开辟的空间
    return count;
}

int check(int mid,int count)
{
    if (mid < count)
        return 1;
    return 0;
}

int distributeCandies(int* candyType, int candyTypeSize) {
    int n = candyTypeSize;
    
    int count=typecount(candyType, candyTypeSize);//糖果种类
    //因为Alice最少吃一种糖果,最多吃n/2种糖果,所以用二分法
    int l = 1, r = n / 2;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid,count))
        {
            l = mid + 1;//如果mid<count,更新左边界,l=mid+1,因为mid肯定不是我们要找的值,
                        //所以我们在[mid+1,r]这个区间去找
        }
        else
            r = mid;//如果mid>=count,更新右边界,r=mid,因为mid可能等于count,也就是说
                    //mid可能是我们要找的值,所以我们在[l,mid]这个区间找
    }
    return r;//最后返回r就是Alice吃到糖的最多种类数,其实返回l也是可以的,因为到
            //最后l==r,返回哪个都是可以的
}

       代码注释的很清楚,这里就不再细说了,还需要注意的一点是count可能大于n/2,但是不影响,我们只需要在[1,n/2]这个区间找就好了。

        请注意 :轻易不要定义全局变量,很危险的,我就是因为把hx定义成全局变量,调试了很长时间,都过不去,就是找不到问题在哪,一定要记住这个坑呀!(当然,不亲身经历应该是记不住的,希望你们经历后,再来看这段话是什么感受)

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

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

相关文章

PMP备考需要多长时间?

PMP备考需要多久&#xff1f;50天就能顺利学完 PMP考试备考时间需要看自己的工作安排了&#xff0c;学习周期要恰到好处&#xff0c;太长的话可能导致边学边忘&#xff0c;根本来不及总结冲刺&#xff1b;太短的话又会造成学习内容掌握不稳定&#xff0c;导致考试的时候发挥失…

JavaScript(一)基础

文章目录 一、JS介绍JavaScript是什么JavaScript书写位置JavaScript的注释输入输出语法字面量 二、变量变量是什么变量基本使用变量的本质变量命名规则与规范变量拓展-数组var与let的区别 三、常量四、数据类型数据类型检测数据类型数据类型转换隐式转换显式转换 简单运算符断点…

3.冒泡排序

冒泡排序 基本思想&#xff1a;每次比较两个相邻的元素 如果它们的顺序错误就把它们交换过来 重点&#xff1a;交换 时间复杂度为&#xff1a;O(n^2)&#xff08;平均情况、最坏情况&#xff09; 最优情况&#xff1a;输入的数组已经是完全有序的时候 冒泡排序只需要进行一…

day11 java不同对象的关联与内存分析 JavaBean用途及讲解 import导入包

不同对象的关联与内存分析 内存图&#xff1a; 对象的属性是另一个对象时&#xff0c;在堆内存内该属性对应的值是另一个对象的首地址&#xff08;指向另一个堆内存内另一个对象&#xff09;&#xff0c;两对象建立了联系&#xff0c;可以根据箭头间接调用。 JavaBean…

基于SpringBoot + Vue实现的员工绩效考核管理系统设计与实现+毕业论文+PPT+任务书+搭建视频

介绍 系统包含员工和管理员两个角色 管理员&#xff1a; 部门管理&#xff1a;负责创建、修改和删除部门&#xff0c;以及为部门设置权限和角色。 岗位管理&#xff1a;定义和管理岗位信息&#xff0c;包括添加、修改和删除岗位&#xff0c;以及设置岗位的职责和要求 员工…

一、企业级架构之LNMP

一、LNMP 概述 1、LNMP之间的关系&#xff1a; LNMP Linux Nginx MySQL PHP 2、配置LNMP服务器&#xff1a; (1) 克隆一台centos7虚拟机&#xff0c;修改 IP 地址 和 UUID 编号。 IP 为 10.1.1.10&#xff0c;UUID 修改后三位。 (2) 设置主机名称&#xff0c;绑定IP地…

计算机组成原理-10-控制单元的设计

10. 控制单元的设计 文章目录 10. 控制单元的设计10.1 组合逻辑设计10.1.1 CU外特性10.1.2 微操作的节拍安排10.1.3 组合逻辑设计步骤 10.2 微程序设计10.2.1 微程序设计思想10.2.2 微指令格式10.2.3 毫微程序设计10.2.4 微程序设计举例 完结撒花 本笔记参考哈工大刘宏伟老师的…

最新社交相亲系统源码PHP

最新社交相亲系统源码PHP 安装环境&#xff1a; php7.2 mysql 5.7 框架&#xff1a; 后端thinkphp6 前端&#xff1a;jquery layui PC 移动端响应式 线上案例&#xff1a;https://cjr.oemsun.com/ 主要页面及功能预览 首页 相亲资料详情页 红娘跟进记录 海报、一键复制分…

Cisco ACI Simulator 6.0(5h) - ACI 模拟器

Cisco ACI Simulator 6.0(5h) - ACI 模拟器 Application Centric Infrastructure (ACI) Simulator Software 请访问原文链接&#xff1a;https://sysin.org/blog/cisco-acisim-6/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.o…

【核弹级安全事件】XZ Utils库中发现秘密后门,影响主要Linux发行版,软件供应链安全大事件

Red Hat 发布了一份“紧急安全警报”&#xff0c;警告称两款流行的数据压缩库XZ Utils&#xff08;先前称为LZMA Utils&#xff09;的两个版本已被植入恶意代码后门&#xff0c;这些代码旨在允许未授权的远程访问。 此次软件供应链攻击被追踪为CVE-2024-3094&#xff0c;其CVS…

卡奥斯工业互联网平台分析

一、 背景 卡奥斯是海尔推出的具有中国自主知识产权、全球首家引入用户全流程参与体验的工业互联网平台。其核心是大规模定制模式&#xff0c;通过持续与用户交互&#xff0c;将硬件体验变为场景体验&#xff0c;将用户由被动的购买者变为参与者、创造者&#xff0c;将企业由原…

Vue3配置router路由步骤

Vue3配置router路由步骤 首先创建一个vue3的项目 先检查一下router的版本&#xff0c;可以在pakage.json里面查看&#xff0c;也可以你直接在终端输入 npm list vue-router如果版本比较低的话&#xff0c;先升级一下 vue3的话&#xff0c;用以下命令 npm install vue-route…

C语言TCP服务器模型 : select + 多线程与双循环单线程阻塞服务器的比较

观察到的实验现象: 启动三个客户端: 使用双循环阻塞服务器:只能accept后等待收发,同时只能与一个客户端建立连接,必须等已连接的客户端多次收发 明确断开后才能与下个客户端连接 使用IO多路复用select:可以同时接收所有的连接请求,并且连接状态一直是存活的,直到客户端关闭连…

Kubesphere 自动化部署失败报错

Kubesphere 自动化部署在 push tag 阶段失败报错 git push http://****:****github.com/****/devops-java-sample.git --tags --ipv4 remote: Support for password authentication was removed on August 13, 2021. remote: Please see https://docs.github.com/get-started/g…

Netty是什么

一、Netty介绍 1、Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用以快速开发高性能、高可靠性的网络IO程序。 2、Netty主要针对在TCP协议下&#xff0c;面向Clients端的高并发应用&#xff0c;或者Peer-to-Peer场景下的大量数据持续传输的应用。 3、Netty本质是…

银行数字化转型导师坚鹏:银行数字化转型给分行带来的8大价值

银行数字化转型给分行带来的8大价值 银行数字化转型对不仅对总行产生了深远影响、给总行带来了新质生产力&#xff0c;对分行也会产生重要价值&#xff0c;银行数字化转型导师坚鹏从以下8个方面进行详细分析&#xff0c;相信能够给您带来重要启发&#xff0c;从而加速银行分行…

【并发编程系列】使用 CompletableFuture 实现并发任务处理

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

[C#]OpenCvSharp利用MatchTemplate实现多目标匹配

【效果展示】 原图 模板图 匹配结果&#xff1a; 【实现部分代码】 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using…

RabbitMQ3.x之九_Docker中安装RabbitMQ

RabbitMQ3.x之_Docker中安装RabbitMQ 文章目录 RabbitMQ3.x之_Docker中安装RabbitMQ1. 官网2. 安装1 .拉取镜像2. 运行容器 3. 访问 1. 官网 rabbitmq - Official Image | Docker Hub 2. 安装 1 .拉取镜像 docker pull rabbitmq:3.13.0-management2. 运行容器 # latest Rabb…

从零起步:开启你的IT职业之旅

简介&#xff1a; 信息技术&#xff08;IT&#xff09;行业以其快速发展和广阔的就业前景吸引着全球众多职场新人。但对于零基础的求职者而言&#xff0c;挺进这一行业似乎是条充满挑战的道路。进入IT行业可能看起来是一项艰巨的挑战&#xff0c;尤其是对于那些没有任何相关经…