【C++】 —— 笔试刷题day_18

一、压缩字符串(一)

题目解析

题目给定一个字符str，让我们将这个字符串进行压缩；

**压缩规则：**出现多次的字符压缩成字符+数字；例如aaa压缩成a3。如果字符值出现一次，1不用写。

算法思路

这道题总的来说就非常简单了，我们直接模拟整个过程即可。

思路：

示例双指针遍历，统计字符和字符出现的次数；

i固定一个字符，j向后遍历找与i位置相同的字符，如果相同就继续向后遍历，直到j位置与i位置的字符不相同；

j向后遍历结束，i位置字符出现的字符次数为j-i；如果j-1大于1就在结果字符串中加入出现的次数；等于1则不用加次数。

代码实现

classSolution{public: string compressString(string param){ string ret;for(int i =0;i<param.size();){int j = i+1;while(j<param.size()&& param[j]== param[i]) j++; ret+=param[i];if(j-i>1) ret+=to_string(j-i); i = j;}return ret;}};

二、chika和蜜柑

题目解析

这道题说chika很喜欢吃蜜柑，每一个蜜柑有一定的甜度和酸度；

现在输入n表示蜜柑的个数，k表示chika要吃k个蜜柑；然后依次输入每个蜜柑的酸度、每个蜜柑的甜度。

chika想要甜度尽可能的大，如果存在甜度相等的情况，就让酸度尽可能小。

现在要我们求酸度和甜度（甜度尽可能大，酸度尽可能小）。

算法思路

对于这道题，是一道topK问题

不知是否对topK还有一些记忆，topK问题简单来说就是在一堆数据中寻找较大/较小的k个数；

那对于我们这道题来说，我们要甜度尽可能大，那就是找甜度较大的k个数；但是，我们这道题在甜度相等的时候，要酸度尽可能小；

我们可以使用pair<int , int>类型来存储每一个蜜柑的甜度和酸度，但是我们要知道pair<int,int>的默认比较大小的方式：首先比较first：first大就大，first相等再看second：second大就大。

**但是我们这里要的比较方式是：**先比较甜度，甜度大就大；甜度相等再看酸度，酸度要尽可能小，而不是尽可能大。

那这里我们就要使用我们这里要求的比较方式，所以我们要自己实现一个可调用对象，这个可调用对象用来比较两个pair<int,int>类型的对象；

比较方式：

这里如果first不相等，就比较first；如果first相等比较second。

这里我们可以排升序，也可以排降序（博主这里实现排降序的）；

如果first不相等，就返回a.first > b.first；如果first相等，就比较second返回a.second < b.second。

这样我们可调用对象返回的就是a是否大于b，排的就是降序。

代码实现

这里可调用对象可以写仿函数、也可以写lambda，这里就实现lambda。

#include<iostream>#include<algorithm>usingnamespace std;constint N =2e5+10;int n,k;typedef pair<int,int> PII; PII arr[N];intmain(){ cin>>n>>k;for(int i =0;i<n;i++) cin>>arr[i].second;for(int i =0;i<n;i++) cin>>arr[i].first;//排序sort(arr,arr+n,[](PII& a,PII& b){if(a.first!=b.first)return a.first>b.first;elsereturn a.second<b.second;});longlong a =0, b =0;for(int i =0;i<k;i++){ a+=arr[i].first; b+=arr[i].second;} cout<<b<<' '<<a<<endl;return0;}

三、01背包

题目解析

OK啊，这道题是一道经典的01背包问题；题目给定一个V表示背包的体积、n表示物品的个数、vw数组，其中vw[i][0]表示第i个物品的体积、vw[i][1]表示第i个物品的重量。

最后让我们返回从i个物品中选择体积不超过V的物品的最大重量。

算法思路

对于01背包问题呢，这道题并没有那么多弯弯绕绕

对于背包问题的结题思路，就是动态规划（线性dp）。

如果没有了解过动态规划，或者没有搞清楚动态规划中它状态表示的含义和动态转移方程，那这道题还是有点难度的。

状态表示：

dp[i][j]： 表示在i个物品中选择体积不超过j的物品，这些物品重量的最大值。（背包容量为j，从i个物品中选择时的最大重量）。

状态转移方程：

对于i位置的物品，我们可以选择这个位置的物品，也可以不选择这个位置的物品；如果选择i位置时dp[i][j] = dp[i-1][j-v[i]] + v[i]（其中v[i]表示i位置物品的重量）；如果我们没有选择i位置：dp[i][j] = dp[i-1][j]。

理解了状态表示和状态转移方程，这里在填写dp表示时还要注意：

在填表时，当我们的背包容量要大于物品i的体积，这时我们可以选择该物品；（这是我们才需要考虑是否选择该物品）

如果背包容量小于物品i的体积，这时我们就不能选择该物品。（这时我们就不用考虑是否选择该位置了）

空间优化：

这里我们使用的是一个二维dp表，我们可以进行一下优化；

简单来说就是使用一维dp表来解决，（在遍历i时，我们就可以认为此时在枚举在i个物品中选择体积不超过j的物品；那对于某一个物品，不选择它时的最大重量就等于此时的dp[j]，选择它时的最大重量就等于dp[j - v[i]] + z[i]（其中z[i]表示i物品的重量）。

那这样我们dp[i] = max(dp[i] , dp[j-v[i]] + z[i])。

还要注意这样我们就需要从右往左填表，否则就会覆盖掉我们的数据。

代码实现

classSolution{public:int dp[1001][1001]={0};intknapsack(int V,int n, vector<vector<int>>& vw){// write code herefor(int i =1;i<=n;i++){for(int j =1;j<=V;j++){if(vw[i-1][0]<= j){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-vw[i-1][0]]+vw[i-1][1]);}else{ dp[i][j]= dp[i-1][j];}}}return dp[n][V];}};

空间优化：

classSolution{public:int dp[1001]={0};intknapsack(int V,int n, vector<vector<int>>& vw){// write code herefor(int i =0;i<n;i++){for(int j = V;j>=vw[i][0];j--) dp[j]=max(dp[j],dp[j-vw[i][0]]+ vw[i][1]);}return dp[V];}};

到这里本篇文章就结束了，继续加油