山东农业大学ACM学习,第二周学习心得_大大大太阳chen的博客-程序员宅基地

山东农业大学ACM选修课
撰写人:陈浩

第二周学习心得总结

STL的简单应用:string stack queue vector sort priority_queue unique upper_bound lower_bound set和multiset map和multimap简单应用
贪心算法:学了一小部分,主体思想就是最优解决办法。它是按照某种最优策略,将复杂问题层层分解成子问题(每次一般只有一个),并由子问题的最优解“回溯”出整个问题的最优解。贪心算法不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解。
万能开头函数:#include <bits/stdc++.h>
增加运行速度的语句: sycn_with_stdio(false)

现在开始总结本周所学STL的应用:
引用字符串
1.string (C++的字符串类型)
.string 表示可变长度的字符序列
字符串是对象
…string 类支持字符串对象的各种操作
各种初始化方式
字符串之间的复制、比较、连接
查询字符串长度和判断字符串是否为空
访问字符串中的单个字符
…使用string 类要包含头文件

其实string即可理解为引出字符串,并可对字符串进行一系列的操作 如:
在这里插入图片描述
此图表是对string的常用操作

读写string对象有三种方式:使用标准库中的iostream 可以使用循环读取未知量的string对象 getline()函数从指定输入流中读取内容,遇到换行符为止。

empty()函数判断string对象是否为空
size()函数返回string对象的长度,即对象中字符的个数
可以用关系运算符比较两个字符串对象,两个string相等意味着它们的长度相同,并且所包含的字符也完全相同,字符串的大小关系依照字典顺序定义且区分大小写字母
允许把一个string对象的值赋给另一个string对象,也可以为string对象赋一个字符串字面值常量
用下标运算符可以访问string对象中指定位置的字符,string对象s的下标范围从0到s.size()-1

经典程序举例:
#include
using namespace std;
int main()
{
string s1, s2;
string s3 = “Hello, World!”;
string s4("I am ");
s2 = “Today”;
s1 = s3 + " " + s4;
s1 += " 5 “;
cout << s1 + s2 + “!” <<endl;
cout <<“Length of s1 is :” << s1.size() << endl;
for (int i = 0; i < s1.size(); ++i)
cout << s1[i] <<” ";
}
/*
Hello, World! I am 5 Today!
Length of s1 is :22
H e l l o , W o r l d ! I a m 5
Process returned 0 (0x0) execution time : 0.167 s
Press any key to continue.
*/

排序问题中所能遇到的相关内容:
栈和队列可以对比理解,有很多的相似之处,也有绝对区别
1.栈(stack)
stack是一种先进后出(First In Last Out, FILO)的数据结构,它只有一个出口,只能操作最顶端元素。
定义:
stack<data_type> stack_name;
如:stack s;
操作:
empty() – 返回bool型,表示栈内是否为空 (s.empty() )
size() – 返回栈内元素个数 (s.size() )
top() – 返回栈顶元素值 (s.top() )
pop() – 移除栈顶元素(s.pop(); )
push(data_type a) – 向栈压入一个元素 a(s.push(a); )
**2.**队列(queue)
queue是一种先进先出(First In First Out, FIFO)的数据结构,从底端加入元素,从顶端取出元素
定义:queue <data_type> queue_name;
如:queue q;
操作:
empty() – 返回bool型,表示queue是否为空 (q.empty() )
size() – 返回queue内元素个数 (q.size() )
front() – 返回queue内的下一个元素 (q.front() )
back() – 返回queue内的最后一个元素(q.back() )
pop() – 移除queue中的一个元素(q.pop(); )
push(data_type a) – 将一个元素a置入queue中(q.push(a); )
3.vector动态数组
定义:vector <data_type> vector_name;
如:vector v;
操作:
empty() – 返回bool型,表示vector是否为空 (v.empty() )
size() – 返回vector内元素个数 (v.size() )
push_back(data_type a) 将元素a插入最尾端
pop_back() 将最尾端元素删除
v[i] 类似数组取第i个位置的元素(v[0] )
4.sort排序(超级经典,个人很喜欢用)
头文件: #include
sort(begin, end);
sort(begin, end, cmp);
小例子:
int num[] = {1,5,6,2,9};
1) sort(num, num + 5);//默认从小到大排序num[] = {1,2,5,6,9};
2) bool cmp(int a, int b){
return a > b;
}
sort(num, num + 5, cmp); //num[] = {9,6,5,2,1};

动态数组和sort排序的小应用:
#include<bits/stdc++.h>
using namespace std;

int main(){
sync_with_stdio(false);
int a[10];
vector b;
for(int i=0;i<5;i++)
{
cin>>a[i];
b.push_back(a[i]);
}
sort(a,a+5);
sort(b.begin(),b.end());
for(int i=0;i<5;i++)
cout<<a[i]<<" “;
cout<<endl;
for(int i=0;i<5;i++)
cout<<b[i]<<” ";
return 0;
}

5.优先序列(priority_queue)
一个拥有权值观念的queue,自动依照元素的权值排列,权值最高排在前面。缺省情况下,priority_queue是利用一个max_heap完成的

头文件: #include
定义:priority_queue <data_type> priority_queue_name;
如:priority_queue q;//默认是大顶堆
操作:
q.push(elem) 将元素elem置入优先队列
q.top() 返回优先队列的下一个元素
q.pop() 移除一个元素
q.size() 返回队列中元素的个数
q.empty() 返回优先队列是否为空
举一个特别喜欢的例子,利用这种方式可以满足我们对于一些特殊要求的求解。
int main(){
priority_queue s;
coord a;
a.x = 3, a.y = 2;
s.push(a);
a.x = 1, a.y = 2;
s.push(a);
a.x = 2, a.y = 2;
s.push(a);
cout << "Size: " << s.size() << endl;
cout << "Top: " << s.top().x << ", " << s.top().y << endl;
s.pop();
cout << "Top: " << s.top().x << ", " << s.top().y << endl;
return 0;
}
在这里插入图片描述
解释一下:第一个输出代表着三个元素
第二个输出第一个元素
第三个输出因为中间使用了 s.pop();所以移到下一元素也就是输出第三个元素

排序后我们对于重复的元素和元素所在的位置又可能提出一些要求,那么我这周又学习了去重unique upper_bound lower_bound 来对排序好的数据进行相关操作。我将依次介绍相关用法。
1.去重unique
iterator unique(iterator begin,iterator);
iterator unique(iterator begin,iterator end,bool MyFunc);
参数列表中前两个参数都是迭代器,表示对区间[it_1,it_2)内进行去重。(区间为左闭右开)。
最后一个参数是元素是否相等的判定函数。
返回值是指向最后一个元素的下一个元素的迭代器。

补充一个知识点:生成排列
头文件: #include
bool next_permutation(begin, end);
改变区间内元素的顺序,产生下一个排列。
bool prev_permutation(begin, end);
产生前一个排列。
end为最后一个元素的下一个位置。

2.upper_bound 和 lower_bound的使用方法
upper_bound(begin, end, value);
返回>value的元素的第一个位置。

lower_bound(begin, end, value);
返回>=value的元素的第一个位置。

num[] = {1,2,2,3,4,5};
lower_bound(num, num + 6, 2)为num + 1
upper_bound(num, num + 6, 2)为num + 3 //注意理解这种说法

举个例子:
#include<bits/stdc++.h>
using namespace std;

int main(){
sync_with_stdio(false);
int a[10] = {1,3,5,2,4,6,7,5,2,5};
sort(a, a + 10);
for (int i = 0; i < 10; ++i) cout<<a[i]<<" “; //排序从小到大
int *s, *e;
s = lower_bound(a, a + 10, 5); // *此时这个s所指地址为排序后元素的地址 此时的s为第六个元素的地址
e = upper_bound(a, a + 10, 5); //此时e的地址为第九个元素的地址
cout<<e-s<<endl; //地址-地址得数字3(中间隔了三个元素所以是3)
while(s!= e){
cout<<*s++<<” "; //重新排序后三个5连着排在一起所以输出三个5
}
cout<<endl;
cout<<*e<<endl;
return 0; //e为第九个元素的地址,即为数6的地址,所以输出6
}
在这里插入图片描述
这个结果特别有意思,注意理解.

在此又学习了两种排序方式,这种排序方法我们可以让数据按照我们想要的方式进行排序,相对从前固定的排序更加灵活。
1.set 和 multiset
set 和 multiset会根据特定的排序准则,自动将元素排序,两者的不同之处在于multiset可以允许元素重复而set不允许元素重复。‘
在这里插入图片描述
set和multiset 简单应用
操作:
s.insert(elem) – 安插一个elem副本,返回新元素位置。
s.erase(elem) – 移除与elem元素相等的所有元素,返回被移除 的元素个数。
s.erase(pos) – 移除迭代器pos所指位置上的元素,无返回值。
s.clear() – 移除全部元素,将整个容器清空。

迭代器举例:
multiset :: iterator pos;
for(pos = s.begin(); pos != s.end(); pos++)
… …
set和multiset 简单应用
操作:
s.size() – 返回容器大小。
s.empty() – 返回容器是否为空。
s.count(elem) – 返回元素值为elem的元素的个数。
s.lower_bound(elem) – 返回 元素值>= elem的第一个元素位置。
s.upper_bound(elem) – 返回元素值 > elem的第一个元素的位置。
以上位置均为一个迭代器。
s.begin() – 返回一个双向迭代器,指向第一个元素。
s.end() – 返回一个双向迭代器,指向最后一个元素的下一 个位置

2.map和multimap
所有元素都会根据元素的键值自动排序,map的所有元素都是pair,pair的第一个元素被视为键值,第二个元素为实值。map不允许两个元素有相同的键值,但multimap可以。

头文件: #include
定义:map <data_type1, data_type2> map_name;
如:map <string, int> m;//默认按string由小到大排序
操作:
m.size() 返回容器大小
m.empty() 返回容器是否为空
m.count(key) 返回键值等于key的元素的个数
m.lower_bound(key) 返回键值等于key的元素的第一个可安插 的位置
m.upper_bound(key) 返回键值等于key的元素的最后一个可安 插的位置

map和multimap简单应用
操作:
m.begin() 返回一个双向迭代器,指向第一个元素。
m.end() 返回一个双向迭代器,指向最后一个元素的下一个 位置。
m.clear() 讲整个容器清空。
m.erase(elem) 移除键值为elem的所有元素,返回个数,对 于map来说非0即1。
m.erase(pos) 移除迭代器pos所指位置上的元素。
直接元素存取:
m[key] = value;
查找的时候如果没有键值为key的元素,则安插一个键值为key的新元素,实值为默认(一般0)。

贪心算法
这周所接触的贪心算法更多的是教我们用最简单的方法解决题目,这是一种算法,但目前在我看来这是一种思维,一种简洁思维,毕竟我们总不能用最普通的方法去解决问题一样,例如我们的数组,循环等方法就是为了解决复杂而又无意义的运算的。

STL简单运用,现在只学了一小部分,从string字符串开始引出对于字符串的相关操作,栈,队列,排序,优先队列都是用来排序。而去重和位置寻找问题的解决思路也相继出现。简单的排列后又学了自定义排列顺序的排列方法。

这周的学习下来,我深深刻刻的体会到了自己到底有多菜,啥都不会,甚至听不懂,但毕竟选了ACM,就要坚持下去。我就喜欢“明知山有虎,偏向虎山行”。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_51465502/article/details/114755269

智能推荐

uncategorizedsqlexception异常解决方法_Esther_Lee的博客-程序员宅基地_uncategorizedsqlexception

人员信息管理系统在做这个项目的日志管理模块的时候,遇到一个错误,如图在显示日志的界面结果一栏显示:uncategorizedsqlexception搜索解决方案的时候,都说是字段类型对不上所导致的错误,于是检查了mapper文件,数据库以及实体类,感觉没有什么错误。然后在对console窗口检查种发现,result一栏好像无法写入,因为自己的result一栏默认是“成功”,所以怀疑是数据...

【笔记】Java并发编程之美-Java并发包中原子操作类原理剖析_Ethan_997的博客-程序员宅基地

原子变量操作类AtomicLongJUC并发包中包含有Atomiclnteger、AtomicLong和AtomicBoolean等原子性操作类,它们的原理类似,本章讲解AtomicLong类。AtomicLong是原子性递增或者递减类,其内部使用Unsafe来实现。AtomicLong类就是通过BootStarp类加载器进行加载的,故可以通过Unsafe.getUnsafe()方法获取到Unsafe类的实例。递增和递减操作代码都是通过调用Unsafe的getAndAddLong方法来实现操作,这个

BZOJ 3073: [Pa2011]Journeys 线段树优化最短路_BlackJack_的博客-程序员宅基地

3073: [Pa2011]JourneysTime Limit: 20 Sec  Memory Limit: 512 MBSubmit: 243  Solved: 80[Submit][Status][Discuss]DescriptionSeter建造了一个很大的星球,他准备建造N个国家和无数双向道路。N个国家很快建造好了,用1..N编号,但是他发现道路实在太多

SPOJ GCD Extreme(推导+筛法)_Miracle_ma的博客-程序员宅基地

T次询问,求∑n−1i=1∑nj=i+1gcd(i,j)T次询问,求\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}gcd(i,j) T有2W,反正反演是T了,虽然感觉O(Tsqrt(n))能过T有2W,反正反演是T了,虽然感觉O(Tsqrt(n))能过 如果固定j,那么就是求T(j)=∑j−1i=1gcd(i,j)如果固定j,那么就是求T(j)=\sum_{i=1}^{j-1}

随便推点

osg动态加载模型不显示_探索未知种族之osg类生物---呼吸函数frame总结(单线程模式)..._胃泰小胃君的博客-程序员宅基地

好。到这里我们就算是完成了对osg::frame的整体介绍(针对单线程的),下面我们就来整体的总结一下fame函数的整个流程。OSG 渲染后台与用户层的接口是摄像机类(Camera)。场景中至少有一个主摄像机,它关联了一个图形设备(GraphicsContext,通常是窗口),以及一个渲染器(Renderer);我们可以在场景树中(或者别的视图 View 中,对于复合视景器而言)添加更多的摄像机,...

在.NET开发中的单元测试工具之(2)——xUnit.Net_KINGSEA_168的博客-程序员宅基地

原文地址:http://zhoufoxcn.blog.51cto.com/792419/1172320在上一篇《在.NET开发中的单元测试工具之(1)——NUnit》中讲述了如何使用NUnit在.NET开发中进行单元测试以及NUnit的一些缺点,今天将讲述如何使用xUnit.Net来进行单元测试。xUnit.Net介绍xUnit.net的创造者的创造者是Jim 

unity EditorGUILayer绘制报错_weixin_30312563的博客-程序员宅基地

最近在开发一个可视化工具的时候,遇到了一个代码错误,小小的记录一下具体的报错信息:ArgumentException: Getting control 0's position in a group with only 0 controls when doing Repaint A从Unity的报错信息上我们可以得知在OnGUI绘制的时候,它找不到可控的位置。经过查找和验证发现一个...

散射机制_Cherylzzx的博客-程序员宅基地

主要的散射机制: 升学形变散射 声学波压电散射 极性光学声子散射 合金无需散射 界面粗糙度散射 位错散射 调制掺杂的远程散射合金无序散射和调制掺杂的远程散射和势垒层的性质有关 界面粗糙度散射和异质界面的性质有关。压势垒层调制掺杂散射调制掺杂异质结中电子迁移率高的原因是而为电子气和施主杂质在空间上分离,从而降低了库伦散射的作用GaN HEMT中没有电离杂质对于的库伦散射,所以具有...

防止form表单重复提交的X种方法_0945v1的博客-程序员宅基地_防止表单重复提交

Form表单重复提交是在多用户Web应用中最常见、带来很多麻烦的一个问题。有很多的应用场景都会遇到重复提交问题,比如:(1)点击提交按钮两次。(2)点击刷新按钮。(3)使用浏览器后退按钮重复之前的操作,导致重复提交表单。(4)使用浏览器历史记录重复提交表单。(5)浏览器重复的HTTP请求。(6)用户提交表单时可能因为网速的原因,或者网页被恶意刷新,致使同一条记录重复插入到数...

推荐文章

热门文章

相关标签