java 查找max个可以参加课程的学员

mccptt67  于 2022-12-21  发布在  Java
关注(0)|答案(3)|浏览(101)

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

更新
我所实现的是,在所有员工天数首选项中计算所有天数,并选择具有最大计数的一天,然后检查该天是否存在于多少员工天数首选项中。

vpfxa7rd

vpfxa7rd1#

诀窍是找出两个不同的集合,使雇员人数最大化.
您的代码中的问题是,您只比较两个集合(天),这是最大雇员的首选。这就是为什么,在案例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;
    }

对于其他人谁不明白这一点,你可以用二维矩阵。

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

对所有组/天进行OR运算,并对所有OR结果求和。例如,在上例中,第8列和第9列将给予最大不同组,即7

vuktfyat

vuktfyat2#

我认为你在执行上的问题,是忽略了一个事实,就是在第一次点票后,出席人数第二多的一天,不一定是第二天。
例如,在E = ["01", "01", "2"]的情况下,乍一看,01似乎是所选日期的良好候选者。然而,由于01都是由相同的人选择的,因此选择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

因此,我认为你要计算第二热门的一天的出席人数,而不考虑已经入座的雇员的喜好。

0yycz8jy

0yycz8jy3#

public int solution(String[] e) {
        // Create a set to store the days that each employee is available
        Set<Integer>[] employeeAvailability = new Set[e.length];
        for (int i = 0; i < e.length; i++) {
            employeeAvailability[i] = new HashSet<>();
            for (int j = 0; j < e[i].length(); j++) {
                employeeAvailability[i].add(Character.getNumericValue(e[i].charAt(j)));
            }
        }

        // Check how many employees are available on each day
        int[] availabilityCount = new int[10];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < e.length; j++) {
                if (employeeAvailability[j].contains(i)) {
                    availabilityCount[i]++;
                }
            }
        }

        // Sort the availability count in descending order
        Arrays.sort(availabilityCount);

        // Return the maximum number of employees available on at least one of the two scheduled days
        return Math.max(availabilityCount[9], availabilityCount[8]);
    }

相关问题