Given an input string (s) and a pattern (p), 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).
Note:
sĀ could be empty and contains only lowercase lettersĀ a-z.
pĀ could be empty and contains only lowercase lettersĀ a-z, and characters likeĀ .Ā orĀ *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation:Ā '*' means zero or more of the precedengĀ element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation:Ā ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation:Ā c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].
For A[i], assuming there are L numbers that are greater than A[i] in range A[0] ~ A[i – 1], and there are R numbers that are greater or equal than A[i] in the range of A[i+1] ~ A[n – 1]. Thus A[i] will be the min of (L + 1) * (R + 1) subsequences.
e.g. A =Ā [3,1,2,4], A[1] = 1, L = 1, R = 2, there are (1 + 1) * (2 + 1) = 6 subsequences are 1 is the min number. [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4]
Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.
The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.
For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].
Example 1:
Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]Output: [null,1,1,1,2,1,4,6]Explanation:
First, S = StockSpanner() is initialized. Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.
Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.
Note:
Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
There will be at most 10000 calls to StockSpanner.next per test case.
There will be at most 150000 calls to StockSpanner.next across all test cases.
The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.
Solution 1: Brute Force (TLE)
Time complexity: O(n) per next call
Space complexity: O(n)
Solution 2: DP
dp[i] := span of prices[i]
j = i – 1
while j >= 0 and prices[i] >= prices[j]: j -= dp[j]
dp[i] = i – j
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Author: Huahua, 144 ms
classStockSpanner{
public:
StockSpanner(){}
intnext(intprice){
if(prices_.empty()||price<prices_.back()){
dp_.push_back(1);
}else{
intj=prices_.size()-1;
while(j>=0&& price >= prices_[j]) {
j -= dp_[j];
}
dp_.push_back(prices_.size()-j);
}
prices_.push_back(price);
returndp_.back();
}
private:
vector<int>dp_;
vector<int>prices_;
};
Solution 3: Monotonic Stack
Maintain a monotonic stack whose element are pairs of <price, span>, sorted by price from high to low.
When a new price comes in
If it’s less than top price, add a new pair (price, 1) to the stack, return 1
If it’s greater than top element, collapse the stack and accumulate the span until the top price is higher than the new price. return the total span
e.g. prices: 10, 6, 5, 4, 3, 7
after 3, the stack looks [(10,1), (6,1), (5,1), (4,1), (3, 1)],
We have aĀ sortedĀ set of digitsĀ D, a non-empty subset ofĀ {'1','2','3','4','5','6','7','8','9'}.Ā (Note thatĀ '0'Ā is not included.)
Now, we write numbers using these digits, using each digit as many times as we want.Ā For example, ifĀ D = {'1','3','5'}, we may write numbers such asĀ '13', '551', '1351315'.
Return the number of positive integers that can be written (using the digits ofĀ D) that are less than or equal toĀ N.
Example 1:
Input: D = ["1","3","5","7"], N = 100Output: 20Explanation:
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
Example 2:
Input: D = ["1","4","9"], N = 1000000000Output: 29523Explanation:
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits of D.
Note:
DĀ is aĀ subset of digitsĀ '1'-'9'Ā in sorted order.
1 <= N <= 10^9
Ā
Solution -1: DFS (TLE)
Time complexity: O(|D|^log10(N))
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Author: Huahua
classSolution{
public:
intatMostNGivenDigitSet(vector<string>& D, int N) {
int ans = 0;
dfs(D,0,N,ans);
returnans;
}
private:
voiddfs(constvector<string>& D, int cur, int N, int& ans) {
if (cur > N) return;
if(cur>0&& cur <= N) ++ans;
for(conststring& d : D)
dfs(D, cur * 10 + d[0] - '0', N, ans);
}
};
Solution 1: Math
Time complexity: O(log10(N))
Space complexity: O(1)
Suppose N has n digits.
less than n digits
We can use all the numbers from D to construct numbers of with length 1,2,…,n-1 which are guaranteed to be less than N.
e.g. n = 52125, D = [1, 2, 5]
format X: e.g. 1, 2, 5 counts = |D| ^ 1
format XX: e.g. 11,12,15,21,22,25,51,52,55, counts = |D|^2
format XXX:Ā counts = |D|^3
format XXXX: counts = |D|^4
exact n digits
if all numbers in DĀ != N[0], counts = |d < N[0] | d in D| * |D|^(n-1), and we are done.
Nearly every one have used theĀ Multiplication Table. But could you find out theĀ k-thĀ smallest number quickly from the multiplication table?
Given the heightĀ mĀ and the lengthĀ nĀ of aĀ m * nĀ Multiplication Table, and a positive integerĀ k, you need to return theĀ k-thĀ smallest number in this table.
Example 1:
Input: m = 3, n = 3, k = 5
Output:Explanation:
The Multiplication Table:
1 2 3
2 4 6
3 6 9
The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Example 2:
Input: m = 2, n = 3, k = 6
Output:Explanation:
The Multiplication Table:
1 2 3
2 4 6
The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).
Note:
TheĀ mĀ andĀ nĀ will be in the range [1, 30000].
TheĀ kĀ will be in the range [1, m * n]
Ā
Solution 1: Nth element (MLE)
Time complexity: O(mn)
Space complexity: O(mn)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
// 59 / 69 test cases passed.
classSolution{
public:
intfindKthNumber(intm,intn,intk){
vector<int>s(m*n);
auto it=begin(s);
for(inti=1;i<=m;++i)
for(intj=1;j<=n;++j)
*it++=i*j;
nth_element(begin(s),begin(s)+k-1,end(s));
returns[k-1];
}
};
Solution2 : Binary Search
Find first x such that there are k elements less or equal to x in the table.
Time complexity: O(m*log(m*n))
Space complexity: O(1)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Author: Huahua, 12 ms
classSolution{
public:
intfindKthNumber(intm,intn,intk){
intl=1;
intr=m*n+1;
while(l<r){
intx=l+(r-l)/2;
if(LEX(m,n,x)>=k)
r=x;
else
l=x+1;
}
returnl;
}
private:
// Returns # of elements in the m*n table that are <= x
intLEX(intm,intn,intx){
intcount=0;
for(inti=1;i<=m;++i)
count+=min(n,x/i);
returncount;
}
};
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Author: Huahua, 16 ms
classSolution{
publicintfindKthNumber(intm,intn,intk){
intl=1;
intr=m*n+1;
while(l<r){
intx=l+(r-l)/2;
if(LEX(m,n,x)>=k)
r=x;
else
l=x+1;
}
returnl;
}
// Returns # of elements in the m*n table that are <= x