刷题强训(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;}
};