Learning summary on June 30, 2022

One 、53. Maximum subarray and - Power button （LeetCode）

  Title Description

Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .

Subarray Is a continuous part of the array .

Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray  [4,-1,2,1] And the biggest , by  6 .
Example 2：

Input ：nums = [1]
Output ：1
Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23
 

Tips ：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Ideas

It turns a little bit DP.
The original idea is from the past to the future , Find the current i The largest subarray and , The time complexity is O(n^2).
Then I changed my mind , Find the current from back to front i The largest subarray and , The time complexity is O(n).

Code implementation

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()<=1)// When there is only one element in the array （ There is no case without elements , Just return this element directly 
        {
            return nums[0];
        }
        int dp[nums.size()];
        int max;
        dp[nums.size()-1]=nums[nums.size()-1];// The last element and its subsequent elements form a sub array （ Successive ） The maximum value of is itself , There is no element behind it 

        // At present i A subarray of the element referred to and the elements following it （ Successive ） The maximum of ,
        // That is, the largest subarray of an element behind it and i The value of the indicated number （ If it is followed by an element 
        // The sum of the largest subarray is greater than 0）, Or himself （ If the largest subarray of an element after it and 
        // Less than or equal to 0）.
        for(int i=nums.size()-2;i>=0;i--)
        {
            if(dp[i+1]>0)//i The sum of the largest subarray of the next element of the indicated element is greater than 0
            {
                dp[i]=dp[i+1]+nums[i];
            }
            else//i The sum of the largest subarray of the next element of the indicated element is less than or equal to 0
            {
                dp[i]=nums[i];
            }
        }
        max=dp[0];
        for(int i=0;i<nums.size();i++)
        {
            if(dp[i]>max)
            {
                max=dp[i];
            }
        }
        return max;
    }
};

Two 、25. K A set of flip list - Power button （LeetCode） 

Title Description

Give you the head node of the list head , Every time  k  Group of nodes to flip , Please return to the modified linked list .

k Is a positive integer , Its value is less than or equal to the length of the linked list . If the total number of nodes is not  k  Integer multiple , Please keep the last remaining nodes in the original order .

You can't just change the values inside the node , It's about actually switching nodes .

Example 1：

Input ：head = [1,2,3,4,5], k = 2
Output ：[2,1,4,3,5]
Example 2：

Input ：head = [1,2,3,4,5], k = 3
Output ：[3,2,1,4,5]
 

Tips ：
The number of nodes in the linked list is n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Ideas

Limit the range of inversion through the pointer , After reversing , Update the pointer , That is, update the scope of inversion . See the code Notes for details .

Code implementation

/**
 * 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* reverse(ListNode* head){// List reversal 
        ListNode* pre=NULL,*cur=head,*next=NULL;
        while(cur!=NULL)
        {
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* p=new ListNode;// Record the head node of the linked list , But it is not a head node itself , its next Point to the head node 
        p->next=head;
        ListNode* pre=p;// Record the previous node of the first node of the linked list to be reversed 
        ListNode* start=head;//start and end Is the range of the reverse linked list 
        ListNode* end=head;
        ListNode* next=head;// The first element of the next inverted linked list 
        while(next!=NULL)
        {
            for(int i=1;i<k&&end!=NULL;i++)// hold end The pointer moves to the last element of the linked list to be reversed 
            {
                end=end->next;
            }
            if(end==NULL)// Insufficient remaining elements k individual , Cannot flip 
            {
                break;
            }
            next=end->next;
            end->next=NULL;// First put the last element of the linked list to be inverted next Domain empty 
            end=start;// After the reversal , Head becomes tail , The tail becomes the head 
            start=reverse(start);
            pre->next=start;// Connect the flipped list with the non flipped list 
            end->next=next;
            pre=end;// Reset to the range of the pointer , That is, the new linked list that needs to be flipped 
            start=next;
            end=start;
        }
        return p->next; // Return to header node 
    }
};

3、 ... and 、1. Sum of two numbers - Power button （LeetCode）

Title Description  

Given an array of integers nums  And an integer target value target, Please find... In the array And is the target value target   the   Two   Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example 1：

Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .
Example 2：

Input ：nums = [3,2,4], target = 6
Output ：[1,2]
Example 3：

Input ：nums = [3,3], target = 6
Output ：[0,1]
 

Tips ：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
There will only be one valid answer

  Ideas ：

Violence law , Directly traverse the sum of the current element and the following element is equal to target.

Hashifa , Store values and positions in map in , look for target Difference from current element , Go straight back when you find it , Put the current element into mp.

Code implementation

//1、 Violence law 
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> a;
        for(int i=0;i<nums.size()-1;i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(i!=j&&nums[i]+nums[j]==target)
                {
                    a.push_back(i);
                    a.push_back(j);
                    return a;
                }
            }
        }
        return a;
    }
};

//2、 Hashtable 
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> a;
        map<int,int> mp;
        for(int i=0;i<nums.size();i++)
        {
            int x=target-nums[i];
            if(mp.count(x)==0)
            {
                mp[nums[i]]=i;
            }
            else
            {
                a.push_back(mp[x]);
                a.push_back(i);
                break;
            }
        }
        return a;
    }
};

Four 、P1440 seek m The minimum in the interval - Luogu | New ecology of computer science education (luogu.com.cn)

Title Description

One contains  n Sequence of terms , Find the m  Number to the minimum value in its range . If the previous number is insufficient  mm  Item from  1 The number begins , If there is no previous number, output 0.

Input format

The first line has two integers , respectively n,m.

The second line ,n A positive integer , For a given sequence of numbers ai​.

Output format

n  That's ok , One integer per row , The first  i  The number is in the sequence ai​  Before m  The minimum number .

I/o sample

Input  

6 2
7 8 1 4 3 2

Output  

0
7
7
1
1
3 

explain / Tips

about 100%  The data of , Guarantee 1≤m≤n≤2×10^6,1≤ai​≤3×10^7.

Ideas

Similar to the monotonic queue template question

P1886 The sliding window /【 Templates 】 A monotonous queue - Luogu | New ecology of computer science education (luogu.com.cn)

And monotonic queue template questions , The slight difference is . This question is to find i The value in front of the indicated element is less than or equal to m The minimum value of elements , Not including myself （ The scope of the window ）. The template question is to find i The element referred to includes itself , Add its own previous m-1 The minimum number of elements （ The scope of the window ）. So this problem is to find the minimum value of the team leader , It's equivalent to looking for ,i The previous element of the indicated element completes for The header element of the monotonous queue after the content in the loop . So the output part should be executed at the beginning .

Code implementation

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[2000001],b[2000001],head=0,tail=0;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++)
    {
        if(i==0)// There is no element before the first element 
        {
            printf("0");
        }
        // Other elements directly find the minimum value within the window range before it , Even if i The element referred to is not preceded by m Elements can also be ,
        // Because the monotonous queue is when the problem requires to find the minimum value , Monotone increasing , The minimum value is always at the head of the team 
        else
        {
            printf("%d",a[b[head]]);
        }
        if(i!=n-1)
        {
            printf("\n");
        }
        if(head<tail&&b[head]<i-m+1)// The queue header element is not within the scope of the window , Just take the team leader element out of the team 
        {
            head++;
        }
        while(head<tail&&a[b[tail-1]]>=a[i])// Queue non-empty time , Compare the tail element with the new element , If it is larger than the new element , Or equal to , Just out of the team 
        {
            tail--;
        }
        b[tail++]=i;// Put new elements in the team 
    }
    return 0;
}

5、 ... and 、P4387 【 Deep base 15. xi 9】 Verify stack sequence - Luogu | New ecology of computer science education (luogu.com.cn)

Title Description

Two sequences are given pushed and poped Two sequences , Its value ranges from 1 To  n(n≤100000). The known stack sequence is pushed, If the out of stack sequence may be poped, The output  Yes, Otherwise output  No. To prevent cheating , Each test point has multiple sets of data .

Input format

The first line is an integer  q, Number of inquiries .

Next  q A asked , For each inquiry ：

The first line is an integer  n Represents sequence length ;

The second line  n An integer represents the stack sequence ;

The third line  n Stack an integer sequence ;

Output format

Output answers for each query .

I/o sample

Input #1

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

Output #1

Yes
No

Ideas ：

Be careful , This topic needs to be carried out q Second judgment . So after every judgment , The stack should be emptied （ for example , The sequence stack I use , Directly set the top of the stack to 0）. Ideas , Stack the stack sequence in turn , If in the process of stacking , The elements of the out of stack sequence are the same as the sequence at the top of the stack , The top of the stack element is removed from the stack , Until the elements at the top of the stack are different from those in the out of stack sequence .

Code implementation

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int q,n,a[101],b[101],c[101],top;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&n);
        top=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0; i<n; i++)
        {
            scanf("%d",&b[i]);
        }
        int i,j=0;
        for(i=0;i<n;i++)
        {
            c[top++]=a[i];
            while(top>0&&c[top-1]==b[j])
            {
                top--;
                j++;
            }
        }
        if(top==0)
        {
            printf("Yes");
        }
        else
        {
            printf("No");
        }
        if(q>=1)
        {
            printf("\n");
        }
    }
    return 0;
}