大家好,我是白晨,一个不是很能熬夜,但是也想日更的人✈。如果喜欢这篇文章,点个赞,关注一下白晨吧!你的支持就是我最大的动力!
文章目录
- 前言
- C++入门必刷经典题目
- 1.选择题
- 1.1 类的类型转换
- 1.2 拷贝构造调用次数
- 1.3 友元函数
- 1.4 静态数据成员
- 1.5 new创建对象
- 1.6 模板格式
- 1.7 空类大小
- 1.8 析构函数
- 1.9 赋值运算符
- 1.10 构造函数调用
- 1.11 初始化列表
- 1.12 const
- 1.13 delete this
- 1.14 c_str()
- 1.15 resize/reserve
- 1.16 cerr
- 1.17 基类与派生类
- 1.18 继承的对象模型
- 2.编程题
- 2.1 字符串相加
- 2.2 字符串相乘
- 2.3 删除有序数组中的重复项
- 2.4 杨辉三角
- 2.5 只出现一次的数字 I
- 2.6 只出现一次的数字 II
- 2.7 只出现一次的数字 III
- 2.8 电话号码的字母组合
- 2.9 连续子数组的最大和
- 2.10 最小栈
- 2.11 栈的压入、弹出序列
- 2.12 逆波兰表达式求值
- 2.13 数组中的第K个最大元素
- ⚔ 后记
前言
白晨这段时间回头复盘了一下我的C++学习之旅,发现了许多坎坷和难点。所以,白晨整理了我入门学习C++遇到的好题目以及大坑。
整理的题目分为两个大类:选择题
和编程题
。
- 选择题
白晨整理了许多入门易错难掌握的知识点,相当于是对于重难知识点的一次复盘,希望大家可以加深对重难知识点的理解。
- 编程题
其中主要是对于C++输入输出
,STL(标准模板库)的使用
,动态规划
,数据结构
等题目,题目不是很难,但是很有代表性和经典性,是每个C++入门应该都会见过并且掌握的题目。
C++入门必刷经典题目
1.选择题
1.1 类的类型转换
答案解析
:
1.2 拷贝构造调用次数
答案解析
:
1.3 友元函数
答案解析
:
1.4 静态数据成员
答案解析
:
答案解析
:
1.5 new创建对象
答案解析
:
1.6 模板格式
答案解析
:
1.7 空类大小
答案解析
:
空类系统为了表示占位,会分配一个字节的空间
1.8 析构函数
答案解析
:
答案解析
:
1.9 赋值运算符
答案解析
:
1.10 构造函数调用
答案解析
:
1.11 初始化列表
1.12 const
答案解析
:
1.13 delete this
答案解析
:
这个写法是正确的,但是不推荐。
1.14 c_str()
答案解析
:
虽然从内容上来说,a == b,但是a,b是两个不同的对象,空间中所存储的位置也不同,c_str
返回值是 const char*
,也就是空间中的地址,所以不可能相等。
所以选择A。
1.15 resize/reserve
答案解析
:
str.reserve(111); //调整容量为 111
str.resize(5); //调整元素个数为 5
str.reserve(50); //调整容量为 50,由于调整的容量小于已有空间容量,故容量不会减小
所以size=5 capacity=111
故答案为: C
1.16 cerr
1.17 基类与派生类
1.18 继承的对象模型
2.编程题
2.1 字符串相加
✈ 原题链接
:字符串相加
模拟:
具体思路
:
我们可以模拟正常的加法,从个位开始,逐位相加,模拟过程中要注意的是:
- 我们取出字符串的每一个元素都是字符,所以不能直接将其相加,必须要减去
'0'
才能得到这个数的真实值。 - 当一个数的每一位都已经遍历完了,如果另一个数还没遍历完,则在这个数的高位补0。
- 如果两个数字之和大于等于10,要进位。
- 每次向要返回字符串插入一个本次相加得到的个位数。
- 最后得到的返回字符串是反的,我们要将其反转。
代码实现
:
class Solution {public:string addStrings(string num1, string num2) {int i = num1.size() - 1, j = num2.size() - 1;int flag = 0;string ret;// 当给定的数字没有遍历完或者要进位时,进入循环while (i >= 0 || j >= 0 || flag != 0){// 判断一个数是否已经遍历完int val1 = i >= 0 ? num1[i] - '0' : 0;int val2 = j >= 0 ? num2[j] - '0' : 0;// 看有没有进位// flag == 1,有进位,反之,无进位flag = flag == 1 ? val1 + val2 + 1 : val1 + val2;// 将本次相加的个位数插到返回字符串后ret += flag % 10 + '0';flag /= 10;i--;j--;}// 反转字符串reverse(ret.begin(), ret.end());return ret;}};
2.2 字符串相乘
✈ 原题链接
:字符串相乘
法一:模拟竖式+加法实现
具体思路
:
先来看例子中的乘法用竖式如何计算:
我们发现,从右到左,
num2
每一位都需要乘以num1
,并且每乘完一次num1
所得的数字的权重要乘10。num2
每一位乘num1
都是个位数*num1
,所以我们可以先把个位数乘num1
的结果保存起来,用的时候直接调用。得到
num2
每一位乘num1
的字符串后,保存起来,最后和竖式一样,依次相加每一位的结果,得到最后的答案。
代码实现
:
class Solution {public:// 复用上题的加法string Add(const string& num1, const string& num2){string ret;int add = 0;int end1 = num1.size() - 1, end2 = num2.size() - 1;while (end1 >= 0 || end2 >= 0 || add != 0){int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;add = n1 + n2 + add;ret += add % 10 + '0';add /= 10;}reverse(ret.begin(), ret.end());return ret;}string multiply(string num1, string num2) {// 出现0时,直接返回"0"if (num1 == "0" || num2 == "0")return "0";int len1 = num1.size(), len2 = num2.size();// 保存 0 ~ 9 乘 num1 的值vector<string> save(10);// 保存num2每一位乘num1的值vector<string> ret(len2 + 1);// 0乘任何数都为0save[0] = "0";// 保存最后的返回值ret[len2] = "0";// 记录权重int pos = 0;// 保存 0 ~ 9 乘 num1 的值for (int i = 1; i < 10; ++i){save[i] = Add(save[i - 1], num1);}// 保存num2每一位乘num1的值for (int i = len2 - 1; i >= 0; --i){int val = num2[i] - '0';ret[i] = save[val];// 根据权重在字符串后面补0for (int j = 0; j < pos; ++j)ret[i] += '0';// 每乘完一个数,权重加一pos++;}// 整体加起来for (int i = 0; i < len2; ++i){ret[len2] = Add(ret[len2], ret[i]);}return ret[len2];}};
2.优化竖式+模拟乘法
具体思路
:
- 首先,我们先来探讨一下 m位数乘n位数得到的结果为多少位数。
由上式可得,最后相乘得到的数字最长为 m+nm+n m+n ,所以我们可以预先开辟一个 m+nm+n m+n 长度的数组来存放这个数字。
由于要使用乘法进行模拟,所以我们可以优化一下我们的竖式乘法
通过上面的例子我们可以得到优化后竖式的具体做法:
- 将原来一次乘一个整形的步骤拆解为一次一个数只乘一个数
- 这样就不用担心溢出问题
- 并且我们可以将相乘的结果直接加到上述数组对应的位上,就如同上面的竖式一样
- 进行完全部的竖式运算后,再处理得到的数组,该进位进位,保证每一位上都是个位数。
- 再将数组转换为字符串后返回。
代码实现
:
class Solution {public:string multiply(string num1, string num2) {if (num1 == "0" || num2 == "0")return "0";int m = num1.size(), n = num2.size();vector<int> num(m + n);string ret;// 模拟每一位乘每一位for (int i = n - 1; i >= 0; --i){int val2 = num2[i] - '0';for (int j = m - 1; j >= 0; --j){int val1 = num1[j] - '0';int mul = val1 * val2;// 将乘来的结果加到对应的位上num[i + j + 1] += mul;}}// 进位for (int i = m + n - 1; i > 0; --i){num[i - 1] += num[i] / 10;num[i] %= 10;}// 判断有没有最高位int i = num[0] == 0 " />1 : 0;for (; i < m + n; ++i){ret += num[i] + '0';}return ret;}};
2.3 删除有序数组中的重复项
✈ 原题链接
:删除有序数组中的重复项
法一:暴力求解
代码实现
:
class Solution {public:int removeDuplicates(vector<int>& nums) {vector<int>::iterator begin = nums.begin();while (begin != nums.end()){if (begin + 1 != nums.end() && *begin == *(begin + 1))begin = nums.erase(begin);elsebegin++;}return nums.size();}};
法二:快慢指针
代码实现
:
class Solution {public:int removeDuplicates(vector<int>& nums) {size_t slow = 0, fast = 0;size_t len = nums.size();while (fast < len){if (nums[slow] != nums[fast]){nums[slow + 1] = nums[fast];slow++;}fast++;}return slow + 1;}};
2.4 杨辉三角
✈ 原题链接
:杨辉三角
这是一道非常典型的动态规划的题目,并且思路也非常简单。
具体思路
:
- 状态: d p [ i ] [ j ]dp [ i ] [ j ]dp[i][j] 为位置的数字
- 初始状态:当 j = = 0 ∣ ∣ i = = j 时 , d p [ i ] [ j ] = 1j == 0 || i== j时, dp [ i ] [ j ] = 1j==0∣∣i==j时,dp[i][j]=1
- 状态转移方程: d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + d p [ i − 1 ] [ j ]dp [i] [j] = dp [i – 1] [j – 1] + dp [i – 1] [ j ]dp[i][j]=dp[i−1][j−1]+dp[i−1][j]。
代码实现
:
class Solution {public:vector<vector<int>> generate(int numRows) {vector<vector<int>> ret(numRows, vector<int>(1, 1));for (int i = 0; i < numRows; ++i){ret[i].resize(i + 1, 1);}for (int i = 2; i < numRows; ++i){for (int j = 1; j < ret[i].size() - 1; ++j){ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];}}return ret;}};
2.5 只出现一次的数字 I
✈ 原题链接
:只出现一次的数字
首先,我们需要了解异或运算的几个性质:
- 交换律: a ⊕ b = b ⊕ a , a ⊕ b ⊕ a = a ⊕ a ⊕ ba ⊕ b = b ⊕ a, a ⊕ b ⊕ a = a ⊕ a ⊕ ba⊕b=b⊕a,a⊕b⊕a=a⊕a⊕b
- 结合律: ( a ⊕ b ) ⊕ a = a ⊕ ( b ⊕ a )(a ⊕ b) ⊕ a = a ⊕ (b ⊕ a)(a⊕b)⊕a=a⊕(b⊕a)
- 任何数与0异或都是其本身: a ⊕ 0 = 0 ⊕ a = aa ⊕ 0 = 0 ⊕ a = aa⊕0=0⊕a=a
- 任何数与自己异或都为0: a ⊕ a = 0a⊕a=0a⊕a=0
其次,题目中明确指出,只有一个数字出现了一次,其余数字均出现了两次,所以,依照上述性质,我们可以将其化为:
a1⊕ a1⊕ a2⊕ a2⊕ . . . ⊕ ak⊕ a k + 1⊕ a k + 1⊕ . . . ⊕ am⊕ am= 0 ⊕ ak= ak a_1 ⊕a_1⊕a_2⊕a_2⊕…⊕a_k⊕a_{k+1}⊕a_{k+1}⊕…⊕a_m⊕a_m = 0⊕a_k=a_ka1⊕a1⊕a2⊕a2⊕...⊕ak⊕ak+1⊕ak+1⊕...⊕am⊕am=0⊕ak=ak
也即,直接将给定数组中的数全部异或起来,最后得到的数就是只出现一次的数。
代码实现
:
class Solution {public:int singleNumber(vector<int>& nums) {int num = 0;for(auto i : nums)num ^= i;return num;}};
2.6 只出现一次的数字 II
✈ 原题链接
:只出现一次的数字 II
法一:排序 + 遍历
- 这个方法就没有什么好说的了,直接暴力排序,遍历选出其中只出现一次的数字。
代码实现
:
class Solution {public:int singleNumber(vector<int>& nums) {if(nums.size() == 1)return nums[0];sort(nums.begin(), nums.end());int len = nums.size();if(nums[0] != nums[1]){return nums[0];}if(nums[len - 1] != nums[len - 2]){return nums[len - 1];}for(int i = 1; i < len - 1; ++i){if(nums[i] != nums[i - 1] && nums[i] != nums[i + 1])return nums[i];}return 0;}};
时间复杂度 O(n∗lo g 2n)O(n*log_2n) O(n∗log2n) ,空间复杂度 O(1)O(1) O(1) 。
法二:哈希表
- 遍历数组,使用哈希表统计数组中的数出现的次数,最后找到只出现一次的数字即可。
代码实现
:
class Solution {public:int singleNumber(vector<int>& nums) {unordered_map<int, int> harsh;for (int e: nums) {++harsh[e];}int ret = 0;for (auto [num, cnt]: harsh) {if (cnt == 1) {ret = num;break;}}return ret;}};
时间复杂度 O(n)O(n) O(n) ,空间复杂度 O(n)O(n) O(n) 。
法三:统计二进制位数
- 建立一个数组,统计全部数字的二进制每一位上
1
出现了多少次。 - 因为除了一个数字以外,其余数字都出现了3次,所以其余数字每一位二进制位为
1
次数的总和一定能被3整除。 - 所以,只需要统计出二进制位中不能被3整除的位,这些位组成的数就是只出现过一次的数。
代码实现
:
class Solution {public:int singleNumber(vector<int>& nums) {int cnt[32] = { 0 };int ret = 0;// 统计全部数字二进制为1的个数for (int i = 0; i < 32; ++i){for (auto e : nums){if ((e >> i) & 1 == 1){cnt[i]++;}}}// 将不能被3整除的位或等起来就是结果for (int i = 0; i < 32; ++i){if ((cnt[i] % 3))ret |= 1 << i;}return ret;}};
时间复杂度 O(n)O(n) O(n) ,空间复杂度 O(1)O(1) O(1) 。
2.7 只出现一次的数字 III
✈ 原题链接
:只出现一次的数字 III
✨ 法一:排序 + 遍历
- 直接排序,然后遍历选出只出现了一次的数字。
代码实现
:
class Solution {public:vector<int> singleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int len = nums.size();vector<int> ret;// 特别情况:对第一个元素和第二个元素进行判断if(nums[0] != nums[1]){ret.push_back(nums[0]);}// 特别情况:对最后一个元素和倒数第二个元素进行判断if(nums[len - 1] != nums[len - 2]){ret.push_back(nums[len - 1]);}if(ret.size() == 2)return ret;// 一般判断:对数组中的其他元素进行判断for(int i = 1; i < len - 1; ++i){if(nums[i] != nums[i - 1] && nums[i] != nums[i + 1])ret.push_back(nums[i]);}return ret;}};
时间复杂度 O(n∗lo g 2n)O(n*log_2n) O(n∗log2n) ,空间复杂度 O(1)O(1) O(1) 。
✨ 法二:哈希表
- 暴力哈希,直接统计每个数字出现次数,最后选出只出现一次的数。
代码实现
:
class Solution {public:vector<int> singleNumber(vector<int>& nums) {unordered_map<int, int> freq;for (int num: nums) {++freq[num];}vector<int> ans;for (const auto& [num, occ]: freq) {if (occ == 1) {ans.push_back(num);}}return ans;}};
✨ 法三:二进制异或法
具体思路
:
- 首先,我们需要了解异或运算的几个性质:
- 交换律: a ⊕ b = b ⊕ a , a ⊕ b ⊕ a = a ⊕ a ⊕ ba ⊕ b = b ⊕ a, a ⊕ b ⊕ a = a ⊕ a ⊕ ba⊕b=b⊕a,a⊕b⊕a=a⊕a⊕b
- 结合律: ( a ⊕ b ) ⊕ a = a ⊕ ( b ⊕ a )(a ⊕ b) ⊕ a = a ⊕ (b ⊕ a)(a⊕b)⊕a=a⊕(b⊕a)
- 任何数与0异或都是其本身: a ⊕ 0 = 0 ⊕ a = aa ⊕ 0 = 0 ⊕ a = aa⊕0=0⊕a=a
- 任何数与自己异或都为0: a ⊕ a = 0a⊕a=0a⊕a=0
其次,题目中明确指出,只有两个数字出现了一次,其余数字均出现了两次,所以,依照上述性质,我们可以将其化为:
a1⊕ a1⊕ a2⊕ a2⊕ . . . ⊕ ak⊕ a k + 1⊕ a k + 1. . . ⊕ an⊕ a n + 1⊕ a n + 1⊕ . . . ⊕ am⊕ am= ak⊕ an a_1 ⊕a_1⊕a_2⊕a_2⊕…⊕a_k⊕a_{k+1}⊕a_{k+1}…⊕a_n⊕a_{n+1}⊕a_{n+1}⊕…⊕a_m⊕a_m = a_k⊕a_na1⊕a1⊕a2⊕a2⊕...⊕ak⊕ak+1⊕ak+1...⊕an⊕an+1⊕an+1⊕...⊕am⊕am=ak⊕an
最后我们得到了两个只出现一次数字的异或值,由异或的定义可知,两个数二进制位上的数不相同时不相同的位上结果为1
,eg. 1000 ⊕ 1110 = 0110 ,可得这两个数字从右到左第二位和第三位不同。
- 当得到了目标数字的不同二进制位时,我们可以依次为依据对数组进行分组,分组后,每一组都只剩下了一个单独出现的数字。
- 再按照
只出现一次的数字 I
的方法分别选出两个数字即可。
代码实现
:
class Solution {public:vector<int> singleNumber(vector<int>& nums) {int num = 0;int len = nums.size();vector<int> ret;// 将全部数字异或起来for(auto e : nums){num ^= e;}int i = 0;// 找出两个数字不一样的二进制位for(i = 0; i < 32; ++i){if((num >> i) & 1 == 1)break;}// 按不同二进制位分组进行异或,最后直接得到两个结果int ret1 = 0, ret2 = 0;for(auto e : nums){if((e >> i) & 1 == 1)ret1 ^= e;elseret2 ^= e;}ret.push_back(ret1);ret.push_back(ret2);return ret;}};
时间复杂度 O(n)O(n) O(n) ,空间复杂度 O(1)O(1) O(1) 。
2.8 电话号码的字母组合
✈ 原题链接
:电话号码的字母组合
具体思路
:
这是一道非常经典的回溯算法题,思路其实也很简单:
- 遍历题目给的数字字符串,按照数字找到对应的字母字符串。
- 按遍历的元素顺序在当前后面加字符,直到遍历完成。
- 当遍历完题目给的数字字符串时,把此时得到的字符串保存。
代码实现
:
// 哈希表用来对照static string harsh[] = {"", "", "abc", "def", "ghi", "jkl", "mno","pqrs", "tuv", "wxyz"};class Solution {public:void Dfs(string& digits, int index, string curStr, vector<string>& ret){// 当当前的字符串长度与digits相等,如果当前字符串不为空,将其插入if(curStr.size() == digits.size()){if(!curStr.empty())ret.push_back(curStr);return;}// 找到当前digits对应的数字int curInd = digits[index] - '0';// 遍历这个哈希表中对应的字符串for(auto& ch: harsh[curInd]){// 尝试每一种结果,index为digits下标,每次加一// 每次在当前字符串后加入当前对应的哈希表字符,尝试所有可能性Dfs(digits, index + 1, curStr + ch, ret);}}vector<string> letterCombinations(string digits) {vector<string> ret;Dfs(digits, 0, "", ret);return ret;}};
2.9 连续子数组的最大和
✈ 原题链接
:连续子数组的最大和
这道题是一道很经典的动态规划的题目,有的同学可能第一眼就直接用贪心+回溯去做,但是这道题用贪心算法的话有些情况下会得不到整体最优的结果。
具体思路
:
这是一道非常经典的动态规划问题:
状态:f(x)f(x) f(x) —— 从上一段连续的最大和到 x 位置的最大和
状态转移方程:f(x)=max(f(x−1)+a[x],a[x])f(x)=max(f(x-1) + a[x], a[x]) f(x)=max(f(x−1)+a[x],a[x]) —— 如果上一段的连续最大和与当前数的和大于当前数,就取上一段的连续最大和与当前数的和,反之,取当前数(相当于如果 前面连续串的和的最大值 以及 当前数 相加的和 如果还不如当前数,不如从这一位置重新开始一个连续的子串,反之继续延续前面的连续串)
初始值:f(0)=a[0]f(0) = a[0] f(0)=a[0] —— 从a[0]开始子串
结果:从 f(0)−f(n−1)f(0) – f(n-1) f(0)−f(n−1) 中选出最大值。因为连续串不确定,所以最后要判断一下。
实例:−2,1,−3,4,−1,2,1,−5-2 ,1,-3,4,-1,2,1,-5 −2,1,−3,4,−1,2,1,−5
序号 0 1 2 3 4 5 6 7 a [ x ]a[x]a[x] -2 1 -3 4 -1 2 1 -5 f ( x )f(x)f(x) -2 1 -2 4 3 5 6 1
再来形象总结一下连续串的思路:
相当于你有一个大型的家族,如果前面你家族的资产很丰厚,和你的资产加起来超过了你原本的资产(你可能还欠钱了),那么你选择继承家产;但是如果你家道中落,家里欠了钱,那么你就可以选择自己出去单干,不要被家族牵连,你又开始建立了一个新家族。你的子孙以你为榜样,继续上面的过程。
最后你的后代翻阅族谱,要找到祖上最阔器的时代,于是将一代代人的资产比较,得到祖上最阔的一代的资产。
代码实现
:
class Solution {public:int FindGreatestSumOfSubArray(vector<int> array) {int num = array[0], Max = array[0];for(int i = 1; i < array.size(); ++i){num = max(array[i] + num, array[i]);Max = num > Max ? num : Max;}return Max;}};
2.10 最小栈
✈ 原题链接
:最小栈
本题既然要求要在线性时间内找到最小值,那么我们可以用空间换时间的做法。
具体思路
:
- 预设两个栈,一个存放正常输入的值——
_st
,另一个专门存放最小值——_min
。 - 入栈:
- 入栈的值直接存放到
_st
; _st
栈为空时,同时将其入栈_min
;- 后面进行入栈时,和
_min
的栈顶元素比较,如果入栈的值小于等于_min
的栈顶元素,就入栈_min
。
- 入栈的值直接存放到
- 出栈:
- 出栈时,如果
_st
的出栈元素等于_min
的栈顶元素,那么两个栈都出栈; - 如果
_st
的出栈元素不等于_min
的栈顶元素,只出_st
栈。
- 出栈时,如果
代码实现
:
class MinStack {public:MinStack() {}void push(int val) {_st.push(val);if (_min.empty() || val <= _min.top()){_min.push(val);}}void pop() {if (_min.top() == _st.top()){_min.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _min.top();}private:stack<int> _st;stack<int> _min;};
2.11 栈的压入、弹出序列
✈ 原题链接
:栈的压入、弹出序列
这道题的主要思路就是——模拟
。
具体思路
:
- 直接模拟栈的出入栈过程。
- 按照给定的入栈顺序依次入栈,入到入栈元素和出栈序列的第一个元素相同时,开始出栈,同时指向出栈序列的下一个元素,循环这个过程,直到栈顶元素和出栈序列元素不同或者栈为空,停止出栈。
- 循环上述过程,直到遍历完入栈序列。
- 此刻,如果栈中没有元素,说明题目给定序列正确,反之,不正确。
代码实现
:
class Solution {public:bool IsPopOrder(vector<int> pushV, vector<int> popV) {stack<int> st;int i = 0, j = 0;// 循环下面的过程,直到遍历完入栈序列while (i < pushV.size()){st.push(pushV[i++]);// 当栈顶元素和出栈序列相等时,开始出栈while (!st.empty() && st.top() == popV[j]){st.pop();j++;}}return st.empty();}};
2.12 逆波兰表达式求值
✈ 原题链接
:逆波兰表达式求值
逆波兰表达式
由波兰的逻辑学家卢卡西维兹提出。逆波兰表达式的特点是:没有括号,运算符总是放在和它相关的操作数之后。因此,逆波兰表达式也称后缀表达式。
具体思路
:
逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作:
如果遇到操作数,则将操作数入栈;
如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数,后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。
整个逆波兰表达式遍历完毕之后,栈内只有一个元素,该元素即为逆波兰表达式的值。
上面思路出自力扣官方
代码实现
:
class Solution {public:int evalRPN(vector<string>& tokens) {stack<int> st;for (const auto& str : tokens){if (str == "+" || str == "-" || str == "*" || str == "/"){int right = st.top();st.pop();int left = st.top();st.pop();switch (str[0]){case '+':st.push(left + right);break;case '-':st.push(left - right);break;case '*':st.push(left * right);break;case '/':st.push(left / right);break;}}else{st.push(stoi(str));}}return st.top();}};
2.13 数组中的第K个最大元素
✈ 原题链接
:数组中的第K个最大元素
法一
:排序
直接排序,选出第k个元素,时间复杂度为 O(n∗logn)O(n*log~n) O(n∗logn)。
class Solution {public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(), nums.end(), greater<int>());return nums[k - 1];}};
法二
:堆排序
使用堆排序,时间复杂度为 O(n+k∗logn)O(n+k*log~n) O(n+k∗logn)
class Solution {public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq(nums.begin(), nums.end());for (int i = 1; i < k; ++i){pq.pop();}return pq.top();}};
法三
:TopK
TopK问题,直接建立一个k个元素大小的小栈,用TopK的解法即可。时间复杂度为 O(n+n∗logk)O(n + n*log~k) O(n+n∗logk),这是这道题的最优解了。
class Solution {public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);for (int i = k; i < nums.size(); ++i){if (nums[i] > pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}};
没有了解过堆的同学可以看这篇文章——【数据结构】堆的全解析,其中很详细的讲解了堆排序和TopK问题。
⚔ 后记
白晨写本文的目的是帮助更多的C++入门学习者更快掌握C++的语法,并且可以将C++用于实践,希望大家可以在这篇文章中有所收获。
如果这篇文章有帮到你的话,还请多多支持白晨,你的支持就是对白晨最大的鼓励。
如果解析有不对之处还请指正,我会尽快修改,多谢大家的包容。
如果大家喜欢这个系列,还请大家多多支持啦!
如果这篇文章有帮到你,还请给我一个大拇指
和小星星
⭐️支持一下白晨吧!喜欢白晨【刷题日记】系列的话,不如关注
白晨,以便看到最新更新哟!!!
我是不太能熬夜的白晨,我们下篇文章见。