013
游游的you__牛客网 (nowcoder.com)
题目：
题解：
组成一个you需要一个o且能得2分，而组成相邻字母oo需要两个o，只能得1分。优先考虑组成尽可能多的you，再考虑剩下的o，放一起。
#include <iostream>
using namespace std;
int main()
{
int q;
cin>>q;
while(q--)
{
int a,b,c;
cin>>a>>b>>c;
int x=min(min(a,b),c);
cout<<x*2+max(b-x-1,0)<<endl; //b-x==0时，刚好用完o
}
return 0;
}014
腐烂的苹果_牛客题霸_牛客网 (nowcoder.com)
题目：
题解：
多源bfs+最短路：将每层刚腐烂的的苹果放入队列中，同时用bool二维数组标记好，再找下一层，直到相邻没有完好的苹果为止。最后遍历一遍查看有没有没有标记的完好的苹果。
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int m,n;
bool vis[1100][1100];
int rotApple(vector<vector<int> >& grid)
{
//多源bfs
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())
{
int sz=q.size();
ret++;
while(sz--)
{
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<m && y>=0 && y<n && grid[x][y]==1 && !vis[x][y])
{
q.push({x,y});
vis[x][y]=true;
}
}
}
}
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;
}
};015
孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网 (nowcoder.com)
题目：
题解：
1.环形链表模拟：构建好环形链表后，沿着链表边遍历边删除节点。
2.递推/递归/动态规划
dp[i]表示：有i个孩子围成一圈时，最终剩下的孩子的编号是多少
每减少一个孩子时，同一编号对应的下标会改变，改变也是有规律的，也就是下标映射，根据下标映射，可得出状态转移方程。
//环形链表
class Solution {
public:
struct Node
{
int val;
Node* next;
Node(int x)
:val(x)
,next(nullptr)
{}
};
int LastRemaining_Solution(int n, int m)
{
Node* head=new Node(0);
Node* cur=head;
for(int i=1;i<n;i++)
{
cur->next=new Node(i);
cur=cur->next;
}
cur->next=head;
cur = head;
Node* prev = nullptr;
while (cur->next != cur) { // 至少还有两个人在环中
for (int i = 1; i < m; i++) { // 报数，找到第m个人
prev = cur;
cur = cur->next;
}
prev->next = cur->next; // 从环中删除出列的人
delete cur; // 释放内存
cur = prev->next; // 从下一个人开始报数
}
return cur->val;
delete cur; // 释放最后一个节点的内存
}
};
//动态规划
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
int f=0;
for(int i=2;i<=n;i++)
{
f=(f+m)%i;
}
return f;
}
};
