您的位置:首页 > 游戏 > 手游 > 沈阳最新数据消息_网页开发软件哪个好用_观看b站的广告网站平台_湖南网站建设推广优化

沈阳最新数据消息_网页开发软件哪个好用_观看b站的广告网站平台_湖南网站建设推广优化

2025/3/18 18:32:54 来源:https://blog.csdn.net/LH__1314/article/details/146271198  浏览:    关键词:沈阳最新数据消息_网页开发软件哪个好用_观看b站的广告网站平台_湖南网站建设推广优化
沈阳最新数据消息_网页开发软件哪个好用_观看b站的广告网站平台_湖南网站建设推广优化

刷题day_5

一、游游的you

题目链接:游游的you

题目解析

在这里插入图片描述

题目要求:

输入abc表示you三个字母的个数;

将这些字母连成字符串,并且这里you三个字母相邻获得2分,两个o字母相邻获得1分。

让我们输出最多可以获得多少分

这里得分规则我们需要注意

  • you相邻获得2
  • oo相邻获得1分,如果字符ooo可以获得2分,oooo可以获得3

算法思路

我们知道了这个得分规则,我们想要获得更高的分数:

  1. 尽可能的让you相邻
  2. 如果不能组成you,则就让所有的o相邻

这样我们就可以知道如何去求最大得分了,

  • 首先就是you的个数(就等于abc中最小的那一个)
  • 然后就是剩余o的个数,让剩余所有的o相邻得分就是o的个数-1;

这样最多的得分就可以表示出来了;

这里需要注意剩余o的个数可能为0,这时就需要处理一下,否则就加了-1

代码实现

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

二、腐烂的苹果

题目链接:腐烂的苹果

题目解析

在这里插入图片描述

题目:

有一个m*n的网格,其中每一个格子有三种情况(没有苹果/0有好的苹果/1有腐烂的苹果/2)

其中,腐烂的苹果每分钟都会向四周(上下左右)传播病菌,相邻的苹果都会腐烂。

让我们求出需要多少分钟,会导致所有的苹果变腐烂;(如果有苹果一直不会腐烂,就返回-1

算法思路

读懂了题目,现在来看如何去实现这个算法(这里简述一下)

这道题的标签是BFS广度优先遍历

所以,这里先遍历给的数组,让所有的2(腐烂的苹果)都存放到一个队列当中;

再进行广度优先遍历,对队列中腐败的苹果进行扩散

这里注意:题目要求出时间,所有我们要按时间来进行

BFS遍历,什么意思呢?

在这里插入图片描述

这里就来捋一捋整个代码的流程

首先准备工作,定义dx[4]dy[4]表示上下左右位置下标变化值;定义vis数组来表示每个位置苹果是否腐烂(true表示腐败`);

  • 遍历grid,将所有值为2的位置的下标入队列;
  • 进行BFS广度优先遍历,进行腐烂的扩散操作;
  • 扩散过程:依次对队列中的每个下标进行上下左右扩散,如果扩散位置不越界,并且扩散位置有苹果且苹果吗,没有被传入腐败,那就修改扩散位置的vis[x][y]true,并让扩散位置下标入队列。
  • 最后,遍历grid数组,如果存在一个位置有苹果且苹果没有被传染腐败,就返回-1否则返回ret-1结果。

代码实现

class Solution {
public:int m,n;int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};bool vis[1001][1001] = {false}; //表示苹果是否腐烂int rotApple(vector<vector<int> >& grid) {// write code herem = grid.size();n = grid[0].size();queue<pair<int,int>> q;//用来存放腐烂苹果的下标for(int i=0;i<m;i++){for(int j = 0;j<n;j++){if(grid[i][j] ==2)q.push({i,j});}}int ret = 0;while(q.size()){ret++;//每加依次,表示过了一分钟int sz = q.size();//记录当前q在腐烂苹果的个数while(sz--)// 循环sz次,表示这一分钟有多少个腐烂苹果会扩散{auto [a,b] = q.front();//记录下标q.pop();//删除整个位置,表示已经扩散过了for(int i=0;i<4;i++){int x = a + dx[i];int y = b + dy[i];//如果扩散位置不越界,扩散位置有苹果且苹果没有腐烂if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == 1 && !vis[x][y]){vis[x][y] = true;//标记苹果腐烂q.push({x,y});//插入到q中}}}}for(int i=0;i<m;i++){for(int j = 0;j<n;j++){if(grid[i][j] == 1 && !vis[i][j])return -1;}}return ret-1;}
};

三、孩子们的游戏

题目链接:孩子们的游戏

题目描述

在这里插入图片描述

这是一道经典的约瑟夫问题,对于约瑟夫,可是早有耳闻;这里就直接提供思路

这里大致可以将所有的思路/解法分为两种

  • 模拟实现
  • 使用递推/递归/动态规划

为什么可以分为两种呢?

第一种就是模拟实现整个过程,可以说是暴力解法了

第二种它们都有一个共同的思路,就是将问题一步一步划分,然后寻找子问题的关系;从而简化整个过程。

算法分析

这里对于两种思路来简单分析一下:

首先模拟实现整个过程

我们可以使用链表或者数组来模拟整个过程。(这里使用数组来模拟)

  • 我们定义一个数组(bool类型的),来表示当前位置下标对应的人还是否在圈内
  • 定义用来计数的一些变量i表示当前遍历位置的下标、sum表示圈内剩余的人数、x表示当前应该报的数
  • 循环遍历整个数组,如果遍历遇到当前位置对应的人不在圈内v[i] == 0,就i++并直接执行下一次循环
  • 如果当前位置的人在圈内,就继续判断报数是否等于m-1x == m-1,如果等于将让当前位置的人出圈,再继续执行循环遍历
  • 知道圈内剩余一个人sum == 1,循环结束,最后返回剩余那个人的下标即可。

其次,第二种思路就说动态规划

这种思路主要就在于理清楚dp[i]代表了什么、和dp[i]状态转移方程

  • 这里dp[i]代表当有i个人时最后剩余的那个人

在这里插入图片描述

如上图所示,我们找到了第一次报圈和第二次报圈对应下标的关系dp[n] = (dp[n-1] + n) %b

我们将dp[i]表示有i个人报圈最后胜出的人,那么dp[0] = 0;那i=2时;dp[2] = (dp[1] +m) %n

以此类推,我们就可以直接推出来有n个人报圈时,最后胜出的人。

代码实现

第一种:

class Solution {public:int LastRemaining_Solution(int n, int m) {//数组来模拟vector<int> vp(n, 1);int x = 0, sum = n;//x表示报数,sum表示剩余人数int i = 0;while (sum > 1) {if (vp[i] == 0) {i++;i %= n;continue;}if (x == m - 1) {sum--;x++;x %= m;vp[i] = 0;} else {x++;}i++;i %= n;}int ret = 0;for (int i = 0; i < n; i++) {if (vp[i] == 1) {ret = i;break;}}return ret;}
};

第二种:

class Solution {
public:int LastRemaining_Solution(int n, int m) {int f = 0;for(int i=1;i<=n;i++)  f = (f+m) % i;return f;}
};

今天题目有点难度,继续加油!!!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com