题解 | #孩子们的游戏(圆圈中最后剩下的数)#
孩子们的游戏(圆圈中最后剩下的数)
https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6
class Solution {
public:
struct Node{
int data;
Node* next;
Node(int x):data(x), next(nullptr){}
};
// 看着题目，套用链表属性
int LastRemaining_Solution(int n, int m) {
// write code here
Node* head = new Node(0);
Node* cur;
cur = head;
for(int i = 1; i < n; ++i)
{
Node* tmp = new Node(i);
cur->next = tmp;
cur = cur->next;
}
cur->next = head;// 构成一个环
Node* pre = cur;
Node* now = head;
// std::cout << " head : " << now->data << std::endl;
while (now->next!= now) // 环判断链表元素个数是否为1
{
for(int i = 0; i < m-1; ++i)// 由于剔除的是第m个，所以循环m-1次
{
//std::cout << now->data << " ";
pre = now;
now = now->next;
}
// std::cout << std::endl;
pre->next = now->next;// 剔除第m个元素
// std::cout << now->data << std::endl;
now = now->next;
}
return now->data;// 最后一个元素就是待返回值
}
};
挤挤刷刷！ 文章被收录于专栏
记录coding过程
查看1道真题和解析