【c++笔试强训】（第八篇）
目录
孩⼦们的游戏（约瑟夫环）
题目解析
1.题目链接：孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网
2.题目描述
描述
每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0... m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？
数据范围：1 \le n \le 50001≤n≤5000，1 \le m \le 100001≤m≤10000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
示例1
输入：
5,3
复制返回值：
3
复制
示例2
输入：
2,3
复制返回值：
1
复制说明：
有2个小朋友编号为0，1，第一次报数报到3的是0号小朋友，0号小朋友出圈，1号小朋友得到礼物
示例3
输入：
10,17
复制返回值：
2
讲解算法原理
解法：算法思路：
解法⼀：模拟。这⾥不多赘述，⽤数组或者链表模拟均可。但是数据量⼤的话会超时......
解法⼆：数学规律。通过画图，可以找到相邻两次删除坐标的规律。通过递推关系，求出剩下的最后⼀个数是哪个。讲解算法原理
编写代码
c++算法代码：
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;
}
};java算法代码：
import java.util.*;
public 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;
}
}
⼤数加法（⾼精度加法）
题目解析
1.题目链接：大数加法_牛客题霸_牛客网
2.题目描述
描述
以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
数据范围：s.length,t.length \le 100000s.length,t.length≤100000，字符串仅由'0'~‘9’构成
要求：时间复杂度 O(n)O(n)
示例1
输入：
"1","99"
复制返回值：
"100"
复制说明：
1+99=100
示例2
输入：
"114514",""
复制返回值：
"114514"
讲解算法原理
解法：
算法思路：
模版类型的算法题，模拟加法列竖式运算的过程即可。
编写代码
c++算法代码：
class Solution
{
public:
string solve(string s, string t)
{
string ret;
int tmp = 0; // 进位 + 本次累加和
int i = s.size() - 1, j = t.size() - 1;
while(i >= 0 || j >= 0 || tmp) // 模拟加法 {
if(i >= 0) tmp += s[i--] - '0';
if(j >= 0) tmp += t[j--] - '0';
ret += '0' + tmp % 10;
tmp /= 10;
}
reverse(ret.begin(), ret.end()); // 别忘逆序 return ret;
}
};java算法代码：
import java.util.*;
public class Solution
{
public String solve (String s, String t)
{
StringBuffer ret = new StringBuffer();
int tmp = 0; // 标记进位 + 本次累加的结果 int i = s.length() - 1, j = t.length() - 1;
while(i >= 0 || j >= 0 || tmp > 0) // 模拟加法 {
if(i >= 0) tmp += s.charAt(i--) - '0';
if(j >= 0) tmp += t.charAt(j--) - '0';
ret.append((char)('0' + tmp % 10));
tmp /= 10;
}
return ret.reverse().toString(); // 别忘逆序 }
}原文地址：https://blog.csdn.net/weixin_73861555/article/details/143794084
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！