1.字符串替换（一）
双指针维护一个相同字符的区间。注意个数可能是一个两位数，得用tostring.
代码：
class Solution { public: string compressString(string param) { int n=param.size(); if(n<=1)return param; string ans=""; int i,j; for( i=1,j=0;i<n;i++){ if(param[i]!=param[i-1]){ ans+=param[j]; if(i-j>1){ ans+=to_string(i-j); } j=i; } } ans+=param[j]; if(n-j>1){ ans+=to_string(n-j); } return ans; } };
2.chike和蜜柑
贪心排序。优先把甜度高的排在前面，甜度一样就优先酸度低的。
代码：
#include <iostream> #include<algorithm> using namespace std; const int N=2e5+10; struct orange{ int t; int s; }o[N]; bool cmp(orange &a,orange &b){ if(a.t==b.t)return a.s<b.s; return a.t>b.t; } int main() { int n,k; cin>>n>>k; for(int i=0;i<n;i++){ cin>>o[i].s; } for(int i=0;i<n;i++)cin>>o[i].t; sort(o,o+n,cmp); long long ans1=0,ans2=0; for(int i=0;i<k;i++){ ans1+=o[i].t; ans2+=o[i].s; //cout<<o[i].s<<"--- "<<o[i].t; } cout<<ans2<<" "<<ans1<<endl; }
3.01背包
dp[j]表示背包容量为i时能最多存放多少重量。
拿还是不拿，拿的话就dp[j-vw[i][0]]+vw[i-1][1],不拿就dp[j](i-1时)。
逆序遍历体积。为什么逆序遍历呢。因为j-vw[i-1][0]一定小于j,不会影响到以及遍历过的dp[j]
代码：
class Solution { public: int knapsack(int V, int n, vector<vector<int> >& vw) { vector<int> dp(V+1); for(int i=1;i<=n;i++){ for(int j=V;j>=vw[i-1][0];j--){ dp[j]=max(dp[j-vw[i-1][0]]+vw[i-1][1],dp[j]); } } return dp[V]; } };
