数据结构算法题 考研专用
Zero神
2019-12-05 09:47:11
# 一、线性表
## 0x00 [二分法](https://www.acwing.com/problem/content/791/)
查找>=key的第一个元素，描述为满足某种情况的最小的元素。
如 2 3 3 4 4 4 5查找 4 则返回 下标3 即最左边的4
```cpp
int l = 0, r = n-1;
while(l < r){
int mid = l + r >> 1;
if(a[mid] >= x) r = mid;
else l = mid+1;
}
if(a[l]!=x) printf("-1 -1\n");//查找失败
```
查找小于<=key的最后一个元素，描述为满足某种情况的最大的元素。
如 2 3 3 4 4 4 5查找 4 则返回 下标5 即最右边的4
```cpp
int l = 0, r = n-1;
while(l < r){
int mid = l+r+1>>1;
if(a[mid] <= x) l = mid;
else r = mid-1;
}
if(a[l]!=x) printf("-1 -1\n");//查找失败
```
##
## 0x01 [回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
```cpp
// s-慢指针 f-快指针
// 循环结束时的状态如下:
// 1 2 2 1 NULL 偶数长度 后半部分起点就是s
// s f
// else
// 1 2 3 2 1 奇数长度 后半部分起点是s的下一个
// s f
bool isPalindrome(ListNode* head) {
if(!head||!head->next) return true;//0个或1个数自然为真
stack<int> stk;//存放前半个数
auto f = head,s = head;
while(f&&f->next){
stk.push(s->val);
s = s->next;
f = f->next->next;
}
if(f) s = s->next;//后半部分起点
while(s){
if(s->val!=stk.top()) return false;
stk.pop(),s = s->next;
}
return true;
}
```
##
## 0x02 [删除链表的倒数第n个节点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
```cpp
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *L = new ListNode(0);
L->next = head;
ListNode *f = L,*s = L;
while(n--&&f->next){f = f->next;}
while(f->next){
s = s->next;
f = f->next;
}
s->next = s->next->next;
return L->next;
}
```
##
## 0x03 [合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
```cpp
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//迭代版
auto h = new ListNode(0), r = h;//r为尾结点
while(l1&&l2){
if(l1->val < l2->val) r->next = l1,l1 = l1->next,r = r->next;//把l1连到尾部
else r->next = l2,l2 = l2->next,r = r->next;
}
if(!l1) r->next = l2;
if(!l2) r->next = l1;
return h->next;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//递归版
if(!l1) return l2;//空时
if(!l2) return l1;
if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
```
##
## 0x04 [旋转链表](https://leetcode-cn.com/problems/rotate-list/)
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
```cpp
ListNode* rotateRight(ListNode* head, int k) {
if(!head) return head;
auto f = head, s = head;
int n = 0;
while(f){n++,f = f->next;}
k = k%n;
f = head;
while(k-- && f->next) f = f->next;
while(f->next) s = s->next, f = f->next;
f->next = head;
head = s->next;
s->next = NULL;
return head;
}
```
##
## 0x05 [反转链表](https://leetcode-cn.com/problems/reverse-linked-list-ii/)
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
```cpp
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(m==n) return head;
auto L = new ListNode(0);
L->next = head;
auto a = L,d = L->next;
for(int len = n-m;len > 0;len--) d = d->next;
while(m-->1){
a = a->next;
d = d->next;
}
auto c = a->next, b = d->next;
for(auto p = c, q = c->next; q!=b;){
auto r = q->next;
q->next = p;
p = q;
q = r;
}
a->next = d;
c->next = b;
return L->next;
}
```
##
## 0x06 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
```cpp
vector<int> vec;
int mid;
TreeNode* sortedListToBST(ListNode* head) {
vec.clear();
while(head){
vec.push_back(head->val);
head=head->next;
}
return buildTree(0,vec.size()-1);
}
TreeNode*buildTree(int l,int r){
if(l>r) return NULL;
int mid=(l+r)/2;
TreeNode *p=new TreeNode(vec[mid]);
p->left=buildTree(l,mid-1);
p->right=buildTree(mid+1,r);
return p;
}
```
##
## 0x07 [环形链表](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
给定一个链表，返回链表开始入环的第一个节点.如果链表无环，则返回 null。
```cpp
ListNode *detectCycle(ListNode *head) {
ListNode *slow=head,*fast=head;
while(fast){
slow = slow->next;
fast = fast->next;
if(fast) fast = fast->next;
else break;
if(slow==fast){
slow = head;
while(slow!=fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}
```
##
## 0x08 [链表的插入排序](https://leetcode-cn.com/problems/insertion-sort-list/)
输入: 4->2->1->3
输出: 1->2->3->4
```cpp
ListNode* insertionSortList(ListNode* head) {
auto h = new ListNode(-1),pre = h,q=head;
for(auto p = head; p; p=q){//把head的每个节点p插入到h链中
for(pre = h; pre->next&&p->val>pre->next->val;pre = pre->next){}//找插入点
q = p->next,p->next = pre->next, pre->next = p;//插入
}
return h->next;
}
```
##
## 0x09 [链表的归并排序](https://leetcode-cn.com/problems/sort-list/)
```cpp
ListNode *sortList(ListNode *head){
if (!head || !head->next) return head;
ListNode *s = head, *f = head->next;
//找到链表的中间位置
while (f&&f->next){ //快慢指针，注意必须前两步存在
s = s->next;
f = f->next->next;
}
ListNode *l1 = sortList(s->next); //右链表
s->next = NULL; //将其断开，为两个链表
ListNode *l2 = sortList(head);
return merge(l1, l2);
}
ListNode *merge(ListNode *l1, ListNode *l2){
auto h = new ListNode(0), r = h;//r为尾结点
while(l1&&l2){
if(l1->val < l2->val) r->next = l1,l1 = l1->next,r = r->next;//把l1连到尾部
else r->next = l2,l2 = l2->next,r = r->next;
}
if(!l1) r->next = l2;
if(!l2) r->next = l1;
return h->next;
}
```
##
## 0x0a [多项式加法和乘法](https://pintia.cn/problem-sets/1169812488801005568/problems/1177113959040782337)
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef struct ListNode{
int val,ex;//系数和指数
ListNode *next;
ListNode(int v, int e) : val(v),ex(e),next(NULL){ }
};
void display(ListNode *h){
ListNode *p = h->next;
if(!p){
printf("0 0");//零多项式
return;
}
else printf("%d %d",p->val,p->ex),p = p->next;//第一项单独输出
while(p) printf(" %d %d",p->val,p->ex),p = p->next;
}
ListNode* add(ListNode *h1, ListNode *h2){
ListNode *h = new ListNode(-1,-1), *r = h,*p = h1->next,*q = h2->next;
while(p&&q){
if(p->ex > q->ex) r->next = new ListNode(p->val,p->ex),r = r->next, p = p->next;
else if(p->ex < q->ex) r->next = new ListNode(q->val,q->ex),r = r->next, q = q->next;
else{
if(q->val+p->val==0){//抵消时
p = p->next,q = q->next;
continue;
}
r->next = new ListNode(q->val+p->val,q->ex);
r = r->next, p = p->next,q = q->next;
}
}
if(!p) r->next = q;
if(!q) r->next = p;
return h;
}
ListNode* mult(ListNode *h1, ListNode *h2){
ListNode *h = new ListNode(-1,-1);
for(ListNode *p = h1->next; p; p = p->next){
for(ListNode *q = h2->next; q; q = q->next){
int val = p->val*q->val, ex = p->ex+q->ex;//一项乘积的值
ListNode *pre = h;
for(; pre->next&&pre->next->ex > ex; pre = pre->next){};//找到插入位置
if(pre->next&&pre->next->ex==ex){
pre->next->val += val;//指数相同,合并同类项
if(pre->next->val==0){//合并后系数为零，则需要删除
ListNode *t = pre->next;
pre->next = pre->next->next;
delete t;
}
}
else {
ListNode *d = new ListNode(val,ex);//乘积项节点 待插入
d->next = pre->next, pre->next = d;
}
}
}
return h;
}
int main(){
ListNode *h1 = new ListNode(-1,-1), *h2 = new ListNode(-1,-1), *r1 = h1, *r2 = h2;//建立两个表达式的头结点
int n, m, v, e;
scanf("%d",&n);
while(n--){//尾插法建立表达式链表
scanf("%d %d",&v,&e);
r1->next = new ListNode(v,e);
r1 = r1->next;
}
scanf("%d",&m);
while(m--){
scanf("%d %d",&v,&e);
r2->next = new ListNode(v,e);
r2 = r2->next;
}
display(mult(h1,h2));
printf("\n");
display(add(h1,h2));
return 0;
}
```
##
## 0x0b [相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
找到两个单链表的交点
A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。如果相交的话，A和B有一段尾巴是相同的，所以两个指针一定会同时到达交点。
```cpp
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto pa = headA,pb = headB;
while(pa!=pb){
pa = (pa ? pa->next:headB);
pb = (pb ? pb->next:headA);
}
return pa;
}
```
##
## 0x0c [删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/)
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2->3->3
输出: 1->2->3
```cpp
ListNode* deleteDuplicates(ListNode* head) {
auto f = head;
while(f){
if(f->next&&f->val==f->next->val) f->next = f->next->next;
else f = f->next;
}
return head;
}
```
##
## 0x0d [删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
输入: 1->2->3->3->4->4->5
输出: 1->2->5
```cpp
ListNode* deleteDuplicates(ListNode* head) {
auto h = new ListNode(-1);//添加头结点
h->next = head;
auto pre = h,p = pre->next;//pre指向无重复的最后一个数 p为遍历节点
while(p){
while(p->next&&p->val==p->next->val) p = p->next;//p与后不同时退出
if(pre->next==p) pre = p, p = p->next;//表示p是无重复元素，更新无重复数 pre = p
else p = p->next,pre->next = p;//p是重复元素,[pre->next,p]全重复 跳过这段即可
}
return h->next;
}
```
# 二、栈
## 0x00 [最小栈](https://leetcode-cn.com/problems/min-stack/)
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
```cpp
stack<int> s,mins;//mins栈同步存储当前栈内元素的最小值
MinStack() {
}
void push(int x) {
s.push(x);
if(mins.empty()) mins.push(x);
else mins.push(min(mins.top(),x));
}
void pop() {
s.pop();
mins.pop();
}
int top() {
return s.top();
}
int getMin() {
return mins.top();
}
```
##
## 0x01 [有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
```cpp
bool isValid(string s) {
stack<char> stk;
for(auto v : s){
if(v=='('||v=='{'||v=='[') stk.push(v);//是左括号则直接入栈
else if(stk.empty()) return false;//只有右括号没有左括号时显然不匹配
else{
int x = stk.top();
stk.pop();
if(v==')'&&x!='('||v=='}'&&x!='{'||v==']'&&x!='[') return false;//不匹配情况
}
}
return stk.empty();//完整的匹配最后栈应该为空
}
```
##
## 0x02 [栈序列合法性](https://leetcode-cn.com/problems/validate-stack-sequences/)
给定 pushed-进栈顺序 和 popped-给定的出栈顺序 两个序列，每个序列中的值都不重复，判断给出的出栈序列是否合法。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
```cpp
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> s;
int n = pushed.size();
for(int i = 0,j=0; i < n; i++){//模拟进栈
s.push(pushed[i]);//先直接进栈
//然后根据出栈序列决定是否出栈
while(!s.empty()&&j<n&&s.top()==popped[j]) s.pop(),j++;//出栈条件
}
return s.empty() ? true:false;//若合法，则此时栈一定是空的
}
```
##
## 0x03 [单调栈](https://www.acwing.com/problem/content/832/)
给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int stk[N],tt,n,x;
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%d",&x);
while(tt&&x<=stk[tt])tt--;
//如果发现新来的x比栈顶元素更小 那么对于之后的数来说 栈内大于x的数便没有价值了
//因为如果之后的数存在左侧更小值,那么会首先选择x,所以栈内大于x的没有价值了
//
if(tt==0) printf("-1 ");
else printf("%d ",stk[tt]);
stk[++tt] = x;
}
return 0;
}
```
##
## 0x04 [逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
```cpp
int getv(string &s){
int ans = 0;
if(s[0]=='-'){
for(int i = 1; i < s.size(); i++) ans = ans*10+s[i]-'0';
return -ans;
}
else{
for(auto v:s) ans = ans*10+v-'0';
return ans;
}
}
int calc(int a, int b, char op){
if(op=='+') return a+b;
else if(op=='-') return a-b;
else if(op=='*') return a*b;
else return a/b;
}
int evalRPN(vector<string>& t) {
stack<int> stk;
for(auto s : t){
if(s[0]>='0'&&s[0]<='9'||s[0]=='-'&&s.size()>1) stk.push(getv(s));//读入数字 负数和减号需要特判
else {//是运算符，则从栈顶弹出两个操作数 进行运算
int b = stk.top();
stk.pop();
int a = stk.top();
stk.pop();
stk.push(calc(a,b,s[0]));
}
}
return stk.top();
}
```
##
## 0x05 [表达式计算](https://www.acwing.com/problem/content/153/)
给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值。
数据可能会出现括号情况，还有可能出现多余括号情况。
数据保证不会出现大于或等于2^31的答案。
数据可能会出现负数情况。
输入格式
输入仅一行，即为表达式。
输出格式
输出仅一行，既为表达式算出的结果。
输入样例：
(2+2)^(1+1)
输出样例：
16
```cpp
#include<bits/stdc++.h>
using namespace std;
stack<char> ops;//运算符栈
stack<int> nums;//运算数栈
int quick_mi(int a, int b){//快速幂
int t = a,ans = 1;
while(b){
if(b&1) ans*=t;
t = t*t;
b>>=1;
}
return ans;
}
void calc(){//执行一次计算
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
char c = ops.top();
ops.pop();
int d;//结果
if(c=='+') d = a + b;
else if(c=='-') d = a - b;
else if(c=='*') d = a * b;
else if(c=='/') d = a / b;
else d = quick_mi(a,b);
nums.push(d);
}
int main(){
string str,left;
ios::sync_with_stdio(false);
cin.tie(0);
cin>>str;
for(int i = 0; i < str.size(); i++) left += '(';
str = left+str+')';//在最左侧添加左括号，防止右括号过多
for(int i = 0; i < str.size(); i++){
if(str[i]>='0'&&str[i]<='9'){//读取正数
int j = i,ta = 0;
while(str[j]>='0'&&str[j]<='9') ta = ta*10+str[j]-'0',j++;//获得该数的值
i = j-1;
nums.push(ta);
}
else if(str[i]=='-'&&i&&!(str[i-1]>='0'&&str[i-1]<='9')&&str[i-1]!=')'){//读取负数 负号的判定，负号前如果是数字，则是减号,反之即可
int j = i+1,ta = 0;
while(str[j]>='0'&&str[j]<='9') ta = ta*10+str[j]-'0',j++;//获得该数的值
i = j-1;
nums.push(-ta);
}
else if(str[i]=='-'||str[i]=='+'){//+,-优先级最低 前面的可以先算了
while(ops.top()!='(') calc();
ops.push(str[i]);
}
else if((str[i]=='*'||str[i]=='/')){// * /时
while(ops.top()=='*'||ops.top()=='/'||ops.top()=='^') calc();//前方可以算的条件
ops.push(str[i]);
}
else if(str[i]=='^'){
while(ops.top()=='^') calc();
ops.push(str[i]);
}
else if(str[i]=='(') ops.push(str[i]);//左括号直接进
else if(str[i]==')'){//括号内的此时一定是优先级递增 可以把括号里的都算了
while(ops.top()!='(') calc();
ops.pop();
}
}
cout<<nums.top();
return 0;
}
```
##
## 0x06 [a进制数转为b进制数](https://www.acwing.com/problem/content/126/)
编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。
这里有62个不同数位{0-9,A-Z,a-z}
输入
62 2 abcdefghiz
输出
62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001
解释: 即把62进制的数 转为 2进制 并输出原数和转化后的数
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a,b;
cin>>n;
while(n--){
string a_line,b_line;//a进制的a_line转为b进制的b_line
vector<int> nums,res;//存储a_line代表的十进制数字,存储b_line代表的十进制数字
cin >> a >> b >> a_line;
for(auto v : a_line){//获得每一位的十进制真值
if(v>='0'&&v<='9') nums.push_back(v-'0');
else if(v>='A'&&v<='Z') nums.push_back(v-'A'+10);
else nums.push_back(v-'a'+36);
}
reverse(nums.begin(),nums.end());//反转，从低位开始,易于处理高位的进位和删除
while(nums.size()){//商不为零时,模拟短除法 直接将a进制转化为b进制
int r = 0;//余数
for(int i = nums.size()-1; i >=0 ; i--){
nums[i] += r*a;//计算当前位的真值(相当于该位的十进制真值)
r = nums[i] % b;//当前位除b后的余数
nums[i]/=b;//当前位的商
}
res.push_back(r);//余数
while(nums.size()&&nums.back()==0) nums.pop_back();//去除除法后高位的前导零
}
reverse(res.begin(),res.end());
for(v:res){//十进制数组转化为字符表达
if(v<10) b_line.push_back(v+'0');
else if(v>=10&&v<36) b_line.push_back(v-10+'A');
else b_line.push_back(v-36+'a');
}
cout<<a<<" "<<a_line<<endl;
cout<<b<<" "<<b_line<<endl;
cout<<endl;
}
}
```
# 三、队列
##
## 0x00 [设计循环队列](https://leetcode-cn.com/explore/learn/card/queue-stack/216/queue-first-in-first-out-data-structure/865/)
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
```cpp
vector<int> data;
int len,front,rear;
MyCircularQueue(int k) {
len = k+1;
data = vector<int>(len);
front = 0,rear = 0; //front指向队头 rear 指向队尾的下一个位置
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if((rear+1)%len==front) return false;//此时队列无法插入
data[rear] = value,rear = (rear+1)%len;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if(rear==front) return false;
front = (front+1)%len;
return true;
}
/** Get the front item from the queue. */
int Front() {
if(rear==front) return -1;
return data[front];
}
/** Get the last item from the queue. */
int Rear() {
if(rear==front) return -1;
return data[(rear-1+len)%len];
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return rear==front;
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
return (rear+1)%len==front;
}
```
##
## 0x01 单调队列-[滑动窗口](https://www.acwing.com/problem/content/156/)
有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。
您只能在窗口中看到k个数字。
每次滑动窗口向右移动一个位置
您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
**输入格式**
输入包含两行。
第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。
第二行有n个整数，代表数组的具体数值。
同行数据之间用空格隔开。
**输出格式**
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
**输入样例：**
8 3
1 3 -1 -3 5 3 6 7
**输出样例：**
-1 -3 -3 -3 3 3
3 3 5 5 6 7
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N];
int q[N],hh,tt=-1;//队列 队头 队尾 注意队列中存的是所代表的数的下标 为了判断是否超出滑动窗口左侧
int main(){
int n,k;//l,r表示窗口范围表示窗口大小
scanf("%d %d",&n,&k);
for(int i = 0; i < n; i++) scanf("%d",&a[i]);
for(int i = 0; i < n; i++){
while(hh<=tt && a[i]<=a[q[tt]]) tt--;//如果发现有更小的数入队,那么之前比它大的数就没用了,因为之前的数会先出队,有小的撑着就行
q[++tt] = i;//入队
if(hh<=tt&&q[hh]<i-k+1) hh++;//如果发现当前最小值出界了(右边界i-窗口长度+1),那么就出队
if(i>=k-1) printf("%d ",a[q[hh]]);//当窗口内有k个元素就输出答案了
}
puts("");
hh = 0, tt = -1;
for(int i = 0; i < n; i++){
while(hh<=tt && a[i]>=a[q[tt]]) tt--;//去除之前的更小的数即可,留大的撑着
q[++tt] = i;//入队
if(hh<=tt&&q[hh]<i-k+1) hh++;
if(i>=k-1) printf("%d ",a[q[hh]]);
}
return 0;
}
```
# 四、二叉树
##
## 0x00 [二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
给定一个二叉树，返回它的前序遍历序列。
```
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
auto p = root;//p为遍历点
while(p||!stk.empty()){
while(p){//只把左侧链全压入
ans.push_back(p->val);//根
stk.push(p);
p = p->left;
}
p = stk.top(),stk.pop();
p = p->right;
}
return ans;
}
```
##
## 0x01 [二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/c-fei-di-gui-ban-by-zeroac/)
```cpp
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
auto p = root;//p为遍历点
stack<TreeNode* > stk;
while(p || !s.empty()){
while(p){只把左侧链全压入
stk.push(p);
p = p->left;
}
p = s.top(),stk.pop();
ans.push_back(p->val);//根
p = p->right;//进入右子树
}
return ans;
}
```
##
## 0x02 [二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/c-fei-di-gui-ban-gen-ju-qian-xu-dao-chu-hou-xu-si-/)
给定一个二叉树，返回它的 后序 遍历。
##### 版本一: 由前序推后序
```cpp
//考虑前序 根左右 想要得到后序 左右根 应该怎么做呢
//首先可以把前序调整一下 根右左 然后逆序即可得到 左右根 即为后序遍历结果
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode* > stk;
auto p = root;//遍历点
while(p||!stk.empty()){//根右左的前序遍历
while(p){
ans.push_back(p->val);
stk.push(p->left);//此处与前序相反 变为右左
p = p->right;
}
p = stk.top();
stk.pop();
}
reverse(ans.begin(),ans.end());//结果逆序即可
return ans;
}
```
##### 版本二: 直接法，增设最近访问节点,用于判断是从左还是右返回的
```cpp
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode* > stk;
TreeNode *p = root,*vised = NULL;//遍历点 最近访问点
while(p||!stk.empty()){
while(p){//左侧链全部压入
stk.push(p);
p = p -> left;
}
p = stk.top();
if(p->right&&p->right!=vised){//说明p的右边还未访问 需要进入右子树遍历
p = p->right;
}
else {//说明p的右子树访问完毕了 可以输出根p了
ans.push_back(p->val);//根
vised = p;
stk.pop();//该点访问完毕 弹出
p = NULL;//下次的p将从栈中取得
}
}
return ans;
}
```
##
## 0x03 [二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
给定一个二叉树，返回其按层次遍历的节点值（即逐层地，从左到右访问所有节点）。
```cpp
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode* > q;
q.push(root);
while(!q.empty()){
vector<int> levelAns;//保存一层的节点
int len = q.size();//该层节点数量
while(len--){
auto p = q.front();
q.pop();
if(p->left) q.push(p->left);
if(p->right) q.push(p->right);
levelAns.push_back(p->val);
}
ans.push_back(levelAns);
}
return ans;
}
```
##
## 0x04 [从前序与中序遍历序列构造二叉树](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回对应的二叉树。
```cpp
unordered_map<int,int> pos;//哈希表 快速查找值的下标
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = inorder.size();
for(int i = 0; i < n; i++) pos[inorder[i]] = i;//记录值的下标
return dfs(preorder,inorder,0,n-1,0,n-1);
}
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){//前序序列的范围 中序序列的范围
if(pl>pr) return NULL;
int val = preorder[pl];
auto rt = new TreeNode(val);
int k = pos[preorder[pl]];//根节点在中序中的位置
int len = k - il;//左子树长度
rt->left = dfs(preorder, inorder, pl+1, pl+len, il,k-1);
rt->right = dfs(preorder,inorder, pl+len+1,pr,k+1,ir);
return rt;
}
```
##
## 0x05 从层序和中序遍历序列构造二叉树
根据一棵树的层序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
层序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回对应的二叉树。
```cpp
int n;//序列长度
unordered_map<int,int> pos;//哈希表 快速查找值的下标
unordered_map<int, bool> vis;//值是否加入树中
TreeNode* buildTree(vector<int>& lev, vector<int>& in) {
n = in.size();
vector<bool> vis(n);//标记层序节点是否用过
for(int i = 0; i < n; i++) pos[in[i]] = i;//记录值的下标
return dfs(lev,in,vis,0,n-1,0);
}
TreeNode* dfs(vector<int>& lev, vector<int>& in,vector<bool>& vis, int il, int ir,int levp){
//il 和 ir为中序区间 levp是层序开始下标
if(ir<il) return NULL;
int ret,p,flag = 0;//根的值及其在中序中的位置 成功标志
for(int i = levp; i < n; i++){//找当前的根 顺序往后遍历层序节点
p = pos[lev[i]],ret = in[p];//查找层序节点在中序中的位置
if(ret!=lev[i]||p<il||p>ir||vis[ret]) continue;//查找失败
vis[ret] = true,flag = 1;//查找成功 标记 跳出
break;
}
if(!flag) return NULL;//查找失败
TreeNode* r = new TreeNode(ret);
r->left = dfs(lev,in,vis,il,p-1,levp+1);
r->right = dfs(lev,in,vis,p+1,ir,levp+1);
return r;
}
```
##
## 0x06 二叉树的宽度
即求节点数最多的那一层的节点个数
```cpp
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
int width = 0;
queue<TreeNode* > q;
q.push(root);
while(!q.empty()){
int len = q.size();//获得该层节点数量
width = max(width,len);//更新最大宽度
while(len--){
auto p = q.front();
q.pop();
if(p->left) q.push(p->left);
if(p->right) q.push(p->right);
}
}
return width;
}
```
##
## 0x07 [二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
```cpp
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//后续遍历思想
if(!root||root==p||root==q) return root;//p,q节点在根部时
//p,q节点在子树中时
auto left = lowestCommonAncestor(root->left,p,q);//左子树的最近祖先
auto right = lowestCommonAncestor(root->right,p,q);//右
if(!left){//左子树中不包含p和q，只能是右的返回值
return right;
}
if(!right) return left;//同理
return root;//此时说明p,q在左右两侧，root就是最近祖先
}
```
##
## 0x08 [对称二叉树](https://leetcode-cn.com/problems/symmetric-tree/)
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的。
##### 递归版
```cpp
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return dfs(root->left,root->right);
}
bool dfs(TreeNode* l, TreeNode* r){//判断左右子树l,r是否对称
if(!l&&!r) return true;
if(l&&!r||!l&&r) return false;
if(l->val==r->val){
return dfs(l->right,r->left)&&dfs(l->left,r->right);
//左子树的右和右子树的左相同，左子树的左和右子树的右相同时 则对称
}
return false;
}
```
##### 迭代版
```cpp
bool isSymmetric(TreeNode* root) {//非递归
//对左子树采取左中右的中序遍历，对右子树采取右中左的中序遍历，在遍历过程中比较即可
if(!root) return true;
stack<TreeNode* > s1,s2;//遍历左子树的栈和遍历右边的栈
auto p1 = root->left, p2 = root->right;
while(p1||s1.size()||p2||s2.size()){
while(p1&&p2){
s1.push(p1),p1 = p1->left;
s2.push(p2),p2 = p2->right;
}
if(p1||p2) return false;//此时两个本应该都为空的
p1 = s1.top(), s1.pop();
p2 = s2.top(), s2.pop();
if(p1->val!=p2->val) return false;
p1 = p1->right,p2 = p2->left;
}
return true;
}
```
##
## 0x09 [验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/)
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
##### 版本一:中序遍历
```cpp
long long pre = -1e10;//中序遍历过程中的前驱节点的值
bool isValidBST(TreeNode* root) {
if(!root) return true;
bool t = isValidBST(root->left);
if(!t||pre>=root->val) return false;//左子树非搜索树或者左子树不小于根
pre = root->val;//准备遍历右子树 则当前根作为右子树的前驱节点了
return isValidBST(root->right);
}
```
##### 版本二:限定节点值的范围
```cpp
bool isValidBST(TreeNode* root) {
return dfs(root,INT_MIN,INT_MAX);
}
//限定节点值的范围即可
bool dfs(TreeNode* p, long long minv, long long maxv){
if(!p) return true;
if(p->val<minv||p->val>maxv) return false;//不满足范围则一定不是
return dfs(p->left,minv,p->val-1ll)&&dfs(p->right,p->val+1ll,maxv);
}
```
##
## 0x0a [验证平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/submissions/)
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7] 则为true
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4] 则为false
```cpp
bool isBalanced(TreeNode* root) {
int h = 0;//树的高度
return dfs(root,h);
}
bool dfs(TreeNode* p, int &h){//求出以p为根的树的高度并返回是否平衡
if(!p) return true;
int hl = 0, hr = 0;//求出左右子树的高度
bool lbal = dfs(p->left,hl);
bool rbal = dfs(p->right,hr);
h = max(hl,hr)+1;//以p为根的树的高度
return lbal && rbal && abs(hl-hr)<=1;//左右均平衡且高度差<=1
}
```
##
## 0x0b [n皇后](https://leetcode-cn.com/problems/n-queens-ii/)
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。(攻击范围为所在的行、列、正反对角线上)。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
```cpp
int n,ans;//n皇后
void dfs(int u, auto &col,auto &gd, auto &rgd){
if(u==n){//搜索完毕
ans++;
return;
}
for(int j = 0; j < n; j++){//枚举u行放在j列时
if(!col[j]&&!gd[j-u+n]&&!rgd[u+j]){//列,对角,反对角不冲突时
col[j] = gd[j-u+n] = rgd[u+j] = 1;//占用
dfs(u+1,col,gd,rgd);//进入下一行搜索
col[j] = gd[j-u+n] = rgd[u+j] = 0;//恢复现场
}
}
}
int totalNQueens(int len) {
n = len;
vector<bool> col(n),gd(2*n),rgd(2*n);//列 对角线 反对角线
dfs(0,col,gd,rgd);//从第0行开始搜索
return ans;
}
```
##
## 0x0c [迷宫问题](https://www.acwing.com/problem/content/1078/)
给定一个 n×n 的二维数组，如下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
对于上图则输出如下路径：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
PII pre[N][N];//保存搜狗所过程中上一步的坐标
bool g[N][N];
int n;
void bfs(PII start){
int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};//四个方向
queue<PII> q;
q.push(start);
memset(pre,-1,sizeof pre);//为-1表示此处还没搜过
pre[n-1][n-1] = {n-1,n-1};
while(q.size()){
PII t = q.front();//当前位置
q.pop();
int tx = t.first, ty = t.second;
for(int i = 0; i < 4; i++){//向四个方向探索下一步
int x = tx + dx[i], y = ty + dy[i];
if(x<0||x>=n||y<0||y>=n||g[x][y]||pre[x][y].first!=-1) continue;
q.push({x,y}),pre[x][y] = {tx,ty};//保存该步信息
}
}
PII end({0,0});
while(true){
int x = end.first, y = end.second;
printf("%d %d\n",x,y);
if(x==n-1&&y==n-1) break;
end = pre[x][y];
}
}
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) scanf("%d",&g[i][j]);
PII end({n-1,n-1});
bfs(end);//逆着搜(从终点向起点搜) 方便输出路径
return 0;
}
```
##
## 0x0d [树的重心](https://www.acwing.com/problem/content/848/)
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输出一个整数，表示删除重心后,所有的子树中最大的子树的结点数目。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N*2;//因为是无向图 需要存双向边
int h[N],e[M],ne[M],idx;//邻接表
int n;
bool st[N];
void add(int a, int b){//插入一条边a->b
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int ans = 0x3f3f3f3f;//
int dfs(int u){//返回以u为根的树的大小
st[u] = 1;
int sum = 1,res = 0;//sum-以u为根的子树大小 res-删除u后的连通块内点的个数最大值
for(int i = h[u]; i != -1; i = ne[i]){//遍历u的所有邻接点
int j = e[i];//对于u->j这条边
if(!st[j]){
int subs = dfs(j);//获得以j为根的子树大小
res = max(res, subs);
sum += subs;
}
}
res = max(n-sum,res);//求出删除u后的最大连通块内节点个数
ans = min(ans,res);//结果值
return sum;
}
int main(){
cin>>n;
memset(h,-1,sizeof h);
for(int i = 0 ,a,b; i < n-1; i++){
cin>>a>>b;
add(a,b),add(b,a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}
```
# 五、图
##
## 0x00 [有向图的拓扑排序](https://www.acwing.com/problem/content/850/)
给定一个n个点m条边的有向图，请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入样例：
3 3（指3个点3条边）
1 2
2 3
1 3
输出样例：
1 2 3
##### 版本一:bfs 不断删除入度为0的点
```cpp
bool topsort(){
int hh = 0, tt = -1;
for(int i = 1; i <= n; i++){//将所有入度为0的入队
if(!ind[i]) q[++tt] = i;//ind[i]表示节点i的入度
}
while(hh<=tt){
int t = q[hh++];
for(int i = h[t]; i!=-1; i = ne[i]){
int j = e[i];
ind[j]--;
if(ind[j]==0) q[++tt] = j;
}
}
return tt==n-1;//如果节点全部入队 说明无环
//若返回true,则可输出拓扑序列，即入队顺序
//for(int i = 0; i < n; i++) cout<<q[i]<<" ";
}
```
##### 版本二:dfs 利用dfs序 按dfs序从大到小输出点
```cpp
int dfstime = 0;//dfs序(即dfs过程中 搜索结束的时间)
vector<pair<int,int> > ans;
int st[N];// -1 表示搜索完毕 1表示该轮dfs还没结束
bool dfs(int u){//给出dfs序以及返回是否有环
if(st[u]==-1) return false;//对于已经搜索完毕了点 无需搜
if(st[u]==1) return true;//因为该点在当前轮搜到过 而现在又来了 第二次到达 说明存在环
st[u] = 1;//当前轮开始访问
dfstime++;//时间+1 到达u
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(dfs(j)) return true;//邻接点存在环
}
st[u] = -1;//以u为起点的dfs访问完毕
ans.push_back({-dfstime,u});//记录该点的退出时间(dfs序) 变为负数 方便从大到小排序
return false;//不存在环
}
bool topsort_dfs(){
for(int i = 1; i <= n; i++){
if(st[i]!=-1){
if(dfs(i)) return false;//发现该连通分量有环 拓扑失败
}
}
sort(ans.begin(),ans.end());
for(auto v : ans){
cout<<v.second<<" ";
}
return true;
}
```
##
## 0x01 [Dijkstra求最短路](https://www.acwing.com/problem/content/851/)
给定一个n个点m条边的有向图, 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
```cpp
int g[N][N];//邻接矩阵
int d[N];//距离数组
bool st[N];//标记数组
int n,m;
int dijkstra(){
memset(d,0x3f,sizeof d);//初始时每个点到起点距离为无穷
d[1] = 0;//1为起点
for(int i = 0; i < n; i++){
int t = -1;//最小值点
for(int j = 1; j <= n; j++){//寻找未加入最短路的距离最小的点(此处可用堆优化找最小值)
if(!st[j]&&(t==-1||d[t]>d[j])) t = j;
}
st[t] = true;
for(int j = 1; j <= n; j++){//用新加入的点更新其它点
if(!st[j]&&d[j] > d[t] + g[t][j]) d[j] = d[t]+g[t][j];
}
}
if(d[n] == 0x3f3f3f3f) return -1;
else return d[n];
}
```
##
## 0x02 最小生成树
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。输出最小生成树的权重之和
##### 版本一: [prim算法](https://www.acwing.com/activity/content/problem/content/924/1/)
```cpp
const int INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
int d[N];//每个点距离生成树的距离
bool st[N];
int prim(){
memset(d,0x3f,sizeof d);
int res = 0;//最小生成树的权重之和
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 1; j <= n; j++)
if(!st[j]&&(t==-1||d[t] > d[j])) t = j;
if(i&&d[t]==INF) return -1;//说明不联通,则不存在
st[t] = true;
if(i) res += d[t];//纳入该边权重，除了起点
for(int j = 1; j <= n; j++){
if(!st[j]&&d[j] > g[t][j]) d[j] = g[t][j];
}
}
return res;
}
```
##### 版本二: [Kruskal算法求最小生成树](https://www.acwing.com/problem/content/861/)
```cpp
struct Edge{//边集
int a,b,w;
bool operator < (const Edge &E) const{//按权重从小到大排序
return w < E.w;
}
}e[N];
int n,m;
int p[N/2];//并查集数组 若p[i]=j 则表示i的父节点为j
int find(int x){//并查集 寻找x的根
if(x!=p[x]) p[x] = find(p[x]);//路径压缩版
return p[x];
}
int kruskal(){
sort(e,e+m);//把边按权重从小到大排序
int res = 0,cnt = 0;//最小生成树的权重之和，选择的边数
for(int i = 1; i <= n; i++) p[i] = i;//并查集初始化
for(int i = 0; i < m; i++){//从小到大选边
int x = find(e[i].a), y = find(e[i].b);
if(x!=y){//若该条边不构成回路 则加入
p[x] = y;
cnt++;
res += e[i].w;//纳入该边
}
}
return cnt==n-1 ? res:0x3f3f3f3f;//最终要选够n-1条边
}
```
##
## 0x03 [floyd求最短路](https://www.acwing.com/problem/content/856/)
即求出所有点对的最短距离
```cpp
int d[N][N];//任意两点间的最短距离
int n,m;
void floyd(){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j= 1; j <= n; j++){
d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
}
}
}
}
```
# 六、查找
##
## 0x00 [kmp字符串](https://www.acwing.com/problem/content/833/)
给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入样例：
3
aba(模板串P)
5
ababa(模式串S)
输出样例：
0 2(输出P在S中出现的起始下标)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = 100010;
char p[N], s[M];
int n,m;
int ne[N];//next数组 匹配失败时 模板串回退的位置
int main(){
cin>>n>>p+1>>m>>s+1;//让下标从1开始
for(int i = 2, j = 0; i <= n; i++){//求出next数组
while(j&&p[j+1]!=p[i]) j = ne[j];//匹配j+1和i,若当前不匹配时 回退寻找匹配的位置
if(p[j+1] == p[i]) j++;//匹配 往前移动
ne[i] = j;//如果起点就不匹配 就是零 否则 就是当前匹配了的长度
}
for(int i = 1, j = 0; i <= m; i++){//匹配过程
while(j&&p[j+1]!=s[i]) j = ne[j];
if(p[j+1]==s[i]) j++;
if(j==n){
cout<<i - n<<" ";//匹配成功 输出下标
j = ne[j];//为继续匹配，在成功为强行失败即可
}
}
return 0;
}
```
##
## 0x01[最短回文串](https://leetcode-cn.com/problems/shortest-palindrome/)
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:
输入: "abcd"
输出: "dcbabcd"
```cpp
/*思路 如对于串 abcd 想要将其变为回文串
那么先把它逆序 然后放在前面 自然是回文了
abcd
dcba
dcbaabcd ->是回文
但是我们发现根本没必要放这么多在前面 因为abcd的前缀和dcab的后缀有重合(如a) 所以为了只添加最少 的字符,我们在前方只需要添加不重复的即可
abcd
dcba
dcbabcd ->依然是回文
//为了添加的最少 我们就需要找到dcba的后缀和abcd的前缀重合的部分，且让重合部分最大即可
//故而联想到kmp算法，它的next数组就是用来求一个串的前缀和后缀相同的长度的最大值
//所以拼接起字符串 abcddcba 但是我们所求的前缀是不能超过中点的，因此用一个特殊字符隔开
// 即为 abcd#dcba 这样在匹配前后缀时，相同长度就一定不会超过#号了
// 这样问题就转化为了 求abcd#dcba的next数组 知道该串的最长前后缀相同时的最大长度为1
a a 前后缀相同的最大长度
所以把后半部分除去重叠的部分拼接到前半部分即可
答案就是 dcbabcd
大功告成!
*/
string shortestPalindrome(string s) {
string revs = s;
int tn = s.size();//终点处,#前面的位置
reverse(revs.begin(),revs.end());
s = ' '+ s + '#' + revs;//让下标从1开始
int n = s.size()-1;//实际长度
vector<int> ne(n+1);//next数组
for(int i = 2, j = 0; i <= n; i++){//求next数组
while(j&&s[i]!=s[j+1]) j = ne[j];
if(s[i]==s[j+1]) j++;
ne[i] = j;
}
return s.substr(tn+2,tn-ne[n])+s.substr(1,tn);//后半部分除去重叠后缀+前半部分
}
```
# 七、排序
##
## 0x00 [直接插入排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
给定一个整数数组 nums，将该数组升序排列。
以第一个元素作为有序数组，其后的元素通过在这个已有序的数组中找到合适的位置并插入
空间：O(1)
最好：O(n)，初始为有序时
最坏：O(n^2) ，初始为是逆序时
平均：O(n^2)
稳定性：是
```cpp
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
for(int i = 1,j; i < n; i++){//此时0~i-1已有序
int v = nums[i];//i位置元素待插入
for(j = i-1; j>=0&&v<nums[j]; j--){//向前寻找插入位置
nums[j+1]=nums[j];
}
nums[j+1] = v;//插入
}
return nums;
}
```
##
## 0x01 [折半插入排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
给定一个整数数组 nums，将该数组升序排列。
与直接插入排序的唯一区别就是 查找插入位置时 使用二分，复杂度不变
```cpp
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
for(int i = 1; i < n; i++){//此时0~i-1已有序
int v = nums[i];//i位置元素待插入
int l = 0, r = i-1;//二分查找插入位置
while(l<r){
int mid = l+r+1 >> 1;
if(nums[mid]<=v) l = mid;
else r = mid-1;
}
if(nums[l]>v) l--;//防止在单个元素中二分的情况
//此时的l即为插入位置的前一个位置
for(int j = i-1; j > l; j--) nums[j+1] = nums[j];//后移
nums[l+1] = v;//插入
}
return nums;
}
```
##
## 0x02 [希尔排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
给定一个整数数组 nums，将该数组升序排列。
类插入排序，只是向前移动的步数变成d，插入排序每次都只是向前移动1。
空间：O(1)
平均：当n在特定范围时为 O(n^1.3)
稳定性：否
```cpp
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
for (int d = n / 2; d >= 1; d /= 2) {//d为增量 d=1时就是0x00的插入排序
for (int i = d,j; i < n; i++) {
int v = nums[i];//i位置元素待插入
for (j = i-d; j >= 0 && v < nums[j]; j -= d) {//以增量d向前寻找插入位置
nums[j+d] = nums[j];
}
nums[j+d] = v;
}
}
return nums;
}
```
##
## 0x03 [冒泡排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
给定一个整数数组 nums，将该数组升序排列。
通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的最大值
空间：O(1)
最好：O(n)，初始即有序时 一趟冒泡即可
最坏：O(n^2)， 初始为逆序时
平均：O(n^2)
稳定性：是
```cpp
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
bool sorted = false;//无序
for(int i = n-1; i >=0 && !sorted; i--){//0~i为无序区
sorted = true;//假定已有序
for(int j = 0; j < i; j++){//相邻比较 大的沉底
if(nums[j]>nums[j+1]) swap(nums[j],nums[j+1]),sorted = false;//发生交换 则无序
}
}
return nums;
}
```
##
## 0x04 [快速排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
给定一个整数数组 nums，将该数组升序排列。
选择一个元素作为基数（通常是第一个元素），把比基数小的元素放到它左边，比基数大的元素放到它右边（相当于二分），再不断递归基数左右两边的序列。
空间：O(log n)，即递归栈深度
最好：O(nlog n) ，其他的数均匀分布在基数的两边，此时的递归就是不断地二分左右序列。
最坏：O(n^2) ，其他的数都分布在基数的一边，此时要划分n次了，每次O(n)
平均：O(nlog n)
稳定性：否
```cpp
void quick_sort(vector<int>& nums, int l , int r){//对下标为 l~r部分 排序
if(l >= r ) return ;
int x = nums[l], i = l-1, j = r+1;//x为划分中枢 i为左半起点 j为右半起点
while(i < j){
while(nums[++i] < x);//左边寻大于x的数
while(nums[--j] > x);//右边寻小于x的数
if(i < j) swap(nums[i],nums[j]);//每次把左边大于x的数和右边小于x的交换即可
}
quick_sort(nums,l,j),quick_sort(nums,j+1,r);
//因为结束时i在j的右边 j是左半段的终点,i是右半段的起点
}
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
quick_sort(nums,0,n-1);
return nums;
}
```
##
## 0x05 [快排应用-第k大数](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/submissions/)
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
```cpp
int quick_select(vector<int>& nums, int l , int r, int k){
//在下标为l~r的数中求第k大的数
if(l >= r) return nums[l];
int x = nums[l], i = l-1, j = r+1;
while(i < j){//以x为枢纽 一次快排划分 此处大的在左边 小的在右边
while(nums[++i] > x);
while(nums[--j] < x);
if(i < j) swap(nums[i],nums[j]);
}
int sl = j-l+1;//左半区间的长度
if(sl>=k) return quick_select(nums, l,j,k);
//k<=左半区间长度,则第k大数必然在左半段 并且是左半段的第k大数
else return quick_select(nums, j+1, r, k - sl);
//第k大数必然在右半段 并且是右半段的第k-sl大数
}
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
return quick_select(nums,0,n-1,k);
}
```
##
## 0x06 [选择排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
给定一个整数数组 nums，将该数组升序排列。
和冒泡排序相似，区别在于选择排序是直接挑出未排序元素的最大值放后面，其它元素不动。无论如何都要O(n^2)
最好：O(n^2)
最坏：O(n^2)
平均：O(n^2)
稳定性：否
```cpp
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
for(int i = n-1; i >=0; i--){//0~i为无序部分
int minpos = -1;
for(int j = 0; j <= i; j++){//寻找0~i区间内的最大值的位置
if(minpos ==-1||nums[j]>nums[minpos]) minpos = j;
}
swap(nums[i],nums[minpos]);//把挑出最大值放到后面
}
return nums;
}
```
##
## 0x07 [堆排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数，表示整数数列。
输出格式
共一行，包含m个整数，表示整数数列中前m小的数。
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
根据数组建立一个堆（类似完全二叉树），每个结点的值都大于左右结点（大根堆，通常用于升序），或小于左右结点（小根堆堆，通常用于降序）。
空间：O(1)
最好：O(nlog n)，log n是调整小根堆所花的时间
最坏：O(nlog n)
平均：O(nlog n)
稳定性：否
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N];//堆
int n,m;
void down(int x){//小根堆 下调
int p = x*2;//左孩子下标
while(p <= n){
if(p + 1 <=n && h[p+1] < h[p]) p++;//找到子节点的最小值
if(h[x]<=h[p]) return;//调整完毕
swap(h[x],h[p]);
x = p;
p = x*2;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&h[i]);
for(int i = n/2; i >=1; i--) down(i);//建堆,从最后一个叶子的父节点开始调整即可
while(m--){
printf("%d ",h[1]);//堆顶即为最小值
swap(h[1],h[n]),n--,down(1);//删除堆顶
}
return 0;
}
```
##
## 0x08 [归并排序](https://www.acwing.com/problem/content/description/789/)
给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
递归将数组分为两个有序序列，再合并这两个序列
空间: O(n) 辅助备份数组
最好：O(nlog n)
最坏：O(nlog n)
平均：O(nlog n)
稳定性：是
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],t[N];//原数组 t为归并的辅助数组
void merge_sort(int l, int r){//将l~r从小到大排序
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(l,mid),merge_sort(mid+1,r);//左右部分别排好序
//合并左右两部分 ，k为待填充位置 每次选最小的去填
//i为左部分的起始下标 j为右部边的起始下标 mid为左部分的边界
for(int k = l,i = l, j = mid+1; k <= r; k++){
if(j > r||i <= mid&&a[i] <= a[j]) t[k] = a[i++];//选择左部分的值去填的条件
else t[k] = a[j++];//否则只能选右半部分了
}
for(int i = l; i <= r; i++) a[i] = t[i];
}
int main(){
int n;
scanf("%d",&n);
for(int i = 0; i < n; i++) scanf("%d",&a[i]);
merge_sort(0,n-1);
printf("%d",a[0]);
for(int i = 1; i < n; i++) printf(" %d",a[i]);
return 0;
}
```
##
## 0x09 [归并排序的应用-逆序对的数量](https://www.acwing.com/problem/content/790/)
给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
输入样例：
6
2 3 4 5 6 1
输出样例：
5
解释:逆序对分别为 (2,1)(3,1)(4,1)(5,1)(6,1)
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N],t[N];
LL ans;//逆序对数量
void merge_sort(int l, int r){//l~r从小到大排 排序过程中统计逆序对数量
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(l,mid),merge_sort(mid+1,r);
for(int k = l,i=l,j=mid+1; k <= r; k++){
if(j > r|| i<= mid&&a[i]<=a[j]) t[k] = a[i++];
else ans += mid-i+1LL,t[k] = a[j++];
//此时arr[i]>arr[j] 逆序 统计逆序对数量 则arr[i~mid]的元素均大于arr[j]构成逆序
}
for(int i = l; i <= r; i++) a[i] = t[i];
}
int main(){
int n;
scanf("%d",&n);
for(int i = 0; i < n; i++) scanf("%d",&a[i]);
merge_sort(0,n-1);
printf("%lld",ans);
return 0;
}
```
##
## 0x0a [基数排序](https://leetcode-cn.com/problems/sort-an-array/submissions/)
使用十个桶0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环最大值的位数次。
只能排列正整数，因为遇到负号和小数点无法进行比较。
空间：O(r) r个队列
最好：O(d(n+r)) d趟分配收集 一趟分配O(n)收集O(r)
最坏：O(d(n+r))
平均：O(d(n+r))
稳定性：是
```cpp
void radixSort(int arr[]) {
int _max = (*max_element(arr, arr+len));
// 计算最大值的位数
int maxDigits = 0;
while(_max) {
maxDigits++;
_max /= 10;
}
// 标记每个桶中存放的元素个数
int bucketSum[10];
memset(bucketSum, 0, sizeof(bucketSum));
int div = 1;
// 第一维表示位数即0-9，第二维表示里面存放的值
int res[10][1000];
while(maxDigits--) {
int digit;
// 根据数组元素的位数将其放到相应的桶里，即分配
for(int i=0; i<len; i++) {
digit = arr[i] / div % 10;
res[digit][bucketSum[digit]++] = arr[i];
}
// 把0-9桶里的数放回原数组后再进行下一个位数的计算，即收集
int index = 0;
for(int i=0; i<=9; i++) {
for(int t=0; t<bucketSum[i]; t++) {
arr[index++] = res[i][t];
}
}
memset(bucketSum, 0, sizeof(bucketSum));
div *= 10;
}
}
```
# 2020考研必胜！