current position:Home>Longest common prefix, binary search problem
Longest common prefix, binary search problem
2022-02-02 23:20:46 【CSDN Q & A】
class Solution {
public:
string longestCommonPrefix(vector& strs) {
if (!strs.size()) {
return "";
}
int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size();
int low = 0, high = minLength;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (isCommonPrefix(strs, mid)) {
low = mid;
}
else {
high = mid - 1;
}
}
return strs[0].substr(0, low);
}
bool isCommonPrefix(const vector<string>& strs, int length) { string str0 = strs[0].substr(0, length); int count = strs.size(); for (int i = 1; i < count; ++i) { string str = strs[i]; for (int j = 0; j < length; ++j) { if (str0[j] != str[j]) { return false; } } } return true;}
};
ask :int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size(); I can't understand this code , I hope to be a responsible boss , Help me analyze them one by one , I don't understand the grammar of this [](const string& s, const string& t)
ask :bool isCommonPrefix The end of this function return true, I'm so confused , Isn't it that every call to this function will return true Do you , If not why
A responsible big man
Refer to the answer 1:
min_element Returns the minimum value in the container , Default string Compare compare... Based on string "a" < "b"
Defined here [](const string& s, const string& t) {return s.size() < t.size();} yes c++ Lambda function , Compare string length
therefore , The shortest string is returned here
then int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size(); Or get minLength The shortest string length in the string containerbool isCommonPrefix This function is to determine the first... In the string array length Are they the same? , See if there are different returns in the implementation false. If the cyclic comparisons are the same , The function finally returns true.
Refer to the answer 2:
Refer to the answer 3:
Function , The first 8 That's ok ,return after , The whole is directly interrupted and returned , No subsequent code will be executed , End directly .
Refer to the answer 4:
copyright notice
author[CSDN Q & A],Please bring the original link to reprint, thank you.
https://en.primo.wiki/2022/02/202202022320449281.html
The sidebar is recommended
- Dlib is already in setting, but there will still be errors when running
- Vs2015 migration project, failed to connect can
- www.bing. Com took too long to respond
- Why do computers use complement codes
- Why do floating point numbers lose accuracy? How to understand
- The problem of Vue routing history mode jumping to a new window
- PR how to remove the original video subtitles
- How do I get a set of filtered drop-down items in an excel table?
- How to set to allow the WWW service to pass through the server (port 80)
- What are the recording chips with built-in flash? It can record about 40 seconds. What are the characteristics of the chip?
guess what you like
-
The company has added a batch of computers. Now it needs to add a network segment to divide the new computers into this network segment
-
Jenkins deployment project execution pipeline script prompt: Python module not found
-
Do you know how to solve & lt/ details&gt; Too many child elements in the page will cause the page to jam when sliding
-
Which database does the following text image come from? Does anyone know the original image and GT image?
-
How to install PIP? I have found many ways to install it, as shown in the figure
-
It's a little difficult for you to find mistakes. All kinds of mistakes
-
MySQL sub nested data update
-
How do I get the words on the console to the window?
-
How to extract specified data from text in C language
-
Failed to load file or assembly
Random recommended
- How does git handle this situation
- How does Python prevent multiple logs under the same file from writing to one file at the same time
- 174 allocation treasure binary violence solution error
- How does Calc (x - y) in CSS make y the height of a class
- How does CSDN mask messages
- About javascript: iframe web page B is embedded. There is a form in web page B, and the parent Web page a does not refresh
- Wechat applet authorization login problem
- C language, enter 10 integers, find the average and fill in the blank
- The linked list code in cFree can run, but the memory limit is exceeded when submitting
- Oracle database startup failed. The data file header is damaged
- In EF core, how to create a sequence and set nextvalue as the default value when defining the ID of a table?
- timing npm:load:cleanupLog Completed in 2ms
- Esp8266 failed to connect to the serial port, indicating that the serial port is occupied or does not exist
- It's strange why the output is - 1
- Here's why getchar can be executed. After it becomes scanf, even if the correct value is entered, it still prompts for input error
- Is there a question about monotonous station
- Using C + + to complete different N / I applets
- What's the matter with API
- Canvas cannot load picture Tkinter
- A simple code to solve it
- If the HTML page cannot be displayed normally, the code of {% block head%} {% endblock%} will be displayed directly. I don't know what the problem is
- What's wrong with this code that skips uppercase letters and only outputs lowercase letters?
- First clear the content in the text, and then add content in the?
- Problems about Jason object in Java front end
- Unreal 4 code version failed to compile and did not move anything. It was downloaded and compiled directly in GitHub. Only one project failed. Please solve it.
- HTML enters jump for the first time and does not jump for the second time.
- How is the progress bar of Python multi process displayed on the UI?
- The complete link and operation method of tiktok draining to the website need to be effective
- Simulink simulates the vector control (FOC) of permanent magnet synchronous motor and starts the oscillation problem
- Dynamic linked list failed to use bubble sorting
- Remote connection redis problem
- Table a and table B, after changing sides, use explain. The result is a little unexpected. Why
- What's the matter with entering an even number in idea to get "= number"?
- How can C language use a function to find characters and replace them
- Several problems in introductory learning!
- Input two strings STR1 and STR2, connect the string STR1 to STR2, and output STR1 and its length (prompt: string connection function: strcat (STR1, STR2) string length calculation function: strlen (STR))
- Using pointer variable: input a one-dimensional array from the keyboard and return one-dimensional array containing only odd numbers and one-dimensional array containing only even numbers respectively. The data in the array is sorted from small to large.
- Maze game, maze initialization, specify the entrance or exit position, and print the maze.
- The notebook may normally accept the sent information, but it can't load the web page. The network diagnosis and treatment shows the results in the figure below. How should I solve it?
- Car interaction code in Android studio