培训期次将在接下来的10天内进行两次。有N名员工(编号从0到N-1)愿意参加培训。每位员工都提供了他们能够参加培训的接下来10天的列表。员工首选项表示为字符串数组。N[K]是由数字(0-9)组成的字符串,表示第k名员工能够参加培训的天数。
需要找出至少在两个计划日期中的一天可以参加的员工的最大数量。
例如
Given E = ["039", "4", "14", "32", "", "34", "7"], the answer is 5. It can be achieved for example by running training on days 3 and 4. This way employees number 0, 1, 2, 3 and 5 will attend the training.
Given E = ["801234567", "180234567", "0", "189234567", "891234567", "98", "9"], the answer is 7. It can be achieved for example by running training on days 0 and 9. This way employees all will attend the training.
Given E = ["5421", "245", "1452", "0345", "53", "345"], the answer is 6. It can be achieved for example by running training once on day 5. This way employees all will attend the training.
这是我的测试,我没有解决。
我试过这个方法,但它只适用于1,2的情况。有人能分享解决它的技巧吗?
public int solution(String[] E) {
Map<String, Integer> daysCount = new HashMap<String, Integer>();
int n = E.length;
for (int i = 0; i < n; i++) {
String inp = E[i];
for (int j = 0; j < inp.length(); j++) {
char c = inp.charAt(j);
if (daysCount.containsKey(Character.toString(c))) {
daysCount.merge(Character.toString(c), 1, Integer::sum);
}
else {
daysCount.put(Character.toString(c), 1);
}
}
}
Map<String, Integer> topTen = daysCount.entrySet().stream()
.sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())).limit(2)
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
List<String> vals = new ArrayList<String>();
topTen.entrySet().forEach(entry -> {
vals.add(entry.getKey());
});
int out = 0;
StringBuilder sb = new StringBuilder();
for (int z = 0; z < vals.size(); z++) {
sb.append(vals.get(z));
}
for (int i = 0; i < n; i++) {
String inp = E[i];
if (inp.matches(".*[" + sb.toString() + "].*")) {
out++;
}
}
return out;
}
更新
我所实现的是,在所有员工天数首选项中计算所有天数,并选择具有最大计数的一天,然后检查该天是否存在于多少员工天数首选项中。
3条答案
按热度按时间vpfxa7rd1#
诀窍是找出两个不同的集合,使雇员人数最大化.
您的代码中的问题是,您只比较两个集合(天),这是最大雇员的首选。这就是为什么,在案例2中,您的代码只比较一对(第8天和第9天),这是给出具有6名雇员的非重复集合,而最大非重复集合是通过比较第0天和第9天,即7名雇员给出的。
因此,您应该比较所有日期的所有集合,而不取max 2(这将删除所有HashMap和max逻辑)。
下面是代码,可能没有经过优化,但可以正常工作
对于其他人谁不明白这一点,你可以用二维矩阵。
对所有组/天进行OR运算,并对所有OR结果求和。例如,在上例中,第8列和第9列将给予最大不同组,即7
vuktfyat2#
我认为你在执行上的问题,是忽略了一个事实,就是在第一次点票后,出席人数第二多的一天,不一定是第二天。
例如,在
E = ["01", "01", "2"]
的情况下,乍一看,0
和1
似乎是所选日期的良好候选者。然而,由于0
和1
都是由相同的人选择的,因此选择2
作为所选日期之一实际上会使参与者的数量最大化:因此,我认为你要计算第二热门的一天的出席人数,而不考虑已经入座的雇员的喜好。
0yycz8jy3#