#medium
Задача: 254. Factor Combinations

Числа можно рассматривать как произведение их множителей.

Например, 8 = 2 x 2 x 2 = 2 x 4.
Дано целое число n, верните все возможные комбинации его множителей. Вы можете вернуть ответ в любом порядке.

Обратите внимание, что множители должны быть в диапазоне [2, n - 1].

Пример:

Input: n = 1
Output: []

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

1️⃣Определите вспомогательную функцию backtracking, которая принимает два параметра: factors (список множителей) и ans (список списков для сохранения всех комбинаций множителей). Начните вызов backtracking с factors, содержащим только n, и пустым списком ans.

2️⃣Основная логика функции backtracking:
Если размер factors больше 1, добавьте его копию в ans, так как это одно из желаемых решений.
Получите последний элемент factors (lastFactor) и удалите его из factors.
Если factors пуст, итерируйте i от 2. В противном случае, итерируйте i от последнего значения в factors. Итерируйте, пока i <= lastFactor / i.
Для каждого i, если lastFactor % i == 0, добавьте i и lastFactor / i в factors и вызовите backtracking(factors, ans).
Восстановите список (откат) factors, удалив последние два элемента из factors.
Восстановите список (откат) factors, добавив обратно lastFactor.

3️⃣В конце выполнения, ans будет содержать все возможные комбинации множителей числа n.

😎 Решение:

class Solution {
    private function backtracking(&$factors, &$ans) {
        if (count($factors) > 1) {
            $ans[] = $factors;
        }
        $lastFactor = array_pop($factors);
        $start = empty($factors) ? 2 : end($factors);
        for ($i = $start; $i * $i <= $lastFactor; ++$i) {
            if ($lastFactor % $i == 0) {
                $factors[] = $i;
                $factors[] = $lastFactor / $i;
                $this->backtracking($factors, $ans);
                array_pop($factors);
                array_pop($factors);
            }
        }
        $factors[] = $lastFactor;
    }

    public function getFactors($n) {
        $ans = [];
        $factors = [$n];
        $this->backtracking($factors, $ans);
        return $ans;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 255. Verify Preorder Sequence in Binary Search Tree

Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.

Пример:

Input: preorder = [5,2,1,3,6]
Output: true

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

1️⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек.

2️⃣Итерируйте по массиву preorder. Для каждого num:
Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit.
Если num <= minLimit, верните false.
Добавьте num в стек.

3️⃣Верните true, если удалось пройти весь массив.

😎 Решение:

class Solution {
    function verifyPreorder($preorder) {
        $minLimit = -PHP_INT_MAX;
        $stack = [];
        
        foreach ($preorder as $num) {
            while (!empty($stack) && end($stack) < $num) {
                $minLimit = array_pop($stack);
            }
            
            if ($num <= $minLimit) {
                return false;
            }
            
            $stack[] = $num;
        }
        
        return true;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 211. Design Add and Search Words Data Structure

Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.

Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1️⃣ Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2️⃣ Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3️⃣ Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

class TrieNode {
    public $children;
    public $isWord;

    public function __construct() {
        $this->children = [];
        $this->isWord = false;
    }
}

class WordDictionary {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function addWord($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!isset($node->children[$ch])) {
                $node->children[$ch] = new TrieNode();
            }
            $node = $node->children[$ch];
        }
        $node->isWord = true;
    }

    private function searchInNode($word, $node) {
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!isset($node->children[$ch])) {
                if ($ch === '.') {
                    foreach ($node->children as $child) {
                        if ($this->searchInNode(substr($word, $i + 1), $child)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                $node = $node->children[$ch];
            }
        }
        return $node->isWord;
    }

    public function search($word) {
        return $this->searchInNode($word, $this->root);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 212. Word Search II

Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.

Каждое слово должно быть составлено из букв последовательных смежных ячеек, где смежные ячейки находятся по горизонтали или вертикали рядом. Одна и та же ячейка с буквой не может использоваться более одного раза в слове.

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1️⃣ Построение Trie:
Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.

2️⃣ Запуск обхода в глубину (Backtracking) с каждой ячейки:
Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3️⃣ Обход соседних ячеек:
В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎

class TrieNode {
    public $children;
    public $word;

    public function __construct() {
        $this->children = [];
        $this->word = null;
    }
}

class Solution {
    private $board;
    private $result;

    public function findWords($board, $words) {
        $root = $this->buildTrie($words);
        $this->board = $board;
        $this->result = [];

        for ($row = 0; $row < count($board); ++$row) {
            for ($col = 0; $col < count($board[0]); ++$col) {
                if (isset($root->children[$board[$row][$col]])) {
                    $this->backtrack($row, $col, $root);
                }
            }
        }
        return $this->result;
    }

    private function buildTrie($words) {
        $root = new TrieNode();
        foreach ($words as $word) {
            $node = $root;
            for ($i = 0; $i < strlen($word); ++$i) {
                $letter = $word[$i];
                if (!isset($node->children[$letter])) {
                    $node->children[$letter] = new TrieNode();
                }
                $node = $node->children[$letter];
            }
            $node->word = $word;
        }
        return $root;
    }

    private function backtrack($row, $col, $parent) {
        $letter = $this->board[$row][$col];
        $currNode = $parent->children[$letter];

        if ($currNode->word !== null) {
            $this->result[] = $currNode->word;
            $currNode->word = null;
        }

        $this->board[$row][$col] = '#';

        $rowOffset = [-1, 0, 1, 0];
        $colOffset = [0, 1, 0, -1];
        for ($i = 0; $i < 4; ++$i) {
            $newRow = $row + $rowOffset[$i];
            $newCol = $col + $colOffset[$i];
            if (
                $newRow >= 0 && $newRow < count($this->board) &&
                $newCol >= 0 && $newCol < count($this->board[0])
            ) {
                if (isset($currNode->children[$this->board[$newRow][$newCol]])) {
                    $this->backtrack($newRow, $newCol, $currNode);
                }
            }
        }

        $this->board[$row][$col] = $letter;

        if (empty($currNode->children)) {
            unset($parent->children[$letter]);
        }
    }
}

// Example usage:
$solution = new Solution();
$board = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
];
$words = ["oath", "pea", "eat", "rain"];
print_r($solution->findWords($board, $words));

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 256. Paint House

Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.

Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.

Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.

Пример:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

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

1️⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2].

2️⃣Для каждого дома i от 1 до n-1 обновите значения массива dp:
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

3️⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).

😎 Решение:

class Solution {
    function minCost($costs) {
        $n = count($costs);
        $dp = array_fill(0, $n, array_fill(0, 3, 0));
        $dp[0] = $costs[0];
        
        for ($i = 1; $i < $n; $i++) {
            $dp[$i][0] = $costs[$i][0] + min($dp[$i-1][1], $dp[$i-1][2]);
            $dp[$i][1] = $costs[$i][1] + min($dp[$i-1][0], $dp[$i-1][2]);
            $dp[$i][2] = $costs[$i][2] + min($dp[$i-1][0], $dp[$i-1][1]);
        }
        
        return min($dp[$n-1][0], $dp[$n-1][1], $dp[$n-1][2]);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 257. Binary Tree Paths

Дано корневое дерево, верните все пути от корня до листа в любом порядке.

Лист — это узел без детей.

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1️⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2️⃣Начните с корневого узла, пустого пути и пустого списка путей.

3️⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    function construct_paths($root, $path, &$paths) {
        if ($root !== null) {
            $path .= $root->val;
            if ($root->left === null && $root->right === null) {
                $paths[] = $path;
            } else {
                $path .= "->";
                $this->construct_paths($root->left, $path, $paths);
                $this->construct_paths($root->right, $path, $paths);
            }
        }
    }

    function binaryTreePaths($root) {
        $paths = [];
        $this->construct_paths($root, "", $paths);
        return $paths;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 258. Add Digits

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1️⃣Инициализируйте переменную digital_root значением 0.

2️⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3️⃣Верните значение digital_root.

😎 Решение:

class Solution {
    function addDigits($num) {
        $digital_root = 0
        while ($num > 0) {
            $digital_root += $num % 10
            $num = intdiv($num, 10)
            if ($num == 0 && $digital_root > 9) {
                $num = $digital_root
                $digital_root = 0
            }
        }
        return $digital_root
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 259. 3Sum Smaller

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

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

1️⃣Отсортируйте массив nums.

2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎 Решение:

class Solution {
    public function threeSumSmaller($nums, $target) {
        sort($nums);
        $sum = 0;
        for ($i = 0; $i < count($nums) - 2; $i++) {
            $sum += $this->twoSumSmaller($nums, $i + 1, $target - $nums[$i]);
        }
        return $sum;
    }

    private function twoSumSmaller($nums, $startIndex, $target) {
        $sum = 0;
        for ($i = $startIndex; $i < count($nums) - 1; $i++) {
            $j = $this->binarySearch($nums, $i, $target - $nums[$i]);
            $sum += $j - $i;
        }
        return $sum;
    }

    private function binarySearch($nums, $startIndex, $target) {
        $left = $startIndex;
        $right = count($nums) - 1;
        while ($left < $right) {
            $mid = intval(($left + $right + 1) / 2);
            if ($nums[$mid] < $target) {
                $left = $mid;
            } else {
                $right = $mid - 1;
            }
        }
        return $left;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 260. Single Number III

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

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

Пример:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

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

1️⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел.

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

3️⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа.

😎 Решение:

class Solution {
    public function singleNumber($nums) {
        $xor = 0;
        foreach ($nums as $num) {
            $xor ^= $num;
        }
        $diff = $xor & -$xor;
        $res = [0, 0];
        foreach ($nums as $num) {
            if (($num & $diff) == 0) {
                $res[0] ^= $num;
            } else {
                $res[1] ^= $num;
            }
        }
        return $res;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 261. Graph Valid Tree

У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.

Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

1️⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2️⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3️⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    function validTree($n, $edges) {
        if (count($edges) != $n - 1) {
            return false;
        }
        
        $adjList = array_fill(0, $n, []);
        foreach ($edges as $edge) {
            $adjList[$edge[0]][] = $edge[1];
            $adjList[$edge[1]][] = $edge[0];
        }
        
        $parent = [0 => -1];
        $queue = [0];
        
        while (!empty($queue)) {
            $node = array_shift($queue);
            foreach ($adjList[$node] as $neighbor) {
                if ($neighbor == $parent[$node]) {
                    continue;
                }
                if (isset($parent[$neighbor])) {
                    return false;
                }
                $parent[$neighbor] = $node;
                $queue[] = $neighbor;
            }
        }
        
        return count($parent) == $n;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ


🔒 База собесов | 🔒 База тестовых

#easy
Задача: 263. Ugly Number

Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.

Дано целое число n, верните true, если n является уродливым числом.

Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

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

1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.

2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.

3️⃣Если после всех делений n равно 1, верните true, иначе верните false.

😎 Решение:

class Solution {
    function isUgly($n) {
        if ($n <= 0) {
            return false;
        }
        foreach ([2, 3, 5] as $factor) {
            $n = $this->keepDividingWhenDivisible($n, $factor);
        }
        return $n == 1;
    }

    private function keepDividingWhenDivisible($dividend, $divisor) {
        while ($dividend % $divisor == 0) {
            $dividend /= $divisor;
        }
        return $dividend;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 240. Search a 2D Matrix II

Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:

Целые числа в каждой строке отсортированы по возрастанию слева направо.
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз.

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

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

1️⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null.

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

3️⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы.

😎 Решение:

class Solution {
    private function binarySearch($matrix, $target, $start, $vertical) {
        $lo = $start;
        $hi = $vertical ? count($matrix[0]) - 1 : count($matrix) - 1;

        while ($hi >= $lo) {
            $mid = intdiv($lo + $hi, 2);
            $value = $vertical ? $matrix[$start][$mid] : $matrix[$mid][$start];
            if ($value < $target) {
                $lo = $mid + 1;
            } else if ($value > $target) {
                $hi = $mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public function searchMatrix($matrix, $target) {
        if ($matrix === null || count($matrix) === 0) return false;

        $shorterDim = min(count($matrix), count($matrix[0]));
        for ($i = 0; $i < $shorterDim; $i++) {
            if ($this->binarySearch($matrix, $target, $i, true) || $this->binarySearch($matrix, $target, $i, false)) {
                return true;
            }
        }
        return false;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 242. Valid Anagram

Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае.

Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

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

1️⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').

2️⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы.

3️⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s.

😎 Решение:

function isAnagram($s, $t) {
    if (strlen($s) != strlen($t)) {
        return false;
    }
    $count = array_fill(0, 26, 0);
    for ($i = 0; $i < strlen($s); $i++) {
        $count[ord($s[$i]) - ord('a')]++;
        $count[ord($t[$i]) - ord('a')]--;
    }
    foreach ($count as $c) {
        if ($c != 0) {
            return false;
        }
    }
   

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 243. Shortest Word Distance

Дан массив строк wordsDict и две разные строки, которые уже существуют в массиве: word1 и word2. Верните кратчайшее расстояние между этими двумя словами в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

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

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

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

3️⃣Сохраняйте минимальное найденное расстояние между двумя словами и возвращайте его в качестве результата.

😎 Решение:

class Solution {
    function shortestDistance($words, $word1, $word2) {
        $minDistance = count($words);
        for ($i = 0; $i < count($words); $i++) {
            if ($words[$i] == $word1) {
                for ($j = 0; $j < count($words); $j++) {
                    if ($words[$j] == $word2) {
                        $minDistance = min($minDistance, abs($i - $j));
                    }
                }
            }
        }
        return $minDistance;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 244. Shortest Word Distance II

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

Реализуйте класс WordDistance:

WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

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

2️⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3️⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

// PHP
class WordDistance {
    private $locations;

    function __construct($words) {
        $this->locations = [];
        foreach ($words as $i => $word) {
            if (!isset($this->locations[$word])) {
                $this->locations[$word] = [];
            }
            $this->locations[$word][] = $i;
        }
    }

    function shortest($word1, $word2) {
        $loc1 = $this->locations[$word1];
        $loc2 = $this->locations[$word2];
        $l1 = 0;
        $l2 = 0;
        $minDiff = PHP_INT_MAX;

        while ($l1 < count($loc1) && $l2 < count($loc2)) {
            $minDiff = min($minDiff, abs($loc1[$l1] - $loc2[$l2]));
            if ($loc1[$l1] < $loc2[$l2]) {
                $l1++;
            } else {
                $l2++;
            }
        }
        return $minDiff;

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 245. Shortest Word Distance II

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.

Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

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

1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3️⃣Верните значение переменной shortestDistance.

😎 Решение:

class Solution {
    function shortestWordDistance($wordsDict, $word1, $word2) {
        $indices1 = [];
        $indices2 = [];
        foreach ($wordsDict as $i => $word) {
            if ($word == $word1) {
                $indices1[] = $i;
            }
            if ($word == $word2) {
                $indices2[] = $i;
            }
        }

        $shortestDistance = PHP_INT_MAX;
        foreach ($indices1 as $index) {
            $x = $this->upper_bound($indices2, $index);
            if ($x < count($indices2)) {
                $shortestDistance = min($shortestDistance, $indices2[$x] - $index);
            }
            if ($x > 0 && $indices2[$x - 1] != $index) {
                $shortestDistance = min($shortestDistance, $index - $indices2[$x - 1]);
            }
        }
        return $shortestDistance;
    }

    function upper_bound($arr, $val) {
        $left = 0;
        $right = count($arr);
        while ($left < $right) {
            $mid = (int

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 246. Strobogrammatic Number

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.

Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: num = "69"
Output: true

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

1️⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2️⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3️⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    function isStrobogrammatic($num) {
        $rotated = '';
        for ($i = strlen($num) - 1; $i >= 0; $i--) {
            $c = $num[$i];
            if ($c == '0' || $c == '1' || $c == '8') {
                $rotated .= $c;
            } else if ($c == '6') {
                $rotated .= '9';
            } else if ($c == '9') {
                $rotated .= '6';
            } else {
                return false;
            }
        }
        return $num == $rotated;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 247. Strobogrammatic Number II

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

Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: n = 2
Output: ["11","69","88","96"]

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

1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

class Solution {
    private $reversiblePairs = [
        ['0', '0'], ['1', '1'],
        ['6', '9'], ['8', '8'], ['9', '6']
    ];

    private function generateStroboNumbers($n, $finalLength) {
        if ($n == 0) {
            return [""];
        }

        if ($n == 1) {
            return ["0", "1", "8"];
        }

        $prevStroboNums = $this->generateStroboNumbers($n - 2, $finalLength);
        $currStroboNums = [];

        foreach ($prevStroboNums as $prevStroboNum) {
            foreach ($this->reversiblePairs as $pair) {
                if ($pair[0] != '0' || $n != $finalLength) {
                    $currStroboNums[] = $pair[0] . $prevStroboNum . $pair[1];
                }
            }
        }

        return $currStroboNums;
    }

    public function findStrobogrammatic($n) {
        return $this->generateStroboNumbers($n, $n);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 249. Group Shifted Strings

Выполните следующие операции сдвига на строке:

Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".
Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".
Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.

Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.

Пример:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

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

1️⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26.

2️⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению.

3️⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups.

😎 Решение:

class Solution {
    private function shiftLetter($letter, $shift) {
        return chr((ord($letter) - $shift + 26) % 26 + ord('a'));
    }

    private function getHash($s) {
        $shift = ord($s[0]);
        $hashKey = '';

        for ($i = 0; $i < strlen($s); $i++) {
            $hashKey .= $this->shiftLetter($s[$i], $shift);
        }

        return $hashKey;
    }

    public function groupStrings($strings) {
        $mapHashToList = [];

        foreach ($strings as $str) {
            $hashKey = $this->getHash($str);
            if (!isset($mapHashToList[$hashKey])) {
                $mapHashToList[$hashKey] = [];
            }
            $mapHashToList[$hashKey][] = $str;
        }

        return array_values($mapHashToList);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 250. Count Univalue Subtrees

Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями.

Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.

Пример:

Input: root = [5,1,5,5,5,null,5]
Output: 4

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

1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.

2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, верните true.
Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false.

3️⃣Верните count.

😎 Решение:

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

class Solution {
    private $count = 0;

    private function dfs($node) {
        if ($node === null) {
            return true;
        }

        $isLeftUniValue = $this->dfs($node->left);
        $isRightUniValue = $this->dfs($node->right);

        if ($isLeftUniValue && $isRightUniValue) {
            if ($node->left !== null && $node->left->val !== $node->val) {
                return false;
            }
            if ($node->right !== null && $node->right->val !== $node->val) {
                return false;
            }
            $this->count++;
            return true;
        }
        return false;
    }

    public function countUnivalSubtrees($root) {
        $this->dfs($root);
        return $this->count;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 251. Flatten 2D Vector

Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.

Реализуйте класс Vector2D:

Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.

Пример:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

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

1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента.

2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.

3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().

😎 Решение:

class Vector2D {
    private $nums;
    private $position;

    public function __construct($v) {
        $this->nums = [];
        foreach ($v as $innerList) {
            $this->nums = array_merge($this->nums, $innerList);
        }
        $this->position = -1;
    }

    public function next() {
        $this->position++;
        return $this->nums[$this->position];
    }

    public function hasNext() {
        return $this->position + 1 < count($this->nums);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых