Bytedance this company, should be all autumn recruitment companies, the algorithm of the most attention to one, every interview will let you basically tear algorithm, today this article on the record was asked a few algorithm questions, and each algorithm I have given the optimal solution in detail, the following reenactment of the interview scene at that time. You must have learned something after reading it
First, the calf test knife: valid brackets
Most of the time, the interviewer will ask you a question that isn’t that difficult, but don’t get too happy about it, because it can lead to more difficult questions, or it can lead to an easy question that turns out to be the best solution. This problem looks like this
Given a string containing only ‘(‘, ‘)’, determine whether the string is valid. Note: An empty string is a valid string
The sample1Input:"(())"Output:trueThe instance2Input:"()"Output:false
Copy the codeWhen I first saw this question, I thought it was so simple and stable.
In fact, this is a simplified version of LeetCode number 20, which is at the Easy level
So I also without thinking directly to use the stack to solve, I believe 99% will use the stack to solve it? Here I will talk a little bit about the following process, the steps are as follows:
If you encounter a “(“), push it to the stack; if you encounter a “(“)”, check whether there is a “(“) in the stack:
(1), if there is, then the top of the stack"("Pop up, which is equal to and")"If not, then the match fails. That's the first part of the string")"Obviously, this is not reasonable.Copy the code2. When the string traversal is complete, check whether the stack is empty. If the stack is empty, the string is valid.
In order to give attention to small white, I should draw a picture for you to demonstrate ，，，， I am too conscience.
The code looks like this (Java, but you don’t have to learn Java to understand it)
public static boolean isValid(String s){
if(s == null || s.length() < 1)
return true;
int n = s.length();// String length
// Create a stack to hold the characters
Stack<Character> stack = new Stack<>();
// Iterate over the string
for(int i = 0; i < n; i++){
// Get the ith character of the string
char c = s.charAt(i);
if(c == '('){
stack.push(c);
}else{
if(stack.isEmpty())
return false;
elsestack.pop(); }}// Check whether it is null
if(stack.isEmpty())
return true;
return false;
}
Copy the codeSecond, the optimization
Then the interviewer said that the space complexity of my question was O(n) and asked me if I could optimize it.
To be honest, if you’ve done Problem number 20 in LeetCode, maybe your brain is going to be orientated, because that’s the best thing to do with the stack. But this is a simplified version of the problem, and you can actually optimize the space complexity to order one, so you can think about it.
Since all the characters stored in the stack are ** the same kind of character **”(“, in fact, we can use a variable to replace the stack, this variable will record the number of “(“, encountered “(” variable will increase by 1, encountered “)” variable will decrease by 1, the stack is empty is equivalent to the value of the variable is 0.
At that time, my mind was a little confused, so I immediately decided to use this method, so I modified the code in one minute, as follows:
public static boolean isValid(String s){
if(s == null || s.length() < 1)
return true;
int n = s.length();// String length
// Record the number of "(" encountered
int sum = 0;
// Iterate over the string
for(int i = 0; i < n; i++){
// Get the ith character of the string
char c = s.charAt(i);
if(c == '('){
sum++;
}else{
if(sum == 0)
return false;
elsesum--; }}return sum == 0 ? true : false;
}
Copy the codeIn this case, the time complexity is O(n) and the space complexity is O(1).
The longest valid parenthesis
The interviewer then continued to make the question harder and asked the following question
Given a string containing only ‘(‘ and ‘)’, find the length of the longest substring with valid parentheses.
Example 1: Enter:"()"Output: 2 Description: The longest valid parenthesis substring is"()"Example 2: Enter:") () ())"Output: 4 Description: The longest valid parenthesis substring is"() ()"
Copy the codeIn fact, this is the same problem as the original LeetCode problem, problem 32, hard.
This is a question that I’ve done before, and I smiled, and I pretended to think about it with a serious face, and then I immediately gave the idea, and I did it violently at first.
1. Violence
The brute force method is simple, it starts with the first character as the first character of the longest valid parenthesis, then iterates the second character as the first character of the longest valid parenthesis, and then iterates the third character……
For example, for s = “()) (())”.
Select * from ‘)’ where Max = 0; select * from ‘)’ where Max = 0; select * from ‘)’ where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘) where Max = 0; select * from ‘; Max = 4….. This is O(n^2) in time, and O(1) in space.
It’s basically the same thing, but it’s done n times.
Then the interviewer asks, can you optimize?
I knew I was going to ask for optimization, and I had done this myself before, so I pretended to think about it, and I gave the optimization right away.
2, to optimize
In the optimized version of this problem, we’re still using the stack, but instead of “(” pushing, we’re pushing the subscript of “(“). The steps are as follows:
1. Put -1 on the stack first. (Why? For each ‘(‘ encountered, we put its index on the stack. 3. For each ‘) ‘we encounter, we pop the element at the top of the stack and subtract the index of the current element from the index of the popped element to find the length of the currently valid parenthesis string.
In this way, we continue to calculate the length of the valid substring and finally return the length of the longest valid substring.
Look not to understand? Ok, let me make an example and draw some pictures, such as s = “()) (())”, and use the variable Max to hold the extent of the longest valid string, I being the index of the current string
0, initialize: Max = 0; I = 0. -1 Put in the stack
1, I = 0, s[I] = ‘(‘, subscript I = 0
1, I = 1, s[I] = ‘)’; I – top stack element = 1 – (-1) = 2, Max = 2
Be careful at this time
Can’t get it? Ok, let’s take a look at the code for further understanding. The code is as follows:
public int longestValidParentheses(String s) {
int max = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
// Subscript push
stack.push(i);
} else {
/ / out of the stack
stack.pop();
// Check whether the top of the stack is empty
if (stack.empty()) {
stack.push(i);
} else {
// I - top of the stack to get the valid bracket length of the schedulemax = Math.max(max, i - stack.peek()); }}}return maxans;
}
Copy the codeThis is O(n) in time, O(n) in space, so it’s nice to think of a stack.
4. The final blow
I thought I gave this solution is ok, the interviewer should change a question, and then, the interviewer came again: can you optimize? . At this time I fell into meditation…….
If you read the article, you can think about whether it can be optimized in space, because it is impossible to optimize in time.
After thinking for a while, I was surprised that stack could not be used. The optimization scheme must be similar to the above problem, which is to replace the stack with the variable of the number of records. Then I came up with the following details:
In fact, we can still optimize this problem by using variables instead of stacks as we did above, but in this case we need two variables, and let’s say the variables are left and right.
We use left to record the number of ‘(‘ and right to record the number of ‘)’ as we traverse the string from left to right. And in the process of traversing:
1, if left == right, it is clear that right ‘)’ must be matched. So the current valid parenthesis length is 2 * right. Then update Max.
If left < right, then ‘)’ must not match, so we set both left and right to 0.
** When we walk through the string, do we get the maximum length of valid parentheses? ** Think about it
The answer is no, we have to go from right to left to calculate it.
Why is that?
Because in fact “(” and”) “are the same thing, why can’t we do it backwards? So, don’t miss it.
The final code looks like this:
public int longestValidParentheses(String s) {
if(s == null || s.length() < 1)
return 0;
int left = 0, right = 0, max = 0;
// From left to right
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
max = Math.max(max, 2 * right);
} else if(right > left){
left = right = 0;
}
}
left = right = 0;
// From right to left
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
max = Math.max(max, 2 * left);
} else if (left > right) {
left = right = 0; }}return max;
}
Copy the codeThis is O(n) in time and O(1) in space.
conclusion
When said, the last method is still more difficult to think of, from the interview can also be seen, do not look at a question is very simple, some questions to make it very simple, but, if you want to do it in the best way, the difficulty immediately exponential rise.
Behind if you can not understand, it is suggested that re-read it well, the problem of frequency is quite high, mainly to do method, the efficiency of each method is different, but I must give you remind here, is when doing the problem at ordinary times, be sure to find the optimal solution, rather than ac have no matter, should look at other people’s solutions.
Have a harvest? Hope the old iron to a triple strike, to more people see this article
1, like, can let more people see this article
2, pay attention to the original wechat public number “shuai play programming”, in order to consolidate the basic knowledge of the computer (computer network + operating system + database +Linux) and algorithm, recently opened a wechat public number “shuai play programming”, interested in can pay attention, focus on the algorithm related articles, xi Xi. “E-books” will send you a gift package of selected ebooks, including quality ebooks for all skills