ETH官方钱包

前往
大廳
主題

LeetCode - 830. Positions of Large Groups 解題心得

Not In My Back Yard | 2021-01-22 09:00:04 | 巴幣 0 | 人氣 158

題目連結(jié):


題目意譯:
小寫(xiě)字母字串 s 中,這些字母形成好幾個(gè)連續(xù)相同字母之群組。

例如,字串如 s = "abbxxxxzyy" 有 "a" 、 "bb" 、 "xxxx" 、 "z" 以及 "yy" 這些群組。

一個(gè)群組以一個(gè)區(qū)間 [start, end] 表示,其中 start 以及 end 代表著群組開(kāi)頭和結(jié)尾之索引值(含左右端點(diǎn))。接續(xù)上例,"xxxx" 為區(qū)間 [3, 6]。

一個(gè)群組若含有三個(gè)以上(含)的字母,即會(huì)被認(rèn)為是「大」的。

回傳所有大群組之區(qū)間,其中所有區(qū)間按照 start 索引值之大小遞增之排序。

限制:
1 ≦ s.length ≦ 1000
s 只包含小寫(xiě)英文字母。



範(fàn)例測(cè)資:
範(fàn)例 1:
輸入: s = "abbxxxxzzy"
輸出: [[3,6]]
解釋?zhuān)?"xxxx" 為唯一大群組,其 start 索引值為 3 、end 索引值為 6 。

範(fàn)例 2:
輸入: s = "abc"
輸出: []
解釋?zhuān)?我們有群組 "a" 、 "b" 以及 "c",但沒(méi)有一個(gè)是大群組。

範(fàn)例 3:
輸入: s = "abcdddeeeeaabbbcd"
輸出: [[3,5],[6,9],[12,14]]
解釋?zhuān)?大群組為 "ddd" 、 "eeee" 和 "bbb"。

範(fàn)例 4:
輸入: s = "aba"
輸出: []


解題思維:
參見(jiàn)這題如何統(tǒng)計(jì)連續(xù)相同字元區(qū)段之長(zhǎng)度。而既然你可以統(tǒng)計(jì)長(zhǎng)度,也知道其區(qū)段結(jié)束於何處(即 end 索引值),則便可以推出其開(kāi)頭(start 索引值)。

接著判斷每個(gè)連續(xù)區(qū)段,其 end - start 是否 ≧ 3。如果是,則直接將當(dāng)前的 [start, end] 加入答案之中。

可以注意到,不需要特別排序。因?yàn)槲覀兪菑淖髵叩接遥ㄋ饕敌〉酱螅虼舜鸢钢忻總€(gè)區(qū)間即照著 start 索引值由小到大排。




此次分享到此為止,如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方,也煩請(qǐng)各位大大撥冗討論。

創(chuàng)作回應(yīng)

更多創(chuàng)作