LeetCode+ 71 - 75

Simplified path

Algorithm tags ： Stack 、 character string

Give us a path , File path simplification is required , The given path must be legal Linux route , A legal Linux The path is generally from / Start ,/ Represents the root directory , There are many subdirectories home、y,"." Indicates in the current directory （ One "." No change ）, ".." Means to return to the previous Directory

If a path is / home / a /.. / b, root directory → home → a → b, Simplification is actually all about "." and ".." Get rid of , The current case is deleted       / home / b

Pay attention to special situations ： Slash " / " There may be multiple consecutive , It is necessary to replace several consecutive inclined rods with one inclined rod , If you return the upper level directory in the root directory , Because the root directory is already the top directory , Can no longer return , If you go up from the root directory and then return to the root directory , Ensure that the entered directory must be a legal directory , So there is no need to consider illegal situations

Pay attention to the output , If it's not the root directory , There is no need to add , If it is the root directory, it will return a diagonal bar

Reference resources

LeetCode 71 Simplified path AcWing

res Represents the current path ,name Indicates that two '/' Characters between

    1. encounter ". .", Go back to the previous Directory , the res The last one is "/" Delete all the characters from the beginning
    2. encounter "." Or redundant "/" Don't deal with it
    3. Other representations can extend new paths , take "/" + name String added to res Back

Simulation example

path = "/a/./b/../../c/"

The implementation is similar to a stack , All operations are either one grid down from the current directory , Or return to the previous grid from the current directory , The entire data structure will only occur at the top of the stack , Or insert an element into the top of the stack , Or pop an element from the top of the stack , There is no need to simulate the stack when implementing , Just use the string , use string Indicates the current directory , Operate according to the format of the current directory , If it is "." Don't change , If it is ".." Return to the previous directory , If it's not for the above two situations, go down one space , Using the idea of stack

Time complexity analysis

The whole string will only be scanned once , Each directory can only enter and exit the stack once at most , So the time complexity is linear

class Solution {
public:
    string simplifyPath(string path) {
        // Define the final answer path   Record the current file name 
        string res, name;
        // Unified format   If  path  Finally not  "/"  Just make up one  "/"  When reading each file name, you read  "/"  end   Make sure that the last file name is read in a similar way 
        if (path.back() != '/') path += '/';
        // Scan every character from front to back 
        for (auto c : path) {
            // If the current character is not  "/"  It indicates that the current file name is not complete   You need to add it to the file name 
            if (c != '/') name += c;
            else {
                // Otherwise, the current character is  "/"  Indicates that the full file name has been read   Put the file name in name Inside 
                // Deal with special situations   If it is  ".."  Return to the previous directory 
                if (name == "..") {
                    //res Not empty and res The last character is not  "/"  Just pop up the last character 
                    while (res.size() && res.back() != '/') res.pop_back();
                    //res Not empty handle  "/"  Get rid of 
                    if (res.size()) res.pop_back();
                } 
                // If  name  yes  "."  Or empty  "//"  No need to deal with it 
                else if (name != "." && name != "") {
                    // Indicates that a new path can be extended , take "/" +  Insert the current file name at the end of the path 
                    res += '/' + name;
                }
                // hold name Empty 
                name.clear();
            }
        }
        // An empty string indicates the location in the root directory 
        if (res.empty()) res = "/";
        return res;
    }
};

Edit distance

Algorithm tags ： character string 、 Dynamic programming

 

Give two words word1 and word2, To put word1 convert to word2, Any word can be 3 Kind of operation , You can insert a character anywhere , You can delete any character , You can replace any character with another character , Ask at least how many operations are required to make word1 become word2？

Simulation example

classic dp problem

Two strings are represented in two dimensions

① There are many kinds of operation schemes , There will be no case of inserting a character first , Then delete this character , Because this is equivalent to two more operations for no reason , It must not be the optimal solution

Will not appear in the original string "abc" Add up "b", And then "b" Get rid of

② The sequence of actions does not affect the answer , for example character string abc, The first a Delete again in b and c Add one between x And First in b and c Add one between x And then a The effect of deletion is actually the same

There are many operations in total , But when we think about it , Just consider a small part of it , There are no redundant operations in this small part , There will be no addition or deletion , There is no chance of changing a letter twice

The second thing to note is that the order can not be considered when considering , You can set a sequence artificially , The order of operations has no effect on the number of answers , You can fix a sequence , The fixed operation sequence is from front to back

Consider this on the basis of the above analysis dp problem

State means f[ i ][ j ] We should consider it from two perspectives , The first point of view is to consider f[ i ][ j ] Indicates which set , The second consideration is f[ i ][ j ] Indicates which attribute of the collection

We only need to consider the scheme that the operation is carried out from front to back , There is no need to consider the situation that the operation sequence will change

f[ i ][ j ] Represents the minimum number of operation steps in all operation schemes

Find the minimum value by dividing the set

see f[ i ][ j ] What subsets can this set be divided into , Then find the minimum value of each subset separately , Take one of these minimum values min That's the answer.

Division is actually looking for the last difference , hold a[ 1,j ] become b[ 1, j ] How many operation schemes are there in the last step , Then we divide it into several kinds according to the last step

Since we are considering all the schemes in sequence , So we only need to consider the operation in the last step , There is no need to consider the situation in the middle

How many are the last operations ？

First, each string has three operations , There are two strings 6 Kind of operation , So we have a total of 6 Different operations

Let's look at the first case , Let's first look at the case where only the first string is manipulated , There are three ways to operate on only the first string , The first operation scheme , Delete a Last character of , After deleting a[ 1,i ] become b[ 1,j ], That is to get rid of ai after , The first string is equal to the second string , That means the first few steps of this operation scheme , You can already put a[ 1,i - 1 ] become b[ 1,j ], Get rid of ai Before ,a[ 1,i -  1 ] Already equal to b[ 1,j ], All of them a[ 1,i -  1 ] Has become a b[ 1,j ] The minimum number of steps plus 1, That is to say f(i - 1,j) + 1

The second case is a Add a character after , Add it to make the first string equal to the second string , The character added must be bj, In addition, there have been a(1,i) be equal to b(1,j - 1), stay ai Fill in one later bj, So the two strings are equal , If in a Add a character after it , The total minimum value should be f(i,j - 1) + 1

The third case , modify ai, hold ai become bj, After the modification ai and bj equal , Before the change ,a Before i - 1 Characters and b Before i - 1 The characters are equal , If a[ i ] and b[ j ] If it's the same, you don't have to change it , If they are not equal, add 1

about a There are three conditions for the operation of , about b There are three similar situations in the operation of , If you remove b Last character of , There are already before deleting a Of the ai Characters and b Of the j - 1 The characters are equal

From the above derivation , Altogether 6 In this case

But watch carefully , We can find that only 3 Categories: , The number of States is n^2 Level , The transfer quantity is only 3 individual , The whole amount of calculation is 3n^2, That is to say n^2

 

class Solution {
public:
    int minDistance(string a, string b) {
        // First find the length of two strings 
        int n = a.size(),m =b.size();
        // For convenience   Let the subscript of both strings be from  1  Start   First fill a space in front of two strings 
        a = ' ' + a,b = ' ' + b;
        // Define the state array 
        vector<vector<int>> f(n + 1,vector<int>(m + 1));
        // Initialize boundary   When the first string length is  0  When , The length of another string depends on the number of operations 
        for(int i = 1;i <= n;i++ ) f[i][0] = i;
        //a、b The boundaries of both strings need to be initialized 
        for(int i = 1;i <= m;i++ ) f[0][i] = i;
        // Find the values of all States 
        for(int i = 1;i <= n;i++ )
            for(int j = 1;j <= m;j++ ) {
            // Two states 
            f[i][j] =  min(f[i - 1][j],f[i][j - 1]) + 1;
            // Last state   use t To show that the addition is 1 still 0  If a[i] It's not equal to b[j] What you want to add is 1  If equal, it means that there is no need to modify. What to add is 0
            int t = a[i] != b[j];
            f[i][j] = min(f[i][j],f[i - 1][j - 1] + t);
        }
        return f[n][m];
    }
};

Matrix zeroing

Algorithm tags ： Array 、 Hashtable 、 matrix

 

Give us one n × m Matrix , Some of them are 0、 Some are 1 Or some other number , You need to modify the values in the matrix , As long as one element is 0, You need to initialize the row and column of this element to 0

Require in place algorithm , You can't open an extra array to solve this problem  

We should have considered 0 Some positions need to be assigned to 0

Now consider when a certain position of the matrix will be assigned 0？

As long as the row or column where this position is located appears 0, This position will be assigned 0, If the row and column of this position are not 0 It's not 0

If we simplify this problem , In a certain position is 0 Change only one line to 0, This problem is very simple ！

Just enumerate each line , See if this line has 0, If this line appears 0, Just turn this line into 0, If not 0 Don't worry

It is also very simple if there are only columns , Just look at each column separately , Each column can use one bool  Variable , Finally, judge whether this column has 0 That's all right.

If rows and columns are interlaced, it is not easy to do , Because when we modify the line , In fact, the column will be modified

Rows and columns interact , When making row changes, you cannot make column changes , When making column changes, you can't make row changes

Next, consider how to do this problem ？

We must use an array to record the status of each row and column , This topic just asks us not to open additional new arrays , So we can actually use the original array , You can use the number of the first row of the original array to indicate whether there is any in each column 0, The number of the first column of the original array is used to indicate whether each row of the matrix has 0, Of course (0,0) Elements in position are useless , In this way, we can express the Submatrix All the states of

Everything in the framed matrix is clearly recorded , But the first row and the first column are not clearly recorded , You can open two variable records , use r0 Record whether the first line has 0, use c0 Record whether the first column has 0

Sum up , We just need two extra variables , And the first row and the first column of the original matrix , You can determine whether each row and column of the entire matrix has 0 All Record It's clear

Last , Let's see if the first column has 0 If the first column has 0 Just put the first column all become 0, Let's see if the second column has 0, If the first 2 Listed 0 Just turn the second column into 0, Scan each column first , Look at each line again , If this line has 0 Just turn this line into 0, Just scan the assignment again

Time complexity analysis

The entire matrix will be scanned many times , But only scan back constant times , So the time complexity of the whole algorithm is 4 × n^2, The space used is only two variables , So it is O( 1 )

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        // If the matrix is empty, return  false
        if(matrix.empty() || matrix[0].empty()) return;
        //n  Number of lines  m  A number of columns 
        int n = matrix.size(),m = matrix[0].size();
        /*  Record  */
        // seek r0 The first line and c0 First column  1 It means that there is no 0 0 Express 0
        int r0 = 1,c0 = 1;
        // Look at the first line 0  If there is 0 Words  r0 Namely 0, If it's all 1 Words ,r0 Namely 1
        for(int i = 0;i < m;i++ ) if(!matrix[0][i]) r0 = 0;
        // See if the first column has 0
        for(int i = 0;i < n;i++ ) if(!matrix[i][0]) c0 = 0;
        /*  Record  */
        // Look at the first column until  n - 1  Column 
        for(int i = 1;i < m;i++ ) 
            // For the first  i  Come on ,j  from  0  Start ,matrix[0][i]  It means the first one  i  Do you have any  0
            for(int j = 0;j < n;j++ )
                // Deal with each column 
                if(!matrix[j][i]) matrix[0][i] = 0;
        // Processing every line  matrix[i][0]  It means the first one  i  Yes, yes no  0
        for(int i = 1;i < n;i++ )
            for(int j = 0;j < m;j++ )
                if(!matrix[i][j]) matrix[i][0] = 0;
        /*  modify  */
        // Enumerate every column except the first column  
        for(int i = 1;i < m;i++ )
            // If matrix[0][i]=0  It means the first one  i  All columns need to be assigned to  0 
            if(!matrix[0][i])
                for(int j = 0;j < n;j++ )
                    matrix[j][i] = 0;
        // See if each line should be assigned  0
        for(int i = 1;i < n;i++ )
            // If matrix[i][0]=0   It means the first one  i  All rows need to be assigned to  0 
            if(!matrix[i][0])
                for(int j = 0;j < m;j++ )
                    matrix[i][j] = 0;
        // See if the first line should be  0
        if(!r0) for(int i = 0;i < m;i++ ) matrix[0][i] = 0;
        // See if the first column should be  0
        if(!c0) for(int i = 0;i < n;i++ ) matrix[i][0] = 0;
    }    
};

Search for a two-dimensional matrix

Algorithm tags ： Array 、 Two points search 、 matrix

The title gives a matrix , It is required to find a value in the matrix , Consider the one-dimensional case first , If you give us an array , Arrays are ordered , Let's find out if a value exists in the array , What can I do ？

Because arrays are ordered , So it can be solved by dichotomy , The value in the array is incremented , To find a target value , Every time you look at the midpoint , If the midpoint value is less than or equal to the current value , Explain that the target is on the right , Just narrow the range to the right , If the value of the midpoint is greater than the current value , Explain that the answer is on the left , So it can be divided in two

Although the title gives a matrix , In essence, it is also a one-dimensional case

This matrix satisfies that each row is incremented from left to right , At the same time, ensure that the first number of each line is greater than the last number of the previous line

When solving, the matrix can be expanded into one dimension , The expansion into one dimension is increasing , Then two points is enough

You need to do a mapping , hold n × m The subscript of the matrix of is imagined from 0 - n × m - 1, Dichotomous mid Is in 0 - n × m - 1 In this coordinate system , You need to change a subscript in this coordinate system into a two-dimensional subscript , Change the subscript of the expanded one-dimensional array back to the subscript of the original two-dimensional array

Take any subscript t, What is its subscript in the original two-dimensional matrix ？

The line has m Number , Subscript from 0 Start , So it is t Divide m That's ok , Moyi m You can get the number of columns , So you get the subscript in the original array

In fact, it is a one-dimensional dichotomy , Just pay attention to the coordinate transformation

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Empty return  false
        if(matrix.empty() || matrix[0].empty()) return false;
        //n  Number of lines  m  A number of columns 
        int n = matrix.size(),m = matrix[0].size();
        // Two points 
        int l = 0,r = m *n - 1;
        while(l < r)
        {
            int mid = (l+ r) /2;
            if(matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }
        if(matrix[r/ m][r % m] == target) return true;
        return false;
    }
};

Color classification

Algorithm tags ： Array 、 Double pointer 、 Sort

Give us an array , There are only 0、1、2 this 3 Number , You need to sort the array , There are two requirements ： Just one scan , Use only constant space

In essence, it is a double pointer Algorithm , While scanning , use i Subscript to scan ,i Scanning from left to right ,j Also scan from left to right , Maintain one more k,k Scan right to left , When scanning, make sure to scan from 0 ~ j - 1 This paragraph is all about 0, from j ~ i - 1 This paragraph is all about 1, from k + 1 ~ n - 1 The last character , This paragraph is all 2, You can ensure that it is in order

i Move back one at a time , Move i When maintaining j and k

When i exceed k The above conditions can be met

Next, let's look at how to maintain this

At the beginning ,i and j They are all at the starting point ,k In the last position

From the beginning 0 ~ j - 1 It doesn't exist , here j by 0, This paragraph is empty , Meet the requirements , from j ~ i It's empty. , Meet the requirements , The last paragraph is also empty , Meet the requirements

In the process of scanning , Per basis i Just adjust the position of ,ai There are three situations , If ai be equal to 0,j The point is 1, hold j The one that points to 1 become 0, hold 1 Move to the back position , Finally, put j Move one back , At that moment, from 0 ~ j - 1 All are 0,j Moved to the next 1 The location of , from j ~ i - 1 All are 1

If ai be equal to 2,ai Should be in k This position , then k- -, because k The location of is already 2,i There is no need to change , because i Is not necessarily 1, It could be 0

If ai be equal to 1,i+ + that will do

Every time either i ++, Or k - -,i and k The distance between them decreases every time 1, Final cycle n It will be over after times , Because I only scanned once , So the time complexity of the whole algorithm is O( n ), After scanning i = k + 1

With three variables a、b、c Statistics 0、1、2 How many , Scan it again , Then output from front to back a individual 0,b individual 1,c individual 2

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for(int i = 0,j = 0,k = nums.size() - 1;i <= k;) {
            if (nums[i] == 0) swap(nums[i ++ ], nums[j++ ]);
            else if(nums[i] == 2) swap(nums[i], nums[k -- ]);
            else i ++;
        }
    }
};