multiset

Multiset in C++ Standard Template Library (STL) | Geeks

valid anafram | leetcode

允许元素重复

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
#include <iostream>
#include <set>
using namespace std;

int main()
{
  multiset<int> myset;
  myset.insert(1);
  myset.insert(2);
  myset.insert(1);
  myset.insert(2);

  auto pos = myset.find(0);
  if(pos == myset.end()) cout << "Not Find" << endl;

  cout << myset.count(1) << endl; // 2

  for(int i : myset) cout << i << " "; cout << endl; // 1 1 2 2 
  myset.erase(myset.find(2));
  for(int i : myset) cout << i << " "; cout << endl; // 1 1 2 
  
  if(myset.empty()) cout << "Empty" << endl;
  myset.erase(1);
  myset.erase(2);
  if(myset.empty()) cout << "Empty" << endl;

  return 0;
}

unordered_set

Unordered Sets in C++ Standard Template Library | Geeks

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
#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
  unordered_set<int> myset;
  myset.insert(1);
  myset.insert(2);
  myset.insert(2);
  cout << myset.size() << endl; // 2
  for(int i : myset) cout << i << " "; cout << endl; // 2 1

  cout << myset.count(0) << endl; // 0
  cout << myset.count(2) << endl; // 1
  if(myset.count(1)==1) cout << "Find" << endl; // Find
  if(myset.find(1) != myset.end()) cout << "Find" << endl; // Find

  myset.erase(2);
  for(int i : myset) cout << i << " "; cout << endl; // 1

  myset.clear();

  return 0;
}

unordered_map

unordered_map in C++ STL | Geeks

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
#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
  unordered_map<char, int> mymap = {{'a', 1}};
  mymap['b'] = 2;
  mymap.insert({'c', 3});
  mymap.insert(make_pair('d', 4));

  for(auto item : mymap)
    cout << item.first << ":" << item.second << " "; cout << endl;
    // d:4 c:3 b:2 a:1 

  auto pos = mymap.find('a');
  if(pos != mymap.end())
    cout << pos->first << ":" << pos->second << " "; cout << endl;
    // a:1

  mymap.erase('a');
  for(auto item : mymap)
    cout << item.first << ":" << item.second << " "; cout << endl;
    // d:4 c:3 b:2

  return 0;
}

list

List in C++ Standard Template Library (STL) | Geeks

string

Strings in C++ | Geeks

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;

int main()
{
  string s = "helloworld";
  cout << s.length() << endl; // 10
  cout << s.size() << endl;   // 10
  for(char c : s) cout << c << " "; cout << endl;
  s.resize(s.size() + 10);
  cout << s.size() << endl;   // 20
  for(char c : s) cout << c << " "; cout << endl;
}
1
2
string s1 = "hello", s2 = "world";
cout << s1 + s2 << endl;

字符串的截取substr()

Substring in C++ | Geeks

1
2
// syntax
substr(size_type pos = 0, size_type n = npos)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string s = "the,sky,is,blue";
// [start, length]
int pre_idx=-1, cur_idx=-1;
while(true){
  cur_idx = s.find(",", cur_idx+1);
  if(cur_idx != string::npos){
    string word = s.substr(pre_idx+1, cur_idx-pre_idx-1);
    cout << word << endl;
    pre_idx = cur_idx;
  }else{
    string word = s.substr(pre_idx+1, s.size());
    cout << word << endl;
    break;
  }
}
// the
// sky
// is
// blue

string find in C++ | Geeks

1
2
// syntax, if not find, return string::npos
find(const CharT *s, size_type pos = 0) -> size_type
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string s = "hello,world,,hello,world";

int index;

index = s.find(",", 0, 1);
cout << index << " " << s[index] << endl; // 5 ,

index = s.find(",", index+1, 1);
cout << index << " " << s[index] << endl; // 11 ,

index = s.find(",", index+1, 1);
cout << index << " " << s[index] << endl; // 12 ,

index = s.find(",", index+1, 1);
cout << index << " " << s[index] << endl; // 18 ,

index = s.find(",", index+1, 1);
cout << index << " " << s[index] << endl; // -1 ,
if(index == string::npos) cout << "Not Found" << endl;

std::string::erase in C++ | Geeks

1
2
// syntax
erase(size_type pos = 0, size_type n = npos)
1
2
3
4
5
6
7
8
string s = "hello,,world";

int index = s.find(",");
s.erase(index, 1);
cout << s << endl; // hello,world

s.erase(5, s.size()-5);
cout << s << endl; // hello

string as stack

1
2
3
4
5
6
7
8
9
10
11
12
13
string s = "";
s.push_back('a');
cout << s.back() << endl; // a
s.push_back('b');
cout << s.back() << endl; // b
s.push_back('c');
cout << s.back() << endl; // c

while(!s.empty()){
  cout << s.back() << " ";
  s.pop_back();
}
// c b a

string 类型可以直接使用关系运算符 ==、!= 进行比较（运算符重载）

1
2
3
string str1 = "zhang", str2 = "zhang";
cout << boolalpha; // 格式化bool输出
cout << (str1 == str2); // true

string to int

1
int a = stoi("314");

std::getline

字符串最后一个单词的长度 | nowcoder

使用 std::getline() 可以读取带空格的输入并写入 string 类型的变量, 可以不使用 char[] 数组来表示字符串.

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    getline(cin, str);
    cout << str << endl;
    return 0;
}

size下溢出

注意各种容器类（包括string和vector）的 size() 方法返回类型为 unsigned long int 类型，当运算得到负数时会发生下溢出

空字符串的size()-1会overflow

1
2
3
string s = "";
cout << s.size() - 1 << endl; // 18446744073709551615, which is not -1 !!!
// size() returns a size_t type value, which is an alias for unsigned long int .

size取负号会下溢出，运算得到负数也会下溢出

1
2
3
4
5
6
7
vector<int> array = {1,2,3,4,5,6};
cout << array.size() << endl;   // 6
cout << -array.size() << endl;  // 18446744073709551610
cout << 5-array.size() << endl; // 18446744073709551615
cout << 6-array.size() << endl; // 0
cout << 7-array.size() << endl; // 1
cout << array.size()-7 << endl; // 18446744073709551615

各种容器的截取

vector

1
2
3
4
vector<int> vec = {0,1,2,3,4,5,6};
vector<int> vec1(vec.begin(), vec.end());
vector<int> vec2(vec.begin(), vec.begin()+3); // 0,1,2,
vector<int> vec3(vec.end()-3, vec.end());     // 4,5,6

string

1
2
3
4
5
6
7
8
9
10
11
12
13
string str = "abcdefg";
cout << str.end() - str.begin() << endl; // 7

auto left=str.begin(), right=str.end();
while(string(left, right).find("e") != string::npos){
    left++;
    cout << string(left, right) << endl;
}
// bcdefg
// cdefg
// defg
// efg
// fg
1
2
3
4
string str = "0123456";
// Truncate the last three characters
string last3 = str.substr(str.size() - 3, 3);
cout << last3 << endl; // 456
1
2
3
string str = "abcdefg";
string sub = string(str.begin()+0, str.begin()+3);
cout << sub; // abc

int

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 <iostream>
#include <vector>
using namespace std;

int main()
{
  int n = 123;
  vector<int> nums;

  while(n != 0){
    nums.push_back(n % 10);
    n /= 10;
  }

  cout << n << endl; // 0
  for(int i : nums) cout << i << " "; cout << endl; // 3 2 1

  n = 123;
  nums.clear();
  while(n != 0){
    nums.insert(nums.begin(),  n % 10);
    n /= 10;
  }

  cout << n << endl; // 0
  for(int i : nums) cout << i << " "; cout << endl; // 1 2 3

  return 0;
}

INT_MAX and INT_MIN

1
2
cout << INT32_MAX << endl; // 2147483647
cout << INT32_MIN << endl; // -2147483648

vector

Vector in C++ STL | Geeks

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
#include <iostream>
#include <vector>
using namespace std;

int main()
{
  vector<int> myvec;
  myvec.push_back(1);
  myvec.push_back(2);
  myvec.push_back(3);
  cout << myvec.size() << endl; // 3
  for(int i : myvec) cout << i << " "; cout << endl; // 1 2 3

  myvec.insert(myvec.begin(), 0);
  myvec.insert(myvec.end(), 4);
  for(auto pos = myvec.begin(); pos != myvec.end(); pos++)
    cout << *pos << " "; cout << endl; // 0 1 2 3 4

  myvec.pop_back();
  for(int i : myvec) cout << i << " "; cout << endl; // 0 1 2 3

  myvec.assign({7,8,9});
  for(int i : myvec) cout << i << " "; cout << endl; // 7 8 9
  myvec.assign(3, 1);
  for(int i : myvec) cout << i << " "; cout << endl; // 1 1 1

  return 0;
}
1
2
3
4
5
6
vector<int>::iterator iter;
vector<int> vec = {1, 2, 3, 4};
// vector<int> vec({1, 2, 3, 4});
for(iter = vec.begin(); iter != vec.end(); iter++){
  cout << *iter << endl;
}
1
2
3
4
5
6
7
8
9
10
11
vector<int> vec1 = {1, 2, 3, 4, 5};

vector<int> vec2(vec1.begin()+1, vec1.end()-1);
for(int i : vec2) cout << i << " "; // 2 3 4

// [start, end) start at 0
vec2.assign(vec1.begin(), vec1.begin()+3);
for(int i : vec2) cout << i << " "; // 1 2 3

vec2.assign(vec1.begin()+3, vec1.begin()+5);
for(int i : vec2) cout << i << " "; // 4 5
  • 返回最大最小元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{ 
  vector<int> nums = {1, 2, 3, 4, 5};
  auto maxPosition = max_element(nums.begin(), nums.end());
  auto minPosition = min_element(nums.begin(), nums.end());

  cout << "maxValue: " << *maxPosition << endl; // 5
  cout << "minValue: " << *minPosition << endl; // 1
  
  return 0;
}
  • Vector求和
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main()
{ 
  vector<int> nums = {1, 2, 3, 4, 5};
  int sum = accumulate(nums.begin(), nums.end(), 0); // 0是初始值
  cout << "sum = " << sum << endl; // 15
  return 0;
}
  • 初始化单个元素
1
2
3
vector<vector<string>> ans;
ans.push_back(vector<string>({"abc"})); // 记得加上{...}
cout << ans.back().back() << endl; // abc
  • 技巧 pair
1
2
3
4
5
6
7
vector<pair<int, char>> vec;
vec.push_back({97, 'a'});
vec.push_back(make_pair(98, 'a'));
vec.push_back({99, 'a'});
cout << vec[0].first << ": " << vec[0].second << endl;
cout << vec[1].first << ": " << vec[1].second << endl;
cout << vec[2].first << ": " << vec[2].second << endl;

102. 二叉树的层序遍历 | Leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr) return vector<vector<int>>();
        queue<pair<TreeNode*, int>> myque;
        vector<vector<int>> ans;
        myque.push({root, 0});
        while(!myque.empty()) {
            auto item = myque.front(); myque.pop();
            auto curNode = item.first;
            int curLevel = item.second;
            if(curNode->left != nullptr) myque.push({curNode->left, curLevel+1});
            if(curNode->right != nullptr) myque.push({curNode->right, curLevel+1});
            if(ans.size() <= curLevel) ans.push_back(vector<int>());
            ans[curLevel].push_back(curNode->val);
        }
        return ans;
    }
};

push_back & emplace_back

C++中push_back和emplace_back的区别

链表

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
#include <iostream>
using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

int main()
{
  int nums[] = {1, 2, 3, 4, 5};
  ListNode *dummyHead = new ListNode, *tail = dummyHead;
  for(int i : nums){
    tail->next = new ListNode(i);
    tail = tail->next;
  }
  ListNode *head = dummyHead->next;

  tail = head;
  while(tail != nullptr) {cout << tail->val << ", "; tail=tail->next;}
}
// 1, 2, 3, 4, 5,

stack

Stack in C++ STL | Geeks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream> 
#include <stack>
using namespace std;

int main() {
  stack<int> stack;
  stack.push(1);
  stack.push(2);
  stack.push(3);
  
  cout << stack.size() << endl; // 3

  while (!stack.empty()) {
    cout << stack.top() <<" ";
    stack.pop();
  }
  // 3 2 1
}

queue

Queue in C++ Standard Template Library (STL)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream> 
#include <queue>
using namespace std;

int main() {
  queue<int> myqueue;
  myqueue.push(1);
  cout << myqueue.back() << endl; // 1
  myqueue.push(2);
  cout << myqueue.back() << endl; // 2
  myqueue.push(3);
  cout << myqueue.back() << endl; // 3

  cout << myqueue.size() << endl; // 3

  while(!myqueue.empty()) {
    cout << myqueue.front() << " ";
    myqueue.pop();
  }
  // 1 2 3 
}

deque

Deque in C++ Standard Template Library (STL) | Geeks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream> 
#include <queue>
#include <stack>
using namespace std;

int main() {
  deque<int> myqueue;
  myqueue.push_back(1);
  cout << myqueue.back() << endl; // 1
  myqueue.push_front(2);
  cout << myqueue.front() << endl; // 2

  cout << myqueue.size() << endl; // 2

  myqueue.pop_back();
  myqueue.pop_front();
}

priority_queue 优先级队列

Priority Queue in C++ Standard Template Library (STL)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream> 
#include <queue>
using namespace std;

int main(){
  priority_queue<int> pque;
  pque.push(3);
  pque.push(1);
  pque.push(5);
  pque.push(4);
  pque.push(2);

  while (!pque.empty()){
    cout << pque.top() << " ";
    pque.pop();
  }
  return 0;
}

大顶堆 (default) 和小顶堆

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 <iostream> 
#include <queue>
using namespace std;

int main(){
  // priority_queue <int, vector<int>, greater<int>> gque;
  priority_queue <int, vector<int>, greater<>> gque; // 小顶堆(top元素最小)
  gque.push(2);
  gque.push(3);
  gque.push(1);
  while(!gque.empty()){
    cout << gque.top() << " ";
    gque.pop();
  } // 1 2 3

  cout << endl;
  
  // priority_queue <int, vector<int>, less<int>> lque;
  priority_queue <int, vector<int>, less<>> lque; // 大顶堆(top元素最大)
  lque.push(2);
  lque.push(3);
  lque.push(1);
  while(!lque.empty()){
    cout << lque.top() << " ";
    lque.pop();
  } // 3 2 1
  
  return 0;
}

例题 23. 合并 K 个升序链表 | leetcode 中使用了优先级队列 (小顶堆)

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
class Solution {
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* dummyHead = new ListNode(-1);
    // 使用优先级队列来创建小顶堆
    priority_queue<pair<int, ListNode*>, 
                  vector<pair<int, ListNode*>>, 
                  greater<pair<int, ListNode*>>> val2node;
    for(auto node : lists) {
      if(node != nullptr)
        val2node.push({node->val, node});
    }

    auto curptr = dummyHead;
    while(!val2node.empty()) {
      auto minval2node = val2node.top(); val2node.pop();
      auto node = minval2node.second;
      curptr->next = node;
      curptr = curptr->next;
      node = node->next;
      if(node != nullptr)
        val2node.push({node->val, node});
    }
    curptr->next = nullptr;
    return dummyHead->next;
  }
};

队列中存放复合类型数据，并自定义排序

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
#include <iostream> 
#include <queue>
using namespace std;

class myComparsion {
public:
  bool operator()(const pair<char, int>& left, const pair<char, int>& right) {
    return left.second > right.second;
  }
};

int main(){
  // 队列中存放复合类型数据，并且自定义排序
  priority_queue<pair<char, int>, vector<pair<char, int>>, myComparsion> mapque;
  mapque.push(pair('b', 2));
  mapque.push(pair('c', 3));
  mapque.push(pair('a', 1));

  while(!mapque.empty()) {
    auto item = mapque.top();
    cout << item.first << ":" << item.second << " ";
    mapque.pop();
  } // a:1 b:2 c:3 

  return 0;
}

sort()

std::sort() in C++ STL | Geeks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
  vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
  for(int i : nums) cout << i << " "; cout << endl; // 3 1 4 1 5 9 2 6
  sort(nums.begin(), nums.end());
  for(int i : nums) cout << i << " "; cout << endl; // 1 1 2 3 4 5 6 9
  sort(nums.begin(), nums.end(), greater<int>());
  for(int i : nums) cout << i << " "; cout << endl; // 9 6 5 4 3 2 1 1

  int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
  int length = sizeof(arr)/sizeof(int);
  for(int i : arr) cout << i << " "; cout << endl; // 3 1 4 1 5 9 2 6
  sort(arr, arr+length);
  for(int i : arr) cout << i << " "; cout << endl; // 1 1 2 3 4 5 6 9
  sort(arr, arr+length, greater<int>());
  for(int i : arr) cout << i << " "; cout << endl; // 9 6 5 4 3 2 1 1
  
  return 0;
}

依据二维数组的第二项对二维数组排序

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
41
42
#include <iostream> 
#include <algorithm>
using namespace std;

// static bool bigger(const vector<int>& lhs, const vector<int>& rhs);
bool bigger(const vector<int>& lhs, const vector<int>& rhs){
  return lhs[1] > rhs[1];
}
// static bool smaller(const vector<int>& lhs, const vector<int>& rhs);
bool smaller(const vector<int>& lhs, const vector<int>& rhs){
  return lhs[1] < rhs[1];
}

int main(){
  // 对二维数组进行排序
  vector<vector<int>> vec2 = {{1,15}, {2, 20}, {3, 10}};
  for(auto vec1 : vec2) cout << vec1[0] << " " << vec1[1] << endl;
  // 1 15
  // 2 20
  // 3 10

  // 依据第二项从大到小排序
  sort(vec2.begin(), vec2.end(), bigger);
  for(auto iter=vec2.begin(); iter!=vec2.end(); iter++){
    cout << (*iter)[0] << " " << (*iter)[1] << endl;
  }
  // 2 20
  // 1 15
  // 3 10

  // 依据第二项从小到大排序
  sort(vec2.begin(), vec2.end(), smaller);
  for(auto iter=vec2.begin(); iter!=vec2.end(); iter++){
    vector<int> vec1 = *iter;
    cout << vec1[0] << " " << vec1[1] << endl;
  }
  // 3 10
  // 1 15
  // 2 20

  return 0;
}

swap()

1
2
swap(a, b);
int temp = a; a = b; b = temp;

reverse()

std::reverse() in C++

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
  string s = "abcdefg";
  reverse(s.begin(), s.begin()+s.size());
  cout << s; // gfedcba
  return 0;
}

gcd & lcm

greatest common divisor & least common multiple

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <numeric>
using namespace std;

int main()
{
  int a = 6, b = 9;
  cout << gcd(a, b) << endl;
  cout << lcm(a, b) << endl;
  return 0;
}
1
2
3
4
PS D:\Code\Cpp> g++ .\test.cpp -o test -std=c++17
PS D:\Code\Cpp> .\test.exe
3
18d

二分查找

Binary Search functions in C++ STL (binary_search, lower_bound and upper_bound)

1
2
3
4
5
6
7
vector<int> nums = {1,2,3,3,3,4};
auto exist = binary_search(nums.begin(), nums.end(), 3);
auto iter_lower = lower_bound(nums.begin(), nums.end(), 3);
auto iter_upper = upper_bound(nums.begin(), nums.end(), 3);
cout << "exist?: " << exist << endl;
cout << "lower bound index: " << iter_lower - nums.begin() << endl;
cout << "upper bound index: " << iter_upper - nums.begin() << endl;