Java-LeetCode763. 划分字母区间-滑动窗口

• 算法
  • 滑动窗口
  • 1.初始化区间左右范围start=0，end=0
  • 2.从第一个字符开始遍历，每次找到相同字符的lastIndex；如果比end大，更新end
  • 3.当遍历到end时，划分一个区间，同时更新区间的左范围start=end+1

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        System.out.println(partitionLabels(s).toString().replaceAll("[\\[|\\]]", "").replaceAll(", ", " "));
    }

    // 不限定字符范围
    public static List<Integer> partitionLabels(String S) {
        ArrayList<Integer> result = new ArrayList<>(10);
        int start = 0, end = 0;
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, S.lastIndexOf(S.charAt(i)));
            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }

    // 限定字符范围
    public static List<Integer> partitionLabels(String S) {
        ArrayList<Integer> result = new ArrayList<>(10);
        int[] map = new int[26];
        for (int i = 0; i < S.length(); i++) {
            map[S.charAt(i) - 'A'] = i;
        }
        int start = 0, end = 0;
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, map[S.charAt(i)-'A']);
            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }