【Hot100】LeetCode—763. 划分字母区间
目录
- 1- 思路
- 哈希表 + 双指针
- 2- 实现
- ⭐763. 划分字母区间——题解思路
- 3- ACM 实现
- 原题链接：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());}
}