数组
大家好，我是老马。
今天我们一起来学习一下数组这种数据结构。
主要知识
数组需要拆分下面几个部分：
-
理论介绍
-
源码分析
-
数据结构实现？
-
题目练习（按照算法思想分类）
-
梳理对应的 sdk 包
-
应用实战
因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。
为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。
简单介绍1，重点为4。其他不是本系列的重点。
相关题目
本质：贪心+合并区间
【leetcode】力扣 数组 array-02-56. 合并区间
扫描线专题
2405. 子字符串的最优划分
给你一个字符串 s ，请你将该字符串划分成一个或多个 子字符串 ，并满足每个子字符串中的字符都是 唯一 的。
也就是说，在单个子字符串中，字母的出现次数都不超过 一次 。
满足题目要求的情况下，返回 最少 需要划分多少个子字符串。
注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。
示例 1：
输入：s = “abacaba” 输出：4 解释： 两种可行的划分方法分别是 (“a”,”ba”,”cab”,”a”) 和 (“ab”,”a”,”ca”,”ba”) 。 可以证明最少需要划分 4 个子字符串。 示例 2：
输入：s = “ssssss” 输出：6 解释： 只存在一种可行的划分方法 (“s”,”s”,”s”,”s”,”s”,”s”) 。
提示：
1 <= s.length <= 105 s 仅由小写英文字母组成
v1-贪心
思路
通过 set 记录字符，如果已经存在，则清空。
实现
public int partitionString(String s) {
Set<Character> set = new HashSet<>();
int count = 0;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(set.contains(c)) {
set.clear();
count++;
}
set.add(c);
}
// 需要多加一次
if(!set.isEmpty()) {
count++;
}
return count;
}
效果
51ms 击败 5.11%
v2-array 改进
思路
用 array 替代 set
实现
public int partitionString(String s) {
int[] set = new int[26];
int count = 1;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(set[c-'a'] > 0) {
// 清空
Arrays.fill(set, 0);
count++;
}
set[c-'a']++;
}
return count;
}
效果
12ms 击败 54.01%
