В этой части я буду решать новые задачи из LeetCode и CodeWars и также расскажу про нововведения в конфигурации Algo1C.
-------------------------------------------------------------
-------------------------------------------------------------
Заранее благодарю за чтение и желаю продуктивно провести время! Если после прочтения возникнут вопросы, пожелания или предложения, то буду рад ознакомиться со всем в комментариях!
Предисловие:
В первой части я начал своё изучение алгоритмических задач. Сегодня я продолжу эту тему, ознакомлюсь сам и также ознакомлю вас с новыми задачами и их решениями. И также перед началом чтения решения задачи, хочу призвать каждого к самостоятельному решению задачи, чтобы после вы могли сравнить своё решение с моим и обсудить это в комментариях. Буду рад послушать ваше мнение!
Давайте, приступим!
-------------------------------------------------------------
Новое в конфигурации 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 * 104
s 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" (Скользящее окно)?
Этот алгоритм подразумевает имитацию окна, которое, в случае в массивом, будет представлено в виде дистанции между двумя индексами, а также последующее увеличение ширины этого "окна" и его движение.
В итоге вместо того чтобы итерировать каждый элемент массива и затем в его итерации итерировать этот же массив, мы будем иметь ограниченное количество итераций главного массива. В случае если массив гигантский, это может сильно выручить, согласитесь. В целом суть алгоритмов ведь в том чтобы сокращать расход ресурсов.
Заключение:
Задача мне показалась весьма простой и интересной. Мне всегда нравилось работать со строками и подстроками в них! Да и в целом алгоритм скользящего окна тоже весьма занимательный!
-------------------------------------------------------------
-------------------------------------------------------------
Задача 2
- Платформа: Leetcode
- Название задачи: 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
Сортировать объединенный массив в принципе нет необходимости, требуют только медиану!
Решение:
Так как исходные массивы в ответе нам не нужны, мы можем себе позволить изменять их. Просто перебираем элементы одного из массивов и добавляем их во второй массив. Потом берем второй массив, перебираем все элементы прибавляя их к одной из переменных. Затем просто делим число в этой переменной на количество элементов массива!
Заключение:
Задачи с массивами и сортировками данных всегда самые интересные. Когда нибудь видели видео с визуализациями сортировок? Советую посмотреть если нет, очень залипательно!
-------------------------------------------------------------
-------------------------------------------------------------
Задача 3
- Платформа: Codewars
- Название задачи: Flick Switch
- Оригинальное описание задачи:
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", чтобы оперативно поменять флаг.
Заключение:
Интересная задача, на самом деле. Изменение поведения обработки данных в процессе обработки этих же данных выглядит очень забавно!
-------------------------------------------------------------
-------------------------------------------------------------
Задача 4
- Платформа: Codewars
- Название задачи: Pillars
- Оригинальное описание задачи:
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. Далее циклом проходим по каждому столбу и прибавляем к ответу дистанцию между столбами, переводя это в сантиметры. И после просто прибавляем ширину всех внутренних столбов. В итоге получаем чистую дистанцию между первым и последним столбом в сантиметрах!
Заключение:
Теоретически весьма полезная задача. В отличие от тех задач что мы уже решали, это решение в принципе можно применить для каких-то жизненных вопросов (если вы занимаетесь установкой столбов, например...)
-------------------------------------------------------------
-------------------------------------------------------------
Заключение:
Ну что ж, пока на этом всё, надеюсь, статья была увлекательной для вас, благодарю за внимание. Подключайтесь к решению алгоритмических задач вместе со мной, делитесь вашим мнением и решениями в комментариях! Увидимся в новой статье!