我正在解決一個關于 LeetCode.com 的問題：給出了小寫字母的字符串 S。我們希望將此字符串劃分為盡可能多的部分，以便每個字母最多出現在一個部分，并返回表示這些部分大小的整數列表。示例：輸入：S = “ababcbacadefegdehijhklij”輸出：[9，7，8]解釋：分區是“ababcbaca”，“defegde”，“hijhklij”。這是一個分區，因此每個字母最多出現在一個部分。像“阿巴巴卡德”“hijhklij”這樣的分區是不正確的，因為它將S分成更少的部分。其中一個高度支持的解決方案如下：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; }}雖然我確實理解解決方案，但我對聲明和子句不是很滿意。這里到底在做什么？last = Math.max(last, map[S.charAt(i)-'a']);if(last == i)
2 回答
侃侃爾雅
TA貢獻1801條經驗 獲得超16個贊
因此，要了解此循環的確切用途，您必須了解其設置方式。它使用以下循環來填充它：formap
for(int i = 0; i < S.length(); i++){
map[S.charAt(i)-'a'] = i;
}現在，這也花了我一秒鐘，但請忍受我。它正在做的是循環遍歷 的每個字符。非常簡單?，F在，它正在獲取要放入數組中的索引：。這是一些非常聰明的編程。它正在做的是讓角色處于當前位置。例如，如果我們在字符串中的索引處，則為 。然后我們從中減去，將它們轉換為UTF-16字符代碼，并將它們彼此相減。這會將它們放置在數組中的位置。然后，它將該索引設置為等于 。因此，在字符串的索引 1 處，數組的元素 1 等于 1。有點令人困惑，但讓我們繼續前進。如果我們位于字符串的索引 5 處，則最后一次出現 。由于 仍然是 1，它將覆蓋索引 1 處的數組，但因為 已更改，因此值已更改。由于這是最后一個索引，我們可以知道數組中每個字符的最后一個索引。SiS.charAt(i)-'a'1S.charAt(i)'b''a'1i'b''b'-'a'i
現在我們已經排除了數組填充，讓我們進入您的實際問題。在下一個循環中，它像第一次一樣遍歷數組，但這次它知道所有字符的最后一個索引。因此，當我們運行語句時，它所做的是從數組中獲取當前字符的最后一個索引，使用與前面描述的方法相同的方法。然后，將其與當前值進行比較。為什么這是特殊的，因為該值是持久的。因此，它獲取 的最后一個索引，并獲取 的最后一個索引，并獲取兩者中較大的索引。這就是實際上將它們放在其部分中的原因。因此，現在我們已經將其作為當前部分的最后一個索引，我們可以將其與實際的當前索引進行比較。如果它們相等，則位于該部分的末尾，并且可以將其添加到列表中。last = Math.max(last, map[S.charAt(i)-'a']);last'a''b'last
我希望這一切都能使這一切成為現實，不要猶豫，問任何問題！
編輯：讓我們看一個示例。假設我們有字符串：。如果我們運行填充數組的第一個循環，它將如下所示：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 | | | | | | | | | | | | |
+----------------+---+---+---+----+----+----+----+----+----+----+----+----+
（注：字符表示僅供參考，哪些索引是哪些）
當我們開始第二個 for 循環時，我們得到字符串中的字符為 0，即 。然后，我們檢查 它的最后一個索引在哪里，即 8。由于當前索引是 0 而不是 8，因此我們轉到下一個索引。下一個字符 是 ，在 中的值為 5。我們獲取前一個值之間的最大值，即 8 和 5，以獲得這兩個字符組合的最后一個索引。'a'map'b'maplast
讓我們跳到位置 8。到這個時候，我們已經看到了、 和 。他們所有最后的指數中最大的是，是8。由于我們位于位置 8，并且 的值為 8，因此我們可以說 和 之間的字符是一個組，將其添加到列表中，并將 的值設置為 的索引。這是為了設置下一組的正確起始位置。'a''b''c''a'laststartlaststartlast+1
現在，如果我們移動到下一個索引，索引9，我們有一個我們以前從未見過的新字符。我們只是重新開始這個過程，就好像我們在位置1一樣。索引 9 是 ，其最后一個索引為 14。由于我們不在索引 14 處，因此我們繼續討論下一個索引。在索引 10 處，我們有 .這個索引的最后一個索引是 15，比 的 14 大，所以我們取 15，因為它更大。這基本上意味著，如果 和 在一個組中，它至少必須一直到索引 15，以便封裝它們的所有字符。然后，它運行其余部分，更新 ，直到它到達最后，在那里它將其作為一個組切斷。'd''e''d''d''e'last
希望這有幫助！
LEATH
TA貢獻1936條經驗 獲得超7個贊
換句話說，解決方案如下：從字符串的開頭開始，讓我們迭代地繼續尋找滿足語句條件的最短子字符串（即，對于此子字符串中的每個字母，其所有出現都屬于此子字符串）。這是所謂的貪婪算法的應用，它相對直觀地解釋了為什么它是正確的：我們采取的子字符串越短，它們就越多，我們已經確定我們正在采取人類可能采取的最短子字符串。您所質疑的特定行執行以下操作：
last = Math.max(last, map[S.charAt(i)-'a'])- 我們正在計算當前子字符串中的所有字符，哪個字符盡可能向右出現
if(last == i){- 我們正在檢查當前子字符串中的所有字符中，盡可能靠近右側的字符是否是我們當前正在查看的字符 - 這意味著子字符串可以在這里結束
讓我們看一個此方法如何工作的示例。讓我們嘗試對字符串進行分區。我們構造這個幫助程序數組，如下所示。abacdbzzmap{2, 5, 3, 4, 0, ..., 0, 7}
i=0：我們從字符串的左側開始，看看字符 。如果字符串中沒有更多的 ，我們可以在這里完成我們的第一個子字符串，并從下一個字符開始一個新的子字符串。不幸的是，字符串中有更多的 's，我們通過更新到 來實現。aaalastmap['a'-'a']=2
i=1：我們正在觀察并意識到，有比我們當前更遠的，即，在's和'之間，最后一個發生在更右邊。我們通過更新到 來反映這一觀察結果。bblastabblastmap['b'-'a']=5
i=2：我們再次遇到一個，它是字符串中的最后一個，但我們不能在這里結束我們的子字符串，因為我們知道我們的子字符串中有一些東西（）仍然在它之外出現。aab
i=3， 4：我們遇到 a 和 a ，它們在我們的狀態中沒有任何變化，因為它們沒有任何其他事件。 仍然是 5。cdlast
i=5：我們終于找到了最后一個.此時，條件已滿足;換句話說，在我們的子字符串（， ， ，）中沒有從左到右的字母出現。這是我們可以采用的最短的子字符串，我們自豪地將其添加到分區中，并在下一個位置開始新的子字符串。blast == iabcd
i=6：我們遇到 一個 和 更新其最右邊出現的索引 。zlastmap['z'-'a']=7
i=7：找到第二個，并滿足（對于字符串中的最后一個字符，這將永遠為真），因此我們將此字符串添加到分區中。zlast == i
結束。
添加回答
舉報
0/150
提交
取消