Leetcode 2021-05-09
🟡 1482.minimum-number-of-days-to-make-m-bouquets
1️⃣ Tags
#array #binary_search
2️⃣ Description
Given an integer array
We need to make
The garden consists of
Return the minimum number of days you need to wait to be able to make
3️⃣ Example
🟡 1482.minimum-number-of-days-to-make-m-bouquets
1️⃣ Tags
#array #binary_search
2️⃣ Description
Given an integer array
bloomDay, an integer m and an integer k.We need to make
m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.The garden consists of
n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.Return the minimum number of days you need to wait to be able to make
m bouquets from the garden. If it is impossible to make m bouquets return -1.3️⃣ Example
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
Leetcode 2021-05-10
🟢 872.leaf-similar-trees
1️⃣ Tags
#tree #depth_first_search
2️⃣ Description
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return
3️⃣ Example
🟢 872.leaf-similar-trees
1️⃣ Tags
#tree #depth_first_search
2️⃣ Description
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is
(6, 7, 4, 9, 8).Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return
true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.3️⃣ Example
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true
Leetcode 2021-05-11
🟡 1734.decode-xored-permutation
1️⃣ Tags
#bit_manipulation
2️⃣ Description
There is an integer array
It was encoded into another integer array
Given the
3️⃣ Example
🟡 1734.decode-xored-permutation
1️⃣ Tags
#bit_manipulation
2️⃣ Description
There is an integer array
perm that is a permutation of the first n positive integers, where n is always odd.It was encoded into another integer array
encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].Given the
encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.3️⃣ Example
Input: encoded = [3,1]
Output: [1,2,3]
Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]
Leetcode 2021-05-12
🟡 1310.xor-queries-of-a-subarray
1️⃣ Tags
#bit_manipulation
2️⃣ Description
3️⃣ Example
🟡 1310.xor-queries-of-a-subarray
1️⃣ Tags
#bit_manipulation
2️⃣ Description
3️⃣ Example
Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8
Leetcode 2021-05-13
🔴 1269.number-of-ways-to-stay-in-the-same-place-after-some-steps
1️⃣ Tags
#dynamic_programming
2️⃣ Description
You have a pointer at index
Given two integers
Since the answer may be too large, return it modulo
3️⃣ Example
🔴 1269.number-of-ways-to-stay-in-the-same-place-after-some-steps
1️⃣ Tags
#dynamic_programming
2️⃣ Description
You have a pointer at index
0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).Given two integers
steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.Since the answer may be too large, return it modulo
10^9 + 7.3️⃣ Example
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
Leetcode 2021-05-14
🟡 12.integer-to-roman
1️⃣ Tags
#math #string
2️⃣ Description
Roman numerals are represented by seven different symbols:
For example,
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not
Given an integer, convert it to a roman numeral.
3️⃣ Example
🟡 12.integer-to-roman
1️⃣ Tags
#math #string
2️⃣ Description
Roman numerals are represented by seven different symbols:
I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example,
2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not
IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900.Given an integer, convert it to a roman numeral.
3️⃣ Example
Input: num = 3
Output: "III"
Leetcode 2021-05-15
🟢 13.roman-to-integer
1️⃣ Tags
#math #string
2️⃣ Description
Roman numerals are represented by seven different symbols:
For example,
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not
Given a roman numeral, convert it to an integer.
3️⃣ Example
🟢 13.roman-to-integer
1️⃣ Tags
#math #string
2️⃣ Description
Roman numerals are represented by seven different symbols:
I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example,
2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not
IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900.Given a roman numeral, convert it to an integer.
3️⃣ Example
Input: s = "III"
Output: 3
Leetcode 2021-05-16
🟡 421.maximum-xor-of-two-numbers-in-an-array
1️⃣ Tags
#bit_manipulation #trie
2️⃣ Description
Given an integer array
Follow up: Could you do this in
3️⃣ Example
🟡 421.maximum-xor-of-two-numbers-in-an-array
1️⃣ Tags
#bit_manipulation #trie
2️⃣ Description
Given an integer array
nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.Follow up: Could you do this in
O(n) runtime?3️⃣ Example
Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.
Leetcode 2021-05-17
🟢 993.cousins-in-binary-tree
🏷️ Tags
#tree #breadth_first_search
Description
In a binary tree, the root node is at depth
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the
Return
Example
🟢 993.cousins-in-binary-tree
🏷️ Tags
#tree #breadth_first_search
Description
In a binary tree, the root node is at depth
0, and children of each depth k node are at depth k+1.Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the
root of a binary tree with unique values, and the values x and y of two different nodes in the tree.Return
true if and only if the nodes corresponding to the values x and y are cousins.Example
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Leetcode 2021-05-18
🟡 1442.count-triplets-that-can-form-two-arrays-of-equal-xor
🏷️ Tags
#bit_manipulation #array #math
Description
Given an array of integers
We want to select three indices
Let's define
Note that ^ denotes the bitwise-xor operation.
Return the number of triplets (
Example
🟡 1442.count-triplets-that-can-form-two-arrays-of-equal-xor
🏷️ Tags
#bit_manipulation #array #math
Description
Given an array of integers
arr.We want to select three indices
i, j and k where (0 <= i < j <= k < arr.length).Let's define
a and b as follows:a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]Note that ^ denotes the bitwise-xor operation.
Return the number of triplets (
i, j and k) Where a == b.Example
Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)
Leetcode 2021-05-19
🟡 1738.find-kth-largest-xor-coordinate-value
🏷️ Tags
#array
Description
You are given a 2D
The value of coordinate
Find the
Example
🟡 1738.find-kth-largest-xor-coordinate-value
🏷️ Tags
#array
Description
You are given a 2D
matrix of size m x n, consisting of non-negative integers. You are also given an integer k.The value of coordinate
(a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).Find the
kth largest value (1-indexed) of all the coordinates of matrix.Example
Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.
Leetcode 2021-05-20
🟡 692.top-k-frequent-words
🏷️ Tags
#heap #trie #hash_table
Description
Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Example
🟡 692.top-k-frequent-words
🏷️ Tags
#heap #trie #hash_table
Description
Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Example
Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.
Leetcode 2021-05-21
🟡 1035.uncrossed-lines
🏷️ Tags
#array
Description
We write the integers of
Now, we may draw connecting lines: a straight line connecting two numbers
The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
Example
🟡 1035.uncrossed-lines
🏷️ Tags
#array
Description
We write the integers of
nums1 and nums2 (in the order they are given) on two separate horizontal lines.Now, we may draw connecting lines: a straight line connecting two numbers
nums1[i] and nums2[j] such that:nums1[i] == nums2[j];The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
Example
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1]=4 to nums2[2]=4 will intersect the line from nums1[2]=2 to nums2[1]=2.
Leetcode 2021-05-22
🔴 810.chalkboard-xor-game
🏷️ Tags
#math
Description
We are given non-negative integers nums[i] which are written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. (Also, we'll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)
Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.
Return True if and only if Alice wins the game, assuming both players play optimally.
Example
🔴 810.chalkboard-xor-game
🏷️ Tags
#math
Description
We are given non-negative integers nums[i] which are written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. (Also, we'll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)
Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.
Return True if and only if Alice wins the game, assuming both players play optimally.
Example
Input: nums = [1, 1, 2]
Output: false
Explanation:
Alice has two choices: erase 1 or erase 2.
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose.
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.
Leetcode 2021-05-23
🔴 1707.maximum-xor-with-an-element-from-array
🏷️ Tags
#bit_manipulation #trie
Description
You are given an array
The answer to the
Return an integer array
Example
🔴 1707.maximum-xor-with-an-element-from-array
🏷️ Tags
#bit_manipulation #trie
Description
You are given an array
nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [xi, mi].The answer to the
ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi. In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi. If all elements in nums are larger than mi, then the answer is -1.Return an integer array
answer where answer.length == queries.length and answer[i] is the answer to the ith query.Example
Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
Leetcode 2021-05-24
🔴 664.strange-printer
🏷️ Tags
#depth_first_search #dynamic_programming
Description
There is a strange printer with the following two special properties:
The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.
Given a string
Example
🔴 664.strange-printer
🏷️ Tags
#depth_first_search #dynamic_programming
Description
There is a strange printer with the following two special properties:
The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.
Given a string
s, return the minimum number of turns the printer needed to print it.Example
Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".
Leetcode 2021-05-25
🔴 1787.make-the-xor-of-all-segments-equal-to-zero
🏷️ Tags
#dynamic_programming
Description
You are given an array
Return the minimum number of elements to change in the array such that the
Example
🔴 1787.make-the-xor-of-all-segments-equal-to-zero
🏷️ Tags
#dynamic_programming
Description
You are given an array
nums and an integer k. The XOR of a segment [left, right] where left <= right is the XOR of all the elements with indices between left and right, inclusive: nums[left] XOR nums[left+1] XOR ... XOR nums[right].Return the minimum number of elements to change in the array such that the
XOR of all segments of size k is equal to zero.Example
Input: nums = [1,2,0,3,0], k = 1
Output: 3
Explanation: Modify the array from [1,2,0,3,0] to from [0,0,0,0,0].
Leetcode 2021-05-26
🟡 1190.reverse-substrings-between-each-pair-of-parentheses
🏷️ Tags
#stack
Description
You are given a string
Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Your result should not contain any brackets.
Example
🟡 1190.reverse-substrings-between-each-pair-of-parentheses
🏷️ Tags
#stack
Description
You are given a string
s that consists of lower case English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Your result should not contain any brackets.
Example
Input: s = "(abcd)"
Output: "dcba"
Leetcode 2021-05-27
🟢 461.hamming-distance
🏷️ Tags
#bit_manipulation
Description
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers
Example
🟢 461.hamming-distance
🏷️ Tags
#bit_manipulation
Description
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers
x and y, return the Hamming distance between them.Example
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
Leetcode 2021-05-28
🟡 477.total-hamming-distance
🏷️ Tags
#bit_manipulation
Description
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given an integer array
Example
🟡 477.total-hamming-distance
🏷️ Tags
#bit_manipulation
Description
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given an integer array
nums, return the sum of Hamming distances between all the pairs of the integers in nums.Example
Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.