剑指Offer45 约瑟夫环

 /*************************************************************************

     > File Name: 45_LastNumberInCircle.cpp

     > Author: Juntaran

     > Mail: [email protected]

     > Created Time: 2016年09月04日 星期日 20时21分57秒

  ************************************************************************/

 #include <stdio.h>

 #include <bits/stdc++.h>

 using namespace std;

 // 环形链表

 int LastRemaining1(int n, int m)

 {

     if (n< || m<)

         return -;

     int i = ;

     list<int> numbers;

     for (int i = ; i < n; ++i)

         numbers.push_back(i);

     list<int>::iterator current = numbers.begin();

     while (numbers.size() > )

     {

         for (int i = ; i < m; ++i)

         {

             current ++;

             if (current == numbers.end())

                 current = numbers.begin();

         }

         list<int>::iterator next = ++current;

         if (next == numbers.end())

             next = numbers.begin();

         --current;

         numbers.erase(current);

         current = next;

     }

     return *current;

 }

 // 数组模拟环

 int LastRemaining2(int n, int m)

 {

     if (n< || m<)

         return -;

     int array[n];

     int i = -;

     int step = ;

     int count = n;

     while (count > )

     {

         i ++;

         if (i >= n)            // 模拟环

             i = ;

         if (array[i] == -)

             continue;

         step ++;

         if (step == m)

         {

             array[i] = -;

             step = ;

             count --;

         }

     }

     int ret = i;

     return ret;

 }

 // 数学解法

 int LastRemaining3(int n, int m)

 {

     if (n< || m<)

         return -;

     int ret = ;

     for (int i = ; i <= n; ++i)

         ret = (ret + m) % i;

     return ret;

 }

 int main()

 {

     int n = ;

     int m = ;

     int ret1 = LastRemaining1(n, m);

     int ret2 = LastRemaining2(n, m);

     int ret3 = LastRemaining3(n, m);

     printf("ret1 is %d\n", ret1);

     printf("ret2 is %d\n", ret2);

     printf("ret3 is %d\n", ret3);

     return ;

 }