Given a string s, find the length of the longest substring without repeating characters.
Design a data structure that follows the constraints of a Least Recently
Used (LRU)
cache. Implement the LRUCache
class
that
supports
get and put
operations
in O(1) average time complexity.
put(k, v) on
existing key updates value and marks as MRU
get() makes it most recently used
get()
returns -1, cache unchanged
1 ≤ capacity ≤ 30000 ≤ key ≤ 1040 ≤ value ≤ 1052 × 105 calls to
get and put
You are given an array of k linked-lists, where
each
linked-list is
sorted in ascending order. Merge all the linked-lists into one sorted
linked-list
and return
it.
lists = [] →
Return
null
lists = [[], []] →
Return null
lists = [[1,2,3]] →
Return the list itself
k = lists.length, 0 ≤ k ≤ 1040 ≤ lists[i].length ≤ 500-104 ≤ lists[i][j] ≤ 104
N ≤ 104Given 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.
You are required to take a total of numCourses
courses,
labeled from 0 to numCourses - 1.
Some courses have prerequisites, defined by the array prerequisites. Each element prerequisites[i] = [a, b] means that to take
course
a, you must first finish
course
b.
This dependency can be modeled as a directed edge from course
b to course a
(i.e.,
b -> a).
Return true if it is possible to finish all
courses
(i.e.,
there are no circular dependencies). Otherwise, return false.
0 -> 1).0 -> 1 (Finish 0 before 1)1 -> 0 (Finish 1 before 0)0 -> 1 -> 0). It is impossible to
complete
either
course.
0 -> 1 -> 2 -> 3.prerequisites = []. Always possible
(true).
[0, 0].
Impossible to
finish (false).
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 2[ai, bi] are distinct.
A transformation sequence from word beginWord to word endWord
using a dictionary wordList is a sequence of
words
beginWord -> s1 -> s2 -> ... -> sk
such that:
si for 1 <= i <= k must be in wordList. Note that beginWord does not need to be in wordList.sk == endWord.
Given two words, beginWord and endWord, and the dictionary wordList, return the number of words in the
shortest transformation sequence from beginWord to endWord. If no
such sequence exists, return 0.
endWord "cog" is not in wordList, so there is no valid
transformation
sequence.
endWord is
not in wordList, immediately return 0.
beginWord
equals
endWord (typically not the case in
constraints, but
if so), length is 1.
1 <= wordList.length <= 5000wordList[i].length == beginWord.length == endWord.length
1 <= beginWord.length <= 10
Given two strings s and t,
return the minimum window substring of s
such that every character in t (including
duplicates) is
included in the window.
If there is no such substring, return the empty string "".
s.length < t.length, strictly impossible.
1 <= s.length, t.length <= 10^5s and t
consist of
uppercase and lowercase English letters.
Given two sorted arrays nums1 and nums2 of size m
and
n respectively, return the
median
of the two
sorted arrays.
The overall run time complexity should be O(log (m+n)).
nums1.length == m, nums2.length == n0 <= m, n <= 10001 <= m + n <= 2000
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's
(water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
m == grid.lengthn == grid[i].length1 <= m, n <= 300
Given an array of intervals where intervals[i] = [start, end], merge all
overlapping
intervals,
and return an array of the non-overlapping intervals that cover
all
the
intervals in the input.
[1,3] and [2,6] overlap. Merging them gives [1,6] (min start, max end).
[a, b].
4 touches 4, so
they merge.
[[1,10], [2,5]]
merges to [[1,10]].
[[1,2]]
returns [[1,2]].
1 <= intervals.length <= 10^4intervals[i].length == 2The median is the middle value in an ordered integer list. If the size of the list is even, the median is the average of the two middle values.
Design a data structure that supports the following:
void addNum(int num) - Adds the integer
num from the data stream to the data
structure.
double findMedian() - Returns the median of
all
elements so far.5 * 10^4 calls in total.-10^5 <= num <= 10^5addNum: O(log N),
findMedian: O(1) (Two Heaps Strategy)
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can only appear once in the sequence.
The path sum is the sum of the node's values in the path. Return the maximum path sum of any non-empty path.
Note: The path does not need to pass through the root.
2 -> 1 -> 3. Sum: 2 + 1 + 3 = 6.
15 -> 20 -> 7. Sum: 15 +
20 +
7 = 42.
Note node -10 is ignored.
[-3],
output is -3 (must pick at least one
node).
[1, 3 * 10^4]-1000 <= Node.val <= 1000Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
"1,2,3,null,null" or preorder/postorder
strings.
Given a string s, return the longest
palindromic
substring in s.
A palindrome is a string that reads the same forward and backward.
1 <= s.length <= 1000s consist of only digits and English
letters.
You are given an integer array coins
representing
coins of
different denominations and an integer amount
representing
a total amount of money.
Return the fewest number of coins needed to make up that
amount. If
that
amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
1 <= coins.length <= 120 <= amount <= 10^4
Given an array of strings strs, group
the
anagrams together. You can return the answer in any
order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
[""].
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i] consists of lowercase English
letters.
Given an integer array nums and an integer
k, return the kth
largest
element in the array.
Note that it is the kth largest element in the
sorted
order,
not the kth distinct element.
Can you solve it without sorting?
k=1 (max)
or
k=n (min).
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Given an integer array nums, return an array
answer such that answer[i]
is
equal to the product of all the elements of nums
except
nums[i].
The product of any prefix or suffix of nums is
guaranteed
to fit in a 32-bit integer.
You must write an algorithm that runs in O(n)
time
and
without
using the division operation.
2 <= nums.length <= 10^5-30 <= nums[i] <= 30
Given an integer array nums, return all the
triplets [nums[i], nums[j], nums[k]] such that
i != j, i != k,
and j != k, and nums[i] + nums[j] + nums[k]
== 0.
The solution set must not contain duplicate triplets.
[-2,0,1,1,2]
should
not yield duplicate triplets like [-2,1,1]
twice.
[].
0 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5A Trie (pronounced as "try") or Prefix Tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
void insert(String word) Inserts the string
word into
the
trie.boolean search(String word) Returns true if
the
string
word is in the trie (i.e., was previously inserted), and false otherwise.
boolean startsWith(String prefix) Returns
true
if there
is a previously inserted string word that has the prefix prefix, and false
otherwise.
1 <= word.length, prefix.length <= 2000
word and prefix
consist only of lowercase English letters.3 * 10^4 calls in total.
Given an array of meeting time intervals intervals
where
intervals[i] = [start, end], return the
minimum
number
of conference rooms required.
[0, 30].[5, 10], then reused
for
[15, 20].
[1,5]
and
[5,10] do not overlap.
Same room
can be
used.
1 <= intervals.length <= 10^40 <= start < end <= 10^6
Construct a deep copy of a linked list where each node contains
an
additional random pointer, which could point to any node in the
list, or
null.
The deep copy should consist of exactly n
brand
new
nodes, where each new node has its value set to the value of its corresponding
original
node.
Both the next and random
pointer of the new nodes should point to new nodes in the copied list.
[val, random_index].
0 <= n <= 1000-10^4 <= Node.val <= 10^4There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
You are given a list of strings words from the
alien
language's
dictionary, where the strings are sorted lexicographically by
the
rules of
this
new language.
Return a string of the unique letters in the new alien language sorted in
lexicographically
increasing order by the new rules. If there is no solution, return
"". If there are multiple solutions, return
any of
them.
["abc", "ab"],
this is invalid because "ab" is a prefix of "abc" but appears after
it.
a < b and
b < a makes it impossible.
1 <= words.length <= 1001 <= words[i].length <= 100
Given a characters array tasks,
representing
the tasks
a CPU
needs to do, where each letter represents a different task. Tasks could be
done
in any
order.
Each task is done in one unit of time. For each unit of time, the CPU could
complete
either
one task or just be idle.
However, there is a non-negative integer n
that
represents
the cooling period between two same tasks
(the
same
letter
in the array), that is that there must be at least n units of time between
any
two same
tasks.
Return the least number of units of time that the CPU will take to finish all the given tasks.
n is
large, we
might
need many idle slots.
1 <= tasks.length <= 10^40 <= n <= 100
Given a binary tree, find the lowest common ancestor (LCA)
of
two given
nodes
p and q.
The lowest common ancestor is defined between two nodes p
and q as the lowest node in T
that has both p and q
as
descendants (where we allow a node to be a descendant of
itself).
[2, 10^5].p != qp and q will
exist
in the tree.
Given a string s and a dictionary of
strings
wordDict, return true if
s can be segmented into a space-separated
sequence of
one or
more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
1 <= s.length <= 3001 <= wordDict.length <= 1000
You are given an integer array height of
length
n. There are n
vertical
lines
drawn such that the two endpoints of the ith
line are
(i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
void addWord(word) Adds word to the data structure.bool search(word) Returns true if there is any string in the data
structure
that matches
word or false
otherwise.
word may contain dots '.'
where dots can be matched with any letter.
"..."
matches any
3-letter
word.
"pad"
(length
3)
should not match "padd" (length 4).
1 <= word.length <= 25
Implement regular expression matching with support for '.' and
'*'.
'.' Matches any single character.'*' Matches zero or more of the
preceding
element.
The matching should cover the entire input string (not partial).
p = "c*a*b*" can
match
empty string "".
1 <= s.length <= 201 <= p.length <= 20s contains only lowercase English
letters.p contains only lowercase English
letters, '.',
and
'*'.
Given an m x n integers matrix, return
the
length
of the
longest increasing path.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
[1, 2, 6, 9].
[3, 4, 5, 6].
Moving
diagonally is not allowed.
m == matrix.length, n ==
matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
You are given an n x n 2D matrix representing an image,
rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose
sum
equals to k.
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
You are given a string s and an integer k. You can choose any character of the string and change
it
to any other uppercase English character.
You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
1 <= s.length <= 10^50 <= k <= s.length
Given two strings s1 and s2,
return
true if s2 contains a
permutation of s1, or false
otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
1 <= s1.length, s2.length <= 10^4
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine
if
the
input string is valid.
An input string is valid if:
1 <= s.length <= 10^4s consists of parentheses only.
Given n pairs of parentheses, write a function to
generate
all combinations of well-formed parentheses.
open < n to
add '(' and close < open to add ')'.
1 <= n <= 8
Given an array of integers temperatures represents the
daily temperatures, return an array answer such that
answer[i] is the number of days you have to wait after
the
ith day to get a warmer temperature.
If there is no future day for which this is possible, keep answer[i] == 0.
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
Given the root of a binary tree, invert the tree, and
return
its root.
(Swap left and right children for every node).
[0,
100].-100 <= Node.val <= 100
Given the root of a binary tree, determine if it is a
valid binary search tree (BST).
A valid BST is defined as follows:
(min,
max)
ranges.
[1,
10^4].-2^31 <= Node.val <= 2^31 - 1
Given the root of a binary tree, return the
level order
traversal of its nodes' values.
(i.e., from left to right, level by level).
[0,
2000].-1000 <= Node.val <= 1000
Given the root of a binary search tree and an
integer
k, return the kth
smallest
value (1-indexed) of all the values of the nodes in the tree.
1 <= k <= n <= 10^40 <= Node.val <= 10^4
Given two integer arrays preorder and inorder where preorder
is the
preorder traversal of a binary tree and inorder is
the
inorder traversal of the same tree, construct and return the binary tree.
1 <= preorder.length <= 3000inorder.length == preorder.lengthGiven a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a
list
(List[Node]) of its neighbors.
[0,
100].1 <= Node.val <= 100Node.val is unique for each node.
You are given an m x n grid where each cell can
have
one of
three values:
0 representing an empty cell,1 representing a fresh orange, or2 representing a rotten orange.Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a
fresh
orange. If this is impossible, return -1.
m == grid.length, n == grid[i].length1 <= m, n <= 10grid[i][j] is 0, 1, or 2.You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount
of
money of each house, return the maximum amount of money you can rob tonight
without
alerting the police.
1 <= nums.length <= 1000 <= nums[i] <= 400
There is a robot on an m x n grid. The robot is
initially
located at the top-left corner (i.e., grid[0][0]).
The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]).
The robot can only move either down or right at any point in time.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
1 <= m, n <= 100
Given two strings text1 and text2,
return the length of their longest common subsequence. If
there is
no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
1 <= text1.length, text2.length <= 1000
A message containing letters from A-Z can be
encoded
into numbers using the following mapping:
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).
Given a string s containing only digits, return
the
number of ways to decode it.
1 <= s.length <= 100
Given an integer array nums of
unique
elements,
return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
1 <= nums.length <= 10-10 <= nums[i] <= 10nums are
unique.
Given an array nums of distinct integers, return
all the
possible permutations. You can return the answer in any
order.
1 <= nums.length <= 6-10 <= nums[i] <= 10nums are
unique.
Given an array of distinct integers candidates
and a target integer target, return a list of
all
unique combinations of candidates
where the
chosen numbers sum to target.
The same number may be chosen from candidates
an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.
1 <= candidates.length <= 302 <= candidates[i] <= 401 <= target <= 40
Given an integer array nums and an integer k, return the k
most
frequent elements.
You may return the answer in any order.
1 <= nums.length <= 10^5k is in the range [1, the number of unique elements in the array].
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln-1 → Ln.
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
[1, 5 * 10^4].1 <= Node.val <= 1000