PHP | LeetCode

Задача: 487. Max Consecutive Ones II Сложность: medium Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля. Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

👨‍💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:

class Solution {
    function findMaxConsecutiveOnes($nums) {
        $longestSequence = 0;
        for ($left = 0; $left < count($nums); $left++) {
            $numZeroes = 0;
            for ($right = $left; $right < count($nums); $right++) {
                if ($nums[$right] == 0) {
                    $numZeroes++;
                }
                if ($numZeroes <= 1) {
                    $longestSequence = max($longestSequence, $right - $left + 1);
                }
            }
        }
        return $longestSequence;
    }
}

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

Задача: 1074. Number of Submatrices That Sum to Target Сложность: hard Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению. Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2. Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'. Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

👨‍💻 Алгоритм: 1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений. 2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target. 3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count. 😎 Решение:

class Solution {
    function numSubmatrixSumTarget($matrix, $target) {
        $r = count($matrix);
        $c = count($matrix[0]);
        $ps = array_fill(0, $r + 1, array_fill(0, $c + 1, 0));
        
        for ($i = 1; $i <= $r; ++$i) {
            for ($j = 1; $j <= $c; ++$j) {
                $ps[$i][$j] = $ps[$i - 1][$j] + $ps[$i][$j - 1] - $ps[$i - 1][$j - 1] + $matrix[$i - 1][$j - 1];
            }
        }
        
        $count = 0;
        
        for ($r1 = 1; $r1 <= $r; ++$r1) {
            for ($r2 = $r1; $r2 <= $r; ++$r2) {
                $h = array();
                $h[0] = 1;
                for ($col = 1; $col <= $c; ++$col) {
                    $currSum = $ps[$r2][$col] - $ps[$r1 - 1][$col];
                    if (isset($h[$currSum - $target])) {
                        $count += $h[$currSum - $target];
                    }
                    if (isset($h[$currSum])) {
                        $h[$currSum]++;
                    } else {
                        $h[$currSum] = 1;
                    }
                }
            }
        }
        
        return $count;
    }
}

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

Задача: 148. Sort List Сложность: Medium Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания. Пример:

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

👨‍💻 Алгоритм: 1⃣Разделение списка (Фаза разделения): Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка. 2⃣Сортировка подсписков и их объединение (Фаза слияния): Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков. 3⃣Иллюстрация процесса сортировки: Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список. 😎 Решение:

class ListNode {
    public $val;
    public $next;

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

class Solution {
    public function sortList($head) {
        if ($head === null || $head->next === null) {
            return $head;
        }
        $mid = $this->getMid($head);
        $left = $this->sortList($head);
        $right = $this->sortList($mid);
        return $this->merge($left, $right);
    }

    private function merge($list1, $list2) {
        $dummyHead = new ListNode();
        $tail = $dummyHead;
        while ($list1 !== null && $list2 !== null) {
            if ($list1->val < $list2->val) {
                $tail->next = $list1;
                $list1 = $list1->next;
            } else {
                $tail->next = $list2;
                $list2 = $list2->next;
            }
            $tail = $tail->next;
        }
        $tail->next = $list1 ?? $list2;
        return $dummyHead->next;
    }

    private function getMid($head) {
        $midPrev = null;
        $slow = $head;
        $fast = $head;
        while ($fast !== null && $fast->next !== null) {
            $midPrev = ($midPrev === null) ? $slow : $midPrev->next;
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        $mid = $midPrev->next;
        $midPrev->next = null;
        return $mid;
    }
}

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

Задача: 366. Find Leaves of Binary Tree Сложность: medium Дан корень бинарного дерева, соберите узлы дерева следующим образом: Соберите все листовые узлы. Удалите все листовые узлы. Повторяйте, пока дерево не станет пустым. Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

👨‍💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1. 2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте. 3⃣Организовать узлы по высоте и вернуть результат. 😎 Решение:

class Solution {
    private $pairs = [];

    private function getHeight($node) {
        if ($node === null) return -1;
        $leftHeight = $this->getHeight($node->left);
        $rightHeight = $this->getHeight($node->right);
        $currHeight = max($leftHeight, $rightHeight) + 1;
        $this->pairs[] = [$currHeight, $node->val];
        return $currHeight;
    }

    public function findLeaves($root) {
        $this->getHeight($root);
        usort($this->pairs, function($a, $b) {
            return $a[0] <=> $b[0];
        });
        $solution = [];
        $currentHeight = -1;
        foreach ($this->pairs as $pair) {
            if ($pair[0] !== $currentHeight) {
                $solution[] = [];
                $currentHeight = $pair[0];
            }
            $solution[count($solution) - 1][] = $pair[1];
        }
        return $solution;
    }
}

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

Задача: 908. Smallest Range I Сложность: easy Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем. Пример:

Input: nums = [1], k = 0
Output: 0

👨‍💻 Алгоритм: 1⃣Найти минимальное и максимальное значения массива nums. 2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции. 3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями. 😎 Решение:

function smallestRangeI($nums, $k) {
    $minVal = min($nums);
    $maxVal = max($nums);
    return max(0, ($maxVal - $k) - ($minVal + $k));
}

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

Задача: 358. Rearrange String k Distance Apart Сложность: hard Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "". Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

👨‍💻 Алгоритм: 1⃣Создайте словарь частот для символов строки и определите максимальную частоту. 2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов. 3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку. 😎 Решение:

class Solution {
    function rearrangeString($s, $k) {
        $freqs = [];
        $maxFreq = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (!isset($freqs[$char])) {
                $freqs[$char] = 0;
            }
            $freqs[$char]++;
            $maxFreq = max($maxFreq, $freqs[$char]);
        }

        $mostChars = [];
        $secondChars = [];

        foreach ($freqs as $char => $freq) {
            if ($freq == $maxFreq) {
                $mostChars[] = $char;
            } else if ($freq == $maxFreq - 1) {
                $secondChars[] = $char;
            }
        }

        $segments = array_fill(0, $maxFreq, "");

        for ($i = 0; $i < $maxFreq; $i++) {
            foreach ($mostChars as $char) {
                $segments[$i] .= $char;
            }
            if ($i < $maxFreq - 1) {
                foreach ($secondChars as $char) {
                    $segments[$i] .= $char;
                }
            }
        }

        $segmentId = 0;

        foreach ($freqs as $char => $freq) {
            if (in_array($char, $mostChars) || in_array($char, $secondChars)) {
                continue;
            }

            for ($j = 0; $j < $freq; $j++) {
                $segments[$segmentId] .= $char;
                $segmentId = ($segmentId + 1) % ($maxFreq - 1);
            }
        }

        for ($i = 0; $i < $maxFreq - 1; $i++) {
            if (strlen($segments[$i]) < $k) {
                return "";
            }
        }

        return implode("", $segments);
    }
}

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

Задача: 1044. Longest Duplicate Substring Сложность: hard Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "". Пример:

Input: s = "banana"
Output: "ana"

👨‍💻 Алгоритм: 1⃣Использование двоичного поиска для определения длины дублированной подстроки: Двоичный поиск используется для поиска максимальной длины дублированной подстроки. 2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины: Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок. 3⃣Хеширование с помощью функции rolling hash: Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов. 😎 Решение:

function longestDupSubstring($s) {
    function search($s, $length) {
        $seen = [];
        for ($i = 0; $i <= strlen($s) - $length; $i++) {
            $sub = substr($s, $i, $length);
            if (isset($seen[$sub])) {
                return $sub;
            }
            $seen[$sub] = true;
        }
        return "";
    }

    $left = 1;
    $right = strlen($s);
    $result = "";
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        $dup = search($s, $mid);
        if ($dup !== "") {
            $result = $dup;
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }
    return $result;
}

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

Задача: 189. Rotate Array Сложность: medium Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число. Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

👨‍💻 Алгоритм: 1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива. 2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов. 3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива. 😎 Решение:

class Solution {
    function rotate(&$nums, $k) {
        $n = count($nums);
        $a = array_fill(0, $n, 0);
        for ($i = 0; $i < $n; $i++) {
            $a[($i + $k) % $n] = $nums[$i];
        }
        for ($i = 0; $i < $n; $i++) {
            $nums[$i] = $a[$i];
        }
    }
}

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

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

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