算法题中常用的C++功能

集合

无重复字符的最长子串

unordered_set<char> occ;
occ.erase(s[i - 1]);
occ.insert(s[rk + 1]);
occ.count(s[rk + 1]);

优先队列

滑动窗口最大值

priority_queue<pair<int, int>> Q;
Q.push({nums[i + k - 1], i + k - 1});
Q.top()
Q.pop();

• 优先队列自定义比较函数
  前k个高频元素

struct ComparePairFirst {bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) const {return lhs.second > rhs.second;}
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, ComparePairFirst> pq;

双端队列

滑动窗口最大值

deque<int> q;
q.front()
q.back()
q.push_front()
q.pop_front()
q.push_back()
q.pop_back()

排序时自定义比较函数

使用lambda表达式:

auto compare = [](int a, int b) { return a > b; };
std::priority_queue<int, std::vector<int>, decltype(compare)> ascendingPQ(compare);

使用结构体：

sort(intervals.begin(), intervals.end(),[](const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}); //小顶堆

最大数值

#include <climits>
INT_MAX

字符串

追加：

1. 使用运算符 +=：

std::string str = "example";
str += 'a';  // 现在 str 是 "examplea"

2. 使用 append 成员函数：

std::string str = "example";
str.append(1, 'a');  // 现在 str 是 "examplea"

这里，append 函数的第一个参数是追加字符的数量（在这个例子中是1），第二个参数是要追加的字符。

删除：

在C++中，要删除std::string类型的字符串的最后一个字符，可以采用以下几种方法：

1. 使用 pop_back() 方法:

   std::string str = "example";
   str.pop_back();  // 删除最后一个字符，现在 str 是 "exampl"
   

   pop_back()函数直接删除字符串末尾的字符。

2. 使用 erase() 方法:

   std::string str = "example";
   str.erase(str.length() - 1);  // 或者 str.erase(str.end() - 1);
   // 删除最后一个字符，现在 str 是 "exampl"
   

   erase()方法可以删除指定位置的字符或字符范围，这里用来删除最后一个字符。

子串：

std::string str = "Hello, World!";
std::string subStr = str.substr(7, 5);  // 从第7个字符开始，取5个字符长度的子串

元组

腐烂的橘子

queue<tuple<int, int, int>> q;
q.push({i, j, 0});
x = get<0>(ele);

vector

查找

std::vector<int>::iterator pos = std::find(vec.begin(), vec.end(), 3);
if(pos != vec.end()) {std::cout << "找到了元素3" << std::endl;
} else {std::cout << "没有找到元素3" << std::endl;
}int lastElement = vec.back();

创建和初始化赋值：

std::vector<std::vector<int>> table(nums.size() + 1, std::vector<int>(target + 1, 0));

字典map

引入头文件

#include <unordered_map>

定义和初始化

定义一个空的unordered_map：

std::unordered_map<std::string, int> myMap;

或者定义并初始化一些元素：

std::unordered_map<std::string, int> myMap = {{"apple", 1},{"banana", 2},{"cherry", 3}
};

插入元素

使用insert方法插入元素：

myMap.insert({"grape", 4});

也可以使用下标操作符[]插入，如果键不存在则插入，存在则修改其值：

myMap["orange"] = 5;

访问元素

通过键访问对应的值，如果键不存在，使用下标操作符会自动插入默认值（对于内置类型如int，默认为0）：

int value = myMap["apple"];

使用find方法查找键，返回一个迭代器：

auto it = myMap.find("banana");
if (it != myMap.end())
{std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
}
else
{std::cout << "Not found!" << std::endl;
}

更新元素

直接通过下标操作符更新：

myMap["apple"] = 10;  // 如果键存在，则更新其值

删除元素

使用erase方法删除元素，可以通过键或迭代器删除：

myMap.erase("banana");
// 或者
myMap.erase(it);

检查元素存在

使用count方法检查键是否存在：

if (myMap.count("pear"))
{std::cout << "Pear exists in the map." << std::endl;
}
else
{std::cout << "Pear does not exist in the map." << std::endl;
}

或使用find后检查迭代器是否等于end()。

遍历元素

使用范围基础for循环遍历：

for (const auto &pair : myMap)
{std::cout << pair.first << ": " << pair.second << std::endl;
}

int和string转换

字符串解码

stack<string> stk;
stk.push(to_string(mul));
int old_mul = stoi(stk.top()); stk.pop();