C++刷LeetCode常用容器和函数

一、字符串与数值转换问题：

经常会涉及类型之间转换的问题，可以使用string头文件李的函数

参考：C++中的字符串（String）和数值转换_c++字符串转数字-CSDN博客

string和数值转换	转换类型
to_string(val)	把val转换成string
stoi(s,p,b)	把字符串s从p开始转换成b进制的int
stol(s,p,b)	把字符串s从p开始转换成b进制的long
stoul(s,p,b)	把字符串s从p开始转换成b进制的unsigned long
stoll(s,p,b)	把字符串s从p开始转换成b进制的long long
stoull(s,p,b)	把字符串s从p开始转换成b进制的unsigned long long
stof(s,p)	把字符串s从p开始转换成float
stod(s,p)	把字符串s从p开始转换成double
stold(s,p)	把字符串s从p开始转换成long double

进制转换：进制转换(C++)_c++进制转换-CSDN博客

二、String

 附表：ASCII 表

1、string初始化

string str；      //生成空字符串

string s(str)；   //生成字符串为str的复制品

string s(str, strbegin,strlen)； //将字符串str中从下标strbegin开始、长度为strlen的部分作为字符串初值

string s(cstr, char_len)； //以C_string类型cstr的前char_len个字符串作为字符串s的初值

string s(num ,c)；         //生成num个c字符的字符串

string s(str, stridx)；    //将字符串str中从下标stridx开始到字符串结束的位置作为字符串初值

string s(begin,end);       //以区间beg;end(不包含end)内的字符作为字符串s的初值,即迭代器间的值。

eg:
    string str1;               //生成空字符串
    string str2("123456789");  //生成"1234456789"的复制品
    string str3("12345", 0, 3);//结果为"123"
    string str4("012345", 5);  //结果为"01234"
    string str5(5, '1');       //结果为"11111"
    string str6(str2, 2);      //结果为"3456789"

2、操作函数

关于大小和容量

size()和length();  //返回string对象的字符个数，他们执行效果相同。

max_size();        //返回string对象最多包含的字符数，超出会抛出length_error异常

capacity();        //重新分配内存之前，string对象能包含的最大字符数

eg:
    string s("1234567");
    cout << "size=" << s.size() << endl;           //7
    cout << "length=" << s.length() << endl;       //7
    cout << "max_size=" << s.max_size() << endl;   //4294967294
    cout << "capacity=" << s.capacity() << endl;   //15

关于比较

C ++字符串支持常见的比较操作符（>,>=,<,<=,==,!=），甚至支持string与C-string的比较(如 str<"hello")。在使用>,>=,<,<=这些操作符的时候是根据"当前字符特性"将字符按字典顺序进行逐一得 比较。字典排序靠前的字符小，比较的顺序是从前向后比较，遇到不相等的字符就按这个位置上的两个字符的比较结果确定两个字符串的大小。同时，string ("aaaa") <string(aaaaa)。
另一个功能强大的比较函数是成员函数compare()。他支持多参数处理，支持用索引值和长度定位子串来进行比较。他返回一个整数来表示比较结果，返回值意义如下：0-相等 〉0-大于 <0-小于。

  string s("abcd");
  s.compare("abcd"); //返回0
  s.compare("dcba"); //返回一个小于0的值
  s.compare("ab"); //返回大于0的值
  s.compare(s); //相等

关于添加和插入

 在尾部添加字符 += , append() ,push_back( ) 插入字符insert( ) 串联字符串 +

 s+=str;  //加个字符串
  s+="my name is jiayp";  //加个C字符串
  s+=’a’;  //加个字符
  s.append(str);
  s.append(str,1,3);  //如果str是"iamangel" 就是把"ama"拼接到字符串
  s.append(str,2,string::npos)  //把字符串str从索引值2开始到结尾拼接到s
  s.append("my name is jiayp");
  s.append("nico",5);
  s.append(5,’x’);
  s.push_back(‘a’);  //这个函数只能增加单个字符

---

string a = "1234";
string b = "5678";

 1.在string字符串某一个位置上插入另一个（string）字符串
  insert(int,string&);
  a.insert(0, b); //结果为 a="56781234";
  a.insert(2, b); //结果为 a="12567834";
  insert(int,const char*);
  a.insert(3,"abcd");//结果为 a="123abcd4";
 2.在string字符串某一个位置上插入另一个字符串的前n个字符
  insert(int,const char*,int);
  a.insert(1,"abcd",2); //结果为 a="1ab234";
 3.在string字符串某一位置上插入另一个string字符串（从下标为n的位置开始到结束）
  insert(int,string&,int);
  a.insert(1,b,2); //结果为 a="178234";
 4.在string字符串某一位置上插入另一个(string)字符串（从下标为n的位置开始连续m个字符）
  insert(int,string&,int，int);
  a.insert(2,b,1,2); //结果为 a="126734";
  a.insert(0,b,0,3); //结果为 a="5671234";
  insert(int,const char*,int，int);
  a.insert(2,"5678",1,2); //结果为 a="126734";
 5.在字符串中插入n个字符
  insert(int,int,const char);
  a.insert(2,5,'k'); //结果为 a="12kkkkk34";
  insert(iterator,const char);
  a.insert(a.begin()+3,'k'); //结果为 a="123k4";
  insert(iterator,int,const char);
  a.insert(a.begin()+3,10,'k'); //结果为 a="123kkkkkkkkkk4";
 6.在字符串某个位置插入另一个字符串的某一个区间字符
  insert(iterator,const_iterator_first,const_iterator_last);
  a.insert(a.begin() + 1, b.begin() + 1, b.end() - 1);//结果为 a="167234";

 删除

把字符串清空的方法有三个：s="";s.clear();s.erase();

在字符串末尾删除一个字符 a.pop_back(); //结果为 a="12";

1.删除所有字符 
a.erase(); //结果为 a=""; 
2.从字符串的某一个位置开始删除
 a.erase(n) //从字符串的第n个字符开始删除 
 a.erase(3); //结果为 a="123"; 
 a.erase(5); //结果为 a="12345"; 
 a.erase(0); //等同于a.erase() a=""; 
3.从字符串的某一个位置开始，向后删除m个字符 
a.erase(n,m); //从字符的第n个字符开始删除m个字符 
a.erase(2,3); //结果为 a="126789"; 
a.erase(4,1); //结果为 a="12346789"; 
4.删除迭代器位置处的字符，并返回下一个字符的迭代器
 auot iter=a.erase(a.begin()+1); //结果为 a="13456789"; 
 cout<<*iter<<endl; //结果为 *iter=3 
5.删除迭代器所指向的区间,并返回下一个字符的迭代器 auto iter=a.erase(a.begin()+1,a.end()-2);//结果为 a="189"; 
cout<<*iter<,endl; //结果为 *iter=8; 
6.删除字符时常常与find()函数配合使用(find()函数的用法会在以后写出)
 a.erase(a.find("56"),2); //结果为 a="1234789";

查找 

    string a="123456789abcdefgab";
  	string b="789abc";
  	如果找不到则返回的值为string::npos
  	/*if(a.find('k')==string::npos){cout<<"没有找到"<<endl;}*/
  	1.在字符串中查找某一个字符
  	   (1).从字符串开始位置开始查找
  	   auto s=a.find('a'); //结果为 s=9; 
  	   //表明a在字符串中从左向右第一次出现的位置的下标为9
  	   (2).从字符串某一个位置开始查找
  	   auto s=a.find('a',11); //结果为 s=16
  	   //从字符串下标为11的地方开始查找字符
  	
  	2.在字符串中查找某一个子串
  	   (1).从字符串开始位置开始查找
  	   auto s=a.find("9a");//结果为 s=8; 
  	   //表明9a子串的第一个字符在字符串中从左向右第一次出现的位置下标为8
  	   auto s=a.find(b); //结果为 s=6;
  	   (2).从字符串某一个位置开始查找
  	   auto s=a.find("ab",11); //结果为 s=16
  	   //从字符下标为11的地方开始向后查找
  	
  	3.在字符串中查找子串的前n个字符
  	 auto s=a.find("abcd",11,2); //结果为 s=16;
  	 //解释：在字符串a中查找，子串"abcd"的前2个字符即在字符串a中查找"ab"
  	 //注意 在这个重载函数中，第一个参数只能是char* 类型，而不能是string类型
  	
  	4.find()与rfind()的区别
  	find()是字符串从前向后查找，rfind()是字符串从后向前查找，其他的用法与find()函数类似

三、vector

参考：详解C++STL容器系列（一）—— vector的详细用法和底层原理_c++ vector底层-CSDN博客

1、初始化

#include <vector> 

vector<int> arr1;								//一个空数组

vector<int> arr2 {1, 2, 3, 4, 5};				//包含1、2、3、4、5五个变量

vector<int> arr3(4);							//开辟4个空间，值默认为0

vector<int> arr4(5, 3);							//5个值为3的数组

vector<int> arr5(arr4);							//将arr4的所有值复制进去，和arr4一样

vector<int> arr6(arr4.begin(), arr4.end());		//将arr4的值从头开始到尾复制

vector<int> arr7(arr4.rbegin(), arr4.rend());	//将arr4的值从尾到头复制


sort(nums.begin(), nums.end());  //排序

 2、操作函数

插入与删除

vector<int> arr;
for (int i = 0; i < 5; i++)
{
    arr.push_back(i);  //尾部插入
}
for (int i = 0; i < 5; i++)
{
    arr.pop_back();  //尾部删除
}

arr.emplace(10);  //尾部插入10，比push_back更快

插入insert有三种用法：

• 在指定位置插入值为val的元素。

//在arr的头部插入值为10的元素
vector<int> arr;
arr.insert(arr.begin(), 10);

•  在指定位置插入n个值为val的元素

//从arr的头部开始，连续插入3个值为10的元素
vector<int> arr;
arr.insert(arr.begin(), 3, 10);

• 在指定位置插入区间[start, end]的所有元素

//从arr的头部开始，连续插入arrs区间[begin, end]的所有元素
vector<int> arr;
vector<int> arrs = { 1, 2, 3, 4, 5 };
arr.insert(arr.begin(), arrs.begin(), arrs.end());

erase通过迭代器删除某个或某个范围的元素，并返回下一个元素的迭代器。

vector<int> arr{1, 2, 3, 4, 5};  

arr.erase(arr.begin() + 2);  //删除arr开头往后偏移两个位置的元素，即arr的第三个元素，3

arr.erase(arr.begin(), arr.begin() + 2);  //删除arr.begin()到arr.begin()+2之间的元素，删除两个;即删除arr.begin()而不到arr.begin()+2的元素

 resize

myvector.resize(5);  //将原来有10个数的vector数组，调整为5个数的长度，多余的数删掉，释放内存。  5 < 10   减小数组长度

myvector.resize(8,100);  //将5个数长度的vector数组的长度调整为8，不够的数用100来填补，即增加了3个100。  8 > 5   增大数组长度，指定填充元素

myvector.resize(12);  //将8个数长度的vector数组的长度调整为12，用0默认填补，即增加了4个0。   12 > 8   增大数组长度，未指定填充元素

四、哈希函数

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

unordered_set<int> set;  声明一个没有任何元素的哈希表
unordered_set<int> nums_set(nums1.begin(), nums1.end());  //将数组中的元素存进去
set.insert(sum);  //插入sum
set.erase(c);  //删除
if (set.find(c) != set.end())  //查找

unordered_map <int,int> map;
map.insert(pair<int, int>(nums[i], i)); 
umap[a + b]++;  //也可以直接这样用

五、链表

初始化

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};


ListNode* head = new ListNode(5);  //创建一个节点

六、栈和队列

队列是一种先进先出（First in First out，FIFO）的数据类型。每次元素的入队都只能添加到队列尾部，出队时从队列头部开始出。C++中，使用队列需要包含头文件<queue>。C++中队列的基本操作如下：

1、push() ：入队。在队列尾端添加一个元素，无返回值；
2、pop() ：出队。将队列头部元素删除（出队），无返回值；
3、front() ：获得队列头部元素。此函数返回值为队列的头部元素，常与pop()函数一起，先通过front()获得队列头部元素，然后将其从队列中删除；
4、size() ：获得队列大小。此函数返回队列的大小，返回值是“size_t”类型的数据，“size_t”是“unsigned int”的别名。
5、empty() ：判断队列是否为空。此函数返回队列是否为空，返回值是bool类型。队列空：返回true；不空：返回false。
6、back() ：返回队列尾部元素，就是队列中最后一个进去的元素。

栈是一种后进先出（Last in First out,LIFO）的数据类型。每次元素入栈时只能添加到栈顶，出栈时只能从栈顶元素出栈。C++中，使用栈需要包含头文件<stack>。C++中栈的基本操作如下：

1、push() ：入栈。在栈顶添加一个元素，无返回值；
2、pop() ：出栈。将栈顶元素删除（出队），无返回值；
3、top() ：获得栈顶元素。此函数返回值为栈顶元素，常与pop()函数一起，先通过top()获得栈顶元素，然后将其从栈中删除；
4、size() ：获得栈大小。此函数返回栈的大小，返回值也是“size_t”类型的数据，“size_t”是“unsigned int”的别名。
5、empty() ：判断栈是否为空。此函数返回栈是否为空，返回值是bool类型。栈空：返回true；不空：返回false。

七、二叉树遍历代码

深度优先遍历之递归（推荐）

//当前为前序遍历，更改函数中的三者位置实现后序或者中序
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中  
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

深度优先遍历之迭代

//当前为中序遍历，只需要更改第二个if的三者访问顺序即可
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

 广度优先遍历之递归

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

 广度优先遍历之迭代（推荐）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};