题解 | #压缩字符串(二)#

压缩字符串(二)

http://www.nowcoder.com/practice/2724df81a7d94b70932d96b759848f0a

题意

给定字符串,和最多可以先删除的字符数量,再对它进行连续字符的压缩,求压缩后字符串的最短长度

限制:

原字符串长度不大于100

方法

dfs(TLE)

题目拆解为两部分

  1. 字符串删除
  2. 压缩字符串

对于字符串删除字符的部分,采用深度搜索的方式, 每层记录,当前遍历的字符串位置,还可以删除的字符串个数,和删除后的字符串的部分

对于压缩字符串的部分,采取遍历和计数的方式来计算压缩后的字符串长度

以题目样例"aabcccccaaa"为例

下标 上个字符 累计个数 总长度
- 0 0 0
0 a 1 0
1 a 2 0
2 b 1 2(和a不同,统计a)
3 c 1 3(和b不同,统计b)
4 c 2 3
5 c 3 3
6 c 4 3
7 c 5 3
8 a 1 5(和c不同,统计c)
9 a 2
10 a 3
- 0 1 7(和c不同,统计c)

代码

class Solution {
public:
    int zip(int cnt){
        if(cnt == 1){ // 一个字符
            return 1;
        }else if(cnt > 1 && cnt < 10){ // 一位数字符
            return 2;
        }else if(cnt > 9 && cnt < 100){ // 两位数字符
            return 3;
        }else if(cnt == 100){
            return 4;
        }
        return 0;
    }
    // 计算压缩后的长度
    int lenStr(string s){
        int ans = 0; // 总长度
        char ch = 0; // 当前字符
        int cnt = 0; // 累计个数
        for(int i = 0;i<s.length();i++){
            if(s[i] == ch){ // 字符相同
                cnt++; // 计数+1
            }else{ // 字符不同
                ans += zip(cnt); // 压缩之前的
                ch = s[i]; // 更新 字符
                cnt = 1;
            }
        }
        ans += zip(cnt);
        return ans;
    }
    
    int dfs(string &s,int idx,int k,string t){
        int r = s.length();
        if(idx == s.length()){
            return lenStr(t);
        }
        if(k){ // 删除这个字符
            r = min(r,dfs(s,idx+1,k-1,t));
        }
        return min(r,dfs(s,idx+1,k,t+s[idx]));  // 不删除这个字符
    }
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int compressString(string s, int k) {
        // write code here
        return dfs(s,0,k,"");
    }
};

复杂度分析

时间复杂度: 对于压缩的时间复杂度为O(n)O(n),但对于深搜,最坏情况,每个位置会存在删或不删,所以总时间复杂度为O(2nn)O(2^n \cdot n)

空间复杂度: 主要在于递归的深度和递归时产生的字符串的占用,所以空间复杂度为O(n2)O(n^2)

递推

设计状态 dp[i][ch][j][k]=l当前位置i,同样的字符ch连续j个,删除了k个,压缩后长度为l

zip是用于计算压缩后的长度的函数

若上个状态是dp[i][ch][j][k] 那么当选择第i个字符时

如果ch==s[i]那么有 dp[i+1][s[i]][j+1][k] = dp[i][ch][j][k] + zip(j+1) - zip(j),

否则如果第i-1不是相同的字符 dp[i][s[i]][1][k] = dp[i][ch][j][k] + zip(1), 因为和前面的字符不同,所以不会和前面的一起被压缩,所以长度为1

对于删除第i个字符的请跨国你dp[i][ch][j][k+1] = dp[i][ch][j][k]

最后在i == s.length()中找最小值即可

代码

class Solution {
public:
    int zip(int cnt){
        if(cnt == 1){ // 一个字符
            return 1;
        }else if(cnt > 1 && cnt < 10){ // 2-位数字符
            return 2;
        }else if(cnt > 9 && cnt < 100){ // 两位数字符
            return 3;
        }else if(cnt == 100){
            return 4;
        }
        return 0;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int compressString(string s, int k) {
        if(k == s.length())return 0;
        const int INF = 0x3f3f3f3f;
        // [i][ch][j][k]=l 当前位置i,同样的字符ch连续j个,删除了k个,压缩后长度为l
        // dp[i][j][k] = dp[i-1][j]
        vector<vector<vector<vector<int>> > > dp(
            s.length()+1,
            vector<vector<vector<int>>>(
                26,
                vector<vector<int>>(
                    s.length()+1,
                    vector<int>(s.length()+1,INF))));
        for(int i = 0;i<26;i++){ // 初始化
            dp[0][i][0][0] = 0;
        }
        for(int i = 0;i<s.length();i++){
            for(int ch = 0;ch<26;ch++){
                for(int j = 0;j<=i;j++){
                    for(int m = 0;m <= min(k,i);m++){
                        if(dp[i][ch][j][m] == INF)continue;
                        // 不删 i
                        if(s[i]-'a' == ch){ // 字符相同
                            dp[i+1][ch][j+1][m] = min(
                                dp[i+1][ch][j+1][m],
                                dp[i][ch][j][m] + zip(j+1)-zip(j)
                            );
                        }else{ // 字符不同
                            dp[i+1][s[i]-'a'][1][m] = min(
                                dp[i+1][s[i]-'a'][1][m],
                                dp[i][ch][j][m] + zip(1)
                            );
                        }
                        // 删 i
                        if(m < k){
                            dp[i+1][ch][j][m+1] = min(
                                dp[i+1][ch][j][m+1],
                                dp[i][ch][j][m]
                            );
                        }
                    }
                }
            }
        }
        int ans = INF;
        // 找最小值
        for(int ch = 0;ch<26;ch++){
            for(int j = 0;j<=s.length();j++){
                for(int m = 0;m <= k;m++){
                    ans = min(ans,dp[s.length()][ch][j][m]);
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 主要是状态和状态转移,其中状态转移是常数O(n3)O(n^3)

空间复杂度: 主要是状态存储O(n3)O(n^3)

全部评论

相关推荐

不愿透露姓名的神秘牛友
06-05 15:27
点赞 评论 收藏
分享
咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务