LeetCOde914 卡牌分组
扑克牌分组问题:探索最大公约数的应用
在编程的世界里,我们经常会遇到各种有趣的算法问题,今天要和大家分享的是一道关于扑克牌分组的问题,它巧妙地运用了最大公约数的概念来解决。
一、问题描述
给定一副牌,每张牌上都写着一个整数。我们需要选定一个数字 X(X >= 2),使得可以将整副牌按下述规则分成 1 组或更多组:
- 每组都有
X张牌。 - 组内所有的牌上都写着相同的整数。
仅当能够找到满足条件的 X 时,返回 true,否则返回 false。
例如,给定牌组 [1, 2, 3, 4, 4, 3, 2, 1],我们可以将其分成两组 [1, 1]、[2, 2]、[3, 3]、[4, 4],此时 X = 2,满足条件,应返回 true。
二、解题思路
这道题的关键在于统计牌中每个数字出现的次数,然后找出这些次数的最大公约数。如果最大公约数大于等于 2,那么就可以按照要求进行分组。
我们可以使用一个数组来统计每个数字的出现次数,然后遍历这个数组,对于出现次数大于 0 的元素,通过辗转相除法(或类似的求最大公约数的方法)来不断更新最大公约数。
三、代码实现
#include <stdio.h>
#include <stdbool.h>// 函数用于判断给定的牌组能否按规则分组
bool hasGroupsSizeX(int* deck, int deckSize) {if (deckSize < 2) {return false;}// 用于统计每个数字出现的次数int count[10000] = {0};for (int i = 0; i < deckSize; i++) {count[deck[i]]++;}int x = count[deck[0]];for (int i = 0; i < 10000; i++) {if (count[i] > 0) {// 求最大公约数的逻辑整合在该函数内while (count[i] % x!= 0) {int temp = x;x = count[i] % x;count[i] = temp;}if (x < 2) {return false;}}}return x >= 2;
}int main() {int deck[] = {1, 2, 3, 4, 4, 3, 2, 1}; // 示例牌组,可替换为其他测试数据int deckSize = sizeof(deck) / sizeof(deck[0]);bool result = hasGroupsSizeX(deck, deckSize);if (result) {printf("可以按照规则分组\n");} else {printf("无法按照规则分组\n");}return 0;
}
在这段代码中,首先判断牌组的大小是否小于 2,如果是则直接返回 false。然后统计每个数字的出现次数,接着选取第一个数字的出现次数作为初始的 x,通过循环遍历统计数组,对出现次数大于 0 的元素求其与 x 的最大公约数,并不断更新 x。如果在过程中 x 小于 2,则返回 false,最后根据最终的 x 是否大于等于 2 返回相应的结果。
四、时间和空间复杂度分析
- 时间复杂度:统计牌中数字出现次数的循环需要遍历整个牌组,时间复杂度为 ,其中
n是牌的数量(deckSize)。求最大公约数的操作最多执行m次,m是牌中不同数字的个数,每次求最大公约数类似辗转相除有一定计算量,整体时间复杂度约为 。 - 空间复杂度:使用了一个固定大小的数组来统计数字出现次数,由于数组大小固定(这里假设数字范围在一定范围内,若数字范围大需优化处理),可近似看作常数空间复杂度 (不算输入的
deck数组占用空间)。
五、总结
这道扑克牌分组问题不仅考验了我们对数组的操作和遍历能力,更深入地涉及到了最大公约数的应用。通过巧妙地统计数字出现次数并求最大公约数,我们能够高效地解决这个看似复杂的分组问题。在解决这类问题的过程中,我们可以加深对算法和数据结构的理解,提升编程能力,为解决更复杂的问题打下坚实的基础。希望这篇博客能够帮助大家理解这道题的解法,如果有任何疑问或者更好的解法,欢迎大家一起讨论交流!
相关文章:
LeetCOde914 卡牌分组
扑克牌分组问题:探索最大公约数的应用 在编程的世界里,我们经常会遇到各种有趣的算法问题,今天要和大家分享的是一道关于扑克牌分组的问题,它巧妙地运用了最大公约数的概念来解决。 一、问题描述 给定一副牌,每张牌…...
MicroDiffusion——采用新的掩码方法和改进的 Transformer 架构,实现了低预算的扩散模型
介绍 论文地址:https://arxiv.org/abs/2407.15811 现代图像生成模型擅长创建自然、高质量的内容,每年生成的图像超过十亿幅。然而,从头开始训练这些模型极其昂贵和耗时。文本到图像(T2I)扩散模型降低了部分计算成本&a…...
QWT 之 QwtPlotDirectPainter直接绘制
QwtPlotDirectPainter 是 Qwt 库中用于直接在 QwtPlot 的画布上绘制图形的一个类。它提供了一种高效的方法来实时更新图表,特别适合需要频繁更新的数据可视化应用,例如实时数据流的显示。 使用 QwtPlotDirectPainter 的主要优势在于它可以绕过 QwtPlot 的…...
埃斯顿机器人程序案例多个点位使用变量
多个点位使用变量取放...
【数据分析】贝叶斯定理
文章目录 一、贝叶斯定理的基本形式二、贝叶斯定理的推导三、贝叶斯定理的应用四、贝叶斯定理的优势与挑战 贝叶斯定理(Bayes Theorem)是概率论中的一个重要公式,它提供了一种根据已有信息更新事件发生概率的方式。贝叶斯定理的核心思想是通过…...
学AI编程的Prompt工程,marscode
利用marscode做个创意应用 Datawhale-AI活动 首先把自己的创意告诉marscode,marscode会针对你的创意开始写代码。如果在把创意给marscode前有更好的梳理,会有更好的结果。 对于一个新开始的项目,只需要点击apply进行应用 由于ai的效果不稳定…...
python中的与时间相关的模块
python中的与时间相关的模块 1. time 模块2. datetime 模块3. calendar 模块4. timeit 模块5. pytz 模块6. dateutil 模块参考资料 1. time 模块 time 模块提供了时间相关的函数,主要用于测量时间间隔、获取当前时间、格式化时间等 主要功能 获取当前时间ÿ…...
【Python运维】构建基于Python的自动化运维平台:用Flask和Celery
《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门! 解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 在现代IT运维中,自动化运维平台扮演着至关重要的角色,它能够显著提高运维效率,减少人为错误,并且增强系统的可维护性。本文将引导读者如…...
Qt 12.28 day3
作业: 1】 思维导图 2】 在登录界面的登录取消按钮进行以下设置: 使用手动连接,将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中,在自定义的槽函数中调用关闭函数 将登录按钮使用qt5版本的连接到自定义的槽函数中&a…...
Java爬虫获取速卖通(AliExpress)商品详情
1. 环境准备 在开始编写爬虫之前,需要准备以下环境和工具: Java开发环境:确保你的计算机上安装了Java开发工具包(JDK)。IDE:选择一个Java集成开发环境,如IntelliJ IDEA、Eclipse等。第三方库&…...
Learning Multi-Scale Photo Exposure Correction
Abstract 用错误的曝光捕捉照片仍然是相机成像的主要错误来源。曝光问题可分为以下两类:(i)曝光过度,即相机曝光时间过长,导致图像区域明亮和褪色;(ii)曝光不足,即曝光时间过短,导致图像区域变暗。曝光不足和曝光过度都会大大降低…...
【Rust自学】7.4. use关键字 Pt.1:use的使用与as关键字
喜欢的话别忘了点赞、收藏加关注哦,对接下来的教程有兴趣的可以关注专栏。谢谢喵!(・ω・) 7.4.1. use的作用 use的作用是将路径导入到当前作用域内。而引入的内容仍然是遵守私有性原则,也就是只有公共的部分引入进来才…...
C++ 设计模式:门面模式(Facade Pattern)
链接:C 设计模式 链接:C 设计模式 - 代理模式 链接:C 设计模式 - 中介者 链接:C 设计模式 - 适配器 门面模式(Facade Pattern)是一种结构型设计模式,它为子系统中的一组接口提供一个一致&#…...
从0到100:基于Java的大学选修课选课小程序开发笔记(上)
背景 为学生提供便捷的课程选择方式,并帮助学校进行课程管理和资源调配;主要功能包括:课程展示,自主选课,取消选课,后台录入课程,统计每门课程报名情况,导出数据,用户管…...
【算法题解】B. President‘s Office - Python实现
题目描述 Berland的总统办公室内设有多个办公桌,其中总统和其属下各自拥有独特颜色的办公桌。总统希望统计哪些属下的办公桌紧邻他的办公桌,但不记得确切的数量。 输入描述: 第一行包含三个值 n, m, c,分别是办公室的长度、宽度…...
【Spring Boot 】详解
Spring Boot 详解 一、Spring Boot 概述 (一)产生背景 随着 Java 应用的日益复杂,传统 Spring 框架在项目搭建与配置方面愈发繁琐,大量的 XML 配置、依赖管理等工作耗费开发者诸多精力。为解决这些痛点,Spring Boot …...
Redisson 框架详解
目录 一.为什么要使用分布式锁? 二.Redisson 的基本使用: 1.添加 Redisson 依赖: 2.在 application.yml 配置 Redis: 3. 创建 Redisson 客户端: (1)单节点模式: (…...
正确导入MapStruct并避免与Lombok编译冲突的深入分析
正确导入MapStruct并避免与Lombok编译冲突的深入分析 一、MapStruct与Lombok概述 1.1 MapStruct简介 MapStruct是一个代码生成器,它基于约定优于配置的原则,通过注解处理器在编译时自动生成源代码,实现对象之间的属性映射。MapStruct的优势在于减少样板代码,提高开发效率…...
K8S 黑魔法之如何从 Pod 拿到节点的命令行
搞 K8S 运维的时候,偶尔会遇到一个难题,定位到问题出在某个节点上,而由于权限审批,错误配置等等各种原因,没有办法拿到节点的 SSH 权限,无法进入节点命令行进一步排障。 这个时候,就可以用这个…...
【bluedroid】A2dp Source播放流程源码分析(4)
接上集分析:【bluedroid】A2dp Source播放流程源码分析(3)-CSDN博客 蓝牙和AUDIO之间的接口 蓝牙和audio之间的通信是通过socket,管理socket中的文件是UIPC,UIPC管理两条socket。 A2DP_CTRL_PATH /data/misc/bluedroid/.a2dp_ctrl A2DP_DATA_PATH /data/misc/bluedroid…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
