PHP | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Mostrar más
Red:1 354
Suscriptores
-124 horas
-47 días
-930 días
Archivo de publicaciones
1 354
#medium
Задача: 281. Zigzag Iterator
Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно.
Реализуйте класс ZigzagIterator:
ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2.
boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае.
int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу.
Пример:
Input: v1 = [1,2], v2 = [3,4,5,6] Output: [1,3,2,4,5,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].👨💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors. Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст. 2⃣Метод next: Удалите первую пару индексов из очереди. Извлеките элемент из соответствующего списка по указанным индексам. Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди. Верните извлеченный элемент. 3⃣Метод hasNext: Проверьте, пуста ли очередь. Верните true, если в очереди есть элементы, и false в противном случае. 😎 Решение:
class ZigzagIterator {
private $vectors = [];
private $queue = [];
public function __construct($v1, $v2) {
$this->vectors[] = $v1;
$this->vectors[] = $v2;
foreach ($this->vectors as $index => $vec) {
if (count($vec) > 0) {
$this->queue[] = [$index, 0];
}
}
}
public function next() {
list($vecIndex, $elemIndex) = array_shift($this->queue);
$nextElemIndex = $elemIndex + 1;
if ($nextElemIndex < count($this->vectors[$vecIndex])) {
$this->queue[] = [$vecIndex, $nextElemIndex];
}
return $this->vectors[$vecIndex][$elemIndex];
}
public function hasNext() {
return count($this->queue) > 0;
}
}1 354
#easy
Задача: 293. Flip Game
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].
Пример:
Input: currentState = "++++" Output: ["--++","+--+","++--"]👨💻 Алгоритм: 1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода. 2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса: Если символы на позициях index и index + 1 равны '+': Создайте новую строку nextState, заменив две последовательные '+' на '--'. Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--" и подстроки после второго '+' до конца. Сохраните созданное nextState в массив nextPossibleStates. 3⃣После цикла верните массив nextPossibleStates, содержащий все возможные следующие состояния. 😎 Решение:
<?php
class Solution {
function generatePossibleNextMoves($currentState) {
$nextPossibleStates = [];
for ($i = 0; $i < strlen($currentState) - 1; $i++) {
if ($currentState[$i] == '+' && $currentState[$i + 1] == '+') {
$nextState = substr($currentState, 0, $i) . "--" . substr($currentState, $i + 2);
$nextPossibleStates[] = $nextState;
}
}
return $nextPossibleStates;
}
}
?>1 354
#medium
Задача: 291. Word Pattern II
Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.
Пример:
Input: pattern = "abab", s = "redblueredblue" Output: true Explanation: One possible mapping is as follows: 'a' -> "red" 'b' -> "blue"👨💻 Алгоритм: 1⃣Инициализация структур данных и определение рекурсивной функции: Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s. Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ. Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону. 2⃣Рекурсивная проверка соответствия: Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false. Получите символ из шаблона по индексу pIndex. Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне. 3⃣Отображение новых подстрок: Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки. Для каждой новой подстроки проверьте, существует ли она уже в ` 😎 Решение:
<?php
class Solution {
function wordPatternMatch($pattern, $s) {
$symbolMap = [];
$wordSet = [];
return $this->isMatch($s, 0, $pattern, 0, $symbolMap, $wordSet);
}
private function isMatch($s, $sIndex, $pattern, $pIndex, &$symbolMap, &$wordSet) {
if ($pIndex == strlen($pattern)) {
return $sIndex == strlen($s);
}
$symbol = $pattern[$pIndex];
if (isset($symbolMap[$symbol])) {
$word = $symbolMap[$symbol];
if (substr($s, $sIndex, strlen($word)) !== $word) {
return false;
}
return $this->isMatch($s, $sIndex + strlen($word), $pattern, $pIndex + 1, $symbolMap, $wordSet);
}
for ($k = $sIndex + 1; $k <= strlen($s); $k++) {
$newWord = substr($s, $sIndex, $k - $sIndex);
if (in_array($newWord, $wordSet)) {
continue;
}
$symbolMap[$symbol] = $newWord;
$wordSet[] = $newWord;
if ($this->isMatch($s, $k, $pattern, $pIndex + 1, $symbolMap, $wordSet)) {
return true;
}
unset($symbolMap[$symbol]);
array_pop($wordSet);
}
return false;
}
}
?>1 354
#easy
Задача: 290. Word Pattern
Дан шаблон и строка s, необходимо определить, следует ли строка s этому шаблону.
Здесь "следует" означает полное соответствие, такое что существует биекция между буквой в шаблоне и непустым словом в строке s.
Пример:
Input: pattern = "abba", s = "dog cat cat dog" Output: true👨💻 Алгоритм: 1⃣Разделение строки на слова: Разделите строку s на отдельные слова. Если количество слов не равно длине шаблона, возвращаем false. 2⃣Создание отображений: Создайте два словаря: один для отображения букв шаблона на слова, другой для слов на буквы шаблона. 3⃣Проверка биекции: Пройдите по каждому символу шаблона и соответствующему слову. Если символ уже в словаре и не соответствует текущему слову или слово уже в словаре и не соответствует текущему символу, возвращаем false. Иначе добавляем символ и слово в словари и продолжаем проверку. Если все проверки пройдены, возвращаем true. 😎 Решение:
<?php
class Solution {
function wordPattern($pattern, $s) {
$mapChar = [];
$mapWord = [];
$words = explode(" ", $s);
if (count($words) != strlen($pattern)) {
return false;
}
for ($i = 0; $i < strlen($pattern); $i++) {
$c = $pattern[$i];
$w = $words[$i];
if (!isset($mapChar[$c])) {
if (isset($mapWord[$w])) {
return false;
} else {
$mapChar[$c] = $w;
$mapWord[$w] = $c;
}
} else {
if ($mapChar[$c] != $w) {
return false;
}
}
}
return true;
}
}1 354
#easy
Задача: 292. Nim Game
Вы играете в следующую игру Nim со своим другом:
Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.
Пример:
Input: n = 4 Output: false Explanation: These are the possible outcomes: 1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins. 2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins. 3. You remove 3 stones. Your friend removes the last stone. Your friend wins. In all outcomes, your friend wins.👨💻 Алгоритм: 1⃣Определите базовый случай: Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true. 2⃣Анализ оставшихся камней: Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false. 3⃣Выигрышная стратегия: Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true. 😎 Решение:
<?php
class Solution {
function canWinNim($n) {
return $n % 4 != 0;
}
}1 354
#medium
Задача: 294. Flip Game II
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните true, если начальный игрок может гарантировать победу, и false в противном случае.
Пример:
Input: currentState = "++++" Output: true Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".👨💻 Алгоритм: 1⃣Генерация всех возможных следующих ходов: Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--". 2⃣Рекурсивная проверка выигрыша: Для каждого нового состояния вызовите функцию рекурсивно, чтобы проверить, может ли противник проиграть в этом новом состоянии. Если противник не может сделать ход, верните true, так как начальный игрок гарантирует победу. 3⃣Проверка всех возможных ходов: Если для всех возможных ходов начальный игрок не может гарантировать победу, верните false. Иначе, если есть хотя бы один ход, при котором противник проигрывает, верните true. 😎 Решение:
<?php
class Solution {
function canWin($currentState) {
$stateArray = str_split($currentState);
for ($i = 0; $i < count($stateArray) - 1; $i++) {
if ($stateArray[$i] == '+' && $stateArray[$i + 1] == '+') {
$stateArray[$i] = '-';
$stateArray[$i + 1] = '-';
$newState = implode('', $stateArray);
if (!$this->canWin($newState)) {
$stateArray[$i] = '+';
$stateArray[$i + 1] = '+';
return true;
}
$stateArray[$i] = '+';
$stateArray[$i + 1] = '+';
}
}
return false;
}
}1 354
#hard
Задача: 295. Find Median from Data Stream
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.
Например, для arr = [2, 3, 4] медиана равна 3.
Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.
Реализуйте класс MedianFinder:
MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.
Пример:
Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0👨💻 Алгоритм: 1⃣Храните числа в контейнере с возможностью изменения размера: Создайте массив для хранения чисел. 2⃣Добавление нового числа: Добавьте новое число в массив. 3⃣Вычисление и вывод медианы: Отсортируйте массив. Если размер массива нечетный, верните среднее значение массива. Если размер массива четный, верните среднее арифметическое двух средних значений массива. 😎 Решение:
<?php
class MedianFinder {
private $numbers;
public function __construct() {
$this->numbers = [];
}
public function addNum($num) {
$this->numbers[] = $num;
}
public function findMedian() {
sort($this->numbers);
$n = count($this->numbers);
if ($n % 2 == 0) {
return ($this->numbers[$n / 2 - 1] + $this->numbers[$n / 2]) / 2.0;
} else {
return $this->numbers[$n / 2];
}
}
}
?>1 354
#medium
Задача: 433. Minimum Genetic Mutation
Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.
Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.
Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.
Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.
Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк.
Пример:
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:
function minMutation($start, $end, $bank) {
$queue = [$start];
$seen = [$start => true];
$steps = 0;
while (count($queue) > 0) {
$nodesInQueue = count($queue);
for ($j = 0; $j < $nodesInQueue; $j++) {
$node = array_shift($queue);
if ($node === $end) {
return $steps;
}
foreach (str_split("ACGT") as $c) {
for ($i = 0; $i < strlen($node); $i++) {
$neighbor = substr($node, 0, $i) . $c . substr($node, $i + 1);
if (!isset($seen[$neighbor]) && in_array($neighbor, $bank)) {
$queue[] = $neighbor;
$seen[$neighbor] = true;
}
}
}
}
$steps++;
}
return -1;
}
echo minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"]) . "\n"; // Output: 1
echo minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]) . "\n"; // Output: 2
echo minMutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"]) . "\n"; // Output: 31 354
#hard
Задача: 296. Best Meeting Point
Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия.
Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи.
Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
Пример:
Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] Output: 6 Explanation: Given three friends living at (0,0), (0,4), and (2,2). The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal. So return 6.👨💻 Алгоритм: 1⃣Определение координат домов: Пройдите по сетке и соберите координаты всех домов (ячейки с значением 1) в два списка: один для координат x и один для координат y. 2⃣Нахождение медианы: Отсортируйте списки координат x и y. Найдите медианы в обоих списках. Медианы координат x и y укажут оптимальную точку встречи. 3⃣Вычисление минимального общего расстояния: Вычислите сумму Манхэттенских расстояний от каждого дома до точки встречи, используя найденные медианы в качестве координат точки встречи. Верните это значение как минимальное общее расстояние путешествия. 😎 Решение:
<?php
class Solution {
function minTotalDistance($grid) {
$minDistance = PHP_INT_MAX;
for ($row = 0; $row < count($grid); $row++) {
for ($col = 0; $col < count($grid[0]); $col++) {
$distance = $this->search($grid, $row, $col);
$minDistance = min($distance, $minDistance);
}
}
return $minDistance;
}
private function search($grid, $row, $col) {
$q = [[$row, $col, 0]];
$m = count($grid);
$n = count($grid[0]);
$visited = array_fill(0, $m, array_fill(0, $n, false));
$totalDistance = 0;
while (!empty($q)) {
list($r, $c, $d) = array_shift($q);
if ($r < 0 || $c < 0 || $r >= $m || $c >= $n || $visited[$r][$c]) {
continue;
}
if ($grid[$r][$c] == 1) {
$totalDistance += $d;
}
$visited[$r][$c] = true;
$q[] = [$r + 1, $c, $d + 1];
$q[] = [$r - 1, $c, $d + 1];
$q[] = [$r, $c + 1, $d + 1];
$q[] = [$r, $c - 1, $d + 1];
}
return $totalDistance;
}
}1 354
#hard
Задача: 297. Serialize and Deserialize Binary Tree
Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.
Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева.
Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.
Пример:
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]👨💻 Алгоритм: 1⃣Сериализация дерева: Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree. Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None". 2⃣Пример: Начните с корня, узел 1, строка сериализации становится "1,". Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,". Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None"). Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,"). 3⃣Десериализация строки: Разделите строку на список значений. Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой. 😎 Решение:
<?php
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 Codec {
function rserialize($root, &$str) {
if ($root === null) {
$str .= "null,";
} else {
$str .= $root->val . ",";
$this->rserialize($root->left, $str);
$this->rserialize($root->right, $str);
}
}
function serialize($root) {
$str = "";
$this->rserialize($root, $str);
return $str;
}
function rdeserialize(&$data) {
if ($data[0] === "null") {
array_shift($data);
return null;
}
$root = new TreeNode(intval(array_shift($data)));
$root->left = $this->rdeserialize($data);
$root->right = $this->rdeserialize($data);
return $root;
}
function deserialize($data) {
$dataArray = explode(",", $data);
return $this->rdeserialize($dataArray);
}
}
?>1 354
⚡️ IT-обучение теперь в Telegram!
В cвязи с недавнем замедлением Ютуба — лучшие обучающие каналы переехали в Telegram
Вот каналы для айтишников:
👩💻 PHP: @PHP
🖥 Базы Данных & SQL: @SQL
👩💻 Frontend: @Frontend
⚙️ Backend: @Backend
🤓 Общее айти: @portalToIT
👩💻 Python: @Python
📱 GitHub: @GitHub
👩💻 Java: @Java
👩💻 C#: @Csharp
👩💻 С/С++: @Cpp
👩💻 Golang: @Golang
👩💻 Моб. разработка: @MobDev
👩💻 Разработка игр: @GameDev
👩💻 DevOps: @DevOps
🖥 Data Science: @DataScience
🤔 Хакинг & ИБ: @InfoSec
🐞 Тестирование: @QA
📱 Маркетинг: @Marketing
🖥 Дизайн: @Design
➡️ Сохраняйте себе, чтобы не потерять
1 354
#medium
Задача: 298. Binary Tree Longest Consecutive Sequence
Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений.
Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.
Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути.
Пример:
Input: root = [1,null,3,2,4,null,null,null,5] Output: 3 Explanation: Longest consecutive sequence path is 3-4-5, so return 3.👨💻 Алгоритм: 1⃣Инициализация и начало обхода: Начните обход дерева с корневого узла. Инициализируйте переменную length, чтобы хранить текущую длину последовательного пути, и передавайте её вниз по дереву. 2⃣Сравнение текущего узла с родительским узлом: Для каждого узла сравните его значение со значением родительского узла. Если значение текущего узла на единицу больше значения родительского узла, увеличьте length. Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1. 3⃣Обход дерева: Рекурсивно обходите левое и правое поддерево, передавая обновлённое значение length. В каждом узле обновляйте максимальную длину последовательного пути, если текущая длина больше. 😎 Решение:
<?php
class Solution {
private $maxLength = 0;
public function longestConsecutive($root) {
$this->dfs($root, null, 0);
return $this->maxLength;
}
private function dfs($node, $parent, $length) {
if ($node === null) return;
if ($parent !== null && $node->val === $parent->val + 1) {
$length++;
} else {
$length = 1;
}
$this->maxLength = max($this->maxLength, $length);
$this->dfs($node->left, $node, $length);
$this->dfs($node->right, $node, $length);
}
}
?>1 354
🧑💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом.
🫤 Ты в курсе, что ...
- говорят по-английски — 20% из всех людей.
- Большое кол-во IT документации написано на английском.
Хочешь понимать код лучше? Изучи язык, который используется в его основе.
📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут:
- Тесты для изучения английского: проверьте свои знания на практике.
- Английский через мемы: учите язык весело и с интересом.
- Шпаргалки для повторения: закрепите знания быстро и эффективно.
- Английский сленг программиста: станьте настоящим профи в коммуникации.
🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп.
🌸 Подпишись, do it!
1 354
#medium
Задача: 299. Bulls and Cows
Вы играете в игру "Быки и коровы" со своим другом.
Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией:
Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции.
Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками.
Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга.
Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры.
Пример:
Input: secret = "1807", guess = "7810" Output: "1A3B" Explanation: Bulls are connected with a '|' and cows are underlined: "1807" | "7810"👨💻 Алгоритм: 1⃣Инициализация счетчиков: Инициализируйте количество быков и коров значениями ноль. Создайте хеш-таблицу для хранения символов строки secret и их частот. 2⃣Обход строки guess: Для каждого символа ch в строке guess: Если ch присутствует в строке secret: Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]): Увеличьте количество быков: bulls += 1. Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0). Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]): Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0). Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1. 3⃣Возврат результата: Верните количество быков и коров в формате "xAyB". 😎 Решение:
<?php
class Solution {
function getHint($secret, $guess) {
$h = [];
for ($i = 0; $i < strlen($secret); $i++) {
$ch = $secret[$i];
if (!isset($h[$ch])) {
$h[$ch] = 0;
}
$h[$ch]++;
}
$bulls = 0;
$cows = 0;
$n = strlen($guess);
$secretArray = str_split($secret);
$guessArray = str_split($guess);
for ($idx = 0; $idx < $n; $idx++) {
$ch = $guessArray[$idx];
if (isset($h[$ch])) {
if ($ch == $secretArray[$idx]) {
$bulls++;
if ($h[$ch] <= 0) {
$cows--;
}
} else {
if ($h[$ch] > 0) {
$cows++;
}
}
$h[$ch]--;
}
}
return "{$bulls}A{$cows}B";
}
}
?>1 354
+4
Senior-разработчик создал крутейший канал про SQL
Благодаря простым картинкам даже новичок научится разрабатывать приложения с использованием баз данных.
Присоединяйтесь: @SQL
1 354
#medium
Задача: 300. Longest Increasing Subsequence
Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.
Пример:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.👨💻 Алгоритм: 1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i. 2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1). 3⃣Верните максимальное значение из dp. 😎 Решение:
<?php
function lengthOfLIS($nums) {
$n = count($nums);
if ($n === 0) {
return 0;
}
$dp = array_fill(0, $n, 1);
for ($i = 1; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($nums[$i] > $nums[$j]) {
$dp[$i] = max($dp[$i], $dp[$j] + 1);
}
}
}
return max($dp);
}1 354
🧑💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом.
🫤 Ты в курсе, что ...
- говорят по-английски — 20% из всех людей.
- Большое кол-во IT документации написано на английском.
Хочешь понимать код лучше? Изучи язык, который используется в его основе.
📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут:
- Тесты для изучения английского: проверьте свои знания на практике.
- Английский через мемы: учите язык весело и с интересом.
- Шпаргалки для повторения: закрепите знания быстро и эффективно.
- Английский сленг программиста: станьте настоящим профи в коммуникации.
🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп.
🌸 Подпишись, do it!
1 354
🔥 Ресурсы для подготовки к работе в IT! 🔥
1️⃣ База собеседований IT – это уникальная коллекция собеседований от реальных топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 150+ собеседований, чтобы ты мог подготовиться к интервью с уверенностью и успехом.
2️⃣ База тестовых заданий – твоё секретное оружие для успешного прохождения этапов отбора! 📋 Здесь ты найдёшь 121+ тестовых заданий от тех же топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries. Решай реальные задачи и набирайся опыта для будущих собеседований!
🎯 Присоединяйся к базам и прокачай свои шансы на успешное трудоустройство!
1 354
#medium
Задача: 395. Longest Substring with At Least K Repeating Characters
Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.
Если такой подстроки не существует, верните 0.
Пример:
Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.👨💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:
function longestSubstring($s, $k) {
if (strlen($s) == 0 || $k > strlen($s)) {
return 0;
}
$result = 0;
for ($start = 0; $start < strlen($s); $start++) {
$countMap = array_fill(0, 26, 0);
for ($end = $start; $end < strlen($s); $end++) {
$countMap[ord($s[$end]) - ord('a')]++;
if (isValid($countMap, $k)) {
$result = max($result, $end - $start + 1);
}
}
}
return $result;
}
function isValid($countMap, $k) {
$countLetters = 0;
$countAtLeastK = 0;
foreach ($countMap as $count) {
if ($count > 0) $countLetters++;
if ($count >= $k) $countAtLeastK++;
}
return $countLetters == $countAtLeastK;
}
echo longestSubstring("aaabb", 3); // Output: 3
echo "\n";
echo longestSubstring("ababbc", 2); // Output: 51 354
CodHub теперь в Telegram!
Бесплатные обучающие материалы, которые лучше платных — книги, ресурсы, статьи и курсы топовых вузов страны тут:
👩💻 Материалы по Python
👩💻 Материалы по Frontend
👩💻 Материалы по Java
👩💻 Материалы по С#
👩💻 Материалы по C/C++
👩💻 Материалы по Хакингу
🖥 Материалы по SQL
👩💻 Материалы по Kotlin/Swift
👩💻 Материалы по Linux
🐞 Материалы по QA
👩💻 Материалы по Go
👩💻 Материалы по PHP
Подписываетесь: @CodHub_tg
