8月26日阿里笔试

前言

阿里2020年08月26日上午9点-10点的笔试题，一共两题。

第一题

给定两个等长且一定是小写的字符串，记做A和B，求出在A和B之间的所有字符串。

比如给定了aab和aad，那么就输出1，因为它们之间只有aac一个符合要求。

题目还特意说了30%的数据，字符串长度小于等于3。我看到这里就以为是需要把所有的组合都求出来，然后进行判断，因为如果你要把所有的组合都求出来，那么由于每个位置有26种可能性，所以时间复杂度是O(26ⁿ)，这显然是很差的。

然后我就花了半个小时去把所有的组合都求了出来，然后在草稿纸上写了一下发现，这TM不就是相当于是26进制的转换吗？我只需要把两个字符串都转成对应的数字，然后减一下不就好了吗？下面是把对应的小写字符串转成26进制的Long整数。

private static long stringToInt(String s) {
    char[] chars = s.toCharArray();
    long sum = 0;
    long basic = 1;
    for (int i = chars.length - 1; i >= 0; i--) {
        sum = sum + (chars[i] - 'a' + 1) * basic;
        basic = basic * 26;
    }
    return sum;
}

然后就非常简单了…..可惜我卡的时间有点久。

第二题

本题和杭电的4415几乎一模一样，除了最后的输出杭电要在每个case之前加个标号。

给定一把武器，这把武器只有一个耐久度。然后给定N个怪兽的信息，每个怪兽有需要砍死它的耐久值和它会掉落的武器。每个怪兽掉落的武器一定能够杀死一个怪物，但是怪兽可能不会掉武器。求出最后你能够杀死的怪物数量和你的初始宝剑剩下的耐久值的最大值。

错误解法1

我的思路很简单，就是先对所有怪物的耐久值，从小到大排序（如果相同就按照掉落的宝剑从大到小排序），然后从第一只怪兽开始判断，如果它掉落的宝剑是0，那就跳过，直到找到第一只怪物掉落的宝剑不是0，杀了它。

然后把那只杀掉的怪兽从list中去除，并且重新按照掉落的宝剑数量从大到小排序（如果宝剑数量相同，那么你爱怎么排就怎么排），然后从掉落宝剑最多的开始杀，看看能不能杀到最后。

下面的代码是按照我上面的思路来写的，但是并不符合题意！

// 注意！下面的思路是错误的。
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int turn = 0;
        for (int count = 0; count < T; count++) {
            turn++;
            int monsterCount = in.nextInt();
            int naijiu = in.nextInt();
            List<Monster> monsters = new ArrayList<>();
            for (int j = 0; j < monsterCount; j++) {
                Monster monster = new Monster(in.nextInt(), in.nextInt());
                monsters.add(monster);
            }

            // 排序
            Collections.sort(monsters, (m1, m2) -> {
                if (m1.requireNaijiu == m2.requireNaijiu) {
                    return m2.weaponCount - m1.weaponCount;
                }
                return m1.requireNaijiu - m2.requireNaijiu;
            });

            int remainNaijiu = naijiu;
            int weaponCount = 1;
            // 首先找到第一只可以杀的怪兽杀了它
            Monster initMonster = null;
            boolean canFindFirst = false;
            for (Monster m : monsters) {
                if (m.requireNaijiu <= naijiu && m.weaponCount > 0) {
                    remainNaijiu = naijiu - m.requireNaijiu;
                    canFindFirst = true;
                    initMonster = m;
                    weaponCount = m.weaponCount;
                    break;
                }
            }
            if (canFindFirst) {
                // 把第一只移除
                monsters.remove(initMonster);

                int killedMonster = 1;

                // 把剩下的怪兽按照掉落的武器数量从大到小排序
                Collections.sort(monsters, (m1, m2) -> {
                    return m2.weaponCount - m1.weaponCount;
                });

                boolean canKillAll = true;
                for (Monster m : monsters) {
                    if (weaponCount == 0) {
                        // 杀不掉目前这只怪兽了
                        canKillAll = false;
                        break;
                    }
                    // 用掉一把武器
                    weaponCount--;
                    // 杀死一个怪物
                    killedMonster++;
                    // 得到死去的怪物的武器
                    weaponCount += m.weaponCount;
                }
                if (canKillAll) {
                    // 可以杀死所有的，那就输出
                    System.out.println("Case " + turn + ": " + killedMonster + " " + (naijiu - remainNaijiu));
                } else {
                    // 并不能杀死所有的
                    System.out.println("Case " + turn + ": " + killedMonster + " " + (naijiu - remainNaijiu));
                }

            } else {
                // 连一只都杀不掉
                System.out.println("Case " + turn + ": 0 0");
            }
        }
        in.close();
    }

    static class Monster {
        public int requireNaijiu;
        public int weaponCount;

        public Monster(int requireNaijiu, int weaponCount) {
            this.requireNaijiu = requireNaijiu;
            this.weaponCount = weaponCount;
        }

        @Override
        public String toString() {
            return "Monster{" +
                    "requireNaijiu=" + requireNaijiu +
                    ", weaponCount=" + weaponCount +
                    '}';
        }
    }
}

错误解法2

emmm 这题做的时候，我以为杀死所有的怪才应该输出，如果有一只杀不死就应该输出0 0，但是其实就算杀不死也应该把已经杀死的输出。

但是我说了，上面的代码还是不符合题意的。为什么？因为忽略了一点，假设我们所有的怪物都不掉落剑，那么你使用初始的宝剑，还是可以杀掉几只怪的，而我上面的代码显然就是错的了。

所以真正的贪心应该是，先用最少的耐久来杀掉一只带着武器的怪，获取到它掉落的武器，然后用掉落的武器把所有拥有武器的怪都杀死。然后再把这些怪物的武器都用完。用完之后，如果还有怪物残留，那么应该用你宝剑剩下的耐久接着去砍！这样才是正确的思路。

正确个鸡儿！上面的意思是把怪物分成了两组，一组是带武器的，一组是不带武器的。那么在我们有武器的时候，我们应该首先去砍掉会掉落武器，且需要消耗最大耐久度的怪。然后才是去砍掉落武器的，最后才是去用初始带的耐久度去砍。

正确解

其实我一开始的错误解法1的前半部分是对的，我只需要考虑用耐久怎么杀就行了（那当然是先杀掉消耗最少耐久的），而不要去考虑怪物掉落的武器怎么杀，因为怪物掉落的武器总能杀掉对应数量的怪物。

所以代码是这样的：

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int turn = 0;
        for (int count = 0; count < T; count++) {
            int cost = 0;
            turn++;
            int n = in.nextInt();
            int m = in.nextInt();
            List<Monster> monsters = new ArrayList<>();
            int killedMonster = 0;
            for (int j = 0; j < n; j++) {
                Monster monster = new Monster(in.nextInt(), in.nextInt());
                monsters.add(monster);
            }

            // 按照耐久从小到大排序
            Collections.sort(monsters, (m1, m2) -> {
                return m1.requireNaijiu - m2.requireNaijiu;
            });

            int firstIndex = 0;
            // 首先找到第一个有武器的，并且记录下它的下标
            for (int i = 0; i < monsters.size(); i++) {
                if (monsters.get(i).weaponCount > 0) {
                    firstIndex = i;
                    break;
                }
            }

            if (monsters.get(firstIndex).requireNaijiu <= m) {
                cost += monsters.get(firstIndex).requireNaijiu;
                killedMonster++;
                for (int i = 0; i < n; i++) {
                    // 如果能够进到循环中，那么所有的剑必然可以获取到
                    killedMonster += monsters.get(i).weaponCount;
                }
            }

            // 按照顺序从头开始杀
            for (int i = 0; monsters.get(i).requireNaijiu + cost <= m; i++) {
                if (i != firstIndex) {
                    cost += monsters.get(i).requireNaijiu;
                    killedMonster++;
                }
            }
            if (killedMonster >= n) {
                killedMonster = n;
            }
            System.out.println("Case " + turn + ": " + killedMonster + " " + cost);

        }
        in.close();
    }

    static class Monster {
        public int requireNaijiu;
        public int weaponCount;

        public Monster(int requireNaijiu, int weaponCount) {
            this.requireNaijiu = requireNaijiu;
            this.weaponCount = weaponCount;
        }

        @Override
        public String toString() {
            return "Monster{" +
                    "requireNaijiu=" + requireNaijiu +
                    ", weaponCount=" + weaponCount +
                    '}';
        }
    }
}

上面的代码只需要对所有的怪物按照它们需求耐久度从小到大排序。

首先第一步，找到一个能被初始耐久度杀掉，且会掉落物品的怪物，有了它，我们就可以得到所有的会掉落物品的怪物了。

接下来，我们从头开始，只要这个怪物不是第一步被剑杀的，我们就用剑的耐久度去杀。不用担心会杀两次之类的，因为我们要求的是最大杀怪数，而不是要求杀的是哪一只。