今天我练习了力扣的一些题目，感觉收获很多。

基础掌握（更新中）

1 心里有数

$\bigstar$的几次方是$1s$？

$\bigstar$在写题的时候要注意特殊的数字，如$0、1$等。

$\bigstar$对二维数组$arr$怎么遍历呢？

1
2
3
for (int i = 0; i < arr.size(); i++) {
    for (int j = 0; j < arr[0].size(); j++)
}

二维数组$arr$初始化：

1
vector<vector<int>>arr(n,vector<int>(m,0));

$\bigstar$注意，在分割字符串的时候，若一定要将字符串s分割成两个字符串，那么遍历的时候$i<n-1，j=i+1$。像这样，而不是$i<n$，是$i<n-1$，这个千万不能忽略，很重要！！！

1
2
3
for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++)
}

$\bigstar$double类型的数字与整型、double类型等不同类型的数字比大小，直接用大于小于等于号即可，不用担心有什么偏差。

$\bigstar$求一个题目的一些数字的和$sum$的时候，请把$sum$设置为long long类型！

2 一些固定数字

$2^{31}-1=2147483648-1$

3 数据结构范围

int的取值范围是$[-2^{31},2^{31}-1]，2^{31}=2147483648$，大概是$2 \times10^9$。

long long的取值范围在$10^{18}$，具体多少就不说了。

4 返回一个数组

1
return [1,2];

5 问句表达式

1
a==b+c? true:false;

6 位运算

异或^

7 计算一段数据中不重复数字的个数

7.1 用set

1
2
3
4
5
set<int>st;
for(int i=0;i<nums.size();i++){
    st.insert(nums[i]);
}
cout<<st.size()<<endl;

7.2 用unordered_map

1
2
3
4
5
unordered_map<int>mp;
for(int i=0;i<nums.size();i++){
	mp[nums[i]]++;
}
cout<<mp.size()<<endl;

7.3 常见应用

**注意！有时候set好用一点，有时候unordered_map好用一点！不一定只用set。**例如2841. 几乎唯一子数组的最大和（详细题解在leetcode-practice-0727的博客里面），因为可能涉及到删除元素，set只能删除所有值为$x$的元素（插入很多个值为$x$的元素，但set里只会显示一个，因此删除也是删除所有值为$x$的元素），但是这一题只要删除一个就行；因此，用map更好一点！

8 常见函数

8.1 绝对值函数

1
abs(x)

8.2 大写字母转小写字母函数

1
tolower(char x)

8.3 sort函数的用法

$\bigstar$可参考博客C++/C sort函数用法（详细)，cmp的构造

$\bigstar$cmp的构造：

1
2
3
4
5
bool cmp(int i,int j){
	return i>j；
}
int a[100]={1, 51 , 65 , 1 , 8 , 9 , 8 , 52 , 89 , 21 };
sort(a,a+100,cmp);

$\bigstar$结构体构造

8.4 reduce函数

$\bigstar$默认求和：

1
2
3
vector<int> nums = {1, 2, 3, 4, 5};
// 默认加法，无初始值（从0开始累计）
int sum = std::reduce(nums.begin(), nums.end());

$\bigstar$求乘法：

1
2
3
4
std::vector<int> nums = {1, 2, 3, 4, 5};
// 指定初始值1，乘法操作
int product = std::reduce(nums.begin(), nums.end(), 
                              1, std::multiplies<>());

9 字符串相关

$\bigstar$小写$a:97$

大写$A:65$

即小写字符的$ASCII$码大于大写字符

$\bigstar$大小写之间的$ASCII$码相差$32$；

则若想将字符$x=A$变成小写的$a$，那么可以这样

1
2
char x='A';
x=x+32

$\bigstar$遍历字符串$s$

1
for(auto c:s)

$\bigstar$一共有$26$个字母，则第$i$个大写字母的$ASCII$码表示为$65+i-1$

$\bigstar$一堆字符中，我只想找出大写字母，怎么办？

1
if(c>=65&&c<=65+26-1)

虽然$c$是字符，但是可以直接和数字相比，可能它可以直接转换为$ASCII$码吧。

10 STL相关

10.1 string

10.1.1 函数

设字符串为$s$。

$\bigstar$s.length()复杂度为$O(1)$

$\bigstar$s.back()返回字符串最后一个字符，复杂度为$O(1)$

$\bigstar$s.find()最坏时间复杂度是$O(n)$

$(1)$查找字符$’c’$：

1
size_t pos = str.find('c');  // 查找字符 'c'首次出现的位置

size_t就是unsigned long long

时间复杂度是$O(n)$。

$(2)$查找子字符串：

1
size_t pos = str.find("ll");  // 查找子字符串 "ll"

时间复杂度是$O(nm)$。

$(3)$从指定位置开始查找：

1
size_t pos = str.find('o', 5);  // 从索引 5 开始查找 'o'

时间复杂度是$O(n)$。

$(4)$从字符串末尾开始寻找：

1
2
std::string str = "hello world";
size_t pos = str.rfind('o');  // O(n) → 从后向前找 'o'（返回 7）

时间复杂度是$O(n)$。

$(5)$查找字符集合中的任意字符：

1
2
std::string str = "hello";
size_t pos = str.find_first_of("aeiou"); // pos = 1（即找到了字符'e'）

时间复杂度是$O(nm)$。

$\bigstar$pop_back函数：移除字符串的最后一个字符，时间复杂度为$O(1)$。

$\bigstar$push_back函数：将一个字符附加到字符串尾部，时间复杂度为$O(1)$.

10.1.2 由函数衍生出来的可能会用到的东西

$\bigstar$string::npos：

1
if(s.find(a) != string::npos)

string::npos 是 C++ 中 std::string 类的一个静态常量，表示 “未找到” 或 “无效位置”。它是 size_t 类型的最大值，通常用于字符串查找函数（如 find()、rfind() 等）的返回值，表示搜索失败。

若能找到，则 !=string::npos 成立，否则将=string::npos 。

10.2 vector

10.2.1 构造

10.2.2 函数

$\bigstar$求数组中的最大的数：

1
max(arr)

$\bigstar$求数组中某个数的下标：

1
arr.index(3) //求数3在数组arr中的下标

10.3 set

10.3.1 构造

1
2
set<int> s1;// 升序
set<int, greater<int>> s2; //降序
1
2
3
set<int> s = { 3,1,2,4,5 };
set<int> s1(s);					// 升序
set<int, greater<int>> s2 = s;	// 降序

10.3.2 函数

$\bigstar$插入函数：

1
2
3
4
5
6
7
8
9
10
11
vector<int> v = { 1,2,5 };
set<int> s;

// 1.直接插入
s.insert(3);
// 2.指定位置插入
s.insert(s.begin(), 4);
// 3.迭代器区间插入
s.insert(v.begin(), v.end());
// 4.initializer插入
s.insert({ 6,7,8 });

$\bigstar$清空函数：

1
2
std::set<int> mySet = {1, 2, 3};
mySet.clear();  // 清空set，size变为0

时间复杂度为$O(n)$。

$\bigstar$记录当前元素的数量：

1
2
set<int> st = {1,2,3};
cout<< st.size()<< endl;

时间复杂度是$O(1)$。

10.4 multiset

10.4.1 初始化

$\bigstar$能用set初始化multiset，反过来也一样！

1
2
std::set<int> s = {1, 2, 3, 4, 5};
std::multiset<int> ms(s.begin(), s.end());  // 用set初始化multiset

10.4.2 函数

$\bigstar$插入：

1
2
std::multiset<int> ms;
ms.insert(3);  // 插入 3

时间复杂度：$O(log N)$，$N$ 为当前元素数量。

$\bigstar$删除所有值为$x$的元素：

1
2
3
4
5
std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
// 删除所有值为 2 的元素，不是只删除一个！！！
ms.erase(2);
for(auto x:ms)
    cout<<x<<" ";// 输出1 3 3 3

时间复杂度：$O(M + log N)$，其中 $M$ 是删除的元素数量，$N$ 是总元素数量。

注意，是删除了所有值为$x$的元素，不是只删除一个！！！解题的时候一定要注意了！！！

$\bigstar$删除一个值为$x$的元素：

1
2
3
4
5
6
7
8
9
std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
// 删除第一个值为 2 的元素
auto it = ms.find(2);  // 查找第一个 2
if (it != ms.end()) {
	ms.erase(it);       // 删除该迭代器指向的元素
}
for (int x : ms) {
	std::cout << x << " ";  // 输出: 1 2 3 3 3（仅删除了第一个 2）
}

10.5 map

10.5.1 构造

1
map<int,int>mp;

构造函数包含了两个参数，第一个参数是关键字Key，第二个参数是关键字的值Key_Value。这两个参数可以是任意类型。

10.5.2 函数

$\bigstar$插入：

1
mp[x]=1; //说明插入了一个关键字为x的数，关键字值为1

$\bigstar$删除：

1
mp.erase(x); //删除Key=x的元素

时间复杂度为$O(logN)$，$N$是mp所存储元素的个数。是删除Key=x的元素，不是删除Key_value=x的元素哦！