一共3道编程题

第一题：足球赛得分

题目描述：

有一场双循环赛制（每个队都要主动和其他所有队打一次）的足球赛，胜、负、平分别得3、0、1分，现在给你一场球赛的比分表，需要你按照积分高低输出排名，积分相同的就按队伍名字排序。球队最多26个，球队名称范围为a-z。

输入输出样例：

Input: （计分板）
a-b 3:0
a-c 2:1
b-a 1:1
c-a 0:1
b-c 4:3
c-b 2:2
Output:
a 10,b 5,c 1

a总共赢3场、平1场，积3*3+1=10分，
b总共赢1场、平2场、负1场，积3+2*1+0=5分，
c总共赢0场、平1场、负3场，积1+0=1分，

解法：

这里处理输入是一个比较头疼的点，需要多次分割。解法没啥好说的，直接模拟就行。

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Main class
 *
 * @author Soarkey
 * @date 2021/3/31
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        // 用26长度先保存队伍
        Team[] team = new Team[26];
        while (in.hasNext()) {
            String[] line = in.nextLine().split(" ");
            // 队伍 a-b
            String[] t = line[0].split("-");
            // 得分 x:y
            String[] s = line[1].split(":");
            // String转为int
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            if (x > y) {
                // a队胜
                x = 3;
                y = 0;
            } else if (x == y) {
                // 平
                x = 1;
                y = 1;
            } else {
                // b队胜
                x = 0;
                y = 3;
            }
            // t[0].charAt(0) - 'a' 代表a队在数组中的下标
            char a = t[0].charAt(0);
            // t[1].charAt(0) - 'a' 代表b队在数组中的下标
            char b = t[1].charAt(0);

            team[a - 'a'] = team[a - 'a'] == null ? new Team(a, 0) : team[a - 'a'];
            team[a - 'a'].score += x;

            team[b - 'a'] = team[b - 'a'] == null ? new Team(b, 0) : team[b - 'a'];
            team[b - 'a'].score += y;
        }

        StringBuilder builder = new StringBuilder();
        // 按照得分和队名进行排序
        Arrays.sort(team, (a, b) -> {
            if (a == null || b == null) {
                return -1;
            }
            if (a.score != b.score) {
                return b.score - a.score;
            } else {
                return a.name - b.name;
            }
        });
        // 输出结果
        for (int i = 0; i < 26; ++i) {
            if (team[i] != null) {
                builder.append(team[i].name + " " + team[i].score + ",");
            }
        }
        builder.deleteCharAt(builder.length() - 1);
        out.println(builder);

        in.close();
        out.close();
    }

    /**
     * 队伍类
     */
    static class Team {
        // 队伍名称
        char name;
        // 累积得分
        int score;

        Team(char name, int score) {
            this.name = name;
            this.score = score;
        }
    }
}

第二题：猜帽子数量

题目描述：

一些员工玩游戏， 每个人都带了一顶有颜色的帽子，有一部分员工会反馈 帽子跟他颜色一样的人 有多少个，组成了一个数组。现在给你这个数组，让你猜出最少有多少个员工在玩这个游戏。

这道题目的题面挺难懂，得结合具体输入输出才能理解。

输入输出样例：

Input:
[1, 1, 2]
[1, 1, 2, 1, 1] // 这个是我自己加的
[0, 0, 0, 0] // 补充！
Output:
5
7
4

第一个输入的意思就是有3个人报了帽子数量，我们可以先假设为三个人的帽子颜色为a、b、c。
第一个人和第二个人都说还有1个人的帽子颜色跟他一样，如果他俩帽子颜色不同，那至少有4个人在玩游戏，而如果他俩帽子颜色一样的话，玩游戏的人最少就为2个，就是他们自己。
第三个人说还有2个人帽子颜色跟他一样，说明玩游戏的人当中有3个人帽子都是一样的颜色，显然不可能是第一个人和第二个人帽子的颜色，不然就矛盾了。
所以结果为2+3=5。

牛友可以自己算第二个试一试。

解法：

我用的是hashmap来根据相同颜色帽子数量来进行统计的，只过了50%，估计是漏了一些条件，有知道的同学欢迎评论区解惑。

补充：后续分析可能是因为漏掉了[0,0,0,0]这个测试用例，这个测试用例可能会导致元素没办法正常remove，因此修改了一下代码，可惜没有验证的机会了。

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * Main class
 * 只通过了50%
 * @author Soarkey
 * @date 2021/3/31
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        while (in.hasNext()) {
            String line = in.nextLine();
            line = line.substring(1, line.length() - 1).replace(" ", "");
            if (line.length() == 0) {
                out.println("0");
                continue;
            }

            String[] hatsStr = line.split(",");
            int[] hats = new int[hatsStr.length];
            for (int i = 0; i < hatsStr.length; ++i) {
                hats[i] = Integer.parseInt(hatsStr[i]);
            }
            Arrays.sort(hats);
            Map<Integer, Integer> map = new HashMap<>();

            int totalHat = 0;
            for (int hat : hats) {
                int t = hat + 1;
                if (map.containsKey(t)) {
                    if (map.get(t) - 1 == 0) {
                        map.remove(t);
                        totalHat += t;
                    } else {
                        map.put(t, map.get(t) - 1);
                    }
                } else {
                    // **************** 修改 ******************* //  
                    if(t == 1){
                        // cover有人报的帽子数量为0的情况
                        totalHat += 1;
                    } else {
                        map.put(t, t - 1);
                    }
                    // **************************************** //
                }
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                totalHat += entry.getKey();
            }
            out.println(totalHat);
        }

        in.close();
        out.close();
    }
}

第三题：游标匹配问题

题目描述：

给定一个字符串s和一个游标，游标指向起点start，另外给定一个字符串pattern，要求移动游标（可以向左向右循环移动，即如果移动到了边界可以跳到另一侧）来匹配字符串pattern，问匹配完成最少需要游标移动多少次。

输入输出样例：

Input:
aemoyn // 字符串s
amo // 待匹配的字符串pattern
0 // 游标起点start

// 下面的是我自己加的用例
aasasfsf
asf
2
Output:
3 // 只有一种情况，起点在0处，匹配到a,游标向右移动两次，匹配到m,继续向右移动一次匹配到o，完成

3 // 我自己加的用例输出

解法：

我用的dfs的思路，但是超时了，只过了70%，目测应该用dp来做，但是无奈没想到转移方程，放一下我的丑陋代码供各位同学参考吧~

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Main class
 * 超时 70%
 *
 * @author Soarkey
 * @date 2021/3/31
 */
public class Main {
    static int ans;

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        while (in.hasNext()) {
            String s = in.nextLine();
            String pattern = in.nextLine();
            // 转成字符数组能加快取第i位的速度，以空间换时间
            char[] sc = s.toCharArray();
            char[] pc = pattern.toCharArray();
            int start = in.nextInt();

            ans = Integer.MAX_VALUE;
            dfs(sc, pc, start, 0, 0);

            out.println(ans);
        }

        in.close();
        out.close();
    }

    /**
     * 匹配到第 k 位
     */
    public static void dfs(char[] sc, char[] pc, int start, int k, int step) {
        if (k == pc.length) {
            ans = Math.min(ans, step);
            return;
        }
        if (step >= ans) {
            return;
        }

        for (int j = 0; j < sc.length; j++) {
            if (pc[k] == sc[j]) {
                int t = Math.abs(j - start);
                dfs(sc, pc, j, k + 1,
                        step + Math.min(t, Math.abs(sc.length - t))
                );
            }
        }
    }
}