劍指offer之圓圈最后剩下的數(shù)

1 問(wèn)題

求圓圈最后剩下的數(shù)，比如數(shù)組0, 1, 2 ,3 ,4圍城一個(gè)環(huán)，我們每次去掉第三個(gè)數(shù)字，刪除的前4個(gè)數(shù)字依次是2, 0, 4, 1，最后剩下的數(shù)字是3

                      0
     
             4               1
     
               3           2


2 思路

我們用list,我們要支持環(huán)就這樣,如果發(fā)現(xiàn)當(dāng)前指針指向是尾巴的時(shí)候，我們把它指向鏈表的開始。

 
 
3 代碼實(shí)現(xiàn)

    #include <iostream>
    #include <list>
     
    using namespace std;
     
    int getIndex(int n, int m)
    {
        if (n < 1 || m < 1)
        {
            return -1;
        }
        list<int> numbers;
        for (int i = 0; i < n; ++i)
        {
            numbers.push_back(i);
        }
        list<int>::iterator current = numbers.begin();
        while(numbers.size() > 1)
            {
            for(int i = 1; i < m; ++i)
            {
                current++;
                //指針向右移動(dòng)的時(shí)候需要判斷是否到了數(shù)組尾巴
                if (current == numbers.end())
                {
                    current = numbers.begin();
                }
            }
            //指針向右移動(dòng)的時(shí)候需要判斷是否到了數(shù)組尾巴
            list<int>::iterator next = ++current;
            if (next == numbers.end())
            {
                next = numbers.begin();
            }
            current--;
                    //刪除指定的元素
            numbers.erase(current);
            current = next;
        }
        return *(current);
    }
     
    int main()
    {
        int a[] = {0, 1, 2, 3, 4};
        int index = getIndex(5, 3);
        if (-1 != index)
            {
            std::cout << a[index] << std::endl;
        }
        return 0;
    }

 
4 運(yùn)行結(jié)果

3


 
5 總結(jié)

如果我們需要環(huán)的數(shù)據(jù)結(jié)構(gòu)，我么可以使用list數(shù)據(jù)結(jié)構(gòu)，然后當(dāng)指針指向尾巴的時(shí)候我們指向頭。

    list<int> numbers;
    for (int i = 0; i < n; ++i)
    {
        numbers.push_back(i);
    }
    list<int>::iterator current = numbers.begin();
    for (int i = 1; i < m; ++i)
    {
        ++current;
        if (current == numbers.end())
        {
            current = numbers.begin();
        }
    }   

 


 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)