Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎 Решение:

class Solution {
    private function dfs($word, $length, &$visited, $dictionary) {
        if ($length == strlen($word)) {
            return true;
        }
        if ($visited[$length]) {
            return false;
        }
        $visited[$length] = true;
        for ($i = strlen($word) - ($length == 0 ? 1 : 0); $i > $length; $i--) {
            if (isset($dictionary[substr($word, $length, $i - $length)]) &&
                $this->dfs($word, $i, $visited, $dictionary)) {
                return true;
            }
        }
        return false;
    }

    function findAllConcatenatedWordsInADict($words) {
        $dictionary = array_flip($words);
        $answer = [];
        foreach ($words as $word) {
            $visited = array_fill(0, strlen($word), false);
            if ($this->dfs($word, 0, $visited, $dictionary)) {
                $answer[] = $word;
            }
        }
        return $answer;
    }
}

$solution = new Solution();
$words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
print_r($solution->findAllConcatenatedWordsInADict($words));

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

Задача: 268. Missing Number
Сложность: easy

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1⃣Сначала отсортируйте массив nums.

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

3⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.

😎 Решение:

class Solution {
    function missingNumber($nums) {
        sort($nums);
        if ($nums[count($nums) - 1] != count($nums)) {
            return count($nums);
        } else if ($nums[0] != 0) {
            return 0;
        }
        for ($i = 1; $i < count($nums); $i++) {
            $expectedNum = $nums[$i - 1] + 1;
            if ($nums[$i] != $expectedNum) {
                return $expectedNum;
            }
        }
        return -1;
    }
}

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

Задача: 418. Sentence Screen Fitting
Сложность: medium

Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом.

Пример:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1

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

1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце.

2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов.

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

😎 Решение:

function wordsTyping($sentence, $rows, $cols) {
    $sentenceStr = implode(" ", $sentence) . " ";
    $length = strlen($sentenceStr);
    $pos = 0;
    
    for ($i = 0; $i < $rows; $i++) {
        $pos += $cols;
        if ($sentenceStr[$pos % $length] == " ") {
            $pos++;
        } else {
            while ($pos > 0 && $sentenceStr[($pos - 1) % $length] != " ") {
                $pos--;
            }
        }
    }
    
    return intdiv($pos, $length);
}

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

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

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

class Solution {
    function numKLenSubstrNoRepeats($s, $k) {
        if ($k > 26) return 0;
        
        $answer = 0;
        $n = strlen($s);
        
        for ($i = 0; $i <= $n - $k; $i++) {
            $freq = array_fill(0, 26, 0);
            $isUnique = true;
            
            for ($j = $i; $j < $i + $k; $j++) {
                $freq[ord($s[$j]) - ord('a')]++;
                if ($freq[ord($s[$j]) - ord('a')] > 1) {
                    $isUnique = false;
                    break;
                }
            }
            
            if ($isUnique) {
                $answer++;
            }
        }
        
        return $answer;
    }
}

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

Задача: 272. Closest Binary Search Tree Value II
Сложность: hard

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

Пример:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

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

1⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив:
Пройти по дереву в глубину, добавляя каждое значение узла в массив.

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

3⃣Вернуть первые k значений из отсортированного массива:
Извлечь первые k элементов из отсортированного массива и вернуть их.

😎 Решение:

class Solution {
    function closestKValues($root, $target, $k) {
        $arr = [];
        $this->dfs($root, $arr);
        usort($arr, function($o1, $o2) use ($target) {
            return abs($o1 - $target) <=> abs($o2 - $target);
        });
        return array_slice($arr, 0, $k);
    }
    
    private function dfs($node, &$arr) {
        if ($node === null) return;
        $arr[] = $node->val;
        $this->dfs($node->left, $arr);
        $this->dfs($node->right, $arr);
    }
}

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