[leetCode 丶 20241113] 3335. 字符串转换后的长度 l

原题: 3335.字符串转换后的长度l

描述:

给你一个字符串 s 和一个整数 t，表示要执行的 转换 次数。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：

  • 如果字符是 'z'，则将其替换为字符串 "ab"。
  • 否则，将其替换为字母表中的下一个字符。例如，'a' 替换为 'b'，'b' 替换为 'c'，依此类推。
    返回 恰好 执行 t 次转换后得到的字符串的 长度。

由于答案可能非常大，返回其对 10^9 + 7 取余的结果。

示例 1：

输入： s = "abcyy", t = 2
输出： 7
解释：

  • 第一次转换 (t = 1)
  • 'a' 变为 'b'
  • 'b' 变为 'c'
  • 'c' 变为 'd'
  • 'y' 变为 'z'
  • 'y' 变为 'z'
  • 第一次转换后的字符串为："bcdzz"
  • 第二次转换 (t = 2)
  • 'b' 变为 'c'
  • 'c' 变为 'd'
  • 'd' 变为 'e'
  • 'z' 变为 "ab"
  • 'z' 变为 "ab"
  • 第二次转换后的字符串为："cdeabab"
  • 最终字符串长度：字符串为 "cdeabab"，长度为 7 个字符。

示例 2：

输入： s = "azbk", t = 1
输出： 5
解释：

  • 第一次转换 (t = 1)
  • 'a' 变为 'b'
  • 'z' 变为 "ab"
  • 'b' 变为 'c'
  • 'k' 变为 'l'
  • 第一次转换后的字符串为："babcl"
  • 最终字符串长度：字符串为 "babcl"，长度为 5 个字符。

提示

  • 1 <= s.length <= 10^5
  • s 仅由小写英文字母组成。
  • 1 <= t <= 10^5

个人版答案

执行用时: ... ms 执行内存消耗: ... M
力扣, 你玩不起, 你这个小垃圾

class Solution {
    class Solution {
    public int lengthAfterTransformations(String s, int t) {
        // for(int i = 0; i < t ;i++){
        //     s = deal(s);
        // }
        // return (int)(s.length() %(Math.pow(10,9)+7));

        // int[] charArr = new int[26];
        // for(char c: s.toCharArray()){
        //     charArr[c - 'a']++;
        // }
        // int charZ = 0;
        // for(int i = 0; i < t; i++){
        //     if(charArr[25] != 0){
        //         charZ = charArr[25];
        //     }else {
        //         charZ = 0;
        //     }
        //     if (charZ != 0){
        //         charArr[25] = 0;
        //         charArr[0] += charZ;
        //         charArr[1] += charZ;
        //     }
        //     for(int j = 25; j >= 1; j--){
        //         if(charArr[j-1] != 0){
        //             charArr[j] += charArr[j-1];
        //             charArr[j-1] = 0;
        //         }
        //     }
        // }
        // return Arrays.stream(charArr).sum() % 1000000007 ;


        BigDecimal[] charArr = new BigDecimal[26];
        Arrays.fill(charArr, BigDecimal.ZERO);
        for(char c: s.toCharArray()){
            charArr[c - 'a'] = charArr[c - 'a'].add(BigDecimal.ONE);
        }
        BigDecimal charZ = BigDecimal.ZERO;
        for(int i = 0; i < t; i++){
            if(!charArr[25].equals(BigDecimal.ZERO)){
                charZ = charArr[25];
            }else {
                charZ = BigDecimal.ZERO;
            }
            if (!charZ.equals(BigDecimal.ZERO)){
                charArr[25] = BigDecimal.ZERO;
                charArr[0] = charZ.add(charArr[0]);
                charArr[1] = charZ.add(charArr[1]);
            }
            for(int j = 25; j >= 1; j--){
                if(!charArr[j-1].equals(BigDecimal.ZERO)){
                    charArr[j] = charArr[j-1].add(charArr[j]);
                    charArr[j-1] = BigDecimal.ZERO;
                }
            }
        }
        return Arrays.stream(charArr).count() % 1000000007;
    }

    // public static String deal(String s, int loop, int finalT){
    //     if (loop == finalT){
    //         return s;
    //     }
    //     StringBuilder sb = new StringBuilder();
    //     for(char c: s.toCharArray()){
    //         int n = c - 'a';
    //         if(n == 25){
    //             sb.append("ab");
    //         }else{
    //             sb.append((char)(n+1+'a'));
    //         }
    //     }
    //     return deal(sb.toString(), loop+1, finalT);
    // }

    // public String deal(String s){
    //     StringBuilder sb = new StringBuilder();
    //     for(char c: s.toCharArray()){
    //         int n = c - 'a';
    //         if(n == 25){
    //             sb.append("ab");
    //         }else{
    //             sb.append((char)(n+1 + 'a'));
    //         }
    //     }
    //     return sb.toString();
    // }
}

优秀解法

执行耗时: x ms

class Solution {
    static final int MODULO = 1000000007;
    static final int SIZE = 26;

    public int lengthAfterTransformations(String s, int t) {
        int[][] dp = new int[t + 1][SIZE];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            dp[0][c - 'a']++;
        }
        for (int i = 1; i <= t; i++) {
            dp[i][0] = dp[i - 1][SIZE - 1];
            dp[i][1] = (dp[i - 1][SIZE - 1] + dp[i - 1][0]) % MODULO;
            for (int j = 2; j < SIZE; j++) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
        int total = 0;
        for (int j = 0; j < SIZE; j++) {
            total = (total + dp[t][j]) % MODULO;
        }
        return total;
    }
}

个人解题思路与优秀答案解析

题目分析及个人版思路

  1. 读题易知就是简单的换位, 只有当Z时候需要向前的ab进位.
  2. 我的第一版思路就是拼接字符串...但是当次数上升后, 超时
  3. 我第一反应是for循环的问题? 然后替换为递归, 然而并没有什么作用
  4. 我又反复阅读提示, 由于结果可能非常大. 要返回一个对10的九次方+7的值进行取余...这个就...
  5. 我寻思如果拼接字符串不行, 那么我们就计数呗. 然后调整算法为计算每个数位上的字母个数[...这时候我只是隐隐的觉得可能又遇见DP了...]
  6. 好, 果然溢出. 然后我寻思, 我直接BigDecimal呗...然后这个小垃圾告诉我不支持.
  7. 为了验证算法是否可行, 我在我本地跑了一下. BigDecimal 是可以计算出来的...但是结果...emmm 我贴一个测试用例吧.
    String s = "jqktcurgdvlibczdsvnsg";
    int t = 7517;

最后一次的执行结果是

[0, 137764861705398164585047192329624471634363201524036570966515261523365671761628031669308403949, 270930105171711496887674849409883695206346000847554960531591218729537326216844328978471758932, 262005219501777605617389351878441505085296504829763940077164062833157284733929095707503596618, 253652650069205412914504458339445245104152944226400283258757783480170369943797818763858288439, 245905922494121652672866790730243822386299418031985075907608010455194411241314500995472376316, 238771070757979309153749008428584310490732695392409039918306595699420191657834747373501694500, 232227348473332043165605544401660180820880461590172401319055310541943719879341215771438264380, 226229607562217196668485180499333768565662151981185460435186906844047179784778607839276011932, 220712115728157579704233761046228549163249976649416539103151737183755634122793724244052883810, 215593506433794319754790077543169820965762677140069706364378512873126555678495847242796729568, 210782496691094721140024494428013303320913721023051560955467401732828745676609378716208724809, 206183972328982636161891710660991542852686709125329180928022399438243975350802036840259767799, 201705030302542621381057805139037126853676202206808891392356670664201314830560703099768882545, 197260584488796207933115789496624226708312910598640134443188173484408675813231084476164220810, 192778184786739213955921764194238117148142514594115812211372734274077435868708219998339698398, 188201766407700392167684756165996946189294648559410763505746808521097203855613796164540046366, 183494131880337025813918885538273441140634475105478330230720596349897602927990185201517686108, 178638065432863638671025164981077143561386311203994262708128649361377826756928281011057607595, 173636079791227281349767571286744123617833361328236015486609062820334479243697963409617201328, 168508890579305317209133708664667398118427321479749118740014966189703332673294489476708832412, 163292795793656708408405402361578356565824132110263918971842499928585467225015187318989566194, 158036201347139638638818428366188990290630816158554645696532589643664378471246656542073581457, 152795574845987450987746922784100419587730153791763823786432414271692485099528240489629930463, 147631127507277572565242157956984540771277993718088040092615041215457524491202525361059241772, 142602519668493273615429162674603039690815330125082142207093432314067539951376197576240092892]

哈哈哈. 我绷不住了...果然很大啊~
看来还是要学DP啊...mark一下, 回头就学下. 不然总是遇见这种题...没法做了

进阶版思路
数位DP. 看一个大哥的吧. 解释的挺详细的...但是我不想看, 等我学会了再说. 哈哈哈哈哈
3335

   
北京 位置
2 点赞
0 关注
0 收藏


1 感谢 


3 回帖 
1.6K