目录

1.压缩字符串

2.chika和蜜柑

3.01背包

---

1.压缩字符串

链接

注意细节：

1.数量为一个时不用输出个数

2.当数量超过 9 时，需要逐个拿出 n 的位数，如153次，需要拿出1、5、3三个数

详细代码：

class Solution {
public:
	int Check(int x) {
		int cnt = 0;
		while (x) {
			x /= 10;
			cnt++;
		}
		return cnt;
	}
	string compressString(string param) {
		string ret;
		for (int i = 0; i < param.size(); ++i) {
			int tmp = param[i];
			int cnt = 0;
			while (param[i] == tmp) {
				cnt++;
				i++;
			}
			ret += tmp;
			if (cnt > 1) {
				int n = Check(cnt);
				if (n > 1) {
					while (cnt) {
						int i = pow(10, n - 1);
						ret += cnt / i + '0';
						cnt %= i;
						n--;
					}
					if (n)
					{
						ret += '0';
						n--;
					}
				}
				else if (n == 1)
				{
					ret += cnt + '0';
				}
			}
			i--;
		}
		return ret;
	}
};

2.chika和蜜柑

链接

经典的TopK问题，取头几个最大甜度，注意排序逻辑：

比较规则是：首先比较第二个元素的值，如果它们不相等，则按照第二个元素的值从大到小排序；如果第二个元素的值相等，则按照第一个元素的值从小到大排序。

    sort(arr, arr + n, [&](const PII& a, const PII& b)
        {
            if (a.second != b.second)
                return a.second > b.second;
            else
                return a.first < b.first;
        });

详细代码：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
typedef pair<int, int> PII;// (酸，甜)
const int N = 2e5 + 10;
PII arr[N];

signed main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
		cin >> arr[i].first;
	for (int i = 0; i < n; ++i)
		cin >> arr[i].second;

	sort(arr, arr + n, [&](const PII& a, const PII& b)
		{
			if (a.second != b.second)
				return a.second > b.second;
			else
				return a.first < b.first;
		});
	int sums = 0;
	int sumt = 0;
	for (int i = 0; i < k; ++i)
	{
		sums += arr[i].first;
		sumt += arr[i].second;
	}
	cout << sums << ' ' << sumt << endl;
	return 0;
}

3.01背包

链接

01背包模版题：

class Solution {
public:
    const static int N = 1010;
    int v[N];
    int w[N];
    int dp[N][N] = { 0 };
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        for(int i = 0; i < vw.size(); ++i)
        {
            v[i + 1] = vw[i][0];
            w[i + 1] = vw[i][1];
        }

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= V; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0)
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j -v[i]] + w[i]);
            }
        }
        return dp[n][V];
    }
};