Йо, меня зовут Наби. Заранее благодарю за чтение и желаю продуктивно провести время! Если после прочтения возникнут вопросы, пожелания или предложения, то буду рад ознакомиться со всем в комментариях!
Предисловие:
В первой части я начал своё изучение алгоритмических задач. Сегодня я продолжу эту тему, ознакомлюсь сам и также ознакомлю вас с новыми задачами и их решениями. И также перед началом чтения решения задачи, хочу призвать каждого к самостоятельному решению задачи, чтобы после вы могли сравнить своё решение с моим и обсудить это в комментариях. Буду рад послушать ваше мнение! Давайте, приступим!
Новое в конфигурации Algo1C:
Актуальную версию конфигурации вы можете загрузить здесь (Нажмите на строку)
- 0.2 : Исправлена ошибка при выводе результата (Отдельная благодарность SAShikutkin)
Решение задач:
Задача 1
Платформа: Leetcode
Название задачи: Longest substring without repeating characters
Ссылка на задачу: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/ (Нажмите на строку)
Оригинальное описание задачи:
Given a string s, find the length of the longest substring without repeating characters
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.
Пояснение:
Суть задачи заключается в том чтобы из данной строки получить длину самой длинной подстроки без повторяющихся символов.
Например:
Дана строка "abcabcbb", в ней есть 10 уникальных подстрок, таких как:
"a", "b", "c", "ab", "bc", "ca", "cb", "abc", "bca", "cab"
У нас есть строки с длиной 1, 2 и 3. Следовательно самая большая длина какой-либо подстроки у нас 3. Ответом также будет просто число 3
Решение:
Слышали когда-нибудь про алгоритм "Sliding Window" (Скользящее окно)?
Этот алгоритм подразумевает имитацию окна, которое, в случае в массивом, будет представлено в виде дистанции между двумя индексами, а также последующее увеличение ширины этого "окна" и его движение.
В итоге вместо того чтобы итерировать каждый элемент массива и затем в его итерации итерировать этот же массив, мы будем иметь ограниченное количество итераций главного массива. В случае если массив гигантский, это может сильно выручить, согласитесь. В целом суть алгоритмов ведь в том чтобы сокращать расход ресурсов.
Вот иллюстрация алгоритма:
Давайте попробуем описать этот алгоритм 1Совским кодом!
ВходнаяСтрока = "abcabcbb";
//
Ответ = 0;
Левый = 0;
Правый = 1;
//
Пока Левый <> Правый Цикл
ПодСтрока = "";
Для НомерСтроки = Левый По Правый-1 Цикл
Если НомерСтроки < СтрДлина(ВходнаяСтрока) Тогда
ПодСтрока = ПодСтрока+Сред(ВходнаяСтрока,НомерСтроки,1);
КонецЕсли;
КонецЦикла;
//++Проверка на уникальность
РезультатПроверкиНаУникальность = Истина;
Для ПодНомерСтроки = 1 По СтрДлина(ПодСтрока) Цикл
Если СтрЧислоВхождений(ПодСтрока,Сред(ПодСтрока,ПодНомерСтроки,1)) > 1 Тогда
РезультатПроверкиНаУникальность = Ложь;
КонецЕсли;
КонецЦикла;
//--Проверка на уникальность
Если РезультатПроверкиНаУникальность Тогда
Если СтрДлина(ПодСтрока) > Ответ Тогда
Ответ = СтрДлина(ПодСтрока);
КонецЕсли;
Если СтрДлина(ВходнаяСтрока) > Правый Тогда
Правый = Правый + 1;
Иначе
Левый = Левый + 1;
КонецЕсли;
Иначе
Левый = Левый + 1;
КонецЕсли;
КонецЦикла;
//
Вывод = Ответ;
Заключение:
Задача мне показалась весьма простой и интересной. Мне всегда нравилось работать со строками и подстроками в них! Да и в целом алгоритм скользящего окна тоже весьма занимательный!
Задача 2
Платформа: Leetcode
Название задачи: Median of two sorted arrays
Ссылка на задачу: https://leetcode.com/problems/median-of-two-sorted-arrays/ (Нажмите на строку)
Оригинальное описание задачи:
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Пояснение:
По условию задачи нам даны 2 отсортированных массива, длина которых не обязательно должна быть одинакова. Из этих двух массивов нам надо получить один массив и вернуть в качестве результата медиану числового ряда
Например:
Даны два массива [1,3] и [2], необходимо объединить их и вычислить медиану числового ряда, что очень легкосделать. Просто прибавляем все элементы и делим на количество элементов, в данном случае это будет:
| 1 + 3 + 2 = 6
| 6/3 = 2
Сортировать объединенный массив в принципе нет необходимости, требуют только медиану!
Решение:
Так как исходные массивы в ответе нам не нужны, мы можем себе позволить изменять их. Просто перебираем элементы одного из массивов и добавляем их во второй массив. Потом берем второй массив, перебираем все элементы прибавляя их к одной из переменных. Затем просто делим число в этой переменной на количество элементов массива!
ПервыйМассив = Новый Массив;
ПервыйМассив.Добавить(1);
ПервыйМассив.Добавить(2);
//
ВторойМассив = Новый Массив;
ВторойМассив.Добавить(3);
ВторойМассив.Добавить(4);
//
Для Каждого Стр Из ВторойМассив Цикл
ПервыйМассив.Добавить(Стр);
КонецЦикла;
//
СуммаЧисел = 0;
Медиана = 0;
//
Для Каждого Стр Из ПервыйМассив Цикл
СуммаЧисел = СуммаЧисел + Стр;
КонецЦикла;
//
Медиана = СуммаЧисел / ПервыйМассив.Количество();
//
Вывод = Медиана;
Заключение:
Задачи с массивами и сортировками данных всегда самые интересные. Когда нибудь видели видео с визуализациями сортировок? Советую посмотреть если нет, очень залипательно!
Задача 3
Платформа: Codewars
Название задачи: Flick Switch
Ссылка на задачу: https://www.codewars.com/kata/64fbfe2618692c2018ebbddb (Нажмите на строку)
Оригинальное описание задачи:
Create a function that always returns True/true for every item in a given list.
However, if an element is the word 'flick', switch to always returning the opposite boolean value.
Examples
['codewars', 'flick', 'code', 'wars'] e42; [True, False, False, False]
['flick', 'chocolate', 'adventure', 'sunshine'] e42; [False, False, False, False]
['bicycle', 'jarmony', 'flick', 'sheep', 'flick'] e42; [True, True, False, False, True]
Notes
"flick" will always be given in lowercase.
A list may contain multiple flicks.
Switch the boolean value on the same element as the flick itself.
Пояснение:
Что от нас требуется? Нам необходимо обработать данный массив из строк и заполнить новый массив значениями типа Булево. В итоге должен получиться массив такой же длины но с Булево значениями. Как понять когда какое значение записывать? Всё просто. Предположим есть флаг, который говорит нам всегда записывать "Истина", если флаг "Истина", ну и само собой наоборот. Следовательно в процессе итерации оригинального массива, мы должны записывать в новый массив значение из флага. Есть одно Но. Каждый раз когда мы будем встречать строку "flick", мы поменяем значение флага на противоположное.
Например:
Дан массив строк ['codewars', 'flick', 'code', 'wars'], наш флаг изначально Истина. Следовательно первое значение в новом массиве будет Истина, далее встретили "flick", поменяли флаг на противоположный, значит второе значение уже Ложь, третье значение тоже Ложь ибо флаг всё ещё Ложь, ну и последнее значение тоже Ложь по той же причине.
В итоге получим массив [Истина,Ложь,Ложь,Ложь]
Решение:
Суть проста. Как я и говорил ранее, создаем флаг для хранения Булево значения, затем перебираем все элементы из входного массива, записывая при этом значение флага в новый массив. Но перед записью обязательно проверяем текущее значение массива на слово "flick", чтобы оперативно поменять флаг.
ВходныеДанные = Новый Массив;
ВходныеДанные.Добавить("codewars");
ВходныеДанные.Добавить("flick");
ВходныеДанные.Добавить("code");
ВходныеДанные.Добавить("wars");
//
Флаг = Истина;
ВыходныеДанные = Новый Массив;
//
Для Каждого Стр Из ВходныеДанные Цикл
Если Стр = "flick" Тогда
Флаг = Не Флаг;
КонецЕсли;
ВыходныеДанные.Добавить(Флаг);
КонецЦикла;
//
Вывод = "[";
Для Каждого Стр Из ВыходныеДанные Цикл
Вывод = Вывод + Строка(Стр) + ",";
КонецЦикла;
Вывод = Лев(Вывод,СтрДлина(Вывод)-1) + "]";
Заключение:
Интересная задача, на самом деле. Изменение поведения обработки данных в процессе обработки этих же данных выглядит очень забавно!
Задача 4
Платформа: Codewars
Название задачи: Pillars
Ссылка на задачу: https://www.codewars.com/kata/5bb0c58f484fcd170700063d (Нажмите на строку)
Оригинальное описание задачи:
There are pillars near the road. The distance between the pillars is the same and the width of the pillars is the same. Your function accepts three arguments:
- number of pillars (≥ 1);
- distance between pillars (10 - 30 meters);
- width of the pillar (10 - 50 centimeters).
Calculate the distance between the first and the last pillar in centimeters (without the width of the first and last pillar).
Пояснение:
Дана дорога со столбами. Дистанция между столбами и ширина столбов всегда одинаковы. Цель задачи заключается в том чтобы найти дистанцию между первым и последним столбом. В качестве входных данных нам дают количество столбов, ширину столбов и дистанцию между столбами. В качестве единицы измерения у дистанции между столбами используются метры а у ширины столба сантиметры, в качестве ответа нам необходимо будет вернуть всё в сантиметрах. Также не нужно будет учитывать ширину первого и последнего столба. Нужно вычислить чисто дистанцию между ними!
Например:
Входные данные:
- Количество столбов = 3 штуки
- Ширина столба = 1 метр
- Дистанция между столбами = 1 метр
В итоге получается что есть три столба, между первым и вторым столбом 1 метр, между вторым и третьим тоже 1 метр, плюс прибавляем ширину среднего столба. Итого получаем 3 метра. Обязательно переводим в сантиметры, получаем ответ 300 сантиметров! Всё звучит очень просто, попробуем решить?
Решение:
В первую очередь проверяем количество столбов. Нет смысла что-либо вычислять если столб всего один. Далее нам нужно вычислить количество внутренних столбов, для этого из количества столбов просто вычитаем 2. Далее циклом проходим по каждому столбу и прибавляем к ответу дистанцию между столбами, переводя это в сантиметры. И после просто прибавляем ширину всех внутренних столбов. В итоге получаем чистую дистанцию между первым и последним столбом в сантиметрах!
КоличествоСтолбов = 2;
ДистанцияМеждуСтолбами = 10;
ШиринаСтолба = 10;
//
Ответ = 0;
Если КоличествоСтолбов <=1 Тогда
Ответ = 0;
Иначе
ВнутренниеСтолбы = КоличествоСтолбов - 2;
Первый = Истина;
Для НомерСтроки = 0 По КоличествоСтолбов-1 Цикл
Если Первый Тогда
Первый = Ложь;
Иначе
Ответ = Ответ + ДистанцияМеждуСтолбами*100
КонецЕсли;
КонецЦикла;
Ответ = Ответ + ВнутренниеСтолбы*ШиринаСтолба;
КонецЕсли;
//
Вывод = Ответ;
Заключение:
Теоретически весьма полезная задача. В отличие от тех задач что мы уже решали, это решение в принципе можно применить для каких-то жизненных вопросов (если вы занимаетесь установкой столбов, например...)
Заключение:
Платформа: Leetcode
Название задачи: Longest substring without repeating characters
Ссылка на задачу: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/ (Нажмите на строку)
Оригинальное описание задачи:
Given a string
s, find the length of the longest substring without repeating charactersExample 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Пояснение:
Суть задачи заключается в том чтобы из данной строки получить длину самой длинной подстроки без повторяющихся символов.
Например:
Дана строка "abcabcbb", в ней есть 10 уникальных подстрок, таких как:
"a", "b", "c", "ab", "bc", "ca", "cb", "abc", "bca", "cab"
У нас есть строки с длиной 1, 2 и 3. Следовательно самая большая длина какой-либо подстроки у нас 3. Ответом также будет просто число 3
Решение:
Слышали когда-нибудь про алгоритм "Sliding Window" (Скользящее окно)?
Этот алгоритм подразумевает имитацию окна, которое, в случае в массивом, будет представлено в виде дистанции между двумя индексами, а также последующее увеличение ширины этого "окна" и его движение.
В итоге вместо того чтобы итерировать каждый элемент массива и затем в его итерации итерировать этот же массив, мы будем иметь ограниченное количество итераций главного массива. В случае если массив гигантский, это может сильно выручить, согласитесь. В целом суть алгоритмов ведь в том чтобы сокращать расход ресурсов.
Вот иллюстрация алгоритма:
Давайте попробуем описать этот алгоритм 1Совским кодом!
ВходнаяСтрока = "abcabcbb";
//
Ответ = 0;
Левый = 0;
Правый = 1;
//
Пока Левый <> Правый Цикл
ПодСтрока = "";
Для НомерСтроки = Левый По Правый-1 Цикл
Если НомерСтроки < СтрДлина(ВходнаяСтрока) Тогда
ПодСтрока = ПодСтрока+Сред(ВходнаяСтрока,НомерСтроки,1);
КонецЕсли;
КонецЦикла;
//++Проверка на уникальность
РезультатПроверкиНаУникальность = Истина;
Для ПодНомерСтроки = 1 По СтрДлина(ПодСтрока) Цикл
Если СтрЧислоВхождений(ПодСтрока,Сред(ПодСтрока,ПодНомерСтроки,1)) > 1 Тогда
РезультатПроверкиНаУникальность = Ложь;
КонецЕсли;
КонецЦикла;
//--Проверка на уникальность
Если РезультатПроверкиНаУникальность Тогда
Если СтрДлина(ПодСтрока) > Ответ Тогда
Ответ = СтрДлина(ПодСтрока);
КонецЕсли;
Если СтрДлина(ВходнаяСтрока) > Правый Тогда
Правый = Правый + 1;
Иначе
Левый = Левый + 1;
КонецЕсли;
Иначе
Левый = Левый + 1;
КонецЕсли;
КонецЦикла;
//
Вывод = Ответ;
Заключение:
Задача мне показалась весьма простой и интересной. Мне всегда нравилось работать со строками и подстроками в них! Да и в целом алгоритм скользящего окна тоже весьма занимательный!
Платформа: Leetcode
Название задачи: Median of two sorted arrays
Ссылка на задачу: https://leetcode.com/problems/median-of-two-sorted-arrays/ (Нажмите на строку)
Оригинальное описание задачи:
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Пояснение:
По условию задачи нам даны 2 отсортированных массива, длина которых не обязательно должна быть одинакова. Из этих двух массивов нам надо получить один массив и вернуть в качестве результата медиану числового ряда
Например:
Даны два массива [1,3] и [2], необходимо объединить их и вычислить медиану числового ряда, что очень легкосделать. Просто прибавляем все элементы и делим на количество элементов, в данном случае это будет:
| 1 + 3 + 2 = 6
| 6/3 = 2
Сортировать объединенный массив в принципе нет необходимости, требуют только медиану!
Решение:
Так как исходные массивы в ответе нам не нужны, мы можем себе позволить изменять их. Просто перебираем элементы одного из массивов и добавляем их во второй массив. Потом берем второй массив, перебираем все элементы прибавляя их к одной из переменных. Затем просто делим число в этой переменной на количество элементов массива!
ПервыйМассив = Новый Массив;
ПервыйМассив.Добавить(1);
ПервыйМассив.Добавить(2);
//
ВторойМассив = Новый Массив;
ВторойМассив.Добавить(3);
ВторойМассив.Добавить(4);
//
Для Каждого Стр Из ВторойМассив Цикл
ПервыйМассив.Добавить(Стр);
КонецЦикла;
//
СуммаЧисел = 0;
Медиана = 0;
//
Для Каждого Стр Из ПервыйМассив Цикл
СуммаЧисел = СуммаЧисел + Стр;
КонецЦикла;
//
Медиана = СуммаЧисел / ПервыйМассив.Количество();
//
Вывод = Медиана;
Заключение:
Задачи с массивами и сортировками данных всегда самые интересные. Когда нибудь видели видео с визуализациями сортировок? Советую посмотреть если нет, очень залипательно!
Платформа: Codewars
Название задачи: Flick Switch
Ссылка на задачу: https://www.codewars.com/kata/64fbfe2618692c2018ebbddb (Нажмите на строку)
Оригинальное описание задачи:
Create a function that always returns True/true for every item in a given list.
However, if an element is the word 'flick', switch to always returning the opposite boolean value.Examples
['codewars', 'flick', 'code', 'wars'] e42; [True, False, False, False]
['flick', 'chocolate', 'adventure', 'sunshine'] e42; [False, False, False, False]
['bicycle', 'jarmony', 'flick', 'sheep', 'flick'] e42; [True, True, False, False, True]
Notes
"flick" will always be given in lowercase.
A list may contain multiple flicks.
Switch the boolean value on the same element as the flick itself.
Пояснение:
Что от нас требуется? Нам необходимо обработать данный массив из строк и заполнить новый массив значениями типа Булево. В итоге должен получиться массив такой же длины но с Булево значениями. Как понять когда какое значение записывать? Всё просто. Предположим есть флаг, который говорит нам всегда записывать "Истина", если флаг "Истина", ну и само собой наоборот. Следовательно в процессе итерации оригинального массива, мы должны записывать в новый массив значение из флага. Есть одно Но. Каждый раз когда мы будем встречать строку "flick", мы поменяем значение флага на противоположное.
Например:
Дан массив строк ['codewars', 'flick', 'code', 'wars'], наш флаг изначально Истина. Следовательно первое значение в новом массиве будет Истина, далее встретили "flick", поменяли флаг на противоположный, значит второе значение уже Ложь, третье значение тоже Ложь ибо флаг всё ещё Ложь, ну и последнее значение тоже Ложь по той же причине.
В итоге получим массив [Истина,Ложь,Ложь,Ложь]
Решение:
Суть проста. Как я и говорил ранее, создаем флаг для хранения Булево значения, затем перебираем все элементы из входного массива, записывая при этом значение флага в новый массив. Но перед записью обязательно проверяем текущее значение массива на слово "flick", чтобы оперативно поменять флаг.
ВходныеДанные = Новый Массив;
ВходныеДанные.Добавить("codewars");
ВходныеДанные.Добавить("flick");
ВходныеДанные.Добавить("code");
ВходныеДанные.Добавить("wars");
//
Флаг = Истина;
ВыходныеДанные = Новый Массив;
//
Для Каждого Стр Из ВходныеДанные Цикл
Если Стр = "flick" Тогда
Флаг = Не Флаг;
КонецЕсли;
ВыходныеДанные.Добавить(Флаг);
КонецЦикла;
//
Вывод = "[";
Для Каждого Стр Из ВыходныеДанные Цикл
Вывод = Вывод + Строка(Стр) + ",";
КонецЦикла;
Вывод = Лев(Вывод,СтрДлина(Вывод)-1) + "]";
Заключение:
Интересная задача, на самом деле. Изменение поведения обработки данных в процессе обработки этих же данных выглядит очень забавно!
Платформа: Codewars
Название задачи: Pillars
Ссылка на задачу: https://www.codewars.com/kata/5bb0c58f484fcd170700063d (Нажмите на строку)
Оригинальное описание задачи:
There are pillars near the road. The distance between the pillars is the same and the width of the pillars is the same. Your function accepts three arguments:
- number of pillars (≥ 1);
- distance between pillars (10 - 30 meters);
- width of the pillar (10 - 50 centimeters).
Calculate the distance between the first and the last pillar in centimeters (without the width of the first and last pillar).
Пояснение:
Дана дорога со столбами. Дистанция между столбами и ширина столбов всегда одинаковы. Цель задачи заключается в том чтобы найти дистанцию между первым и последним столбом. В качестве входных данных нам дают количество столбов, ширину столбов и дистанцию между столбами. В качестве единицы измерения у дистанции между столбами используются метры а у ширины столба сантиметры, в качестве ответа нам необходимо будет вернуть всё в сантиметрах. Также не нужно будет учитывать ширину первого и последнего столба. Нужно вычислить чисто дистанцию между ними!
Например:
Входные данные:
- Количество столбов = 3 штуки
- Ширина столба = 1 метр
- Дистанция между столбами = 1 метр
В итоге получается что есть три столба, между первым и вторым столбом 1 метр, между вторым и третьим тоже 1 метр, плюс прибавляем ширину среднего столба. Итого получаем 3 метра. Обязательно переводим в сантиметры, получаем ответ 300 сантиметров! Всё звучит очень просто, попробуем решить?
Решение:
В первую очередь проверяем количество столбов. Нет смысла что-либо вычислять если столб всего один. Далее нам нужно вычислить количество внутренних столбов, для этого из количества столбов просто вычитаем 2. Далее циклом проходим по каждому столбу и прибавляем к ответу дистанцию между столбами, переводя это в сантиметры. И после просто прибавляем ширину всех внутренних столбов. В итоге получаем чистую дистанцию между первым и последним столбом в сантиметрах!
КоличествоСтолбов = 2;
ДистанцияМеждуСтолбами = 10;
ШиринаСтолба = 10;
//
Ответ = 0;
Если КоличествоСтолбов <=1 Тогда
Ответ = 0;
Иначе
ВнутренниеСтолбы = КоличествоСтолбов - 2;
Первый = Истина;
Для НомерСтроки = 0 По КоличествоСтолбов-1 Цикл
Если Первый Тогда
Первый = Ложь;
Иначе
Ответ = Ответ + ДистанцияМеждуСтолбами*100
КонецЕсли;
КонецЦикла;
Ответ = Ответ + ВнутренниеСтолбы*ШиринаСтолба;
КонецЕсли;
//
Вывод = Ответ;
Заключение:
Теоретически весьма полезная задача. В отличие от тех задач что мы уже решали, это решение в принципе можно применить для каких-то жизненных вопросов (если вы занимаетесь установкой столбов, например...)
Ну что ж, пока на этом всё, надеюсь, статья была увлекательной для вас, благодарю за внимание. Подключайтесь к решению алгоритмических задач вместе со мной, делитесь вашим мнением и решениями в комментариях! Увидимся в новой статье!
