Блог

Я изучаю технику с двумя указателями в технике с двумя указателями — Сценарий II

Он ввел указатель быстрого запуска и указатель медленного запуска для перемещения элементов и возврата новой длины

 public int removeElement(int[] nums, int val) {
    int k = 0;
    for (int i = 0; i < nums.length;   i) {
        if (nums[i] != val) {
            nums[k] = nums[i];
            k  ;
        }
    }
    return k;
}
 

Ниже приводится краткое изложение:

Это очень распространенный сценарий использования метода с двумя указателями, когда вам нужно:

Один медленный и один быстрый запуск одновременно.

Ключом к решению такого рода проблем является

Определите стратегию перемещения для обоих указателей.

Подобно предыдущему сценарию, вам иногда может потребоваться sort массив перед использованием метода с двумя указателями. И вам может понадобиться greedy подумать, чтобы определить свою стратегию движения.

Ссылка на

И вам может понадобиться greedy подумать, чтобы определить свою стратегию движения.

Это сбивает с greedy толку, поскольку мы greedy считаем фундаментальные жадные алгоритмы само собой разумеющимися.

Какие виды жадных алгоритмов могут быть использованы в двух указателях?

Не могли бы вы помочь примером?

Какие виды жадных алгоритмов могут быть использованы в двух указателях?

Рассмотрим эту проблему 3sum в LeetCode.

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

Рассмотрим другой проблемный контейнер с наибольшим количеством воды в LeetCode.

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