2024-1-11
2645. 构造有效字符串的最少插入数
方法一:计算组数
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 生日快乐
点击移步博客主页,欢迎光临~文章来源:https://www.toymoban.com/news/detail-796434.html
文章来源地址https://www.toymoban.com/news/detail-796434.html
到了这里,关于【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!