找到可以参加课程的max学生

Question

培训课程将在接下来的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;
    }

使现代化

我实现了什么，在所有员工的天偏好计数的所有天，并采取了一天有最大计数，然后检查这一天是目前有多少员工的天偏好。

Answer 1

我认为你实施的问题在于忽视了一个事实，即在第一次点名之后，出席人数第二多的那一天不一定是第二天。

例如，在E=[“01”、“01”、“2”]的情况下，乍一看，0和1似乎是所选日期的最佳候选者。然而，由于0和1都是由相同的人选择的，因此选择2作为所选日期之一实际上会使服务员的数量最大化：

E = ["01", "01", "2"]

Chosen days [0,1]          -> Total num of attendants is 2
Chosen days [0,2] or [1,2] -> Total num of attendants is 3

因此，我认为你必须计算第二个最受欢迎的一天的出席人数，而不考虑已经获得座位的员工的偏好。

Answer 2

诀窍是确定两个不同的集合，这可以最大限度地增加员工数量
代码中的问题是，您只比较了大多数员工喜欢的两组（天数）。这就是为什么在案例2中，您的代码只比较单个对（第8天和第9天），这是一个有6名员工的独特集，而最大独特集是通过比较第0天和第9天（即7名员工）得出的
因此，您应该在不使用max 2的情况下比较所有天数的所有集合（这将删除所有HashMap和max逻辑）
下面是代码，它可能没有经过优化，但可以工作

public int solution(String[] E) {
        int n = E.length;
        int max = 0;

        for(int i=0;i <10; i++)
            for(int j=i+1;j<10; j++) {
                //create all pairs of days one by one like 01, 02, 03, 04, 05..... 89
                String sb = i+""+j;
                int out = 0;                
                for (int k = 0; k < n; k++) {

                    String inp = E[k];
                        
                    if (inp.matches(".*[" + sb.toString() + "].*")) {
                        out++;
                    }

                }
                if(out>max) {
                    max=out;
                }
            }

        return max;
    }

对于其他不理解这一点的人，您可以使用2D矩阵来完成。

days    0   1   2   3   4   5   6   7   8   9
emp0    1   1   1   1   1   1   1   1   1   0
emp1    1   1   1   1   1   1   1   1   1   0
emp2    1   0   0   0   0   0   0   0   0   0
emp3    0   1   1   1   1   1   1   1   1   1
emp4    0   1   1   1   1   1   1   1   1   1
emp5    0   0   0   0   0   0   0   0   1   1
emp6    0   0   0   0   0   0   0   0   0   1

取所有集合/天的或，并取所有或结果的总和。e、 g.在上述示例中，第8列和第9列将给出最大不同集，即7