2022-09-05
429. N-ary Tree Level Order Traversal
Topic: Tree, Breadth-First Search
Difficulty: Medium
Problem:
Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png
Example 2:
Image: https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png
Constraints:
• The height of the n-ary tree is less than or equal to
• The total number of nodes is between
429. N-ary Tree Level Order Traversal
Topic: Tree, Breadth-First Search
Difficulty: Medium
Problem:
Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
Example 2:
Image: https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
Constraints:
• The height of the n-ary tree is less than or equal to
1000• The total number of nodes is between
[0, 10^4]2022-09-06
814. Binary Tree Pruning
Topic: Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
A subtree of a node
Example 1:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png
Example 2:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png
Example 3:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png
Constraints:
• The number of nodes in the tree is in the range
•
814. Binary Tree Pruning
Topic: Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.A subtree of a node
node is node plus every node that is a descendant of node.Example 1:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
Example 2:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png
Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]
Example 3:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png
Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]
Constraints:
• The number of nodes in the tree is in the range
[1, 200].•
Node.val is either 0 or 1.2022-09-07
606. Construct String from Binary Tree
Topic: String, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons1-tree.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons2-tree.jpg
Constraints:
• The number of nodes in the tree is in the range
•
606. Construct String from Binary Tree
Topic: String, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons1-tree.jpg
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons2-tree.jpg
Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Constraints:
• The number of nodes in the tree is in the range
[1, 10^4].•
-1000 <= Node.val <= 10002022-09-08
94. Binary Tree Inorder Traversal
Topic: Stack, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg
Example 2:
Example 3:
Constraints:
• The number of nodes in the tree is in the range
•
Follow up: Recursive solution is trivial, could you do it iteratively?
94. Binary Tree Inorder Traversal
Topic: Stack, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, return the inorder traversal of its nodes' values.Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Constraints:
• The number of nodes in the tree is in the range
[0, 100].•
-100 <= Node.val <= 100Follow up: Recursive solution is trivial, could you do it iteratively?
2022-09-09
1996. The Number of Weak Characters in the Game
Topic: Array, Stack, Greedy, Sorting, Monotonic Stack
Difficulty: Medium
Problem:
You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array
A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character
Return the number of weak characters.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
1996. The Number of Weak Characters in the Game
Topic: Array, Stack, Greedy, Sorting, Monotonic Stack
Difficulty: Medium
Problem:
You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array
properties where properties[i] = [attack_i, defense_i] represents the properties of the i^th character in the game.A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character
i is said to be weak if there exists another character j where attack_j > attack_i and defense_j > defense_i.Return the number of weak characters.
Example 1:
Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Explanation: No character has strictly greater attack and defense than the other.
Example 2:
Input: properties = [[2,2],[3,3]]
Output: 1
Explanation: The first character is weak because the second character has a strictly greater attack and defense.
Example 3:
Input: properties = [[1,5],[10,4],[4,3]]
Output: 1
Explanation: The third character is weak because the second character has a strictly greater attack and defense.
Constraints:
•
2 <= properties.length <= 10^5•
properties[i].length == 2•
1 <= attack_i, defense_i <= 10^52022-09-10
188. Best Time to Buy and Sell Stock IV
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are given an integer array
Find the maximum profit you can achieve. You may complete at most
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Example 2:
Constraints:
•
•
•
188. Best Time to Buy and Sell Stock IV
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are given an integer array
prices where prices[i] is the price of a given stock on the i^th day, and an integer k.Find the maximum profit you can achieve. You may complete at most
k transactions.Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Constraints:
•
0 <= k <= 100•
0 <= prices.length <= 1000•
0 <= prices[i] <= 10002022-09-11
1383. Maximum Performance of a Team
Topic: Array, Greedy, Sorting, Heap (Priority Queue)
Difficulty: Hard
Problem:
You are given two integers
Choose at most
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
•
1383. Maximum Performance of a Team
Topic: Array, Greedy, Sorting, Heap (Priority Queue)
Difficulty: Hard
Problem:
You are given two integers
n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the i^th engineer respectively.Choose at most
k different engineers out of the n engineers to form a team with the maximum performance.The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo
10^9 + 7.Example 1:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
Example 2:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.
Example 3:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72
Constraints:
•
1 <= k <= n <= 10^5•
speed.length == n•
efficiency.length == n•
1 <= speed[i] <= 10^5•
1 <= efficiency[i] <= 10^82022-09-12
948. Bag of Tokens
Topic: Array, Two Pointers, Greedy, Sorting
Difficulty: Medium
Problem:
You have an initial power of
Your goal is to maximize your total score by potentially playing each token in one of two ways:
• If your current power is at least
• If your current score is at least
Each token may be played at most once and in any order. You do not have to play all the tokens.
Return the largest possible score you can achieve after playing any number of tokens.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
948. Bag of Tokens
Topic: Array, Two Pointers, Greedy, Sorting
Difficulty: Medium
Problem:
You have an initial power of
power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the i^th token (0-indexed).Your goal is to maximize your total score by potentially playing each token in one of two ways:
• If your current power is at least
tokens[i], you may play the i^th token face up, losing tokens[i] power and gaining 1 score.• If your current score is at least
1, you may play the i^th token face down, gaining tokens[i] power and losing 1 score.Each token may be played at most once and in any order. You do not have to play all the tokens.
Return the largest possible score you can achieve after playing any number of tokens.
Example 1:
Input: tokens = [100], power = 50
Output: 0
Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.
Example 2:
Input: tokens = [100,200], power = 150
Output: 1
Explanation: Play the 0^th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1^st token since you cannot play it face up to add to your score.
Example 3:
Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
1. Play the 0^th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3^rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1^st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2^nd token (300) face up, your power becomes 0 and score becomes 2.
Constraints:
•
0 <= tokens.length <= 1000•
0 <= tokens[i], power < 10^42022-09-13
393. UTF-8 Validation
Topic: Array, Bit Manipulation
Difficulty: Medium
Problem:
Given an integer array
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
1. For a 1-byte character, the first bit is a
2. For an n-bytes character, the first
This is how the UTF-8 encoding would work:
Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
Example 2:
Constraints:
•
•
393. UTF-8 Validation
Topic: Array, Bit Manipulation
Difficulty: Medium
Problem:
Given an integer array
data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
1. For a 1-byte character, the first bit is a
0, followed by its Unicode code.2. For an n-bytes character, the first
n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.This is how the UTF-8 encoding would work:
Number of Bytes | UTF-8 Octet Sequence
| (binary)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x denotes a bit in the binary form of a byte that may be either 0 or 1.Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
Input: data = [235,140,4]
Output: false
Explanation: data represented the octet sequence: 11101011 10001100 00000100.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.
Constraints:
•
1 <= data.length <= 2 * 10^4•
0 <= data[i] <= 2552022-09-14
1457. Pseudo-Palindromic Paths in a Binary Tree
Topic: Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/05/06/palindromic_paths_1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/05/07/palindromic_paths_2.png
Example 3:
Constraints:
• The number of nodes in the tree is in the range
•
1457. Pseudo-Palindromic Paths in a Binary Tree
Topic: Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/05/06/palindromic_paths_1.png
Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 2:
Image: https://assets.leetcode.com/uploads/2020/05/07/palindromic_paths_2.png
Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 3:
Input: root = [9]
Output: 1
Constraints:
• The number of nodes in the tree is in the range
[1, 10^5].•
1 <= Node.val <= 92022-09-15
2007. Find Original Array From Doubled Array
Topic: Array, Hash Table, Greedy, Sorting
Difficulty: Medium
Problem:
An integer array
Given an array
Example 1:
Example 2:
Example 3:
Constraints:
•
•
2007. Find Original Array From Doubled Array
Topic: Array, Hash Table, Greedy, Sorting
Difficulty: Medium
Problem:
An integer array
original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.Given an array
changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.Example 1:
Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].
Example 2:
Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.
Example 3:
Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.
Constraints:
•
1 <= changed.length <= 10^5•
0 <= changed[i] <= 10^52022-09-16
1770. Maximum Score from Performing Multiplication Operations
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
You are given two integer arrays
You begin with a score of
• Choose one integer
• Add
• Remove
Return the maximum score after performing
Example 1:
Example 2:
Constraints:
•
•
•
•
•
1770. Maximum Score from Performing Multiplication Operations
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
You are given two integer arrays
nums and multipliers of size n and m respectively, where n >= m. The arrays are 1-indexed.You begin with a score of
0. You want to perform exactly m operations. On the i^th operation (1-indexed), you will:• Choose one integer
x from either the start or the end of the array nums.• Add
multipliers[i] * x to your score.• Remove
x from the array nums.Return the maximum score after performing
m operations.Example 1:
Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.
Example 2:
Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score.
The total score is 50 + 15 - 9 + 4 + 42 = 102.
Constraints:
•
n == nums.length•
m == multipliers.length•
1 <= m <= 10^3•
m <= n <= 10^5•
-1000 <= nums[i], multipliers[i] <= 10002022-09-17
336. Palindrome Pairs
Topic: Array, Hash Table, String, Trie
Difficulty: Hard
Problem:
Given a list of unique words, return all the pairs of the distinct indices
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
336. Palindrome Pairs
Topic: Array, Hash Table, String, Trie
Difficulty: Hard
Problem:
Given a list of unique words, return all the pairs of the distinct indices
(i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.Example 1:
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
Example 2:
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
Example 3:
Input: words = ["a",""]
Output: [[0,1],[1,0]]
Constraints:
•
1 <= words.length <= 5000•
0 <= words[i].length <= 300•
words[i] consists of lower-case English letters.2022-09-18
42. Trapping Rain Water
Topic: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack
Difficulty: Hard
Problem:
Given
Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png
Example 2:
Constraints:
•
•
•
42. Trapping Rain Water
Topic: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack
Difficulty: Hard
Problem:
Given
n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
•
n == height.length•
1 <= n <= 2 * 10^4•
0 <= height[i] <= 10^52022-09-19
609. Find Duplicate File in System
Topic: Array, Hash Table, String
Difficulty: Medium
Problem:
Given a list
A group of duplicate files consists of at least two files that have the same content.
A single directory info string in the input list has the following format:
•
It means there are
The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:
•
Example 1:
Example 2:
Constraints:
•
•
•
•
• You may assume no files or directories share the same name in the same directory.
• You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info.
Follow up:
• Imagine you are given a real file system, how will you search files? DFS or BFS?
• If the file content is very large (GB level), how will you modify your solution?
• If you can only read the file by 1kb each time, how will you modify your solution?
• What is the time complexity of your modified solution? What is the most time-consuming part and memory-consuming part of it? How to optimize?
• How to make sure the duplicated files you find are not false positive?
609. Find Duplicate File in System
Topic: Array, Hash Table, String
Difficulty: Medium
Problem:
Given a list
paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order.A group of duplicate files consists of at least two files that have the same content.
A single directory info string in the input list has the following format:
•
"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"It means there are
n files (f1.txt, f2.txt ... fn.txt) with content (f1_content, f2_content ... fn_content) respectively in the directory "root/d1/d2/.../dm". Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:
•
"directory_path/file_name.txt"Example 1:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
Example 2:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]
Constraints:
•
1 <= paths.length <= 2 * 10^4•
1 <= paths[i].length <= 3000•
1 <= sum(paths[i].length) <= 5 * 10^5•
paths[i] consist of English letters, digits, '/', '.', '(', ')', and ' '.• You may assume no files or directories share the same name in the same directory.
• You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info.
Follow up:
• Imagine you are given a real file system, how will you search files? DFS or BFS?
• If the file content is very large (GB level), how will you modify your solution?
• If you can only read the file by 1kb each time, how will you modify your solution?
• What is the time complexity of your modified solution? What is the most time-consuming part and memory-consuming part of it? How to optimize?
• How to make sure the duplicated files you find are not false positive?
2022-09-20
718. Maximum Length of Repeated Subarray
Topic: Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function
Difficulty: Medium
Problem:
Given two integer arrays
Example 1:
Example 2:
Constraints:
•
•
718. Maximum Length of Repeated Subarray
Topic: Array, Binary Search, Dynamic Programming, Sliding Window, Rolling Hash, Hash Function
Difficulty: Medium
Problem:
Given two integer arrays
nums1 and nums2, return the maximum length of a subarray that appears in both arrays.Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].
Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Constraints:
•
1 <= nums1.length, nums2.length <= 1000•
0 <= nums1[i], nums2[i] <= 1002022-09-21
985. Sum of Even Numbers After Queries
Topic: Array, Simulation
Difficulty: Medium
Problem:
You are given an integer array
For each query
Return an integer array
Example 1:
Example 2:
Constraints:
•
•
•
•
•
985. Sum of Even Numbers After Queries
Topic: Array, Simulation
Difficulty: Medium
Problem:
You are given an integer array
nums and an array queries where queries[i] = [val_i, index_i].For each query
i, first, apply nums[index_i] = nums[index_i] + val_i, then print the sum of the even values of nums.Return an integer array
answer where answer[i] is the answer to the i^th query.Example 1:
Input: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: At the beginning, the array is [1,2,3,4].
After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.
Example 2:
Input: nums = [1], queries = [[4,0]]
Output: [0]
Constraints:
•
1 <= nums.length <= 10^4•
-10^4 <= nums[i] <= 10^4•
1 <= queries.length <= 10^4•
-10^4 <= val_i <= 10^4•
0 <= index_i < nums.length2022-09-22
557. Reverse Words in a String III
Topic: Two Pointers, String
Difficulty: Easy
Problem:
Given a string
Example 1:
Example 2:
Constraints:
•
•
•
• There is at least one word in
• All the words in
557. Reverse Words in a String III
Topic: Two Pointers, String
Difficulty: Easy
Problem:
Given a string
s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.Example 1:
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Example 2:
Input: s = "God Ding"
Output: "doG gniD"
Constraints:
•
1 <= s.length <= 5 * 10^4•
s contains printable ASCII characters.•
s does not contain any leading or trailing spaces.• There is at least one word in
s.• All the words in
s are separated by a single space.2022-09-23
1680. Concatenation of Consecutive Binary Numbers
Topic: Math, Bit Manipulation, Simulation
Difficulty: Medium
Problem:
Given an integer
Example 1:
Example 2:
Example 3:
Constraints:
•
1680. Concatenation of Consecutive Binary Numbers
Topic: Math, Bit Manipulation, Simulation
Difficulty: Medium
Problem:
Given an integer
n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9 + 7.Example 1:
Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1.
Example 2:
Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.
Example 3:
Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 10^9 + 7, the result is 505379714.
Constraints:
•
1 <= n <= 10^52022-09-24
113. Path Sum II
Topic: Backtracking, Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg
Example 3:
Constraints:
• The number of nodes in the tree is in the range
•
•
113. Path Sum II
Topic: Backtracking, Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Example 2:
Image: https://assets.leetcode.com/uploads/2021/01/18/pathsum2.jpg
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []
Constraints:
• The number of nodes in the tree is in the range
[0, 5000].•
-1000 <= Node.val <= 1000•
-1000 <= targetSum <= 1000