2024-1-11
2645. 構(gòu)造有效字符串的最少插入數(shù)
方法一：計(jì)算組數(shù)
1.用count統(tǒng)計(jì)，能構(gòu)成幾組abc
2.如果當(dāng)前字符大于之前字符，說(shuō)明還在組內(nèi)，不更新
3.如果當(dāng)前字符小于等于之前字符,說(shuō)明不是同一組的abc,組數(shù)更新
4.最終返回值：組數(shù)*3，再減去原本的字符數(shù)，就是要插入的次數(shù)
//2645. 構(gòu)造有效字符串的最少插入數(shù)---計(jì)算組數(shù)
public int addMinimum2(String word) {
int n = word.length();
int count = 1;
//最終構(gòu)成abc的組數(shù)
for (int i = 1; i < n; i++) {
if (word.charAt(i - 1) >= word.charAt(i)) {
//當(dāng)前字符小于等于之前字符
count++;
//組數(shù)加一
}
}
return count*3-n;
//返回最終構(gòu)成abc的總數(shù)-原本字符，即為要插入的次數(shù)
}
方法二：動(dòng)態(tài)規(guī)劃
1.從1開始，d[i]為前i個(gè)字符拼成abc需要的最小插入數(shù)
2.情況一：word[i]單獨(dú)存在于一組abc中，需要插兩次，才能組成abc.插入次數(shù)為之前的次數(shù)+2
3.情況二：當(dāng)前字符比前一個(gè)字符大，需要插一次，就可以組成abc.修改當(dāng)前插入次數(shù)為：之前的次數(shù)-1，因?yàn)橹安迦氲膬纱沃幸呀?jīng)包含了當(dāng)前字符。
public int addMinimum(String word) {
int n = word.length();
int[] d = new int[n + 1];
//d[]數(shù)組用來(lái)統(tǒng)計(jì)，1到n的插入次數(shù)
//從1開始，d[i]為前i個(gè)字符拼成abc需要的最小插入數(shù)。
for (int i = 1; i <= n; i++) {
d[i] = d[i - 1] + 2;
//word[i]單獨(dú)存在于一組abc中，在之前情況的基礎(chǔ)上+2. eg: a+bc / b+ac / c+ab
if (i > 1 && word.charAt(i - 1) > word.charAt(i - 2)) {
//如果當(dāng)前字符比前一個(gè)字符大，eg:ab/ ac / bc
d[i] = d[i - 1] - 1;
//當(dāng)前字符和之前的字符在同一個(gè)abc中，重新覆蓋d[i],前一個(gè)位置的插入數(shù)-1
}
}
return d[n];
}
方法三: 考慮相鄰字母
1.設(shè)當(dāng)前字符為x,前一個(gè)字符為y,
2.x大于y的情況：x-y-1
3.x小于等于y的情況：(x-y-1+3)mod 3 ，將計(jì)算的結(jié)果控制在0-2之間
4.開頭的單獨(dú)一個(gè)字符：word[0]-‘a(chǎn)’ ，結(jié)尾的一個(gè)字符：‘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;
//合并處理開頭和結(jié)尾的情況
for (int i = 1; i < n; i++) {
res += (word.charAt(i) - word.charAt(i - 1) + 2) % 3;
}
return res;
}
1-11 生日快樂
點(diǎn)擊移步博客主頁(yè)，歡迎光臨~文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-796434.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-796434.html
到了這里，關(guān)于【LeetCode每日一題】2645. 構(gòu)造有效字符串的最少插入數(shù)（計(jì)算組數(shù)+動(dòng)態(tài)規(guī)劃+考慮相鄰字母）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
