【C++笔试强训】如何成为算法糕手Day5

  

---

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台  

 循环渐进Forward-CSDN博客

---

目录

 循环渐进Forward-CSDN博客

第一题：游游的you

 思路：

第二题：腐烂的苹果

思路：

第三题：孩子们的游戏

思路：

---

第一题：游游的you

牛客网做题链接：游游的you__牛客网 (nowcoder.com)

 思路：

        这是一道简单的模拟题，我们要找出三个字符（y、o、u）中最少的那个字符的数量，这个数量n表示最多能组成多少个"you"。然后，我们计算o字符的总数减去n，得到剩余的o字符数量。如果剩余的o字符少于2个，那么就不需要进一步操作。如果剩余的o字符数量是2个或更多，我们可以在结果上加1（对于2个o），加2（对于3个o），以此类推。最终的结果是n加上剩余o字符数量减去1。

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

---

第二题：腐烂的苹果

牛客网做题链接：腐烂的苹果_牛客题霸_牛客网 (nowcoder.com)

思路：

这个问题可以通过广度优先搜索（BFS）来解决，因为我们需要以最短的时间传播腐烂的苹果。我们可以将每个腐烂的苹果看作是一个源点，然后从这些源点同时开始传播。

1. 初始化队列：

   • 创建一个队列，并将所有初始状态为腐烂的苹果的位置（坐标）加入到队列中。这些腐烂的苹果是腐烂过程开始的地方。

2. 广度优先搜索（BFS）：

   • 对队列中的每个元素（即腐烂的苹果位置）进行处理：
     • 检查该位置的四个直接邻居（上、下、左、右）。
     • 如果邻居是一个完好的苹果（通常用1表示），则将其状态更改为腐烂（例如，用2表示），并将该邻居的位置加入到队列中。
     • 确保每个位置只被加入队列一次，避免重复处理。

3. 记录时间：

   • 维护一个变量来记录传播的层数，这代表分钟数。
   • 每次从队列中取出一个元素进行处理时，层数加1。

4. 检查完好的苹果：

   • 当队列为空时，停止搜索。
   • 遍历整个网格，检查是否还有完好的苹果。
   • 如果发现还有完好的苹果，说明这些苹果无法被腐烂的苹果触及，因此返回-1。
   • 如果所有苹果都已经腐烂，返回记录的层数，即传播所需的总分钟数。

同时注意同一点不能重复入队列以及每次取front()都要对应pop()移除对头，否则会导致 内存超限 控制出队列的循环永无止境，从而程序超时判否。

class Solution {public:int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};queue<pair<int, int>> q;bool vis[1001][1001];int ret;void bfs(vector<vector<int> >& grid) {while (!q.empty()) {int sz = q.size();while (sz--) {auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {grid[x][y] = 2;q.push({x, y});}}}ret++;}}int rotApple(vector<vector<int> >& grid) {
// 第一次进去不算ret = -1;m = grid.size(), n = grid[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (grid[i][j] == 2) {q.push({i, j});}}bfs(grid);for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {return -1;}}return ret;}
};};

---

第三题：孩子们的游戏

牛客网做题链接：孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网 (nowcoder.com)

思路：

        一道约瑟夫环的应用版本（一样的思路）。

    public int LastRemaining_Solution (int n, int m) {//初始化模拟的列表List<Integer> list = new ArrayList();for(int i=0;i<n;i++){list.add(i);}int start = 0;//直到剩最后一个才返回while(list.size() !=1){int size = list.size();//计算每次要移除的坐标,就是//上一次的起始坐标start+这次数的新坐标m%size//再将这两个和取余%size,不然可能会超出size范围//最终减去1就是要移除的位置start = (start+m%size)%size-1;//需要考虑如果二者之和size如果相同的话,那么余数是0的特殊情况start = start<0?size-1:start;//移除后进行下一个循环list.remove(start);}//返回剩下的最后一个即可return list.get(0);}

---

 学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

---