划分字母区间

题目

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

具体思路

• 确定每个字母的终点位置
  • 不能想着一个for循环，就解决所有问题
• 设置hash数组进行映射
• 初始化cur
  • 如果当前的cur不等于当前遍历到的i
    • 判断当前遍历到的是否更大，如果更大那就更新数组，否则什么都不做
  • 如果当前得到的结果是cur == i那么收集切割点，并尝试设置下一个收割点
• 从收割点，得到最终长度

具体代码

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // 设置hash映射
        vector<int> res;
        vector<int> hash(27, 0);
        for (int i = 0; i < s.size(); i++) {
            hash[s[i] - 'a'] = i;
        }
        // 初始化cur
        int cur = hash[s[0] - 'a'];
        for (int i = 0; i < s.size(); i++) {
            if (hash[s[i] - 'a'] > cur)
                cur = hash[s[i] - 'a'];
            // 切割完一片
            if (i == cur) {
                // 记录切割点的位置
                res.push_back(i + 1);
                // 如果存在下一次切割，那么重新设置cur
                if (i + 1 < s.size())
                    cur = hash[s[i + 1] - 'a'];
            }
        }
        // 按照切割点，确定每一段的长度，从后向前
        for (int i = res.size() - 1; i >= 1; i--) {
            res[i] -= res[i - 1];
        }
        return res;
    }
};

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> hash(27, 0);
        vector<int> res;
        for (int i = 0; i < s.size(); i++) {
            hash[s[i] - 'a'] = i;
        }
        int cur = 0;
        int left = 0;
        for (int i = 0; i < s.size(); i++) {
            cur = max(cur, hash[s[i] - 'a']);
            if (i == cur) {
                res.push_back(cur - left + 1);
                left = cur + 1;
            }
        }
        return res;
    }
};

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] hash = new int[30];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int end = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, hash[s.charAt(i) - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}

改成区间来做:

1. 初始化左右区间；
2. 按照左区间进行排序；
3. 合并区间；

    public List<Integer> partitionLabels(String s) {
        int count = 1;
        int[][] map = new int[27][2];
        for(int[] row : map){
            Arrays.fill(row, s.length());
        }
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (map[index][0] == s.length()) {
                map[index][0] = i;
                map[index][1] = i;
            } else {
                map[index][1] = i;
            }
        }
        Arrays.sort(map, (x, y) -> {
            return x[0] == y[0] ? x[1] - y[1] : x[0] - y[0];
        });

        // 合并区间
        int begin = map[0][0];
        int end = map[0][1];
        List<Integer> res = new ArrayList<>();
        for(int i = 1; i < map.length ; i++){
            if(map[i][0] > end){
                res.add(end - begin + 1);
                begin = map[i][0];
            }
            end = Math.max(end, map[i][1]);
        }
        return res;
    }