一、压缩字符串(一)
题目解析
题目给定一个字符
str，让我们将这个字符串进行压缩；**压缩规则：**出现多次的字符压缩成
字符+数字；例如aaa压缩成a3。如果字符值出现一次，1不用写。
算法思路
这道题总的来说就非常简单了，我们直接模拟整个过程即可。
思路：
示例双指针遍历，统计字符和字符出现的次数；
i固定一个字符，j向后遍历找与i位置相同的字符，如果相同就继续向后遍历，直到j位置与i位置的字符不相同；
j向后遍历结束，i位置字符出现的字符次数为j-i；如果j-1大于1就在结果字符串中加入出现的次数；等于1则不用加次数。
代码实现
class Solution {
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>using namespace std;
const int N = 2e5+10;
int n,k;
typedef pair<int,int> PII;
PII arr[N];
int main()
{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;});long long a = 0, b = 0;for(int i = 0;i<k;i++){a+=arr[i].first;b+=arr[i].second;}cout<<b<<' '<<a<<endl;return 0;
}
三、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])。还要注意这样我们就需要从右往左填表，否则就会覆盖掉我们的数据。
代码实现
class Solution {
public:int dp[1001][1001] = {0};int knapsack(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];}
};
空间优化：
class Solution {
public:int dp[1001] = {0};int knapsack(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];}
};
到这里本篇文章就结束了，继续加油