数据结构与算法模板总结(一)
数据结构与算法模板总结(一)
一. 排序
快排
思想
① 确定分界点: q(l), q[(l+r)/2], q[r], 随机取;
② 调整区间：通过x划分为两段，第一个区间的值都小于等于x, 第二个区间的值都大于等于x；
③ 递归处理左右两端，因为左边的最大值要小于右边的最小值；
调整区间的方法：
-
简单方法实现
step1: 开两个空间: a[] , b[] ;
step2: 扫描q[l->r]: 将小于x的值放入a,将大于x的值放入b；
step3；将a和b的值放入原数组中;
-
经典方法实现
step1：定义两个指针I,j，让i和j分别向中间走;
step2: i先往中间走, 只要i指向的数<x,那么i向后移动一位,直到i指向的数是大于等于x的,i就停下;移动j, 同理，当遇到小于x的,j就停下；
step3: swap(I,j)，i和j都往前移动一位。
实现模板
public static void quickSort(int q[],int l,int r){
if(l>=r) return;
int x = q[l],i=l-1,j=r+1;
while(i<j){
do{
i++;
}while(q[i]<x);
do{
j--;
}while(q[j]>x);
if(i<j){
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quickSort(q,l,j);
quickSort(q,j+1,r);
}
「注意：」
-
如果要改为从大到小，把 q[i]<x改为q[i]>x,q[j]>x改为q[j]<x即可; -
当递归的界限取j时,分界点不能取最右边的r,会有界限问题。默写时最好按照l,j这样进行默写。
题目链接：https://www.acwing.com/problem/content/787/
归并排序
思想
快排是用数来分，归并是以中间点为分界线。
① 确定分界点mid;
② 递归排序左边和右边；
③ 归并: 将两个有序数组合并为一个；
实现模板
public static void mergeSort(int[] q,int l,int r){
if(l>=r) return;
int mid = (l+r)/2;
mergeSort(q,l,mid);
mergeSort(q,mid+1,r);
int[] tmp = new int[r-l+1];
int k=0,i=l,j=mid+1;
while(i<=mid && j<=r){
if(q[i]<=q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i<=mid) tmp[k++] = q[i++];
while(j<=r) tmp[k++] = q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i] = tmp[j];
}
题目链接：https://www.acwing.com/problem/content/789/
二. 二分查找
使用场景
当题目在一个区间内满足性质，在另一个区间内不满足性质时，可以考虑二分求解。
实现模板
模板一：
当满足红色区间内的性质时：
public static int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
模板二:
当满足绿色区间内的性质时：
public static int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = (l + r + 1)/2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
「重点：」 这里注意是(l+r+1)/2,因为如果r=l-1时,不加一的情况会向下取整,导致l会一直无限循环。
模板的使用方法
-
当遇到使用场景时,先写好如下框架:
int l=0,r=len-1;
while(l<r){
int mid = (l+r)/2;
if()
else
}
return l;
-
再根据判断满足的性质属于红色区间(左边)还是绿色区间(右边)来确定if的条件，从而再确定是哪个模板; -
根据模板看mid是 l+r还是l+r+1;
题目：数的范围
题目链接：https://www.acwing.com/problem/content/791/
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(),m=sc.nextInt();
int[] q = new int[n];
for(int i=0;i<n;i++){
q[i] = sc.nextInt();
}
while(m-- != 0){
int x = sc.nextInt();
int l=0,r=n-1;
while(l<r){
int mid = (l+r)/2;
if(q[mid]>=x) r=mid;
else l=mid+1;
}
if(q[l]!=x){
System.out.println("-1 -1");
}
else{
System.out.print(l+" ");
l=0;
r=n-1;
while(l<r){
int mid = (l+r+1)/2;
if(q[mid]<=x) l=mid;
else r=mid;
}
System.out.println(l+" ");
}
}
}
三. 双指针
使用场景
快排和归并其实都算是双指针，快排是两个指针指向一个序列，归并两个指针分别指向两个不同的序列。但是本节说的双指针着重解释的是「如何对双循环的情况进行优化的双指针」，如下：
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
}
}
实现模板
用一个指针i来遍历数组,指针j来对i之前的区间进行遍历并判断条件。
for(int i=0;i<n;i++){
while(j<i && check(i,j)) j++;
// 题目具体逻辑
}
题目一
输入一个字符串，然后把其中的每个单词输出出来，单词是空格隔开的。
让i指向单词的首字母，j指向单词的最后一个位置,遍历i到j输出单词。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int n = str.length();
for(int i=0;i<n;i++){
int j=i;
while(j<n && str.charAt(j)!=' ') j++;
for(int k=i;k<j;k++) System.out.print(str.charAt(k));
System.out.println();
i = j;
}
}
}
题目二：最长不含重复字符的子字符串
int[] s = new int[10000];
int res = 0;
for(int i=0,j=0;i<n;i++){
s[a[i]]++;
while(s[a[j]]>1){
s[a[j]]--;
j++;
}
res = max(res,i-j+1);
}
// 输出res