【Hot100】LeetCode—763. 划分字母区间

• 原题链接：763. 划分字母区间

1- 思路

哈希表 + 双指针

• ① 找到元素最远的出现位置：哈希表
• ② 根据最远出现位置，判断区间的分界线：双指针

实现

• 1- 定义一个哈希数组，判断最远出现的位置： int[] hash = new int [27]
  • 遍历字符串，记录最远出现位置
• 2- 分割点
  • 利用数组，收集结果
  • int left = 0; int right = 0; 记录左右区间范围
  • right = Math.max(right,hash[s[i] - 'a');
    • if( i == right ) { res.push(right - left +1); left = i+1; }

思路

• ① 先通过遍历字符串，统计最远出现位置
• ② 定义 left 和 right 指针，每次依据 当前位置的最远出现位置，更新 right = Math.max(right,hash[s[i] - 'a');
  • 如果 i == right ，此时收集结果

2- 实现

⭐763. 划分字母区间——题解思路

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] hash = new int[26];

        for(int i = 0 ; i < s.length() ; i++){
            hash[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();

        // 定义 left 和 right 判断最远位置
        int left = 0;
        int right = 0;
        for(int i = 0 ; i < s.length() ; i++){
            right = Math.max(right,hash[s.charAt(i)-'a']);
            if(i==right){
                res.add(right-left+1);
                left = right+1;
            }
        }
        return res;
    }
}

3- ACM 实现

public class maxInterval {


    public static List<Integer> maxL (String str){

        // 哈希表
        int len = str.length();
        int[] hash = new int[26];

        for(int i = 0 ; i <  len;i++){
            hash[str.charAt(i) -'a'] = i;
        }


        // 2. 找到最远区间分割  双指针
        List<Integer> res = new ArrayList<>();
        int left = 0;
        int right = 0;
        for(int i = 0 ; i < len;i++ ){
            right = Math.max(right,hash[str.charAt(i)-'a']);
            if(i==right){
                res.add(right-left+1);
                left = right+1;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        System.out.println("结果是"+maxL(input).toString());
    }
}