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> threeSum(vector& nums) { vector> a; if(nums.size()<3)//数组nums的长度小于3，则不能构成三数之和 { return {}; } /*for(int i=0; i0||nums[nums.size()-1]<0)//排序后，第一个数大于0，最后一个数小于0，则不可能构成三数之和等于0 { return {}; } for(int i=0; i0)//排序后，三个数的第一个数字大于0，那三个数的和肯定大于0 { return a; } if(i>0&&nums[i]==nums[i-1])//三个数的第一个数与它的前一个数相同，则要排除重复 { continue; } int l=i+1; int r=nums.size()-1; while(l{nums[i],nums[l],nums[r]}); while(l



 
二、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=sign)
{
right--;

}
if(nums[right]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：查找单词 2 并调入内存。 
1 2：在内存中找到单词 1。 
1 2 5：查找单词 5 并调入内存。 
2 5 4：查找单词 4 并调入内存替代单词 1。 
2 5 4：在内存中找到单词 4。 
5 4 1：查找单词 1 并调入内存替代单词 2。 
 共计查了 5 次词典。

 
数据范围

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

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

 代码实现

 
#include
using namespace std;

int main()
{
int m,n,a[1001],head=0,tail=0,b[1001];
//数组a是存放的是文章的内容，后面即为一个顺序队列
scanf("%d %d",&m,&n);

map mp;
//STL
for(int i=0;
 i(a[i],a[i]));
//直接插入到mp中
b[tail++]=a[i];
//直接入队
sum++;
//内存容量增加
}
else//内存容量已满，将队头元素出队列
{
mp.erase(b[head]);
//从mp中删去队头元素
head++;
//出队
mp.insert(pair(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
using namespace std;

int main()
{
int a[1000001],n,k,x[1000001],y[1000001];

scanf("%d %d",&n,&k);

for(int i=0;
i=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=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 iai?? {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；

 【2022/6/29学习总结】对于 100% 的数据， 1≤n≤3×10^6，1≤ai?≤10^9。

 
  思路：

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

 代码实现

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

}



		  	

    
    




    
    
    


推荐阅读

           
                  
              
                  如何下载bt磁力种子 
                
                   
                
              
            

                  
              
                  亚索在永恩出来后新台词 mysql的特征及性能 
                
                   
                
              
            

                  
              
                  三星W2019手机屏幕失灵维修价格 
                
                   
                
              
            

                  
              
                  解压包子使用感怎么样 网红解压包子里面是什么 
                
                   
                
              
            

                  
              
                  经常莫名其妙的就来一下胸口痛，想知道怎么了 
                
                   
                
              
            

                  
              
                  非法吸收公众存款罪怎么处罚 非法吸收公众存款罪怎么处罚的 
                
                   
                
              
            

                  
              
                  方太烤箱烧烤用哪个模式 方太烤箱烤红薯用哪个模式 
                
                   
                
              
            

                  
              
                  大金空调制冷可以制热没反应 大金空调为什么加热不制冷解决步骤 
                
                   
                
              
            

                  
              
                  湖山入映—西湖游记 
                
                   
                
              
            

                  
              
                  石斛粉一天吃多少克为好 
                
                   
                
              
            

                  
              
                  《LOL》IG经理透露,战队被官方针对,选手在韩服无法正常游戏,这事你怎么看？ 
                
                   
                
              
            

                  
              
                  莲子煮粥一次放几个 
                
                   
                
              
            

                  
              
                  数据分析行业的薪酬,游戏公司数据分析工程师薪酬 
                
                   
                
              
            

                  
              
                  原神神鹤是谁 原神神鹤雨海阵容厉害吗 
                
                   
                
              
            

                  
              
                  ?V怎么读 汜怎么读 
                
                   
                
              
            

                  
              
                  有没有专门抓小三的机构 专业捉小三团队多少钱 
                
                   
                
              
            

                  
              
                  公司不证明个人可以申请工伤鉴定吗 
                
                   
                
              
            

                  
              
                  大众辉昂的发动机是进口的吗 大众辉昂的发动机是进口的吗多少钱 
                
                   
                
              
            

                  
              
                  八下期中语文考卷 
                
                   
                
              
            

                  
              
                  二零小麦粉和三零面粉的区别 二零小麦粉和三零面粉的区别是什么 
                
                   
                
              
            

          

c++|红黑树，插入和删除，基于C++的实现 
 Java初级学习笔记|Java语法之多线程（线程的创建，线程的状态，线程安全）的使用 
 数据结构|【数据结构】约瑟夫环（单向循环链表的应用）——C语言 
 比赛经验|2022年6月第十三届蓝桥杯软件类国赛（决赛）C组C语言/C++真题及答案 with 感想 
 leetcode刷题|C++标准模板库方法STL和函数使用说明 
 C#|C#通过线索二叉树进行中序遍历输出 
 数据结构实验报告|数据结构前言练习 
 数据结构|二叉树(2)--------数据结构 
 数据结构与算法|数据结构与算法——栈、队列、堆汇总整理