蓝桥杯算法日记|贪心、双指针

3412 545 2928 2128

贪心学习总结：

1、一般经常用到sort（a，a+n）；【a[n]】排序，可以给整数排，也可以给字符串按照字典序排序

2、每次选最优

 双指针

有序数组、字符串、二分查找、数字之和、反转字符串、回文数、颠倒二进制

对撞指针

一个是最左边，另一个是最右边，条件l<=r

回文#include <bits/stdc++.h>
using namespace std;
int main()
{// 请在此输入您的代码string s;cin>>s;int n=s.size();int l=0,r=n-1;while(l<=r){if(s[l]!=s[r]){cout<<"N"<<'\n';exit(0);}l++;r--;}cout<<"Y"<<'\n';return 0;
}

快慢指针

从同一侧开始遍历序列，且一动的步长一个快一个慢【l,r】,两指针一不同的速度、不同策略移动，直到快指针移动到数组尾端、或者两指针相交，或者其他条件为止。

快指针移动策略，慢指针移动策略

for（慢指针移动策略）{

while（快指针移动策略）

if{题目条件}结果；

其他补充；

}

#include <bits/stdc++.h>
using namespace std;
int main()
//{
//  // 请在此输入您的代码
//  int n,s;cin>>n>>s;
//  int a[n];
//  for(int i=0;i<n;i++){cin>>a[i];}
//  //输出美丽区间和》s并且越短越美丽
//  //区间问题，想到了前缀和
//  int sum[n];sum[0]=a[0];
//  for(int i=1;i<n;i++){
//    sum[i]=sum[i-1]+a[i];
//  }
//  for(int i=0;i<n;i++){
//    for(int j=i+1;j<n;j++){
//      if(i=0){if(sum[j]>s){cout<<j-i-1<<'\n';exit(0);}}
//      else{if(sum[j]-sum[i]>s){cout<<j-i-1<<'\n';exit(0);}}
//    }
//  }
//  return 0;
//}
//正确率对一个 ，最短的不一定先出现 
{
//随时更新最短长度 int n,s;cin>>n>>s;int a[n];for(int i=1;i<=n;i++){cin>>a[i];}int ans=n+1;for(int i=1,j=0,sum=0;i<=n;i++){//区间变大  while(j<i||(j<n&&sum<s)){sum=sum+a[++j];cout<<sum<<" ";} if(sum>=s)ans=min(ans,j-i+1);sum=sum-a[i];cout<<sum<<'\n'; //收缩左边界，保证i+1后，sum } cout<<ans<<'\n';return 0;
} 

#include <iostream>
using namespace std;
int main()
{// 请在此输入您的代码int n,m,k;cin>>n>>m>>k;int a[n];for(int i=1;i<=n;i++){cin>>a[i];}int sum=0,res=0;for(int i=1,r=0;i<=n;i++){//不满足条件,则移动快指针while(r<i||(sum<k&&r+1<=n)){sum=sum+(a[++r]>=m);}//满足条件if(sum>=k)res=res+1+n-r;sum=sum-(a[i]>=m);}cout<<res<<'\n';
//错误代码：// for(int i=1;i<=n;i++){//   for(int j=i;j<=n;j++){//     //至少有k个数是大于等于m//     if(a[j]>=m)sum++;//     if(sum=k){res=1+n-j;break;}//   }// }// cout<<res<<'\n';return 0;
}

今日打卡：

2.10
挑选字符串

https://www.lanqiao.cn/problems/1621/learning/
美丽的区间
https://www.lanqiao.cn/problems/1372/learning/
回文判定
https://www.lanqiao.cn/problems/1371/learning/