题解 | #孩子们的游戏(圆圈中最后剩下的数)#
孩子们的游戏(圆圈中最后剩下的数)
http://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6
第七十六题
方法一：模拟出这个圈，然后遍历和删除
class Solution {
public:
int LastRemaining_Solution(int n, int m) {
// 数据结构中就说过 好像叫约瑟夫环
// 方法1，模拟循环下去，每三个人干掉一个
vector<int> circle;
for(int i=0;i<n;i++)
circle.push_back(i);
int now=0;
while(n>1){
public:
int LastRemaining_Solution(int n, int m) {
// 数据结构中就说过 好像叫约瑟夫环
// 方法1，模拟循环下去，每三个人干掉一个
vector<int> circle;
for(int i=0;i<n;i++)
circle.push_back(i);
int now=0;
while(n>1){
// 循环队列
now=(now+m-1)%n;
circle.erase(circle.begin()+now);
n--;
}
return circle[0];
}
};
now=(now+m-1)%n;
circle.erase(circle.begin()+now);
n--;
}
return circle[0];
}
};
方法2：上网找原理讲解吧
class Solution {
public:
int LastRemaining_Solution(int n, int m) {
// 数据结构中就说过 好像叫约瑟夫环
// 方法2 正经的约瑟夫环的算法
return f(n,m);
}
// 递归调用求解
int f(int n,int m)
{
if(n == 1)
return 0;
else
return (f(n-1,m) + m) % n;
}
};
public:
int LastRemaining_Solution(int n, int m) {
// 数据结构中就说过 好像叫约瑟夫环
// 方法2 正经的约瑟夫环的算法
return f(n,m);
}
// 递归调用求解
int f(int n,int m)
{
if(n == 1)
return 0;
else
return (f(n-1,m) + m) % n;
}
};
题解 文章被收录于专栏
一遍做剑指offer 一边保存做题步骤 并附带详细注释哦
投递完美世界等公司10个岗位 >
