python解题之寻找最大的葫芦
问题描述
问题描述
在一场经典的德州扑克游戏中,有一种牌型叫做“葫芦”。“葫芦”由五张牌组成,其中包括三张相同牌面值的牌 �a 和另外两张相同牌面值的牌 �b。如果两个人同时拥有“葫芦”,我们会优先比较牌 �a 的大小,若牌 �a 相同则再比较牌 �b 的大小,牌面值的大小规则为:1 (A) > K > Q > J > 10 > 9 > ... > 2,其中 1 (A) 的牌面值为1,K 为13,依此类推。
在这个问题中,我们对“葫芦”增加了一个限制:组成“葫芦”的五张牌牌面值之和不能超过给定的最大值 ���max。
给定一组牌,你需要找到符合规则的最大的“葫芦”组合,并输出其中三张相同的牌面和两张相同的牌面。如果找不到符合条件的“葫芦”,则输出 “0, 0”。
测试样例
样例1:
输入:
n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]
输出:[8, 5]
说明:array
数组中可组成4个葫芦,分别为[6,6,6,8,8],[6,6,6,5,5],[8,8,8,6,6],[8,8,8,5,5]。其中[8,8,8,6,6]的牌面值为36,大于34不符合要求。剩下的3个葫芦的大小关系为[8,8,8,5,5]>[6,6,6,8,8]>[6,6,6,5,5],故返回[8,5]
样例2:
输入:
n = 9, max = 37, array = [9, 9, 9, 9, 6, 6, 6, 6, 13]
输出:[6, 9]
说明:可组成2个葫芦,分别为[9,9,9,6,6]和[6,6,6,9,9],由于[9,9,9,6,6]的牌面值为39,大于37,故返回[6,9]
样例3:
输入:
n = 9, max = 40, array = [1, 11, 13, 12, 7, 8, 11, 5, 6]
输出:[0, 0]
说明:无法组成任何葫芦,故返回[0,0]
样例4:
输入:
n = 6, max = 50, array = [13, 13, 13, 1, 1, 1]
输出:[1, 13]
说明:可组成两个葫芦,分别为[A,A,A,K,K]和[K,K,K,A,A],两者牌面值都小于50,故都合法。因为三张相同牌面值的A > K,故[A,A,A,K,K]比[K,K,K,A,A]要大,返回[1,13]
为了解决这个问题,我们可以采用以下步骤:
- 排序和计数:首先对给定的牌进行排序,并计算每种牌面值出现的次数。
- 寻找可能的“葫芦”组合:遍历排序后的数组,尝试找到三张相同牌面值的牌(
a
),然后继续查找两张相同但不同于a
的牌面值的牌(b
)。 - 检查总和是否满足条件:对于每一个可能的“葫芦”组合,检查其总和是否不超过
max
。 - 记录最优解:如果当前“葫芦”组合是合法的,并且比之前找到的更好(即
a
更大,或者a
相同而b
更大),则更新最优解。 - 返回结果:遍历完成后,返回最优解。如果没有找到任何合法的“葫芦”,则返回
[0, 0]
。
下面是 Python 实现代码:
def solution(n: int, max: int, array: list) -> list:assert n == len(array)from collections import Counterc = Counter(array)vals = [1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]for x in vals:for y in vals:if x * 3 + y * 2 <= max and c[x] >= 3 and c[y] >= 2 and x != y:return [x, y]return [0, 0]if __name__ == '__main__':print(solution(n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]) == [8, 5])print(solution(n = 9, max = 37, array = [9, 9, 9, 9, 6, 6, 6, 6, 13]) == [6, 9])print(solution(n = 9, max = 40, array = [1, 11, 13, 12, 7, 8, 11, 5, 6]) == [0, 0])
解题过程
- 统计牌面值数量:使用
Counter
统计每种牌面值的数量。 - 遍历所有可能的牌面值组合:通过双层循环遍历所有可能的牌面值组合 (x,y),其中 x 代表三张相同牌面值的牌,y 代表两张相同牌面值的牌。
- 检查条件:对于每个组合 (x,y),检查是否满足以下条件:
- x×3+y×2≤max:五张牌的牌面值之和不超过最大值 max。
- c[x]≥3:牌面值为 x 的牌数量至少为 3。
- c[y]≥2:牌面值为 y 的牌数量至少为 2。
- x=y:三张相同牌面值的牌和两张相同牌面值的牌不能相同。
- 返回结果:如果找到符合条件的组合,返回 [x,y];否则返回 [0,0]。
复杂度分析
- 时间复杂度:O(n+k2),其中 n 是牌的数量,k 是牌面值的种类数(本题中 k=13)。首先需要 O(n) 的时间统计每种牌面值的数量,然后需要 O(k2) 的时间遍历所有可能的牌面值组合。
- 空间复杂度:O(k),主要用于存储每种牌面值的数量。
知识点扩展
- 哈希表:在本题中,使用
Counter
统计每种牌面值的数量,这是一种典型的哈希表应用。哈希表可以在 O(1) 的时间复杂度内完成插入和查找操作,非常适合用于统计和计数问题。 - 双层循环:通过双层循环遍历所有可能的牌面值组合,这是一种常见的暴力枚举方法。虽然时间复杂度较高,但在本题中由于牌面值种类数 k 较小,因此是可行的。
相关文章:
python解题之寻找最大的葫芦
问题描述 问题描述 在一场经典的德州扑克游戏中,有一种牌型叫做“葫芦”。“葫芦”由五张牌组成,其中包括三张相同牌面值的牌 �a 和另外两张相同牌面值的牌 �b。如果两个人同时拥有“葫芦”,我们会优先比较牌 &#…...
openwrt安装tailscale
1. 下载 进入tailscale的github仓库复制最新版本的链接:点击跳转 wget https://github.com/adyanth/openwrt-tailscale-enabler/releases/download/v1.36.1-fb2f6cf-autoupdate/openwrt-tailscale-enabler-v1.36.1-fb2f6cf-autoupdate.tgz2.解压缩 tar x -zvC / …...
基于物联网的智能插座云平台 WIFI云平台MQTT协议
功能介绍 功能描述: STM32单片机为控制核心 LCD1602液晶显示当前时间温度 开启时间 关闭时间 按键设置开启时间/关闭时间,温度报警上限 到开启时间,继电器自动打开,到关闭时间,自动关闭 通过DS18B20温度传感器获…...
MySQL 事务
概念介绍 事务就是一组DML语句组成,这些语句在逻辑上存在相关性,这一组 DML 语句要么全部成功,要么全部失败,是一个整体。MySQL 提供一种机制,保证我们达到这样的效果。 事务就是要做的或所做的事情,主要用…...
消息中间件面试题-参考回答
消息中间件面试题-参考回答 面试官:RabbitMQ-如何保证消息不丢失 候选人: 嗯!我们当时MYSQL和Redis的数据双写一致性就是采用RabbitMQ实现同步的,这里面就要求了消息的高可用性,我们要保证消息的不丢失。主要从三个层面…...
解决 MyBatis 中空字符串与数字比较引发的条件判断错误
问题复现 假设你在 MyBatis 的 XML 配置中使用了如下代码: <if test"isCollect ! null"><choose><when test"isCollect 1">AND exists(select 1 from file_table imgfile2 where task.IMAGE_SEQimgfile2.IMAGE_SEQ and im…...
【ETCD】【源码阅读】深入解析 etcd 的 `EtcdServer.Start` 函数
深入解析 etcd 的 EtcdServer.Start 函数 在 etcd 的代码中,EtcdServer.Start 是一个关键方法,用于初始化并启动服务器以便处理请求。本文将从源码的角度逐步分析此函数的每一步操作。 函数签名及注释 // Start performs any initialization of the Se…...
嵌入式驱动开发详解16(音频驱动开发)
文章目录 前言WM8960简介I2S协议接口说明 SAI音频接口简介驱动框架简介设备树配置内核使能声卡设置与测试 后续参考文献 前言 该专栏主要是讲解嵌入式相关的驱动开发,但是由于ALSA驱动框架过于复杂,实现音频编解码芯片的驱动不是一个人能完成的…...
【数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
目录😋 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二分查找的算法。 相关知识 为了完成本关任务,你需要掌握:1.根据键盘输入的一组有序数据建立顺序表,2.顺序表的输…...
探索云原生数据库 PolarDB
引言 在云计算时代,数据库的重要性不言而喻。随着企业数字化转型的加速,对数据库的性能、可靠性和灵活性的要求也越来越高。阿里云推出的云原生数据库 PolarDB,正是为了满足这些需求而设计的一款高性能、兼容性强、弹性灵活的关系型数据库产品。本文将详细介绍 PolarDB 的特…...
OGG FOR MYSQL同步DDL
以下实验测试OGG FOR mysql 同步DDL, OGG 21.3 MYSQL 8.0.27 --创建测试数据 create table oggddl_20241201 (oid int primary key ,oname varchar(10)); create table oggddl_20241202 (oid int primary key ,oname varchar(10)); create table oggddl_20241203…...
【CAN】asc报文格式文件合并(python版)
目录 一、简介二、合并asc格式报文1、准备多个asc文件2、根据时间合并asc文件3、结果 三、总结四、参考 一、简介 CAN通信:CAN(Controller Area Network)是一种多主方式的串行通讯总线。基本设计规范要求有高位速率、高抗电磁干扰性…...
C++之STL的map容器
map map的实现方式 set是一个有序的关联容器,是基于平衡二叉搜索树(红黑树)实现的,元素是有序的 map的用法 #include <iostream> #include <map> using namespace std;const int ADDSIZE 20; int main() {map<int, int> m;cout &…...
基于卷积神经网络的图像二分类检测模型训练与推理实现教程 | 幽络源
前言 对于本教程,说白了,就是期望能通过一个程序判断一张图片是否为某个物体,或者说判断一张图片是否为某个缺陷。因为本教程是针对二分类问题,因此主要处理 是 与 不是 的问题,比如我的模型是判断一张图片是否为苹果…...
react-dnd 拖拽事件与输入框的文本选中冲突
问题描述 当我们使用拖拽库的时候,往往会遇到拖拽的一个元素他的子孙元素有输入框类型的dom节点,当拖拽的事件绑定在该元素身上时候,发现子孙的输入框不能进行文本选中了,会按住鼠标去选中文本的时候会触发拖拽 实际的效果&…...
‘Close Project‘ is not available while IDEA is updating indexes的解决
XXX is not available while IDEA is updating indexes IDEA 1.Remove from Recent Projects 2.重新 Open工程即可...
如何解决samba服务器共享文件夹不能粘贴文件
sudo vim /etc/samba/smb.conf在samba的配置文件中增加一个选项 writable yes重启Samba服务以使更改生效: sudo service smbd restart...
Three.js入门-材质详解,构建视觉真实感的核心
Three.js 材质详解:构建视觉真实感的核心 Three.js 是一个强大的 3D JavaScript 库,它为开发者提供了丰富的工具来创建和渲染逼真的三维场景。在这些工具中,材质是一个非常重要的组成部分。材质定义了物体表面的外观特性,例如颜色…...
GitHub、Google等镜像加速地址收集
GitHub、Google等镜像加速地址收集 摘要 本文用于收集GitHub、Google等镜像/加速地址。 GitHub GitHub加速地址一览 fastgithub Https://www.fastgithub.com/(推荐) 站源地址缓存github.comwww.fastgithub.com无raw.githubusercontent.com无github.gi…...
五、网络层:控制平面,《计算机网络(自顶向下方法 第7版,James F.Kurose,Keith W.Ross)》
目录 一、导论 二、路由选择算法 2.1 路由(route)的概念 2.2 网络的图抽象 2.2.1 边和路由的代价 2.2.2 最优化原则 2.3 路由的原则 2.4 路由选择算法的分类 2.5 link state 算法 2.5.1 LS路由工作过程 2.5.2 链路状态路由选择(lin…...
Fix the “The repository no longer has a Release file” error on Ubuntu 23.04
背景信息 在Ubuntu 23.04操作系统上执行apt-get update命令更新操作系统时,得到以下错误 登录后复制 # apt-get update Ign:1 http://mirrors.aliyun.com/ubuntu lunar InRelease Ign:2 http://mirrors.aliyun.com/ubuntu lunar-updates InRelease Ign:3 http://mir…...
开源 AI 智能名片 S2B2C 商城小程序对私域流量运营的全方位助力
在当今竞争激烈的商业环境中,私域流量运营已成为企业实现可持续发展和提升竞争力的关键策略之一。开源 AI 智能名片 S2B2C 商城小程序凭借其独特的功能与特性,从多个维度为私域流量运营提供了强有力的支持与推动,以下将详细阐述其在各个方面的…...
Java Exception解决方法
Java中的Exception是所有异常的基类,它指的是程序在执行过程中发生的非严重错误,比如空指针异常、数组越界异常等。 为了解决Java中的Exception,从以下步骤进行排查解决: 阅读错误信息:查看异常的完整堆栈跟踪信息&a…...
HCIA-Access V2.5_2_2_2网络通信基础_IP编址与路由
网络层数据封装 首先IP地址封装在网络层,它用于标识一台网络设备,其中IP地址分为两个部分,网络地址和主机地址,通过我们采用点分十进制的形式进行表示。 IP地址分类 对IP地址而言,它细分为五类,A,B,C,D,E,…...
JeecgBoot passwordChange 任意用户密码重置漏洞复现
0x01 产品简介 Jeecg Boot是一个企业级低代码开发平台,基于前后端分离的架构,融合了SpringBoot、SpringCloud、Ant Design、Vue、Mybatis-plus、Shiro、JWT等多种主流技术,旨在帮助企业快速构建各种应用系统,提高开发效率,降低开发成本。采用最新主流的前后分离框架,使得…...
7-8 整型关键字的散列映射
给定一系列整型关键字和素数 p,用除留余数法定义的散列函数 H(key)key%p 将关键字映射到长度为 p 的散列表中。用线性探测法解决冲突。 输入格式: 输入第一行首先给出两个正整数 n(≤1000)和 p(≥n 的最小素数)&…...
谷粒商城—分布式高级①.md
1. ELASTICSEARCH 1、安装elastic search dokcer中安装elastic search (1)下载ealastic search和kibana docker pull elasticsearch:7.6.2 docker pull kibana:7.6.2(2)配置 mkdir -p /mydata/elasticsearch/config mkdir -p /mydata/elasticsearch/data echo "h…...
MySQL SQL语句性能优化
MySQL SQL语句性能优化指南 一、查询设计优化1. 避免 SELECT *2. 使用 WHERE 进行条件过滤3. 避免在索引列上使用函数和表达式4. 使用 LIMIT 限制返回行数5. 避免使用子查询6. 优化 JOIN 操作7. 避免全表扫描 二、索引优化1. 使用合适的索引2. 覆盖索引3. 索引选择性4. 多列索引…...
【潜意识Java】期末考试可能考的选择题(附带答案解析)
目录 选择题一:Java 数据类型 选择题二:Java 控制结构 选择题三:面向对象编程 选择题四:Java 集合框架 选择题五:Java 异常处理 选择题六:Java 方法 选择题七:Java 流程控制 选择题八&a…...
修炼之道 --- 其一
序言 大家对面试中的面经八股文是怎样的看法呢,从他的名字 八股文 就可以看出来大家可能并不喜欢他,八股文一般是 死板、浮于表面、不重实际 的特点。但是,我们需要通过辩证的角度来看待一个事情,不能单方面来定性! …...
【前端】HTML
目录 一、HTML结构 1.1 HTML标签1.2 HTML文件基本结构1.3 快速生成框架 二、HTML常见标签 2.1 注释标签 !-- –2.2 标题标签 h1到h62.3 段落标签 p2.4 换行标签 br2.5 格式化标签2.6 图片标签 img2.7 超链接标签 a 三、表格标签 3.1 常用标签3.2 合并单元格 四、列表标签五、表…...
LabVIEW实现GPS通信
目录 1、GPS通信原理 2、硬件环境部署 3、程序架构 4、前面板设计 5、程序框图设计 6、测试验证 本专栏以LabVIEW为开发平台,讲解物联网通信组网原理与开发方法,覆盖RS232、TCP、MQTT、蓝牙、Wi-Fi、NB-IoT等协议。 结合实际案例,展示如何利用LabVIEW和常用模块实现物联网系…...
【Python 小课堂】第 2 课 Python 基础知识:语句、常量、变量和注释
第 2 课 基础知识:语句、常量/变量和注释 By Yichen Li 2024/12/14 一、内容简介 在本次课中,介绍Python语句、常量/变量以及代码注释的基本概念,一些详细的概念、扩展及用法等细节,留至后续介绍。 二、Python语句 一般来说&…...
基于STM32设计的工地扬尘与噪音实时监测系统(网页)
一、前言 当前项目使用的相关软件工具、传感器源代码工程已经上传到网盘(实时更新项目内容):https://ccnr8sukk85n.feishu.cn/wiki/QjY8weDYHibqRYkFP2qcA9aGnvb?fromfrom_copylink 1.1 项目开发背景 近年来,随着城市化进程的…...
LLM之RAG实战(五十)| FastAPI:构建基于LLM的WEB接口界面
FastAPI是WEB UI接口,随着LLM的蓬勃发展,FastAPI的生态也迎来了新的机遇。本文将围绕FastAPI、OpenAI的API以及FastCRUD,来创建一个个性化的电子邮件写作助手,以展示如何结合这些技术来构建强大的应用程序。 下面我们开始分步骤操…...
JavaScript 中的 Map方法
JavaScript 中的 Map方法 在 JavaScript 中,Map 是一种用于存储键值对的数据结构,相较于传统的对象(Object),Map 提供了更高效的键值对操作方式适合处理需要频繁操作键值对的场景。 1. 创建 Map const map new Map…...
img引入svg如何修改颜色
方法1:通过css中filter:drop-shadow 首先需要一个容纳图标的父盒子(下方实例中的.svg-img),通过css造一个图标的‘影子’(.svg-color中的drop-shadow),然后设置‘影子’的颜色,再把图标本体移出父盒子&…...
自然语言处理基础及应用场景
自然语言处理定义 让计算机理解人所说的文本 语音 Imitation Game 图灵测试 行为主义 鸭子理论 自然语言处理的基本任务 词性标注:区分每个词名词、动词、形容词等词性命名实体的识别:名词的具体指代是哪一类事物共指消解:代词指代的是前面…...
构建centos docker基础镜像
1、介绍 比较老的版本docker镜像,不太好找,可以尝试自己构建 各版本构建基础镜像方法不太一样,方式也不同,自己尝试,本文只介绍了我自己的尝试 2、构建centos5.11 docker镜像 准备iso文件 (1)安…...
etcd命令大全
默认安装自带etcdctl 命令行客户端,分两个版本ETCDCTL_API2和ETCDCTL_API3,两个版本不一样,操作的数据也不相容。 本文以v3 为例。 使用之前需要先设置:export ETCDCTL_API3。 1 etcd查询集群节点列表及状态 标准输出࿱…...
Go有限状态机实现和实战
Go有限状态机实现和实战 有限状态机 什么是状态机 有限状态机(Finite State Machine, FSM)是一种用于建模系统行为的计算模型,它包含有限数量的状态,并通过事件或条件实现状态之间的转换。FSM的状态数量是有限的,因此称…...
使用torch模拟 BMM int8量化计算。
使用torch模型BMM int8计算。 模拟:BMM->softmax->BMM 计算流程 import torch import numpy as np torch.manual_seed(777) def int8_quantize_per_token(x: torch.Tensor, axis: int -1, attnsFalse):if x.dtype ! torch.float32:x x.type(torch.float32)…...
vue3的watch一次性监听多个值用法
vue3的watch一次性监听多个值 1、监听单个值 watch(() > route.params.keyword, (newValue, oldValue) > {console.log(监听值变化, newVal, oldVal)state.a newValue});2、监听多个值 watch(() > [route.params.id, route.params.keyword], (newValue, oldValue) &g…...
【one-api和ollama结合使用】
将Ollama接入one-api one-api是一个开源AI中间件服务,可以聚合各家大模型API,比如OpenAI、ChatGLM、文心一言等,聚合后提供统一的OpenAI调用方法。举个例子:ChatGLM和文心一言的API调用方法并不相同,one-api可以对其进…...
Oracle PDB的开启和关闭
[生产环境关闭与开启Oracle PDB] 【运维场景】 在运维Oracle PDB的时候经常要开启和关闭PDB,对关闭和开启PDB的操作要非常熟悉。 【操作方法】 1. PDB的打开与关闭 关闭和开启DB的时候要看DB的警告日志,日志位置(在Oracle用户下查看&…...
十一、动态构建UI元素
装饰器Builder 装饰器BuilderParam <font style"color:rgba(0, 0, 0, 0.9);">BuilderParam</font> 该装饰器用于声明任意UI描述的一个元素,类似slot占位符。 链接 简而言之:就是自定义组件允许外部传递 UI // SonCom 的实现略…...
智能时代的基石:神经网络
智能时代的基石:神经网络 第一节:神经网络简介 课程目标 本节课程旨在全面介绍神经网络的基本概念、结构以及其在历史发展中的重要里程碑。通过深入理解神经网络的工作原理和演变过程,学员将能够掌握神经网络在现实世界中的多种应用&#…...
VScode配置GIT
在Visual Studio Code(VSCode)中检测不到已安装的Git可以通过以下步骤来解决: 确认Git是否正确安装:首先,确保在计算机上正确安装了Git。可以通过打开命令行窗口并输入git --version来检查是否能够显示Git的版本…...
【CSS】css 如何实现固定宽高比
今天和同事讨论这个问题,一时间还想不到了,于是学习了下,就顺便当个记录吧 要在CSS中实现固定宽高比,有两种主要的方法可以选择。一种是使用新的aspect-ratio属性,另一种是利用padding技巧。随着现代浏览器对aspect-ra…...
使用webrtc-streamer查看实时监控
摄像头配置(海康摄像头为例) 摄像头视频编码应改成H264格式 webrtc-streamer下载 webrtc-streamer下载地址 下载后解压出来双击运行,端口默认8000 VUE2项目引入文件 在项目静态文件“public”中需引入两个js文件“webrtcstreamer.js”与“…...