国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

算法第十七天-構(gòu)造有效字符串的最少插入數(shù)

2年前作者：alstonlou分類：Toy博客閱讀(22)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了算法第十七天-構(gòu)造有效字符串的最少插入數(shù)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

構(gòu)造有效字符串的最少插入數(shù)

題目要求

算法第十七天-構(gòu)造有效字符串的最少插入數(shù),算法基礎(chǔ),算法,leetcode,python

解題思路

考慮abc的個(gè)數(shù)

假設(shè)答案有n個(gè)"abc"組成，那么需要插入的字符個(gè)數(shù)為 $3 ? n ? l e n (s)$ 。

對(duì)于相鄰的兩個(gè)字符x和y（x在y左側(cè)）：

如果 $x < y$ ，那么x和y可以在同一個(gè)"abc"內(nèi)，否則一定不在；
如果 $x\ge y$ ，那么x和y一定不可以在同一個(gè)"abc"內(nèi)，

所以， $n$ 就是 $x\ge y$ 的次數(shù)加1文章來源地址http://www.zghlxwxcb.cn/news/detail-799002.html

代碼


class Solution:
    def addMinimum(self, s: str) -> int:
        ans = ord(s[0]) - ord(s[-1]) + 2
        for x, y in pairwise(map(ord, s)):
            ans += (y - x + 2) % 3
        return ans

復(fù)雜度分析

時(shí)間復(fù)雜度： $O (n)$ ，其中 $n$ 為word的長(zhǎng)度
空間復(fù)雜度： $O (1)$

到了這里，關(guān)于算法第十七天-構(gòu)造有效字符串的最少插入數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

【LeetCode每日一題】2645. 構(gòu)造有效字符串的最少插入數(shù)（計(jì)算組數(shù)+動(dòng)態(tài)規(guī)劃+考慮相鄰字母）
2024-1-11 2645. 構(gòu)造有效字符串的最少插入數(shù) 方法一：計(jì)算組數(shù) 1.用count統(tǒng)計(jì)，能構(gòu)成幾組abc 2.如果當(dāng)前字符大于之前字符，說明還在組內(nèi)，不更新 3.如果當(dāng)前字符小于等于之前字符,說明不是同一組的abc,組數(shù)更新 4.最終返回值：組數(shù)*3，再減去原本的字符數(shù)，就是要插入的次數(shù)
2024年01月17日
瀏覽(23)
【力扣·每日一題】2645. 構(gòu)造有效字符串的最小插入數(shù)（動(dòng)態(tài)規(guī)劃貪心滾動(dòng)數(shù)組優(yōu)化 C++ Go）
題目鏈接給你一個(gè)字符串 word ，你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次，返回使 word 有效需要插入的最少字母數(shù)。如果字符串可以由 “abc” 串聯(lián)多次得到，則認(rèn)為該字符串有效。提示： 1 = w o r d . l e n g t h = 50 1 = word.length = 50 1 = w or d . l e n g t h = 50 w
2024年01月16日
瀏覽(26)
【算法題】2745. 構(gòu)造最長(zhǎng)的新字符串
給你三個(gè)整數(shù) x ，y 和 z 。這三個(gè)整數(shù)表示你有 x 個(gè) “AA” 字符串，y 個(gè) “BB” 字符串，和 z 個(gè) “AB” 字符串。你需要選擇這些字符串中的部分字符串（可以全部選擇也可以一個(gè)都不選擇），將它們按順序連接得到一個(gè)新的字符串。新字符串不能包含子字符串 “AAA” 或者
2024年02月12日
瀏覽(17)
【LeetCode題解】2645. 構(gòu)造有效字符串的最少插入數(shù)（計(jì)算組數(shù)+動(dòng)態(tài)規(guī)劃+考慮相鄰字母）+2085. 統(tǒng)計(jì)出現(xiàn)過一次的公共字符串（哈希表）+2807. 在鏈表中插入最大公約數(shù)
2645. 構(gòu)造有效字符串的最少插入數(shù) 方法一：計(jì)算組數(shù) 1.用count統(tǒng)計(jì)，能構(gòu)成幾組abc 2.如果當(dāng)前字符大于之前字符，說明還在組內(nèi)，不更新 3.如果當(dāng)前字符小于等于之前字符,說明不是同一組的abc,組數(shù)更新 4.最終返回值：組數(shù)*3，再減去原本的字符數(shù)，就是要插入的次數(shù) 方法二
2024年04月12日
瀏覽(96)
算法通關(guān)村第十二關(guān)-字符串基礎(chǔ)題目
思路：遍歷字符串，將第i個(gè)字符和第N-i-1個(gè)字符串交換即可；代碼實(shí)現(xiàn)：題目：反轉(zhuǎn)字符串2 思路：每2k個(gè)一組，將其前k個(gè)字符反轉(zhuǎn)，使用i+k與字符串長(zhǎng)度n判斷剩余字符串長(zhǎng)度屬于（0，k）還是 [k,2k)之間；然后按照要求剩余字符串即可；代碼實(shí)現(xiàn)：題目：僅僅反轉(zhuǎn)字母思
2024年01月22日
瀏覽(21)
算法通關(guān)村第十二關(guān)——字符串反轉(zhuǎn)問題解析
字符串反轉(zhuǎn)是關(guān)于字符串算法里的重要問題，雖然不是太難，但需要考慮到一些邊界問題。本篇文章就對(duì)幾道字符串反轉(zhuǎn)題目進(jìn)行分析。力扣344題，編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 s 的形式給出。不要給另外的數(shù)組分配額外的空間，
2024年02月10日
瀏覽(21)
算法通關(guān)村第十二關(guān)——不簡(jiǎn)單的字符串轉(zhuǎn)換問題
字符串是我們?cè)谌粘ｉ_發(fā)中最常處理的數(shù)據(jù)，雖然它本身不是一種數(shù)據(jù)結(jié)構(gòu)，但是由于其可以包含所有信息，所以通常作為數(shù)據(jù)的一種形式出現(xiàn)，由于不同語言創(chuàng)建和管理字符串的方式也各有差異，因此針對(duì)不同語言特征又產(chǎn)生了很多問題。常見的字符串轉(zhuǎn)換題目，也就是在
2024年02月10日
瀏覽(24)
[Go版]算法通關(guān)村第十二關(guān)黃金——字符串沖刺題
題目鏈接：LeetCode-14. 最長(zhǎng)公共前綴以第一個(gè)子字符串為標(biāo)準(zhǔn)，遍歷其每個(gè)字符時(shí)，內(nèi)嵌遍歷其余子字符串的對(duì)應(yīng)字符是否一致。不一致時(shí)，則返回當(dāng)前字符之前的子字符串。復(fù)雜度：時(shí)間復(fù)雜度 O ( n ? m ) O(n*m) O ( n ? m ) 、空間復(fù)雜度 O ( 1 ) O(1) O ( 1 ) 時(shí)間復(fù)雜度：其中 n
2024年02月12日
瀏覽(22)
不簡(jiǎn)單的字符串轉(zhuǎn)換問題（算法村第十二關(guān)青銅挑戰(zhàn)）
709. 轉(zhuǎn)換成小寫字母 - 力扣（LeetCode）給你一個(gè)字符串 s ，將該字符串中的大寫字母轉(zhuǎn)換成相同的小寫字母，返回新的字符串。 1 = s.length = 100 解大寫字母和小寫字母的值之間存在固定的差異。例如，小寫字母 a 的ASCII值為 97 ，而對(duì)應(yīng)的大寫字母 A 的ASCII值為 65 ，兩者之差恰
2024年01月25日
瀏覽(28)
數(shù)據(jù)結(jié)構(gòu)與算法之字符串: Leetcode 20. 有效的括號(hào) (Typescript版)
有效的括號(hào) https://leetcode.cn/problems/valid-parentheses/ 描述給定一個(gè)只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判斷字符串是否有效。有效字符串需滿足：左括號(hào)必須用相同類型的右括號(hào)閉合。左括號(hào)必須以正確的順序閉合。每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相
2024年02月01日
瀏覽(22)

<b id="nky2h"><rt id="nky2h"></rt></b>

<pre id="nky2h"></pre>