我正在解決一個(gè)關(guān)于 LeetCode.com 的問題：給出了小寫字母的字符串 S。我們希望將此字符串劃分為盡可能多的部分，以便每個(gè)字母最多出現(xiàn)在一個(gè)部分，并返回表示這些部分大小的整數(shù)列表。示例：輸入：S = “ababcbacadefegdehijhklij”輸出：[9，7，8]解釋：分區(qū)是“ababcbaca”，“defegde”，“hijhklij”。這是一個(gè)分區(qū)，因此每個(gè)字母最多出現(xiàn)在一個(gè)部分。像“阿巴巴卡德”“hijhklij”這樣的分區(qū)是不正確的，因?yàn)樗鼘分成更少的部分。其中一個(gè)高度支持的解決方案如下：public List<Integer> partitionLabels(String S) { if(S == null || S.length() == 0){ return null; } List<Integer> list = new ArrayList<>(); int[] map = new int[26]; // record the last index of the each char for(int i = 0; i < S.length(); i++){ map[S.charAt(i)-'a'] = i; } // record the end index of the current sub string int last = 0; int start = 0; for(int i = 0; i < S.length(); i++){ last = Math.max(last, map[S.charAt(i)-'a']); if(last == i){ list.add(last - start + 1); start = last + 1; } } return list; }}雖然我確實(shí)理解解決方案，但我對(duì)聲明和子句不是很滿意。這里到底在做什么？last = Math.max(last, map[S.charAt(i)-'a']);if(last == i)
2 回答
侃侃爾雅
TA貢獻(xiàn)1801條經(jīng)驗(yàn) 獲得超16個(gè)贊
因此，要了解此循環(huán)的確切用途，您必須了解其設(shè)置方式。它使用以下循環(huán)來填充它：formap
for(int i = 0; i < S.length(); i++){
map[S.charAt(i)-'a'] = i;
}現(xiàn)在，這也花了我一秒鐘，但請(qǐng)忍受我。它正在做的是循環(huán)遍歷 的每個(gè)字符。非常簡(jiǎn)單。現(xiàn)在，它正在獲取要放入數(shù)組中的索引：。這是一些非常聰明的編程。它正在做的是讓角色處于當(dāng)前位置。例如，如果我們?cè)谧址械乃饕?，則為 。然后我們從中減去，將它們轉(zhuǎn)換為UTF-16字符代碼，并將它們彼此相減。這會(huì)將它們放置在數(shù)組中的位置。然后，它將該索引設(shè)置為等于 。因此，在字符串的索引 1 處，數(shù)組的元素 1 等于 1。有點(diǎn)令人困惑，但讓我們繼續(xù)前進(jìn)。如果我們位于字符串的索引 5 處，則最后一次出現(xiàn) 。由于 仍然是 1，它將覆蓋索引 1 處的數(shù)組，但因?yàn)?已更改，因此值已更改。由于這是最后一個(gè)索引，我們可以知道數(shù)組中每個(gè)字符的最后一個(gè)索引。SiS.charAt(i)-'a'1S.charAt(i)'b''a'1i'b''b'-'a'i
現(xiàn)在我們已經(jīng)排除了數(shù)組填充，讓我們進(jìn)入您的實(shí)際問題。在下一個(gè)循環(huán)中，它像第一次一樣遍歷數(shù)組，但這次它知道所有字符的最后一個(gè)索引。因此，當(dāng)我們運(yùn)行語句時(shí)，它所做的是從數(shù)組中獲取當(dāng)前字符的最后一個(gè)索引，使用與前面描述的方法相同的方法。然后，將其與當(dāng)前值進(jìn)行比較。為什么這是特殊的，因?yàn)樵撝凳浅志玫?。因此，它獲取 的最后一個(gè)索引，并獲取 的最后一個(gè)索引，并獲取兩者中較大的索引。這就是實(shí)際上將它們放在其部分中的原因。因此，現(xiàn)在我們已經(jīng)將其作為當(dāng)前部分的最后一個(gè)索引，我們可以將其與實(shí)際的當(dāng)前索引進(jìn)行比較。如果它們相等，則位于該部分的末尾，并且可以將其添加到列表中。last = Math.max(last, map[S.charAt(i)-'a']);last'a''b'last
我希望這一切都能使這一切成為現(xiàn)實(shí)，不要猶豫，問任何問題！
編輯：讓我們看一個(gè)示例。假設(shè)我們有字符串：。如果我們運(yùn)行填充數(shù)組的第一個(gè)循環(huán)，它將如下所示：ababcbacadefegdehijhklijmap
+----------------+---+---+---+----+----+----+----+----+----+----+----+----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
+----------------+---+---+---+----+----+----+----+----+----+----+----+----+
| Value | 8 | 5 | 7 | 14 | 15 | 11 | 13 | 19 | 22 | 23 | 20 | 21 |
+----------------+---+---+---+----+----+----+----+----+----+----+----+----+
| Character | a | b | c | d | e | f | g | h | i | j | k | l |
| representation | | | | | | | | | | | | |
+----------------+---+---+---+----+----+----+----+----+----+----+----+----+
（注：字符表示僅供參考，哪些索引是哪些）
當(dāng)我們開始第二個(gè) for 循環(huán)時(shí)，我們得到字符串中的字符為 0，即 。然后，我們檢查 它的最后一個(gè)索引在哪里，即 8。由于當(dāng)前索引是 0 而不是 8，因此我們轉(zhuǎn)到下一個(gè)索引。下一個(gè)字符 是 ，在 中的值為 5。我們獲取前一個(gè)值之間的最大值，即 8 和 5，以獲得這兩個(gè)字符組合的最后一個(gè)索引。'a'map'b'maplast
讓我們跳到位置 8。到這個(gè)時(shí)候，我們已經(jīng)看到了、 和 。他們所有最后的指數(shù)中最大的是，是8。由于我們位于位置 8，并且 的值為 8，因此我們可以說 和 之間的字符是一個(gè)組，將其添加到列表中，并將 的值設(shè)置為 的索引。這是為了設(shè)置下一組的正確起始位置。'a''b''c''a'laststartlaststartlast+1
現(xiàn)在，如果我們移動(dòng)到下一個(gè)索引，索引9，我們有一個(gè)我們以前從未見過的新字符。我們只是重新開始這個(gè)過程，就好像我們?cè)谖恢?一樣。索引 9 是 ，其最后一個(gè)索引為 14。由于我們不在索引 14 處，因此我們繼續(xù)討論下一個(gè)索引。在索引 10 處，我們有 .這個(gè)索引的最后一個(gè)索引是 15，比 的 14 大，所以我們?nèi)?15，因?yàn)樗?。這基本上意味著，如果 和 在一個(gè)組中，它至少必須一直到索引 15，以便封裝它們的所有字符。然后，它運(yùn)行其余部分，更新 ，直到它到達(dá)最后，在那里它將其作為一個(gè)組切斷。'd''e''d''d''e'last
希望這有幫助！
LEATH
TA貢獻(xiàn)1936條經(jīng)驗(yàn) 獲得超7個(gè)贊
換句話說，解決方案如下：從字符串的開頭開始，讓我們迭代地繼續(xù)尋找滿足語句條件的最短子字符串（即，對(duì)于此子字符串中的每個(gè)字母，其所有出現(xiàn)都屬于此子字符串）。這是所謂的貪婪算法的應(yīng)用，它相對(duì)直觀地解釋了為什么它是正確的：我們采取的子字符串越短，它們就越多，我們已經(jīng)確定我們正在采取人類可能采取的最短子字符串。您所質(zhì)疑的特定行執(zhí)行以下操作：
last = Math.max(last, map[S.charAt(i)-'a'])- 我們正在計(jì)算當(dāng)前子字符串中的所有字符，哪個(gè)字符盡可能向右出現(xiàn)
if(last == i){- 我們正在檢查當(dāng)前子字符串中的所有字符中，盡可能靠近右側(cè)的字符是否是我們當(dāng)前正在查看的字符 - 這意味著子字符串可以在這里結(jié)束
讓我們看一個(gè)此方法如何工作的示例。讓我們嘗試對(duì)字符串進(jìn)行分區(qū)。我們構(gòu)造這個(gè)幫助程序數(shù)組，如下所示。abacdbzzmap{2, 5, 3, 4, 0, ..., 0, 7}
i=0：我們從字符串的左側(cè)開始，看看字符 。如果字符串中沒有更多的 ，我們可以在這里完成我們的第一個(gè)子字符串，并從下一個(gè)字符開始一個(gè)新的子字符串。不幸的是，字符串中有更多的 's，我們通過更新到 來實(shí)現(xiàn)。aaalastmap['a'-'a']=2
i=1：我們正在觀察并意識(shí)到，有比我們當(dāng)前更遠(yuǎn)的，即，在's和'之間，最后一個(gè)發(fā)生在更右邊。我們通過更新到 來反映這一觀察結(jié)果。bblastabblastmap['b'-'a']=5
i=2：我們?cè)俅斡龅揭粋€(gè)，它是字符串中的最后一個(gè)，但我們不能在這里結(jié)束我們的子字符串，因?yàn)槲覀冎牢覀兊淖幼址杏幸恍〇|西（）仍然在它之外出現(xiàn)。aab
i=3， 4：我們遇到 a 和 a ，它們?cè)谖覀兊臓顟B(tài)中沒有任何變化，因?yàn)樗鼈儧]有任何其他事件。 仍然是 5。cdlast
i=5：我們終于找到了最后一個(gè).此時(shí)，條件已滿足;換句話說，在我們的子字符串（， ， ，）中沒有從左到右的字母出現(xiàn)。這是我們可以采用的最短的子字符串，我們自豪地將其添加到分區(qū)中，并在下一個(gè)位置開始新的子字符串。blast == iabcd
i=6：我們遇到 一個(gè) 和 更新其最右邊出現(xiàn)的索引 。zlastmap['z'-'a']=7
i=7：找到第二個(gè)，并滿足（對(duì)于字符串中的最后一個(gè)字符，這將永遠(yuǎn)為真），因此我們將此字符串添加到分區(qū)中。zlast == i
結(jié)束。
添加回答
舉報(bào)
0/150
提交
取消