Требования

Рекомендуется, чтобы читатели имели базовое представление о языке программирования Java, прежде чем приступить к изучению этой статьи. Сюда входит знакомство с объявлением переменных, использованием циклов (циклы for и while) и реализацией условных операторов (таких как операторы if-else). Если вы новичок в программировании или Java, может быть полезно получить эти базовые навыки, прежде чем продолжить. Чтобы начать работу, доступно множество онлайн-ресурсов, включая учебные пособия, курсы и книги по программированию. Не стесняйтесь вернуться к этой статье после того, как вы приобретете некоторые знания в области программирования.

Введение

Вы заинтересованы в улучшении своих навыков программирования и повышении своей ценности на рынке труда? Изучение алгоритмов и структур данных — отличное место для начала. Четкое понимание этих концепций может дать вам преимущество на собеседованиях и помочь вам писать более эффективный и действенный код.

В этой статье мы углубимся в проблему с массивами вводного уровня из LeetCode, написанную на Java. Цель этой части — предоставить пошаговое руководство для тех, кто только начинает изучать алгоритмы и структуры данных в Java. К концу этой статьи вы должны иметь четкое представление о том, как подходить к этому типу проблем, и чувствовать себя более уверенно в своих навыках кодирования.

LeetCode — популярная платформа для отработки и совершенствования навыков кодирования. Он предлагает обширный набор задач по кодированию, называемых «вызовами», предназначенных для проверки и улучшения ваших навыков в различных языках программирования.

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

Эта статья является дополнительным ресурсом, который поможет заполнить пробелы и начать ваш путь к освоению алгоритмов и структур данных с использованием LeetCode или аналогичных платформ (HackerRank, CodeChef, CodeForces, Project Euler, Кодербайт и др.).

Без лишних слов, давайте погрузимся и начнем учиться!

Проблема

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

Это вызов LeetCode легкого уровня (оригинальный вызов).

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

  1. Понимание требований (ввод, вывод и ограничения)
  2. Напишите описание решения на естественном языке
  3. Закодируйте решение

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

Вы можете найти ввод и вывод на выбранном вами языке в редакторе LeetCode, чтобы лучше понять, какой тип/форму возвращаемого значения.

public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
    // your solution will go here
}

Приступим к анализу входных данных.«функция, которая принимает три целочисленных массива, отсортированных в строго возрастающем порядке». Знание того, что входные массивы уже отсортированы, избавляет нас от необходимости переупорядочивать все входные массивы. В большинстве случаев, если входной массив уже отсортирован, нет необходимости сортировать массив в другом порядке. Но есть еще одна вещь, которую следует учитывать здесь. Как насчет размера каждого массива? Все ли массивы имеют одинаковый размер? Вам нужно задать эти вопросы в технической задаче на собеседовании, чтобы интервьюер мог намекнуть или более подробно объяснить ограничения. В этой задаче три массива имеют одинаковую длину.

Теперь необходимый вывод. "возвратить новый отсортированный массив, содержащий только целые числа, которые появились во всех трех входных массивах". Мы можем сказать, какие данные необходимо вернуть в конце функции. Поскольку массив может различаться по размеру, нам нужен ArrayList вместо фиксированного Array, чтобы создать окончательное решение путем добавления значений.

Кроме того, я переписал исходный вопрос этой статьи, чтобы подчеркнуть еще один момент при использовании ArrayList. Прочтите жирным шрифтом часть объяснения ввода"return..., содержащую только целые числа..." В большинстве случаев можно предположить, что вы может вернуть пустой массив или ничего, если вы видите единственное слово в описании ограничения. Но это всегда хорошая идея, чтобы подтвердить с интервьюером.

Описание на естественном языке

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

Есть несколько преимуществ использования описаний на естественном языке для объяснения кода:

  1. Они могут упростить понимание сложного кода: описания на естественном языке могут помочь прояснить цель и логику фрагмента кода, облегчая понимание того, что он делает, для тех, кто не знаком с кодом.
  2. Они могут помочь при проверке кода: описание на естественном языке может предоставить общий обзор фрагмента кода, который может быть полезен во время проверки кода, чтобы убедиться, что код правильный и соответствует требованиям проекта.
  3. Они могут улучшить коммуникацию: описания на естественном языке могут быть полезны для сообщения цели и логики фрагмента кода членам команды, незнакомым с языком программирования.
  4. Их можно использовать для документирования кода: описания на естественном языке могут быть включены в документацию по коду, чтобы дать нетехническое объяснение того, что делает код и как он вписывается в общий проект.

Если вы стремитесь работать в крупных технологических компаниях, таких как Google, Microsoft или Apple, вам необходимо изучить этот навык, поскольку они хотят оценить ваш мыслительный процесс при решении проблемы.

Чтобы решить эту проблему, мы будем использовать подход с n-указателями. Поскольку у нас есть три массива в качестве входных данных, это будет подход с тремя указателями. Этот подход состоит в одновременном переборе всех массивов с использованием независимого указателя для каждого массива. У нас есть три массива в качестве входных данных, поэтому нам нужно три указателя для независимого поиска в каждом массиве. Вместо итерации с использованием for, как мы делаем с одним массивом, нам нужен цикл while, поскольку итерация заканчивается при выполнении условия, а не посещает все позиции массивов.

Решение в описании на естественном языке выглядит так:

Шаг 1: Объявите список с именем solution для хранения общих элементов трех массивов.

Шаг 2: Объявите три переменные i, j и k для представления текущих индексов трех массивов. Все индексы начинаются с 0.

Шаг 3а: цикл while. Если одно из этих условий истинно, цикл завершается:

  • iменьше длины arr1
  • j меньше длины arr2
  • k меньше длины arr3

Шаг 3b: Что нам нужно сделать внутри цикла while (предположим, что у нас есть три массива [1,2,7], [2,7,8] и [7,8,9] в качестве входных данных для анализа требуемой здесь логики. Решение для этих массивов — [7], потому что 7 — единственное значение, которое существует в каждый заданный массив):

  • Проверьте, содержат ли arr1[i], arr2[j] и arr3[k] одно и то же значение. Все указатели начинаются с 0, что означает, что мы сравниваем 1, 2 и 7 в первой итерации. Нам нужна логика, которая увеличивает значение указателей на каждой итерации, чтобы выполнить поиск и добавить значения к solution.
  • Увеличьте значение каждого указателя, следуя некоторым правилам. В случае первой итерации мы сравнили 1, 2 и 7. Поскольку все массивы сортируются по нарастающей, мы можем гарантировать, что 1 и 2 не попадут в solution. Поскольку 7 является наименьшим значением в 3-м массиве, больше нет смысла искать в 3-м массиве. Это означает, что нам нужна логика, которая увеличивает значение указателя из массива, содержащего наименьшее значение, на каждой итерации.
  • Когда точное значение будет найдено, добавьте его к solution и одновременно увеличьте значения трех указателей.

4: Вернуть solution

Теперь, когда у нас есть решение на естественном языке, мы можем приступить к реализации решения на Java.

Код решения

class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        // step 1
        List<Integer> solution = new ArrayList<>();
        // step 2
        int i = 0, j = 0, k = 0;
        // step 3a
        // i is less than the length of arr1 -> i < arr1.length
        // j is less than the length of arr2 -> j < arr2.length
        // k is less than the length of arr3 -> k < arr3.length
        while (i < arr1.length && j < arr2.length && k < arr3.length) {
            // step 3b
            // if values at the current iteration are equal, add to solution
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                // you may use arr2[j] or arr3[k] since they have the same value
                solution.add(arr1[i]);
                // When the same value is found, add it to 
                // solution and increase the values of the 
                // three pointers simultaneously
                i++;
                j++;
                k++;
            }
            // otherwise, increment index of the smallest element
            else if (arr1[i] <= arr2[j] && arr1[i] <= arr3[k]) {
                // arr1[i] contains the smallest value, increase i
                i++;
            }
            else if (arr2[j] <= arr1[i] && arr2[j] <= arr3[k]) {
                // arr2[j] contains the smallest value, increase j
                j++;
            }
            else {
                // arr3[k] contains the smallest value, increase k
                k++;
            }
        }
        // step 4
        return solution;
    }
}

Вы должны быть в состоянии пройти испытание, используя этот код. Кроме того, вы можете ознакомиться с различными решениями, опубликованными в разделе Обсуждение, чтобы получить дополнительные сведения. Анализ подходов других людей часто может помочь углубить ваше понимание проблемы и решения. Удачи!

Заключение

Поздравляем с решением задачи уровня 1 массива! Я надеюсь, что вы нашли статью интересной и интересной. Если вы нашли контент ценным, рассмотрите возможность выразить признательность несколькими хлопками. Это помогает мотивировать меня создавать больше контента для всех вас 🙂.

Кроме того, если у вас есть какие-либо отзывы или предложения, я буду рад их услышать. Ваш вклад помогает мне совершенствоваться и создавать еще более полезные и информативные статьи в будущем.

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