为了账号安全,请及时绑定邮箱和手机立即绑定

直觉落后于最后==i?

直觉落后于最后==i?

元芳怎么了 2022-09-22 16:32:39

我正在解决一个关于 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贡献1479条经验 获得超13个赞

因此,要了解此循环的确切用途,您必须了解其设置方式。它使用以下循环来填充它: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

希望这有帮助!


查看完整回答
反对 回复 2022-09-22
?
LEATH

TA贡献1566条经验 获得超6个赞

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

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

结束。


查看完整回答
反对 回复 2022-09-22

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信