• 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)。

    代码实现

    1. class Solution {
    2. public:
    3.     int maxSubArray(vector<int>& nums) {
    4.         if(nums.size()<=1)//数组中只有一个元素时（不存在没有元素的情况，直接返回该元素即可
    5.         {
    6.             return nums[0];
    7.         }
    8.         int dp[nums.size()];
    9.         int max;
    10.         dp[nums.size()-1]=nums[nums.size()-1];//最后一个元素与它后面的元素组成的子数组（连续的）的最大值就是它本身，它后面没有元素了
    11.  
    12.         //当前i所指的元素与它后面的元素组成的子数组（连续的）的最大值，
    13.         //也就是它后面的一个元素的最大子数组和与i所指的数的值（如果它后面的一个元素的
    14.         //最大子数组和大于0），或者是他自己本身（如果它后面的一个元素的最大子数组和
    15.         //小于等于0）。
    16.         for(int i=nums.size()-2;i>=0;i--)
    17.         {
    18.             if(dp[i+1]>0)//i所指的元素的后面一个元素的最大子数组和大于0
    19.             {
    20.                 dp[i]=dp[i+1]+nums[i];
    21.             }
    22.             else//i所指的元素的后面一个元素的最大子数组和小于等于0
    23.             {
    24.                 dp[i]=nums[i];
    25.             }
    26.         }
    27.         max=dp[0];
    28.         for(int i=0;i<nums.size();i++)
    29.         {
    30.             if(dp[i]>max)
    31.             {
    32.                 max=dp[i];
    33.             }
    34.         }
    35.         return max;
    36.     }
    37. };

    二、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

    思路

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

    代码实现

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     ListNode* reverse(ListNode* head){//链表反转
    14.         ListNode* pre=NULL,*cur=head,*next=NULL;
    15.         while(cur!=NULL)
    16.         {
    17.             next=cur->next;
    18.             cur->next=pre;
    19.             pre=cur;
    20.             cur=next;
    21.         }
    22.         return pre;
    23.     }
    24.     ListNode* reverseKGroup(ListNode* head, int k) {
    25.         ListNode* p=new ListNode;//记录链表的头结点，但它本身不是头结点，它的next指向头结点
    26.         p->next=head;
    27.         ListNode* pre=p;//记录要反转的链表的第一个结点的前一个结点
    28.         ListNode* start=head;//start和end是记录反转链表的范围
    29.         ListNode* end=head;
    30.         ListNode* next=head;//下一个反转的链表的第一个元素
    31.         while(next!=NULL)
    32.         {
    33.             for(int i=1;i<k&&end!=NULL;i++)//把end指针移动到要反转的链表的最后一个元素
    34.             {
    35.                 end=end->next;
    36.             }
    37.             if(end==NULL)//剩余的元素不足k个，不能进行翻转
    38.             {
    39.                 break;
    40.             }
    41.             next=end->next;
    42.             end->next=NULL;//先把要进行反转的链表的最后一个元素的next域置空
    43.             end=start;//反转之后的话，头变成尾，尾变成头
    44.             start=reverse(start);
    45.             pre->next=start;//将已翻的链表与未翻转的链表连接
    46.             end->next=next;
    47.             pre=end;//重新定为指针的范围，也就是新的需要翻转的链表
    48.             start=next;
    49.             end=start;
    50.         }
    51.         return p->next; //返回头结点
    52.     }
    53. };

    三、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. //1、暴力法
    2. class Solution {
    3. public:
    4.     vector<int> twoSum(vector<int>& nums, int target) {
    5.         vector<int> a;
    6.         for(int i=0;i<nums.size()-1;i++)
    7.         {
    8.             for(int j=i+1;j<nums.size();j++)
    9.             {
    10.                 if(i!=j&&nums[i]+nums[j]==target)
    11.                 {
    12.                     a.push_back(i);
    13.                     a.push_back(j);
    14.                     return a;
    15.                 }
    16.             }
    17.         }
    18.         return a;
    19.     }
    20. };
    1. //2、哈希表
    2. class Solution {
    3. public:
    4.     vector<int> twoSum(vector<int>& nums, int target) {
    5.         vector<int> a;
    6.         map<int,int> mp;
    7.         for(int i=0;i<nums.size();i++)
    8.         {
    9.             int x=target-nums[i];
    10.             if(mp.count(x)==0)
    11.             {
    12.                 mp[nums[i]]=i;
    13.             }
    14.             else
    15.             {
    16.                 a.push_back(mp[x]);
    17.                 a.push_back(i);
    18.                 break;
    19.             }
    20.         }
    21.         return a;
    22.     }
    23. };

    四、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循环里面的内容之后的单调队列的队头元素。所以输出部分要放在最开始执行。

    代码实现

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. int main()
    4. {
    5.     int n,m,a[2000001],b[2000001],head=0,tail=0;
    6.     scanf("%d %d",&n,&m);
    7.     for(int i=0;i<n;i++)
    8.     {
    9.         scanf("%d",&a[i]);
    10.     }
    11.     for(int i=0;i<n;i++)
    12.     {
    13.         if(i==0)//第一个元素前面没有元素
    14.         {
    15.             printf("0");
    16.         }
    17.         //另外的元素就直接找在它之前的窗子范围之内的最小值，即使i所指的元素前面没有m个元素也可以，
    18.         //因为单调队列在题目要求找最小值的时候，单调递增，最小值一直位于队头
    19.         else
    20.         {
    21.             printf("%d",a[b[head]]);
    22.         }
    23.         if(i!=n-1)
    24.         {
    25.             printf("\n");
    26.         }
    27.         if(head<tail&&b[head]<i-m+1)//队头元素不在窗口的范围内，就将队头元素出队
    28.         {
    29.             head++;
    30.         }
    31.         while(head<tail&&a[b[tail-1]]>=a[i])//队列非空时，队尾元素与新元素比较，如果比新元素大，或者等于，就出队
    32.         {
    33.             tail--;
    34.         }
    35.         b[tail++]=i;//将新元素入队
    36.     }
    37.     return 0;
    38. }

    五、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）。思路，依次将入栈序列入栈，如果在入栈的过程中，出栈序列的元素与栈顶的序列相同，则将栈顶元素出栈，直到栈顶元素与出栈序列的元素不同时。

    代码实现

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. int main()
    4. {
    5.     int q,n,a[101],b[101],c[101],top;
    6.     scanf("%d",&q);
    7.     while(q--)
    8.     {
    9.         scanf("%d",&n);
    10.         top=0;
    11.         for(int i=0; i<n; i++)
    12.         {
    13.             scanf("%d",&a[i]);
    14.         }
    15.         for(int i=0; i<n; i++)
    16.         {
    17.             scanf("%d",&b[i]);
    18.         }
    19.         int i,j=0;
    20.         for(i=0;i<n;i++)
    21.         {
    22.             c[top++]=a[i];
    23.             while(top>0&&c[top-1]==b[j])
    24.             {
    25.                 top--;
    26.                 j++;
    27.             }
    28.         }
    29.         if(top==0)
    30.         {
    31.             printf("Yes");
    32.         }
    33.         else
    34.         {
    35.             printf("No");
    36.         }
    37.         if(q>=1)
    38.         {
    39.             printf("\n");
    40.         }
    41.     }
    42.     return 0;
    43. }
  • 相关阅读:
    Python之第六章 内置容器 --- 正则表达式
    C++模板元模板（异类词典与policy模板）- - - 后篇
    早安心语|不委屈不将就，让生活充满仪式感
    盘点2022年世界杯的科技与狠活
    用 docker 创建 jmeter 容器, 实现性能测试，该如何下手？
    《视觉SLAM十四讲》-- 后端 2
    Spring MVC数据绑定和响应——简单数据绑定（四）自定义类型转换器
    docker下快速部署openldap与self-service-password
    Flutter 通过BottomSheetDialog实现抖音打开评论区，内容自动上推、缩放效果
    嵌入式软件开发工程师未来的薪资待遇是什么情况
  • 原文地址：https://blog.csdn.net/qq_63514555/article/details/125532426