NC187. 压缩字符串(二)
描述
示例1
输入:
"aabcccccaaa",0
输出:
7
说明:
压缩后的字符串为"a2bc5a3"，长度为7示例2
输入:
"aabcccccaaa",1
输出:
6
说明:
在不删除任何任何字符串时候，压缩后的字符串为"a2bc5a3"，删除1个字符串b之后，压缩后的字符串最好为"a2c5a3"，长度为6，删除其他的字符，长度依然为7示例3
输入:
"aaabbbaaa",3
输出:
2
说明:
删除3个b字符，压缩后为a6，长度为2C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-01-14
#include<vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int compressString(string s, int k) {
// write code here
int lens = s.length();
vector<vector<int>>dp(lens+1,vector<int>(k+1,INT_MAX>>1));//存储前i个字符串中删除掉j个后最短长度
dp[0][0] = 0;
for(int i = 0;i<=lens;i++){
for(int j = 0;j<=i&&j<=k;j++){
if(j>0)
dp[i][j] = dp[i-1][j-1];//删掉第i个字符
int same = 0,diff = 0;
for(int f = i;f >=1&&diff<=j;f--){//如果字符相同，考虑是否保留
if(s[i-1] == s[f-1])
dp[i][j] = min(dp[i][j],dp[f-1][j-diff]+zip(++same));
else
diff++;
}
}
}
return dp[lens][k];
}
int zip(int n){
if(n==1) return 1;
if(n<10) return 2;
if(n<100) return 3;
return 4;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2021-12-09
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int compressString(string s, int k) {
auto calc = [](int x) {
if (x == 1) {
return 1;
}
if (x < 10) {
return 2;
}
if (x < 100) {
return 3;
}
return 4;
};
int n = s.size();
vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX >> 1));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k && j <= i; ++j) {
if (j > 0) {
f[i][j] = f[i - 1][j - 1];
}
int same = 0, diff = 0;
for (int i0 = i; i0 >= 1 && diff <= j; --i0) {
if (s[i0 - 1] == s[i - 1]) {
++same;
f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same));
} else {
++diff;
}
}
}
}
return f[n][k];
}
};
C 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-06-06
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int min(int a, int b) {
return a > b ? b : a;
}
int max(int a, int b) {
return a > b ? a : b;
}
int count(int k) {
if (k <= 1) return 0;
if (k < 10) return 1;
if (k < 100) return 2;
return 3;
}
int compressString(char* s, int k) {
int sLen = strlen(s);
if (s == NULL || k >= sLen) {
return 0;
}
int **dp = (int **)malloc(sizeof(int *) * (sLen + 1));
for (int i = 0; i < sLen + 1; i++) {
dp[i] = (int *)malloc(sizeof(int) * (k + 1));
for (int j = 0; j < k + 1; j++) {
dp[i][j] = max(0, i-j);
}
}
int del = 0, l = 0, sameCount = 0;
for (int i = 1; i < sLen + 1; i++) {
dp[i][0] = i;
for (int j = 0; j <= i && j < k + 1; j++) {
if (j > 0) {
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j] + 1);
}
del = 0;
sameCount = 0;
for (l = i; l > 0; l--) {
if (s[l-1] == s[i-1]) {
sameCount++;
} else {
dp[i][j] = min(dp[l][j-del] + count(sameCount) + 1, dp[i][j]);
if (++del > j) {
break;
}
}
}
if (l == 0) {
dp[i][j] = min(count(sameCount) + 1, dp[i][j]);
}
}
}
int result = dp[sLen][k];
for (int i = 0; i < sLen + 1; i++) {
free(dp[i]);
}
free(dp);
return result;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 448KB, 提交时间: 2021-12-16
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int compressString(string s, int k) {
if (s.size() == 0) {
return 0;
}
vector<vector<int>> line(s.size(), vector<int>(k+1,0));
int letter = s[0];
int count = 1;
line[0][0] = 1;
for (int i = 1; i < s.size(); i++) {
line[i][0] = line[i - 1][0];
if (s[i] == letter) {
count++;
if (count == 2 ||count == 10 || count == 100) {
line[i][0] += 1;
}
} else {
letter = s[i];
count = 1;
line[i][0] += 1;
}
}
auto it = s.begin();
for (int total = 1; total< s.size(); total ++) {
int letter = s[total];
int size = min(total, k);
for (int i = 1; i <= size; i++) {
// 删除当前字母的情况
line[total][i] = line[total-1][i-1];
// 删除的数量
int del =0;
int same = 0;
count = 1;
// 不删除当前字母，则把该字母往前匹配，尽量找出相同的字母，删除不同的字母，找出最优解
for (int j = total; j >=0; j --) {
int letterJ = s[j];
if (letterJ == letter) {
same ++;
if (same == 2) {
count = 2;
} else if ( same == 10) {
count = 3;
} else if (same == 100) {
count = 4;
}
if (j == 0) {
line[total][i] = min(line[total][i], count);
} else {
line[total][i] = min(line[total][i], line[j - 1][i - del] + count);
}
} else {
del ++;
if (del > i) {
break;
}
if (j == 0) {
line[total][i] = min(line[total][i], count);
} else {
line[total][i] = min(line[total][i], line[j - 1][i - del] + count);
}
}
}
}
}
return line[s.size()-1][k];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 512KB, 提交时间: 2021-11-27
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int compressString(string s, int k) {
auto calc = [](int x) {
if (x == 1) {
return 1;
}
if (x < 10) {
return 2;
}
if (x < 100) {
return 3;
}
return 4;
};
int n = s.size();
vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX >> 1));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k && j <= i; ++j) {
if (j > 0) {
f[i][j] = f[i - 1][j - 1];
}
int same = 0, diff = 0;
for (int i0 = i; i0 >= 1 && diff <= j; --i0) {
if (s[i0 - 1] == s[i - 1]) {
++same;
f[i][j] = min(f[i][j], f[i0 - 1][j - diff] + calc(same));
} else {
++diff;
}
}
}
}
return f[n][k];
}
};