Платформа: 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" (Скользящее окно)?
Этот алгоритм подразумевает имитацию окна, которое, в случае в массивом, будет представлено в виде дистанции между двумя индексами, а также последующее увеличение ширины этого "окна" и его движение.
В итоге вместо того чтобы итерировать каждый элемент массива и затем в его итерации итерировать этот же массив, мы будем иметь ограниченное количество итераций главного массива. В случае если массив гигантский, это может сильно выручить, согласитесь. В целом суть алгоритмов ведь в том чтобы сокращать расход ресурсов.

Вот иллюстрация алгоритма:

Давайте попробуем описать этот алгоритм 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:

1. number of pillars (≥ 1);
2. distance between pillars (10 - 30 meters);
3. 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
		КонецЕсли;
	КонецЦикла;
	Ответ = Ответ + ВнутренниеСтолбы*ШиринаСтолба;
КонецЕсли;
//
Вывод = Ответ;

Заключение:

Теоретически весьма полезная задача. В отличие от тех задач что мы уже решали, это решение в принципе можно применить для каких-то жизненных вопросов (если вы занимаетесь установкой столбов, например...)