LeetCode_ 7_ five

1. Sum of two numbers

[ Sum of two numbers ](1. Sum of two numbers - Power button （LeetCode）)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
		int n = nums.size();
        
        // Open a mapping array 
        vector<int> idxs;
        for(int i = 0; i < n; ++i) idxs.push_back(i);
        
        // You can't sort it directly a, Yes a Array subscript mapping array sorting 
        sort(idxs.begin(), idxs.end(), [nums, idxs](int i, int j){
            return nums[idxs[i]] < nums[idxs[j]];
        });
        
        int l = 0, r = n - 1;
        vector<int> ret;
        while(l < r){
            int sum = nums[idxs[l]] + nums[idxs[r]];
            if(sum == target){
                ret.push_back(idxs[l]);
                ret.push_back(idxs[r]);
                break;
            }else if(sum < target){
                l++;
            }else{
                r--;
            }
        }
        return ret;
    }
};

2. Addition of two numbers

[ Addition of two numbers ](2. Addition of two numbers - Power button （LeetCode）)

High precision addition , It's a bit like adding strings we've done .

(1) We can add it by bits , Consider carrying , After each bit operation, the carry must be reset .

(2) Linked lists are not equal in length

(2) If two linked lists are of equal length and the last digit needs to be carried, add 1.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		// Open a header node to store the calculation results of each bit 
        ListNode* H = new ListNode();
        //ptr Traverse ,H->next return 
        ListNode* ptr = H;
        
        int carry = 0;
        while(l1 || l2 || carry){
            int val = 0;
            if(l1) val += l1->val, l1 = l1->next;
            if(l2) val += l2->val, l2 = l2->next;
            val  += carry;
            
            ListNode* node = new ListNode(val % 10);
            ptr->next = node;
            ptr = node;
            
            // Reset carry
            carry = val / 10;
        }
        return H->next;
    }
};

3. Longest substring without repeating characters

Longest substring without repeating characters

Suppose we randomly intercept a part of the original string , Then this part happens to be a substring without repeated characters , We can try to expand on both sides . Only if you don't encounter the same characters as this part, you can expand all the way .

alike , We can also fix one end , Use the other end to expand .

Because the string given by the title is only composed of English letters 、 Numbers 、 Match and space , Is a relatively limited string , So we can open a hash table , To count the number of occurrences of each character in the current interval .

When each character appears only once , We can expand . When a character appears twice , We don't need to delete the characters on the extension side , Instead, let the fixed end cross the position where the character last appeared . It forms a legal New Area .

The sliding window , After two pointers sweep to the end , This problem is solved , So time complexity is O(n).

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
		int n = s.length();
        int ret = 0;
        // Fixed left section 
        int l = 0;
        // Open a hash table 
        unordered_map<char, int> count;
        for(int r = 0; r < n; ++r){
            count[s[r]]++;
            // If a character appears, the left range crosses this character, that is l++
            // At the same time, the number of occurrences of this character --
            while(count[s[r]] >= 2){
                count[s[l++]]--;
            }
            ret = max(ret,r-l+1);
        }
        return ret;
    }
};

4. Find the median of two positive arrays

4. Find the median of two positive arrays - Power button （LeetCode）

emmm, This problem requires that the time complexity should be O(log (m+n)), It's more difficult .

(1) First , We should only grasp the median . Let's calculate the median first , This median is actually a number in the middle of the merged two arrays , Let's assume that k individual .

here k According to the size of the array n To discuss the odd and even numbers of , These two cases can be combined into a formula with a simple mathematical skill .

Because when it's odd (n+1)/2、(n+2)/2 Pointing to the same location .

(2) Yes k Do two points

We take the first two arrays respectively h(k Half of ) individual , Put it into a size k In the container . At this time, the sum of the lengths of the two extracted arrays must be less than or equal to k, If the array is odd, one less , If the array is even, it is equal to k.

If a[h-1]<=b[h-1], Then the red paragraph can never be the first k Elements ( The two arrays are ordered ).

At this point, we can eliminate the first half of the red range , In the next round, we should find the No. in the Yellow range k-h Number .

If b[h-1]<=a[h-1], We will eliminate the blue segment .

(3) The end condition

1. Because every time we score two k When , All the a、b One prefix of the two arrays is reduced . So the length of these two arrays cannot be guaranteed , Because it's possible that in a certain two-point , One array has been completely reduced . At this point, we directly read the k-1 One element will do .
2. If both arrays are not reduced ,k Reduced to 1. Then it is the smaller of the minimum values of the two arrays .

class Solution {
public:
    // from a[sta,n-1] as well as b[stb,m-1] Find the number kth Elements 
    int findKth(const vector<int>& a, int sta, const vector<int>& b, int stb, int kth) {
        //a Reduced 
        if (sta >= a.size()) return b[stb + kth - 1];
        //b Reduced 
        if (stb >= b.size()) return a[sta + kth - 1];
        //k Reduced to 1
        if (kth == 1) return min(a[sta], b[stb]);
        
        // Start two 
        int half = kth / 2;
        int vala = sta + half > a.size() ? a.back() : a[sta + half - 1];
        int counta = sta + half > a.size() ? a.size() - sta : half;

        int valb = stb + half > b.size() ? b.back() : b[stb + half - 1];
        int countb = stb + half > b.size() ? b.size() - stb : half;

        if (vala <= valb) 
            return findKth(a, sta + counta, b, stb, kth - counta);
        return findKth(a, sta, b, stb + countb, kth - countb);
    }

    double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int m = b.size();
        int idx0 = (n + m + 1) / 2;
        int idx1 = (n + m + 2) / 2;

        int val0 = findKth(a, 0, b, 0, idx0);
        int val1 = findKth(a, 0, b, 0, idx1);
        return 1. * (val0 + val1) / 2;
    }
};

    int idx1 = (n + m + 2) / 2;

    int val0 = findKth(a, 0, b, 0, idx0);
    int val1 = findKth(a, 0, b, 0, idx1);
    return 1. * (val0 + val1) / 2;
}

};