给你一个整数数组 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; } }

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

示例 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 均按 非递减顺序 排列

/** * 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; } };

题目背景 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
题目描述 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 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。

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

题目描述 有一个长为 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)。

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

题目背景 模板题，无背景。
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; }

推荐阅读

• 

  公主连接re毛二力怎么样 毛二力属性被动技能介绍
• 

  冉闵的简介资料，冉闵的主要成就，力挽狂澜的华夏民族英雄
• 

  免疫|免疫治疗，抗癌领域升起的明星！它是如何发挥作用的？
• 

  如何看待那些想当网红的女孩子呢？
• 

  九刃,九丑在八字中代表什么意思
• 

  p30是安卓系统吗
• 

  民族风情园设计主题是什么？民族风情园景区
• 

  maxwell涡流场分析视频教程
• 

  蔗糖素是糖，蔗糖素是什么
• 

  法律对员工的辞退年龄有哪些规定？
• 

  上古王冠英雄如何升星
• 

  全款购买一套二手房,合同已经签了,现在房主反悔,该怎么办？
• 

  彭放|彭放| 感悟《论语》的人文情怀之【5·23】——不念旧恶，怨是用希
• 

  母猪菜的功效与作用
• 

  ［青春］情窦初开的少年（1）
• 

  苹果id密码在哪里输入
• 

  合同履行地不明怎么确定 合同履行不明确怎么办
• 

  像素|摩托罗拉Edge 20系列手机官宣，8月5日发布，采用1亿像素主摄
• 

  Linux下C++|Linux下C++ EPOLL TCP服务器的设计与实现
• 

  室内白天都算散射光吗

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