PHP | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد
الشبكة:1 356
المشتركون
-124 ساعات
-67 أيام
-930 أيام
أرشيف المشاركات
1 356
Задача: 1014. Best Sightseeing Pair
Сложность: medium
Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.
Пример:
Input: values = [8,1,5,2,6] Output: 11👨💻 Алгоритм: 1⃣Инициализация переменных: Инициализируйте переменную max_score для хранения максимальной оценки пары. Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву. 2⃣Проход по массиву: Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value. Обновите значение max_score, если текущая оценка больше. Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value. 3⃣Возврат результата: Верните значение max_score как максимальную оценку пары достопримечательностей. 😎 Решение:
class Solution {
function maxScoreSightseeingPair($values) {
$maxScore = 0;
$maxIPlusValue = $values[0];
for ($j = 1; $j < count($values); $j++) {
$maxScore = max($maxScore, $maxIPlusValue + $values[$j] - $j);
$maxIPlusValue = max($maxIPlusValue, $values[$j] + $j);
}
return $maxScore;
}
}1 356
Задача: 320. Generalized Abbreviation
Сложность: medium
Обобщённая аббревиатура слова может быть построена путём замены несмежных и неперекрывающихся подстрок на их длины.
Например, для слова "abcde" возможны сокращения:
"a3e" — "bcd" заменено на "3"
"1bcd1" — "a" и "e" заменены на "1"
"5" — всё слово заменено на длину
"abcde" — без сокращений
Недопустимы:
"23" — замены "ab" и "cde" смежны
"22de" — замены "ab" и "bc" перекрываются
Нужно вернуть все возможные обобщённые аббревиатуры слова word.
Пример:
Input: word = "a" Output: ["1","a"]👨💻 Алгоритм: 1⃣Создание битовых масок Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур. 2⃣Генерация аббревиатур Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик. 3⃣Перебор всех комбинаций Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1. 😎 Решение:
class Solution {
function generateAbbreviations($word) {
$result = [];
$n = strlen($word);
for ($x = 0; $x < (1 << $n); $x++) {
$result[] = $this->abbr($word, $x);
}
return $result;
}
private function abbr($word, $x) {
$builder = "";
$k = 0;
$n = strlen($word);
for ($i = 0; $i < $n; $i++, $x >>= 1) {
if (($x & 1) == 0) {
if ($k != 0) {
$builder .= $k;
$k = 0;
}
$builder .= $word[$i];
} else {
$k++;
}
}
if ($k != 0) $builder .= $k;
return $builder;
}
}
$sol = new Solution();
print_r($sol->generateAbbreviations("word"));1 356
Задача: 127. Word Ladder
Сложность: Hard
Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:
Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.
Пример:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.👨💻 Алгоритм: 1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние. 2⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий
beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.
3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.
😎 Решение:
function ladderLength($beginWord, $endWord, $wordList) {
$L = strlen($beginWord);
$allComboDict = [];
foreach ($wordList as $word) {
for ($i = 0; $i < $L; $i++) {
$newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
if (!isset($allComboDict[$newWord])) {
$allComboDict[$newWord] = [];
}
$allComboDict[$newWord][] = $word;
}
}
$queue = [[$beginWord, 1]];
$visited = [$beginWord => true];
while (count($queue) > 0) {
$node = array_shift($queue);
$word = $node[0];
$level = $node[1];
for ($i = 0; $i < $L; $i++) {
$newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
if (!isset($allComboDict[$newWord])) {
$allComboDict[$newWord] = [];
}
foreach ($allComboDict[$newWord] as $adjacentWord) {
if ($adjacentWord === $endWord) {
return $level + 1;
}
if (!isset($visited[$adjacentWord])) {
$visited[$adjacentWord] = true;
$queue[] = [$adjacentWord, $level + 1];
}
}
}
}
return 0;
}1 356
Задача: 227. Basic Calculator II
Сложность: medium
Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение.
Целочисленное деление должно округляться к нулю.
Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval().
Пример:
Input: s = "3+2*2" Output: 7👨💻 Алгоритм: 1⃣Вместо использования стека, используем переменную lastNumber для отслеживания значения последнего вычисленного выражения. 2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации. 3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки. 😎 Решение:
class Solution {
function calculate($s) {
$length = strlen($s);
if ($length == 0) return 0;
$currentNumber = 0;
$lastNumber = 0;
$result = 0;
$sign = '+';
for ($i = 0; $i < $length; $i++) {
$currentChar = $s[$i];
if (ctype_digit($currentChar)) {
$currentNumber = ($currentNumber * 10) + intval($currentChar);
}
if (!ctype_digit($currentChar) && !ctype_space($currentChar) || $i == $length - 1) {
if ($sign == '+' || $sign == '-') {
$result += $lastNumber;
$lastNumber = ($sign == '+') ? $currentNumber : -$currentNumber;
} else if ($sign == '*') {
$lastNumber *= $currentNumber;
} else if ($sign == '/') {
$lastNumber /= $currentNumber;
}
$sign = $currentChar;
$currentNumber = 0;
}
}
$result += $lastNumber;
return $result;
}
}1 356
Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium
Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.
Пример:
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] Output: "apple"👨💻 Алгоритм: 1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s. 2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку. 3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку. 😎 Решение:
class Solution {
function isSubsequence($x, $y) {
$j = 0;
for ($i = 0; $i < strlen($y) && $j < strlen($x); $i++) {
if ($x[$j] == $y[$i]) {
$j++;
}
}
return $j == strlen($x);
}
function findLongestWord($s, $d) {
$max_str = "";
foreach ($d as $str) {
if ($this->isSubsequence($str, $s)) {
if (strlen($str) > strlen($max_str) || (strlen($str) == strlen($max_str) && strcmp($str, $max_str) < 0)) {
$max_str = $str;
}
}
}
return $max_str;
}
}1 356
Задача: 758. Bold Words in String
Сложность: medium
При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.
Возвращает после добавления тегов, выделенных жирным шрифтом. Возвращаемая строка должна содержать как можно меньшее количество тегов, и теги должны образовывать допустимую комбинацию.
Пример:
Input: words = ["ab","bc"], s = "aabcd" Output: "a<b>abc</b>d"👨💻 Алгоритм: 1⃣Создайте массив для хранения флагов, указывающих, какие символы в строке a должны быть выделены жирным шрифтом. 2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов. 3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов. 😎 Решение:
function addBoldTags($keywords, $s) {
$n = strlen($s);
$bold = array_fill(0, $n, false);
foreach ($keywords as $word) {
$start = strpos($s, $word);
while ($start !== false) {
for ($i = $start; $i < $start + strlen($word); $i++) {
$bold[$i] = true;
}
$start = strpos($s, $word, $start + 1);
}
}
$result = '';
$i = 0;
while ($i < $n) {
if ($bold[$i]) {
$result .= '<b>';
while ($i < $n && $bold[$i]) {
$result .= $s[$i];
$i++;
}
$result .= '</b>';
} else {
$result .= $s[$i];
$i++;
}
}
return $result;
}1 356
Задача: 1539. Kth Missing Positive Number
Сложность: easy
Дан массив
arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.
Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.
Пример:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.class Solution {
function findKthPositive($arr, $k) {
if ($k <= $arr[0] - 1) {
return $k;
}
$k -= $arr[0] - 1;
$n = count($arr);
for ($i = 0; $i < $n - 1; ++$i) {
$currMissing = $arr[$i + 1] - $arr[$i] - 1;
if ($k <= $currMissing) {
return $arr[$i] + $k;
}
$k -= $currMissing;
}
return $arr[$n - 1] + $k;
}
}1 356
Задача: 46. Permutations
Сложность: medium
Дан массив nums, состоящий из различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [0,1] Output: [[0,1],[1,0]]👨💻 Алгоритм: 1⃣Если длина curr равна длине nums, добавьте копию curr в ans и вернитесь. 2⃣Итерируйтесь по nums. Для каждого num, если num не в curr, выполните следующее: Добавьте num в curr и вызовите backtrack(curr), затем удалите num из curr. 3⃣Вызовите backtrack с изначально пустым curr. Верните ans. 😎 Решение:
function permute($nums) {
$ans = [];
$backtrack = function (&$curr) use (&$ans, &$backtrack, $nums) {
if (count($curr) === count($nums)) {
$ans[] = $curr;
return;
}
foreach ($nums as $num) {
if (!in_array($num, $curr)) {
$curr[] = $num;
$backtrack($curr);
array_pop($curr);
}
}
};
$backtrack([]);
return $ans;
}1 356
Задача: 207. Course Schedule
Сложность: medium
Всего у вас есть numCourses курсов, которые нужно пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните true, если вы можете завершить все курсы. В противном случае верните false.
Пример:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.👨💻 Алгоритм: 1⃣Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1. 2⃣Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов. 3⃣Пока очередь не пуста: Извлеките первый узел из очереди. Увеличьте nodesVisited на 1. Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor. Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь. Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses. 😎 Решение:
class Solution {
function canFinish($numCourses, $prerequisites) {
$indegree = array_fill(0, $numCourses, 0);
$adj = array_fill(0, $numCourses, []);
foreach ($prerequisites as $prerequisite) {
$adj[$prerequisite[1]][] = $prerequisite[0];
$indegree[$prerequisite[0]]++;
}
$q = [];
for ($i = 0; $i < $numCourses; $i++) {
if ($indegree[$i] == 0) {
$q[] = $i;
}
}
$nodesVisited = 0;
while (!empty($q)) {
$node = array_shift($q);
$nodesVisited++;
foreach ($adj[$node] as $neighbor) {
$indegree[$neighbor]--;
if ($indegree[$neighbor] == 0) {
$q[] = $neighbor;
}
}
}
return $nodesVisited == $numCourses;
}
}1 356
Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium
Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.
Пример:
Input ["FindElements","find","find"] [[[-1,null,-1]],[1],[2]] Output [null,false,true]👨💻 Алгоритм: 1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2. 2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов. 3⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений. 😎 Решение:
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 FindElements {
private $root;
private $values;
function __construct($root) {
$this->root = $root;
$this->values = [];
$this->root->val = 0;
$this->values[0] = true;
$this->recover($root);
}
function recover($node) {
if ($node->left !== null) {
$node->left->val = 2 * $node->val + 1;
$this->values[$node->left->val] = true;
$this->recover($node->left);
}
if ($node->right !== null) {
$node->right->val = 2 * $node->val + 2;
$this->values[$node->right->val] = true;
$this->recover($node->right);
}
}
function find($target) {
return isset($this->values[$target]);
}
}1 356
Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard
Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.
Пример:
Input: traversal = "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,7]👨💻 Алгоритм: 1⃣Разбор строки: Пройдите по строке, чтобы определить уровни узлов и их значения. Используйте два счетчика: один для отслеживания текущего уровня (количество тире), второй для значения узла. 2⃣Создание узлов: Создайте новые узлы на основе уровня и значения из строки. Для каждого нового узла найдите его родительский узел из стека и добавьте узел как левого или правого ребенка. 3⃣Построение дерева: Используйте стек для отслеживания текущих узлов на каждом уровне глубины. Когда узел создан, добавьте его в стек. Если узел завершен, уберите его из стека. 😎 Решение:
class TreeNode {
public $val = 0;
public $left = null;
public $right = null;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
function recoverFromPreorder($S) {
$stack = [];
$i = 0;
while ($i < strlen($S)) {
$level = 0;
while ($i < strlen($S) && $S[$i] == '-') {
$level++;
$i++;
}
$value = 0;
while ($i < strlen($S) && is_numeric($S[$i])) {
$value = $value * 10 + intval($S[$i]);
$i++;
}
$node = new TreeNode($value);
if ($level == count($stack)) {
if (!empty($stack)) {
$stack[count($stack) - 1]->left = $node;
}
} else {
while ($level != count($stack)) {
array_pop($stack);
}
$stack[count($stack) - 1]->right = $node;
}
array_push($stack, $node);
}
while (count($stack) > 1) {
array_pop($stack);
}
return $stack[0];
}
}1 356
Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy
Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.
Пример:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.👨💻 Алгоритм: 1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице. 2⃣Использовать два вложенных цикла для итерации по каждому элементу матрицы grid, и если элемент отрицательный, увеличить count на 1. 3⃣Вернуть count. 😎 Решение:
class Solution {
public function countNegatives($grid) {
$count = 0;
foreach ($grid as $row) {
foreach ($row as $element) {
if ($element < 0) {
$count++;
}
}
}
return $count;
}
}1 356
Задача: 1055. Shortest Way to Form String
Сложность: medium
Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.
Пример:
Input: source = "abc", target = "abcbc"
Output: 2function minSubsequences($source, $target) {
$subsequencesCount = 0;
$targetIndex = 0;
while ($targetIndex < strlen($target)) {
$sourceIndex = 0;
$subsequencesCount++;
$startIndex = $targetIndex;
while ($sourceIndex < strlen($source) && $targetIndex < strlen($target)) {
if ($source[$sourceIndex] === $target[$targetIndex]) {
$targetIndex++;
}
$sourceIndex++;
}
if ($targetIndex === $startIndex) {
return -1;
}
}
return $subsequencesCount;
}1 356
Задача: 906. Super Palindromes
Сложность: hard
Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.
Пример:
Input: left = "4", right = "1000" Output: 4👨💻 Алгоритм: 1⃣Найти все палиндромы до корня из right. 2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right]. 3⃣Подсчитать количество таких суперпалиндромов. 😎 Решение:
function isPalindrome($x) {
$s = strval($x);
return $s == strrev($s);
}
function superpalindromesInRange($left, $right) {
$leftNum = intval($left);
$rightNum = intval($right);
$count = 0;
for ($i = 1; $i < 100000; $i++) {
$s = strval($i);
$palin1 = intval($s . strrev($s));
$palin2 = intval($s . strrev(substr($s, 0, -1)));
if ($palin1 * $palin1 > $rightNum) {
break;
}
if ($palin1 * $palin1 >= $leftNum && isPalindrome($palin1 * $palin1)) {
$count++;
}
if ($palin2 * $palin2 >= $leftNum && $palin2 * $palin2 <= $rightNum && isPalindrome($palin2 * $palin2)) {
$count++;
}
}
return $count;
}1 356
Задача: 640. Solve the Equation
Сложность: medium
Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.
Пример:
Input: s = "*" Output: 9👨💻 Алгоритм: 1⃣Разделение уравнения Разделите уравнение на левую и правую части относительно знака равенства '='. 2⃣Парсинг и упрощение Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений. 3⃣Решение уравнения Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'. 😎 Решение:
function solveEquation($equation) {
function parse($s) {
$coeff = 0;
$constPart = 0;
$sign = 1;
$num = 0;
$i = 0;
while ($i < strlen($s)) {
if ($s[$i] === '+') {
$sign = 1;
$i++;
} else if ($s[$i] === '-') {
$sign = -1;
$i++;
} else if (ctype_digit($s[$i])) {
$num = 0;
while ($i < strlen($s) && ctype_digit($s[$i])) {
$num = $num * 10 + (int)$s[$i];
$i++;
}
if ($i < strlen($s) && $s[$i] === 'x') {
$coeff += $sign * $num;
$i++;
} else {
$constPart += $sign * $num;
}
} else if ($s[$i] === 'x') {
$coeff += $sign;
$i++;
}
}
return [$coeff, $constPart];
}
list($left, $right) = explode('=', $equation);
list($leftCoeff, $leftConst) = parse($left);
list($rightCoeff, $rightConst) = parse($right);
$coeff = $leftCoeff - $rightCoeff;
$constPart = $rightConst - $leftConst;
if ($coeff == 0) {
return $constPart == 0 ? "Infinite solutions" : "No solution";
}
return "x=" . ($constPart / $coeff);
}1 356
Задача: 400. Nth Digit
Сложность: medium
Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].
Пример:
Input: n = 3 Output: 3👨💻 Алгоритм: 1⃣Определение диапазона: Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.). Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра. 2⃣Нахождение конкретного числа: Когда определите диапазон, найдите точное число, содержащее n-ю цифру. Определите индекс цифры в этом числе. 3⃣Возвращение n-й цифры: Извлеките и верните n-ю цифру из найденного числа. 😎 Решение:
class Solution {
function findNthDigit($n) {
$length = 1;
$count = 9;
$start = 1;
while ($n > $length * $count) {
$n -= $length * $count;
$length++;
$count *= 10;
$start *= 10;
}
$start += intval(($n - 1) / $length);
$s = strval($start);
return intval($s[($n - 1) % $length]);
}
}1 356
Задача: 1010. Pairs of Songs With Total Durations Divisible by 60
Сложность: medium
Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.
Пример:
Input: time = [30,20,150,100,40] Output: 3👨💻 Алгоритм: 1⃣Инициализация и вычисление остатков: Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями. 2⃣Подсчет пар: Пройдитесь по каждой песне в списке и для каждого элемента: Вычислите остаток от деления времени песни на 60. Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0). Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0). Обновите массив остатков, увеличивая количество песен с текущим остатком на 1. 3⃣Возврат результата: Верните общее количество пар. 😎 Решение:
class Solution {
function numPairsDivisibleBy60($time) {
$remainders = array_fill(0, 60, 0);
$count = 0;
foreach ($time as $t) {
if ($t % 60 == 0) {
$count += $remainders[0];
} else {
$count += $remainders[60 - $t % 60];
}
$remainders[$t % 60]++;
}
return $count;
}
}1 356
Задача: 61. Rotate List
Сложность: medium
Дан указатель на начало связного списка, поверните список вправо на k позиций.
Пример:
Input: head = [0,1,2], k = 4 Output: [2,0,1]👨💻 Алгоритм: 1⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n. 2⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n). 3⃣Разорвите кольцо (new_tail.next = None) и верните new_head. 😎 Решение:
function rotateRight($head, $k) {
if ($head === null) return null;
if ($head->next === null) return $head;
$oldTail = $head;
$n = 1;
while ($oldTail->next !== null) {
$oldTail = $oldTail->next;
$n++;
}
$oldTail->next = $head;
$newTail = $head;
for ($i = 0; $i < $n - $k % $n - 1; $i++) {
$newTail = $newTail->next;
}
$newHead = $newTail->next;
$newTail->next = null;
return $newHead;
}1 356
Задача: 734. Sentence Similarity
Сложность: easy
Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].
Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи.
Пример:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]] Output: true👨💻 Алгоритм: 1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false. 2⃣Создайте словарь для хранения всех пар похожих слов. 3⃣Проверьте каждую пару слов из предложений sentence1 и sentence2 на схожесть, используя словарь и правило, что слово всегда похоже на само себя. 😎 Решение:
function areSentencesSimilar($sentence1, $sentence2, $similarPairs) {
if (count($sentence1) != count($sentence2)) {
return false;
}
$similar = [];
foreach ($similarPairs as $pair) {
list($x, $y) = $pair;
if (!isset($similar[$x])) {
$similar[$x] = [];
}
if (!isset($similar[$y])) {
$similar[$y] = [];
}
$similar[$x][] = $y;
$similar[$y][] = $x;
}
for ($i = 0; $i < count($sentence1); $i++) {
$w1 = $sentence1[$i];
$w2 = $sentence2[$i];
if ($w1 != $w2 && (!isset($similar[$w1]) || !in_array($w2, $similar[$w1]))) {
return false;
}
}
return true;
}1 356
Задача: 1329. Sort the Matrix Diagonally
Сложность: medium
Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].
Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.
Пример:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]class Solution {
function diagonalSort($mat) {
$m = count($mat);
$n = count($mat[0]);
$diagonals = [];
for ($row = 0; $row < $m; $row++) {
for ($col = 0; $col < $n; $col++) {
$key = $row - $col;
if (!isset($diagonals[$key])) {
$diagonals[$key] = [];
}
$diagonals[$key][] = $mat[$row][$col];
}
}
foreach ($diagonals as &$diagonal) {
sort($diagonal);
}
for ($row = 0; $row < $m; $row++) {
for ($col = 0; $col < $n; $col++) {
$key = $row - $col;
$mat[$row][$col] = array_shift($diagonals[$key]);
}
}
return $mat;
}
}