leetcode刷题（C++版本）_c++ 刷题

参考书籍：labuladong算法小抄

一、常见函数：
1 accumulate
常用用途：可以用 + 运算符求出元素序列的和。前两个参数是定义序列的输入迭代器，第三个参数是和的初值；
示例：力扣413题
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if(n < 3) return 0;
        vector<int> dp(n,0);
        for(int i = 2;i < n;++i){
            if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]){
                dp[i] = dp[i - 1] + 1;
            }
        }
        return accumulate(dp.begin(), dp.end(), 0);//求dp序列所有元素之和，累加初值为0

    }
};
2 max
常用用途：求两者的最大值。
示例：力扣198题
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        vector<int> dp(n + 1 ,0);//因为我们下面想要dp从1开始，也就是抢1间房子
        dp[1] = nums[0];
        for(int i = 2;i <= n;++i){
            dp[i] = max(dp[i - 1],dp[i - 2] + nums[i - 1]);//不抢当前房子或者抢当前房子
        }
        return dp[n];
    }
};
3 sort
常用用途：排序。
sort (first, last)    对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。
示例：力扣455题
int findContentChildren(vector<int>& children, vector<int>& cookies) {
sort(children.begin(), children.end());
sort(cookies.begin(), cookies.end());
int child = 0, cookie = 0;
while (child < children.size() && cookie < cookies.size()) {
if (children[child] <= cookies[cookie]) ++child;
++cookie;
}
return child;
}
自定义排序
sort(first,last,cmp) 注意cmp函数如何定义。
示例：力扣406题
class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b){//static关键字不能丢
        if(a[0] == b[0])
            return a[1] < b[1];//身高相同k小的排前面
        return a[0] > b[0];//身高高的排前面
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> ans;
        for(int i = 0; i < people.size(); ++i){
            int pos = people[i][1];
            ans.insert(ans.begin() + pos, people[i]);
            
        }
        return ans;
    }
};
力扣954题 sort(vals.begin(), vals.end(),[](int a,int b){return abs(a)<abs(b);});
class Solution {
public:
    bool canReorderDoubled(vector<int> &arr) {
        unordered_map<int, int> cnt;
        for (int x : arr) {
            ++cnt[x];
        }
        if (cnt[0] % 2) {
            return false;
        }

        vector<int> vals;
        vals.reserve(cnt.size());
        for (auto &[x, _] : cnt) {
            vals.push_back(x);
        }
        sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });

        for (int x : vals) {
            if (cnt[2 * x] < cnt[x]) { // 无法找到足够的 2x 与 x 配对
                return false;
            }
            cnt[2 * x] -= cnt[x];
        }
        return true;
    }
};
4 substr
常用用途：复制子字符串，要求从指定位置开始，并具有指定的长度。
•    形式 ： s.substr(pos, len)
•    返回值：string，包含s中从pos开始的len个字符的拷贝（pos的默认值是0，len的默认值是s.size() - pos，即不加参数会默认拷贝整个s）
示例：力扣139题
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1,false);
        dp[0] = true ;//
        for(int i = 1;i <= n;++i){
            for(const string & word: wordDict){
                int len = word.size();
                if(i >= len && s.substr(i - len,len) == word){
                    dp[i] = dp[i] || dp[i - len];
                }
            }
        }
        return dp[n];
    }
};
5 max_element系列
C++max_element（）min_element（）函数简介8 赞同 · 4 评论文章
6 make_pair
make_pair(a,b); //a,b可以是同类数据 也可以是不同类型数据
常用用途：两个数据组合成一个数据，两个数据可以是同一类型或者不同类型。
C++标准程序库中凡是“必须返回两个值”的函数， 都会利用pair对象。
class pair可以将两个值视为一个单元。容器类别map和multimap就是使用pairs来管理其健值/实值(key/value)的成对元素。
pair被定义为struct,因此可直接存取pair中的个别值.。
两个pairs互相比较时， 第一个元素正具有较高的优先级.。
示例：力扣474题
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));
        for(const string & str: strs){
            auto [count0,count1] = count(str);
            for(int i = m;i >= count0;--i){//i表示装0的背包 j表示装1的背包
                for(int j = n;j >= count1;--j){
                    dp[i][j] = max(dp[i][j],dp[i - count0][j - count1] + 1);
                }
            }
        }
        return dp[m][n];

    }
    //辅函数 求得每个字符串中含有的0和1的数量
    pair<int,int> count(const string & s){
        int count0 = s.size(),count1 = 0;
        for(const char & c: s){
            if(c == '1'){
                ++count1;
                --count0;
            }
        }
        return make_pair(count0,count1);
    }
};
6 push_back与emplace_back
作用：这两个函数都是在Vector最后添加一个元素（参数为要插入的值）。
不同点是emplace_back能就地通过参数构造对象，不需要拷贝或者移动内存，相比push_back能更好地避免内存的拷贝与移动，使容器插入元素的性能得到进一步提升。在大多数情况下应该优先使用emplace_back来代替push_back。
示例：力扣241题 以下push_back都可以换成emplace_back（）。
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        //存储中间值
        vector<int> count;
        for(int i = 0;i < expression.size();++i){
            char c = expression[i];
            // 找到运算符
            if(c == '+' ||c == '-' ||c == '*'){
                // 运算符左边的运算结果
                vector<int> left = diffWaysToCompute(expression.substr(0,i));
                // 运算符右边的运算结果
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
               // 左右两边继续运算 
                for(int& l : left){
                    for(int& r : right){
                        switch(c){
                            case '+':
                                count.push_back(l + r);
                                break;
                            case '-':
                                count.push_back(l - r);
                                break;
                            case '*':
                                count.push_back(l * r);
                                break;                   
                        }
                    }
                }
            }
        }
        if(count.size() == 0) {
            count.push_back(stoi(expression));
        }
        return count;
    }
};
7 stoi
作用将string字符串转换为int类型。
int stoi (const string& str, size_t* idx = 0, int base = 10)
str:表示所要转化的字符串
idx:表示想要str中开始转化的位置，默认为从第一个字符开始。
base:表示要用的进制（如2进制、16进制，默认为10进制）转化为int类型十进制数字。
示例见上题倒数第五行代码处。
8 map.count
用法：map_name.count(key)
功能：如果在映射容器中存在带有键K的元素，则该函数返回1。如果容器中不存在键为K的元素，则返回0。
示例：力扣932
class Solution {
    map<int,vector<int>> memo;//建立map
public:
    vector<int> beautifulArray(int n) {
        if(memo.count(n)){//如果map中存在带有key = n的元素，则返回其value。
            return memo[n];
        }

        vector<int> res(n);
        if(n == 1) res[0] = 1;
        else
        {
            int t = 0;
            for(int &x : beautifulArray((n + 1)/2)) 
            {
                res[t++] = 2 * x - 1;
            }
             for(int &y : beautifulArray(n/2))
            {
                res[t++] = 2 * y;           
            }

        }
        memo[n] = res;
        return res;
    }

};
9 erase
（1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
（2）erase(position);删除position处的一个字符(position是个string类型的迭代器)
（3）erase(first,last);删除从first到last之间的字符（first和last都是迭代器）
示例：力扣383
class Solution {
public:
    bool canConstruct(string& ransomNote, string& magazine) {
        for(int j = 0;j < magazine.size();++j){
            for(int i = 0;i < ransomNote.size();++i){             
                if(ransomNote[i] == magazine[j]){
                    ransomNote.erase(ransomNote.begin() + i);// ransomNote删除这个字符
                    break;
                }            
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
        }
    
};
10 swap
交换函数，常用于交换数组中两个数。
示例：力扣344
class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0,j = s.size() - 1;i < s.size()/2; i++, j--){
            swap(s[i],s[j]);
        }
    }
};
11 reverse
逆序（反转），常用于数组，字符串，容器等。
reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数没有返回值
vector<int> v = {5,4,3,2,1};
reverse(v.begin(),v.end());//v的值为1,2,3,4,5
这里要说一下end,它是返回的末尾元素再下一个元素的迭代器。它不指向最后一个元素，因此要获取我们可以使用的最后一个元素vector::end()-1。
示例：力扣541
class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0;i < s.size();i += (2 * k)){
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if(i + k <= s.size()){
                reverse(s.begin() + i,s.begin() + i + k);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s.begin() + i,s.begin() + s.size());
        }
        return s;
    }
};
12 resize
语法 resize（n） 重构容器大小
如果n小于当前容器的大小，则将内容减少到其前n个元素，并删除超出范围的元素（并销毁它们）。
如果n大于当前容器的大小，则通过在末尾插入所需数量的元素来扩展内容，以达到n的大小。如果指定了val，则将新元素初始化为val的副本，否则将对它们进行值初始化。
如果n也大于当前容器容量，将自动重新分配已分配的存储空间
示例 剑指offer 05
class Solution {
public:
    string replaceSpace(string s) {
        int n = s.size();
        int count = 0;
        for(int i = 0;i < n;++i){
            if(s[i] == ' ') count++;
        }
        // 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
        s.resize(n + count * 2);
        int newSize = s.size();
        for(int i = newSize - 1,j = n - 1;j < i;i--,j--){
            if(s[j] != ' '){
                s[i] = s[j];
            }else{
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
         }
         return s;
    }
};
13 pop_back与erase
erase（）可以删除由一个iterator指出的元素，也可以删除一个指定范围的元素。
iterator erase (const_iterator position);//删除指定位置元素
iterator erase (const_iterator first, const_iterator last);//删除起始到结束一段元素
pop_back（）删除容器内的最后一个元素，容器的size减1.
示例：力扣151
class Solution {
public: