课程总结（第一周）-白红宇

课程总结（第一周）

阅读量：209 次

发布时间：2019-03-01

本文共 3231 字，大约阅读时间需要 10 分钟。

课程总结（第一周）

翌得知识：

一.string函数的用法

二.初学重载运算符以及重载函数

三.贪心算法及三道例题思路

四.二分法初识

五.栈队列和 vector

一.string 函数

构造string的多种方式：
string str：生成一个空字符串
string s(str):字符串s等于str，为str的一个复制品
string s(str,strbegin,strlen)：操作字符串str，strbegin为开始下标，去长度为strlen的子字符串
string s(str1, str_len ) : 从str中取子字符串长度为len，赋给str1
string s（num，c）：生成num个c字符的字符串
string s(str,stridx) : 从下标为stridx开始读至末尾

#include 
   
    #include
    
     using namespace std;int main(){       string str;    cout<
     
      <

abcdefgcdeabcfffffdefgProcess returned 0 (0x0)   execution time : 0.048 sPress any key to continue.

2.对string类型大小拼接和插入

插入语句：push_back() 和 insert（）

字符大小：变量名.size() 和变量名.length()

字符拼接：string类型支持基础运算，变量名.append()起连接作用

#include 
   
    #include
    
     using namespace std;int main(){       string s;    s.push_back('a');    s.push_back('b');    s.push_back('c');    cout<
     <

abc2abc410737418202abcdefProcess returned 0 (0x0)   execution time : 0.282 sPress any key to continue.

3.string类型的查找：find（）

#include 
   
    #include
    
     using namespace std;int main(){       string s("abc def ghi jkl mn"); //string类型接收空格    cout<
     
      <

二.初学重载运算符及重载函数

重载函数

作用：函数名相同，提高函数复用性

特征：

1.同一个作用域下

2.函数名称相同

3.设置参数类型不同或者个数不同或者顺序不同

//引用可以作为重载条件

for instance：fun（int &a）和 fun（const int &a）

主函数中调用 fun(a) 和 fun（10）所调用函数不同

//函数重载碰到默认参数

void fun（int a ,int b=10）和 void fun（int a）

主函数中：

调用 fun（10），则会引起二义性，系统无法识别

重载运算符（并不是很懂）

定义：

<返回类型说明符> operator <运算符符号>(<参数表>)

{

<函数体>

}

比如：

bool operator < (const t1 &b)const

{ return key<b.key}

//若小于返回true，若大于等于则返回false ；若用于sort函数，则会控制升序或者降序

bool operator + (const t1 &b)const //加号

bool operator - (const t1 &b)const //减号

三.贪心算法

作用：寻找问题的最优化方案

三.贪心三道例题

1.贪心题A:

题意：N头牛在不同位置发出叫声，某头牛发出的叫声要使得其他牛都听到，计算所有牛发出叫声的总音量（volume）

题解：最暴力的方法是各个数相减取绝对值，然后相加，但会报超时。贪心算法要求将牛所在位置排好序（sort），双重for循环，遍历后面的数减去前面的数，得到结果乘以2，会省去机器一半的计算量。

核心代码：

for（int i=0;i

题B：supermarket

题意：共有n个产品，每个产品都自带属性（利润，销售截止日期）。一天只能卖一种产品，相同截止日期的，售卖利润高的优先，利润低的则放到前面卖，若前面天数都已被其他产品占据，则舍去。

题解：将利润从高到低排好序，满足结构数组前面利润高的产品，在相应天卖出，且用另一数组标记该天是否被占据，利润低的在截止日期前空出天数卖出。

for(int i=0;i
   
    =1&&c[j]!=0) j--'if(j<1) continue;c[j]=1;sum=sum+a[i].price;}

题F：

题意：老鼠有一堆猫粮，要和守护房间的多只猫换取鼠粮，要求换出的鼠粮最大化

题解：由于每个房间存储的鼠粮不同和需要的猫粮也不同。因此算出该房间对于老鼠的性价比，从高到低排序，相应换取。最后当存储的猫粮不足以支付时，根据比例换取

for（int i=0;i
   
    f) {   sum+=ja;  m=m-f;  }  else  {   sum+=m*a[i].rate;   break;}}{

四.二分法初识

二分法对数据的搜索更加快速，以指数倍的效率，每次将范围缩小二分之一

int rearch(int a[],int n,int x){       int left=0,right=n-1;    while(left<=right)    {           int middle=(left+right)/2;        if(a[middle]==x) return middle;        if(x>a[middle]) left=middle+1;        else right=middle-1;    }    return -1;}

五.栈队列和 vector

栈："先进后出“”

定义：stack<date_type>stack_name;

如: stack <int>s;

empty()–返回bool类型，表示栈内是否为空

size()–返回栈内元素个数

top（）：返回栈顶元素值

push（date_type a）–向栈压入一个值

队列：“先进先出”

定义：queue<date_type>queue_name;

如: queue <int>s;

empty()–返回bool类型，表示队列内是否为空