PHP | LeetCode

Задача: 538. Convert BST to Greater Tree
Сложность: medium

Дано корень бинарного дерева поиска (BST), преобразуйте его в дерево, в котором каждый ключ исходного BST изменен на исходный ключ плюс сумму всех ключей, больших исходного ключа в BST.
Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям:
Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла.
Правое поддерево узла содержит только узлы с ключами, большими ключа узла.
И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

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

2⃣Посещаем текущий узел, обновляем его значение и общую сумму.

3⃣Рекурсивно обрабатываем левое поддерево.

😎 Решение:

class Solution {
    private $sum = 0;

    public function convertBST($root) {
        if ($root !== null) {
            $this->convertBST($root->right);
            $this->sum += $root->val;
            $root->val = $this->sum;
            $this->convertBST($root->left);
        }
        return $root;
    }
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

function deleteTreeNodes($nodes, $parent, $value) {
    $tree = [];
    for ($i = 0; $i < $nodes; $i++) {
        if (!isset($tree[$parent[$i]])) $tree[$parent[$i]] = [];
        $tree[$parent[$i]][] = $i;
    }

    function dfs($node, &$tree, &$value) {
        $totalSum = $value[$node];
        $totalCount = 1;
        if (isset($tree[$node])) {
            foreach ($tree[$node] as $child) {
                list($childSum, $childCount) = dfs($child, $tree, $value);
                $totalSum += $childSum;
                $totalCount += $childCount;
            }
        }
        return $totalSum == 0 ? [0, 0] : [$totalSum, $totalCount];
    }

    return dfs(0, $tree, $value)[1];
}

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

Задача: 374. Guess Number Higher or Lower
Сложность: easy

Мы играем в игру "Угадай число" от 1 до n.
Есть предопределённая функция guess(int num), которая возвращает:
-1 — если num больше загаданного числа
1 — если num меньше загаданного числа
0 — если num совпадает с загаданным числом

Пример:

Input: n = 10, pick = 6
Output: 6

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

1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

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

3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного.

😎 Решение:

class Solution extends GuessGame {
    function guessNumber($n) {
        $low = 1;
        $high = $n;
        while ($low <= $high) {
            $mid = $low + intdiv($high - $low, 2);
            $res = guess($mid);
            if ($res == 0)
                return $mid;
            else if ($res < 0)
                $high = $mid - 1;
            else
                $low = $mid + 1;
        }
        return -1;
    }
}

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

Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.
Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

function checkInclusion($s1, $s2) {
    $s1Len = strlen($s1);
    $s2Len = strlen($s2);
    if ($s1Len > $s2Len) return false;

    $s1Count = array_fill(0, 26, 0);
    $s2Count = array_fill(0, 26, 0);

    for ($i = 0; $i < $s1Len; $i++) {
        $s1Count[ord($s1[$i]) - ord('a')]++;
        $s2Count[ord($s2[$i]) - ord('a')]++;
    }

    for ($i = 0; $i < $s2Len - $s1Len; $i++) {
        if ($s1Count == $s2Count) return true;
        $s2Count[ord($s2[$i]) - ord('a')]--;
        $s2Count[ord($s2[$i + $s1Len]) - ord('a')]++;
    }

    return $s1Count == $s2Count;
}

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

Задача: 645. Set Mismatch
Сложность: easy

У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива.

Пример:

Input: nums = [1,2,2,4]
Output: [2,3]

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

1⃣Пройдите по массиву, используя набор для отслеживания чисел, чтобы определить дублированное число.

2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

function findErrorNums($nums) {
    $n = count($nums);
    $numSet = [];
    $duplicate = -1;
    foreach ($nums as $num) {
        if (in_array($num, $numSet)) {
            $duplicate = $num;
        }
        $numSet[] = $num;
    }
    $missing = ($n * ($n + 1)) / 2 - array_sum(array_unique($numSet));
    return [$duplicate, $missing];
}

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

Задача: 282. Expression Add Operators
Сложность: hard

Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.
Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.

Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

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

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

2⃣Рекурсивная генерация выражений:
В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения.
Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение.

3⃣Проверка и запись валидных выражений:
Когда вся строка цифр обработана, проверяйте, соответствует ли итоговое значение целевому значению и нет ли остатков операндов.
Если выражение валидное, записывайте его в список результатов.

😎 Решение:

class Solution {
    private $answer;
    private $digits;
    private $target;

    private function recurse($index, $previousOperand, $currentOperand, $value, &$ops) {
        if ($index == strlen($this->digits)) {
            if ($value == $this->target && $currentOperand == 0) {
                $this->answer[] = implode("", $ops);
            }
            return;
        }

        $currentOperand = $currentOperand * 10 + intval($this->digits[$index]);
        $currentValRep = strval($currentOperand);

        if ($currentOperand > 0) {
            $this->recurse($index + 1, $previousOperand, $currentOperand, $value, $ops);
        }

        $ops[] = "+";
        $ops[] = $currentValRep;
        $this->recurse($index + 1, $currentOperand, 0, $value + $currentOperand, $ops);
        array_pop($ops);
        array_pop($ops);

        if (count($ops) > 0) {
            $ops[] = "-";
            $ops[] = $currentValRep;
            $this->recurse($index + 1, -$currentOperand, 0, $value - $currentOperand, $ops);
            array_pop($ops);
            array_pop($ops);

            $ops[] = "*";
            $ops[] = $currentValRep;
            $this->recurse($index + 1, $currentOperand * $previousOperand, 0, $value - $previousOperand + ($currentOperand * $previousOperand), $ops);
            array_pop($ops);
            array_pop($ops);
        }
    }

    public function addOperators($num, $target) {
        if (strlen($num) == 0) {
            return [];
        }

        $this->target = $target;
        $this->digits = $num;
        $this->answer = [];
        $ops = [];
        $this->recurse(0, 0, 0, 0, $ops);
        return $this->answer;
    }
}

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

Задача: 137. Single Number II
Сложность: medium

Дан массив целых чисел nums, в котором каждый элемент встречается три раза, кроме одного, который встречается ровно один раз. Найдите этот единственный элемент и верните его.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

Input: nums = [2,2,3,2]
Output: 3

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

1⃣Сортировка массива:
Отсортируйте массив nums. Это упорядочит все элементы так, чтобы одинаковые числа находились рядом.

2⃣Итерация с проверкой:
Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива.
Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла.

3⃣Возврат уникального элемента:
Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе.
Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше.

😎 Решение:

function singleNumber($nums) {
    sort($nums);
    $len = count($nums);
    for ($i = 0; $i < $len - 1; $i += 3) {
        if ($nums[$i] !== $nums[$i + 1]) {
            return $nums[$i];
        }
    }
    return $nums[$len - 1];
}

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

Задача: 233. Number of Digit One
Сложность: hard

Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

function countDigitOne($n) {
    $countr = 0;
    for ($i = 1; $i <= $n; $i *= 10) {
        $divider = $i * 10;
        $countr += intval($n / $divider) * $i + min(max($n % $divider - $i + 1, 0), $i);
    }
    return $countr;
}

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

Задача: 1469. Find All The Lonely Nodes
Сложность: easy

В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.

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

Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

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

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎 Решение:

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 {
    function DFS($root, $isLonely, &$ans) {
        if ($root === null) {
            return;
        }
        
        if ($isLonely) {
            $ans[] = $root->val;
        }
        
        $this->DFS($root->left, $root->right === null, $ans);
        $this->DFS($root->right, $root->left === null, $ans);
    }
    
    function getLonelyNodes($root) {
        $ans = [];
        $this->DFS($root, false, $ans);
        return $ans;
    }
}

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

Задача: 863. All Nodes Distance K in Binary Tree
Сложность: medium

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

Ответ можно вернуть в любом порядке.

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

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

1⃣Определите рекурсивную функцию add_parent(cur, parent), чтобы рекурсивно добавлять указатель на родителя к узлу cur. Если cur не пустой, добавьте указатель на parent: cur.parent = parent. Затем рекурсивно вызовите add_parent для левого и правого детей cur: add_parent(cur.left, cur) и add_parent(cur.right, cur). Вызовите add_parent(root, None), чтобы добавить все указатели на родителей (корневой узел не имеет родителя).

2⃣Инициализируйте пустой массив answer и пустое множество visited. Определите рекурсивную функцию dfs(cur, distance) для поиска всех узлов на расстоянии k от узла target. Если cur пустой или уже был посещён, вернитесь. Добавьте cur в visited, чтобы его не посещали повторно. Если distance = k, добавьте cur в answer и вернитесь.

3⃣Рекурсивно вызовите dfs для детей и родителя cur. Вызовите dfs(target, 0), чтобы найти все узлы на расстоянии k. Верните answer после завершения DFS.

😎 Решение:

class Solution {
    function distanceK($root, $target, $k) {
        $this->addParent($root, null);
        
        $answer = [];
        $visited = new SplObjectStorage();
        
        $this->dfs($target, $k, $visited, $answer);
        return $answer;
    }
    
    private function addParent($cur, $parent) {
        if ($cur) {
            $cur->parent = $parent;
            $this->addParent($cur->left, $cur);
            $this->addParent($cur->right, $cur);
        }
    }
    
    private function dfs($cur, $distance, $visited, &$answer) {
        if (!$cur || $visited->contains($cur)) return;
        $visited->attach($cur);
        if ($distance == 0) {
            $answer[] = $cur->val;
            return;
        }
        $this->dfs($cur->parent, $distance - 1, $visited, $answer);
        $this->dfs($cur->left, $distance - 1, $visited, $answer);
        $this->dfs($cur->right, $distance - 1, $visited, $answer);
    }
}

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

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

Дан массив arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение:

class Solution {
    function findKthPositive($arr, $k) {
        if ($k <= $arr[0] - 1) {
            return $k;
        }
        $k -= $arr[0] - 1;
        $n = count($arr);
        for ($i = 0; $i < $n - 1; ++$i) {
            $currMissing = $arr[$i + 1] - $arr[$i] - 1;
            if ($k <= $currMissing) {
                return $arr[$i] + $k;
            }
            $k -= $currMissing;
        }
        return $arr[$n - 1] + $k;
    }
}

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

Задача: 280. Wiggle Sort
Сложность: medium

Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....
Вы можете считать, что входной массив всегда имеет допустимый ответ.

Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

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

1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена.

2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

😎 Решение:

class Solution {
    private function swap(&$nums, $i, $j) {
        $temp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $temp;
    }

    public function wiggleSort(&$nums) {
        for ($i = 0; $i < count($nums) - 1; $i++) {
            if (($i % 2 == 0 && $nums[$i] > $nums[$i + 1]) || ($i % 2 == 1 && $nums[$i] < $nums[$i + 1])) {
                $this->swap($nums, $i, $i + 1);
            }
        }
    }
}

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

Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard

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

Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).

Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].

Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

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

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

2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:
Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.

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

😎 Решение:

class Solution {
    private function bitmask($word) {
        $mask = 0;
        for ($i = 0; $i < strlen($word); $i++) {
            $mask |= 1 << (ord($word[$i]) - ord('a'));
        }
        return $mask;
    }

    function findNumOfValidWords($words, $puzzles) {
        $wordCount = [];
        foreach ($words as $word) {
            $mask = $this->bitmask($word);
            if (!isset($wordCount[$mask])) {
                $wordCount[$mask] = 0;
            }
            $wordCount[$mask]++;
        }

        $result = [];
        foreach ($puzzles as $puzzle) {
            $first = 1 << (ord($puzzle[0]) - ord('a'));
            $count = isset($wordCount[$first]) ? $wordCount[$first] : 0;
            $mask = $this->bitmask(substr($puzzle, 1));
            for ($submask = $mask; $submask > 0; $submask = ($submask - 1) & $mask) {
                $count += isset($wordCount[$submask | $first]) ? $wordCount[$submask | $first] : 0;
            }
            $result[] = $count;
        }
        return $result;
    }
}

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

Задача: 415. Add Strings
Сложность: easy

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: num1 = "11", num2 = "123"
Output: "134"

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

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

2⃣Пройдите по массиву nums, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов.

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

😎 Решение:

function thirdMax($nums) {
    $first = null;
    $second = null;
    $third = null;
    
    foreach ($nums as $num) {
        if ($num === $first || $num === $second || $num === $third) {
            continue;
        }
        if ($first === null || $num > $first) {
            $third = $second;
            $second = $first;
            $first = $num;
        } elseif ($second === null || $num > $second) {
            $third = $second;
            $second = $num;
        } elseif ($third === null || $num > $third) {
            $third = $num;
        }
    }
    
    return $third !== null ? $third : $first;
}

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

Задача: 532. K-diff Pairs in an Array
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.
Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

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

1⃣Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums.

2⃣Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:
Если k > 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:

class Solution {
    function findPairs($nums, $k) {
        $counter = [];
        foreach ($nums as $num) {
            if (!isset($counter[$num])) {
                $counter[$num] = 0;
            }
            $counter[$num]++;
        }
        
        $result = 0;
        foreach ($counter as $x => $val) {
            if ($k > 0) {
                if (isset($counter[$x + $k])) {
                    $result++;
                }
            } else if ($k == 0 && $val > 1) {
                $result++;
            }
        }
        
        return $result;
    }
}

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

Задача: 435. Non-overlapping Intervals
Сложность: medium

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    function eraseOverlapIntervals($intervals) {
        usort($intervals, function($a, $b) {
            return $a[1] - $b[1];
        });
        $ans = 0;
        $k = -INF;
        
        foreach ($intervals as $interval) {
            list($x, $y) = $interval;
            if ($x >= $k) {
                $k = $y;
            } else {
                $ans++;
            }
        }
        
        return $ans;
    }
}

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

Задача: 393. UTF-8 Validation
Сложность: medium

Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).
Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:
Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:

     Количество байтов  |        UTF-8 Октетная последовательность
                       |              (бинарная)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.

Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных.

Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

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

1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep.

2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа.

3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий.

Теперь давайте перейдем к реализации этого алгоритма.

😎 Решение:

class Solution {
    function validUtf8($data) {
        $nBytes = 0;
        foreach ($data as $num) {
            $binRep = substr(sprintf('%08b', $num), -8);
            if ($nBytes == 0) {
                foreach (str_split($binRep) as $bit) {
                    if ($bit == '0') break;
                    $nBytes++;
                }
                if ($nBytes == 0) continue;
                if ($nBytes == 1 || $nBytes > 4) return false;
            } else {
                if (!(substr($binRep, 0, 2) == '10')) return false;
            }
            $nBytes--;
        }
        return $nBytes == 0;
    }
}

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

Задача: 141. Linked List Cycle
Сложность: easy

Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.
Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.
Верните true, если в связном списке есть цикл. В противном случае верните false.

Пример:

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

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

1⃣Инициализация структуры данных:
Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы.

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

3⃣Проверка на цикл:
Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false.
Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true.
Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка.

😎 Решение:

class ListNode {
    public $val;
    public $next;

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

function hasCycle($head) {
    $nodesSeen = [];
    $current = $head;

    while ($current !== null) {
        $nodeId = spl_object_id($current); 
        if (isset($nodesSeen[$nodeId])) {
            return true;
        }
        $nodesSeen[$nodeId] = true;
        $current = $current->next;
    }
    return false;
}

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

Задача: 438. Find All Anagrams in a String
Сложность: medium

Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

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

1⃣Построить эталонный счетчик pCount для строки p.

2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

function findAnagrams($s, $p) {
    $ns = strlen($s);
    $np = strlen($p);
    if ($ns < $np) {
        return [];
    }

    $pCount = array_fill_keys(range('a', 'z'), 0);
    $sCount = array_fill_keys(range('a', 'z'), 0);

    for ($i = 0; $i < $np; $i++) {
        $pCount[$p[$i]]++;
    }

    $output = [];

    for ($i = 0; $i < $ns; $i++) {
        $sCount[$s[$i]]++;

        if ($i >= $np) {
            $leftChar = $s[$i - $np];
            if ($sCount[$leftChar] == 1) {
                unset($sCount[$leftChar]);
            } else {
                $sCount[$leftChar]--;
            }
        }

        if ($pCount == $sCount) {
            $output[] = $i - $np + 1;
        }
    }

    return $output;
}

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

Задача: 1063. Number of Valid Subarrays
Сложность: hard

Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

class Solution {
    function validSubarrays($nums) {
        $ans = 0;
        $st = [];
        
        for ($i = 0; $i < count($nums); $i++) {
            while (!empty($st) && $nums[$i] < $nums[end($st)]) {
                $ans += ($i - array_pop($st));
            }
            $st[] = $i;
        }
        
        while (!empty($st)) {
            $ans += (count($nums) - array_pop($st));
        }
        
        return $ans;
    }
}

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