2022/6/30学习总结

一、53. 最大子数组和 - 力扣（LeetCode）

 题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
 

提示：

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

思路

稍微转了一点弯的DP。
原本的思路是从前往后，找当前i所指的元素的最大子数组和，时间复杂度为O(n^2)。
然后改变了一下思路，从后往前找当前i所指的元素的最大子数组和，时间复杂度为O(n)。

代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()<=1)//数组中只有一个元素时（不存在没有元素的情况，直接返回该元素即可
        {
            return nums[0];
        }
        int dp[nums.size()];
        int max;
        dp[nums.size()-1]=nums[nums.size()-1];//最后一个元素与它后面的元素组成的子数组（连续的）的最大值就是它本身，它后面没有元素了

        //当前i所指的元素与它后面的元素组成的子数组（连续的）的最大值，
        //也就是它后面的一个元素的最大子数组和与i所指的数的值（如果它后面的一个元素的
        //最大子数组和大于0），或者是他自己本身（如果它后面的一个元素的最大子数组和
        //小于等于0）。
        for(int i=nums.size()-2;i>=0;i--)
        {
            if(dp[i+1]>0)//i所指的元素的后面一个元素的最大子数组和大于0
            {
                dp[i]=dp[i+1]+nums[i];
            }
            else//i所指的元素的后面一个元素的最大子数组和小于等于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;
    }
};

二、25. K 个一组翻转链表 - 力扣（LeetCode） 

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
 

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

思路

通过指针限定反转的范围，反转之后，再更新指针，也就是更新反转的范围。详细思路见代码注释。

代码实现

/**
 * 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){//链表反转
        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;//记录链表的头结点，但它本身不是头结点，它的next指向头结点
        p->next=head;
        ListNode* pre=p;//记录要反转的链表的第一个结点的前一个结点
        ListNode* start=head;//start和end是记录反转链表的范围
        ListNode* end=head;
        ListNode* next=head;//下一个反转的链表的第一个元素
        while(next!=NULL)
        {
            for(int i=1;i<k&&end!=NULL;i++)//把end指针移动到要反转的链表的最后一个元素
            {
                end=end->next;
            }
            if(end==NULL)//剩余的元素不足k个，不能进行翻转
            {
                break;
            }
            next=end->next;
            end->next=NULL;//先把要进行反转的链表的最后一个元素的next域置空
            end=start;//反转之后的话，头变成尾，尾变成头
            start=reverse(start);
            pre->next=start;//将已翻的链表与未翻转的链表连接
            end->next=next;
            pre=end;//重新定为指针的范围，也就是新的需要翻转的链表
            start=next;
            end=start;
        }
        return p->next; //返回头结点
    }
};

三、1. 两数之和 - 力扣（LeetCode）

题目描述 

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

 思路：

暴力法，直接遍历当前元素与它后面的一个元素的和等于target。

哈希法，将值和位置存入map中，找target与当前元素的差，找到就直接返回，未找到就将当前元素放入mp。

代码实现

//1、暴力法
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、哈希表
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;
    }
};

四、P1440 求m区间内的最小值 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

一个含有 n 项的数列，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 mm 项则从第 1 个数开始，若前面没有数则输出 0。

输入格式

第一行两个整数，分别表示 n，m。

第二行，n 个正整数，为所给定的数列 ai​。

输出格式

n 行，每行一个整数，第 i 个数为序列中 ai​ 之前 m 个数的最小值。

输入输出样例

输入 

6 2
7 8 1 4 3 2

输出 

0
7
7
1
1
3 

说明/提示

对于 100% 的数据，保证 1≤m≤n≤2×10^6，1≤ai​≤3×10^7。

思路

类似于单调队列模板题

P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

和单调队列模板题，稍微的差别在于。这题是找i所指的元素前面的小于或等于m个的元素里面的最小值，不包括自己在内（窗口的范围）。模板题是找i所指的元素包括自己在内，加上它自己之前的m-1个元素的最小值（窗口的范围）。所以这题找队头的最小值，就相当于找的是，i所指的元素的前面一个元素完成for循环里面的内容之后的单调队列的队头元素。所以输出部分要放在最开始执行。

代码实现

#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)//第一个元素前面没有元素
        {
            printf("0");
        }
        //另外的元素就直接找在它之前的窗子范围之内的最小值，即使i所指的元素前面没有m个元素也可以，
        //因为单调队列在题目要求找最小值的时候，单调递增，最小值一直位于队头
        else
        {
            printf("%d",a[b[head]]);
        }
        if(i!=n-1)
        {
            printf("\n");
        }
        if(head<tail&&b[head]<i-m+1)//队头元素不在窗口的范围内，就将队头元素出队
        {
            head++;
        }
        while(head<tail&&a[b[tail-1]]>=a[i])//队列非空时，队尾元素与新元素比较，如果比新元素大，或者等于，就出队
        {
            tail--;
        }
        b[tail++]=i;//将新元素入队
    }
    return 0;
}

五、P4387 【深基15.习9】验证栈序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。

输入格式

第一行一个整数 q，询问次数。

接下来 q 个询问，对于每个询问：

第一行一个整数 n 表示序列长度；

第二行 n 个整数表示入栈序列；

第三行 n 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

输入输出样例

输入 #1

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

输出 #1

Yes
No

思路：

注意，这个题目要进行q次判断。所以每次判断完之后，应该将栈清空（例如，我用的顺序栈，直接将栈顶置为0）。思路，依次将入栈序列入栈，如果在入栈的过程中，出栈序列的元素与栈顶的序列相同，则将栈顶元素出栈，直到栈顶元素与出栈序列的元素不同时。

代码实现

#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;
}