اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
PHP | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+pSDoLEZBQRZlNmFi Вопросы собесов t.me/+RJaDhjYaQDo2Njcy Вакансии t.me/+J-DKRUtjUgMxZGNi
نمایش بیشتر1 387
مشترکین
-124 ساعت
+37 روز
-1030 روز
آرشیو پست ها
1 387
Задача: 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];
}1 387
Задача: 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;
}
}1 387
Задача: 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;
}1 387
Задача: 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];
}1 387
Задача: 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;
}
}1 387
Задача: 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];
}1 387
Задача: 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;
}1 387
Задача: 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.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;
}
}1 387
Задача: 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.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);
}
}1 387
Задача: 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.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;
}
}1 387
![Задача: 280. Wiggle Sort Сложность: medium Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] &g](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDACgcHiMeGSgjISMtKygwPGRBPDc3PHtYXUlkkYCZlo+AjIqgtObDoKrarYqMyP/L2u71////m8H////6/+b9//j/2wBDASstLTw1PHZBQXb4pYyl+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj/wAARCAAUACgDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwDYLY7H8qb5nsfyp2Bn/wCvSFQ3UUAAbPajdUL70y2E2juSaRLlP42UemM0rj5WWAeaKQEMoI6GimIX8aMe5oooACOOpprLnHJH0NFFAAq853N+dFFFAH//2Q==)
Задача: 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);
}
}
}
}1 387
Задача: 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]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;
}
}1 387
Задача: 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;
}1 387
Задача: 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;
}
}1 387
Задача: 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;
}
}1 387
Задача: 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;
}
}1 387
Задача: 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;
}1 387
Задача: 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;
}1 387
Задача: 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].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;
}
}1 387
Задача: 247. Strobogrammatic Number II
Сложность: medium
Дано целое число 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);
}
}