划分字母区间[贪心＞空间换时间＞数组hash优化]

贪心是一个很考察分析能力的题型之一&＃xff0c;第一步需要分析到贪心点&＃xff0c;第二步需要利用已知数据结构来完成构建代码&＃xff0c;当如果不能直接解决&＃xff0c;那就要考虑是否需要问题转换一下了。

从左到到右&＃xff0c;一旦右边没前面出现的字符&＃xff0c;就切断。&＃xff08;贪心点&＃xff09;

如何实现&＃xff1f;即如何知道右边还有没有该字符&＃xff1f;从后往前先标记最后一个字符的位置。

package everyday.greed;import java.util.*;// 划分字母区间
public class PartitionLabels {// 从左到到右&＃xff0c;一旦右边没前面出现的字符&＃xff0c;就切断。&＃xff08;贪心点&＃xff09;// 如何实现&＃xff1f;即如何知道右边还有没有该字符&＃xff1f;从后往前先标记最后一个字符的位置。public List<Integer> partitionLabels(String s) {Map<Character, Integer> fx &＃61; new HashMap<>();char[] arr &＃61; s.toCharArray();for (int i &＃61; arr.length - 1; i >&＃61; 0; i--) if (!fx.containsKey(arr[i])) fx.put(arr[i], i);List<Integer> ans &＃61; new ArrayList<>();for (int i &＃61; 0; i < arr.length; i&＃43;&＃43;) {size &＃61; fx.get(arr[i]);for (int j &＃61; i &＃43; 1; j < size; j&＃43;&＃43;) {if (fx.get(arr[j]) > size) size &＃61; fx.get(arr[j]);}ans.add(size - i &＃43; 1);i &＃61; size;}return ans;}int size;// hash数组会更快。public List<Integer> partitionLabels2(String s) {int[] fx &＃61; new int[26];char[] arr &＃61; s.toCharArray();for (int i &＃61; arr.length - 1; i >&＃61; 0; i--) if (fx[arr[i] - &＃39;a&＃39;] &＃61;&＃61; 0) fx[arr[i] - &＃39;a&＃39;] &＃61; i;List<Integer> ans &＃61; new ArrayList<>();for (int i &＃61; 0; i < arr.length; i&＃43;&＃43;) {size &＃61; fx[arr[i] - &＃39;a&＃39;];for (int j &＃61; i &＃43; 1; j < size; j&＃43;&＃43;) {if (fx[arr[j] - &＃39;a&＃39;] > size) size &＃61; fx[arr[j] - &＃39;a&＃39;];}ans.add(size - i &＃43; 1);i &＃61; size;}return ans;}
}
总结

1&＃xff09;从分析贪心点&＃xff0c;再到选者hashMap&＃xff0c;再到hash优化&＃xff0c;虽然没有问题转换&＃xff0c;但是锻炼常规分析流程。

[1] LeetCode 划分字母区间