Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium

Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

3⃣Обновление максимальной длины
На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки.

😎 Решение:

class Solution {
    function lengthOfLongestSubstringKDistinct($s, $k) {
        $left = 0;
        $right = 0;
        $charCount = [];
        $maxLength = 0;
        
        while ($right < strlen($s)) {
            $charCount[$s[$right]] = ($charCount[$s[$right]] ?? 0) + 1;
            while (count($charCount) > $k) {
                $charCount[$s[$left]]--;
                if ($charCount[$s[$left]] == 0) {
                    unset($charCount[$s[$left]]);
                }
                $left++;
            }
            $maxLength = max($maxLength, $right - $left + 1);
            $right++;
        }
        
        return $maxLength;
    }
}

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

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.
Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.

3⃣Заполни и верни массив назначений.

😎 Решение:

function assignBikes($workers, $bikes) {
    $pairs = [];
    
    for ($i = 0; $i < count($workers); $i++) {
        for ($j = 0; $j < count($bikes); $j++) {
            $distance = abs($workers[$i][0] - $bikes[$j][0]) + abs($workers[$i][1] - $bikes[$j][1]);
            $pairs[] = [$distance, $i, $j];
        }
    }
    
    usort($pairs, function($a, $b) {
        if ($a[0] !== $b[0]) return $a[0] - $b[0];
        if ($a[1] !== $b[1]) return $a[1] - $b[1];
        return $a[2] - $b[2];
    });
    
    $result = array_fill(0, count($workers), -1);
    $bikeTaken = array_fill(0, count($bikes), false);
    $workerAssigned = array_fill(0, count($workers), false);
    
    foreach ($pairs as [$distance, $workerIdx, $bikeIdx]) {
        if (!$workerAssigned[$workerIdx] && !$bikeTaken[$bikeIdx]) {
            $result[$workerIdx] = $bikeIdx;
            $bikeTaken[$bikeIdx] = true;
            $workerAssigned[$workerIdx] = true;
        }
    }
    
    return $result;
}

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private $maxLength = 0;

    function longestZigZag($root) {
        $this->dfs($root, true, 0);
        $this->dfs($root, false, 0);
        return $this->maxLength;
    }

    private function dfs($node, $isLeft, $length) {
        if ($node === null) return;
        $this->maxLength = max($this->maxLength, $length

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

Задача: 126.Word Ladder II
Сложность: Hard

Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:
Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

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

1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

2⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList.

3⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths.

😎 Решение:

class Solution {
    function findLadders($beginWord, $endWord, $wordList) {
        $adjList = [];
        $wordSet = array_flip($wordList);
        $this->bfs($beginWord, $endWord, $wordSet, $adjList);
        $this->currPath = [$endWord];
        $this->shortestPaths = [];
        $this->backtrack($endWord, $beginWord, $adjList);
        return $this->shortestPaths;
    }

    function findNeighbors($word, &$wordSet) {
        $neighbors = [];
        $charList = str_split($word);
        for ($i = 0; $i < strlen($word); $i++) {
            $oldChar = $charList[$i];
            foreach (range('a', 'z') as $c) {
                if ($c != $oldChar) {
                    $charList[$i] = $c;
                    $newWord = implode('', $charList);
                    if (isset($wordSet[$newWord])) {
                        $neighbors[] = $newWord;
                    }
                }
            }
            $charList[$i] = $oldChar;
        }
        return $neighbors;
    }

    function backtrack($source, $destination, &$adjList) {
        if ($source == $destination) {
            $this->shortestPaths[] = array_reverse($this->currPath);
        } else if (isset($adjList[$source])) {
            foreach ($adjList[$source] as $neighbor) {
                array_push($this->currPath, $neighbor);
                $this->backtrack($neighbor, $destination, $adjList);
                array_pop($this->currPath);
            }
        }
    }

    function bfs($beginWord, $endWord, &$wordSet, &$adjList) {
        $queue = [$beginWord];
        unset($wordSet[$beginWord]);

        while ($queue) {
            $currentWord = array_shift($queue);
            $neighbors = $this->findNeighbors($currentWord, $wordSet);

            foreach ($neighbors as $neighbor) {
                $adjList[$neighbor][] = $currentWord;
                if (isset($wordSet[$neighbor])) {
                    unset($wordSet[$neighbor]);
                    $queue[] = $neighbor;
                }
            }
        }
    }
}

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