刷题强训(day05) -- 游游的you、腐烂的苹果、孩子们的游戏(圆圈中最后剩下的数)

目录

1、游游的you

1.1 题目

1.2 思路

1.3 代码实现

2、腐烂的苹果

2.1 题目

2.2 思路

2.3 代码实现

3、孩子们的游戏(圆圈中最后剩下的数)

3.1 题目

3.2 思路

 3.3 代码实现

3.3.1 环形链表

​编辑3.3.2 动态规划

​编辑


1、游游的you

1.1 题目

1.2 思路

根据题目得知,首先要you的次数最多,再去拼接oo,注意oo是1分,ooo是2分,oooo是3分,所以oo的分数为b-;you的个数是a,b,c中的最小值,所以我们先拼出you,同时消耗b,所以oo的分数就时b减去you的个数在减去1;

理清思路,接下来就是代码实现。

1.3 代码实现

#include <iostream>
using namespace std;int main() 
{int q = 0;cin >> q;int a,b,c;while(q--){cin >> a >> b >> c;int you = min(a,min(b,c));int oo = max(b-you-1,0);cout << you*2+oo << endl;}return 0;
}

2、腐烂的苹果

2.1 题目

2.2 思路

这是一道考察多源BFS+最短路的题目,0,1,2分别表示空格,好苹果,坏苹果,坏苹果每分钟回向上下左右四个方向扩散(这里可以理解为搜索),找到好苹果则传染为坏的,因为这里是一圈一圈的扩散,所以能想到用多源BFS。

我们先遍历一遍矩阵,把所有坏苹果放入到一个队列中,就可以实现每次出队列就可同时操作多个坏苹果,用一个变量count记录一下坏苹果的传播次数,传播到0则不管,传播到1则把1置为2,或标记为已传播,然后把这个被标记的苹果放到对列中。遍历传播结束后,在遍历一遍矩阵是否还有好苹果,有则返回-1,否则返回count。

2.3 代码实现

注意遍历结束后,还要判断矩阵中是否还有好苹果,这时候相当于多扩散了一次,所以要输出count - 1。

class Solution 
{int m,n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[1001][1001] = {0};
public:int rotApple(vector<vector<int> >& grid) {n = grid.size(),m = grid[0].size();queue<pair<int,int>> q; //用pair存放坏苹果的行和列for(int i = 0;i < n;i++)for(int j = 0;j < m;j++)if(grid[i][j]==2)q.push({i,j});int count = 0;while(q.size()){count++;int qs = q.size();while(qs--){auto [a,b] = q.front();//拿出队头元素q.pop();for(int i =0 ;i< 4;i++){int x = a + dx[i],y= b + dy[i];//边界控制,防止出界且好苹果未被标记if(x>=0 && x<n && y >= 0 && y < m && grid[x][y] == 1 && !vis[x][y]){vis[x][y] = true;q.push({x,y});}}}}for(int i = 0;i < n;i++){for(int j = 0;j< m;j++){if(grid[i][j] == 1 && !vis[i][j])return -1;}}return count-1;}
};

 

3、孩子们的游戏(圆圈中最后剩下的数)

3.1 题目

3.2 思路

这是一个约瑟夫环问题,我们可以用环形链表模拟来实现或者用动态规划来解决

 3.3 代码实现

3.3.1 环形链表

class Solution 
{
public:int LastRemaining_Solution(int n, int m) {list<int> lt;for(int i = 0;i < n;i++)lt.push_back(i);auto it  = lt.begin();while(lt.size()>1){for(int i = 1; i <  m;i++){++it;//当走到尾部的时候,让it在走到链表的头,形成环if(it == lt.end())it = lt.begin();}//erase删除后自动指向下一个节点it = lt.erase(it);if(it == lt.end())it = lt.begin();}return *it;}
};

3.3.2 动态规划

class Solution 
{
public:int LastRemaining_Solution(int n, int m) {   // int dp[5001];// dp[1] = 0;// for(int i = 2;i <= n;i++)//     dp[i] = (dp[i-1]+m) % i;// return dp[n];//优化一下空间,用一个变量代dp,因为我们仅用dp[i-1]的值int f = 0;for(int i = 2;i <=n;i++)f = (f+m) % i;return f;}
};


本篇完,下篇见!如有问题,欢迎在评论区指导!

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PyQt5超详细教程终篇

PyQt5超详细教程 前言 接&#xff1a; [【Python篇】PyQt5 超详细教程——由入门到精通&#xff08;序篇&#xff09;](【Python篇】PyQt5 超详细教程——由入门到精通&#xff08;序篇&#xff09;-CSDN博客) 建议把代码复制到pycahrm等IDE上面看实际效果&#xff0c;方便理…

并查集算法实现

模板 模板分为三大部分 初始化查询i的祖先合并i j(使他们祖先成为一个人) // 1 初始化 void init(int n) {for (int i 1; i < n; i)fa[i] i;//将该数的父节点定义为该数 }// 2 查询i的祖先 int find(int i) {if (i fa[i])return i;else{![查](../pic/并查集.png)fa[i]…

(实战)WebApi第13讲:怎么把不同表里的东西,包括同一个表里面不同的列设置成不同的实体,所有的给整合到一起?【前端+后端】、前端中点击标签后在界面中显示

一、实现全局跨域&#xff1a;新建一个Controller&#xff0c;其它的controller都继承它 1、新建BaseController 2、在后端配置&#xff0c;此处省略【详情见第12讲四、3、】 3、其它的控制器继承BaseController&#xff0c;这个时候就能够完成全局的跨域 【向后台传cookie和…

【计算机基础——数据结构——红黑树】

1. 红黑树&#xff08;RBTree&#xff09; 为什么HashMap不直接使用AVL树&#xff0c;而是选择了红黑树呢&#xff1f; 由于AVL树必须保证左右子树平衡&#xff0c;Max(最大树高-最小树高) < 1&#xff0c;所以在插入的时候很容易出现不平衡的情况&#xff0c;一旦这样&…

【MatLab手记】 --从0到了解超超超详过程!!!

文章目录 MatLab笔记一、命令行窗口二、变量命名规则三、数据类型1. 数字2. 字符与字符串3. 矩阵3.1 矩阵创建3.2 矩阵的修改和删除3.3 矩阵的拼接与重构重排3.4 矩阵的运算方法3.5 矩阵的下标 4. 元胞数组&#xff08;类似数据容器&#xff09;5. 结构体 四、逻辑与流程控制五…

Qt_day5_常用类

常用类 目录 1. QString 字符串类&#xff08;掌握&#xff09; 2. 容器类&#xff08;掌握&#xff09; 2.1 顺序容器QList 2.2 关联容器QMap 3. 几种Qt数据类型&#xff08;熟悉&#xff09; 3.1 跨平台数据类型 3.2 QVariant 统一数据类型 3.3 QStringList 字符串列表 4. QD…

【THM】linux取证 DisGruntled

目录 0x00 房间介绍 0x01 连接并简单排查 0x02 让我们看看做没做坏事 0x03 炸弹已埋下。但何时何地&#xff1f; 0x04 收尾 0x05 结论 0x00 房间介绍 嘿&#xff0c;孩子&#xff01;太好了&#xff0c;你来了&#xff01; 不知道您是否看过这则新闻&#xff0c;我…

MFC中Excel的导入以及使用步骤

参考地址 在需要对EXCEL表进行操作的类中添加以下头文件&#xff1a;若出现大量错误将其放入stdafx.h中 #include "resource.h" // 主符号 #include "CWorkbook.h" //单个工作簿 #include "CRange.h" //区域类&#xff0c;对Excel大…

智能化温室大棚控制系统设计(论文+源码)

1 系统的功能及方案设计 本次智能化温室大棚控制系统的设计其系统整体结构如图2.1所示&#xff0c;整个系统在器件上包括了主控制器STC89C52&#xff0c;温湿度传感器DHT11&#xff0c;LCD1602液晶&#xff0c;继电器&#xff0c;CO2传感器&#xff0c;光敏电阻&#xff0c;按…

一篇文章教会你使用Linux的‘sed‘基础命令

Linux sed 命令详解 Linux sed 命令详解1、基本语法2、常用命令2.1 替换2.2 删除行2.3 查找并打印行2.4 插入与追加2.5 多命令组合 3、高级用法3.1 替换并保存结果到新文件3.2 在范围内替换3.3 正则表达式匹配 4、小结 Linux sed 命令详解 sed 是 Linux 系统中非常强大的流编辑…

集群化消息服务解决方案

目录 集群化消息服务解决方案项目概述架构图使用说明服务端通过API接口推送消息给客户端调用方式 请求参数返回参数 客户端推送消息连接websocket或发送消息 接收消息项目地址作者信息 集群化消息服务解决方案 项目概述 集群化消息服务解决方案是一种用于处理大量消息的高可用…

elementUI 点击弹出时间 date-picker

elementUI的日期组件&#xff0c;有完整的UI样式及弹窗&#xff0c;但是我的页面不要它的UI样式&#xff0c;点击的时候却要弹出类似的日期选择器&#xff0c;那怎么办呢&#xff1f; 以下是elementUI自带的UI风格&#xff0c;一定要一个输入框来触发。 这是我的项目中要用到的…

【go从零单排】go中的三种数据类型array、slices、maps

Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 array数组 package mainimport "fmt"func main() {var a [5]int //var关键字定义数组&#xff0c;[5]表…

科技改变阅读习惯:最新研究揭示电子阅读器的普及趋势

据QYResearch调研团队最新报告“全球电子阅读器市场报告2023-2029”显示&#xff0c;预计2029年全球电子阅读器市场规模将达到6.9亿美元&#xff0c;未来几年年复合增长率CAGR为0.4%。 如上图表/数据&#xff0c;摘自QYResearch最新报告“全球电子阅读器市场研究报告2023-2029.…

解决 VSCode 中 C/C++ 编码乱码问题的两种方法

解决 VSCode 中 C/C 编码乱码问题的两种方法 在中国地区&#xff0c;Windows 系统中的 cmd 和 PowerShell 默认编码是 GBK&#xff0c;但 VSCode 默认使用 UTF-8 编码。这种编码不一致会导致在 VSCode 终端中运行 C/C 程序时出现乱码。以下介绍两种方法来解决这一问题。 方法…

UE5遇到问题记录

问题描述&#xff1a; 在让敌人自动追踪玩家的时候一开始运行就会播放攻击的动画 解决方法&#xff1a; 这样是因为敌人一开始就检测到自己了&#xff0c;所以触发动画。 方式一&#xff1a;加一个条件 方式二&#xff1a;改一下碰撞预设

内网对抗-信息收集篇SPN扫描DC定位角色区域定性服务探针安全防护凭据获取

知识点&#xff1a; 1、信息收集篇-网络架构-出网&角色&服务&成员 2、信息收集篇-安全防护-杀毒&防火墙&流量监控 3、信息收集篇-密码凭据-系统&工具&网站&网络域渗透的信息收集&#xff1a; 在攻防演练中&#xff0c;当完成边界突破后进入内…

基于Matlab 疲劳驾驶检测

Matlab 疲劳驾驶检测 课题介绍 该课题为基于眼部和嘴部的疲劳驾驶检测。带有一个人机交互界面GUI&#xff0c;通过输入视频&#xff0c;分帧&#xff0c;定位眼睛和嘴巴&#xff0c;通过眼睛和嘴巴的张合度&#xff0c;来判别是否疲劳。 二、操作步骤 第一步&#xff1a;最…

11.11 代码块

一 java 1.代码块 1&#xff09; 理解 使用构造器时&#xff1a;先默认 调用代码块内容 再调用 构造器内容【代码块 > 构造器】 1.1 细节 1&#xff09;静态代码块 只能加载一次 2&#xff09;先调用父类代码块 再子类代码块 3&#xff09;静态代码块是随着类加载而执行…

在gitlab,把新分支替换成master分支

1、备份master分支&#xff0c;可以打tag 2、删除master分支 正常情况下&#xff0c;master分支不允许删除&#xff0c;需要做两个操作才能删除 a、变更项目默认分支为非master分支&#xff0c;可以先随便选择 b、取消master为非保护分支 操作了上述两步&#xff0c;就可以删…