Реализация метода двух указателей в наборах на C++

Я пытаюсь реализовать метод двух указателей в наборах на С++. Я хочу проверить, равна ли разница двух элементов набора константе «k».

void solve(int n,int k,set<int> s){
    auto it_1 = s.begin();
    auto it_2 = s.end();
    while(it_1 < it_2){ 
        if (*it_2 - *it_1 == k){
            cout << "YES" << endl;
            return;
        }
        else if (*it_2 - *it_1 > k){
            it_1++;
        }
        else{
            it_2--;
        }
    }
    cout << "NO" << endl;
    return;
}

Я получаю следующую ошибку: -

error: no match for 'operator<' (operand types are 'std::_Rb_tree_const_iterator' and 'std::_Rb_tree_const_iterator') while(it_1 < it_2)

Я знаю, что ошибка в том, что я сравниваю два указателя. Как я могу проверить, находится ли это_1 позади это_2?

Это не единственная проблема. if (*it_2... разыменует конечный итератор последовательности при первом запуске, который вызывает неопределенное поведение. Кроме того, я не понимаю, какое отношение имеет n ко всему этому, поэтому непонятно, почему он вообще предоставляется в качестве параметра для solve. он никогда не используется в функции.

WhozCraig 06.04.2022 18:15
... Я сравниваю два указателя... Неверно, вы сравниваете два итераторы. И эти итераторы поддерживают == и !=, но не поддерживают <.
Eljay 06.04.2022 18:17
void solve(int n,int k,set<int> s) -- Это подозрительно похоже на один из тех вопросов с сайтов, посвященных онлайн-соревнованиям по программированию. Если вы получили этот вопрос отсюда, вы не будете изучать C++, посещая эти сайты.
PaulMcKenzie 06.04.2022 18:18

«Как я могу проверить, находится ли it_1 за it_2» — вы схлопываетесь слева и справа одним движением одного итератора (1 или 2) за итерацию. Итак, простое использование while (it_1 != it_2) должно работать. Предостережение: это не решит проблему разыменования конечного итератора, о которой я упоминал ранее.

WhozCraig 06.04.2022 19:08

@PaulMcKenzie Я написал код в solve() для лучшего понимания проблемы. Это не проблема любого из соревнований по кодированию. Спасибо за ваш комментарий!

Anshuman Verma 06.04.2022 20:58

@WhozCraig Раньше я использовал массивы, поэтому вы видите n в коде. Спасибо за ваш комментарий !

Anshuman Verma 06.04.2022 20:59
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
6
50
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблемы с итераторами решаются быстро.

  • Просто используйте оператор != вместо <
  • Начинайте не с end-итератора, а на один элемент раньше. Потому что end-итератор указывает на последний допустимый элемент.

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

Давайте возьмем ваш первоначальный подход в качестве примера, исправим мелкие ошибки и посмотрим на результат:

#include <iostream>
#include <set>

void solve(int k, std::set<int>& s) {
    auto it_1 = s.begin();
    auto it_2 = std::prev(s.end());
    while (it_1 != it_2) {
        std::cout << *it_1 << ' ' << *it_2 << '\n';
        if (*it_2 - *it_1 == k) {
            std::cout << "YES\n";
            return;
        }
        else if (*it_2 - *it_1 > k) {
            it_1++;
        }
        else {
            it_2--;
        }
    }
    std::cout << "NO\n";
    return;
}
int main() {
    std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
    solve(8, test);
}

Это приведет к:

1 89
2 89
3 89
5 89
8 89
13 89
21 89
34 89
55 89
NO

Вы видите проблему.

Кстати, нахождение суммы — это типичный вариант использования подхода с двумя указателями. Тогда это всегда будет работать. Набор отсортирован. И мы начинаем с минимального значения в начале и максимального значения в конце. Таким образом, построение первой суммы даст нам максимально возможную сумму. Затем мы перемещаем сначала указатель с меньшими числами или, в зависимости от суммы, уменьшаем верхний указатель.

Пример:

#include <iostream>
#include <set>

void solve(int k, std::set<int>& s) {
    auto it_1 = s.begin();
    auto it_2 = std::prev(s.end());
    while (it_1 != it_2) {
        std::cout << *it_1 << ' ' << *it_2 << '\n';
        if (*it_2 + *it_1 == k) {
            std::cout << "YES\n";
            return;
        }
        else if (*it_2 + *it_1 < k) {
            it_1++;
        }
        else {
            it_2--;
        }
    }
    std::cout << "NO\n";
    return;
}
int main() {
    std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
    solve(8, test);
}

Выход:

1 89
1 55
1 34
1 21
1 13
1 8
1 5
2 5
3 5
YES


Но как решить дельта-проблему?

Что всегда будет работать, так это грубая сила. Это будет выглядеть так:

#include <iostream>
#include <set>

void solve(int k, std::set<int>& s) {
    auto it_1 = s.begin();
    auto it_2 = std::next(s.begin());

    while ((it_1 != s.end()) and (it_2 != s.end())) {
        std::cout << *it_1 << ' ' << *it_2 << '\n';
        if ((it_1 != it_2) and ((*it_2 - *it_1 == k) or (*it_1 - *it_2 == k))) {
            std::cout << "YES\n";
            return;
        }
        else if (*it_2 - *it_1 < k)
            ++it_2;
        else
            ++it_1;
    }
    std::cout << "NO\n";
    return;
}
int main() {
    std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
    solve(8, test);
}

Со следующим выводом:

1 2
1 3
1 5
1 8
1 13
2 13
3 13
5 13
YES

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

Другие вопросы по теме