圆圈中最后剩下的数字－C++

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程https://www.captainai.net/troubleshooter// 面试题62圆圈中最后剩下的数字 // 题目0, 1, …, n-1这n个数字排成一个圆圈从数字0开始每次从这个圆圈里 // 删除第m个数字。求出这个圆圈里剩下的最后一个数字。 #include cstdio #include list using namespace std; // 方法1 int LastRemaining_Solution1(unsigned int n, unsigned int m) { if (n 1 || m 1) return -1; unsigned int i 0; listint numbers; for (i 0; i n; i) numbers.push_back(i); listint::iterator current numbers.begin(); while (numbers.size() 1) { for (int i 1; i m; i) { current; if (current numbers.end()) current numbers.begin(); } listint::iterator next current; if (next numbers.end()) next numbers.begin(); --current; numbers.erase(current); current next; } return *(current); } // 方法2 int LastRemaining_Solution2(unsigned int n, unsigned int m) { if (n 1 || m 1) return -1; int last 0; for (int i 2; i n; i) last (last m) % i; return last; } // 测试代码 void Test(const char *testName, unsigned int n, unsigned int m, int expected) { if (testName ! nullptr) printf(%s begins: \n, testName); if (LastRemaining_Solution1(n, m) expected) printf(Solution1 passed.\n); else printf(Solution1 failed.\n); if (LastRemaining_Solution2(n, m) expected) printf(Solution2 passed.\n); else printf(Solution2 failed.\n); printf(\n); } void Test1() { Test(Test1, 5, 3, 3); } void Test2() { Test(Test2, 5, 2, 2); } void Test3() { Test(Test3, 6, 7, 4); } void Test4() { Test(Test4, 6, 6, 3); } void Test5() { Test(Test5, 0, 0, -1); } void Test6() { Test(Test6, 4000, 997, 1027); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); return 0; } // ------ Output ------ /* Test1 begins: Solution1 passed. Solution2 passed. Test2 begins: Solution1 passed. Solution2 passed. Test3 begins: Solution1 passed. Solution2 passed. Test4 begins: Solution1 passed. Solution2 passed. Test5 begins: Solution1 passed. Solution2 passed. Test6 begins: Solution1 passed. Solution2 passed. */