首页 > 编程语言 >算法基础(3)

算法基础(3)

时间:2023-03-24 23:25:12浏览次数:51  
标签:std 10 int 基础 算法 alls using include

双指针算法 O(n)
采用双指针算法的前提是具有单调性

 

 

题目:提取单词

 

#include <iostream>
#include <string.h>
using namespace std ; 
const int N = 1e3+10;

int main(){
       
    char str[1000];
    gets(str);
    int n = strlen(str); 
    for(int i=0; i<n ; i++)
    {
        int j = i;  
        while(j<n && str[j] !=' ') j++ ;
        for(int k=i; k<j ; k++) cout<<str[k]; 
        cout<<endl;
        i=j; 
    }    
    return 0;
}

 

最长连续不重复子序列(不是特别理解)

#include <iostream>
using namespace std;
const int N = 1e6+10; 
int n; 
int a[N],s[N]; 

int main(){
    
    cin>>n ; 
    for(int i=0; i<n;i++ ) cin>>a[i]; 
    int res = 0; 
    
    for( int i=0,j=0;  i<n ; i++ )
    {
        s[a[i]]++ ; 
        while( s[a[i]] > 1 && j<i )
        {
            s[a[j]]--;
            j++;
        }
        res = max(res, i-j+1); 
    }
    cout<<res<<endl;
    return 0;
} 

提取目标和:

请你求出满足 <span id="MathJax-Span-14" class="mrow"><span id="MathJax-Span-15" class="mi">A<span id="MathJax-Span-16" class="mo">[<span id="MathJax-Span-17" class="mi">i<span id="MathJax-Span-18" class="mo">]<span id="MathJax-Span-19" class="mo">+<span id="MathJax-Span-20" class="mi">B<span id="MathJax-Span-21" class="mo">[<span id="MathJax-Span-22" class="mi">j<span id="MathJax-Span-23" class="mo">]<span id="MathJax-Span-24" class="mo">=<span id="MathJax-Span-25" class="mi">xA[i]+B[j]=x 的数对 <span id="MathJax-Span-27" class="mrow"><span id="MathJax-Span-28" class="mo">(<span id="MathJax-Span-29" class="mi">i<span id="MathJax-Span-30" class="mo">,<span id="MathJax-Span-31" class="mi">j<span id="MathJax-Span-32" class="mo">)&nbsp;

#include <iostream>
using namespace std;
const int N = 1e6+10; 
int a[N],b[N]; 

int main(){
    int n,m,x; 
    cin>>n>>m>>x; 
    
    for(int i=0;i<n;i++) cin>>a[i]; 
    for(int j=0;j<m;j++) cin>>b[j];
    
    for(int i=0,j=m-1; i<n || j>=0 ; )
    {
        while( a[i]+b[j]>x ) j-- ;
        while( a[i]+b[j]<x ) i++ ;
        if(a[i]+b[j] == x ) 
        {
            cout<<i<<' '<<j ; 
            break; 
        }
    }

    return 0;
} 

判断子序列:

#include <iostream>
using namespace std;
const int N = 1e6+10; 
int a[N],b[N]; 

int main(){
    int n,m; 
    cin>>n>>m; 
    
    for(int i=0;i<n;i++) cin>>a[i]; 
    for(int j=0;j<m;j++) cin>>b[j];
    
    for(int i=0,j=0; i<n && j<m ; )
    { 
        while(a[i]==b[j] && i<n) { i++ ; j++; } 
        while(a[i]!=b[j] && j<m ) j++;
        if(i==n)
        {
            cout<<"Yes"; return 0;     
        } 
    }
    cout<<"No";
    return 0;
} 

位运算

n的二进制表示中第k位:

(1)先把第k位移到最后一位, x>>k ; 

(2)看个位是什么 ; n>>k && 1; 

lowbit(x): 返回x的最后一位1,例如10,即1010,返回10;

     x & -x = x&(~x + 1) 

例题:统计二进制数中的1的个数

#include <iostream>
using namespace std; 
int lowbit(int x )
{
    return x&-x ;  
}
int main()
{
    int n; cin>>n ; 
    while(n--)
    {
        int x; cin>>x ; 
        int cnt = 0;
        while(x)
        {
            x -= lowbit(x) ; 
            cnt++ ; 
        }
        cout<<cnt<<' ' ;
    }
}

离散化

基本概念:

例题:区间和,难度较大

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6+10; 
int a[N],s[N]; 
int n,m; 

typedef pair<int,int> PII; 
vector<int> alls; 
vector<PII> add,query ; 

int find(int x ) //求离散化的结果 ,二分
{
    int l =0, r = alls.size()-1 ; 
    while(l<r){
        int mid =(l+r)/2; 
        if(alls[mid]>=x)  r=mid ; 
        else l = mid+1; 
    } 
    return r+1 ;
}
int main(){
    
    cin>>n>>m; 
    for(int i=0; i<n;i++)
    {
        int x,c; 
        cin>>x>>c; 
        add.push_back({x,c}) ; 
        alls.push_back(x);
    }
    for(int i=0;i<m;i++)
    {
        int l,r; 
        cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    
    //去重 
    sort(alls.begin(), alls.end()) ;
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    //处理插入 
    for( auto item:add)
    {
        int x = find(item.first) ; 
        a[x] += item.second ; 
    }
    
    //预处理前缀和
    for(int i=1; i<=alls.size(); i++)
        s[i] = s[i-1]+a[i] ;
    
    // 处理询问
    for( auto item:query)
    {
        int l=find(item.first),r=find(item.second) ;
        cout<<s[r]-s[l-1]<<endl; 
     } 
    return 0;
} 

标签:std,10,int,基础,算法,alls,using,include
From: https://www.cnblogs.com/zundicai/p/17253627.html

相关文章

  • 第二章 DC-DC变换器设计与磁学基础
    对于DCDC变换器,只有电感这一个磁性元件需要考虑,它通常需要我们自行设计。2.1直流传递函数开关导通期间,电感中的电流在电压的作用下呈现一定的斜率上升,增量为:\[\triangle......
  • 机器学习算法(四): 基于支持向量机的分类预测(SVM)
    机器学习算法(四):基于支持向量机的分类预测本项目链接:https://www.heywhale.com/home/column/64141d6b1c8c8b518ba97dcc1.相关流程支持向量机(SupportVectorMachine,SVM......
  • Java面试-基础篇(一)6
    synchronized与ReentrantLock的区别说到synchronized与ReentrantLock,我们都知道,他们是java并发编程很重要的技术。他们可以帮助我们保证编程过程中数据的正确性,也就是我们......
  • C语言基础知识
    1、变量类型   字符型--char--所占字节(1)   整型--int--所占字节(4)   短整型--short--所占字节(2)   长整型--long--所占字节(4)   更长的整形--longlo......
  • 计算机基础
    计算机基础逻辑门逻辑门是一种常见的元器件,能够执行一种或多种逻辑运算。常见的逻辑门有:与门(ANDgate)、或门(ORgate)、非门(NOTgate)、异或门(XORgate)等。与或非是计算机......
  • 通信基础知识-名词解释
    AWGN:加性高斯白噪声(AWGN)是一个数学模型,用于仿真发射机和接收机之间的信道。这个模型是线性增加的宽带噪声,具有恒定的频谱密度和高斯分布的幅度。AWGN不适用于衰落、互......
  • 代码随想录算法训练营Day52 动态规划
    代码随想录算法训练营代码随想录算法训练营Day52动态规划|300.最长递增子序列674.最长连续递增序列718.最长重复子数组300.最长递增子序列题目链接:300.最长递增子......
  • 【THM】Pentesting Fundamentals(渗透测试基础介绍)-学习
    本文相关的TryHackMe实验房间链接:https://tryhackme.com/room/pentestingfundamentals本文相关内容:了解渗透测试背后的重要道德规范和方法论。什么是渗透测试?在学习道......
  • HTML 文本处理基础
    提前声明本博客只是将自己学到的知识做总结而已,细节学习请来这里,大佬的教学很详细很棒。学习结果展示本次学习学到了 标题的使用 无序列表的使用看,第二个无......
  • 【黑马前端】基础班总结
    HTML1、定义:超文本标记语言(hypertextmarkuplanguage)​ 超:可以加图片、声音、动画、多媒体等非文本内容;​ 可以从一个文件跳到另一个文件,即超级链接文......