2131. 连接两字母单词得到的最长回文串
问题描述
给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
回文串 指的是从前往后和从后往前读一样的字符串。
示例
输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。
输入：words = ["ab","ty","yt","lc","cl","ab"]
输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。
输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。
解题思路
这是一道典型的贪心算法相关的题目。
我们可以用三个集合来统计单词：
集合X统计"lc"、"zt"这种互相之间没有倒序相等关系的单词；
集合Y统计和集合X有倒序相等关系的单词；
集合double统计与自己互为倒序相等的单词，例如“tt”、“yy”。
关于统计字符串长度：
假如集合Y有“lc”，集合X必定有“cl”，那么这对单词允许出现的次数为Math.min(countInX, countInY);
集合double中的单词只有被2整除的部分可以使用，另外，允许出现孤零零的一个叠词（我们姑且将与自己互为倒序相等的单词称为“叠词”），例如 ["cc","ll","cc"] => "ccllcc"。
代码示例（JAVA）
class Solution {
public int longestPalindrome(String[] words) {
// "lc"、"zt"且互相之间没有倒序相等关系的单词
Map<String, Integer> xMap = new HashMap<>();
// 与xMap中存在倒序相等关系的单词
Map<String, Integer> yMap = new HashMap<>();
// "gg"、"cc"这样的叠词
Map<String, Integer> doubleMap = new HashMap<>();
// 统计词出现的类型及情况
for (String word : words) {
if (word.charAt(0) == word.charAt(1)) {
doubleMap.put(word, doubleMap.get(word) == null ? 1 : doubleMap.get(word) + 1);
} else {
if (xMap.get(word) != null) {
xMap.put(word, xMap.get(word) + 1);
} else if (yMap.get(word) != null) {
yMap.put(word, yMap.get(word) + 1);
} else {
String reserve = new StringBuilder(word).reverse().toString();
if (xMap.get(reserve) != null) {
yMap.put(word, 1);
} else {
xMap.put(word, 1);
}
}
}
}
double ans = 0;
// 先统计“lc”、“cl”这种
for (String word : yMap.keySet()) {
int y = yMap.get(word);
int x = xMap.get(new StringBuilder(word).reverse().toString());
ans += Math.min(x, y);
}
// 统计“tt”这种，注意，这种是允许出现一次单个的“tt”的
boolean flag = false;
for (String word : doubleMap.keySet()) {
int k = doubleMap.get(word);
if (k % 2 == 1 && !flag) {
ans += 0.5;
flag = true;
}
ans += k / 2;
}
return (int) (ans * 4);
}
}
621. 任务调度器
问题描述
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
解题思路
-
模拟法暴力解题
首先，我们统计一下所有的任务类型及次数；
然后，遵循冷却时间短、剩余任务执行次数多的任务优先执行进行解题。 -
构造（这像极了一道奥数题...）
假设次数最多的任务它的任务次数为max，任务次数为max的任务类型有maxCount个；那么完成这些任务需要的时间为(max - 1) * (n + 1) + maxCount。
从图中可以发现，如果任务次数都和A一样，公式成立；如果任务次数都比A小，那么也不会影响A的执行。
但是上面的假设是在比较好的情况下，还有一种情况就是：
如果此时还有5个D，会发现行数超出了A最后的行数，但是我们可以将D补到前面的位置，前面的格子依次挪到下一个时间点，那么这种情况花费的时间就是task的个数。
因此，我们的结果应该为Math.max((max - 1) * (n + 1) + maxCount, tasks.length)。
代码示例（JAVA）
1. 模拟法暴力解题
class Solution {
public int leastInterval(char[] tasks, int n) {
List<Map<String, Object>> list = new ArrayList<>();
for (char c : tasks) {
int i = 0;
for (; i < list.size(); i++) {
Map<String, Object> map = list.get(i);
if ((char) map.get("type") == c) {
map.put("count", (int) map.get("count") + 1);
break;
}
}
if (i == list.size()) {
Map<String, Object> item = new HashMap<>();
item.put("type", c);
item.put("count", 1);
item.put("cd", 0);
list.add(item);
}
}
int ans = 0;
while (!list.isEmpty()) {
Map<String, Object> target = getTargetTask(list);
int remainCd = (int) target.get("cd");
ans += remainCd + 1;
target.put("count", (int) target.get("count") - 1);
target.put("cd", n);
if ((int) target.get("count") == 0) {
list.remove(target);
}
// 群体减cd
for (Map<String, Object> item : list) {
if ((int) item.get("cd") > 0 && (target == null || (char) target.get("type") != (char) item.get("type"))) {
item.put("cd", (int) item.get("cd") - remainCd - 1);
}
}
}
return ans;
}
public Map<String, Object> getTargetTask(List<Map<String, Object>> list) {
Map<String, Object> target = null;
Integer minCd = Integer.MAX_VALUE;
Integer count = -1;
for (int i = 0; i < list.size(); i++) {
Map<String, Object> item = list.get(i);
if ((int) item.get("cd") > minCd) {
continue;
} else if ((int) item.get("cd") == minCd) {
if ((int) item.get("count") > count) {
target = item;
count = (int) target.get("count");
}
} else {
target = item;
minCd = (int) target.get("cd");
count = (int) target.get("count");
}
}
return target;
}
}
2. 构造
class Solution {
public static int leastInterval(char[] tasks, int n) {
int max = 0;
int maxCount = 0;
int[] arr = new int[26];
for (char task : tasks) {
arr[task - 'A'] = arr[task - 'A'] + 1;
}
for (int i = 0; i < 26; i++) {
if (arr[i] > max) {
max = arr[i];
maxCount = 1;
} else if (arr[i] == max) {
maxCount++;
}
}
return Math.max((max - 1) * (n + 1) + maxCount, tasks.length);
}
}
网友评论