程序员面试金典——番外篇之约瑟夫问题2

参考网址：https://www.nowcoder.com/profile/9270572/codeBookDetail?submissionId=15779150

Solution1：

解题思路：在c++中利用vector来做
1. 每一轮报数完毕之后，将vector尾部节点复制到首部同时删除尾部结点，开始新一轮的报数。
2. vector中仅剩一个节点，程序结束。
3. 举个例子：假设n = 24，第一个人编号为1。
（1）第一轮：依次报1，2，1，2…然后报到2的人出局，则第一轮过后未出局的编号为1、3、5、7、9、11、13、15、17、19、21、23；
（2）第二轮：从上一轮最后一个报数的人开始依次报1，2，3，1，2，3…报到2，3的人出局。我这里做的处理是，先将上一轮最后一个报数的编号移动到最前面，即23、1、3、5、7、9、11、13、15、17、19、21；然后开始第二轮报数，未出局的编号为23、5、11、17；
（3）第三轮：从上一轮最后一个报数的人开始依次报1，2，3，4，1，2，3，4…报到2，3，4的人出局。同样，我这里做的处理是，先将上一轮最后一个报数的编号移动到最前面，即17、23、5、11；然后开始第三轮报数，未出局的编号为17，此时链表中仅剩一个节点，故程序结束。
PS：这思路是真好，菜鸡啥时候长大

class Joseph {
public:
int getResult(int n) {
// write code here
vector<int> ysf;
for (int i = 1; i <= n; i++)
ysf.push_back(i);
int m = 2;
vector<int> temp;
while (ysf.size() != 1) {
temp.push_back(0);
for (size_t i = 1; i <= ysf.size(); i += m) {
temp.push_back(ysf[i - 1]);
}
temp[0] = temp.back();
temp.erase(temp.end() - 1);
ysf.swap(temp);//swap函数的两种用法均可
//swap(ysf, temp);
temp.clear();
m++;
}
return ysf.back();
}
};

vector中swap函数的用法

《C++ Primer》第五版P303中写到：swap操作交换两个相同类型容器的内容。调用swap后，两个容器中的元素会交换。
除此之外，可以利用swap对vector的内存进行强制释放

template < class T> void ClearVector( vector<T>& v )
{
vector<T>vtTemp;
vtTemp.swap( v );
}
如
vector<int> v ;
nums.push_back(1);
nums.push_back(3);
nums.push_back(2);
nums.push_back(4);
vector<int>().swap(v);
/* 或者v.swap(vector<int>()); */
/*或者{ std::vector<int> tmp = v;
v.swap(tmp);
}; //加大括号{ }是让tmp退出{ }时自动析构*/

参考：
一个关于c++中vector函数各种用法总结的博客：C++中 vector（容器）的用法
https://www.cnblogs.com/yoke/p/6080080.html

最后

以上就是明亮荷花为你收集整理的程序员面试金典——番外篇之约瑟夫问题2程序员面试金典——番外篇之约瑟夫问题2的全部内容，希望文章能够帮你解决程序员面试金典——番外篇之约瑟夫问题2程序员面试金典——番外篇之约瑟夫问题2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。