Решения LeetCode - Страница 1
1. Two Sum
JuniorОписание: Дан массив целых чисел nums и целое число target, верните индексы двух чисел таких, чтобы их сумма была равна target.
Код:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
$d = [];
foreach ($nums as $i => $x) {
$y = $target - $x;
if (isset($d[$y])) {
return [$d[$y], $i];
}
$d[$x] = $i;
}
}
}
9. Palindrome Number
JuniorОписание: Дано целое число x, верните true, если x является палиндромом, и false в противном случае.
Код:
class Solution {
/**
* @param Integer $x
* @return Boolean
*/
function isPalindrome($x) {
if ($x < 0 || ($x && $x % 10 == 0)) {
return false;
}
$y = 0;
while ($x > $y) {
$y = $y * 10 + ($x % 10);
$x = (int) ($x / 10);
}
return $x == $y || $x == (int) ($y / 10);
}
}
13. Roman to Integer
JuniorОписание: Римские цифры представлены семью различными символами: I, V, X, L, C, D и M. Дано римское число, преобразуйте его в целое число.
Код:
class Solution {
/**
* @param String $s
* @return Integer
*/
function romanToInt($s) {
$d = [
'I' => 1,
'V' => 5,
'X' => 10,
'L' => 50,
'C' => 100,
'D' => 500,
'M' => 1000,
];
$ans = 0;
$len = strlen($s);
for ($i = 0; $i < $len - 1; $i++) {
if ($d[$s[$i]] < $d[$s[$i + 1]]) {
$ans -= $d[$s[$i]];
} else {
$ans += $d[$s[$i]];
}
}
$ans += $d[$s[$len - 1]];
return $ans;
}
}
14. Longest Common Prefix
JuniorОписание: Напишите функцию для поиска самой длинной строки общего префикса среди массива строк.
Код:
class Solution {
/**
* @param String[] $strs
* @return String
*/
function longestCommonPrefix($strs) {
$rs = '';
for ($i = 0; $i < strlen($strs[0]); $i++) {
for ($j = 1; $j < count($strs); $j++) {
if ($strs[0][$i] != $strs[$j][$i]) {
return $rs;
}
}
$rs = $rs . $strs[0][$i];
}
return $rs;
}
}
20. Valid Parentheses
JuniorОписание: Дана строка s, содержащая только символы '(', ')', ', ', '[' и ']', определите, является ли входная строка допустимой.
Код:
class Solution {
/**
* @param string $s
* @return boolean
*/
function isValid($s) {
$stack = [];
$brackets = [
')' => '(',
'}' => '{',
']' => '[',
];
for ($i = 0; $i < strlen($s); $i++) {
$char = $s[$i];
if (array_key_exists($char, $brackets)) {
if (empty($stack) || $stack[count($stack) - 1] !== $brackets[$char]) {
return false;
}
array_pop($stack);
} else {
array_push($stack, $char);
}
}
return empty($stack);
}
}
21. Merge Two Sorted Lists
JuniorОписание: Слейте два отсортированных связанных списка и верните результат в виде отсортированного списка.
Код:
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $list1
* @param ListNode $list2
* @return ListNode
*/
function mergeTwoLists($list1, $list2) {
if (is_null($list1)) {
return $list2;
}
if (is_null($list2)) {
return $list1;
}
if ($list1->val <= $list2->val) {
$list1->next = $this->mergeTwoLists($list1->next, $list2);
return $list1;
} else {
$list2->next = $this->mergeTwoLists($list1, $list2->next);
return $list2;
}
}
}
26. Remove Duplicates from Sorted Array
JuniorОписание: Дан массив целых чисел nums, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз.
Код:
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function removeDuplicates(&$nums) {
$k = 0;
foreach ($nums as $x) {
if ($k == 0 || $x != $nums[$k - 1]) {
$nums[$k++] = $x;
}
}
return $k;
}
}
27. Remove Element
JuniorОписание: Дан массив целых чисел nums и целое число val, удалите все вхождения val в nums на месте.
Код:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $val
* @return Integer
*/
function removeElement(&$nums, $val) {
for ($i = count($nums) - 1; $i >= 0; $i--) {
if ($nums[$i] == $val) {
array_splice($nums, $i, 1);
}
}
}
}
28. Find the Index of the First Occurrence in a String
JuniorОписание: Даны две строки needle и haystack, верните индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.
Код:
class Solution {
/**
* @param String $haystack
* @param String $needle
* @return Integer
*/
function strStr($haystack, $needle) {
$strNew = str_replace($needle, '+', $haystack);
$cnt = substr_count($strNew, '+');
if ($cnt > 0) {
for ($i = 0; $i < strlen($strNew); $i++) {
if ($strNew[$i] == '+') {
return $i;
}
}
} else {
return -1;
}
}
}
35. Search Insert Position
JuniorОписание: Дан отсортированный массив различных целых чисел и целевое значение, верните индекс, если цель найдена. Если нет, верните индекс, в котором она была бы, если бы была вставлена по порядку.
Код:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function searchInsert($nums, $target) {
$l = 0;
$r = count($nums);
while ($l < $r) {
$mid = ($l + $r) >> 1;
if ($nums[$mid] >= $target) {
$r = $mid;
} else {
$l = $mid + 1;
}
}
return $l;
}
}
58. Length of Last Word
JuniorОписание: Дана строка s, состоящая из слов и пробелов, верните длину последнего слова в строке.
Код:
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLastWord($s) {
$count = 0;
while ($s[strlen($s) - 1] == ' ') {
$s = substr($s, 0, -1);
}
while (strlen($s) != 0 && $s[strlen($s) - 1] != ' ') {
$count++;
$s = substr($s, 0, -1);
}
return $count;
}
}
70. Climbing Stairs
JuniorОписание: Вы поднимаетесь по лестнице. Чтобы достичь вершины, нужно n шагов. Каждый раз вы можете подняться на 1 или 2 шага. Сколькими различными способами вы можете подняться на вершину?
Код:
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function climbStairs($n) {
if ($n <= 2) {
return $n;
}
$dp = [0, 1, 2];
for ($i = 3; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 2] + $dp[$i - 1];
}
return $dp[$n];
}
}
88. Merge Sorted Array
JuniorОписание: Вам даны два отсортированных целочисленных массива nums1 и nums2. Объедините nums2 в nums1 как один отсортированный массив.
Код:
class Solution {
/**
* @param Integer[] $nums1
* @param Integer $m
* @param Integer[] $nums2
* @param Integer $n
* @return NULL
*/
function merge(&$nums1, $m, $nums2, $n) {
while (count($nums1) > $m) {
array_pop($nums1);
}
for ($i = 0; $i < $n; $i++) {
array_push($nums1, $nums2[$i]);
}
asort($nums1);
}
}
100. Same Tree
JuniorОписание: Даны корни двух бинарных деревьев p и q, напишите функцию, чтобы проверить, являются ли они одинаковыми или нет.
Код:
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* 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 {
/**
* @param TreeNode $p
* @param TreeNode $q
* @return Boolean
*/
function isSameTree($p, $q) {
if ($p == null && $q == null) {
return true;
}
if ($p == null || $q == null) {
return false;
}
if ($p->val != $q->val) {
return false;
}
return $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right);
}
}
121. Best Time to Buy and Sell Stock
JuniorОписание: Вам дан массив цен, где prices[i] — цена акции в i-й день. Вы хотите максимизировать прибыль, выбрав один день для покупки и другой день в будущем для продажи.
Код:
class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$ans = 0;
$mi = $prices[0];
foreach ($prices as $v) {
$ans = max($ans, $v - $mi);
$mi = min($mi, $v);
}
return $ans;
}
}
125. Valid Palindrome
JuniorОписание: Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех небуквенно-цифровых символов она читается одинаково вперед и назад.
Код:
class Solution {
/**
* @param String $s
* @return Boolean
*/
function isPalindrome($s) {
$regex = '/[a-z0-9]/';
$s = strtolower($s);
preg_match_all($regex, $s, $matches);
if ($matches[0] == null) {
return true;
}
$len = floor(count($matches[0]) / 2);
for ($i = 0; $i < $len; $i++) {
if ($matches[0][$i] != $matches[0][count($matches[0]) - 1 - $i]) {
return false;
}
}
return true;
}
}
169. Majority Element
JuniorОписание: Дан массив nums размера n, верните мажоритарный элемент (элемент, который встречается более n/2 раз).
Код:
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function majorityElement($nums) {
$m = 0;
$cnt = 0;
foreach ($nums as $x) {
if ($cnt == 0) {
$m = $x;
}
if ($m == $x) {
$cnt++;
} else {
$cnt--;
}
}
return $m;
}
}
217. Contains Duplicate
JuniorОписание: Дан массив целых чисел nums, верните true, если любое значение встречается в массиве хотя бы дважды, и false, если каждый элемент уникален.
Код:
class Solution {
/**
* @param Integer[] $nums
* @return Boolean
*/
function containsDuplicate($nums) {
$numsUnique = array_unique($nums);
return count($nums) != count($numsUnique);
}
}
219. Contains Duplicate II
JuniorОписание: Дан массив целых чисел nums и целое число k, верните true, если в массиве есть два различных индекса i и j, таких что nums[i] == nums[j] и abs(i - j) <= k.
Код:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Boolean
*/
function containsNearbyDuplicate($nums, $k) {
$d = [];
for ($i = 0; $i < count($nums); ++$i) {
if (array_key_exists($nums[$i], $d) && $i - $d[$nums[$i]] <= $k) {
return true;
}
$d[$nums[$i]] = $i;
}
return false;
}
}
263. Ugly Number
JuniorОписание: Уродливое число — это положительное целое число, простые множители которого ограничены 2, 3 и 5. Дано целое число n, верните true, если n — уродливое число.
Код:
class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function isUgly($n) {
while ($n) {
if ($n % 2 == 0) {
$n = $n / 2;
} elseif ($n % 3 == 0) {
$n = $n / 3;
} elseif ($n % 5 == 0) {
$n = $n / 5;
} else {
break;
}
}
return $n == 1;
}
}
268. Missing Number
JuniorОписание: Дан массив nums, содержащий n различных чисел в диапазоне [0, n], верните единственное число из этого диапазона, которое отсутствует в массиве.
Код:
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function missingNumber($nums) {
$n = count($nums);
$sumN = (($n + 1) * $n) / 2;
for ($i = 0; $i < $n; $i++) {
$sumN -= $nums[$i];
}
return $sumN;
}
}
303. Range Sum Query - Immutable
JuniorОписание: Дан массив целых чисел nums, обработайте несколько запросов следующего типа: вычислить сумму элементов nums между индексами left и right включительно, где left <= right.
Код:
class NumArray {
/**
* @param Integer[] $nums
*/
function __construct($nums) {
$this->s = [0];
foreach ($nums as $x) {
$this->s[] = $this->s[count($this->s) - 1] + $x;
}
}
/**
* @param Integer $left
* @param Integer $right
* @return Integer
*/
function sumRange($left, $right) {
return $this->s[$right + 1] - $this->s[$left];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* $obj = NumArray($nums);
* $ret_1 = $obj->sumRange($left, $right);
*/
349. Intersection of Two Arrays
JuniorОписание: Даны два целочисленных массива nums1 и nums2, верните массив их пересечения. Каждый элемент в результате должен быть уникальным.
Код:
class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Integer[]
*/
function intersection($nums1, $nums2) {
$s1 = array_unique($nums1);
$s2 = array_unique($nums2);
$ans = array_intersect($s1, $s2);
return array_values($ans);
}
}
350. Intersection of Two Arrays II
JuniorОписание: Даны два целочисленных массива nums1 и nums2, верните массив их перес ечения. Каждый элемент в результате должен встречаться столько раз, сколько он встречается в обоих массивах.
Код:
class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Integer[]
*/
function intersect($nums1, $nums2) {
$cnt = [];
foreach ($nums1 as $x) {
if (isset($cnt[$x])) {
$cnt[$x]++;
} else {
$cnt[$x] = 1;
}
}
$ans = [];
foreach ($nums2 as $x) {
if (isset($cnt[$x]) && $cnt[$x] > 0) {
$ans[] = $x;
$cnt[$x]--;
}
}
return $ans;
}
}
383. Ransom Note
JuniorОписание: Даны две строки ransomNote и magazine, верните true, если ransomNote может быть построена с использованием букв из magazine, и false в противном случае.
Код:
class Solution {
/**
* @param String $ransomNote
* @param String $magazine
* @return Boolean
*/
function canConstruct($ransomNote, $magazine) {
$arrM = str_split($magazine);
for ($i = 0; $i < strlen($magazine); $i++) {
$hashtable[$arrM[$i]] += 1;
}
for ($j = 0; $j < strlen($ransomNote); $j++) {
if (!isset($hashtable[$ransomNote[$j]]) || $hashtable[$ransomNote[$j]] == 0) {
return false;
} else {
$hashtable[$ransomNote[$j]] -= 1;
}
}
return true;
}
}
387. First Unique Character in a String
JuniorОписание: Дана строка s, найдите в ней первый неповторяющийся символ и верните его индекс. Если его не существует, верните -1.
Код:
class Solution {
/**
* @param String $s
* @return Integer
*/
function firstUniqChar($s) {
for ($i = 0; $i < strlen($s); $i++) {
$hashtable[$s[$i]]++;
}
for ($i = 0; $i < strlen($s); $i++) {
if ($hashtable[$s[$i]] == 1) {
return $i;
}
}
return -1;
}
}
412. Fizz Buzz
JuniorОписание: Дано целое число n, верните строковый массив answer (1-indexed), где answer[i] равен 'FizzBuzz', 'Fizz', 'Buzz' или i.
Код:
class Solution {
/**
* @param Integer $n
* @return String[]
*/
function fizzBuzz($n) {
$ans = [];
for ($i = 1; $i <= $n; ++$i) {
$s = '';
if ($i % 3 == 0) {
$s .= 'Fizz';
}
if ($i % 5 == 0) {
$s .= 'Buzz';
}
if (strlen($s) == 0) {
$s .= $i;
}
$ans[] = $s;
}
return $ans;
}
}
434. Number of Segments in a String
JuniorОписание: Дана строка s, верните количество сегментов в строке. Сегмент определяется как непрерывная последовательность непробельных символов.
Код:
class Solution {
/**
* @param String $s
* @return Integer
*/
function countSegments($s) {
$arr = explode(' ', $s);
$cnt = 0;
for ($i = 0; $i < count($arr); $i++) {
if (strlen($arr[$i]) != 0) {
$cnt++;
}
}
return $cnt;
}
}
485. Max Consecutive Ones
JuniorОписание: Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве.
Код:
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function findMaxConsecutiveOnes($nums) {
$ans = $cnt = 0;
foreach ($nums as $x) {
if ($x == 1) {
$cnt += 1;
$ans = max($ans, $cnt);
} else {
$cnt = 0;
}
}
return $ans;
}
}
509. Fibonacci Number
JuniorОписание: Числа Фибоначчи, обычно обозначаемые F(n), образуют последовательность, в которой каждое число является суммой двух предыдущих, начиная с 0 и 1.
Код:
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function fib($n) {
$a = 0;
$b = 1;
for ($i = 0; $i < $n; $i++) {
$temp = $a;
$a = $b;
$b = $temp + $b;
}
return $a;
}
}