AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

基础算法技巧总结1(排序，二分，前缀和与差分，双指针，字符串)

2026-03-25 14
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文系统讲解排序、二分、前缀和与差分、双指针及字符串等核心算法，涵盖快速/归并/堆排序、整数/浮点二分、一维/二维前缀和与差分、多种双指针技巧（如滑动窗口、双数组遍历）及字符串处理（翻转、匹配、加密等），均附ACwing/LeetCode题目链接与C++/Java双语言实现。

 1.排序

1.1 快速排序

https://www.acwing.com/problem/content/787/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int arr[N];
void qSort(int arr[],int l,int r){
  if(l>=r) return;
  int x=arr[(l+r)>>1];
  int i=l-1,j=r+1;
  while(j>i){
    do{
      i++;
    } while(arr[i]<x);
    do{
      j--;
    } while(arr[j]>x);
    if(j>i){
      swap(arr[i],arr[j]);
    }
  }
  qSort(arr,l,j);
  qSort(arr,j+1,r);
  
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>arr[i];
  
  qSort(arr,1,n);
  for(int i=1;i<=n;i++) cout<<arr[i]<<" ";
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e6+10);
    public static int n;
    public static int []arr=new int[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        
        qSort(arr,1,n);
        for(int i=1;i<=n;i++){
            System.out.print(arr[i]+" ");
        }
        
    }
    private static void qSort(int[] arr, int l, int r) {
        if(l>=r) return;
        int x=arr[(l+r)>>1];
        int i=l-1,j=r+1;
        while (j>i){
            do{
                i++;
            }while (arr[i]<x);
            do{
                j--;
            }while (arr[j]>x);
            if(j>i){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        qSort(arr,l,j);
        qSort(arr,j+1,r);
        
    }
}

image.gif

1.2 归并排序

1.2.1 模板

https://www.acwing.com/problem/content/789/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int arr[N];
int res[N];
void mSort(int arr[],int l,int r){
  if(l>=r) return;
  int mid=(l+r)>>1;
  int i=l,j=mid+1;
  mSort(arr,i,mid);
  mSort(arr,j,r);
  int k=1;
  while(i<=mid && j<=r){
    if(arr[i]<=arr[j]){
      res[k++]=arr[i++];
    } else {
      res[k++]=arr[j++];
    }
  }
  while(i<=mid){
    res[k++]=arr[i++];
  }
  while(j<=r){
    res[k++]=arr[j++];
  }
  
  for(int i=l,j=1;i<=r;i++,j++){
    arr[i]=res[j];
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>arr[i];
  }
  mSort(arr,1,n);
  for(int i=1;i<=n;i++){
    cout<<arr[i]<<" ";
  }
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e6+10);
    public static int n;
    public static int []arr=new int[N];
    public static int []res=new int[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        mSort(arr,1,n);
        for(int i=1;i<=n;i++){
            System.out.print(arr[i]+" ");
        }
    }
    private static void mSort(int[] arr, int l, int r) {
        if(l>=r) return;
        int mid=(l+r)>>1;
        int i=l,j=mid+1;
        mSort(arr,i,mid);
        mSort(arr,j,r);
        int k=1;
        while (i<=mid && j<=r){
            if(arr[i]<=arr[j]){
                res[k++]=arr[i++];
            } else {
                res[k++]=arr[j++];
            }
        }
        while(i<=mid) res[k++]=arr[i++];
        while(j<=r) res[k++]=arr[j++];
        for(int a=l,b=1;a<=r;a++,b++){
            arr[a]=res[b];
        }
    }
}

image.gif

1.2.1 逆序对数量

https://www.acwing.com/problem/content/790/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
int arr[N];
int res[N];
ll cnt;
void mSort(int arr[],int l,int r){
  if(l>=r) return;
  int mid=(l+r)>>1;
  int i=l,j=mid+1;
  mSort(arr,i,mid);
  mSort(arr,j,r);
  int k=1;
  while(i<=mid && j<=r){
    if(arr[i]<=arr[j]){
      res[k++]=arr[i++];
    } else {
      cnt+=mid-i+1;
      res[k++]=arr[j++];
    }
  }
  while(i<=mid) res[k++]=arr[i++];
  while(j<=r) res[k++]=arr[j++];
  
  for(int i=l,j=1;i<=r;i++,j++){
    arr[i]=res[j];
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>arr[i];
  mSort(arr,1,n);
  cout<<cnt<<endl;
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N = (int) (1e6 + 10);
    public static int n;
    public static int[] arr = new int[N];
    public static int[] res = new int[N];
    public static long cnt;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        mSort(arr,1,n);
        System.out.println(cnt);
    }
    
    private static void mSort(int[] arr, int l, int r) {
        if(l>=r) return;
        int mid=(l+r)>>1;
        int i=l,j=mid+1;
        mSort(arr,i,mid);
        mSort(arr,j,r);
        int k=1;
        while (i<=mid && j<=r){
            if(arr[i]<=arr[j]){
                res[k++]=arr[i++];
            } else {
                cnt+=mid-i+1;
                res[k++]=arr[j++];
            }
        }
        while (i<=mid) res[k++]=arr[i++];
        while (j<=r) res[k++]=arr[j++];
        for(int a=l,b=1;a<=r;a++,b++){
            arr[a]=res[b];
        }
    }
    
}

image.gif

1.3 排序函数使用

1.3.1 奖学金

https://www.luogu.com.cn/problem/P1093

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=350;
struct Score{
  int chinese;
  int math;
  int english;
  int sum;
  int range;
};
Score arr[N];
int n;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0); 
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>arr[i].chinese>>arr[i].math>>arr[i].english;
    arr[i].sum+=arr[i].chinese+arr[i].math+arr[i].english;
    arr[i].range=i;
  }
  sort(arr+1,arr+n+1,[](const Score &a,const Score &b){
    if(a.sum!=b.sum){
      return a.sum>b.sum;
    } else {
      if(a.chinese!=b.chinese){
        return a.chinese>b.chinese;
      } else {
        return a.range<b.range;
      }
    }
  });
  for(int i=1;i<=5;i++){
    cout<<arr[i].range<<" "<<arr[i].sum<<endl;
  }
  
  
  return 0;
}

image.gif 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Node{
    int chinese;
    int math;
    int english;
    int sum;
    int range;
}
public class Main {
    public static final int N=350;
    public static int n;
    public static Node[] arr=new Node[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++){
            arr[i]=new Node();
            arr[i].chinese=sc.nextInt();
            arr[i].math=sc.nextInt();
            arr[i].english=sc.nextInt();
            arr[i].sum+=arr[i].chinese+arr[i].math+arr[i].english;
            arr[i].range=i;
        }
        Arrays.sort(arr, 1, n + 1, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.sum!=o2.sum){
                    return Integer.compare(o2.sum,o1.sum);
                } else {
                    if(o1.chinese!=o2.chinese){
                        return Integer.compare(o2.chinese,o1.chinese);
                    } else{
                        return Integer.compare(o1.range,o2.range);
                    }
                }
            }
        });
        for(int i=1;i<=5;i++){
            System.out.println(arr[i].range+" "+arr[i].sum);
        }
    }
}

image.gif

1.4 堆排序

1.4.1 小根堆排序

https://www.acwing.com/problem/content/840/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,cnt;
int heap[N];
void down(int u){
  int t=u;//三个节点中最小节点编号
  if(u*2<=cnt && heap[u*2]<heap[t]) t=u*2;
  if(u*2+1<=cnt && heap[u*2+1]<heap[t]) t=u*2+1;
  if(t!=u){
    swap(heap[t],heap[u]);
    down(t);
  }
}
int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>heap[i];
  cnt=n;
  for(int i=n/2;i>=1;i--) down(i);//最后一层占n/2无需down
  for(int i=1;i<=m;i++){
    cout<<heap[1]<<" ";
    //删堆顶
    heap[1]=heap[cnt];
    cnt--;
    down(1); 
  }
  
  return 0;
}

image.gif

 

1.4.2 大根堆排序

在前一题的基础上改为从大到小输出前m大的数

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,cnt;
int heap[N];
void down(int u){
  int t=u;//三节点中最大的编号
  if(u*2<=cnt && heap[u*2]>heap[t]) t=u*2;
  if(u*2+1<=cnt && heap[u*2+1]>heap[t]) t=u*2+1;
  if(t!=u){
    swap(heap[t],heap[u]);
    down(t);
  } 
}
int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>heap[i];
  cnt=n;
  for(int i=n/2;i>=1;i--) down(i);
  for(int i=1;i<=m;i++){
    cout<<heap[1]<<" ";
    //删除堆顶
    heap[1]=heap[cnt];
    cnt--;
    down(1); 
  } 
  
  return 0;
}

image.gif

1.4.3 STL与集合中的堆

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  //大根堆 (#include <queue>)
  priority_queue<int,vector<int>,less<int>> max_heap;
  max_heap.push(2);
  max_heap.push(4);
  max_heap.push(9);
  while(!max_heap.empty()){
    cout<<max_heap.top()<<" ";
    max_heap.pop();
  }
  cout<<endl;
  //小根堆 
  priority_queue<int,vector<int>,greater<int>> min_heap; 
  min_heap.push(2);
  min_heap.push(4);
  min_heap.push(9);
  while(!min_heap.empty()){
    cout<<min_heap.top()<<" ";
    min_heap.pop();
  }
  
  return 0;
}

image.gif 

import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
    public static void main(String[] args) {
        //小根堆（默认）
        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
        minHeap.offer(5);
        minHeap.offer(1);
        minHeap.offer(3);
        while (!minHeap.isEmpty()){
            System.out.println(minHeap.poll()+" ");
        }
        System.out.println();
        //大根堆
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(1);
        maxHeap.offer(3);
        while (!maxHeap.isEmpty()){
            System.out.println(maxHeap.poll()+" ");
        }
    }
}

image.gif

2.二分

2.1 整数二分模板

https://www.acwing.com/problem/content/791/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,q;
int arr[N];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>q;
  for(int i=1;i<=n;i++) cin>>arr[i];
  
  for(int i=1;i<=q;i++){
    int k;
    cin>>k;
    int l1=1,r1=n;
    while(r1>l1){
      int mid=(l1+r1)>>1;
      if(arr[mid]>=k){
        r1=mid;
      } else {
        l1=mid+1;
      }
    }
    
    if(arr[l1]!=k){
      cout<<"-1 -1"<<endl;
    } else {
      int l2=1,r2=n;
      while(r2>l2){
        int mid=(l2+r2+1)>>1;
        if(arr[mid]<=k){
          l2=mid;
        } else {
          r2=mid-1;
        }
      }
      cout<<(l1-1)<<" "<<(l2-1)<<endl;
    }
  
  }
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e6+10);
    public static int n,q;
    public static int[]arr=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        q=sc.nextInt();
        for(int i=1;i<=n;i++) {
            arr[i]=sc.nextInt();
        }
        for(int i=1;i<=q;i++){
            int k=sc.nextInt();
            int l1=1,r1=n;
            while(r1>l1){
                int mid=(l1+r1)>>1;
                if(arr[mid]>=k){
                    r1=mid;
                } else {
                    l1=mid+1;
                }
            }
            if(arr[l1]!=k){
                System.out.println("-1 -1");
            } else {
                int l2=1,r2=n;
                while(r2>l2){
                    int mid=(l2+r2+1)>>1;
                    if(arr[mid]<=k){
                        l2=mid;
                    } else {
                        r2=mid-1;
                    }
                }
                System.out.println((l1-1)+" "+(l2-1));
            }
        }
    }
}

image.gif

2.2 木材加工

https://www.luogu.com.cn/problem/P2440

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int len[N];
int fun(int x){
  int sum=0;
  for(int i=1;i<=n;i++){
    sum+=len[i]/x;
  }
  return sum;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0); 
  cin>>n>>k;
  int r=0;
  for(int i=1;i<=n;i++){
    cin>>len[i];
    r=max(r,len[i]);  
  }
  int l=0;
  while(r>l){
    int mid=(l+r+1)>>1;
    if(fun(mid)>=k){
      l=mid;
    } else {
      r=mid-1;
    }
  }
  cout<<l<<endl; 
  
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int n,k;
    public static int []len=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        k=sc.nextInt();
        int r=-1;
        for(int i=1;i<=n;i++){
            len[i]=sc.nextInt();
            r=Math.max(r,len[i]);
        }
        int l=0;
        while(r>l){
            int mid=(l+r+1)>>1;
            if(fun(mid)>=k){
                l=mid;
            } else {
                r=mid-1;
            }
        }
        System.out.println(l);
    }
    private static int fun(int x) {
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=len[i]/x;
        }
        return sum;
    }
}

image.gif

2.3 分巧克力

https://www.luogu.com.cn/problem/P8647

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int h[N];
int w[N];
int fun(int x){
  int sum=0;
  for(int i=1;i<=n;i++){
    int a=h[i]/x;
    int b=w[i]/x;
    sum+=a*b; 
  }
  return sum;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0); 
  cin>>n>>k;
  int r=0;
  for(int i=1;i<=n;i++){
    cin>>h[i]>>w[i];
    r=max(r,h[i]);
    r=max(r,w[i]);
  }
  int l=0;
  while(r>l){
    int mid=(l+r+1)>>1;
    if(fun(mid)>=k){
      l=mid;
    } else{
      r=mid-1;
    }
  }
  
  cout<<l<<endl;
   
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int []h=new int[N];
    public static int []w=new int[N];
    public static int n,k;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        k=sc.nextInt();
        int r=-1;
        for(int i=1;i<=n;i++){
            h[i]=sc.nextInt();
            w[i]=sc.nextInt();
            r=Math.max(r,h[i]);
            r=Math.max(r,w[i]);
        }
        int l=1;
        while (r>l){
            int mid=(l+r+1)>>1;
            if(fun(mid)>=k){
                l=mid;
            } else {
                r=mid-1;
            }
        }
        System.out.println(l);
    }
    private static int fun(int x) {
        int sum=0;
        for(int i=1;i<=n;i++){
            int a=h[i]/x;
            int b=w[i]/x;
            sum+=a*b;
        }
        return sum;
    }
}

image.gif

2.4 烦恼的高考志愿

https://www.luogu.com.cn/problem/P1678

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int m,n;
int arr[N];
ll sum;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0); 
  cin>>m>>n;
  for(int i=1;i<=m;i++) cin>>arr[i];
  sort(arr+1,arr+m+1);
  for(int i=1;i<=n;i++){
    int b;
    cin>>b;
    int l=1,r=m;
    while(r>l){
      int mid=(l+r+1)>>1;
      if(arr[mid]<=b){
        l=mid;
      } else{
        r=mid-1;
      }
    }
    int ac=abs(arr[l]-b);
    if(l!=1) ac=min(ac,abs(arr[l-1]-b));
    if(r!=m) ac=min(ac,abs(arr[r+1]-b));
    
    sum+=ac;
  }
  cout<<sum<<endl;
  
  
  return 0;
}

image.gif 

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int n,m;
    public static int[]arr=new int[N];
    public static long res;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m=sc.nextInt();
        n=sc.nextInt();
        for(int i=1;i<=m;i++){
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr,1,m+1);
        for(int i=1;i<=n;i++){
            int b=sc.nextInt();
            int l=1,r=m;
            while (r>l){
                int mid=(l+r+1)>>1;
                if(arr[mid]<=b){
                    l=mid;
                } else {
                    r=mid-1;
                }
            }
            int diff=Math.abs(arr[l]-b);
            if(l!=1) diff=Math.min(diff,Math.abs(arr[l-1]-b));
            if(l!=m) diff=Math.min(diff,Math.abs(arr[l+1]-b));
            res+=diff;
        }
        System.out.println(res);
    }
}

image.gif

2.5 冶炼金属

https://www.acwing.com/problem/content/description/4959/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n;
int arr[N],brr[N];
bool fun1(int x){
  for(int i=1;i<=n;i++){
    if(arr[i]/(brr[i]+1)>=x){
      return false;
    } 
  }
  return true;
}
bool fun2(int x){
  for(int i=1;i<=n;i++){
    if(arr[i]/brr[i]<x){
      return false;
    }
  }
  return true;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0); 
  cin>>n;
  int m=-1;
  for(int i=1;i<=n;i++){
    cin>>arr[i]>>brr[i];
    m=max(m,arr[i]);
  } 
  
  int l1=0,r1=m;
  while(r1>l1){
    int mid=(l1+r1)>>1;
    if(fun1(mid)){
      r1=mid;
    } else {
      l1=mid+1;
    }
  }
  int l2=0,r2=m;
  while(r2>l2){
    int mid=(l2+r2+1)>>1;
    if(fun2(mid)){
      l2=mid;
    } else{
      r2=mid-1;
    }
  }
  cout<<l1<<" "<<l2<<endl;
  
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e4+10);
    public static int n;
    public static int []arr=new int[N];
    public static int []brr=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        int r=-1;
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
            brr[i]=sc.nextInt();
            r=Math.max(r,arr[i]);
        }
        int l1=0,r1=r;
        while(r1>l1){
            int mid=(l1+r1)>>1;
            if(fun1(mid)){
                r1=mid;
            } else {
                l1=mid+1;
            }
        }
        int l2=0,r2=r;
        while(r2>l2){
            int mid=(l2+r2+1)>>1;
            if(fun2(mid)){
                l2=mid;
            } else {
                r2=mid-1;
            }
        }
        System.out.println(l1+" "+l2);
    }
    private static boolean fun2(int x) {
        for(int i=1;i<=n;i++){
            if(x>arr[i]/brr[i]){
                return false;
            }
        }
        return true;
    }
    private static boolean fun1(int x) {
        for(int i=1;i<=n;i++){
            if(x<=arr[i]/(brr[i]+1)){
                return false;
            }
        }
        return true;
    }
}

image.gif

2.6 数的三次方根(浮点二分)

https://www.acwing.com/problem/content/792/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
double n;
int main()
{
  scanf("%lf",&n);
  double l=-10000,r=10000;
  while(r-l>1e-8){
    double mid=(l+r)/2;
    if(mid*mid*mid>=n){
      r=mid;
    } else {
      l=mid;
    }
  }
  printf("%.6lf",l); 
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static double n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextDouble();
        double l=-10000.0,r=10000.0;
        while(r-l>1e-8){
            double mid=(l+r)/2;
            if(mid*mid*mid>=n){
                r=mid;
            } else {
                l=mid;
            }
        }
        System.out.printf("%.6f",l);
    }
}

image.gif

2.7 剪绳子(浮点二分)

https://www.acwing.com/problem/content/682/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int len[N];
int fun(double x){
  int sum=0;
  for(int i=1;i<=n;i++){
    int cnt=len[i]*1.0/x;
    sum+=cnt;
  }
  return sum;
}
int main()
{
  scanf("%d%d",&n,&m);
  double r=0.0;
  for(int i=1;i<=n;i++) {
    scanf("%d",&len[i]);  
    r=max(r,len[i]*1.0);
  }
  
  double l=0.0;
  while(r-l>1e-4){
    double mid=(l+r)/2;
    if(fun(mid)>=m){
      l=mid;
    } else {
      r=mid;
    }
  }
  printf("%.2lf",l);
  
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e6+10);
    public static int n,m;
    public static int[]len=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        double r=0.0;
        for(int i=1;i<=n;i++){
            len[i]=sc.nextInt();
            r=Math.max(r,len[i]*1.0);
        }
        double l=0.0;
        while(r-l>1e-4){
            double mid=(l+r)/2;
            if(fun(mid)>=m){
                l=mid;
            } else {
                r=mid;
            }
        }
        System.out.printf("%.2f",l);
    }
    private static int fun(double x) {
        int sum=0;
        for(int i=1;i<=n;i++){
            double ac=len[i]*1.0/x;
            sum+=ac;
        }
        return sum;
    }
}

image.gif

3.前缀和与差分

3.1 一维前缀和

https://www.acwing.com/problem/content/797/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int arr[N];
int preSum[N]; 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>arr[i];
  
  for(int i=1;i<=n;i++) preSum[i]=preSum[i-1]+arr[i];
  
  for(int i=1;i<=m;i++){
    int l,r;
    cin>>l>>r;
    cout<<preSum[r]-preSum[l-1]<<endl;
  }
    
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e6+10);
    public static int n,m;
    public static int []arr=new int[N];
    public static int[] preSum=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        for(int i=1;i<=n;i++){
            preSum[i]=preSum[i-1]+arr[i];
        }
        
        for(int i=1;i<=m;i++){
            int l=sc.nextInt();
            int r=sc.nextInt();
            System.out.println(preSum[r]-preSum[l-1]);
        }
        
    }
}

image.gif

3.2 一维差分

https://www.acwing.com/problem/content/799/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int arr[N];
int diff[N];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>arr[i];
  for(int i=1;i<=n;i++) diff[i]=arr[i]-arr[i-1];
  
  for(int i=1;i<=m;i++){
    int l,r,c;
    cin>>l>>r>>c; 
    diff[l]+=c;
    diff[r+1]-=c;
  }
  for(int i=1;i<=n;i++) arr[i]=arr[i-1]+diff[i];
  for(int i=1;i<=n;i++) cout<<arr[i]<<" "; 
    
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e6+10);
    public static int n,m;
    public static int []arr=new int[N];
    public static int[] diff=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        for(int i=1;i<=n;i++){
            diff[i]=arr[i]-arr[i-1];
        }
        for(int i=1;i<=m;i++){
            int l=sc.nextInt();
            int r=sc.nextInt();
            int c=sc.nextInt();
            diff[l]+=c;
            diff[r+1]-=c;
        }
        for(int i=1;i<=n;i++){
            arr[i]=arr[i-1]+diff[i];
        }
        for(int i=1;i<=n;i++){
            System.out.print(arr[i]+" ");
        }
        
    }
}

image.gif

3.3 二维前缀和

https://www.acwing.com/problem/content/798/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int n,m,q;
int arr[N][N];
int preSum[N][N];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m>>q;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>arr[i][j];
    }
  }
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+arr[i][j];
    }
  } 
  
  for(int i=1;i<=q;i++){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    cout<<preSum[x2][y2]-preSum[x2][y1-1]-preSum[x1-1][y2]+preSum[x1-1][y1-1]<<endl;
  }
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N=1010;
    public static int n,m,q;
    public static int [][]arr=new int[N][N];
    public static int [][]preSum=new int[N][N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        q=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+arr[i][j];
            }
        }
        for(int i=1;i<=q;i++){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            System.out.println(preSum[x2][y2]-preSum[x2][y1-1]-preSum[x1-1][y2]+preSum[x1-1][y1-1]);
        }
    }
}

image.gif

3.4 二维差分

https://www.acwing.com/problem/content/800/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int n,m,q;
int arr[N][N];
int brr[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
  brr[x1][y1]+=c;
  brr[x1][y2+1]-=c;
  brr[x2+1][y1]-=c;
  brr[x2+1][y2+1]+=c;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m>>q;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>arr[i][j];
      insert(i,j,i,j,arr[i][j]);
    }
  }
  
  for(int i=1;i<=q;i++){
    int x1,y1,x2,y2,c;
    cin>>x1>>y1>>x2>>y2>>c;
    insert(x1,y1,x2,y2,c);
  }
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      brr[i][j]+=brr[i-1][j]+brr[i][j-1]-brr[i-1][j-1];
    }
  }
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cout<<brr[i][j]<<" ";
    }
    cout<<endl;
  }
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N=1010;
    public static int n,m,q;
    public static int [][]arr;
    public static int [][]brr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        q=sc.nextInt();
        arr=new int[n+10][m+10];//直接在全局初始化new数组好像会超时
        brr=new int[n+10][m+10];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                arr[i][j]=sc.nextInt();
                insert(i,j,i,j,arr[i][j]);
            }
        }
        for(int i=1;i<=q;i++){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            int c=sc.nextInt();
            insert(x1,y1,x2,y2,c);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                brr[i][j]+=brr[i-1][j]+brr[i][j-1]-brr[i-1][j-1];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                System.out.print(brr[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void insert(int x1,int y1,int x2,int y2,int c){
        brr[x1][y1]+=c;
        brr[x2+1][y1]-=c;
        brr[x1][y2+1]-=c;
        brr[x2+1][y2+1]+=c;
    }
}

image.gif

4.双指针与字符串

4.1 最长连续不重复子序列

https://www.acwing.com/problem/content/801/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int arr[N];
int cnt[N];
int res;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>arr[i];
  
  int j=1;
  for(int i=1;i<=n;i++){
    cnt[arr[i]]++;
    while(j<i && cnt[arr[i]]>=2){
      cnt[arr[j]]--;
      j++;
    }
    res=max(res,i-j+1);
  }
  cout<<res<<endl;
  
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static final int N= (int) (1e5+10);
    public static int n,res;
    public static int[]arr;
    public static int[]cnt=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        arr=new int[n+10];
        for(int i=1;i<=n;i++) arr[i]=sc.nextInt();
        int j=1;
        for(int i=1;i<=n;i++){
            cnt[arr[i]]++;
            while(j<i && cnt[arr[i]]>=2){
                cnt[arr[j]]--;
                j++;
            }
            res=Math.max(res,i-j+1);
        }
        System.out.println(res);
    }
}

image.gif

4.2 数组元素的目标和

https://www.acwing.com/problem/content/802/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x;
int arr[N];
int brr[N];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m>>x;
  for(int i=1;i<=n;i++) cin>>arr[i];
  for(int i=1;i<=m;i++) cin>>brr[i];
  
  int j=m;
  for(int i=1;i<=n;i++){
    while(j>=1 && arr[i]+brr[j]>x){
      j--;
    }
    if(arr[i]+brr[j]==x){
      cout<<(i-1)<<" "<<(j-1)<<endl; 
      return 0;
    }
  }
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static int n,m,x;
    public static int[]arr;
    public static int[]brr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        x=sc.nextInt();
        arr=new int[n+10];
        brr=new int[m+10];
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        for(int i=1;i<=m;i++){
            brr[i]=sc.nextInt();
        }
        int j=m;
        for(int i=1;i<=n;i++){
            while (j>=1 && arr[i]+brr[j]>x){
                j--;
            }
            if(arr[i]+brr[j]==x){
                System.out.println((i-1)+" "+(j-1));
                return;
            }
        }
    }
}

image.gif

4.3 判断子序列

https://www.acwing.com/problem/content/2818/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int arr[N];
int brr[N];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>arr[i];
  for(int i=1;i<=m;i++) cin>>brr[i];
  
  int j=1;
  for(int i=1;i<=m;i++){
    if(j<=n && arr[j]==brr[i]){
      j++;
    }
  }
  if(j==n+1) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  
  return 0;
}

image.gif 

import java.util.Scanner;
public class Main {
    public static int n,m;
    public static int[]arr;
    public static int[]brr;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        arr=new int[n+10];
        brr=new int[m+10];
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        for(int i=1;i<=m;i++){
            brr[i]=sc.nextInt();
        }
        int j=1;
        for(int i=1;i<=m;i++){
            if(j<=n && arr[j]==brr[i]){
                j++;
            }
        }
        if(j==n+1) System.out.println("Yes");
        else System.out.println("No");
    }
}

image.gif

4.4 移动0

代码实现（C++/Java）

283. 移动零 - 力扣（LeetCode）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        int j=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=0){
                nums[j]=nums[i];
                j++;
            }
        }
        for(int i=j;i<n;i++){
            nums[i]=0;
        }
    }
};

image.gif

4.5 有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size();
        vector<int> res(n,-1);
        int l=0,r=n-1;
        int k=n-1;
        while(r>=l){
            if(nums[l]*nums[l]<=nums[r]*nums[r]){
                res[k]=nums[r]*nums[r];
                k--;
                r--;
            } else {
                res[k]=nums[l]*nums[l];
                k--;
                l++;
            }
        }
        return res;
    }
};

image.gif

4.6 螺旋矩阵Ⅱ

59. 螺旋矩阵 II - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));;
        int l=0,r=n-1,t=0,b=n-1;
        int cnt=1;
        while(r>=l && b>=t){
            for(int i=l;i<=r;i++){
                res[t][i]=cnt;
                cnt++;
            }
            t++;
            for(int i=t;i<=b;i++){
                res[i][r]=cnt;
                cnt++;
            }
            r--;
            for(int i=r;i>=l;i--){
                res[b][i]=cnt;
                cnt++;
            }
            b--;
            for(int i=b;i>=t;i--){
                res[i][l]=cnt;
                cnt++;
            }
            l++;
        }
        return res;
        
    }
};

image.gif

4.7 长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        int j=0;
        int sum=0;
        int res=0x3f3f3f3f;
        for(int i=0;i<n;i++){
            sum+=nums[i];
            while(sum>=target){
                res=min(res,i-j+1);
                sum-=nums[j];
                j++;
            }
        }
        if(res==0x3f3f3f3f) return 0;
        else return res;
    }
};

image.gif

4.8 盛水最多的容器

11. 盛最多水的容器 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int l=0,r=n-1;
        int res=-1;
        while(r>l){
            int a=r-l;
            int b=min(height[l],height[r]);
            res=max(res,a*b);
            if(height[l]<height[r]){
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
};

image.gif

4.9 无重复字符的最长子串（无需连续）

3. 无重复字符的最长子串 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.size();
        int last[128];
        memset(last,-1,sizeof(last));
        int j=0;
        int res=0;
        for(int i=0;i<n;i++){
            char c=s[i];
            if(last[c]>=j) j=last[c]+1;
            last[c]=i;
            res=max(res,i-j+1);
        }
        return res;
    }
};

image.gif

4.10 三数之和

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

代码实现（C++/Java）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            int l=i+1,r=nums.size()-1;
            while(r>l){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum>0){
                    r--;
                } else if(sum<0){
                    l++;
                } else {
                    vector<int> t;
                    t.push_back(nums[i]);
                    t.push_back(nums[l]);
                    t.push_back(nums[r]);
                    res.push_back(t);
                    while(l<r && nums[l]==nums[l+1]) l++;
                    while(l<r && nums[r]==nums[r-1]) r--;
                    l++;
                    r--; 
                }
            }
        }
        return res;
    }
};

image.gif

4.11 四数之和

18. 四数之和 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            //剪支,后面不可能凑出更小的和
            if(nums[i]>target && nums[i]>0) break;
            if(i>0 && nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<nums.size();j++){
               //剪支
               if((long long)nums[i]+nums[j]>target && nums[j]>0) break;
               if(j>i+1 && nums[j]==nums[j-1]) continue;
                int l=j+1,r=nums.size()-1;
                while(r>l){
                    long long sum=(long long)nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum>target){
                        r--;
                    } else if(sum<target){
                        l++;
                    } else {
                        vector<int> t;
                        t.push_back(nums[i]);
                        t.push_back(nums[j]);
                        t.push_back(nums[l]);
                        t.push_back(nums[r]);
                        res.push_back(t);
                        while(r>l && nums[r]==nums[r-1]) r--;
                        while(r>l && nums[l]==nums[l+1]) l++;
                        l++;
                        r--;
                    }
                }
            }
        }
         return res;
    }
};

image.gif

4.13 反转字符串

344. 反转字符串 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l=0,r=s.size()-1;
        while(r>l){
            swap(s[l],s[r]);
            l++;
            r--;
        }
    }
};

image.gif

4.14 反转字符串2

541. 反转字符串 II - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    void fun(string& s,int l,int r){
        for(int i=l,j=r;i<=j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for(int i=0;i<s.size();i+=2*k){
            //注意传参第二个参数
            int l=i,r=min(i+k-1,(int)s.size()-1);
            //注意传参地址引用
            fun(s,l,r);
        }
        return s;
    }
};

image.gif

4.15 动态口令

LCR 182. 动态口令 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    void fun(string &s,int l,int r){
        while(r>l){
            swap(s[l],s[r]);
            l++;
            r--;
        }
    }
    string dynamicPassword(string password, int target) {
        //直接记忆规律
        fun(password,0,target-1);
        fun(password,target,password.size()-1);
        fun(password,0,password.size()-1);
        return password;
    }
};

image.gif

4.16 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n=haystack.size();
        int m=needle.size();
        for(int i=0;i<=n-m;i++){
            int j=0;
            while(j<m && needle[j]==haystack[i+j]){
                j++;
            }
            if(j==m) return i;
        }
        return -1;
    }
};

image.gif

4.17 反转字符串中的单词

151. 反转字符串中的单词 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    void reverse(string &s,int l,int r){
        while(r>l){
            swap(s[l],s[r]);
            l++;
            r--;
        }
    }
    string respace(string &s){
        stringstream ss(s);
        string word,res;
        while(ss>>word){
            if(!res.empty()) res+=" ";// 如果不是第一个词，补空格
            res+=word;
        }
        return res;
    }
    string reverseWords(string s) {
        s=respace(s);
        reverse(s,0,s.size()-1);
        for(int i=0;i<s.size();i++){
            int j=i;
            while(j<s.size() && s[j]!=' '){
                j++;
            }
            reverse(s,i,j-1);
            i=j;
        }
        return s;
    }
};

image.gif

4.18 重复的子字符串

459. 重复的子字符串 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t=s+s;
        t=t.substr(1,t.size()-2);
        return t.find(s)!=string::npos;
    }
};

image.gif 

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String t=s+s;
        t=t.substring(1,t.length()-1);
        return t.contains(s);
    }
}

image.gif

4.19 循环相克令

https://www.acwing.com/problem/content/765/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int t;
//不要123，否则取余数无法取
int fun(string s){
    if(s=="Hunter") return 0;
    else if(s=="Gun") return 1;
    else return 2;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    for(int i=1;i<=t;i++){
        string s1,s2;
        cin>>s1>>s2;
        int n1=fun(s1);
        int n2=fun(s2);
        if(n1==n2) cout<<"Tie"<<endl;
        else if((n1+1)%3==n2) cout<<"Player1"<<endl;
        else cout<<"Player2"<<endl;
    }   
    
    return 0;
}

image.gif

4.20 输出字符串

https://www.acwing.com/problem/content/766/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
string a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    getline(cin,a);
    string b;
    for(int i=0;i<a.size()-1;i++){
        b+=a[i]+a[i+1];
    }
    b+=a[0]+a[a.size()-1];
    cout<<b<<endl;
    
    return 0;
}

image.gif

4.21 去掉多余空格

https://www.acwing.com/problem/content/768/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    getline(cin,s);
    string res;
    for(int i=0;i<s.size();i++){
        if(s[i]!=' ') res+=s[i];
        else {
            int j=i;
            while(j<s.size() && s[j]==' ') j++;
            i=j-1;
            res+=s[i];
        }
    }
    cout<<res<<endl;
    
    return 0;
}

image.gif

4.22 信息加密

https://www.acwing.com/problem/content/769/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    getline(cin,s);
    for(int i=0;i<s.size();i++){
        if(s[i]>='a' && s[i]<='z'){
            s[i]='a'+(s[i]+1-'a')%26;
        } else if(s[i]>='A' && s[i]<='Z'){
            s[i]='A'+(s[i]+1-'A')%26;
        }
    }
    cout<<s<<endl;
    
    return 0;
}

image.gif

4.23 忽略大小写比较字符串大小

https://www.acwing.com/problem/content/770/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string s1,s2;
    getline(cin,s1);//不用这个读入会报错，以后用这个读入字符串
    getline(cin,s2);
    for(char &c:s1) c=tolower(c);
    for(char &c:s2) c=tolower(c); 
    if(s1==s2) cout<<"="<<endl;
    else if(s1>s2) cout<<">"<<endl;
    else cout<<"<"<<endl;
    
    return 0;
}

image.gif

4.24 替换字符

https://www.acwing.com/problem/content/771/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string s;
    char c;
    getline(cin,s);
    cin>>c;
    for(int i=0;i<s.size();i++){
        if(s[i]==c){
            s[i]='#';
        }
    }
    cout<<s<<endl;
    return 0;
}

image.gif

4.25 单词替换

https://www.acwing.com/problem/content/772/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string s,a,b;
    getline(cin,s);
    getline(cin,a);
    getline(cin,b);
    for(int i=0;i<s.size();i++){
        int j=i;
        string t;
        while(s[j]!=' ' && j<s.size()){
            t+=s[j];
            j++;
        }
        i=j;
        if(t==a) cout<<b<<" ";
        else cout<<t<<" "; 
        
    }
    
    return 0;
}

image.gif

4.26 字符串中最长的连续出现的字符

https://www.acwing.com/problem/content/773/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    cin>>n>>ws;//数字和字符串之间 
    for(int i=1;i<=n;i++){
        string s;
        getline(cin,s);
        int res=0;
        char c;
        for(int j=0;j<s.size();j++){
            int k=j;
            while(k<s.size() && s[k]==s[j]){
                k++;
            }
            int cnt=k-j;
            if(cnt>res){
                res=cnt;
                c=s[j];
            }
            j=k-1;//下一轮还要自增 
        }
        cout<<c<<" "<<res<<endl;
    }
    return 0;
}

image.gif

4.27 只出现一次的字符

https://www.acwing.com/problem/content/774/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int h[28];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    string s;
    getline(cin,s);
    for(int i=0;i<s.size();i++){
        h[s[i]-'a']++;
    }
    for(int i=0;i<s.size();i++){
        if(h[s[i]-'a']==1){
            cout<<s[i]<<endl;
            return 0;
        }
    }
    cout<<"no"<<endl; 
    return 0;
}

image.gif

4.28 字符串插入

https://www.acwing.com/problem/content/775/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    string a,b;
    while(cin>>a>>b){
        int t=0;
        for(int i=0;i<a.size();i++){
            if(a[i]>a[t]){
                t=i;
            }
        }
        string res=a.substr(0,t+1)+b+a.substr(t+1);
        cout<<res<<endl;
    }
    
    
    return 0;
}

image.gif

4.29 最长单词

https://www.acwing.com/problem/content/776/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    string word,res;
    while(cin>>word){
        if(word.back()=='.') word.pop_back();
        if(word.size()>res.size()){
            res=word;
        }
    }
    cout<<res<<endl;
    
    
    return 0;
}

image.gif

4.30 倒排单词

https://www.acwing.com/problem/content/777/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    string s;
    getline(cin,s);
    for(int i=0,j=s.size()-1;i<j;i++,j--){
        swap(s[i],s[j]);
    }
    for(int i=0;i<s.size();){
        int j=i;
        while(s[j]!=' ' && j<s.size()) j++;
        for(int l=i,r=j-1;r>l;l++,r--){
            swap(s[l],s[r]);
        }
        i=j+1;
    }
    cout<<s<<endl;
    
    
    return 0;
}

image.gif

4.31 字符串移位包含问题

https://www.acwing.com/problem/content/778/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()<s2.size()){
        swap(s1,s2);
    }
    s1+=s1;
    bool flag=false;
    for(int i=0;i<s1.size();i++){
        //substr(起始位置，子串长度)
        string t=s1.substr(i,s2.size());
        if(t==s2) flag=true;
    }
    if(flag) cout<<"true"<<endl;
    else cout<<"false"<<endl;
    
    return 0;
}

image.gif

4.32 字符串乘方

https://www.acwing.com/problem/content/779/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    string s;
    while(cin>>s && s!="."){
        int k=1;
        while(k<=s.size()){
            if(s.size()%k==0){
                bool flag=true;
                for(int i=k;i<s.size();i+=k){
                    for(int j=0;j<k;j++){
                        if(s[j]!=s[i+j]){
                            flag=false;
                        }
                    }
                }
                if(flag) break;//K合法
                k++;//K不合法 
            } else {
                k++;
            }
        }
        cout<<s.size()/k<<endl; 
    }
    
    return 0;
}

image.gif

4.33 字符串最大跨距

https://www.acwing.com/problem/content/780/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string str;
    cin>>str;
    string s,s1,s2;
    int k=0;
    while(str[k]!=','){
        s+=str[k];
        k++;
    }
    k++;
    while(str[k]!=','){
        s1+=str[k];
        k++;
    }
    k++;
    while(k<str.size()){
        s2+=str[k];
        k++;
    }
    int l=0,r=s.size()-1;
    while(l<s.size()){
        if(s.substr(l,s1.size())==s1) break;
        l++;
    }
    while(r>=0){
        if(s.substr(r,s2.size())==s2) break;
        r--;
    }
    if(l+s1.size()-1<=r) cout<<r-(l+s1.size())<<endl;
    else cout<<-1<<endl;
    
    return 0;
}

image.gif

4.34 最长公共字符串后缀

https://www.acwing.com/problem/content/781/

代码实现（C++/Java）

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n;
string word[N];
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(cin>>n && n!=0){
        for(int i=0;i<n;i++) cin>>word[i];
        
        int k=1;
        while(true){
            bool flag=true;
            for(int i=0;i<n;i++){
                if(word[i].size()<k){
                    flag=false;
                    break;
                } else if(word[i].substr(word[i].size()-k,k)!=word[0].substr(word[0].size()-k,k)){
                    flag=false;
                    break;
                }
            }
            if(!flag) break;
            k++;    
        }
        k--;
        cout<<word[0].substr(word[0].size()-k,k)<<endl;
        
    }
    
    
    return 0;
}

image.gif

4.35 接雨水

42. 接雨水 - 力扣（LeetCode）

代码实现（C++/Java）

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(n==0) return 0;
        int l=0,r=n-1;
        int lMax=0,rMax=0;
        int res=0;
        while(r>l){
            if(height[l]<height[r]){
                if(height[l]>=lMax){
                    lMax=height[l];
                } else{
                    res+=lMax-height[l];
                }
                l++;
            } else {
                if(height[r]>=rMax){
                    rMax=height[r];
                } else {
                    res+=rMax-height[r];
                }
                r--;
            }
        }
        return res;
    }
};

image.gif


文章标签：
Java
C++
算法
容器
数据安全/隐私保护
游客onzhxyi7cxqew
目录
相关文章
LucianaiB
|
3天前
|
人工智能 JSON 机器人
让龙虾成为你的“公众号分身” | 阿里云服务器玩Openclaw
本文带你零成本玩转OpenClaw：学生认证白嫖6个月阿里云服务器，手把手配置飞书机器人、接入免费/高性价比AI模型（NVIDIA/通义），并打造微信公众号“全自动分身”——实时抓热榜、AI选题拆解、一键发布草稿，5分钟完成热点→文章全流程！
LucianaiB
10556 52
让龙虾成为你的“公众号分身” | 阿里云服务器玩Openclaw
ClawdbotMoltbot
|
9天前
|
人工智能 JavaScript API
解放双手！OpenClaw Agent Browser全攻略（阿里云+本地部署+免费API+网页自动化场景落地）
“让AI聊聊天、写代码不难，难的是让它自己打开网页、填表单、查数据”——2026年，无数OpenClaw用户被这个痛点困扰。参考文章直击核心：当AI只能“纸上谈兵”，无法实际操控浏览器，就永远成不了真正的“数字员工”。而Agent Browser技能的出现，彻底打破了这一壁垒——它给OpenClaw装上“上网的手和眼睛”，让AI能像真人一样打开网页、点击按钮、填写表单、提取数据，24小时不间断完成网页自动化任务。
ClawdbotMoltbot
2378 5
OpenClaw
|
23天前
|
人工智能 JavaScript Ubuntu
5分钟上手龙虾AI！OpenClaw部署（阿里云+本地）+ 免费多模型配置保姆级教程（MiniMax、Claude、阿里云百炼）
OpenClaw（昵称“龙虾AI”）作为2026年热门的开源个人AI助手，由PSPDFKit创始人Peter Steinberger开发，核心优势在于“真正执行任务”——不仅能聊天互动，还能自动处理邮件、管理日程、订机票、写代码等，且所有数据本地处理，隐私完全可控。它支持接入MiniMax、Claude、GPT等多类大模型，兼容微信、Telegram、飞书等主流聊天工具，搭配100+可扩展技能，成为兼顾实用性与隐私性的AI工具首选。
OpenClaw
23964 121
JavaPub
|
3天前
|
人工智能 IDE API
2026年国内 Codex 安装教程和使用教程：GPT-5.4 完整指南
Codex已进化为AI编程智能体，不仅能补全代码，更能理解项目、自动重构、执行任务。本文详解国内安装、GPT-5.4接入、cc-switch中转配置及实战开发流程，助你从零掌握“描述需求→AI实现”的新一代工程范式。（239字）
JavaPub
2183 126

热门文章

最新文章

  • 1
    李峋同款爱心Python代码版来了
  • 2
    阿里巴巴动物园又又又叕来了新同学
  • 3
    基于redis的分布式ID生成器
  • 4
    [译] 如何避免我作为初级开发者时所犯下的 7 个错误
  • 5
    计算删除日期(二)
  • 6
    Office2010新功能：方便快捷的屏幕截图
  • 7
    iOS: performXXX的几种方法总结：
  • 8
    【漫威】美国队长3 - 让我们聊聊内战那回事(上)
  • 9
    Linux下的Nginx安装(开机自启动)
  • 10
    IT行业新职位——IT审计师
  • 1
    OpenClaw+Ollama v0.18.1 联网搜索全攻略：阿里云+本地三系统部署+千问/Coding Plan配置及问题排查
    226
  • 2
    OpenClaw 养虾防翻车完全手册：28个高频错误避坑指南+全平台部署与大模型配置
    80
  • 3
    OpenClaw进阶指南：阿里云/本地部署+API配置+多模态融合+跨平台联动实战手册
    101
  • 4
    缓存是黑客最爱渗透和攻击的一环。为什么？优雅草卓伊凡
    55
  • 5
    MiniMax M2.7 赋能 OpenClaw 全能力：本地+阿里云部署、千问/Coding Plan 配置与实战指南
    338
  • 6
    解防跨站功能生成的.user.ini文件溯源跨站脚本攻击（XSS）-优雅草卓伊凡
    37
  • 7
    B/S端和C/S端两种架构的应用详解，架构对于网络安全以及系统本身的详解-优雅草卓伊凡
    57
  • 8
    【Bean】JavaBean（原生规范）/ Spring Bean 【重点】/ 企业级Bean（EJB/Jakarta Bean）
    37
  • 9
    B/S端（浏览器/服务器架构）和C/S端（客户端/服务器架构）得攻防难易度区别？优雅草卓伊凡
    29
  • 10
    Codex 的两种使用方式：为什么很多人一开始就用错了？
    116

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    狂揽7.5k星！这款开源API网关彻底解放开发者：一键聚合GPT-4、Suno、Midjourney，还能在线充值！