Решения LeetCode - Страница 3
1672. Richest Customer Wealth
JuniorОписание: Решение задачи LeetCode "richest-customer-wealth" на PHP.
Код:
class Solution {
/**
* @param Integer[][] $accounts
* @return Integer
*/
function maximumWealth($accounts) {
$rs = 0;
for ($i = 0; $i < count($accounts); $i++) {
$sum = 0;
for ($j = 0; $j < count($accounts[$i]); $j++) {
$sum += $accounts[$i][$j];
}
if ($sum > $rs) {
$rs = $sum;
}
}
return $rs;
}
}
1704. Determine if String Halves Are Alike
JuniorОписание: Решение задачи LeetCode "determine-if-string-halves-are-alike" на PHP.
Код:
class Solution {
/**
* @param String $s
* @return Boolean
*/
function halvesAreAlike($s) {
$n = strlen($s) / 2;
$vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
$cnt = 0;
for ($i = 0; $i < $n; $i++) {
if (in_array($s[$i], $vowels)) {
$cnt++;
}
if (in_array($s[$i + $n], $vowels)) {
$cnt--;
}
}
return $cnt == 0;
}
}
1732. Find the Highest Altitude
JuniorОписание: Решение задачи LeetCode "find-the-highest-altitude" на PHP.
Код:
class Solution {
/**
* @param Integer[] $gain
* @return Integer
*/
function largestAltitude($gain) {
$max = 0;
for ($i = 0; $i < count($gain); $i++) {
$tmp += $gain[$i];
if ($tmp > $max) {
$max = $tmp;
}
}
return $max;
}
}
1748. Sum of Unique Elements
JuniorОписание: Решение задачи LeetCode "sum-of-unique-elements" на PHP.
Код:
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function sumOfUnique($nums) {
$sum = 0;
for ($i = 0; $i < count($nums); $i++) {
$hashtable[$nums[$i]] += 1;
if ($hashtable[$nums[$i]] == 1) {
$sum += $nums[$i];
}
if ($hashtable[$nums[$i]] == 2) {
$sum -= $nums[$i];
}
}
return $sum;
}
}
1876. Substrings of Size Three with Distinct Characters
JuniorОписание: Решение задачи LeetCode "substrings-of-size-three-with-distinct-characters" на PHP.
Код:
class Solution {
/**
* @param String $s
* @return Integer
*/
function countGoodSubstrings($s) {
$ans = 0;
$n = strlen($s);
$l = 0;
$r = 0;
$mask = 0;
while ($r < $n) {
$x = ord($s[$r]) - ord('a');
while (($mask >> $x) & 1) {
$y = ord($s[$l++]) - ord('a');
$mask ^= 1 << $y;
}
$mask |= 1 << $x;
if ($r - $l + 1 >= 3) {
$ans++;
}
$r++;
}
return $ans;
}
}
1941. Check if All Characters Have Equal Number of Occurrences
JuniorОписание: Решение задачи LeetCode "check-if-all-characters-have-equal-number-of-occurrences" на PHP.
Код:
class Solution {
/**
* @param String $s
* @return Boolean
*/
function areOccurrencesEqual($s) {
$cnt = array_fill(0, 26, 0);
for ($i = 0; $i < strlen($s); $i++) {
$cnt[ord($s[$i]) - ord('a')]++;
}
$v = 0;
foreach ($cnt as $x) {
if ($x == 0) {
continue;
}
if ($v && $v != $x) {
return false;
}
$v = $x;
}
return true;
}
}
1945. Sum of Digits of String After Convert
JuniorОписание: Решение задачи LeetCode "sum-of-digits-of-string-after-convert" на PHP.
Код:
class Solution {
/**
* @param String $s
* @param Integer $k
* @return Integer
*/
function getLucky($s, $k) {
$rs = '';
for ($i = 0; $i < strlen($s); $i++) {
$num = ord($s[$i]) - 96;
$rs = $rs . strval($num);
}
while ($k != 0) {
$sum = 0;
for ($j = 0; $j < strlen($rs); $j++) {
$sum += intval($rs[$j]);
}
$rs = strval($sum);
$k--;
}
return intval($rs);
}
}
1957. Delete Characters to Make Fancy String
JuniorОписание: Решение задачи LeetCode "delete-characters-to-make-fancy-string" на PHP.
Код:
class Solution {
/**
* @param String $s
* @return String
*/
function makeFancyString($s) {
$ans = '';
for ($i = 0; $i < strlen($s); $i++) {
$c = $s[$i];
if ($i < 2 || $c !== $s[$i - 1] || $c !== $s[$i - 2]) {
$ans .= $c;
}
}
return $ans;
}
}
1984. Minimum Difference Between Highest and Lowest of K Scores
JuniorОписание: Решение задачи LeetCode "minimum-difference-between-highest-and-lowest-of-k-scores" на PHP.
Код:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function minimumDifference($nums, $k) {
sort($nums);
$ans = 10 ** 5;
for ($i = 0; $i < count($nums) - $k + 1; $i++) {
$ans = min($ans, $nums[$i + $k - 1] - $nums[$i]);
}
return $ans;
}
}
2000. Reverse Prefix of Word
JuniorОписание: Решение задачи LeetCode "reverse-prefix-of-word" на PHP.
Код:
class Solution {
/**
* @param String $word
* @param String $ch
* @return String
*/
function reversePrefix($word, $ch) {
$len = strlen($word);
$rs = '';
for ($i = 0; $i < $len; $i++) {
$rs = $rs . $word[$i];
if ($word[$i] == $ch) {
break;
}
}
if (strlen($rs) == $len && $rs[$len - 1] != $ch) {
return $word;
}
$rs = strrev($rs);
$rs = $rs . substr($word, strlen($rs));
return $rs;
}
}
2068. Check Whether Two Strings are Almost Equivalent
JuniorОписание: Решение задачи LeetCode "check-whether-two-strings-are-almost-equivalent" на PHP.
Код:
class Solution {
/**
* @param String $word1
* @param String $word2
* @return Boolean
*/
function checkAlmostEquivalent($word1, $word2) {
for ($i = 0; $i < strlen($word1); $i++) {
$hashtable[$word1[$i]] += 1;
$hashtable[$word2[$i]] -= 1;
}
$keys = array_keys($hashtable);
for ($j = 0; $j < count($keys); $j++) {
if (abs($hashtable[$keys[$j]]) > 3) {
return false;
}
}
return true;
}
}
2190. Most Frequent Number Following Key In an Array
JuniorОписание: Решение задачи LeetCode "most-frequent-number-following-key-in-an-array" на PHP.
Код:
class Solution {
function mostFrequent($nums, $key) {
$cnt = array_fill(0, max($nums) + 1, 0);
$ans = 0;
$mx = 0;
for ($i = 0; $i < count($nums) - 1; ++$i) {
if ($nums[$i] === $key) {
$cnt[$nums[$i + 1]]++;
if ($mx < $cnt[$nums[$i + 1]]) {
$mx = $cnt[$nums[$i + 1]];
$ans = $nums[$i + 1];
}
}
}
return $ans;
}
}
2215. Find the Difference of Two Arrays
JuniorОписание: Решение задачи LeetCode "find-the-difference-of-two-arrays" на PHP.
Код:
class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Integer[][]
*/
function findDifference($nums1, $nums2) {
$s1 = array_flip($nums1);
$s2 = array_flip($nums2);
$diff1 = array_diff_key($s1, $s2);
$diff2 = array_diff_key($s2, $s1);
return [array_keys($diff1), array_keys($diff2)];
}
}
2248. Intersection of Multiple Arrays
JuniorОписание: Решение задачи LeetCode "intersection-of-multiple-arrays" на PHP.
Код:
class Solution {
/**
* @param Integer[][] $nums
* @return Integer[]
*/
function intersection($nums) {
$rs = [];
for ($i = 0; $i < count($nums); $i++) {
for ($j = 0; $j < count($nums[$i]); $j++) {
$hashtable[$nums[$i][$j]] += 1;
if ($hashtable[$nums[$i][$j]] === count($nums)) {
array_push($rs, $nums[$i][$j]);
}
}
}
sort($rs);
return $rs;
}
}
2259. Remove Digit From Number to Maximize Result
JuniorОписание: Решение задачи LeetCode "remove-digit-from-number-to-maximize-result" на PHP.
Код:
class Solution {
/**
* @param String $number
* @param String $digit
* @return String
*/
function removeDigit($number, $digit) {
$max = 0;
for ($i = 0; $i < strlen($number); $i++) {
if ($number[$i] == $digit) {
$tmp = substr($number, 0, $i) . substr($number, $i + 1);
if ($tmp > $max) {
$max = $tmp;
}
}
}
return $max;
}
}
2351. First Letter to Appear Twice
JuniorОписание: Решение задачи LeetCode "first-letter-to-appear-twice" на PHP.
Код:
class Solution {
/**
* @param String $s
* @return String
*/
function repeatedCharacter($s) {
for ($i = 0; ; $i++) {
$hashtable[$s[$i]] += 1;
if ($hashtable[$s[$i]] == 2) {
return $s[$i];
}
}
}
}
2379. Minimum Recolors to Get K Consecutive Black Blocks
JuniorОписание: Решение задачи LeetCode "minimum-recolors-to-get-k-consecutive-black-blocks" на PHP.
Код:
class Solution {
/**
* @param String $blocks
* @param Integer $k
* @return Integer
*/
function minimumRecolors($blocks, $k) {
$cnt = 0;
for ($i = 0; $i < $k; $i++) {
if ($blocks[$i] === 'W') {
$cnt++;
}
}
$min = $cnt;
for ($i = $k; $i < strlen($blocks); $i++) {
if ($blocks[$i] === 'W') {
$cnt++;
}
if ($blocks[$i - $k] === 'W') {
$cnt--;
}
$min = min($min, $cnt);
}
return $min;
}
}
2404. Most Frequent Even Element
JuniorОписание: Решение задачи LeetCode "most-frequent-even-element" на PHP.
Код:
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function mostFrequentEven($nums) {
$max = $rs = -1;
for ($i = 0; $i < count($nums); $i++) {
if ($nums[$i] % 2 == 0) {
$hashtable[$nums[$i]] += 1;
if (
$hashtable[$nums[$i]] > $max ||
($hashtable[$nums[$i]] == $max && $rs > $nums[$i])
) {
$max = $hashtable[$nums[$i]];
$rs = $nums[$i];
}
}
}
return $rs;
}
}
2485. Find the Pivot Integer
JuniorОписание: Решение задачи LeetCode "find-the-pivot-integer" на PHP.
Код:
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function pivotInteger($n) {
$sum = ($n * ($n + 1)) / 2;
$pre = 0;
for ($i = 1; $i <= $n; $i++) {
if ($pre + $i === $sum - $pre) {
return $i;
}
$pre += $i;
}
return -1;
}
}
94. Binary Tree Inorder Traversal
JuniorОписание:
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Код:
The non-recursive approach is as follows:
1. Define a stack `stk`.
2. Push the left nodes of the tree into the stack in sequence.
3. When the left node is null, pop and process the top element of the stack.
4. Repeat steps 2-3.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree, and the space complexity mainly depends on the stack space.
111. Minimum Depth of Binary Tree
JuniorОписание:
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Constraints:
- The number of nodes in the tree is in the range
[0, 10^5]. -1000 <= Node.val <= 1000
Код:
Use a queue to implement breadth-first search, initially adding the root node to the queue. Each time, take a node from the queue. If this node is a leaf node, directly return the current depth. If this node is not a leaf node, add all non-null child nodes of this node to the queue. Continue to search the next layer of nodes until a leaf node is found.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
141. Linked List Cycle
JuniorОписание:
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true* if there is a cycle in the linked list*. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Constraints:
- The number of the nodes in the list is in the range
[0, 10^4]. -10^5 <= Node.val <= 10^5posis-1or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
Код:
We define two pointers, $fast$ and $slow$, both initially pointing to $head$.
The fast pointer moves two steps at a time, and the slow pointer moves one step at a time, in a continuous loop. When the fast and slow pointers meet, it indicates that there is a cycle in the linked list. If the loop ends without the pointers meeting, it indicates that there is no cycle in the linked list.
The time complexity is $O(n)$, and the space complexity is $O(1)$, where $n$ is the number of nodes in the linked list.
144. Binary Tree Preorder Traversal
JuniorОписание:
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Код:
The idea of using a stack to implement non-recursive traversal is as follows:
1. Define a stack $stk$, and first push the root node into the stack.
2. If the stack is not empty, pop a node from the stack each time.
3. Process the node.
4. First push the right child of the node into the stack, then push the left child of the node into the stack (if there are child nodes).
5. Repeat steps 2-4.
6. Return the result.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.
145. Binary Tree Postorder Traversal
JuniorОписание:
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Код:
The order of preorder traversal is: root, left, right. If we change the order of the left and right children, the order becomes: root, right, left. Finally, reversing the result gives us the postorder traversal result.
Therefore, the idea of using a stack to implement non-recursive traversal is as follows:
1. Define a stack $stk$, and first push the root node into the stack.
2. If the stack is not empty, pop a node from the stack each time.
3. Process the node.
4. First push the left child of the node into the stack, then push the right child of the node into the stack (if there are child nodes).
5. Repeat steps 2-4.
6. Reverse the result to get the postorder traversal result.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.
206. Reverse Linked List
JuniorОписание:
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Код:
We recursively reverse all nodes from the second node to the end of the list, then attach the $head$ to the end of the reversed list.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the linked list.
222. Count Complete Tree Nodes
JuniorОписание:
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 6
Example 2:
Input: root = []
Output: 0
Example 3:
Input: root = [1]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[0, 5 * 10^4]. 0 <= Node.val <= 5 * 10^4- The tree is guaranteed to be complete.
Код:
For this problem, we can also take advantage of the characteristics of a complete binary tree to design a faster algorithm.
Characteristics of a complete binary tree: leaf nodes can only appear on the bottom and second-to-bottom layers, and the leaf nodes on the bottom layer are concentrated on the left side of the tree. It should be noted that a full binary tree is definitely a complete binary tree, but a complete binary tree is not necessarily a full binary tree.
If the number of layers in a full binary tree is $h$, then the total number of nodes is $2^h - 1$.
We first count the heights of the left and right subtrees of $root$, denoted as $left$ and $right$.
1. If $left = right$, it means that the left subtree is a full binary tree, so the total number of nodes in the left subtree is $2^{left} - 1$. Plus the $root$ node, it is $2^{left}$. Then we recursively count the right subtree.
1. If $left > right$, it means that the right subtree is a full binary tree, so the total number of nodes in the right subtree is $2^{right} - 1$. Plus the $root$ node, it is $2^{right}$. Then we recursively count the left subtree.
The time complexity is $O(\log^2 n)$.
231. Power of Two
JuniorОписание:
Given an integer n, return true if it is a power of two. Otherwise, return false.
An integer n is a power of two, if there exists an integer x such that n == 2^x.
Example 1:
Input: n = 1
Output: true
Explanation: 2^0 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 2^4 = 16
Example 3:
Input: n = 3
Output: false
Constraints:
-2^31 <= n <= 2^31 - 1
Follow up: Could you solve it without loops/recursion?
Код:
According to the definition of $\text{lowbit}$, we know that $\text{lowbit}(x) = x \& (-x)$, which can get the decimal number represented by the last bit $1$ of $n$. Therefore, if $n > 0$ and $\text{lowbit}(n)$ equals $n$, then $n$ is a power of $2$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
270. Closest Binary Search Tree Value 🔒
JuniorОписание:
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286
Output: 4
Example 2:
Input: root = [1], target = 4.428571
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[1, 10^4]. 0 <= Node.val <= 10^9-10^9 <= target <= 10^9
Код:
We can rewrite the recursive function in an iterative form, using a loop to simulate the recursive process. We start from the root node and check whether the absolute difference between the current node's value and the target value is less than the current minimum difference. If it is, we update the answer. Then, based on the size relationship between the target value and the current node's value, we decide to move to the left subtree or the right subtree. The loop ends when we traverse to a null node.
The time complexity is $O(n)$, where $n$ is the number of nodes in the binary search tree. The space complexity is $O(1)$.
326. Power of Three
JuniorОписание:
Given an integer n, return true if it is a power of three. Otherwise, return false.
An integer n is a power of three, if there exists an integer x such that n == 3^x.
Example 1:
Input: n = 27
Output: true
Explanation: 27 = 3^3
Example 2:
Input: n = 0
Output: false
Explanation: There is no x where 3^x = 0.
Example 3:
Input: n = -1
Output: false
Explanation: There is no x where 3^x = (-1).
Constraints:
-2^31 <= n <= 2^31 - 1
Follow up: Could you solve it without loops/recursion?
Код:
If $n$ is a power of $3$, then the maximum value of $n$ is $3^{19} = 1162261467$. Therefore, we only need to check if $n$ is a divisor of $3^{19}$.
Time complexity $O(1)$, space complexity $O(1)$.
346. Moving Average from Data Stream 🔒
JuniorОписание:
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Implement the MovingAverage class:
MovingAverage(int size)Initializes the object with the size of the windowsize.double next(int val)Returns the moving average of the lastsizevalues of the stream.
Example 1:
Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]
Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3
Constraints:
1 <= size <= 1000-10^5 <= val <= 10^5- At most
10^4calls will be made tonext.
Код:
We can use a queue $\textit{q}$ to store the last $\textit{size}$ elements, and a variable $\textit{s}$ to record the sum of these $\textit{size}$ elements.
When calling the $\textit{next}$ function, we first check if the length of the queue $\textit{q}$ is equal to $\textit{size}$. If it is, we dequeue the front element of the queue $\textit{q}$ and update the value of $\textit{s}$. Then we enqueue $\textit{val}$ and update the value of $\textit{s}$. Finally, we return the value of $\frac{s}{\text{len}(q)}$.
The time complexity is $O(1)$, and the space complexity is $O(n)$, where $n$ is the integer $\textit{size}$ given in the problem.