刷题day_5
一、游游的you
题目链接:游游的you
题目解析
题目要求:
输入
a
,b
,c
表示y
、o
、u
三个字母的个数;将这些字母连成字符串,并且这里
you
三个字母相邻获得2
分,两个o
字母相邻获得1
分。让我们输出最多可以获得多少分
这里得分规则我们需要注意
you
相邻获得2
分oo
相邻获得1
分,如果字符ooo
可以获得2
分,oooo
可以获得3
分
算法思路
我们知道了这个得分规则,我们想要获得更高的分数:
- 尽可能的让
you
相邻- 如果不能组成
you
,则就让所有的o
相邻这样我们就可以知道如何去求最大得分了,
- 首先就是
you
的个数(就等于a
、b
、c
中最小的那一个)- 然后就是剩余
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 here
m = 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-1
x == 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;
}
};
今天题目有点难度,继续加油!!!