有什么可以下载软件的网站,中国教育网站官网,wordpress如何发照片,百度网址安全中心面试题45#xff1a;圆圈中最后剩下的数字 题目#xff1a;0,1,…,n-1这n个数字排成一个圆圈#xff0c;从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
❖ 经典的解法#xff0c;用环形链表模拟圆圈
代码如下:
#include iostream圆圈中最后剩下的数字 题目0,1,…,n-1这n个数字排成一个圆圈从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
❖ 经典的解法用环形链表模拟圆圈
代码如下:
#include iostream
#include list
using namespace std;int LastRemaining(unsigned int n, unsigned int m)
{if (n 1 || m 1) return -1;listintnumbers;for (int i 0; i n; i)numbers.push_back(i);listint::iterator current numbers.begin();while (numbers.size() 1){for (int i 1; i m; i){current;if (current numbers.end()) current numbers.begin();}listint::iterator next current;if (next numbers.end()) next numbers.begin();--current;numbers.erase(current);current next;}return *(current);
}❖ 创新的解法拿到Offer不在话下
代码如下:
#include iostream
using namespace std;int josephus(int n, int m)
{if (n 1) return 0;else return (josephus(n - 1, m) m) % n;
}测试用例 ● 功能测试输入的m小于n比如从最初有5个数字的圆圈删除每次第2、3个数字输入的m大于或者等于n比如从最初有6个数字的圆圈删除每次第6、7个数字。 ● 特殊输入测试圆圈中有0个数字。 ● 性能测试从最初有4000个数字的圆圈中每次删除第997个数字。 本题考点 ● 考查抽象建模的能力。不管应聘者是用环形链表来模拟圆圈还是分析被删除数字的规律都要深刻理解这个问题的特点并编程实现自己的解决方案。 ● 考查对环形链表的理解及应用能力。大部分面试官只要求应聘者基于环形链表的方法解决这个问题。 ● 考查数学功底及逻辑思维能力。少数对算法和数学基础要求很高的公司面试官会要求应聘者不能使用 On的辅助内存这个时候应聘者就只能静下心来一步步推导出每次删除的数字有哪些规律。
