Leetcode 5727. 找出游戏的获胜者（DAY 82） ---- 周赛题目-白红宇

Leetcode 5727. 找出游戏的获胜者（DAY 82） ---- 周赛题目

阅读量：193 次

发布时间：2019-02-28

本文共 1043 字，大约阅读时间需要 3 分钟。

原题题目

题目描述：给定一个整数集合S，起始为1到n的连续整数。每次从集合中移除一个元素，并将其乘以k。最终剩下的唯一一个元素即为“赢家”。任务是通过编写代码，找出这个赢家。

代码实现

#include 
   
    using namespace std;class Solution {public:    int findTheWinner(int n, int k) {        vector
    
      dp;        for(int i = 1; i <= n; ++i) {            dp.push_back(i);        }        auto pos = dp.begin();        while(dp.size() > 1) {            int count = 1;            while(count != k) {                pos++;                count++;                if(pos == dp.end()) {                    pos = dp.begin();                }            }            pos = dp.erase(pos);            if(pos == dp.end()) {                pos = dp.begin();            }        }        return dp.front();    }};

解释代码实现

该代码通过模拟一个循环过程来找出最终的赢家。具体步骤如下：

初始化数据结构：使用一个向量dp来存储当前集合的元素，初始值为1到n的连续整数。

定位元素并进行操作：通过一个循环不断从集合中移除元素。具体来说：

初始化count为1，表示已经处理了多少次。

在集合中寻找第count个元素的位置。

当找到目标元素时，将其从集合中移除，并更新当前位置指向下一个元素。

处理循环边界：当指针pos指向集合末尾时，循环将其重置到集合起始位置。

返回结果：当集合只剩下一个元素时，返回该元素作为最终赢家。

该算法的时间复杂度为O(n^2)，在n较小时能够较好地运行。通过不断地移除元素并更新当前位置，逐步缩小集合范围，最终找到最后一个剩下的元素。

转载地址：http://vbni.baihongyu.com/

你可能感兴趣的文章