PHP | LeetCode
Сайт: easyoffer.ru Реклама: @easyoffer_adv
إظهار المزيد
Network:822
المشتركون
لا توجد بيانات24 ساعات
+67 أيام
+4730 أيام
- المشتركون
- التغطية البريدية
- ER - نسبة المشاركة
جاري تحميل البيانات...
معدل نمو المشترك
جاري تحميل البيانات...
#medium
Задача: 249. Group Shifted Strings
Выполните следующие операции сдвига на строке:
Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".
Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".
Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.
Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...
Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.
Пример:
Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"] Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]👨💻 Алгоритм: 1️⃣Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26. 2️⃣Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению. 3️⃣Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups. 😎 Решение:
class Solution {
private function shiftLetter($letter, $shift) {
return chr((ord($letter) - $shift + 26) % 26 + ord('a'));
}
private function getHash($s) {
$shift = ord($s[0]);
$hashKey = '';
for ($i = 0; $i < strlen($s); $i++) {
$hashKey .= $this->shiftLetter($s[$i], $shift);
}
return $hashKey;
}
public function groupStrings($strings) {
$mapHashToList = [];
foreach ($strings as $str) {
$hashKey = $this->getHash($str);
if (!isset($mapHashToList[$hashKey])) {
$mapHashToList[$hashKey] = [];
}
$mapHashToList[$hashKey][] = $str;
}
return array_values($mapHashToList);
}
}#medium
Задача: 247. Strobogrammatic Number II
Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
Input: n = 2 Output: ["11","69","88","96"]👨💻 Алгоритм: 1️⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа. 2️⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n: Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"]. Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns. Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n. 3️⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums. 😎 Решение:
class Solution {
private $reversiblePairs = [
['0', '0'], ['1', '1'],
['6', '9'], ['8', '8'], ['9', '6']
];
private function generateStroboNumbers($n, $finalLength) {
if ($n == 0) {
return [""];
}
if ($n == 1) {
return ["0", "1", "8"];
}
$prevStroboNums = $this->generateStroboNumbers($n - 2, $finalLength);
$currStroboNums = [];
foreach ($prevStroboNums as $prevStroboNum) {
foreach ($this->reversiblePairs as $pair) {
if ($pair[0] != '0' || $n != $finalLength) {
$currStroboNums[] = $pair[0] . $prevStroboNum . $pair[1];
}
}
}
return $currStroboNums;
}
public function findStrobogrammatic($n) {
return $this->generateStroboNumbers($n, $n);
}
}#easy
Задача: 246. Strobogrammatic Number
Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
Input: num = "69" Output: true👨💻 Алгоритм: 1️⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false. 2️⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку. 3️⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false. 😎 Решение:
class Solution {
function isStrobogrammatic($num) {
$rotated = '';
for ($i = strlen($num) - 1; $i >= 0; $i--) {
$c = $num[$i];
if ($c == '0' || $c == '1' || $c == '8') {
$rotated .= $c;
} else if ($c == '6') {
$rotated .= '9';
} else if ($c == '9') {
$rotated .= '6';
} else {
return false;
}
}
return $num == $rotated;
}
}#medium
Задача: 245. Shortest Word Distance II
Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.
Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.
Пример:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1👨💻 Алгоритм: 1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX. 2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают. 3️⃣Верните значение переменной shortestDistance. 😎 Решение:
class Solution {
function shortestWordDistance($wordsDict, $word1, $word2) {
$indices1 = [];
$indices2 = [];
foreach ($wordsDict as $i => $word) {
if ($word == $word1) {
$indices1[] = $i;
}
if ($word == $word2) {
$indices2[] = $i;
}
}
$shortestDistance = PHP_INT_MAX;
foreach ($indices1 as $index) {
$x = $this->upper_bound($indices2, $index);
if ($x < count($indices2)) {
$shortestDistance = min($shortestDistance, $indices2[$x] - $index);
}
if ($x > 0 && $indices2[$x - 1] != $index) {
$shortestDistance = min($shortestDistance, $index - $indices2[$x - 1]);
}
}
return $shortestDistance;
}
function upper_bound($arr, $val) {
$left = 0;
$right = count($arr);
while ($left < $right) {
$mid = (int#medium
Задача: 244. Shortest Word Distance II
Создайте структуру данных, которая будет инициализироваться массивом строк, а затем должна отвечать на запросы о наименьшем расстоянии между двумя разными строками из массива.
Реализуйте класс WordDistance:
WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.
Пример:
Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding"); // return 1// PHP
class WordDistance {
private $locations;
function __construct($words) {
$this->locations = [];
foreach ($words as $i => $word) {
if (!isset($this->locations[$word])) {
$this->locations[$word] = [];
}
$this->locations[$word][] = $i;
}
}
function shortest($word1, $word2) {
$loc1 = $this->locations[$word1];
$loc2 = $this->locations[$word2];
$l1 = 0;
$l2 = 0;
$minDiff = PHP_INT_MAX;
while ($l1 < count($loc1) && $l2 < count($loc2)) {
$minDiff = min($minDiff, abs($loc1[$l1] - $loc2[$l2]));
if ($loc1[$l1] < $loc2[$l2]) {
$l1++;
} else {
$l2++;
}
}
return $minDiff;#easy
Задача: 243. Shortest Word Distance
Дан массив строк
wordsDict и две разные строки, которые уже существуют в массиве: word1 и word2. Верните кратчайшее расстояние между этими двумя словами в списке.
Пример:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice" Output: 3👨💻 Алгоритм: 1️⃣Начните с перебора всего массива для поиска первого слова. Каждый раз, когда вы находите встречу первого слова, запомните его позицию. 2️⃣При каждом обнаружении первого слова переберите массив в поисках ближайшего вхождения второго слова, сохраняя позицию и сравнивая расстояние с предыдущими найденными. 3️⃣Сохраняйте минимальное найденное расстояние между двумя словами и возвращайте его в качестве результата. 😎 Решение:
class Solution {
function shortestDistance($words, $word1, $word2) {
$minDistance = count($words);
for ($i = 0; $i < count($words); $i++) {
if ($words[$i] == $word1) {
for ($j = 0; $j < count($words); $j++) {
if ($words[$j] == $word2) {
$minDistance = min($minDistance, abs($i - $j));
}
}
}
}
return $minDistance;
}
}Photo unavailableShow in Telegram
👨💻 sudo cd
Если ты сидишь на Linux, то знаешь, что будет ошибка. А я знаю канал, где подобные тесты выходят каждый день.
Тесты на вывод команд + тесты по Linux на этом канале!
👉 sudo Зайди к нам, тут много интересного
#easy
Задача: 242. Valid Anagram
Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае.
Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.
Пример:
Input: s = "anagram", t = "nagaram" Output: true👨💻 Алгоритм: 1️⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z'). 2️⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы. 3️⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s. 😎 Решение:
function isAnagram($s, $t) {
if (strlen($s) != strlen($t)) {
return false;
}
$count = array_fill(0, 26, 0);
for ($i = 0; $i < strlen($s); $i++) {
$count[ord($s[$i]) - ord('a')]++;
$count[ord($t[$i]) - ord('a')]--;
}
foreach ($count as $c) {
if ($c != 0) {
return false;
}
}
Photo unavailableShow in Telegram
#medium
Задача: 240. Search a 2D Matrix II
Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:
Целые числа в каждой строке отсортированы по возрастанию слева направо.
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз.
Пример:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true👨💻 Алгоритм: 1️⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null. 2️⃣Итерация по диагоналям: Итерируйте по диагоналям матрицы, используя инвариант отсортированности срезов строк и столбцов, начиная с текущей позиции (строка, столбец). Для каждого такого среза используйте бинарный поиск для нахождения целевого значения. 3️⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы. 😎 Решение:
class Solution {
private function binarySearch($matrix, $target, $start, $vertical) {
$lo = $start;
$hi = $vertical ? count($matrix[0]) - 1 : count($matrix) - 1;
while ($hi >= $lo) {
$mid = intdiv($lo + $hi, 2);
$value = $vertical ? $matrix[$start][$mid] : $matrix[$mid][$start];
if ($value < $target) {
$lo = $mid + 1;
} else if ($value > $target) {
$hi = $mid - 1;
} else {
return true;
}
}
return false;
}
public function searchMatrix($matrix, $target) {
if ($matrix === null || count($matrix) === 0) return false;
$shorterDim = min(count($matrix), count($matrix[0]));
for ($i = 0; $i < $shorterDim; $i++) {
if ($this->binarySearch($matrix, $target, $i, true) || $this->binarySearch($matrix, $target, $i, false)) {
return true;
}
}
return false;
}
}#easy
Задача: 263. Ugly Number
Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.
Дано целое число n, верните true, если n является уродливым числом.
Пример:
Input: n = 6 Output: true Explanation: 6 = 2 × 3👨💻 Алгоритм: 1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым. 2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5. 3️⃣Если после всех делений n равно 1, верните true, иначе верните false. 😎 Решение:
class Solution {
function isUgly($n) {
if ($n <= 0) {
return false;
}
foreach ([2, 3, 5] as $factor) {
$n = $this->keepDividingWhenDivisible($n, $factor);
}
return $n == 1;
}
private function keepDividingWhenDivisible($dividend, $divisor) {
while ($dividend % $divisor == 0) {
$dividend /= $divisor;
}
return $dividend;
}
}اختر خطة مختلفة
تسمح خطتك الحالية بتحليلات لما لا يزيد عن 5 قنوات. للحصول على المزيد، يُرجى اختيار خطة مختلفة.