Задача: 142. Linked List Cycle II
Сложность: medium

Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.
Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.
Не модифицируйте связный список.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

👨‍💻 Алгоритм:

1⃣Инициализация и начало обхода:
Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов.
Начните обход со связного списка, перемещая узел на один шаг за раз.

2⃣Проверка на наличие узла в множестве:
Для каждого посещенного узла проверьте, содержится ли он уже в множестве nodes_seen.
Если узел найден в множестве, это означает, что был найден цикл. Верните текущий узел как точку входа в цикл.

3⃣Добавление узла в множество или завершение обхода:
Если узел не найден в nodes_seen, добавьте его в множество и перейдите к следующему узлу.
Если узел становится равным null (конец списка), верните null. В списке нет цикла, так как в случае наличия цикла вы бы застряли в петле и не достигли бы конца списка.

😎 Решение:

class ListNode {
    public $val;
    public $next;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function detectCycle($head) {
    $nodesSeen = [];
    $node = $head;
    while ($node !== null) {
        if (in_array($node, $nodesSeen, true)) {
            return $node;
        } else {
            $nodesSeen[] = $node;
            $node = $node->next;
        }
    }
    return null;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1180. Count Substrings with Only One Distinct Letter
Сложность: easy

Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву.

Пример:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

👨‍💻 Алгоритм:

1⃣Инициализируйте целочисленную переменную total для подсчета количества подстрок, а также два указателя left и right, которые отмечают начало и конец подстроки, содержащей только одну уникальную букву.

2⃣Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки.

3⃣После завершения итерации добавьте к total количество подстрок для последнего сегмента, если он не был учтен. Верните значение total.

😎 Решение:

class Solution {
    function countLetters($S) {
        $total = 0;
        $left = 0;

        for ($right = 0; $right <= strlen($S); $right++) {
            if ($right == strlen($S) || $S[$left] != $S[$right]) {
                $lenSubstring = $right - $left;
                $total += (1 + $lenSubstring) * $lenSubstring / 2;
                $left = $right;
            }
        }
        return $total;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 686. Repeated String Match
Сложность: medium

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

👨‍💻 Алгоритм:

1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1.

😎 Решение:

class Solution {
    function repeatedStringMatch($A, $B) {
        $q = 1;
        $S = $A;
        while (strlen($S) < strlen($B)) {
            $S .= $A;
            $q++;
        }
        if (strpos($S, $B) !== false) return $q;
        if (strpos($S . $A, $B) !== false) return $q + 1;
        return -1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 468. Validate IP Address
Сложность: medium

Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "192.168@1.1" являются недопустимыми IPv4-адресами.
Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.

Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

👨‍💻 Алгоритм:

1⃣Для проверки адреса IPv4:
Разделить IP на четыре части по разделителю ".".
Проверить каждую подстроку:
Является ли она целым числом между 0 и 255.
Не содержит ли она ведущих нулей (исключение — число "0").

2⃣Для проверки адреса IPv6:
Разделить IP на восемь частей по разделителю ":".
Проверить каждую подстроку:
Является ли она шестнадцатеричным числом длиной от 1 до 4 символов.

3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither".

😎 Решение:

class Solution {
    public function validateIPv4($IP) {
        $nums = explode('.', $IP);
        if (count($nums) != 4) return "Neither";
        foreach ($nums as $x) {
            if (strlen($x) == 0 || strlen($x) > 3) return "Neither";
            if ($x[0] == '0' && strlen($x) != 1) return "Neither";
            if (!ctype_digit($x)) return "Neither";
            if (intval($x) > 255) return "Neither";
        }
        return "IPv4";
    }

    public function validateIPv6($IP) {
        $nums = explode(':', $IP);
        $hexdigits = "0123456789abcdefABCDEF";
        if (count($nums) != 8) return "Neither";
        foreach ($nums as $x) {
            if (strlen($x) == 0 || strlen($x) > 4) return "Neither";
            for ($i = 0; $i < strlen($x); $i++) {
                if (strpos($hexdigits, $x[$i]) === false) return "Neither";
            }
        }
        return "IPv6";
    }

    public function validIPAddress($IP) {
        if (substr_count($IP, '.') == 3) {
            return $this->validateIPv4($IP);
        } elseif (substr_count($IP, ':') == 7) {
            return $this->validateIPv6($IP);
        } else {
            return "Neither";
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 955. Delete Columns to Make Sorted II
Сложность: medium

Вам дан массив из n строк одинаковой длины. Мы можем выбрать любые индексы удаления и удалить все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef", "uvwxyz"] и индексы удаления {0, 2, 3}, то конечный массив после удаления будет ["bef", "vyz"]. Предположим, что мы выбрали набор индексов удаления answer таким образом, что после удаления конечный массив имеет элементы в лексикографическом порядке (т.е, strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Возвращает минимально возможное значение answer.length.

Пример:

Input: strs = ["ca","bb","ac"]
Output: 1

👨‍💻 Алгоритм:

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

2⃣Итеративно проверить каждую пару соседних строк для всех столбцов.
Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления.

3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.

😎 Решение:

function minDeletionSize($strs) {
    $n = count($strs);
    $m = strlen($strs[0]);
    $deleteCount = array_fill(0, $m, false);
    
    function isSorted($strs, $deleteCount) {
        $n = count($strs);
        $m = count($deleteCount);
        for ($i = 0; $i < $n - 1; $i++) {
            for ($j = 0; $j < $m; $j++) {
                if ($deleteCount[$j]) continue;
                if ($strs[$i][$j] > $strs[$i + 1][$j]) return false;
                if ($strs[$i][$j] < $strs[$i + 1][$j]) break;
            }
        }
        return true;
    }
    
    while (!isSorted($strs, $deleteCount)) {
        for ($j = 0; $j < $m; $j++) {
            if ($deleteCount[$j]) continue;
            for ($i = 0; $i < $n - 1; $i++) {
                if ($strs[$i][$j] > $strs[$i + 1][$j]) {
                    $deleteCount[$j] = true;
                    break;
                }
            }
            if ($deleteCount[$j]) break;
        }
    }
    
    return array_sum($deleteCount);
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram
Сложность: medium

Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.

Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s.

Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.

Пример:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

👨‍💻 Алгоритм:

1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count.

2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count.

3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s.

😎 Решение:

class Solution {
    public function minSteps($s, $t) {
        $count = array_fill(0, 26, 0);
        
        for ($i = 0; $i < strlen($s); $i++) {
            $count[ord($t[$i]) - ord('a')]++;
            $count[ord($s[$i]) - ord('a')]--;
        }

        $ans = 0;
        for ($i = 0; $i < 26; $i++) {
            $ans += max(0, $count[$i]);
        }

        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 949. Largest Time for Given Digits
Сложность: medium

Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.

Пример:

Input: arr = [1,2,3,4]
Output: "23:41"

👨‍💻 Алгоритм:

1⃣Перебрать все возможные перестановки массива arr.

2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.

3⃣Алгоритм
Перебрать все возможные перестановки массива arr.
Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.
Вернуть найденное время в формате "HH
". Если допустимое время не найдено, вернуть пустую строку.

😎 Решение:

function largestTimeFromDigits($arr) {
    sort($arr);
    $maxTime = -1;
    
    do {
        $hours = $arr[0] * 10 + $arr[1];
        $minutes = $arr[2] * 10 + $arr[3];
        if ($hours < 24 && $minutes < 60) {
            $maxTime = max($maxTime, $hours * 60 + $minutes);
        }
    } while (next_permutation($arr));
    
    if ($maxTime == -1) {
        return "";
    }
    
    return sprintf("%02d:%02d", $maxTime / 60, $maxTime % 60);
}

function next_permutation(&$arr) {
    $n = count($arr);
    for ($i = $n - 2; $i >= 0; $i--) {
        if ($arr[$i] < $arr[$i + 1]) {
            for ($j = $n - 1; $j > $i; $j--) {
                if ($arr[$j] > $arr[$i]) {
                    list($arr[$i], $arr[$j]) = [$arr[$j], $arr[$i]];
                    $left = array_slice($arr, 0, $i + 1);
                    $right = array_reverse(array_slice($arr, $i + 1));
                    $arr = array_merge($left, $right);
                    return true;
                }
            }
        }
    }
    return false;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

👨‍💻 Алгоритм:

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

2⃣Поиск максимальной суммы:
Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
    function maxSumTwoNoOverlap($nums, $firstLen, $secondLen) {
        return max($this->maxSumNonOverlap($nums, $firstLen, $secondLen), $this->maxSumNonOverlap(array_reverse($nums), $secondLen, $firstLen));
    }
    
    private function maxSumNonOverlap($nums, $firstLen, $secondLen) {
        $n = count($nums);
        $prefix = array_fill(0, $n + 1, 0);
        for ($i = 0; $i < $n; $i++) {
            $prefix[$i + 1] = $prefix[$i] + $nums[$i];
        }
        
        $maxFirst = array_fill(0, $n, 0);
        for ($i = $firstLen - 1; $i < $n; $i++) {
            $maxFirst[$i] = max(($i > 0 ? $maxFirst[$i - 1] : 0), $prefix[$i + 1] - $prefix[$i + 1 - $firstLen]);
        }
        
        $maxSecond = array_fill(0, $n, 0);
        for ($i = $secondLen - 1; $i < $n; $i++) {
            $maxSecond[$i] = max(($i > 0 ? $maxSecond[$i - 1] : 0), $prefix[$i + 1] - $prefix[$i + 1 - $secondLen]);
        }
        
        $maxSum = 0;
        for ($i = $firstLen + $secondLen - 1; $i < $n; $i++) {
            $maxSum = max($maxSum, $maxFirst[$i - $secondLen] + ($prefix[$i + 1] - $prefix[$i + 1 - $secondLen]));
        }
        
        return $maxSum;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти

Вот отсортированная база с тонной материала (постепенно пополняется):

(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR

Скачивать ничего не нужно — все выложили в Telegram

Задача: 1017. Convert to Base -2
Сложность: medium

Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".

Пример:

Input: n = 2
Output: "110"

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Создайте пустую строку для хранения двоичного представления числа.
Используйте цикл для вычисления каждой цифры числа в базе -2.

2⃣Вычисление цифр:
В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2.
Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1.
Добавляйте остаток в начало строки.

3⃣Возврат результата:
Верните строку, представляющую число в базе -2. Если строка пустая, верните "0".

😎 Решение:

class Solution {
    function baseNeg2($n) {
        if ($n == 0) return "0";
        $res = "";
        while ($n != 0) {
            $remainder = $n % -2;
            $n = intdiv($n, -2);
            if ($remainder < 0) {
                $remainder += 2;
                $n += 1;
            }
            $res = $remainder . $res;
        }
        return $res;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60
Сложность: medium

Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.

Пример:

Input: time = [30,20,150,100,40]
Output: 3

👨‍💻 Алгоритм:

1⃣Инициализация и вычисление остатков:
Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями.

2⃣Подсчет пар:
Пройдитесь по каждой песне в списке и для каждого элемента:
Вычислите остаток от деления времени песни на 60.
Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0).
Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0).
Обновите массив остатков, увеличивая количество песен с текущим остатком на 1.

3⃣Возврат результата:
Верните общее количество пар.

😎 Решение:

class Solution {
    function numPairsDivisibleBy60($time) {
        $remainders = array_fill(0, 60, 0);
        $count = 0;
        
        foreach ($time as $t) {
            if ($t % 60 == 0) {
                $count += $remainders[0];
            } else {
                $count += $remainders[60 - $t % 60];
            }
            $remainders[$t % 60]++;
        }
        
        return $count;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

👨‍💻 Алгоритм:

1⃣Построим дерево регионов, где каждый регион указывает на своего родителя.

2⃣Используя родительскую информацию, найдем путь от каждого региона до корня.

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

class Solution {
    function findSmallestRegion($regions, $region1, $region2) {
        $parent = [];

        foreach ($regions as $regionList) {
            for ($i = 1; $i < count($regionList); $i++) {
                $parent[$regionList[$i]] = $regionList[0];
            }
        }

        $ancestors1 = [];
        while ($region1 !== null) {
            $ancestors1[$region1] = true;
            $region1 = isset($parent[$region1]) ? $parent[$region1] : null;
        }

        while (!isset($ancestors1[$region2])) {
            $region2 = isset($parent[$region2]) ? $parent[$region2] : null;
        }

        return $region2;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 942. DI String Match
Сложность: easy

Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.

Пример:

Input: s = "IDID"
Output: [0,4,1,3,2]

👨‍💻 Алгоритм:

1⃣Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке.

2⃣Создать массив perm длиной n + 1.
Пройти по строке s:
Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.
Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.
Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.

3⃣Вернуть массив perm.

😎 Решение:

function diStringMatch($s) {
    $n = strlen($s);
    $low = 0;
    $high = $n;
    $perm = array_fill(0, $n + 1, 0);
    
    for ($i = 0; $i < $n; $i++) {
        if ($s[$i] == 'I') {
            $perm[$i] = $low++;
        } else {
            $perm[$i] = $high--;
        }
    }
    
    $perm[$n] = $low;
    return $perm;
}

Ставь 👍 и забирай 📚 Базу знаний