个人技术分享

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];
    }
};