2022/6/29学习总结

一、15. 三数之和 - 力扣（LeetCode）

题目描述 

 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

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

输入：nums = [0]
输出：[]
 

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

思路

一开始，采用了暴力解题，时间复杂度为O(n^3)，超时。

后面采用了双指针，左指针指向nums[]数组中的第i个数的后面一个数，右指针指向nums[]数组的最后一个数。通过双指针的移动，寻找与num[]数组中第i个数的和等于0的数。

代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> a;
        if(nums.size()<3)//数组nums的长度小于3，则不能构成三数之和
        {
            return {};
        }
        /*for(int i=0;i<nums.size();i++)//对数组nums排好序后，更有利于判断是否该三数之和是否重复
        {
            for(int j=0;j<nums.size();j++)
            {
                if(nums[i]<nums[j])
                {
                    int t=nums[i];
                    nums[i]=nums[j];
                    nums[j]=t;
                }
            }
        }*/
        sort(nums.begin(),nums.end());
        if(nums[0]>0||nums[nums.size()-1]<0)//排序后，第一个数大于0，最后一个数小于0，则不可能构成三数之和等于0
        {
            return {};
        }
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]>0)//排序后，三个数的第一个数字大于0，那三个数的和肯定大于0
            {
                return a;
            }
            if(i>0&&nums[i]==nums[i-1])//三个数的第一个数与它的前一个数相同，则要排除重复
            {
                continue;
            }
            int l=i+1;
            int r=nums.size()-1;
            while(l<r)
            {
                if(nums[l]+nums[r]+nums[i]==0)
                {
                    a.push_back(vector<int>{nums[i],nums[l],nums[r]});
                    while(l<r&&nums[l]==nums[l+1])//去除重复元素
                    {
                        l++;
                    }
                    while(l<r&&nums[r]==nums[r-1])//去除重复元素
                    {
                        r--;
                    }
                    /*if(nums[l]!=nums[l+1]&&nums[r]!=nums[r-1])
                    {
                        l++;
                        r--;
                    }*/
                    l++;
                    r--;
                }
                else if(nums[l]+nums[r]+nums[i]<0)
                {
                    l++;
                }
                else
                {
                    r--;
                }
            }
        }
        return a;
    }
};

二、912. 排序数组 - 力扣（LeetCode）

题目描述

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

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

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
 

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

思路

直接采用快速排序算法。

代码实现

class Solution {
    public void quickSort(int[] nums, int l, int r)
    {
        if(l>r)
        {
            return;
        }
        int left=l;
        int right=r;
        int sign=nums[left];
        while(left<right)
        {
            while(left<right&&nums[right]>=sign)
            {
                right--;
            }
            if(nums[right]<sign)
            {
                nums[left]=nums[right];
            }
            while(left<right&&nums[left]<=sign)
            {
                left++;
            }
            if(nums[left]>sign)
            {
                nums[right]=nums[left];
            }
            if(left>=right)
            {
                nums[right]=sign;
            }
        }
        quickSort(nums,l,right-1);
        quickSort(nums,left+1,r);
    }
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
}

三、21. 合并两个有序链表 - 力扣（LeetCode）

题目描述 

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
 

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路：

首先确定合成链表的头结点是list1的头结点还是list2的头结点，然后同时遍历list1、list2两条链表，最后肯定会有一条链表不为空，则直接将不为空的链表剩余的元素连接在合成链表后即可。

代码实现

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL)
        {
            return list2;
        }
        if(list2==NULL)
        {
            return list1;
        }
        ListNode* head;
        ListNode* p;
        if(list1->val>=list2->val)
        {
            head=list2;
            list2=list2->next;
        }
        else
        {
            head=list1;
            list1=list1->next;
        }
        p=head;
        while(list1!=NULL&&list2!=NULL)
        {
            if(list1->val<=list2->val)
            {
                p->next=list1;
                p=p->next;
                list1=list1->next;
            }
            else
            {
                p->next=list2;
                p=p->next;
                list2=list2->next;
            }
        }
        while(list1!=NULL)
        {
            p->next=list1;
            p=p->next;
            list1=list1->next;
        }
        while(list2!=NULL)
        {
            p->next=list2;
            p=p->next;
            list2=list2->next;
        }
        /*if(list1!=NULL)//两个while也可以用这两个if替换
        {
            p->next=list1;
        }
        if(list2!=NULL)
        {
            p->next=list2;
        }*/
        return head;
    }
};

四、P1540 [NOIP2010 提高组] 机器翻译 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

题目描述

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M-1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入格式

共 2 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 M,N 代表内存容量和文章的长度。

第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式

一个整数，为软件需要查词典的次数。

输入输出样例

输入

3 7
1 2 1 5 4 4 1

输出 

5

说明/提示

样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

1. 1：查找单词 1 并调入内存。
2. 1 2：查找单词 2 并调入内存。
3. 1 2：在内存中找到单词 1。
4. 1 2 5：查找单词 5 并调入内存。
5. 2 5 4：查找单词 4 并调入内存替代单词 1。
6. 2 5 4：在内存中找到单词 4。
7. 5 4 1：查找单词 1 并调入内存替代单词 2。

共计查了 5 次词典。

数据范围

• 对于 10% 的数据有 M=1，N≤5；
• 对于 100% 的数据有 1001≤M≤100，1≤N≤1000。

思路

题目中“若内存中已存入 MM 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词”，则类似于队列“先进先出”的性质，所以用队列来存放内存中的单词。还有要查询内存中是否有该单词，map中的键值唯一，所以同时用map存放内存中的单词。详细思路代码中有注释。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,a[1001],head=0,tail=0,b[1001];//数组a是存放的是文章的内容，后面即为一个顺序队列
    scanf("%d %d",&m,&n);
    map<int,int> mp;//STL
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    int sum=0,cnt=0;//sum表示已用的内存，cnt表示查词典的次数
    for(int i=0; i<n; i++)
    {
        if(mp.count(a[i])==0)//mp没有该元素
        {
            cnt++;//内存中没有该单词，查词典次数增加
            if(sum<m)//内存容量未满
            {
                mp.insert(pair<int,int>(a[i],a[i]));//直接插入到mp中
                b[tail++]=a[i];//直接入队
                sum++;//内存容量增加
            }
            else//内存容量已满，将队头元素出队列
            {
                mp.erase(b[head]);//从mp中删去队头元素
                head++;//出队
                mp.insert(pair<int,int>(a[i],a[i]));//map中插入新元素
                b[tail++]=a[i];//入队
                //内存容量一直是满的，所以无需改变
            }
        }
    }
    printf("%d",cnt);
    return 0;
}

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

题目描述

有一个长为 n的序列 a，以及一个大小为 k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1,3,-1,-3,5,3,6,7], and k = 3。

输入格式

输入一共有两行，第一行有两个正整数 n,k。 第二行 n 个整数，表示序列 a

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

输入输出样例

输入 

8 3
1 3 -1 -3 5 3 6 7

输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明/提示

【数据范围】
对于 50% 的数据，1≤n≤10^5；
对于 100% 的数据，1≤k≤n≤10^6，ai​∈[−2^31,2^31)。

思路

单调队列。

首先，队列中的元素一定都是位于窗口范围内的，又因为每次只往后移动一个位置，所以只需要判断队头元素是否位于窗口范围内即可。

然后，因为要报错队列内元素的单调性，所以需要将队尾元素不断与当前i所指的元素比较。当找窗口内的最小值时，只有当队尾元素小于当前i所指的元素时，才能够保持当前i所的元素进入到队列里面时，队列里面的元素继续保持单调性。找窗口内的最大值类似，不同的是只有队尾元素大于当前i所指的元素时，才能够保持当前i所的元素进入到队列里面时，队列里面的元素继续保持单调性。

最后，记得只有当窗口经过的长度大于等于k值时，才能去找最大值。

还要注意，他们的顺序不要搞错了，否则结果会出错。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[1000001],n,k,x[1000001],y[1000001];
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int head=0,tail=0;
    for(int i=0;i<n;i++)
    {
        if(head<tail&&y[head]<i-k+1)//队头元素不在窗口的范围内，就将队头元素出队
        {
            head++;
        }
        while(head<tail&&a[y[tail-1]]>=a[i])//队列非空时，队尾元素与新元素比较，如果比新元素大，或者等于，就出队
        {
            tail--;
        }
        y[tail++]=i;//将新元素入队
        if(i>=k-1)//只有窗口经过的元素大于等于k个时，才开始找最大值
        {
            printf("%d ",a[y[head]]);
        }
    }
    printf("\n");
    head=0,tail=0;
    for(int i=0;i<n;i++)
    {
        if(head<tail&&x[head]<i-k+1)//队头元素不在窗口的范围内，就将队头元素出队
        {
            head++;
        }
        while(head<tail&&a[x[tail-1]]<=a[i])//队列非空时，队尾元素与新元素比较，如果小于等于新元素，就出队
        {
            tail--;
        }
        x[tail++]=i;//将新元素入队
        if(i>=k-1)//只有窗口经过的元素大于等于k个时，才开始找最大值
        {
            printf("%d ",a[x[head]]);
        }
    }
    return 0;
}

六、P5788 【模板】单调栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

题目描述

给出项数为 n 的整数数列 a1…n​。

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai​ 的元素的下标，即 f(i)=min i<j≤n,aj​>ai​​ {j}。若不存在，则f(i)=0。

试求出 f(1…n)。

输入格式

第一行一个正整数 n。

第二行 n 个正整数 a1…n​。

输出格式

一行 n 个整数 f(1…n) 的值。

输入输出样例

输入 

5
1 4 2 3 5

输出 

2 5 4 5 0

说明/提示

【数据规模与约定】

对于 30% 的数据，100n≤100；

对于 60% 的数据， n≤5×10^3；

对于 100% 的数据， 1≤n≤3×10^6，1≤ai​≤10^9。

 思路：

从数组的最后往前遍历。如果栈内有元素且栈顶的元素小于当前元素，则出栈，直到栈内没有元素或者栈顶元素小于当前元素。出栈完成之后，如果栈内还有元素，第一个大于当前元素的元素的下标在数组中的位置即栈顶元素，否则，不存在第一个大于当前元素的元素。然后再把当前元素的下标存入栈内。

代码实现

#include<bits/stdc++.h>
using namespace std;
void next(int a[],int n,int b[])
{
    int top=0,c[3000001];//顺序栈
    for(int i=n;i>=1;i--)
    {
        while(top>0&&a[i]>=a[c[top-1]])//栈内有元素且栈顶的元素小于当前元素
        {
            top--;//出栈
        }
        if(top>0)//栈内有元素
        {
            b[i]=c[top-1];//等于栈顶元素
        }
        else
        {
            b[i]=0;
        }
        c[top++]=i;//存下标
    }
}
int main()
{
    int n,a[3000001],b[3000001];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    next(a,n,b);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",b[i]);
    }
    return 0;
}