C++中的零碎 - 张天宇的博客

记录算法刷题路上遇到的C++零碎问题和知识，边走边学。

编程规范

1. 语句顺序

示例：

void last(vector<int>& nums, int pos) {
    if (pos >= nums.size()) return;
    int temp = nums[nums.size() - 1];
    for (int i = nums.size() - 1; i > pos; i--) nums[i] = nums[i - 1];
    nums[pos] = 0;
}
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    nums1.push_back(0);
    for (int i = 0; i < nums2.size(); i++) {
        int pos = 0;
        while (nums2[i] >= nums1[pos] && pos <= m + i) {//问题出现了
            pos++;
        }
        if (pos != 0) pos -= 1;
        last(nums1, pos);
        nums1[pos] = nums2[i];
    }
}

这种写法在VSCode上面没有检查出来，正常输出了。但是提交到LeetCode后发现，数组越界。经过仔细检查发现问题出在注释那一行。Pos在本程序是不能等于m+n的，但是当循环执行了最后一次后，pos=m+n再次进入while，先判断的是&&前面的，即出现了nums[pos]=nums[m+n]，导致越界。

因此该语句需要修改为：

1
2
3

while (pos <= m + i && nums2[i] >= nums1[pos]) {
            pos++;
}

类似的还有Java中的字符串先判空再判空串“”。

函数使用

1. vector的基本用法

1. 排序

#include <vector>
#include <algorithm>
vector<int> a;
//排序
sort(a.begin(), a.end());

2. 删除

//删除元素
//1（需要#include <algorithm>）
vector<int>::iterator iter=find(a.begin(),a.end(),3);
a.erase(iter);
//2
a.erase(a.begin()+2);
//3
vector<int>::iterator it = vec.begin();
for(;it != vec.end();){
    if(*it == 5)
        //删除指定元素，返回指向删除元素的下一个元素的位置的迭代器
        it = vec.erase(it);
    else
        //迭代器指向下一个元素位置
        ++it;
}

3. 查找

//查找指定元素位置
vector<int>::iterator iter;
iter = find(nums.begin(), nums.end(), target);
if (iter != nums.end()) resu = distance(nums.begin(), iter);

4. 截取

vector<int> vector{1,2,3,4,5,6,7,8,9};
//截取前4个数
vector<int>::const_iterator first1 = vector.begin();
vector<int>::const_iterator last1  = vector.begin() + 4;
vector<int> cut1_vector(first1, last1);
cout << "\ncut1_vector: ";
for(auto el : cut1_vector) {
    cout << el << " ";
}
//截取后4个数
vector<int>::const_iterator first2 = vector.end() - 4;
vector<int>::const_iterator last2  = vector.end();
vector<int> cut2_vector(first2, last2);
cout << "\ncut2_vector: ";
for(auto el : cut2_vector) {
   cout << el << " ";
}
cout << "\n";

5. 去重

1 2	sort(vector.begin(),vector.end()); vector.erase(unique(vector.begin(),vector.end()), vector.end());

2. 字符串全排列和全组合

// https://blog.csdn.net/nwpubear/article/details/82503917 
// 递归解法，第一个元素拿出来，求出后面的全排列
// 需要注意相同的元素不替换
// 但是只是相同的元素不替换不能保证所有的不重复，还需要去重
// 去重需要先排序，再返回去重index，然后erase即可。
class Solution {
public:
    //递归解法
    vector<string> Permutation(string str) {
        vector<string> ret;
        if(str.size()==0)
            return ret;
        if(str.size()==1){
            ret.push_back(str);
            return ret;
        }
        string str2="";
        str2.insert(str2.end(),str.begin()+1,str.end());
        vector<string> ret2=Permutation(str2);
        ret=changeLoc(str[0],ret2);
        sort(ret.begin(),ret.end());
        auto index=unique(ret.begin(),ret.end());
        ret.erase(index,ret.end());
        return ret;
    }
    vector<string> changeLoc(char c,vector<string> ret2){
        vector<string> ret;
        for(string ss:ret2){
            ss=c+ss;
            for(int i=0;i<ss.size();i++){
                string tmp=ss;
                if(i==0 || c!=tmp[i]){
                    swap(tmp[0],tmp[i]);
                    ret.push_back(tmp);
                }
            }
        }
        return ret;
    }
};

3. unorder_map

//在内部，unordered_map中的元素没有按照它们的键值或映射值的任何顺序排序，而是根据它们的散列值组织成桶以允许通过它们的键值直接快速访问单个元素（具有常数平均时间复杂度）。
//leetcode 49
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> m;
        for (string str : strs) {
            string t = str;
            sort(t.begin(), t.end());
            m[t].push_back(str);
        }
        for (auto a : m) {
            res.push_back(a.second);
        }
        return res;
    }
};
//例子
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
    unordered_map<string, vector<string>> m;
    string strs[] = {"12345", "54321", "ate", "tae"};
    for (auto str : strs) {
        string t = str;
        sort(t.begin(), t.end());
        m[t].push_back(str);
        //即“12345”存了“12345”“54321”
    }
    for (auto a : m) {
        for (auto b : a.second) {
            cout << b << endl;
        }
        cout << "---" << endl;
    }
    return 0;
}

4. 字符串整数互转

long stol(string str) {  
    long result;  
    istringstream is(str);  
    is >> result;  
    return result;  
}
string ltos(long l) {  
    ostringstream os;  
    os<<l;  
    string result;  
    istringstream is(os.str());  
    is>>result;  
    return result;  
}

5. Map的基本用法

5.1 pair类型

//定义和初始化
pair<T1, T2> p;
pair<T1, T2> p(v1, v2);
make_pair(v1, v2)
//取出对象值
p.first
p.second

5.2 map对象

//定义
map<k, v> m;
map<k, v> m(m2);//创建了m2的副本
map<k, v> m(b, e);
//插入
mp[i] = i;
mp.insert(make_pair(i, i));
//查找出现次数
mp.count(i);
//查找key对应的值
map<int, int>::iterator it_find;
it_find = mp.find(0);
//删除元素k，返回删除的元素的个数
m.erase(k)
//删除迭代器p指向的元素，返回类型void
m.erase(p)
//删除迭代器b到e范围内的元素，返回类型void
m.erase(b, e)

6. 绝对值函数

int abs(int i)  //返回整型参数i的绝对值 
double cabs(struct complex znum)  //返回复数znum的绝对值  
double fabs(double x)  //返回双精度参数x的绝对值    
long labs(long n)  //返回长整型参数n的绝对值

7. 字符串切割

1. find函数

原型：size_t find ( const string& str, size_t pos = 0 ) const;
功能：查找子字符串第一次出现的位置。
参数说明：str为子字符串，pos为初始查找位置。
返回值：找到的话返回第一次出现的位置，否则返回string::npos(表示位置不存在的整数)

2. substr函数

原型：string substr ( size_t pos = 0, size_t n = npos ) const;
功能：获得子字符串。
参数说明：pos为起始位置（默认为0），n为结束位置（默认为npos）
返回值：子字符串

3. 按字符切割

vector<string> split(string str, string sp) {
    vector<string> result;
    char *context;
    char *p = strtok(const_cast<char *>(str.data()), sp.data());
    for (p; p != nullptr; p = strtok(nullptr, sp.data())) {
        //char *转string
        char tmp[100];
        strcpy(tmp, p);
        string t = string(tmp);
        result.push_back(t);
    }
    return result;
}

8. 字符串查找系列函数

以下所讲的所有的string查找函数，都有唯一的返回类型，那就是size_type，即一个无符号整数（按打印出来的算）。若查找成功，返回按查找规则找到的第一个字符或子串的位置；若查找失败，返回npos，即-1（打印出来4294967295）。

1. find函数

1
2
3

string st1("babbabab");
cout << st1.find('a') << endl;//1   由原型知，若省略第2个参数，则默认从位置0（即第1个字符）起开始查找
cout << st1.find('a', 0) << endl;//1

2. rfind函数

find()是从指定位置起向前查找，直到串首。

3. find_first_of函数

在源串中从位置pos起往后查找，只要在源串中遇到一个字符，该字符与目标串中任意一个字符相同，就停止查找，返回该字符在源串中的位置；若匹配失败，返回npos。

1
2
3

string str1("bcgjhikl");
string str2("kghlj");
cout << str1.find_first_of(str2, 0) << endl;

4. find_last_of函数

该函数与find_first_of()函数相似，只不过查找顺序是从指定位置向前。

//目标串中仅有字符c与源串中的两个c匹配，其余字符均不匹配
string str("abcdecg");
cout << str.find_last_of("hjlywkcipn", 6) << endl;//5   从str的位置6(g)开始想前找，g不匹配，再找c，c匹配，停止查找，返回c在str中的位置5
cout << str.find_last_of("hjlywkcipn", 4) << endl;//2   从str的位置4(e)开始想前找，e不匹配，再找d,d不匹配，再找c，c匹配，停止查找，返回c在str中的位置5
cout << str.find_last_of("hjlywkcipn", 200) << endl;//5   当第2个参数超出源串的长度（这里str长度是7）时，不会出错，相当于从源串的最后一个字符起开始查找

5. find_first_not_of函数

在源串中从位置pos开始往后查找，只要在源串遇到一个字符，该字符与目标串中的任意一个字符都不相同，就停止查找，返回该字符在源串中的位置；若遍历完整个源串，都找不到满足条件的字符，则返回npos。

1
2
3

string str("abcdefg");
cout << str.find_first_not_of("kiajbvehfgmlc", 0) << endl;//3   从源串str的位置0(a)开始查找，目标串中有a（匹配），再找b，b匹配,再找c，c匹配，再找d，目标串中没有d（不匹配），停止查找，返回d在str中的位置3
//即源串中不在目标串中的第一个元素的位置

6. find_last_not_of函数

find_last_not_of()与find_first_not_of()相似，只不过查找顺序是从指定位置向前。

9. 整数取整

#include<cmath>
//或math.h
cout << floor(4.9)<<endl;	//4
cout << ceil(4.9) << endl;	//5

10. bitset的用法及作用

bitset用于对数字的位进行操作，将32位的数字m转换位bitset类型为：

1 2	#include <bitset> bitset<32> var(m);

10.1 any()

为了测试bitset 对象是否含有被设置为1的位，我们可以使用any()操作。当bitset对象的一位或多个位被设置为1 时any()返回true。

1 2	bitset<32> var(0); cout << var.any() << endl;//0

10.2 none()

相反，如果bitset 对象的所有位都被设置为0 ,则none()操作返回true。

1 2	bitset<32> var(0); cout << var.none() << endl;//1

10.3 count()

返回被设置为1的位的个数。

1 2	bitset<32> var(7); cout << var.count() << endl;//3

LeetCode 11题：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

class Solution {
public:
     int  NumberOf1(int n) {
        return bitset<32>(n).count();
     }
};

10.4 set()

set或者下标将某位单独设置。

1
2
3

bitset<3> var(7);
cout << var.set(0, 0) << endl;//110
var[0]=0;

10.5 test()

测试某一位，test和下标。

1 2	if (bitvec.test(0)) if (bitvec[index])

10.6 reset()

将某一位单独设置为0，reset和下标。

1 2	bitvec.reset(0); bitvec[0] = 0;

10.7 filp()

flip()操作翻转整个bitset对象或一个独立的位。

1
2
3

bitvec.flip(0); // 翻转第一位
bitvec[0].flip(); // 也是翻转第一位
bitvec.flip(); // 翻转所有的位的值

10.8 其他构造方法

//还有两种方法可以构造bitset 对象，它们都提供了将某位初始化为1的方式：
//一种方法是为构造函数显式地提供一个无符号参数。bitset 对象的前N 位被初始化为参数的相应位值，例如：
bitset< 32 > bitvec2( 0xffff );
//将bitvec2 的低16 位设为1
//下面的bitvec3 的定义
bitset< 32 > bitvec3( 012 );
//将第1 和3 位的值设置为1 假设位置从0 开0
//因为 012 在c语言中表示八进制数字12即二进制数字“1010”
//我们还可以传递一个代表0 和1 的集合的字符串参数来构造bitset 对象如下所示
// 与bitvec3 的初始化等价
string bitval( "1010" );
bitset< 32 > bitvec4( bitval );
//bitvec4 和bitvec3 的第1 和3 位都被设置为1 而其他位保持为0
bitvec.set();

数据结构

1. 树的基本操作

参考链接

1.1 树的定义

typedef char DataType;
typedef struct TreeNode{
    DataType data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode;

1.2 树的遍历

1.2.1 前序遍历

递归写法

void PreOrder(const TreeNode *root){
    if (root == NULL){                 //若结点为空
        printf("#");
        return;
    }
    printf("%c ", root->data);        //输出根节点的值
    PreOrder(root->left);             //前序访问左子树
    PreOrder(root->right);            //前序访问右子树
}

非递归写法

如果存在左孩子，就一路将左孩子压入栈，直到叶子节点。分别作top操作访问右孩子。

void PreOrderLoop(TreeNode *root){
    std::stack<TreeNode *> s;
    TreeNode *cur, *top;
    cur = root;
    while (cur != NULL || !s.empty()){
        while (cur != NULL){
            printf("%c ", cur->data);
            s.push(cur);
            cur = cur->left;
        }
        top = s.top();
        s.pop();
        cur = top->right;
    }
}

1.2.2 中序遍历

递归写法

void InOrder(const TreeNode *root){
    if (root == NULL){              //判断节点是否为空
        printf("# ");
        return;
    }
    InOrder(root->left);           //中序遍历左子树
    printf("%c ", root->data);     //访问节点值
    InOrder(root->right);          //中序遍历右子树
}

非递归写法

保存节点自身和它的右子树都没有被访问的节点地址。

cur指针一路沿着最左边往下访问，路过的节点全部压栈，直到遇到空节点。从栈中取出栈顶节点top，输出栈顶结点的值并使cur = top->right，从第一步开始去遍历top的右子树。

void InOrderLoop(TreeNode *root){
    std::stack<TreeNode *> s;
    TreeNode *cur;
    cur = root;
    while (cur != NULL || !s.empty()){
        while (cur != NULL){
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        printf("%c ", cur->data);
        cur = cur->right;
    }
}

1.2.3 后序遍历

递归写法

void PostOrder(TreeNode *root){
    if (root == NULL){
        printf("# ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ", root->data);
}

非递归写法

沿着左子树一路往下走，将路过的节点都压栈，直到走到空节点。然后从栈中看一下栈顶元素（只看一眼，用top指针记下，先不出栈），如果top节点没有右子树，或者last等于top的右孩子，说明top的右子树不存在或者遍历过了，就输出top节点的值，并将栈顶元素pop掉（出栈），反之则是从左子树回到根节点的，接下来要去右子树。

void PostOrderLoop(TreeNode *root){
    std::stack<TreeNode *> s;
    TreeNode *cur, *top, *last = NULL;
    cur = root;
    while (cur != NULL || !s.empty()){
        while (cur != NULL){
            s.push(cur);
            cur = cur->left;
        }
        top = s.top();
        if (top->right == NULL || top->right == last){
            s.pop();
            printf("%c ", top->data);
            last = top;
        }
        else {
            cur = top->right;
        }
    }
}

1.2.4 层序遍历

层序遍历的思路是，创建一个队列，先将根节点（A）入队，然后用front指针将根节点记下来，再将根节点出队，接下来看front节点（也就是刚才的根节点）有没有左孩子或右孩子，如果有，先左（B）后右（C）入队，最后输出front节点的值，只要队列还不为空，就说明还没有遍历完，就进行下一次循环，这时的队头元素（front）则为刚才入队的左孩子（B），然后front出队，再把它的左右孩子拉进来（如果有），因为队列的先进先出性质，B的左右孩子DE是排在C后面的，然后输出B，下一次循环将会拉人C的左右孩子FG，最后因为FG没有左右孩子，一直出队，没有入队元素，队列迟早会变为空，当队列为空时，整颗树就层序遍历完成了，结束循环。

void LevelOrder(TreeNode *root){
    std::queue<TreeNode *> q;
    TreeNode *front;
    if (root == NULL)return;
    q.push(root);
    while (!q.empty()){
        front = q.front();
        q.pop();
        if (front->left)
            q.push(front->left);
        if (front->right)
            q.push(front->right);
        printf("%c ", front->data);
    }
}

其他

1. 指针地址

1	int *p, a = 10; p = &a;

*p表示指针p

&a表示取a的内存地址

p = &a 表示p等于a的内存地址

&*p表示获取指针p的内存地址

*&p表示指向P内存地址的一个指针

编程规范

1. 语句顺序

函数使用

1. vector的基本用法

1. 排序

2. 删除

3. 查找

4. 截取

5. 去重

2. 字符串全排列和全组合

3. unorder_map

4. 字符串整数互转

5. Map的基本用法

5.1 pair类型

5.2 map对象

6. 绝对值函数

7. 字符串切割

1. find函数

2. substr函数

3. 按字符切割

8. 字符串查找系列函数

1. find函数

2. rfind函数

3. find_first_of函数

4. find_last_of函数

5. find_first_not_of函数

6. find_last_not_of函数

9. 整数取整

10. bitset的用法及作用

10.1 any()

10.2 none()

10.3 count()

10.4 set()

10.5 test()

10.6 reset()

10.7 filp()

10.8 其他构造方法

数据结构

1. 树的基本操作

1.1 树的定义

1.2 树的遍历

1.2.1 前序遍历

1.2.2 中序遍历

1.2.3 后序遍历

1.2.4 层序遍历

其他

1. 指针地址

标签