算法竞赛入门经典(第2版)第5章笔记上

哎,之前学习算法的日子并没有系统的学习,东补补西凑凑刷刷题,最近准备用4个月(也就是9月之前)把算法竞赛入门与指南学了(如果你和我一样是小白(大佬忽略),建议系统的学习算法)。
日子过得可真快啊,每天学点算法就过完了,但是感觉到头来又忘了,特此写点学习过程中的收获留作复习。

算法竞赛入门经典第五章笔记上

输入输出流优缺点
用cin输入的方式相比scanf输入的方式最大的优势就是不需要记忆%d %s等占位符,但是也有弊端就是运行太慢。
效率不同的两种解释
①cin与stdin总是保持同步的,也就是说这两种方法可以混用,而不必担心文件指针混乱,同时cout和stdout也一样,两者混用不会输 出顺序错乱。正因为这个兼容性的特性,导致cin有许多额外的开销。
②cout在输出时总是要先将输出的存入缓存区。而printf直接调用系统进行IO,它是非缓存的。所以cout比printf慢。
在比赛中如果数据量过大建议用scanf(),printf()方式输入输出,或者关闭与stdio的同步也就是:ios:sync_with_stdio(false)。

名称空间
为什么c++比c多出了 using namespace std;呢? 它是用来解决复杂程序的组织问题,例如LH写了一个函数叫is_prime(int n);ME也写了一个函数叫is_prime(int n),那么当有一天把他们程序合在一起,就会出现问题(参数相同,函数名相同情况下不能重载),那么把函数写在各自的名称空间,就可以用 LH::is_prime()或者ME::is_prime()调用。

问题: 输入一行若干个以空格隔开的整数,输出每行中所有整数和
方案一:getchar()一个一个字符的读取,容易少考虑换行符而出错

#include <iostream>
#include <vector>

using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    char k;
    //flag判断前一个是否为数字
    int ans=0,flag=0;
    vector<int> p;
    while((k=getchar())!=EOF){
        //注意换行符要进行判断,意味着换行了
        if(k==' '||k=='\n'){
           if(flag!=0) p.push_back(ans);
           //输出数据
           if(k=='\n'){
              ans=0;
              for(int i=0;i<p.size();i++)
                  ans+=p[i];
              cout <<ans<<endl;
              p.clear();
           }
           flag=0;
           ans=0;
        }
        else {
            ans=ans*10+k-'0';
            flag=1;
        }
    }
    return 0;
}


方案二:先读取每一行,再扫描该行的字符,进而计算结果(书上代码)。
sstream头文件包含stringstream类,可进行输入输出操作

#include <iostream>
#include <sstream>

using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    string line;
    while(getline(cin,line)){
        int sum=0,x;
        stringstream ss(line);
        while(ss >> x) sum+=x;
        cout << sum <<endl;
    }
    return 0;
}

第二种方案使用istream& getline (istream& is, string& str)函数,getline默认以’\n’结束,可以读取空格,Tab等字符。
但是不限于此,istream& getline (istream& is, string& str, char delim);此处getline可以以delim字符结束(比如"abcd",getline(cin,line,‘c’),此时line为"ab")。
而对stringstream的清空:
clear():清除流的状态标志,但不会改变流中的内容。
str(”“):清空流中的数据,相当于无论之前流中的数据是什么,使用str(”“)之后,流数据为空,并且将状态符固定。
具体大家可以去实验一下。
注意:用sstream很慢。

结构体不再需要typedef的方式定义一个struct,结构体中可以包含一些辅助成员函数。

c++< algorithm >头文件包含lower_bound(),upper_bound()函数。

lower_bound(起始地址,结束地址,val) 如果在数列中存在val返回的是第一次(从前往后找)出现val的位置,否则返回第一个插入val不影响原序列顺序的位置。

upper_bound(起始地址,结束地址,val) 返回的是第一个大于val值的位置

binary_search(起始地址,结束地址,val) 返回的是是否存在这么val,是一个bool值

至于STL中的容器我会在C++专栏里面详细介绍

tolower():将字符转化为小写字符
toupper():将字符转化为大写字符
因为有时候一个字符一个字符转化太麻烦,怎么将字符串转化为小写/大写字符串呢?如下:
transform(处理对象容器起始地址,处理对象容器结束地址,存放结果的容器地址,处理操作(可自定义))
注意:前后两个容器的大小一致,可通过resize()设置或者直接放在处理对象的容器处
例如:

transform(p.begin(),p.end(),p.begin(),::tolower);
transform(p.begin(),p.end(),p.begin(),::toupper);

希望大家耐心看完,如果有帮助的留下的你赞支持一下,冲啊 今天是美好的 明天也是

上一篇:使用C++输入一个包含空格的字符串,再输入单独的一个字符,找到这个字符串中当前字符的个数(注意不区分大小写)


下一篇:leetcode笔记总结——(5)简化路径(python和C++实现)