Ответ 1

Попробуйте следующее:

int containsPairs(vector<int> hand)
{
    int pairs{ 0 };

    for (int i = 0; i < hand.size(); i++)
    {
        int c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            int c2 = hand[j];
            if (c1 == c2)
            {
                pairs++;
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                i--;
                break;
            }
        }
    }
    return pairs;
}

Это почти ваша версия, единственная разница заключается в том, что вместо goto существует i--; break;. Эта версия более эффективна, чем ваша, поскольку она выполняет только двойной цикл.

Яснее? Ну, это личное предпочтение. Я вообще не против goto, я думаю, его текущий статус "никогда не использовать" должен быть пересмотрен. Бывают случаи, когда goto - лучшее решение.

Здесь еще одно, еще более простое решение:

int containsPairs(vector<int> hand)
{
    int pairs{ 0 };

    for (int i = 0; i < hand.size(); i++)
    {
        int c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            int c2 = hand[j];
            if (c1 == c2)
            {
                pairs++;
                hand.erase(hand.begin() + j);
                break;
            }
        }
    }
    return pairs;
}

В принципе, когда он находит пару, он удаляет только более длинную карту и разбивает цикл. Поэтому не нужно быть сложным с i.

Ответ 2

А (слегка) более быстрый алгоритм также позволяет избежать goto

Удаление из a std::vector никогда не бывает быстрым и его следует избегать. То же самое верно для копирования a std::vector. Избегая обоих, вы также избегаете goto. Например

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand
{
    size_t num_pairs = 0;
    std::unordered_set<size_t> in_pair;

    for(size_t i=0; i!=hand.size(); ++i)
    {
        if(in_pair.count(i)) continue;
        auto c1 = hand[i];
        for(size_t j=i+1; j!=hand.size(); ++j)
        {
            if(in_pair.count(j)) continue;
            auto c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                ++num_pairs;
                in_pair.insert(i);
                in_pair.insert(j);
            }
        }
    }
    return num_pairs;
}

Для больших рук этот алгоритм все еще медленный, так как O (N ^ 2). Быстрее будет сортировка, после чего пары должны быть соседними картами, предоставляя алгоритм O (N logN).

Тем не менее быстрее, O (N), должен использовать unordered_set не для карт в парах, а для всех других карт:

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand
{
    size_t num_pairs = 0;
    std::unordered_set<Card> not_in_pairs;
    for(auto card:hand)
    {
        auto match = not_in_pairs.find(card));
        if(match == not_in_pairs.end())
        {
            not_in_pairs.insert(card);
        }
        else
        {
            ++num_pairs;
            not_in_pairs.erase(match);
        }   
    }
    return num_pairs;
}

При достаточно малых hand.size() это может быть не быстрее, чем код выше, в зависимости от sizeof(Card) и/или стоимости его конструктора. Аналогичный подход заключается в использовании распределения, предложенного в Eric Duminil answer:

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand
{
    std::unordered_map<Card,size_t> slots;
    for(auto card:hand)
    {
        slots[card]++;
    }
    size_t num_pairs = 0;
    for(auto slot:slots)
    {
        num_pairs += slot.second >> 1;
    }
    return num_pairs;
}

Конечно, эти методы могут быть реализованы гораздо проще, если Card можно тривиально отобразить в небольшое целое, если не требуется хеширование.

Ответ 3

Для развлечения здесь есть еще два пути, я представляю несколько более эффективный метод без перерывов или goto. Затем я представляю менее эффективный метод, который сначала сортируется.

Оба эти метода просты для чтения и понимания.

На самом деле это просто означает показать альтернативы другим ответам. Первый метод containsPairs, который у меня есть, требует, чтобы значения карт находились в диапазоне от 0 до 13 и прерывались, если это не так, но очень немного эффективнее любого из других ответов, которые я видел.

int containsPairs(const vector<int> &hand)
{
    int pairs{ 0 };
    std::vector<int> counts(14); //note requires 13 possible card values
    for (auto card : hand){
        if(++counts[card] == 2){
            ++pairs;
            counts[card] = 0;
        }
    }
    return pairs;
}

int containsPairs(const vector<int> &hand)
{
    int pairs{ 0 };

    std::sort(hand.begin(), hand.end());
    for (size_t i = 1;i < hand.size();++i){
        if(hand[i] == hand[i - 1]){
            ++i;
            ++pairs;
        }
    }
    return pairs;
}

Примечание: несколько других ответов будут обрабатывать 3 одинаковые карты в руке в виде двух пар. Эти два вышеперечисленных метода учитывают это, и вместо этого будут учитываться только 1 пара для 3. Они будут рассматривать его как 2 пары, если есть 4 похожих карты.

Ответ 4

goto - только одна проблема. Еще одна большая проблема заключается в том, что ваш метод неэффективен.

Ваш метод

Ваш текущий метод в основном смотрит на первую карту, выполняет итерацию над остальными и ищет одно и то же значение. Затем он возвращается ко второй карте и сравнивает ее с остальными. Это O(n**2).

Сортировка

Как вы считаете пары в реальной жизни? Вероятно, вы отсортировали карты по достоинству и искали пары. Если вы сортируете эффективно, это будет O(n*log n).

Распространение

Самый быстрый способ - подготовить 13 слотов на столе и распределить карты в соответствии с их номинальной стоимостью. После раздачи каждой карты вы можете подсчитывать карты в каждом слоте и видеть, имеет ли какой-либо слот минимум 2 карты. Он O(n), и он также обнаружит три вида или четыре вида.

Несомненно, нет большой разницы между n**2 и n, когда n равно 5. В качестве бонуса последний метод был бы кратким, легким для записи и goto -бесплатным.

Ответ 5

Если вы действительно хотите избежать goto, вы можете просто вызвать функцию рекурсивно, где будет строка goto [label], передавая любые переменные, состояние которых вы хотите сохранить как параметры. Тем не менее, я бы рекомендовал придерживаться goto.

Ответ 6

Я лично поставил эти два цикла в лямбда, вместо goto вернется из этой лямбда с указанием, что петли должны перезапустить и вызовет лямбду в цикле. Что-то вроде этого:

auto iterate = [&hand, &pairs]() {
             {
              ... // your two loops go here, instead of goto return true
             }
             return false;
}

while (iterate());

Малое добавление. Я не думаю, что это лучший алгоритм для поиска пар карт в колоде. Для этого есть намного лучшие варианты. Я скорее отвечаю на вездесущий вопрос о том, как передать управление в или из двух циклов сразу.

Ответ 7

Да, вам следует избегать использования goto здесь.

Это ненужное использование goto специально потому, что алгоритм не нуждается в нем. В стороне, я склонен не использовать goto, но я не уверен в этом, как многие. goto - отличный инструмент для разрыва вложенных циклов или для выхода из функции, когда интерфейс не поддерживает RAII.

Есть несколько недостатков с вашим текущим подходом:

• Нет причин для повторного поиска списка с самого начала, когда вы найдете подходящую пару. Вы уже искали все предыдущие комбинации. Извлечение карт не изменяет относительный порядок неиспользуемых карт, и, кроме того, он не предоставляет вам больше пар.
• Нет необходимости удалять элементы из середины hand. Для этой проблемы удаление из середины std::vector, предположительно представляющего руку из 5 карт, не является проблемой. Однако, если количество карт велико, это может быть неэффективным. В таких проблемах вы должны спросить себя, имеет ли порядок элементов? Ответ не в этом. Мы можем перетасовать любые карты, которые еще не были спарены, и по-прежнему получают тот же ответ.

Вот измененная версия вашего кода:

int countPairs(std::vector<Card> hand)
{
    int pairs{ 0 };

    for (decltype(hand.size()) i = 0; i < hand.size(); ++i)
    {
        // I assume getFace() has no side-effects and is a const
        // method of Card.  If getFace() does have side-effects
        // then this whole answer is flawed.
        const Card& c1 = hand[i];
        for (auto j = i + 1; j < hand.size(); ++j)
        {
            const Card& c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                // We found a matching card for card i however we
                // do not need to remove card i since we are
                // searching forward.  Swap the matching card
                // (card j) with the last card and pop it from the
                // back.  Even if card j is the last card, this
                // approach works fine.  Finally, break so we can
                // move on to the next card.
                pairs++;
                std::swap(c2, hand.back());
                hand.pop_back(); // Alternatively decrement a size variable
                break;
            }
        }
    }
    return pairs;
}

Вы можете прикоснуться к вышеуказанному подходу к использованию итераторов, если это необходимо. Вы также можете взять константную ссылку std::vector и использовать std::reference_wrapper для повторной сортировки контейнера.

Для общего лучшего алгоритма постройте частотную таблицу каждого номинала и соответствующий счетчик.

Ответ 8

Я бы сделал так:

Особенности:

• 3 не является парой
• возвращает вектор карт в порядке нисходящей Линии, указывающей, какие лица являются парами в руке.

std::vector<Card> reduceToPair(std::vector<Card> hand)
{
    auto betterFace = [](auto&& cardl, auto&& cardr)
    {
        return cardl.getFace() > cardr.getFace();
    };

    std::sort(begin(hand), end(hand), betterFace);

    auto first = begin(hand);
    while (first != end(hand))
    {
        auto differentFace = [&](auto&& card)
        {
            return card.getFace() != first->getFace();
        };
        auto next = std::find_if(first + 1, end(hand), differentFace);
        auto dist = std::distance(first, next);
        if (dist == 2)
        {
            first = hand.erase(first + 1, next);
        }
        else
        {
            first = hand.erase(first, next);
        }
    }

    return hand;
}

использование:

pairInfo = reduceToPair(myhand);
bool hasPairs = pairInfo.size();
if (hasPairs)
{
  auto highFace = pairInfo[0].getFace();
  if (pairInfo.size() > 1) {
    auto lowFace = pairInfo[1].getFace();
  }
}

Ответ 9

Если сортировка карт по лицу возможна и разрешена, мы можем считать пары с помощью всего лишь одного прохода без стирания:

bool Compare_ByFace(Card const & left, Card const & right)
{
    return(left.Get_Face() < right.Get_Face());
}

size_t Count_Pairs(vector<Card> hand)
{
    size_t pairs_count{0};
    if(1 < hand.size())
    {
        sort(hand.begin(), hand.end(), &Compare_ByFace);
        auto p_card{hand.begin()};
        auto p_ref_card{p_card};
        for(;;)
        {
           ++p_card;
           if(hand.end() == p_card)
           {          
               pairs_count += static_cast< size_t >((p_card - p_ref_card) / 2);
               break;
           }
           if(p_ref_card->Get_Face() != p_card->Get_Face())
           {
               pairs_count += static_cast< size_t >((p_card - p_ref_card) / 2);
               p_ref_card = p_card;
           }
        }
    }
    return(pairs_count);
}

Ответ 10

#include <vector>
#include <unordered_map>
#include <algorithm>

std::size_t containsPairs(const std::vector<int>& hand)
{
    // boilerplate for more readability
    using card_t = std::decay_t<decltype(hand)>::value_type;
    using map_t = std::unordered_map<card_t, std::size_t>;

    // populate map and count the entrys with 2 occurences
    map_t occurrences;
    for (auto&& c : hand) { ++occurrences[c]; }
    return std::count_if( std::cbegin(occurrences), std::cend(occurrences), [](const map_t::value_type& entry){ return entry.second == 2; });
}

Ответ 11

Одна из проблем с goto заключается в том, что ярлыки, как правило, идут на переходы по ошибочному рефакторингу. Это принципиально, почему они мне не нравятся. Лично, в вашем случае, если вам нужно сохранить алгоритм как есть, я бы перевернул goto в рекурсивный вызов:

int containsPairs(vector<Card>&/*Deliberate change to pass by reference*/hand)
{
    for (int i = 0; i < hand.size(); i++)
    {
        Card c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            Card c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                return 1 + containsPairs(hand); 
            }
        }
    }
    return 0;
}

Накладные расходы при создании фрейма стека незначительны cf. std::vector. Это может быть непрактичным в зависимости от сайта вызова: вы больше не можете вызывать функцию с анонимным временным, например. Но действительно есть лучшие альтернативы для идентификации пары: почему бы не упорядочить руку более оптимально?

Ответ 12

Можно ли изменить порядок элементов в векторе? Если да, просто используйте алгоритм adjacent_find в одном цикле.

Таким образом, вы не только избавитесь от goto, но получите лучшую производительность (в настоящее время у вас есть O(N^2)) и гарантированная правильность:

std::sort(hand.begin(), hand.end(), 
    [](const auto &p1, const auto &p2) { return p1.getFace() < p2.getFace(); });
for (auto begin = hand.begin(); begin != hand.end(); )
{
  begin = std::adjacent_find(begin, hand.end(), 
        [](const auto &p1, const auto &p2) { return p1.getFace() == p2.getFace(); });
  if (begin != hand.end())
  {
    auto distance = std::distance(hand.begin(), begin);
    std::erase(begin, begin + 2);  // If more than 2 card may be found, use find to find to find the end of a range
    begin = hand.begin() + distance;
  }
}

Ответ 13

Ваша реализация не работает, так как она считается тремя в виде одной пары, четыре в виде двух.

Вот реализация, которую я предлагаю:

int containsPairs(std::vector<Card> hand)
{
    std::array<int, 14> face_count = {0};
    for (const auto& card : hand) {
        ++face_count[card.getFace()]; // the Face type must be implicitly convertible to an integral. You might need to provide this conversion or use an std::map instead of std::array.
    }
    return std::count(begin(face_count), end(face_count), 2);
}

(демо на coliru)

Он может быть обобщен для подсчета не только пар, но и n вида, путем настройки 2.

Ответ 14

Другие ответы до сих пор касаются того, как фундаментально перестроить ваш код. Они указывают, что ваш код не очень эффективен для начала, и к тому моменту, когда вы исправили, что вам нужно только вырваться из одного цикла, так что вам все равно не нужен goto.

Но я собираюсь ответить на вопрос о том, как избежать goto без коренного изменения алгоритма. Ответ (как это часто бывает для избежания goto) заключается в том, чтобы переместить часть вашего кода в отдельную функцию и использовать ранний return:

void containsPairsImpl(vector<Card>& hand, int& pairs)
{
    for (int i = 0; i < hand.size(); i++)
    {
        Card c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            Card c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                pairs++;
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                return;
            }
        }
    }
    hand.clear();
}

int containsPairs(vector<Card> hand)
{
    int pairs{ 0 };
    while (!hand.empty()) {
        containsPairsImpl(hand, pairs);
    }
    return pairs;
}

Обратите внимание, что я передаю hand и pairs ссылкой на внутреннюю функцию, чтобы их можно было обновить. Если у вас много этих локальных переменных или вам нужно разбить функцию на несколько частей, это может стать громоздким. Тогда решение должно использовать класс:

class ContainsPairsTester {
public:
    ContainsPairsTester(): m_hand{}, m_pairs{0} {}

    void computePairs(vector<Card> hand);

    int pairs() const { return m_pairs; }
private:
    vector<Card> m_hand;
    int m_pairs;

    void computePairsImpl(vector<Card> hand);
};

void ContainsPairsTester::computePairsImpl()
{
    for (int i = 0; i < m_hand.size(); i++)
    {
        Card c1 = m_hand[i];
        for (int j = i + 1; j < m_hand.size(); j++)
        {
            Card c2 = m_hand[j];
            if (c1.getFace() == c2.getFace())
            {
                m_pairs++;
                m_hand.erase(m_hand.begin() + i);
                m_hand.erase(m_hand.begin() + (j - 1));
                return;
            }
        }
    }
    m_hand.clear();
}

void ContainsPairsTester::computePairs(vector<Card> hand)
{
    m_hand = hand;
    while (!m_hand.empty()) {
        computePairsImpl();
    }
}

Ответ 15

Как отмечали другие, вы должны не только избегать goto, но и избегать написания собственного кода, где есть стандартный алгоритм, который может выполнять эту работу. Я удивлен, что никто не предложил уникальный, который предназначен для этой цели:

bool cardCmp(const Card& a, const Card& b) {
    return a.getFace() < b.getFace();
}

size_t containsPairs(vector<Card> hand) {
    size_t init_size = hand.size();

    std::sort(hand.begin(), hand.end(), cardCmp);
    auto it = std::unique(hand.begin(), hand.end(), cardCmp);
    hand.erase(it, hand.end());

    size_t final_size = hand.size();
    return init_size - final_size;
}

(Первый ответ на StackOverflow - извинения за любой faux pas!)

Ответ 16

Хотя goto на самом деле не так уж и страшно, если вам это нужно, здесь это не обязательно. Поскольку вас беспокоит только количество пар, также нет необходимости записывать, что представляют собой эти пары. Вы можете просто xor через весь список.

Если вы используете GCC или clang, будет работать следующее. В MSVC вы можете использовать __popcnt64() вместо этого.

int containsPairs(vector<Card> hand)
{
    size_t counter = 0;
    for ( Card const& card : hand )
        counter ^= 1ul << (unsigned) card.getFace();

    return ( hand.size() - __builtin_popcountll(counter) ) / 2u;
}