Полное руководство по алгоритмам, структурам данных и решениям для LeetCode, предназначенное для начинающих.
Ах, алгоритмы — строительные блоки информатики! Сначала они могут показаться пугающими, но не волнуйтесь, мы разберем их для вас.
Проще говоря, алгоритм — это набор инструкций, которым компьютер может следовать для решения проблемы. Это как рецепт, только для компьютеров вместо еды. Точно так же, как вам нужно следовать шагам рецепта, чтобы испечь торт, компьютеру нужно следовать шагам алгоритма, чтобы решить проблему.
Теперь вы можете задаться вопросом: «Зачем нам вообще нужны алгоритмы?» Что ж, представьте, что вы пытаетесь решить сложную проблему без какого-либо плана или метода — это все равно, что пытаться пройти лабиринт с завязанными глазами! Алгоритмы дают нам систематический подход к решению проблем, облегчая нам решение сложных задач.
Но не волнуйтесь, вам не нужно быть компьютерным гением, чтобы понимать алгоритмы. На самом деле каждый может научиться их создавать и реализовывать. Все, что нужно, это немного терпения и желание учиться. Итак, вы готовы погрузиться глубже в мир алгоритмов? Давайте начнем!
Если вы хотите вывести свои навыки работы с алгоритмами и структурами данных на новый уровень, я настоятельно рекомендую книгу «Алгоритмы, 4-е издание» Роберта Седжвика и Кевина Уэйна. Как человек, который также учится по этой книге, я могу засвидетельствовать ее удобный для начинающих подход и всестороннее освещение темы. Книга глубоко погружается в основы алгоритмов и структур данных, а также содержит практические примеры и фрагменты кода, которые помогут вам применить то, что вы узнали. Если вы хотите копнуть глубже и укрепить свое понимание концепций, эта книга обязательна к прочтению. А если вы воспользуетесь партнерской ссылкой, которую я указал ниже, это не только сэкономит ваше время на поиске книги, но и принесет мне небольшие чаевые. Это беспроигрышная ситуация для нас обоих!
Давайте подробнее рассмотрим эти два алгоритма.
Во-первых, у нас есть алгоритм деления. Как следует из названия, этот алгоритм используется для деления одного числа на другое. Процедура этого алгоритма включает инициализацию делимого и делителя целыми числами, а затем вычитание делителя из делимого до тех пор, пока делимое не станет меньше делителя. Частное — это количество раз, когда делитель вычитался из делимого, а остаток — это значение делимого после завершения вычитания.
Чтобы реализовать этот алгоритм на Java, мы можем использовать цикл while для вычитания делителя из делимого до тех пор, пока делимое не станет меньше делителя. Мы увеличиваем частное при каждом вычитании и в конце выводим как частное, так и остаток.
int dividend = 25;
int divisor = 5;
int quotient = 0;
while (dividend >= divisor) {
dividend -= divisor;
quotient++;
}
System.out.println("Quotient: " + quotient);
System.out.println("Remainder: " + dividend);
Далее у нас есть алгоритм умножения. Этот алгоритм используется для умножения одного числа на другое. Процедура этого алгоритма включает в себя инициализацию двух чисел, которые нужно умножить, а затем добавление первого числа к произведению столько раз, сколько указано вторым числом.
Чтобы реализовать этот алгоритм на Java, мы можем использовать цикл for, чтобы добавить первое число к произведению столько раз, сколько указано вторым числом. Затем мы распечатываем продукт в конце.
int num1 = 5;
int num2 = 6;
int product = 0;
for (int i = 0; i < num2; i++) {
product += num1;
}
System.out.println("Product: " + product);
И вот они у вас есть — два основных алгоритма, которые составляют основу информатики. Имейте в виду, что алгоритмы могут быть гораздо более сложными, чем эти, но важно начать с основ и строить дальше. Так что продолжайте учиться и исследовать, и кто знает — возможно, вы создадите следующий новаторский алгоритм!
Алгоритмы часто используются для организации данных и управления ими, что, в свою очередь, приводит к созданию структур данных. Важно понимать взаимосвязь между алгоритмами и структурами данных, потому что выбор структуры данных может иметь большое влияние на производительность алгоритма.
Что касается языков программирования, Java — отличный выбор для тех, кто интересуется информатикой и разработкой программного обеспечения. Это популярный язык, используемый в самых разных приложениях, от веб-разработки до разработки мобильных приложений. Java известен своей мощной поддержкой объектно-ориентированного программирования, что упрощает написание сложных программ и их поддержку с течением времени.
В Java программа обычно организована в классы, которые могут содержать статические методы (функции) или типы данных. Для создания библиотек статических методов и типов данных мы используем пять ключевых компонентов:
- Классы: это строительные блоки программ Java, которые определяют поведение и данные объектов.
- Интерфейсы: они определяют набор методов, которые должен реализовать класс, что обеспечивает большее повторное использование кода и гибкость.
- Наследование: это позволяет одному классу наследовать поведение и данные от другого класса, что упрощает создание специализированных версий существующих классов.
- Полиморфизм: это позволяет обрабатывать объекты разных классов так, как если бы они были одного типа, что упрощает написание кода, который может работать со многими различными типами объектов.
- Исключения: они используются для обработки ошибок и исключительных ситуаций, которые могут возникнуть во время выполнения программы.
Понимая эти ключевые компоненты, мы можем создавать хорошо организованные и эффективные программы Java, которые легко поддерживать и расширять с течением времени.
Примитивные типы данных. Эти маленькие ребята подобны строительным блокам любой программы, определяя значение таких терминов, как целые числа, действительные числа и логические значения. Это как иметь свой личный словарь, чтобы машина могла его понять.
Далее у нас есть заявления. Думайте о них как о хореографе вашей программы, направляющем поток выполнения и вызывающем всевозможные побочные эффекты. Объявления, присваивания, условные операторы, циклы, вызовы и возвраты — это танцевальные движения, которые оживляют вашу программу.
А как же массивы? Что ж, они похожи на хоровую строку значений, позволяющую вам работать с несколькими значениями одного и того же типа. Это похоже на то, как если бы у вас под рукой была резервная копия данных.
Теперь поговорим о статических методах. Они как супергерои вашего кода, инкапсулирующие и повторно использующие код для создания независимых модулей. Они как Мстители, но для программирования.
Строки, с другой стороны, больше похожи на див вашей программы — они требуют внимания и могут быть немного сложными в обслуживании. Но эй, это последовательности символов, и некоторые операции над ними встроены прямо в Java.
А кто мог забыть ввод/вывод? Это своего рода коммуникационный центр вашей программы, позволяющий ей взаимодействовать с внешним миром. Это как иметь телефонную линию во вселенную.
И последнее, но не менее важное: у нас есть абстракция данных. Это выводит инкапсуляцию и повторное использование на новый уровень, позволяя нам определять непримитивные типы данных и поддерживая объектно-ориентированное программирование. Это похоже на создание собственного словаря, чтобы машина могла его понять.
И запустить вашу Java-программу? Это так же просто, как скомпилировать его с помощью команды javac и запустить с помощью java. Это все равно, что дать вашей программе собственную взлетно-посадочную полосу для выхода в цифровой мир.
Итак, вот и все — основы программирования на Java. Теперь идите вперед и создайте магию кода!
Привет, если вы в восторге от структур данных и хотите сразу приступить к кодированию, я настоятельно рекомендую проверить LeetCode! Они предлагают курс для начинающих, который идеально подходит для начала, и я даже скину вам ссылку. Задачи в этом курсе рассчитаны на новичков, поэтому вы сможете укрепить свою уверенность, решая их. И не волнуйтесь, как только вы справитесь с этими более простыми задачами, вы сможете постепенно переходить к более сложным, которые действительно проверят ваши навыки. Это как восхождение на гору, только вместо прекрасного вида на вершине вы получаете удовольствие от написания классного кода!
2235. Сложить два целых числа
Даны два целых числа num1 и num2, вернуть сумму двух целых чисел.
Пример 1:
Input: num1 = 12, num2 = 5 Output: 17 Explanation: num1 is 12, num2 is 5, and their sum is 12 + 5 = 17, so 17 is returned.
Пример 2:
Input: num1 = -10, num2 = 4 Output: -6 Explanation: num1 + num2 = -6, so -6 is returned.
Решение
Это решение занимает 6мб памяти, попробуем более эффективное
class Solution {
public:
int sum(int num1, int num2) {
int sum;
sum = num1 + num2;
return sum;
}
};
Следующее решение превосходит 63,82%
class Solution {
public:
int sum(int num1, int num2) {
return num1 + num2;
}
};
2236. Корень равен сумме детей.
Вам дан корень бинарного дерева, состоящего ровно из 3 узлов: корня, его левого дочернего элемента и его правого дочернего элемента.
Возвращает true, если значение корня равно сумме значений двух его дочерних элементов, или false в противном случае.
Пример 1:
Input: root = [10,4,6] Output: true Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively. 10 is equal to 4 + 6, so we return true.
Пример 2:
Input: root = [5,3,1] Output: false Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively. 5 is not equal to 3 + 1, so we return false.
Решение
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean checkTree(TreeNode root) {
return root.right.val + root.left.val == root.val;
}
}
Объяснение
В данной задаче нам предлагается определить, равно ли значение корневого узла бинарного дерева сумме значений его левого и правого потомков. Нам дан корневой узел бинарного дерева, состоящего ровно из трех узлов: корня, его левого дочернего элемента и его правого дочернего элемента.
Решение проблемы простое. Нам просто нужно проверить, равно ли значение корневого узла сумме значений его левого и правого потомков. Если это так, мы возвращаем true; в противном случае мы возвращаем false.
В предоставленном решении нам дан класс TreeNode, представляющий узел в двоичном дереве. Нам также дан метод checkTree, который принимает корневой узел бинарного дерева в качестве входных данных и возвращает логическое значение.
Метод checkTree просто проверяет, равно ли значение корневого узла сумме значений его левого и правого дочерних элементов, используя следующую строку кода:
return root.right.val + root.left.val == root.val;
Если значение корневого узла равно сумме значений его левого и правого потомков, эта строка кода возвращает true. В противном случае возвращается false.
Обратите внимание, что это решение предполагает, что бинарное дерево имеет ровно три узла: корень, его левый дочерний элемент и его правый дочерний элемент. Если бинарное дерево имеет другую структуру, это решение может работать некорректно.
1480. Бегущая сумма 1d массива
Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = sum(nums[0]…nums[i]). Возвращает текущую сумму чисел.
Пример 1:
Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Пример 2:
Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Пример 3:
Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]
Ограничения:
1 <= nums.length <= 100010^6 <= nums[i] <= 10^6
class Solution {
public int[] runningSum(int[] nums) {
for(int i=1;i<nums.length;i++){
nums[i]=nums[i-1]+nums[i];
}
return nums;
}
}
Объяснение
Данная задача просит нас вычислить текущую сумму массива. Нам дан массив целых чисел nums и требуется вычислить массив runningSum таким образом, что runningSum[i] представляет собой сумму всех элементов nums до индекс i-th.
Решение проблемы простое. Мы можем вычислить массив runningSum за один проход через входной массив nums. Начиная со второго элемента массива nums, мы можем вычислить сумму предыдущих элементов и добавить текущий элемент, чтобы получить runningSum. Мы можем обновить сам массив nums для хранения значений runningSum, так как нам не нужны исходные значения nums после вычисления runningSum.
В предоставленном решении нам дан класс Solution с методом runningSum, который принимает массив целых чисел nums в качестве входных данных и возвращает массив целых чисел runningSum.
Метод runningSum вычисляет массив runningSum путем перебора входного массива nums, начиная со второго элемента. Для каждого элемента nums[i] мы добавляем к нему предыдущий элемент nums[i-1], чтобы получить runningSum. Мы обновляем сам массив nums значениями runningSum. Наконец, мы возвращаем массив nums, содержащий значения runningSum.
Предоставленное решение имеет временную сложность O(n) и пространственную сложность O(1), поскольку оно обновляет сам входной массив для хранения значений runningSum.
1672. Богатство самого богатого клиента
Вам задано m x n целочисленных счетов сетки, где account[i][j] — сумма денег i-го клиента в j-м банке. Верните богатство, которое есть у самого богатого покупателя.
Богатство клиента — это сумма денег, которую он имеет на всех своих банковских счетах. Самый богатый клиент — это клиент, который имеет максимальное богатство.
Пример 1:
Input: accounts = [[1,2,3],[3,2,1]] Output: 6 Explanation:1st customer has wealth = 1 + 2 + 3 = 6 2nd customer has wealth = 3 + 2 + 1 = 6 Both customers are considered the richest with a wealth of 6 each, so return 6.
Пример 2:
Input: accounts = [[1,5],[7,3],[3,5]] Output: 10 Explanation: 1st customer has wealth = 6 2nd customer has wealth = 10 3rd customer has wealth = 8 The 2nd customer is the richest with a wealth of 10.
Пример 3:
Input: accounts = [[2,8,7],[7,1,3],[1,9,5]] Output: 17
Решение
class Solution {
public int maximumWealth(int[][] accounts) {
int temp = 0;
int max = 0;
for(int i=0; i<accounts.length; i++)
{
for (int j=0; j < accounts[i].length; j++)
{
temp = temp + accounts[i][j];
}
if(temp>max)
{
max = temp;
}
temp = 0;
}
return max;
}
}
Объяснение
В данной задаче предлагается найти самого богатого клиента в банке. Богатство клиента — это сумма денег, которую он имеет на всех своих банковских счетах. Проблему можно решить, перебирая каждого клиента и суммируя остатки на его счетах, чтобы вычислить их богатство.
Решение начинается с инициализации двух переменных temp и max нулями. Вложенный цикл используется для перебора учетных записей каждого клиента и вычисления их богатства путем сложения остатков на их счетах. В переменной temp хранится сумма остатков на счетах текущего клиента. Внешний цикл перебирает каждого клиента и вычисляет его богатство, а также проверяет, превышает ли вычисленное богатство максимальное вычисленное на данный момент богатство. Если это так, переменная max обновляется новым вычисленным богатством. Переменная temp обнуляется перед переходом к следующему клиенту. Наконец, функция возвращает переменную max, которая представляет богатство самого богатого клиента.
Временная сложность решения равна O(mn), где m и n — размерности массива accounts, поскольку нам нужно перебирать остатки на счетах каждого клиента. Объемная сложность решения равна O(1), так как мы используем постоянный объем дополнительного пространства только для хранения переменных temp и max.
1342. Количество шагов для уменьшения числа до нуля
Учитывая целое число, вернуть количество шагов, чтобы уменьшить его до нуля. За один шаг, если текущее число четное, вы должны разделить его на 2, в противном случае вы должны вычесть из него 1.
Пример 1:
Input: num = 14 Output: 6 Explanation: Step 1) 14 is even; divide by 2 and obtain 7. Step 2) 7 is odd; subtract 1 and obtain 6. Step 3) 6 is even; divide by 2 and obtain 3. Step 4) 3 is odd; subtract 1 and obtain 2. Step 5) 2 is even; divide by 2 and obtain 1. Step 6) 1 is odd; subtract 1 and obtain 0.
Пример 2:
Input: num = 8 Output: 4 Explanation: Step 1) 8 is even; divide by 2 and obtain 4. Step 2) 4 is even; divide by 2 and obtain 2. Step 3) 2 is even; divide by 2 and obtain 1. Step 4) 1 is odd; subtract 1 and obtain 0.
Пример 3:
Input: num = 123 Output: 12
Алгоритм
Попробуем написать алгоритм,
- Возьмите ввод
- Подумайте, четное оно или нечетное
- Если нечетно, то минус 1
- Если даже тогда сделать деление
- Повторяйте то же самое до тех пор, пока он не станет равным нулю, и выведите, сколько шагов потребовалось.
Код
class Solution {
public int numberOfSteps(int num) {
return helper(num,0); //helper function to pass no. of steps as an argument
}
int helper(int num,int steps){
if(num==0){
return steps; //if all the steps end and the no. finaaly becomes 0
}
if(num%2==0){ //for even number
return helper(num/2,steps+1);
}
else{ //for odd number
return helper(num-1,steps+1);
}
}
}
Объяснение
Данный код представляет собой решение на Java для нахождения количества шагов, необходимых для уменьшения заданного целого числа до нуля с использованием заданных правил.
Функция numberOfSteps принимает целое число num в качестве входных данных и возвращает целое число, представляющее количество шагов, необходимых для уменьшения num до нуля.
Вспомогательная функция — это рекурсивная функция, которая принимает два аргумента — num и steps. Аргумент num представляет текущее число, а аргумент steps представляет количество пройденных шагов.
Функция проверяет, равен ли аргумент num нулю. Если это так, функция возвращает аргумент steps, представляющий количество шагов, необходимых для уменьшения исходного num до нуля.
Если аргумент num четный, функция делит его на 2 и вызывает себя с новым значением num и steps+1. Если аргумент num нечетный, функция вычитает из него 1 и вызывает себя с новым значением num и steps+1.
Функция numberOfSteps вызывает функцию helper с начальным значением num и значением steps, равным 0. Она возвращает значение, возвращаемое функцией helper, которое представляет количество необходимых шагов. уменьшить num до нуля.
В целом решение использует рекурсивный подход для подсчета количества шагов, необходимых для уменьшения заданного целого числа до нуля.
876. Середина связанного списка
Учитывая заголовок односвязного списка, вернуть средний узел связанного списка. Если есть два средних узла, вернуть второй средний узел.
Пример 1:
Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.
Пример 2:
Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Решение
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode mid = head;
ListNode far = head;
while(far != null && far.next != null)
{
mid = mid.next;
far = far.next.next;
}
return mid;
}
}
Объяснение
Это Java-решение проблемы поиска среднего узла заданного односвязного списка. Вход — это связанный список, представленный его головным узлом, а выход — средний узел (узлы) связанного списка.
Решение работает с использованием двух указателей, один из которых называется mid, а другой — far. Оба указателя начинаются с начала связанного списка. Указатель mid перемещает один узел за раз, а указатель far перемещает два узла за раз. Таким образом, когда указатель far достигает конца связанного списка, указатель mid будет указывать на средний узел списка.
Цикл while продолжается до тех пор, пока far не равно нулю, а far.next не равно нулю. Если связанный список имеет нечетное количество узлов, указатель far в конечном итоге достигнет конца списка, а указатель mid будет указывать на средний узел. Если связанный список имеет четное количество узлов, указатель far достигнет конца списка на предпоследнем узле, а указатель mid будет указывать на второй средний узел.
После завершения цикла while указатель mid указывает на средний (или второй средний) узел связанного списка, поэтому он возвращается в качестве вывода.
383. Записка о выкупе
Имея две строки ransomNote и magazine, вернуть true если ransomNote можно составить, используя буквы из magazine и false иначе >.
Каждая буква в magazine может использоваться только один раз в ransomNote.
Пример 1:
Input: ransomNote = "a", magazine = "b" Output: false
Пример 2:
Input: ransomNote = "aa", magazine = "ab" Output: false
Пример 3:
Input: ransomNote = "aa", magazine = "aab" Output: true
Решение
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length())
return false;
// creating a counter
int [] counter = new int[26];
// Converting into array
for (char c : magazine.toCharArray())
{
counter [c-'a']++;
}
// checking if ransomNote can be constructed by using the letters from magazine
for (char c : ransomNote.toCharArray())
{
if (counter [c-'a'] == 0)
return false;
counter [c-'a']--;
}
return true;
}
}
Объяснение
Это Java-решение проблемы определения того, может ли данная записка о выкупе быть составлена с использованием писем из данного журнала. Входные данные — две строки, ransomNote и magazine, а выходные данные — логическое значение, указывающее, можно ли составить записку о выкупе, используя буквы из журнала.
Решение работает, сначала проверяя, превышает ли длина строки ransomNote длину строки magazine. Если это так, то составить записку о выкупе по письмам из журнала невозможно, поэтому функция возвращает false.
Если длина ransomNote меньше или равна длине magazine, функция создает массив счетчиков, где каждый элемент массива соответствует букве алфавита (от a до z). Затем строка magazine преобразуется в массив символов, а счетчики в массиве counter увеличиваются при каждом появлении символа в строке magazine.
Затем функция проверяет каждый символ в строке ransomNote, чтобы определить, можно ли его составить, используя буквы из строки magazine. Если символ в примечании о выкупе не найден в строке magazine или если счетчик этого символа в массиве counter равен нулю, то невозможно составить примечание о выкупе, используя буквы из строки журнал, поэтому функция возвращает false. В противном случае счетчик для этого символа в массиве counter уменьшается, так как он использовался для построения записки о выкупе.
Если все символы в строке ransomNote могут быть составлены из букв строки magazine, функция возвращает true.
Заключение
Что ж, это было настоящее путешествие! От изучения основ алгоритмов и структур данных до изучения синтаксиса Java мы охватили много вопросов. Но мы не остановились на этом — мы также поделились некоторыми фантастическими решениями и пояснениями LeetCode, чтобы помочь новичкам справиться с этими сложными задачами программирования.
Мы надеемся, что вы нашли эту статью информативной, увлекательной и, возможно, даже немного забавной. Помните, что обучение кодированию — это бесконечное путешествие, и каждый шаг, который вы делаете, приближает вас к вашим целям. Так что продолжайте практиковаться, продолжайте экспериментировать и продолжайте изучать новые инструменты и техники. И самое главное, никогда не забывайте немного повеселиться в пути!
Кто знает, может быть, однажды вы вспомните эту статью как отправную точку своей удивительной карьеры программиста. Нам не терпится увидеть, что вы создадите!
Присоединяйтесь к команде Teen Different в нашем Инстаграме. Ознакомьтесь с нашими последними статьями, советами и рекомендациями по кибербезопасности, производительности, информатике и многому другому. Не пропустите веселье, следуйте за нами сегодня!
Мы приветствуем ответственное использование вспомогательных технологий искусственного интеллекта на Medium. Чтобы повысить прозрачность и помочь сформировать ожидания читателей, мы требуем, чтобы любая история, созданная с помощью ИИ, была четко обозначена как таковая.
