Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium
Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.
Пример:
👨💻 Алгоритм:
1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.
2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.
3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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.
👨💻 Алгоритм:
1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.
2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.
3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].
😎 Решение:
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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 57. Insert Interval
Сложность: medium
Вам дан массив непересекающихся интервалов
Вставьте
Верните массив
Обратите внимание, что не обязательно модифицировать массив
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата.
2⃣Обработка случаев без перекрытия и с перекрытием:
В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему.
В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один.
3⃣Обработка интервалов после вставки:
Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.
Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 441. Arranging Coins
Сложность: medium
У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.
Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.
Пример:
👨💻 Алгоритм:
1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций.
2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.
3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 979. Distribute Coins in Binary Tree
Сложность: medium
Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.
За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.
Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.
2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves.
3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 958. Check Completeness of a Binary Tree
Сложность: medium
Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.
В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.
Пример:
👨💻 Алгоритм:
1⃣Если корень дерева равен null, верните true.
2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.
3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1248. Count Number of Nice Subarrays
Сложность: medium
Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.
Пример:
👨💻 Алгоритм:
1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.
2⃣Используя технику скользящего окна (или двух указателей), найдите все подмассивы, содержащие ровно k единиц.
3⃣Подсчитайте количество таких подмассивов и верните этот результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 205. Isomorphic Strings
Сложность: easy
Даны две строки s и t, определите, являются ли они изоморфными.
Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.
Все вхождения одного символа должны быть заменены другим символом, сохраняя порядок символов. Два символа не могут отображаться в один и тот же символ, но один символ может отображаться сам на себя.
Пример:
👨💻 Алгоритм:
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 после окончания итерации по строкам.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 155. Min Stack
Сложность: medium
Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время.
Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.
Вы должны реализовать решение с временной сложностью O(1) для каждой функции.
Пример:
👨💻 Алгоритм:
1⃣Инициализация стека:
Создайте структуру данных, которая будет использоваться для хранения элементов стека. Эта структура должна поддерживать не только обычные операции стека, но и быстрый доступ к минимальному элементу.
Инициализируйте стек с помощью конструктора MinStack(), который подготовит все необходимые структуры данных для дальнейшей работы.
2⃣Работа со стеком:
Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.
3⃣Доступ к элементам:
Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 -2
👨💻 Алгоритм:
1⃣Инициализация стека:
Создайте структуру данных, которая будет использоваться для хранения элементов стека. Эта структура должна поддерживать не только обычные операции стека, но и быстрый доступ к минимальному элементу.
Инициализируйте стек с помощью конструктора MinStack(), который подготовит все необходимые структуры данных для дальнейшей работы.
2⃣Работа со стеком:
Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.
3⃣Доступ к элементам:
Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.
😎 Решение:
class 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];
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1087. Brace Expansion
Сложность: medium
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
👨💻 Алгоритм:
1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.
2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.
3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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"]👨💻 Алгоритм:
1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.
2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.
3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.
😎 Решение:
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);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 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 является победителем.
Пример:
👨💻 Алгоритм:
1⃣Инициализация:
Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно.
Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно.
Инициализируйте размер доски n.
2⃣Выполнение хода:
Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода.
Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal.
3⃣Проверка победы:
Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя.
Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium
Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.
Пример:
👨💻 Алгоритм:
1⃣Сортировка:
Сначала отсортируем массив камней.
2⃣Максимальное количество ходов:
Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня.
3⃣Минимальное количество ходов:
Минимальное количество ходов можно определить следующим образом:
Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни.
Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0.
В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место).
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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];
}Ставь 👍 и забирай 📚 Базу знаний