LeetCode1446连续字符
LeetCode 1446 连续字符解题思考
⼀、题⽬描述：
  给你⼀个字符串 s ，字符串的「能量」定义为：只包含⼀种字符的最长⾮空⼦字符串的长度。请你返回字符串的能量。
⽰例 1：　
输⼊：s = "leetcode"
输出：2
解释：⼦字符串"ee"长度为2，只包含字符'e'。
⽰例 2：
输⼊：s = "abbcccddddeeeeedcba"100个常量字符串
输出：5
解释：⼦字符串"eeeee"长度为5，只包含字符'e'。
⽰例3：
输⼊：s = "triplepillooooow"
输出：5
⽰例4：
输⼊：s = "hooraaaaaaaaaaay"
输出：11
⽰例5：
输⼊：s = "tourist"
输出：1
提⽰：
1 <= s.length <= 500
s 只包含⼩写英⽂字母。
⼆、题⽬分析：
  实际上就是出⼀个字符上，连续相同字母个数的最⼤值。归为字符串，或者模拟题的类⽐。
  我先画个流程图，再结合分析下：
分析：
  （1）最外层初始值：ans保存最终结果值，i 是给出字符串A[x]的第⼀个位置（ 1<= x <=len(A) ）。
（2）每⼀次遍历i：cnt 和 j 的初始值都为 1。
    cnt 记录的是每个 i 的最长步长。即，每遍历⼀个A[i]，当 A[i+cnt] = A[i] 时（cnt >= 1），cnt 相对A[i] 可以⾛的最长步数；j 是每次遍历i，相对 i 的下⼀个位置，如果A[i]=A[j]，j 就前进⼀个位置，步长cnt相应加1，对应上图的 j = j+1，同时根据当前步长cnt，去更新ans的值该题有个优化，就是单独拎出来 cnt=1 的判断，如果cnt = 1，意味着 j=i+1，即两个紧挨着的两个字符不相等，此时 i 前进到下⼀个位置
（对应上图：i=i+1）；如果cnt != 1，意味着 j 相对 i 不⽌⾛了⼀步，曾经⾛过上图A[i] = A[j] 的判断！也就是最长相同字母⼦串为：
A[i]=A[i+cnt]，但 A[i]  != A[i+cnt+1]，即字符不相等，我们应该更新下⼀次遍历的 i 的位置，进⾏下⼀轮 i 的遍历。我们不再需要⽐较 i ~ i+cnt 的位置了，因为前⾯已经算过，这些位置的字符都是相等的，所以 i 的下⼀个位置应该跳到 i+cnt+1 。
拿上⾯的字符串作为例⼦，当 i = 7，j 可以⾛到10的位置，cnt等于3，⾛到11的位置发现跟A[i] 不相等。此时应更新下⼀个遍历的 i 位置，应该是A[11]，公式就是 i = i+cnt+1=7+3+1 = 11。我们没有必要将 i 前进⼀个步数，因为前⼀趟⽐较相等的时候，已经知道A[7]到A[10]都是相等的
官⽅竟然没做 i 的优化，有点意外…… 但⽐我⽅法⽤少了⼀个变量，哈哈哈
  还是建议⼤家思考过再看吧~~~

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。