现已上线！2025 年 Telegram 研究 — 年度关键洞察 
PHP | LeetCode
前往频道在 Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+pSDoLEZBQRZlNmFi Вопросы собесов t.me/+RJaDhjYaQDo2Njcy Вакансии t.me/+J-DKRUtjUgMxZGNi
显示更多1 385
订阅者
+124 小时
+27 天
-1330 天
帖子存档
1 385
Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium
Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.
Пример:
Input: stones = [7,4,9] Output: [1,2]👨💻 Алгоритм: 1⃣Сортировка: Сначала отсортируем массив камней. 2⃣Максимальное количество ходов: Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня. 3⃣Минимальное количество ходов: Минимальное количество ходов можно определить следующим образом: Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни. Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0. В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место). 😎 Решение:
function numMovesStonesII($stones) {
sort($stones);
$n = count($stones);
$maxMoves = $stones[$n-1] - $stones[0] + 1 - $n;
$maxMoves -= min($stones[1] - $stones[0] - 1, $stones[$n-1] - $stones[$n-2] - 1);
$minMoves = PHP_INT_MAX;
$j = 0;
for ($i = 0; $i < $n; $i++) {
while ($j < $n && $stones[$j] - $stones[$i] + 1 <= $n) {
$j++;
}
$alreadyInWindow = $j - $i;
if ($alreadyInWindow == $n - 1 && $stones[$j-1] - $stones[$i] + 1 == $n - 1) {
$minMoves = min($minMoves, 2);
} else {
$minMoves = min($minMoves, $n - $alreadyInWindow);
}
}
return [$minMoves, $maxMoves];
}1 385
Задача: 348. Design Tic-Tac-Toe
Сложность: medium
Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:
Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:
TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.
Пример:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1]👨💻 Алгоритм: 1⃣Инициализация: Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно. Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно. Инициализируйте размер доски n. 2⃣Выполнение хода: Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода. Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal. 3⃣Проверка победы: Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя. Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода. 😎 Решение:
class TicTacToe {
private $n;
private $rows;
private $cols;
private $diagonal;
private $antiDiagonal;
function __construct($n) {
$this->n = $n;
$this->rows = array_fill(0, $n, 0);
$this->cols = array_fill(0, $n, 0);
$this->diagonal = 0;
$this->antiDiagonal = 0;
}
function move($row, $col, $player) {
$add = $player === 1 ? 1 : -1;
$this->rows[$row] += $add;
$this->cols[$col] += $add;
if ($row === $col) {
$this->diagonal += $add;
}
if ($row + $col === $this->n - 1) {
$this->antiDiagonal += $add;
}
if (abs($this->rows[$row]) === $this->n ||
abs($this->cols[$col]) === $this->n ||
abs($this->diagonal) === $this->n ||
abs($this->antiDiagonal) === $this->n) {
return $player;
}
return 0;
}
}1 385
Задача: 1087. Brace Expansion
Сложность: medium
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]class Solution {
private function storeFirstOptions($s, $startPos, &$firstOptions) {
if ($s[$startPos] != '{') {
$firstOptions[] = $s[$startPos];
} else {
$startPos++;
while ($s[$startPos] != '}') {
if ($s[$startPos] >= 'a' && $s[$startPos] <= 'z') {
$firstOptions[] = $s[$startPos];
}
$startPos++;
}
sort($firstOptions);
}
return $startPos + 1;
}
private function findAllWords($s, $startPos) {
if ($startPos == strlen($s)) {
return [""];
}
$firstOptions = [];
$remStringStartPos = $this->storeFirstOptions($s, $startPos, $firstOptions);
$wordsWithRemString = $this->findAllWords($s, $remStringStartPos);
$expandedWords = [];
foreach ($firstOptions as $c) {
foreach ($wordsWithRemString as $word) {
$expandedWords[] = $c . $word;
}
}
return $expandedWords;
}
public function expand($s) {
return $this->findAllWords($s, 0);
}
}1 385
Задача: 155. Min Stack
Сложность: medium
Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время.
Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.
Вы должны реализовать решение с временной сложностью O(1) для каждой функции.
Пример:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2class MinStack {
private $stack = [];
public function __construct() {
$this->stack = [];
}
private function last() {
return end($this->stack);
}
public function push($x) {
if (empty($this->stack)) {
array_push($this->stack, [$x, $x]);
return;
}
$currentMin = $this->last()[1];
array_push($this->stack, [$x, min($currentMin, $x)]);
}
public function pop() {
array_pop($this->stack);
}
public function top() {
$last = $this->last();
return $last[0];
}
public function getMin() {
$last = $this->last();
return $last[1];
}
}1 385
Задача: 205. Isomorphic Strings
Сложность: easy
Даны две строки s и t, определите, являются ли они изоморфными.
Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.
Все вхождения одного символа должны быть заменены другим символом, сохраняя порядок символов. Два символа не могут отображаться в один и тот же символ, но один символ может отображаться сам на себя.
Пример:
Input: s = "egg", t = "add" Output: true👨💻 Алгоритм: 1⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s. 2⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению. 3⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам. 😎 Решение:
class Solution {
function isIsomorphic($s, $t) {
$mappingStoT = [];
$mappingTtoS = [];
for ($i = 0; $i < strlen($s); ++$i) {
$c1 = $s[$i];
$c2 = $t[$i];
if (!isset($mappingStoT[$c1]) && !isset($mappingTtoS[$c2])) {
$mappingStoT[$c1] = $c2;
$mappingTtoS[$c2] = $c1;
} else if (($mappingStoT[$c1] ?? null) !== $c2 || ($mappingTtoS[$c2] ?? null) !== $c1) {
return false;
}
}
return true;
}
}1 385
Главный навык на ближайшие годы — ВАЙБ-КОДИНГ
ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня
И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную.
Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg
1 385
Задача: 1248. Count Number of Nice Subarrays
Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
Input: arr = [1,2] Output: 2👨💻 Алгоритм: 1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1. 2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц. 3⃣Подсчитайте количество таких подмассивов и верните этот результат. 😎 Решение:
class Solution {
function numberOfSubarrays($nums, $k) {
return $this->atMost($nums, $k) - $this->atMost($nums, $k - 1);
}
private function atMost($nums, $k) {
$res = 0;
$left = 0;
$count = 0;
for ($right = 0; $right < count($nums); $right++) {
if ($nums[$right] % 2 === 1) $count++;
while ($count > $k) {
if ($nums[$left++] % 2 === 1) $count--;
}
$res += $right - $left + 1;
}
return $res;
}
}1 385
Задача: 958. Check Completeness of a Binary Tree
Сложность: medium
Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.
В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.
Пример:
Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
👨💻 Алгоритм:
1⃣Если корень дерева равен null, верните true.
2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.
3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.
😎 Решение:
class Solution {
/**
* @param TreeNode $root
* @return Boolean
*/
function isCompleteTree($root) {
if ($root === null) {
return true;
}
$queue = [$root];
$nullNodeFound = false;
while (!empty($queue)) {
$node = array_shift($queue);
if ($node === null) {
$nullNodeFound = true;
} else {
if ($nullNodeFound) {
return false;
}
$queue[] = $node->left;
$queue[] = $node->right;
}
}
return true;
}
}1 385
Задача: 979. Distribute Coins in Binary Tree
Сложность: medium
Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.
За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.
Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.
Пример:
Input: root = [3,0,0] Output: 2 Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.👨💻 Алгоритм: 1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0. 2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves. 3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves. 😎 Решение:
class Solution {
private $moves;
function distributeCoins($root) {
$this->moves = 0;
$this->dfs($root);
return $this->moves;
}
private function dfs($current) {
if ($current == null) return 0;
$leftCoins = $this->dfs($current->left);
$rightCoins = $this->dfs($current->right);
$this->moves += abs($leftCoins) + abs($rightCoins);
return $current->val - 1 + $leftCoins + $rightCoins;
}
}1 385
Задача: 441. Arranging Coins
Сложность: medium
У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.
Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.
Пример:
Input: n = 5 Output: 2 Explanation: Because the 3rd row is incomplete, we return 2.👨💻 Алгоритм: 1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций. 2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N. 3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2]. 😎 Решение:
class Solution {
function arrangeCoins($n) {
return (int)(sqrt(2 * $n + 0.25) - 0.5);
}
}1 385
Задача: 57. Insert Interval
Сложность: medium
Вам дан массив непересекающихся интервалов
intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.
Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).
Верните массив intervals после вставки.
Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.
Пример:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]👨💻 Алгоритм: 1⃣Инициализация переменных: Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата. 2⃣Обработка случаев без перекрытия и с перекрытием: В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему. В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один. 3⃣Обработка интервалов после вставки: Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним. Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом. 😎 Решение:
class Solution {
public function insert($intervals, $newInterval) {
$res = [];
$i = 0;
// Process intervals with no overlap before the new interval
while ($i < count($intervals) && $intervals[$i][1] < $newInterval[0]) {
array_push($res, $intervals[$i]);
$i++;
}
// Merge overlapping intervals with newInterval
while ($i < count($intervals) && $newInterval[1] >= $intervals[$i][0]) {
$newInterval[0] = min($newInterval[0], $intervals[$i][0]);
$newInterval[1] = max($newInterval[1], $intervals[$i][1]);
$i++;
}
array_push($res, $newInterval);
// Append remaining intervals after merging
while ($i < count($intervals)) {
array_push($res, $intervals[$i]);
$i++;
}
return $res;
}
}1 385
Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium
Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.
Пример:
Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.class Solution {
function minSwaps($data) {
$ones = array_sum($data);
$cnt_one = 0;
$max_one = 0;
$left = 0;
$right = 0;
while ($right < count($data)) {
$cnt_one += $data[$right++];
if ($right - $left > $ones) {
$cnt_one -= $data[$left++];
}
$max_one = max($max_one, $cnt_one);
}
return $ones - $max_one;
}
}1 385
Задача: 1396. Design Underground System
Сложность: medium
Подземная железнодорожная система отслеживает время поездок между станциями для вычисления среднего времени поездки от одной станции до другой.
Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке.
Пример:
Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
👨💻 Алгоритм:
1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.
2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.
3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.
😎 Решение:
class UndergroundSystem {
private $journeyData;
private $checkInData;
function __construct() {
$this->journeyData = [];
$this->checkInData = [];
}
function checkIn($id, $stationName, $t) {
$this->checkInData[$id] = [$stationName, $t];
}
function checkOut($id, $stationName, $t) {
list($startStation, $startTime) = $this->checkInData[$id];
unset($this->checkInData[$id]);
$routeKey = "{$startStation}->{$stationName}";
$tripTime = $t - $startTime;
if (!isset($this->journeyData[$routeKey])) {
$this->journeyData[$routeKey] = [0, 0];
}
list($totalTime, $trips) = $this->journeyData[$routeKey];
$this->journeyData[$routeKey] = [$totalTime + $tripTime, $trips + 1];
}
function getAverageTime($startStation, $endStation) {
list($totalTime, $trips) = $this->journeyData["{$startStation}->{$endStation}"];
return $totalTime / $trips;
}
}1 385
Задача: 372. Super Pow
Сложность: medium
Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.
Пример:
Input: a = 2, b = [3] Output: 8👨💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:
class Solution {
function getSum($a, $b) {
$x = abs($a);
$y = abs($b);
if ($x < $y) return $this->getSum($b, $a);
$sign = $a > 0 ? 1 : -1;
if ($a * $b >= 0) {
while ($y != 0) {
$carry = ($x & $y) << 1;
$x ^= $y;
$y = $carry;
}
} else {
while ($y != 0) {
$borrow = ((~$x) & $y) << 1;
$x ^= $y;
$y = $borrow;
}
}
return $x * $sign;
}
}1 385
Задача: 152. Maximum Product Subarray
Сложность: Medium
Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.👨💻 Алгоритм: 1⃣Инициализация: Если массив nums пуст, возвращаем 0, так как нет элементов для обработки. Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения. 2⃣Перебор элементов: Используем вложенные циклы для обработки всех возможных подмассивов: Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива. Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив. 3⃣Вычисление произведения и обновление результата: Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого. Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result. 😎 Решение:
class Solution {
function maxProduct($nums) {
if (count($nums) == 0) return 0;
$result = $nums[0];
for ($i = 0; $i < count($nums); $i++) {
$accu = 1;
for ($j = $i; $j < count($nums); $j++) {
$accu *= $nums[$j];
$result = max($result, $accu);
}
}
return $result;
}
}1 385
🖼️ Стажировки и вакансии для PHP разработчиков.
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
👉 @jobs_php
🤖 ML & DS 👩💻 DevOps
👨✈️ ИБ & OSINT 👣 Go
👩💻 Mobile 👩💻 C#
👩💻 Node.js 👩💻 Python
🔎 QA 👩💻 Java
👩💻 UX/UI 👩💻 Frontend
🖼️ PHP 📋 Analyst
💼 1C 🖥 SQL
👩💻 IT HR
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
1 385
Задача: 594. Longest Harmonious Subsequence
Сложность: easy
Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1.
Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.
Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.
Пример:
Input: nums = [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].👨💻 Алгоритм: 1⃣Пройдитесь по массиву, создавая словарь для подсчета частоты каждого элемента. 2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности. 3⃣Верните максимальную длину гармоничной подпоследовательности. 😎 Решение:
class Solution {
function findLHS($nums) {
$count = [];
$res = 0;
foreach ($nums as $num) {
if (isset($count[$num])) {
$count[$num]++;
} else {
$count[$num] = 1;
}
if (isset($count[$num + 1])) {
$res = max($res, $count[$num] + $count[$num + 1]);
}
if (isset($count[$num - 1])) {
$res = max($res, $count[$num] + $count[$num - 1]);
}
}
return $res;
}
}1 385
Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium
Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.
Пример:
Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de"👨💻 Алгоритм: 1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления. 2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления. 3⃣Создайте новую строку, удалив все помеченные скобки. 😎 Решение:
class Solution {
function minRemoveToMakeValid($s) {
$stack = [];
$s = str_split($s);
for ($i = 0; $i < count($s); $i++) {
if ($s[$i] == '(') {
array_push($stack, $i);
} elseif ($s[$i] == ')') {
if (!empty($stack)) {
array_pop($stack);
} else {
$s[$i] = '';
}
}
}
while (!empty($stack)) {
$s[array_pop($stack)] = '';
}
return implode('', $s);
}
}1 385
Задача: 784. Letter Case Permutation
Сложность: medium
Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.
Пример:
Input: s = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"]👨💻 Алгоритм: 1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине. 2⃣Если c является цифрой, мы добавим его к каждому слову. 3⃣Продолжайте процесс для всех символов в строке, чтобы получить все возможные комбинации. 😎 Решение:
class Solution {
function letterCasePermutation($S) {
$ans = [[]];
foreach (str_split($S) as $char) {
$n = count($ans);
if (ctype_alpha($char)) {
for ($i = 0; $i < $n; $i++) {
$ans[] = $ans[$i];
$ans[$i][] = strtolower($char);
$ans[$n + $i][] = strtoupper($char);
}
} else {
for ($i = 0; $i < $n; $i++) {
$ans[$i][] = $char;
}
}
}
return array_map(function($arr) {
return implode('', $arr);
}, $ans);
}
}1 385
Задача: 930. Binary Subarrays With Sum
Сложность: medium
Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.
Пример:
Input: nums = [1,0,1,0,1], goal = 2 Output: 4👨💻 Алгоритм: 1⃣Использовать словарь для хранения количества встреченных сумм префиксов. Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями. 2⃣Пройти по массиву и обновить текущую сумму. Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов. Обновить словарь префиксных сумм. 3⃣Вернуть счетчик подмассивов. 😎 Решение:
function numSubarraysWithSum($nums, $goal) {
$prefixSumCount = [0 => 1];
$currentSum = 0;
$count = 0;
foreach ($nums as $num) {
$currentSum += $num;
if (isset($prefixSumCount[$currentSum - $goal])) {
$count += $prefixSumCount[$currentSum - $goal];
}
if (isset($prefixSumCount[$currentSum])) {
$prefixSumCount[$currentSum]++;
} else {
$prefixSumCount[$currentSum] = 1;
}
}
return $count;
}