Leetcode notes

LeetCode 1. Sum of two numbers

Ideas

This problem is guaranteed to be solved , Therefore, there is no need to judge the boundary condition that the array is empty
1. Violence enumeration , Double cycle O(n^2)
2. Sort , Double pointer O(nlogn)+O(n) But the sort subscript will change It can be used pair Store values and original Subscripts
3. One traverse O(n)： Hashtable Enumerate the second number each time , Check whether there is a corresponding answer in front of the elements of the current enumeration , To query whether a certain number exists , You can use hash tables , It can be O(1) Find out whether a certain number exists within the time complexity
Here the hash table is used unordered_map, Its underlying implementation is hash table , Every step O(1) and map The bottom implementation is balanced binary tree , Every step O(logn)

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        unordered_map<int, int> heap;// First define a hash table , Map each number traversed in the array to the corresponding subscript 
        for(int i = 0; i < nums.size(); i ++)  // Traverse every element in the array from front to back 
        {
    
            int r =target - nums[i];// The number to query is target-nums[i]
            if(heap.count(r)) return {
    heap[r], i};// If the number to be queried is in the hash table , Return the subscript of both 
            heap[nums[i]] = i; // If not, insert the current element into the hash table 
        }
        return {
    };  // Because there must be a solution , So there must be return, To avoid warning 

    }
};

LeetCode 2. Addition of two numbers

Ideas

( The linked list simulates manual addition ) O(n)
This is a simulation problem , The storage number of the given linked list is the low order in front , High position behind , Simulate the process of column vertical addition when we were young ：
From the lowest to the highest , Add bit by bit , If sum is greater than or equal to 10, Keep one digit number , At the same time, move forward 1. If the highest bit has carry , You need to fill in at the front 1.
Do the topic about the linked list , There's a common technique ： Add a virtual head node ：ListNode *dummy = new ListNode(-1);, It can simplify the judgment of boundary conditions .
Time complexity ： Because a total of one scan , So time complexity is O(n)

/** * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
    
        // For convenience , First define a virtual head node , In this way, there is no need to judge the head node 
        auto dummy = new ListNode(-1), cur = dummy; //cur Represents the tail node of the current sum 
      
        int t = 0; // carry 
        while(l1 || l2 || t) // When l1 The cycle is not finished , perhaps l2 The cycle is not finished , Or carry t Not for 0 Always do 
        {
                    
            if(l1) t += l1->val, l1 = l1->next;
            if(l2) t += l2->val, l2 = l2->next;
            cur = cur -> next = new ListNode(t % 10);
            t /= 10;
        }

        return dummy->next;

    }
};

LeetCode 3. Longest substring without repeating characters

Ideas

Given a string , Please find the longest substring that does not contain duplicate characters
Notice the difference between substring and subsequence ： The substring must be a continuous segment Subsequence is not necessarily a continuous segment , But the subscript requirement is increasing
Double pointer , Sliding window algorithm Consider how to enumerate all cases , Take a max, All substrings can be divided into n class
Enumeration to i For all substrings of the tail endpoint , Find in it with i Is the farthest end of the tail j bring [j,i] Is the longest substring without repeated characters
If you use a hash table directly , Double circulation , The time complexity is O(n^2)
Double pointer optimization considers monotonicity , In this question, that is the end point i In the future , Corresponding starting point j Will it also be in the future , The answer is yes , The method of counter evidence can prove
Maintain dynamically with hash table [j,i] The number of occurrences of each character in this interval

class Solution {
    
public:
    int lengthOfLongestSubstring(string s) {
    
        unordered_map<char, int> heap; // Define a hash table to dynamically maintain the number of occurrences of each character in the statistical interval 
        int res = 0;
        for( int i = 0, j = 0; i < s.size(); i ++){
    
            heap[s[i]] ++;// Add the currently traversed characters every time 
            while (heap[s[i]] > 1) heap[s[j ++]] --;// If there is repetition, it must be just added s[i] The resulting repetition 
            // hold j Move one back 
            res = max(res, i - j + 1);// Update answers 
        }
        return res;

    }
};

LeetCode 4. Find the median of two positive arrays

Ideas

First consider ： In two ordered arrays , Find out the k decimal , So the first (n+m)/2 The decimal is the median we want
We from nums1 and nums2 Take the front from the middle k/2 Elements , If nums1[k/2−1]>nums2[k/2−1], So on the whole , Less than... In two arrays nums2[k/2−1] There must be insufficient elements k individual , So we can take nums2 Middle front k/2 Remove the number , Find the number in the remaining number k/2 decimal , Become a recursive subproblem , Reduce the elements by half each time , At most recursion logk Time , So time complexity is log(n+m)

class Solution {
    
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        int tot = nums1.size() + nums2.size();
        if (tot % 2 == 0) {
    // The median should pay attention to odd and even numbers , here +1 Because we need to find the first few elements ,size==4 It means to find No 2 And the 3 Elements 
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;// Must pay attention to /2.0, Otherwise, it will be rounded down 
        } else {
    
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
    
        // For convenience , Suppose the first array has a shorter part to query 
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (k == 1) {
    // The first boundary case , For the minimum , Also note that the part of the smaller array to be queried may be empty 
            if (nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }// The second border , The smaller array is empty 
        if (nums1.size() == i) return nums2[j + k - 1];
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        // here si It's from i Start the first k/2 The next position of the element , So when comparing -1,sj The same thing 
        if (nums1[si - 1] > nums2[sj - 1])
            return find(nums1, i, nums2, sj, k - (sj - j));
        else
            return find(nums1, si, nums2, j, k - (si - i));
    }
};

LeetCode 5. Longest text substring

Ideas

Double pointer The time complexity is O(n^2)
Palindrome string , Right and left symmetry , According to the parity of palindrome string length, there are two kinds
Odd number ： It is enough to satisfy the symmetry of left and right sides , The middle element doesn't matter
even numbers ： Two pairs are symmetrical and equal
First enumerate the central points of each palindrome string , When the center point is determined , Use two pointers to walk from the center to both sides at the same time , Until the two characters are different , Or a pointer goes to the boundary , In this way, the longest palindrome substring centered on the current point is found
At this time, the palindrome string is [l+1,r-1] The corresponding length is (r-1)-(l+1)+1 If it is an odd palindrome string ,l and r Initialize to l=i-1 r=i+1
If it is a palindrome string with even length ,l and r Initialize to l=i r=i+1
First enumerate the central points , Traverse once , The time complexity is O(n), After the center point is determined , Enumerating two pointers is O(n), The total time complexity is O(n^2)
The other two methods , The first kind of string hash + Two points , Low time complexity , But it's hard , The second kind DP The time complexity is the same , But you need to open an extra array , Space complexity is high

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        string res;
        for(int i=0;i<s.size();i++){
    // Traverse every character , Explore the longest palindrome substring centered on it 
            // First explore the odd case 
            int l=i-1,r=i+1;
            // When the two pointers do not cross the boundary , And the characters are the same , Take a step outward 
            while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;
            // When you jump out of the loop ,[l+1,r-1] This string is i The corresponding longest odd palindrome substring 
            if(res.size()<r-l-1) res=s.substr(l+1,r-l-1);
            l=i,r=i+1;
            while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;
            if(res.size()<r-l-1) res=s.substr(l+1,r-l-1);
        }
        return res;
    }
};

LeetCode 6. Z Font conversion

Ideas

Looking for a regular , The first line is 0( Subscript ) At the beginning , The tolerance is 2n-2 Equal difference sequence of ; The middle row can be split into two arithmetic sequences , It is divided into the number on the vertical line and the number on the slash , The last row is also an arithmetic sequence , The tolerances for all series of equal differences are 2n-2
The starting element on the vertical line is 0 To n-1, The beginning of the slash is 2n-2- The beginning of the vertical line

class Solution {
    
public:
    string convert(string s, int n) {
    
        string res;// Define the answer sequence 
        if (n == 1) return s;// Boundary condition judgment , Because if you don't judge , stay n==1 Under the circumstances , The tolerance is calculated as 0, It's a dead cycle 
        for (int i = 0; i < n; i ++ ) {
    // Enumerate each row 
            if (i == 0 || i == n - 1) {
    // There is only one arithmetic sequence in the first or last row 
                for (int j = i; j < s.size(); j += 2 * n - 2)
                    res += s[j];
            } 
            else {
    
                for (int j = i, k = 2 * n - 2 - i; j < s.size() || k < s.size(); j += 2 * n - 2, k += 2 * n - 2) {
    // Two equal difference series , The first term of the two equal difference series in each row is i and 2n-2-i
                    if (j < s.size()) res += s[j];
                    if (k < s.size()) res += s[k];
                }
            }
        }
        return res;
    }
};

LeetCode 7. Integer inversion

Ideas

1. Convert to string , After inversion, it becomes an integer
2. Mathematical approach Let's see how to pick out each digit of the number first , Take positive numbers for example , x%10 obtain x Last digit of ,x/10 Get rid of the last one Note that after taking the mold in Mathematics , The number obtained is greater than or equal to 0,c++ Take the modulus of positive numbers in the middle to get a positive number , Negative numbers are modeled as negative numbers , After this , This code can also be applied to negative numbers

class Solution {
    
public:
    int reverse(int x) {
    
// First use longlong To write , Finally, it was changed to int
        long long r=0;
        while(x){
    
            r=r*10+x%10;// There is no need to consider the positive and negative situations alone , because cpp The nature of taking modules 
            x/=10;
        }
        if(r>INT_MAX) return 0;
        if(r<INT_MIN) return 0;
        return r;
    }
};

class Solution {
    
public:
    int reverse(int x) {
    
        int r=0;
        while(x){
    
        	// Try it first , It may have nothing to do with the problem of the sum of three numbers , But the idea of testing is very similar 
            if(r>0&&r>(INT_MAX-x%10)/10) return 0;
            if(r<0&&r<(INT_MIN-x%10)/10) return 0;
            r=r*10+x%10;
            x/=10;
        }
        return r;
    }
};

LeetCode 8. String conversion integers (atoi)

class Solution {
    
public:
    int myAtoi(string str) {
    
        int k = 0;
        while (k < str.size() && str[k] == ' ') k ++ ;// First delete the space in front 
        if (k == str.size()) return 0;// If the whole string is blank , return 0

        int minus = 1;// Handle the possible positive and negative symbols 
        if (str[k] == '-') minus = -1, k ++ ;
        else if (str[k] == '+') k ++ ;
// First use longlong Come and save , Finally, change it to int
        // long long res=0;
        // while(k<str.size()&&str[k]>='0'&&str[k]<='9'){//k Point to numeric characters 
        // res=res*10+str[k]-'0';// Character to number 
        // k++;
        // if(res>INT_MAX) break;// At this time res Must be positive , Just consider whether to add symbols when outputting 
        // }

        // res*=minus;
        // if(res>INT_MAX) return INT_MAX;
        // if(res<INT_MIN) return INT_MIN;
        // return res;
//longlong Change to int, Just add some troublesome special judgments , That's judgment res=res*10+str[k]-'0' Whether there is overflow after this operation , It is divided into positive and negative special judgments 
        int res = 0;
        while (k < str.size() && str[k] >= '0' && str[k] <= '9') {
    
            int x = str[k] - '0';
// Positive numbers res * 10 + x>INT_MAX The former will overflow , Turn into res > (INT_MAX - x) / 10
// negative -res * 10 - x <INT_MIN, Turn it into -res < (INT_MIN + x) / 10
            if (minus > 0 && res > (INT_MAX - x) / 10) return INT_MAX;
            if (minus < 0 && -res < (INT_MIN + x) / 10) return INT_MIN;
// Note that negative absolute values are more than positive absolute values 1, Use special negative infinite , Note that this can only be judged alone , Never change it to less than or equal to , Because such words are like 
//"-2147483647" Will be output -2147483648
            if (-res * 10 - x == INT_MIN) return INT_MIN;
            res = res * 10 + x;
            k ++ ;
        }
        res *= minus;
        return res;
    }
};

LeetCode 9. Palindrome number

Ideas

Numerical methods , Be similar to LeetCode 7. Integer inversion , And this problem does not long long Limit

class Solution {
    
public:
    bool isPalindrome(int x) {
    
        if(x < 0|| x && x % 10 == 0) return false;// If x Itself is negative , Or say x Not 0 But its last one is 0 Words , direct return
        int y = x;// First save the given integer 
        long long res = 0;
        // Start with a bit x Every one of you picks it out and puts it in front 
        while(x){
    
            res = res * 10 + x % 10;
            x /= 10;
        }
        return y == res;
    }
};

Numerical methods , If there is longlong Limit , Only use int, You can only flip the second half , Then judge whether it is equal to the first half

class Solution {
    
public:
    bool isPalindrome(int x) {
    
        if (x < 0 || x && x % 10 == 0) return false;
        int s = 0;
        while (s <= x)
        {
    
            s = s * 10 + x % 10;
            if (s == x || s == x / 10) return true; //  Handle the case that the integer length is odd or even 
            x /= 10;
        }
        return false;
    }
};

class Solution {
    
public:
    bool isPalindrome(int x) {
    
// String method , Convert to string 
        if (x < 0) return 0;
        string s = to_string(x);
        return s == string(s.rbegin(), s.rend());
    }
};

LeetCode 10. Regular Expression Matching

Ideas

similar dp Many problems , For example, give two strings , Find the longest common subsequence , Can it match
Regular Expression Matching ,’.’ Match any single character ,’*’ It means that the character in front of it can appear any number of times ( Include 0 Time )
Dynamic programming ( Sequence model )：
State means f[i,j]
aggregate ： all s[1-i] and p[1-j] Matching scheme
attribute ：bool Whether there is a legal scheme
State calculation
If p[j] No “ star ”, First look at s[i] and p[j] match , Two cases ：s[i] be equal to p[j] perhaps p[j] be equal to ’ spot ’, also f[i-1,j-1] Also match
If p[j] yes “ star ”, Let's enumerate , This ’ star ’ Indicates how many characters , If it is 0 Characters f[i,j-2],1 Characters f[i-1,j-2]&&s[i] matching
2 Characters f[i-2,j-2]&&s[i] matching &&s[i-1] matching …
f[i,j] =f[i,j-2] | f[i-1,j-2]&s[i] | f[i-2,j-2]&s[i]&s[i-1]…
f[i-1,j]=f[i-1,j-2] | f[i-2,j-2]&s[i-1] | f[i-3,j-2]s[i-1]&s[i-2]…
The above formula ： f[i,j] =f[i,j-2] | f[i-1,j] & s[i] matching Optimization is very similar to complete knapsack

class Solution {
    
public:
    bool isMatch(string s, string p) {
    
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;// Subscripts are all from 1 Start , So fill in a space in front 
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));// Boolean array 
        f[0][0] = true;// initialization 
        for (int i = 0; i <= n; i ++ )// It can come from 0 Start , Because it may match when there are no characters 
            for (int j = 1; j <= m; j ++ ) {
    
			// If j==0 Words , because f[0][0] It's already initialized , other i Not for 0 The situation must not match , therefore j from 0 It doesn't make sense at first 
            //* And the previous character as a whole , If you encounter something like this a* Of a If so, skip a
                if (j + 1 <= m && p[j + 1] == '*') continue;
                if ( p[j] != '*') {
    // If i Point to a non empty character , also p[j]!='*',i from 1 Start , otherwise i-1 It makes no sense 
                    f[i][j] = i &&f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                } else if (p[j] == '*') {
    
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }

        return f[n][m];
    }
};