如何创建更优化的解决方案

Question

因此,我的老师通常会在一些在线工具上为我们分配问题,例如hackerrank for practice.目前有一个特定问题阻碍了我,问题如下.

一所学校正在举办一场比赛,以测试学生的知识.成立了一个由五名学生组成的团队,每个学生都熟练掌握学校提供的五个科目之一.在学校教授的科目是物理(p),化学(c),数学(m),植物学(b),动物学(z).每个团队可以有五个学生,一个学生不能在两个团队中,每个团队每个科目只有一个人.所以团队中不可能有两个擅长物理学的人.

我的任务是,给出一个字符串,该字符串与纯粹由某个科目中的技能确定的学生列表有关,确定可以形成多少个团队.

例如,

pcmpcmbbbzz将返回2 pcmpp将返回0

static int differentTeams(String skills) {
    char [] c1 = skills.toCharArray();
    //number of students that can be on a team
    int max = 5;
    //create set of characters for any team instance which can be max of 5
    Set<Character> teamSet = new HashSet<Character>();
    //create set of used characters or indexs in this string
    Set<Integer> insertedSet = new HashSet<Integer>();
    int i = 0;
    int numberOfTeams = 0;
    //iterate through the array of chars
    while(i < c1.length){
        if(teamSet.contains(c1[i]) || insertedSet.contains(i)){
            //if the specific character or study type has been added to the team or it has been used 
            //skip over it and proceed to the next thing
            i++;
            continue;
        }
        //if none of these if blocks execute that means it can be added to the team.
        //also need to keep track of the fact that it was inserted because a student can only be
        //on one team
        teamSet.add(c1[i]);
        insertedSet.add(i);
        i++;

    if(teamSet.size() % max == 0 && teamSet.size() > 0){
            //signals that a complete team of five people have been created
            //empty the set
            teamSet.clear();
            //increment the number of teams
            numberOfTeams++;
            //reset i
            i = 0;
        }
    }
    return numberOfTeams;
}

这就是我到目前为止,我的思考过程可以在评论中看到.但是,对于某些测试用例,它超时意味着需要比给定时间更长的时间才能找到解决方案.显然,我的解决方案是天真的,或者甚至可能是暴力强迫有任何方式我可以优化我已经拥有的东西,因为我很遗憾.

Answer 1

试试这个.我们的想法是为五个科目创建一个计数数组.一旦创建了这个数组,你所要做的就是迭代字符串,找到所需的字符(p,c,m,b,z -> 0,1,2,3,4)并增加计数.由于您需要最少的团队,您需要在五个值中找到最小值.这为您提供了最少的团队数量.

static int differentTeams(String skills) {
    int numberOfTeams = Integer.MAX_VALUE;
    // Assign an array count of people in 5 Subjects
    int[] countArr = new int[5];
    for(int i=0;i<skills.length;i++){
       char subject = skills.charAt(i);
       if(subject=='p'){
            countArr[0]++;
       }else if(subject=='c'){
            countArr[1]++;
       }else if(subject=='m'){
            countArr[2]++;
       }else if(subject=='b'){
            countArr[3]++;
       }else if (subject=='z'){
            countArr[4]++;
       }else{ 
            throw new IllegalArgumentException("Invalid Input: " + subject); 
       }

    }
    // Iterate count array to find the Minimum Value
    for(int i=0;i<5;i++){
       if(countArr[i]<numberOfTeams){
          numberOfTeams = countArr[i];
       }
    }
    return numberOfTeams;
}