Реализация метода двух указателей в наборах на 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
Получение данных из формы с помощью JavaScript - краткое руководство
Получение данных из формы с помощью JavaScript - краткое руководство
Получить данные из формы с помощью JS очень просто: вы запрашиваете элемент формы, передаете его конструктору new FormData() и, наконец, получаете...
Пользовательские правила валидации в Laravel
Пользовательские правила валидации в Laravel
Если вы хотите создать свое собственное правило валидации, Laravel предоставляет возможность сделать это. Создайте правило с помощью следующей...
3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
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. Но, может быть, это слишком много для этого.

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