直觉落后于最后==i？

Question

我正在解决一个关于 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)

Answer 1

因此，要了解此循环的确切用途，您必须了解其设置方式。它使用以下循环来填充它：formap

for(int i = 0; i < S.length(); i++){
    map[S.charAt(i)-'a'] = i;
}

现在，这也花了我一秒钟，但请忍受我。它正在做的是循环遍历 的每个字符。非常简单。现在，它正在获取要放入数组中的索引：。这是一些非常聪明的编程。它正在做的是让角色处于当前位置。例如，如果我们在字符串中的索引处，则为 。然后我们从中减去，将它们转换为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

希望这有帮助！

Answer 2

换句话说，解决方案如下：从字符串的开头开始，让我们迭代地继续寻找满足语句条件的最短子字符串（即，对于此子字符串中的每个字母，其所有出现都属于此子字符串）。这是所谓的贪婪算法的应用，它相对直观地解释了为什么它是正确的：我们采取的子字符串越短，它们就越多，我们已经确定我们正在采取人类可能采取的最短子字符串。您所质疑的特定行执行以下操作：

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

结束。