给定任务AABCB, 冷却时间k（相同任务之间的最短距离时间），任务顺序不能变，问完成任务的总时间。
例子：AABCB, k = 3, A _ _ A B C _ B, 时间为8.
解法：用hashtable保存上次的时间。
Followup1：如果k很小，怎么优化？ 解法：之前的hashtable的大小是unique task的大小，如果k很小，可以只维护k那么大的hashtable
给一个String, 如AABACCDCD, 插入''使同一个字母间隔为k: 如果k=3: A - - - A B - - A C - - - C D - - C D,
遍历, 与上次该字母的所在位置进行比较, 因此需要一个map不断保存每个字母最后出现的位置.
public String schedule(String str, int n) {
StringBuilder sb = new StringBuilder();
Map<Character, Integer> pos = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (!pos.containsKey(c)) {
sb.append(c);
} else {
while ((sb.length() - pos.get(c)) <= n) {
sb.append('_');
}
sb.append(c);
}
pos.put(c, sb.length() - 1);
}
return sb.toString();
}
时间复杂度O(N).
只需要返回长度.
public static int schedule2(String str, int n) {
int pos = 0;
Map<Character, Integer> locs = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (locs.containsKey(c) && pos - locs.get(c) <= n) {
pos += locs.get(c) + n - pos + 1;
}
locs.put(c, pos++);
}
return pos;
}