Задача: 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);
    }
}

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