【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)

这篇具有很好参考价值的文章主要介绍了【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2024-1-11

2645. 构造有效字符串的最少插入数

【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母),LeetCode,leetcode,动态规划,代理模式

方法一:计算组数

1.用count统计,能构成几组abc

2.如果当前字符大于之前字符,说明还在组内,不更新

3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新

4.最终返回值:组数*3,再减去原本的字符数,就是要插入的次数

    //2645. 构造有效字符串的最少插入数---计算组数
    public int addMinimum2(String word) {
        int n = word.length();
        int count = 1;
        //最终构成abc的组数
        for (int i = 1; i < n; i++) {
            if (word.charAt(i - 1) >= word.charAt(i)) {
                //当前字符小于等于之前字符
                count++;
                //组数加一
            }
        }
        return count*3-n;
        //返回最终构成abc的总数-原本字符,即为要插入的次数
    }
方法二:动态规划

1.从1开始,d[i]为前i个字符拼成abc需要的最小插入数

2.情况一:word[i]单独存在于一组abc中,需要插两次,才能组成abc.插入次数为之前的次数+2

3.情况二:当前字符比前一个字符大,需要插一次,就可以组成abc.修改当前插入次数为:之前的次数-1,因为之前插入的两次中已经包含了当前字符。

    public int addMinimum(String word) {
        int n = word.length();
        int[] d = new int[n + 1];
        //d[]数组用来统计,1到n的插入次数
        //从1开始,d[i]为前i个字符拼成abc需要的最小插入数。
        for (int i = 1; i <= n; i++) {
            d[i] = d[i - 1] + 2;
            //word[i]单独存在于一组abc中,在之前情况的基础上+2. eg: a+bc / b+ac / c+ab
            if (i > 1 && word.charAt(i - 1) > word.charAt(i - 2)) {
                //如果当前字符比前一个字符大,eg:ab/ ac / bc
                d[i] = d[i - 1] - 1;
                //当前字符和之前的字符在同一个abc中,重新覆盖d[i],前一个位置的插入数-1
            }
        }
        return d[n];
    }

方法三: 考虑相邻字母

1.设当前字符为x,前一个字符为y,

2.x大于y的情况:x-y-1

3.x小于等于y的情况:(x-y-1+3)mod 3 ,将计算的结果控制在0-2之间

4.开头的单独一个字符:word[0]-‘a’ ,结尾的一个字符:‘c’-word[n-1],合并为word[0]-word[n-1]+2

    public int addMinimum3(String word) {
        int n = word.length();
        int res = word.charAt(0) - word.charAt(n - 1) + 2;
        //合并处理开头和结尾的情况
        for (int i = 1; i < n; i++) {
            res += (word.charAt(i) - word.charAt(i - 1) + 2) % 3;
        }
        return res;
    }

1-11 生日快乐

点击移步博客主页,欢迎光临~

【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母),LeetCode,leetcode,动态规划,代理模式文章来源地址https://www.toymoban.com/news/detail-796434.html

到了这里,关于【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2645. 构造有效字符串的最少插入数

    给你一个字符串  word  ,你可以向其中任何位置插入 \\\"a\\\"、\\\"b\\\" 或 \\\"c\\\" 任意次,返回使  word   有效  需要插入的最少字母数。 如果字符串可以由 \\\"abc\\\" 串联多次得到,则认为该字符串  有效  。 示例 1: 示例 2: 示例 3: 提示: 1 = word.length = 50 word  仅由字母 \\\"a\\\"、\\\"b\\\" 和 \\\"c\\\" 组成

    2024年01月20日
    浏览(44)
  • 【LeetCode每日一题】2182. 构造限制重复的字符串

    2024-1-13 2182. 构造限制重复的字符串 思路: 按照字符出现次数从高到低的顺序进行重复,通过维护一个指针 j 来寻找下一个非零出现次数的字母。同时,利用 StringBuilder 对象可以高效地构建字符串,避免频繁的字符串拼接操作 首先,创建一个长度为26的数组 cnt ,用于统计字

    2024年01月18日
    浏览(46)
  • 【LeetCode题解】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)+2085. 统计出现过一次的公共字符串(哈希表)+2807. 在链表中插入最大公约数

    2645. 构造有效字符串的最少插入数 方法一:计算组数 1.用count统计,能构成几组abc 2.如果当前字符大于之前字符,说明还在组内,不更新 3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新 4.最终返回值:组数*3,再减去原本的字符数,就是要插入的次数 方法二

    2024年04月12日
    浏览(61)
  • 【每日一题】构造限制重复的字符串

    【贪心】【字符串】【2024-01-13】 2182. 构造限制重复的字符串 思路 解题思想比较简单,利用贪心思想,每次选择当前剩余字符串中字典序最大的字符加到答案字符串末尾,如果答案字符串末尾的字符已经连续出现了 repeatLimit 次,则将字典序次大的字符加到答案字符串,随后

    2024年01月22日
    浏览(43)
  • ( 字符串) 205. 同构字符串 ——【Leetcode每日一题】

    难度:简单 给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个

    2024年02月02日
    浏览(53)
  • (字符串 ) 459. 重复的子字符串——【Leetcode每日一题】

    难度:简单 给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 示例 1: 输入: s = “abab” 输出: true 解释: 可由子串 “ab” 重复两次构成。 示例 2: 输入: s = “aba” 输出: false 示例 3: 输入: s = “abcabcabcabc” 输出: true 解释: 可由子串 “abc” 重复四次构

    2024年02月07日
    浏览(45)
  • 【力扣·每日一题】2182.构造限制重复的字符串(模拟 贪心 优先队列 C++ Go)

    题目链接 给你一个字符串 s 和一个整数 repeatLimit ,用 s 中的字符构造一个新字符串 repeatLimitedString ,使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。 返回 字典序最大的 repeatLimitedString 。 如果在字符串 a 和 b 不同的第一个位置,字符串 a 中

    2024年01月17日
    浏览(53)
  • LeetCode·每日一题·415. 字符串相加·模拟

    作者:小迅 链接:https://leetcode.cn/problems/add-strings/solutions/2347085/mo-ni-zhu-shi-chao-ji-xiang-xi-by-xun-ge-fges/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。   题意 - 给定二个字符串,计算它们的和并同样以字符串形式返回。 直接从

    2024年02月16日
    浏览(40)
  • (字符串) 844. 比较含退格的字符串——【Leetcode每日一题】

    难度:简单 给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。 # 代表退格字符。 注意 :如果对空文本输入退格字符,文本继续为空。 示例 1: 输入:s = “ab#c”, t = “ad#c” 输出:true 解释:s 和 t 都会变成 “ac”。 示例 2: 输入

    2024年02月11日
    浏览(41)
  • (字符串 ) 剑指 Offer 58 - II. 左旋转字符串 ——【Leetcode每日一题】

    难度:简单 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串\\\"abcdefg\\\"和数字2,该函数将返回左旋转两位得到的结果\\\"cdefgab\\\"。 示例 1: 输入: s = “abcdefg”, k = 2 输出: “cdefgab” 示例 2:

    2024年02月08日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包