wordpress 架站上海网站备案咨询

---

题目

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

---

1- 思路

思路
目标：同样的字母 字符串尽可能的长

• 问1：怎么确定字母数 ——> 哈希表
• 问2：怎么让字符尽可能的长？——> 统计每个字符出现的最远位置，根据单个字符的最远出现位置，判断字符串的最远出现位置
  • 如果满足 字符串中所有字符的最远出现位置 <= 当前字符串的最远出现位置，这个字符串就是最长的

---

2- 实现

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

class Solution {List<Integer> res = new ArrayList<>();public List<Integer> partitionLabels(String s) {// 1.定义 hashint[] hash = new int[26];// 2. 求单个字母最远距离for(int i = 0 ; i < s.length();i++){hash[s.charAt(i) - 'a'] = i;}int left = 0;int right = 0;// 3. 实现逻辑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 longestSub {static List<Integer> res = new ArrayList<>();public static List<Integer> partitionLabels(String str){// 1. 定义 hashint len = str.length();int[] hash = new int[len];// 2. 求单个字符最远for(int i = 0 ; i < len;i++){hash[str.charAt(i)-'a'] = i;}int left = 0;int right = 0;// 3. 实现逻辑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 str = sc.nextLine();List<Integer> forRes = partitionLabels(str);System.out.println(forRes.toString());}
}

---