1. 首页
  2. 文章中心
  3. Other

【PAT】Learning Notes

98 阅读 0 评论
我是靠谱客的博主 酷酷芝麻，这篇文章主要介绍【PAT】Learning Notes，现在分享给大家，希望可以做个参考。

算法

二分查找

二分查找尽量不要使用递归，使用while循环解决

查找范围内等于value的索引，当退出while循环时，即意味着在vec内没有对应mid的值，返回-1

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
int find(int left,int right,int value){
while(left<=right){
int mid = left+(right-left)/2;
//循环内判断，返回真实值
if (vec[mid]==value) return mid;
else if (vec[mid]>value) right = mid -1;
else left = mid + 1;
}
// 一旦退出循环，则返回-1
return -1;
}

查找范围内大于等于value的索引

复制代码
1
2
3
4
5
6
7
8
9
10
int find(int left,int right,int value){
while(left<right){
int mid = left+(right-left)/2;
if (vec[mid]>=value) right = mid;
else left = mid + 1;
}
//因为是查找大于等于的数，退出循环时，即left==right,就是第一个满足条件的树
return left;
}

查找范围内大于value的索引

复制代码
1
2
3
4
5
6
7
8
9
10
nt find(int left,int right,int value){
while(left<right){
int mid = left+(right-left)/2;
// 注意这里的条件判断
if (vec[mid]>value) right = mid;
else left = mid + 1;
}
return left;
}

另外，在判断大于等于或者是大于时，输入的right索引应当是n，而不是准确查找时的n-1，这样当最终结果返回n时，可以表示在当前数组内没有大于这个值的，超界限了。

STL

vector

只有在vector和string中才允许使用vec.begin()+2 和*(iter+i)的索引方式。map这种可以使用iter++

复制代码
1
2
3
4
5
6
7
//以下时间复杂度均为N
vector <int> vec;
vec.insert(vec.begin()+3,10);
vec.erase(vec.begin()+3);
vec.erase(vec.begin(),vec.end());
vec.clear();

set

set 按照自动递增排序，自动去除重复元素。

复制代码
1
2
3
4
5
6
7
8
9
10
11
//以下时间复杂度均为logN
set <int> set_int;
set_int.insert(10);
set_int.find(10);
// erase 使用iterator删除 时间复杂度O(1)
set_int.erase(set_int.find(10));
// 删除指定范围的
set_int.erase(set_int.find(10)，set_int.end());
// erase 按照值删除,时间复杂度O(logN)
set_int.erase(10);

不去重的set：multiset
去重不排序的set：unordered_set

string

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <string>
using namespace std;
string str;
cout<<str<<endl;
// string 转为字符数组
printf("%sn",str.c_str());
// 拼接
string hello = "Hello";
string world = " World";
string printout= hello+world;
// length() size()
int size = hello.size();
// 插入
hello.insert(hello.begin()+1,world.begin()+2,world.begin()+4);
// 删除
hello.erase(hello.begin()+2);
hello.erase(hello.begin(),hello.end());
hello.erase(1,2);// 删除从1位置开始的2个字符
hello.clear();
//截取
hello.substr(1,2);
//查找字串
string sub_str = "ll";
hello.find(sub_str);
//将从1开头到3的位置用world替代
hello.replace(1,3,world)；
//
hello.replace(string.begin()+1,string.begin()+4,world);

以下代码摘自 string的find函数
其中s.npos 和string::npos 都是常量，为-1，相等时表示不存在该字串

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
find函数返回类型 size_type
string s("1a2b3c4d5e6f7jkg8h9i1a2b3c4d5e6f7g8ha9i");
string flag;
string::size_type position;
//find 函数 返回jk 在s 中的下标位置
position = s.find("jk");
if (position != s.npos)
//如果没找到，返回一个特别的标志c++中用npos表示，我这里npos取值是4294967295，
{
printf("position is : %dn" ,position);
}
else
{
printf("Not found the flagn");
}
}

map

map.find() 进行查找，如果没有找到返回end()
map.count() 如果有，返回1，没有返回0，因为不存在重复的key，所以只存在这两个值。
map默认是按照key的升序排列的

map中的类型为pair类型，使用迭代器取到的first即为key，second即为value
该代码片段摘自C++（十三）— map的排序

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include <vector>
#include<string>
#include<map>
#include <functional> // std::greater
using namespace std;
struct CmpByKeyLength {
bool operator()(const string& k1, const string& k2)const {
return k1.length() < k2.length();
}
};
int main()
{
//1、map这里指定less作为其默认比较函数(对象),就是默认按键值升序排列
// map<string, int> name_score_map;
// 2、可以自定义，按照键值升序排列，注意加载 
// #include <functional> // std::greater
// map<string, int, greater<string>> name_score_map;
//3、按照自定义内容进行排序，比如字符串的长度
map<string, int, CmpByKeyLength> name_score_map;
name_score_map["LiMin"] = 90;
name_score_map["ZiLinMi"] = 79;
name_score_map["BoB"] = 92;
name_score_map.insert(make_pair("Bing", 99));
name_score_map.insert(make_pair("Albert", 86));
map<string, int>::iterator iter;
for ( iter = name_score_map.begin();iter != name_score_map.end();++iter) {
cout << (*iter).first << endl;
}
system("pause");
return 0;
}

map删除时，可以使用erase(iter)和erase(key)的方式
Notice:

  1. 在map将比对参数设置为greater时，需要传入greater
  2. 将key和value存入map的方式 map[key]=value, map.insert(make_pair(key,value))
  3. 之前考虑的都是将value的设置为结构体，单独将value传入vector后进行想要的排序，实际上可以将pair类型整体传入vector，对pair的比较进行重载。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include <vector>
#include<string>
#include<map>
#include <functional> // std::greater
using namespace std;
bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
return a.second < b.second;
}
int main()
{
//1、map这里指定less作为其默认比较函数(对象),就是默认按键值升序排列
map<string, int> name_score_map;
name_score_map["LiMin"] = 90;
name_score_map["ZiLinMi"] = 79;
name_score_map["BoB"] = 92;
name_score_map.insert(make_pair("Bing", 99));
name_score_map.insert(make_pair("Albert", 86));
//输出添加的内容
map<string, int>::iterator iter;
for (iter = name_score_map.begin(); iter != name_score_map.end(); ++iter) {
cout << (*iter).first << endl;
}
cout << endl;
// 将map中的内容转存到vector中
vector<pair<string, int>> vec(name_score_map.begin(), name_score_map.end());
//对线性的vector进行排序
sort(vec.begin(), vec.end(), cmp);
for (int i = 0; i < vec.size(); ++i)
cout << vec[i].first << endl;
system("pause");
return 0;
}

另外，也可以通过完成函数对象，传入sort。

复制代码
1
2
3
4
5
6
7
typedef pair<string,int> PAIR;
struct cmp{
bool operator()(const PAIR& a, const PAIR& b) {
return a.second < b.second;
}
sort(vec.begin(), vec.end(), cmp());

如何实现自定义key，以及比较
按key：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//自定义map的key
typedef struct UrlKey
{
uint64_t dwBussID;
uint64_t dwVersion;
uint64_t dwHashUrl;
}UrlKey;
//自定义map的value
typedef struct UrlValue
{
string strUrl;
}UrlValue;
//map的比较函数
struct cmp_key
{
bool operator()(const UrlKey &k1, const UrlKey &k2)const
{
if(k1.dwBussID != k2.dwBussID)
{
return k1.dwBussID < k2.dwBussID;
}
if(k1.dwVersion != k2.dwVersion)
{
return k1.dwVersion < k2.dwVersion;
}
if(k1.dwHashUrl != k2.dwHashUrl)
{
return k1.dwHashUrl < k2.dwHashUrl;
}
　　　　　　　　
return false;
}
};
map<UrlKey, UrlValue, cmp_key> UrlMap;

按value：

这个就比较麻烦了。大致分为两种方法：

1：再建一个新的map和原先map的key和value正好反过来，但前提是原先的value没有重复。

2：将map转换成vector<pair<> >来排序。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
map<int,int> MMP;
struct CmpByValue {
bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs)const {
return lhs.second < rhs.second;
}
};
int main(){
MMP.insert(make_pair(1,4));
MMP.insert(make_pair(2,3));
MMP.insert(make_pair(3,2));
MMP.insert(make_pair(4,1));
vector< pair<int,int> > V(MMP.begin(),MMP.end());
sort(V.begin(),V.end(),CmpByValue());
for(int i=0 ; i<V.size() ; ++i){
printf("%dn",V[i].second);
}
return 0;
}

DIY Key的比较函数时，需要注意的问题：

stl的关联容器（map，set）的key一般要求提供 < 比较操作。假设我们有一个结构SomeKey：

复制代码
1
2
3
4
5
struct SomeKey
{
int a, b;
};

要想以SomeKey作为std::map的key，需要为这个结构提供operator < 比较操作，比如：

// 实现1

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool operator < (const SomeKey& left, const SomeKey& right)
{
if (left.a < right.a) // 主key
{
return true;
}
else if (left.a == right.a && left.b < right.b) // 次key
{
return true;
}
else
{
return false;
}
}

或者：

// 实现2

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
bool operator < (const SomeKey& left, const SomeKey& right)
{
if (left.a != right.a) // 主key
{
return left.a < right.a;
}
if (left.b != right.b) // 次key
{
return left.b < right.b;
}
return false;
}

这两种实现方式是很常见的了，似乎也没什么好聊的。不过在项目中，我一次又一次地遇到错误的operator < 实现，着实让人吃惊！比如：

// 实现3（错误）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
bool operator < (const SomeKey& left, const SomeKey& right)
{
if (left.a < right.a) // 主key
{
return true;
}
if (left.b < right.b) // 次key
{
return true;
}
return false;
}

或者

复制代码
1
2
3
4
5
6
// 实现4（错误）
bool operator < (const SomeKey& left, const SomeKey& right)
{
return (left.a < right.a || left.b < right.b);
}

queue

复制代码
1
2
3
4
5
6
queue<int> queue_int;
queue_int.push();
queue_int.pop();
queue_int.front();
queue_int.back();

prority_queue

prority_queue 默认优先级：数越小，则优先级越小。

如果定义数小，优先级反而大的priority_queue

复制代码
1
2
3
4
5
6
7
8
9
// 定义一个个位数大的优先级优先级反而小的优先队列
priority_queue<int, vector<int> cmp> pq;
struct cmp {
// true 时，a的优先级比b大
bool operator()(const int a, const int b) const{
return a%10>b%10;
}
};

如果想要定义一个数字大，优先级反而小的

复制代码
1
2
3
4
priority_queue<int, vector<int>,greater<int> >pq;
//否则
priority_queue<int, vector<int>,less<int> >pq;
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct fruit{
string name;
int price;
friend bool operator < (fruit f1,fruit f2){
// 价格很高的优先级大
return f1.price<f2.price;
}
}
priority_queue < fruit > p_q;
//也可以定义结构体函数
struct cmp{
bool operator()(fruit f1,fruit f2){
return f1.price<f2.price;
}
}
// 第二个参数表示priority_queue 底层使用vector的形式存放
priority_queue< fruit, vector<fruit>, cmp> p_q;

priority_queue的用途：贪心算法和优化Dijkstra算法

pair

pair可以直接使用比较操作符，先比较first，后比较second。
可以代替二元结构体

复制代码
1
2
3
4
5
6
pair<int, string> p(5,"haha");
// map 中的使用
map.insert(p);
map.insert(pair<int,string>("wawa",10);
map.insert(make_pair("haha",5);

常用的函数

复制代码
1
2
3
4
5
6
7
8
9
10
#include <algorithm>
max();
min();
abs();
// float
fabs();
swap();
reverse();
fill();

注意 sort只适用 vector，string，deque。set和map自身使用红黑树实现，自身有序。

————————
欢迎关注我的公众号《处理器与AI芯片》

最后

以上就是酷酷芝麻最近收集整理的关于【PAT】Learning Notes的全部内容，更多相关【PAT】Learning内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(65)

相关文章

计算机应用基础创新版,计算机应用基础如何培养学生创新意识
计算机应用基础创新版,计算机应用基础如何培养学生创新意识
计算机的创新知识,创新高中计算机知识学习的策略分析
计算机的创新知识,创新高中计算机知识学习的策略分析
排列组合思维导图_思维模型10 - 排列组合是什么？
排列组合思维导图_思维模型10 - 排列组合是什么？
C++ Primer learning notes #2C++ Learning notes
C++ Primer learning notes #2C++ Learning notes
【PAT】Learning Notes
【PAT】Learning Notes
c++ 学习笔记--class Complex(01)class Complex
c++ 学习笔记--class Complex(01)class Complex
Machine Learning系列实验--SoftMax Regression
Machine Learning系列实验--SoftMax Regression
C++ self-learning notes(4)
C++ self-learning notes(4)

评论列表共有 0 条评论

立即
投稿
返回
顶部