当前位置: 首页 > news >正文

每日一练2024.5.9

题目:

给定一副牌,每张牌上都写着一个整数。

此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组:

  • 每组都有 X 张牌。
  • 组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true

示例 1:

输入:deck = [1,2,3,4,4,3,2,1]
输出:true
解释:可行的分组是 [1,1],[2,2],[3,3],[4,4]

示例 2:

输入:deck = [1,1,1,2,2,2,3,3]
输出:false
解释:没有满足要求的分组。

解题:

        这是一道典型的编程问题,通常出现在算法和数据结构相关的挑战中。其核心要求是寻找一组数X,使得给定数组(牌堆 deck)能够按照一定的规则分组。这里的规则是:每组牌的数量需要相同,且每组牌上的数字也需要相同。

解题思路可以分为以下几步:

  1. 计数:首先需要统计deck中每个数字出现的频率。例如,如果deck[1,2,3,4,4,3,2,1],那么数字1出现2次,数字2出现2次,数字3出现2次,数字4出现2次。

  2. 寻找最大公约数:在得到每个数字的出现次数后,需要寻找这些次数的最大公约数(GCD)。如果最大公约数大于等于2,那么意味着可以将牌分组,每组牌的数目都是这个最大公约数,且每组中的牌的数字相同。

  3. 判断结果:最终的判断基于最大公约数是否大于等于2。如果是,返回true(表示可以分组),否则返回false(表示无法满足题目中的分组要求)。

        举例来说,在示例1中,每种数字出现的次数都是2,它们的最大公约数也是2,因此可以分为每组2张牌的几组,每组内的数字相同,所以返回true

        在示例2中,数字1, 2, 3的出现次数各为3,它们的最大公约数是1,因为题目要求X至少为2,所以这个情况下没有满足要求的分组方法,返回false。        

代码:

import java.util.HashMap;
import java.util.Map;
// Solution类,包含实现算法的方法
class Solution {// hasGroupsSizeX,这是核心的公共方法,它检查能否将deck分成满足条件的组。// 它接受一个整型数组作为参数。public boolean hasGroupsSizeX(int[] deck) {// 频率数组count,用来统计deck中每个数字出现的次数。// 我们这里假设deck中的数值不会超过10000。int[] count = new int[10000];for (int num : deck) {count[num]++;}// g用来记录当前找到的所有数的次数的最大公约数。int g = -1;for (int i = 0; i < count.length; i++) {if (count[i] > 0) {// 初始化g或者不断找到新的g(新的数的次数和当前g的最大公约数)。if (g == -1) {g = count[i];} else {g = gcd(g, count[i]);}// 如果在任何时候g变为1,由于问题的设定,直接返回false。if (g == 1) {return false;}}}// 如果g不小于2,则说明我们可以将deck按要求分组。return g >= 2;}// 辅助方法gcd,它利用循环计算两个正整数的最大公约数。private int gcd(int a, int b) {while (b != 0) {int t = b;      // 在这里,t是用来暂存b的值。b = a % b;      // 根据欧几里得算法更新b的值为a除以b的余数。a = t;          // 然后将a的值设置为之前b的值。}return a;           // 在b变成0时,最大公约数就是a。}
}

知识点概览:

  1. Java基础 - 方法的定义、循环、条件语句、返回值。
  2. 数组 - 使用静态分配的数组来存储整型数据。
  3. 增强型for循环 (for-each loop) - 遍历数组中的元素。
  4. 辅助方法(gcd方法) - 封装逻辑以与主要逻辑分离,并实现代码复用。
  5. 算法 - 最大公约数的计算(欧几里得算法)。
  6. 变量的作用域和生命周期 - g变量、临时变量it在方法内的局部使用。
  7. 逻辑短路 - 在发现gcd为1的情况下立即返回false,不需要执行更多的操作。
  • 数组int[] count = new int[10000],这一句初始化了一个大小为10000的整型数组。这个数组被用来统计每个数字出现的次数。我们可以使用数组而不是HashMap因为整数可以直接映射到数组索引,这里我们假设deck中的整数不会超过10000。

  • 增强型for循环for (int num : deck)这个循环是Java的增强型for循环,它能够遍历数组或者任何实现了Iterable接口的集合中的所有元素。

  • 循环与条件判断for (int i = 0; i < count.length; i++)这个循环遍历我们之前创建的count数组。if (count[i] > 0)这个判断确保我们只在数的出现次数不为0时进行gcd计算。

  • 最大公约数计算函数(gcd函数):这是一个本地辅助方法,它通过循环计算两个数的最大公约数,而不是递归,这可以提高效率并避免栈溢出错误。该方法是一个封装的逻辑块,可以从主逻辑中分离出来,并在需要时被重用。

  • 逻辑短路:在计算gcd的过程中,代码通过判断if (g == 1)来检查是否已经有证据表明无法按要求进行分组。如果gcd是1,函数会立即返回false,因为根据数学定理,gcd为1说明没有其他的数大于1可以整除数组中的所有数的出现频率。

  • 变量作用域g是一个整型变量,它存储了当前gcd的值;t是gcd算法中的临时变量,用于交换数值。

知识点类别描述
Java基础方法定义、循环控制、条件语句、返回值等
数组使用固定大小的数组来统计频次,整数作为数组索引
增强型for循环遍历数组中的元素,简化集合或数组的迭代
辅助方法(GCD方法)欧几里得算法的实现,局部逻辑封装,增强代码的复用性
算法最大公约数(GCD)的求解,关键于问题的解决
变量作用域和生命周期局部变量g用于存储最大公约数,it用于循环和值交换,在方法内部控制其生命周期
逻辑短路提前返回逻辑,当算出的最大公约数为1时,立即决定输出,并结束方法的执行,提升代码的效率和执行速度

 

0502ffb80b674896ab1ea3389904a244.png2024.5.9

 

相关文章:

每日一练2024.5.9

题目&#xff1a; 给定一副牌&#xff0c;每张牌上都写着一个整数。 此时&#xff0c;你需要选定一个数字 X&#xff0c;使我们可以将整副牌按下述规则分成 1 组或更多组&#xff1a; 每组都有 X 张牌。组内所有的牌上都写着相同的整数。 仅当你可选的 X > 2 时返回 tru…...

P2622 关灯问题

小小注解&#xff1a; 1. vis&#xff1a;表示到达该状态的步数&#xff08;min&#xff09;1&#xff0c; 因为我们是从开始状态 穷举&#xff0c;所以每次到一个新状态&#xff08;之前没有到过的状态&#xff09;就是最小步数。 如何判断是否是一个新状态呢&#xff0c…...

从头开始的建材类电商小程序开发指南

在当今数字化时代&#xff0c;小程序已经成为了许多企业推广和销售的重要渠道。对于建筑材料行业来说&#xff0c;开发一个属于自己的小程序商城不仅可以提升产品曝光度&#xff0c;还可以提供更好的用户购物体验。下面&#xff0c;我们将逐步教你如何开发建筑材料行业小程序。…...

数据结构中的栈(C语言版)

一.栈的概念 栈是一种常见的数据结构&#xff0c;它遵循后进先出的原则。栈可以看作是一种容器&#xff0c;其中的元素按照一种特定的顺序进行插入和删除操作。 压栈&#xff1a;栈的插入操作叫做进栈/压栈/入栈&#xff0c;入数据在栈顶。 出栈&#xff1a;栈的删除操作叫做…...

(贪心05) 无重叠区间 划分字母区间 合并区间

一、无重叠区间 力扣第435题 第一种方法&#xff1a; 个人思路&#xff1a; 按照区间左边界排序&#xff0c;然后从左开始遍历&#xff0c;每遍历到一个区间就要保证该区间之前的集合为不重叠区间&#xff08;贪心&#xff0c;局部最优解&#xff09;。 难点在于如何把新遍历…...

简单网络管理协议(SNMP)入门

目录 概述 SMI&#xff08;对象命名、数据类型、编码方法&#xff09; 对象命名 数据类型 编码方法 MIB&#xff08;版本、分组、对象定义、变量访问&#xff09; 版本 分组 对象定义 变量访问 SNMP 实现机制与报文分析 协议操作 报文格式 实现机制 验证分析 SN…...

leetcode解题思路分析(一百五十七)1366 - 1372 题

通过投票对团队排名 现在有一个特殊的排名系统&#xff0c;依据参赛团队在投票人心中的次序进行排名&#xff0c;每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。 排名规则如下&#xff1a; 参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在…...

药物代谢动力学学习笔记

一、基本概念 二、经典房室模型 三、非线性药物代谢动力学 四、非房室模型 五、药代动力学与药效动力学 六、生物等效性评价 七、生物样品分析方法 基本概念 生物样品&#xff1a;生物机体的全血、血浆、血清、粪便、尿液或其他组织的样品 特异性&#xff0c;specificity&…...

IDEA中git的常用操作(保姆级教学)

IDEA中git的常用操作&#xff08;保姆级教学&#xff09; 以下是git的工作原理&#xff0c;觉得繁琐的可以跳过不看 Workspace&#xff1a;工作区 (平时存放代码的地方) Index / Stage&#xff1a;暂存区&#xff08;用于临时存放存放你的改动&#xff0c;事实上就是一个文件&…...

保研面试408复习 3——操作系统

文章目录 1、操作系统一、进程有哪几种状态&#xff0c;状态之间的转换、二、调度策略a.处理机调度分为三级&#xff1a;b.调度算法 标记文字记忆&#xff0c;加粗文字注意&#xff0c;普通文字理解。 为什么越写越少&#xff1f; 问就是在打瓦。(bushi) 1、操作系统 一、进程…...

【代码随想录37期】Day02 有序数组的平方、长度最小的子数组、螺旋矩阵Ⅱ(施工中)

有序数组的平方 977. 有序数组的平方 - 力扣&#xff08;LeetCode&#xff09; v1.0:直接暴力 4分半做出来&#xff0c;用sort api class Solution { public:vector<int> sortedSquares(vector<int>& nums) {vector<int> result;for(int i 0; i<…...

通俗的理解网关的概念的用途(三):你的数据包是如何到达下一层的

其实&#xff0c;这一章我写不好&#xff0c;因为这其中会涉及到一些计算和一些广播等概念&#xff0c;本人不善于此项。在此略述&#xff0c;可以参考。 每台设备的不同连接在获得有效的IP地址后&#xff0c;会根据IP地址的规则和掩码的规则&#xff0c;在操作系统和交换机&a…...

基于Springboot的校运会管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的校运会管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&a…...

USP技术提升大语言模型的零样本学习能力

大语言模型&#xff08;LLMs&#xff09;在零样本和少样本学习能力上取得了显著进展&#xff0c;这通常通过上下文学习&#xff08;in-context learning, ICL&#xff09;和提示&#xff08;prompting&#xff09;来实现。然而&#xff0c;零样本性能通常较弱&#xff0c;因为缺…...

前端安全防护实战:XSS、CSRF防御与同源策略详解(react 案例)

前端安全防护实战中&#xff0c;主要涉及三个方面&#xff1a;XSS (Cross-Site Scripting) 攻击的防御、CSRF (Cross-Site Request Forgery) 攻击的防御&#xff0c;以及浏览器的同源策略。以下是这三个方面的详细说明&#xff1a; XSS 防御详解 XSS 概述 XSS攻击是一种让攻…...

2024C题生物质和煤共热解问题的研究 详细思路

背景 随着全球能源需求的不断增长和对可再生能源的追求&#xff0c;生物质和煤共热解作为一种潜在的能源转化技术备受关注。生物质是指可再生能源&#xff0c;源自植物和动物的有机物质&#xff0c;而煤则是一种化石燃料。** 在共热解过程中&#xff0c;生物质和煤在高温和缺氧…...

智慧旅游引领未来风尚,科技助力旅行更精彩:科技的力量推动旅游业创新发展,为旅行者带来更加便捷、高效和智能的旅行服务

目录 一、引言 二、智慧旅游的概念与特点 &#xff08;一&#xff09;智慧旅游的概念 &#xff08;二&#xff09;智慧旅游的特点 三、科技推动旅游业创新发展 &#xff08;一&#xff09;大数据技术的应用 &#xff08;二&#xff09;人工智能技术的应用 &#xff08;…...

十.吊打面试官系列-Tomcat优化-通过压测Tomcat调优实战

前言 上一篇文章我们讲解了一下Tomcat底层的结构和执行原理&#xff0c;我们需要重点去掌握的是Tomcat的高内聚低耦合的设计&#xff0c;以及责任链模式&#xff0c;以及Tomcat NIO编程模式&#xff0c;这些是Tomcat比较核心的点&#xff0c;本篇文章我们将对Tomcat的参数做一…...

JVM调优—减少FullGC

背景 最近负责了一个审批流程新项目&#xff0c;带领了几个小伙伴&#xff0c;哼哧哼哧的干了3个月左右&#xff0c;终于在三月底完美上线了&#xff0c;好消息是线上客户用的很丝滑&#xff0c;除了几个非常规的业务提单之外&#xff0c;几乎没有什么大的问题&#xff0c;但是…...

力扣 256. 粉刷房子 LCR 091. 粉刷房子 python AC

动态规划 class Solution:def minCost(self, costs):row, col len(costs), 3dp [[0] * col for _ in range(row 1)]for i in range(1, row 1):for j in range(col):dp[i][j] costs[i - 1][j - 1]if j 0:dp[i][j] min(dp[i - 1][1], dp[i - 1][2])elif j 1:dp[i][j] m…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...