leetcode763

public class Solution
    {
        public IList<int> PartitionLabels(string S)
        {
            var dic = new Dictionary<char, int[]>();
            //记录每一个字符的第一次出现位置，和最后一次出现位置
            for (int i = 0; i < S.Length; i++)
            {
                if (!dic.ContainsKey(S[i]))
                {
                    dic.Add(S[i], new int[2] { i, i });
                }
                else
                {
                    dic[S[i]][1] = i;
                }
            }
            var list = new List<int>();
            int low = 0;
            int high = S.Length - 1;
            while (low <= high)
            {
                var c = S[low];
                var i = dic[c][0];//当前字符最小索引
                var j = dic[c][1];//当前字符最大索引
                if (j == high)
                {
                    list.Add(high - low + 1);
                    return list;
                }
                for (; i <= j; i++)
                {
                    var cc = S[i];
                    var ii = dic[cc][0];
                    var jj = dic[cc][1];
                    if (jj == high)
                    {
                        list.Add(high - low + 1);
                        return list;
                    }
                    if (jj > j)
                    {
                        j = jj;
                    }
                }
                list.Add(i - low);
                low = i;
            }

            return list;
        }
    }      

本题使用贪心算法思想，这里给出的代码是比较高效的一种解法。

转载于:https://www.cnblogs.com/asenyang/p/9759616.html