一 定义
set A;
二 用法
A.insert(item);
A.earse(item); //删除元素item
A.clear(); //清空set
A.empty();
A.size()
A.find(k);
A.lower_bound(k) //返回第一个大于k的元素的下标。
A.upper_bound(k)
A.count(1) //容器中出现1的次数
A.end(); // 表示未找到。
set集合中的元素不重复，可以用来解决去除重复一类的题目,如：移除重复节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| ListNode* removeDuplicateNodes(ListNode* head) {
set<int>s;
ListNode* pre = nullptr, *cur = head;
while(cur) {
if(s.find(cur->val) != s.end()) {
pre->next = cur->next;
}
else {
s.emplace(cur->val);
pre = cur;
}
cur = cur->next;
}
return head;
}
|
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
37
38
39
40
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
cout << "set容器大小："<< s.size() <<endl;
cout << "set容器的第一个元素： "<< *s.begin() <<endl;
cout << "set容器最后一个元素： "<< *s.end() <<endl;
cout << "出现1的次数" << s.count(1) <<endl;
set<int> s1;
set<int>::iterator iter;
for(int i=1;i<=5;i++)
{
s1.insert(i);
}
cout << "遍历set1集合:"<<endl;
for(iter = s1.begin();iter!=s1.end();iter++)
{
cout <<*iter <<" ";
}
cout <<endl;
return 0;
}
|
输出结果：
set容器大小：4
set容器的第一个元素： 1
set容器最后一个元素： 4
出现1的次数1
遍历set1集合:
1 2 3 4 5
三 遍历set集合中的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| string s;
cin >> s;
set<char> cache;
int len = s.size();
for(int i=0;i<len;i++)
{
cache.insert(s[i]);
}
set<char>::iterator it;
for(it =cache.begin(); it!=cache.end();it++)
{
cout<< *it <<endl;
}
|
四 习题
HDU 4989
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
37
38
39
40
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
int main()
{
int t;
set<int> n;
ll arr[1000];
ll sum;
while(cin >> t)
{
n.clear();
sum = 0;
for(int i=0;i<t;i++)
cin >>arr[i];
for(int i=0;i<t;i++)
{
for(int j=i+1;j<t;j++)
{
n.insert(arr[i]+arr[j]);
}
}
for(auto x:n)
{
sum+=x;
}
cout << sum <<endl;
}
return 0;
}
|
HDU2094
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<set>
using namespace std;
int main()
{
string s,s1;
set<string>A,B;
int t;
while(cin>>t && t)
{
A.clear();
B.clear();
while(t--)
{
cin >> s >>s1;
A.insert(s);
A.insert(s1);
B.insert(s1);
}
if(A.size()-B.size()==1)
cout <<"Yes"<<endl;
else
cout <<"No"<<endl;
}
return 0;
}
|
LeetCode 3.无重复字符最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: “pwwkew”输出: 3
- 这题的思路是“滑动窗口”，即判断字符串的每一个字符，在set集合中是否存在，若不存在（set.end()）就加入到集合中；若存在，则把字符串左边去掉。
- 每个变量设置得非常巧妙，不用for循环遍历s，而通过index的数量控制循环次数。而cnt留在if中，只有等插入元素到set的时候才有可能改变maxn的值，当进入else去掉集合中的元素时，maxn的值仍没有影响。
- 强制转换集合的类型：(int)set.size()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int lengthOfLongestSubstring(string s) {
set<char>cache;
int index = 0;
int left = 0;
int maxn = 0;
while(index < s.size())
{
if(cache.find(s[index]) == cache.end())
{
cache.insert(s[index++]);
maxn = max(maxn,(int)cache.size());
}
else
{
cache.erase(s[left++]);
}
}
return maxn;
}
|
