LeetCode+ 16 - 20

The closest sum of three

Algorithm tags ： Array 、 Double pointer 、 Sort

LeetCode+ 11 - 15_ Xiaoxuecai's blog -CSDN Blog

Give you a length of n Array of integers for  nums  and A target value  target. Please start from nums Choose three integers , Make their sum with  target  Nearest

The closest has two meanings ：① Greater than or equal to target The smallest number of ② Less than or equal to target The maximum number of , One is in t On the right , One is in t On the left , Both cases should be considered

There is only one answer to the question , There is no need to consider the problem of weight determination

In the worst case , Triple cycle , enumeration i、j、k, Enumerate each answer , Just ask for the nearest one , Violent solution

Consider double pointer optimization , First sort the array from small to large , Because there are three variables , It's not good to use double pointers directly , First enumerate one of the variables i, enumeration i after nums[ i ] Fix , Enumerate with two pointers j and k, For each of these j To find the smallest k, bring num[ i ] + nums[ j ] + nums[ k ] ≥ target, In this way, it is possible to enumerate greater than or equal to target The minimum value of

Let's look at another situation ： Less than or equal to target The maximum of , There is no need to rewrite the entire code , As long as the number of pieces is greater than or equal to target The smallest k,num[ i ] + nums[ j ] + nums[ k - 1 ] necessarily ＜ target, It can be found that as long as k - 1 Bring in is less than target The maximum number of

For each of these i、j、k Use these two cases to update the minimum value

nums[ i ] Is constant , When nums[ j ] When it gets bigger ,num[ i ] + nums[ j ] + nums[ k ] still ≥ target, therefore nums[ k ] It can't get bigger , It can only be the same or smaller

because j When it's added ,k Must reduce , You can use the double pointer algorithm to remove one dimension

abs The efficiency of a function is O(1) Of ,pair Compare first first, If first Compare the same second：C++ pair Compare the size of

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        // Sort 
        sort(nums.begin(),nums.end());
        // Need an answer   When storing, you should not only store the difference, but also store and   Need to use  pair  Storage 
        pair<int,int> res(INT_MAX,INT_MAX);
        // enumeration  i j k
        for(int i = 0;i < nums.size();i++) {
            for(int j = i + 1,k = nums.size()- 1;j < k;j++) {
                // For each of these  j  Find the smallest  k
                while(k - 1 > j && nums[i] + nums[j] +nums[k -1] >= target) k--;
                // The sum of the 
                int s = nums[i] + nums[j] + nums[k];
                // The answer is the smallest one   Be careful  s - target  Not necessarily greater than or equal to  target,target  It is likely that less than or equal to target The situation of 
                res = min(res,make_pair(abs(s - target),s));
                if(k - 1 > j) {
                    s = nums[i] + nums[j] + nums[k - 1];
                    res = min(res,make_pair(target - s,s));
                } 
            }
        }
        return res.second;
    }
};

Letter combination of telephone number

Algorithm tags ： Hash 、 character string 、 to flash back 、 Violent search 、 recursive

Give a number only  2-9  String , Returns all the letter combinations it can represent , Each number represents 3 ~ 4 Characters , Give the order of pressing , ask ： How many different character sequences correspond to ？

Press... In the example 23,2 Yes abc Three options ,3 Yes def Three options , There are nine choices for multiplication

A string of indefinite length is given in the title , It is required to output all possible combinations , classical dfs problem

The recursive search tree is given below , Then convert the recursive search tree into code

Recursion and recursion _ Xiaoxuecai's blog -CSDN Blog

In recursion ：① Need to use string path Storage path / programme ② Need to use int u Store the current number of bits

How can we easily find out which letters a number can represent ？ You can open an array to represent

The time complexity of the whole algorithm is related to the length , In the worst case , Each number has 4 A choice , The worst time complexity is 4^n,push_back Answer needs O( n ) Time complexity of , The string length is n, The final time complexity is 4^n × n

class Solution {
public:
    // External variables record the answer 
    vector<string> ans;
    // Use an array to represent all possible cases of each number 
    string strs[10] = {
        //0 1  It's empty 
        "","","abc","def",
        "ghi","jkl","mno",
        "pqrs","tuv","wxyz",
    };
    vector<string> letterCombinations(string digits) {
        // If the string is empty, it directly returns 
        if(digits.empty()) return ans;
        // Incoming string   What is the current number   The initial path is empty 
        dfs(digits,0,"");
        return ans;
    }
    void dfs(string& digits,int u,string path) {
        // If equal to the last digit , Add the current solution to the answer 
        if(u == digits.size()) ans.push_back(path);
        else {
            // Otherwise, traverse the characters that can be taken from the current bit 
            for(auto c : strs[digits[u] - '0'])
                dfs(digits,u + 1,path + c);
        }
    }
};

Sum of four numbers

Algorithm tags ： Array 、 Double pointer 、 Sort

 

 

Refer to the first 15 topic LeetCode+ 11 - 15_ Xiaoxuecai's blog -CSDN Blog

The sum of four and the practice of violence , The time complexity of the quadruple cycle is O( n^4 ), Double pointer optimization is O( n^3 )

Enumerate two variables first , The last two variables are optimized into with the double pointer algorithm O( n ), The method of weight removal is the same as before

If each pointer is the same as the previous number , Just skip. , In this way, we can find all the solutions without repetition ( If it is the same as the previous number , It means that the current status has been enumerated before , And as long as the current number is different from the previous one , The plan must be completely different )

The sum of three numbers enumerates one of them first , The sum of four numbers enumerates two of them first . . .

 i , j, k,u Add up and it may overflow
hold nums[i] + nums[j] + nums[k] + nums[u] ==  targe    Change to nums[i] + nums[j] - target == - nums[k] - nums[u]
hold nums[i] + nums[j] + nums[k] + nums[u-1] >= target Change to nums[i] + nums[j] >= target - (nums[k] + nums[u-1])

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // Sort 
        sort(nums.begin(),nums.end());
        // Record answer 
        vector<vector<int>> res;
        // First enumerate the first pointer  
        for(int i = 0;i < nums.size();i++ ) {
            // Judge that if the current number is equal to the previous number, skip 
            if(i && nums[i] == nums[i - 1]) continue;
            // Enumerate the second pointer 
            for(int j = i + 1;j < nums.size();j++ ) {
                //j  Not the first  1  Number   also  nums[j]  Equal to the previous number   skip 
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;       
                // Enumerate the third variable   from  j + 1  Start the double pointer algorithm 
                for(int k = j + 1,u = nums.size() - 1;k < u;k++ ) {
                    if(k > j + 1 && nums[k] == nums[k - 1]) continue;
                    // For this  k  Find the smallest  u  Make the sum of four numbers greater than or equal to  target
                    while(u - 1 > k && nums[i] + nums[j] >= target - (nums[k] + nums[u-1])) u--;
                    // If the sum of four numbers equals  target  Add the current solution to the answer 
                    if(nums[i] + nums[j] - target == - nums[k] - nums[u]) {
                        res.push_back({nums[i],nums[j],nums[k],nums[u]});
                    }
                }
            }
        }
        return res;
    }
};

Delete the last of the linked list N Nodes

Algorithm tags ： Linked list 、 Double pointer

 

 

 

Give a list , It is required to delete the penultimate of the linked list n Nodes

The header node may be deleted , In case the header node will change , You can add a virtual head node , In this way, the header node will not be deleted

Delete the last k The core of this point is ： Find the last k A point before a point , Then let the previous point next The pointer is equal to the next pointer at the current point

The total length of the linked list is n, Looking for the penultimate k A point before a point , That's the penultimate k + 1 A little bit , You can traverse the entire linked list first , Find the total length of the linked list n, Traverse from top to bottom k + 1 Just a little bit

Start with the virtual head node , Want to find the penultimate k + 1 How many steps does it take to jump a point ？ jump 1 Step can skip to step 2 A little bit , To jump to the penultimate k + 1 A little bit , Altogether n A little bit , Last but not least k + 1 A dot is a positive number n + 1 - ( k + 1 ), That is, the positive number n - k A little bit

jump 1 Step can skip to step 2 A little bit , If you want to jump to the n - k A little bit , Need to jump n - k - 1 Step

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int k) {
        // Create a virtual header node 
        auto dummy = new ListNode(-1);
        dummy->next = head;
        // First find the total length of the linked list , Every point traversed  n++, Last  n  Is the total length of the linked list 
        int n = 0;
        for(auto p = dummy;p;p = p->next) n++;

        // Start with the virtual head node 
        auto p = dummy;
        // Need to jump  n - k - 1  Step 
        for(int i = 0;i < n - k - 1;i++ ) p = p->next;
        // Delete 
        p->next = p->next->next;
        // Return to the next position of the virtual head node   That is, the real head node 
        return dummy->next;
    }
};

Valid parenthesis

Algorithm tags ： Stack 、 character string

 

 

Given a contains only '(',')','{','}','[',']' Sequence , Judge whether the sequence is legal

The left parenthesis is passive , The right parenthesis is active

The left bracket can only wait in place , The right parenthesis can find the nearest left parenthesis that has not been taken away , And match it

The analysis process can be simulated by stack

Every time you encounter an open parenthesis , Add the left bracket to the top of the stack , After encountering the right bracket , At this point, the top element of the stack is the left bracket nearest to the right bracket that has not been taken away , Determine whether the current closing bracket matches it , If the match , Just take it away , If it doesn't match, it means it's illegal

There are two illegal schemes

① If the closing bracket does not find a match , It means it's illegal

② It is also illegal to leave some left parentheses

data structure --- c Language implementation stack ( Array stack & Chain stack & Double stack & Bracket matching problem )_ Xiaoxuecai's blog -CSDN Blog

If you encounter an open bracket, put it on the top of the stack , See if the top of the stack matches the right parenthesis , If it doesn't match, it's illegal , If it matches, pop the top of the stack

At the end, judge whether the stack is empty , If it is empty, it means it is legal , If it is not empty, it means it is illegal

class Solution {
public:
    bool isValid(string s) {
        // Define a stack 
        stack<char> stk;
        // Enumerate all characters from front to back 
        for(auto c : s) {
            // If the current character is an open parenthesis, add it to the stack 
            if(c == '(' || c == '[' || c == '{') stk.push(c);
            // Otherwise, judge whether it matches 
            else {
                /*   Left and right parentheses ASCII Yards don't go very far 
                     If the two parentheses are a pair   So between them ASCII The difference between codes will not be greater than 2
                */
                // If there are elements in the stack   And the top element of the stack ASCII Code and current element ASCII If the code is less than or equal to 2 It is a match   Delete the top of the stack 
                if(stk.size() && abs(stk.top() - c) <= 2) stk.pop();
                // Otherwise, the description does not match 
                else return false;
            }
        }
        // If the stack is empty, it means it is legal   Otherwise, it is illegal 
        return stk.empty();
    }
};