数据结构与算法之贪心: LeetCode 649. Dota2 参议院 (Ts版)
Dota2 参议院
- https://leetcode.cn/problems/dota2-senate/
描述
-
Dota2 的世界里有两个阵营:Radiant(天辉)和 Dire(夜魇)
-
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中,每一位参议员都可以行使两项权利中的 一 项:
- 禁止一名参议员的权利:参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
- 宣布胜利:如果参议员发现有权利投票的参议员都是 同一个阵营的 ,他可以宣布胜利并决定在游戏中的有关变化
-
给你一个字符串 senate 代表每个参议员的阵营。字母 ‘R’ 和 'D’分别代表了 Radiant(天辉)和 Dire(夜魇)。然后,如果有 n 个参议员,给定字符串的大小将是 n
-
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过
-
假设每一位参议员都足够聪明,会为自己的政党做出最好的策略,你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 “Radiant” 或 “Dire”
示例 1
输入:senate = "RD"
输出:"Radiant"
解释:
第 1 轮时,第一个参议员来自 Radiant 阵营,他可以使用第一项权利让第二个参议员失去所有权利
这一轮中,第二个参议员将会被跳过,因为他的权利被禁止了
第 2 轮时,第一个参议员可以宣布胜利,因为他是唯一一个有投票权的人
示例 2
输入:senate = "RDD"
输出:"Dire"
解释:
第 1 轮时,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中,第二个来自 Dire 阵营的参议员会将被跳过,因为他的权利被禁止了。
这一轮中,第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
提示
- n == senate.length
- 1 <= n <= 1 0 4 10^4 104
- senate[i] 为 ‘R’ 或 ‘D’
Typescript 版算法实现
1 ) 方案1:贪心 + 「循环」队列
function predictPartyVictory(senate: string): string {const n = senate.length;const radiant = [], dire = [];for (const [i, ch] of Array.from(senate).entries()) {if (ch === 'R') {radiant.push(i);} else {dire.push(i);}}while (radiant.length && dire.length) {if (radiant[0] < dire[0]) {radiant.push(radiant[0] + n);} else {dire.push(dire[0] + n);}radiant.shift();dire.shift();}return radiant.length ? "Radiant" : "Dire";
};
2 ) 方案2:优化版
function predictPartyVictory(senate: string): string {const queue = senate.split('')const stack = []while (queue[0]) {const s = queue.shift()if (stack.length === 0 || stack[stack.length - 1] === s) {stack.push(s)continue;}queue.push(stack.pop())}return stack.pop() === 'R' ? "Radiant" : "Dire"
};
相关文章:
数据结构与算法之贪心: LeetCode 649. Dota2 参议院 (Ts版)
Dota2 参议院 https://leetcode.cn/problems/dota2-senate/ 描述 Dota2 的世界里有两个阵营:Radiant(天辉)和 Dire(夜魇) Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。…...
西藏酥油茶:高原上的醇香温暖
西藏酥油茶:高原上的醇香温暖 在西藏高原,有一种饮品,它不仅滋养了一代又一代的藏民,还承载着丰富的文化与历史,它就是西藏酥油茶。酥油茶,藏语称为“恰苏玛”,意为搅动的茶,是藏族人民日常生活中不可或缺的一部分,更是待客、祭祀等活动中的重要礼仪物品。 历史与文化渊源 酥…...
【模型】RNN模型详解
1. 模型架构 RNN(Recurrent Neural Network)是一种具有循环结构的神经网络,它能够处理序列数据。与传统的前馈神经网络不同,RNN通过将当前时刻的输出与前一时刻的状态(或隐藏层)作为输入传递到下一个时刻&…...
C++----STL(list)
介绍 list的数据结果是一个带头双向链表。 使用 有了前面string、vector的基础,后续关于list使用的讲解主要提及与string和vector的不同之处。 使用文档:cplusplus.com/reference/list/list/?kwlist 迭代器问题 insert以后迭代器不失效 #include…...
数据结构——AVL树的实现
Hello,大家好,这一篇博客我们来讲解一下数据结构中的AVL树这一部分的内容,AVL树属于是数据结构的一部分,顾名思义,AVL树是一棵特殊的搜索二叉树,我们接下来要讲的这篇博客是建立在了解搜索二叉树这个知识点…...
知识图谱在个性化推荐中的应用:赋能智能化未来
目录 前言1. 知识图谱的基本概念2. 个性化推荐的挑战与知识图谱的优势2.1 个性化推荐的主要挑战2.2 知识图谱在个性化推荐中的优势 3. 知识图谱赋能推荐系统的具体实现3.1 数据增强与关系建模3.2 嵌入技术的应用3.3 图神经网络(GNN)的应用3.4 多模态数据…...
C语言自定义数据类型详解(一)——结构体类型(上)
什么是自定义数据类型呢?顾名思义,就是我们用户自己定义和设置的类型。 在C语言中,我们的自定义数据类型一共有三种,它们分别是:结构体(struct),枚举(enum),联合(union)。接下来,我…...
使用 Tailwind CSS + PostCSS 实现响应式和可定制化的前端设计
随着前端开发框架和工具的不断更新,设计和样式的管理已经成为前端开发中的一项核心任务。传统的 CSS 编写方式往往让样式的复用和可维护性变得困难,而 Tailwind CSS 和 PostCSS 作为当下流行的工具,提供了强大的功能来简化开发过程࿰…...
巧用多目标识别能力,帮助应用实现智能化图片解析
为了提升用户体验,各类应用正通过融合人工智能技术,致力于提供更智能、更高效的服务。应用不仅能通过文字和语音的方式与用户互动,还能深入分析图片内容,为用户提供精准的解决方案。 在解析图片之前,应用首先需要准确识…...
算法中的移动窗帘——C++滑动窗口算法详解
1. 滑动窗口简介 滑动窗口是一种在算法中常用的技巧,主要用来处理具有连续性的子数组或子序列问题。通过滑动窗口,可以在一维数组或字符串上维护一个固定或可变长度的窗口,逐步移动窗口,避免重复计算,从而提升效率。常…...
AcWing 3585:三角形的边 ← sort() 函数
【题目来源】 给定三个已知长度的边,确定是否能够构成一个三角形,这是一个简单的几何问题。 我们都知道,这要求两边之和大于第三边。 实际上,并不需要检验所有三种可能,只需要计算最短的两个边长之和是否大于最大那个就…...
阿里云-银行核心系统转型之业务建模与技术建模
业务领域建模包括业务建模和技术建模,整体建模流程图如下: 业务建模包括业务流程建模和业务对象建模 业务流程建模:通过对业务流程现状分析,结合目标核心系统建设能力要求,参考行业建 模成果,形成结构化的…...
MySQL核心知识:春招面试数据库要点
在前文中,我们深入剖析了MyBatis这一优秀的持久层框架,了解了它如何实现SQL语句与Java对象的映射,以及其缓存机制等重要内容。而作为数据持久化的核心支撑,数据库的相关知识在Java开发中同样至关重要。MySQL作为最流行的开源关系型…...
Hive之加载csv格式数据到hive
场景: 今天接了一个需求,将测试环境的hive数据导入到正式环境中。但是不需要整个流程的迁移,只需要迁移ads表 解决方案: 拿到这个需求首先想到两个方案: 1、将数据通过insert into语句导出,然后运行脚本 …...
Java web与Java中的Servlet
一。前言 Java语言大多用于开发web系统的后端,也就是我们是的B/S架构。通过浏览器一个URL去访问系统的后端资源和逻辑。 当我在代码里看到这个类HttpServletRequest 时 让我想到了Servlet,Servlet看上去多么像是Java的一个普通类,但是它确实…...
kafka常用目录文件解析
文章目录 1、消息日志文件(.log)2、消费者偏移量文件(__consumer_offsets)3、偏移量索引文件(.index)4、时间索引文件( .timeindex)5、检查点引文件( .checkpoint&#x…...
RV1126+FFMPEG推流项目源码
源码在我的gitee上面,感兴趣的可以自行了解 nullhttps://gitee.com/x-lan/rv126-ffmpeg-streaming-projecthttps://gitee.com/x-lan/rv126-ffmpeg-streaming-project...
ANSYS SimAI
ANSYS SimAI 是 ANSYS 公司推出的一款基于人工智能(AI)的仿真解决方案,旨在通过机器学习技术加速仿真流程,降低计算资源需求,并为用户提供更高效的工程决策支持。其核心目标是简化复杂仿真过程,帮助工程师快…...
hedfs和hive数据迁移后校验脚本
先谈论校验方法,本人腾讯云大数据工程师。 1、hdfs的校验 这个通常就是distcp校验,hdfs通过distcp迁移到另一个集群,怎么校验你的对不对。 有人会说,默认会有校验CRC校验。我们关闭了,为什么关闭?全量迁…...
蓝桥杯单片机(八)定时器的基本原理与应用
模块训练: 当有长定时情况时,也就是定时长度超过65.5ms时,采用多次定时累加 一、定时器介绍 1.单片机的定时/计数器 2.定时器工作原理 3.定时器相关寄存器 二、定时器使用程序设计 1.程序设计思路 与写中断函数一样,先写一个初…...
基于FPGA的伺服驱动系统:电流环控制与多环路反馈、SVPWM及编码器协议实现的研究
伺服驱动FPGA电流环,包含坐标变换,电流环,速度环,位置环,电机反馈接口,SVPWM,编码器协议,电流环和编码器协议都是FPGA里实现的伺服驱动系统里玩FPGA可不是闹着玩的,尤其是…...
张量维度操控心法:从reshape到升维降维,吃透PyTorch形状操作的底层逻辑
✨ 张量维度操控心法:从reshape到升维降维,吃透PyTorch形状操作的底层逻辑🔐 张量形状操作的黄金法则:形状是视角,内容是本质🔧 reshape函数:零侵入的形状重塑神器核心原理与执行规则实操代码与…...
显卡驱动彻底清理指南:用DDU解决90%的显示问题
显卡驱动彻底清理指南:用DDU解决90%的显示问题 【免费下载链接】display-drivers-uninstaller Display Driver Uninstaller (DDU) a driver removal utility / cleaner utility 项目地址: https://gitcode.com/gh_mirrors/di/display-drivers-uninstaller 当…...
Pixel Aurora Engine效果展示:青蓝+明黄配色系像素画作视觉冲击力解析
Pixel Aurora Engine效果展示:青蓝明黄配色系像素画作视觉冲击力解析 1. 视觉震撼力解析 Pixel Aurora Engine通过精心设计的青蓝明黄配色方案,创造出极具视觉冲击力的像素艺术作品。这种色彩组合源自经典16位游戏的美学理念,但通过现代AI技…...
SAP移动类型全解析:从收货到移库,一文搞懂库存管理核心配置
SAP移动类型实战指南:解锁库存管理的核心密码 当你第一次在SAP系统中执行货物移动时,面对上百种移动类型代码,是否感到无从下手?作为全球500强企业广泛采用的ERP系统,SAP的库存管理模块以其严谨性和灵活性著称…...
ZYNQ PS侧DDR3内存配置避坑指南:以ACZ702开发板为例,手把手教你搞定MT41K128M16
ZYNQ PS侧DDR3内存配置实战:从硬件原理到Vivado参数设置全解析 当你第一次拿到ACZ702这样的ZYNQ开发板,准备配置PS侧的DDR3内存时,是否遇到过这样的困惑:为什么在Vivado中找不到DDR管脚约束选项?为什么按照传统FPGA的D…...
Anaconda虚拟环境管理:为春联生成模型创建独立Python空间
Anaconda虚拟环境管理:为春联生成模型创建独立Python空间 你是不是也遇到过这种情况?电脑上装了好几个Python项目,有的需要TensorFlow 2.0,有的却只能用TensorFlow 1.x,结果为了运行一个项目,把整个系统的…...
【Python内存管理终极指南】:20年专家实测5大智能策略,90%开发者忽略的GC优化盲区揭晓
第一章:Python智能体内存管理策略对比评测报告全景概览本报告聚焦于当前主流Python智能体(Agent)框架在内存管理层面的设计差异与运行表现,涵盖LangChain、LlamaIndex、AutoGen及自研轻量Agent Runtime四大实现。评测维度包括对象…...
4个核心功能实现智能散热:FanControl个性化温控指南
4个核心功能实现智能散热:FanControl个性化温控指南 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcode.com/GitHub_Trending/fa/F…...
避坑指南:UGUI项目中使用SpriteAtlas的5个致命错误(附解决方案)
UGUI项目中使用SpriteAtlas的5个致命错误与实战解决方案 在Unity UI开发中,SpriteAtlas作为性能优化的利器,能够显著减少DrawCall并优化内存使用。然而,许多开发者在实际项目中往往会踩中一些"坑",导致性能不升反降&…...
