题目
0, 1, …, n-1这n个数字(n>0)排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。
求出这个圆圈里剩下的最后一个数字。
样例
输入：n=5 , m=3
输出：3

解法一：模拟

c++中list容器用作双向链表
时间复杂度O(nm)，空间复杂度O(n)

  1. #include <list>
  3. class Solution {
  4. public:
  5.     int lastRemaining(int n, int m){
  6.         list<int> l;
  7.         for (int i = 0; i < n; i++) 
  8.             l.push_back(i);
  10.         int cnt = m - 1;
  11.         auto it = l.begin();
  12.         while (l.size() > 1) {
  13.             while (cnt--) {
  14.                 it++;
  15.                 if (it == l.end()) it = l.begin();
  16.             }
  17.             it = l.erase(it);
  18.             if (it == l.end()) it = l.begin();
  19.             cnt = m - 1;
  20.         }
  22.         return l.front();
  23.     }
  24. };

解法二：DP

dp(n, m) 表示n个人, m为号的最后结果
每次删除一个人后重新编号
那么 dp(n, m) = (dp(n - 1, m) + m) % n
因为此时0的位置是原来m的位置
时间复杂度O(n)，空间复杂度O(1)

  1. class Solution {
  2. public:
  3.     int lastRemaining(int n, int m){
  4.         int ans = 0;
  5.         for (int i = 1; i <= n; i++) {
  6.             ans += m;
  7.             if (ans >= i) ans %= i;
  8.         }
  10.         return ans;
  11.     }
  12. };
  14. // class Solution {
  15. // public:
  16. //     int lastRemaining(int n, int m){
  17. //         if (n == 0) return 0;
  18. //         return (lastRemaining(n - 1, m) + m) % n;
  19. //     }
  20. // };