2021-阿里巴巴编程题

一、完美对

有 n n个物品，每个物品有 k k个属性，第 i i件物品的第 j j个属性用一个正整数表示记为ai,ja**i,j，两个不同的物品 i,j i,j被称为是完美对的当且仅当ai,1+aj,1=ai,2+aj,2=⋯=ai,k+aj,ka**i,1+a**j,1=a**i,2+a**j,2=⋯=a**i,k+a**j,k，求完美对的个数。

输入例子：

5 3
2 11 21
19 10 1
20 11 1
6 15 24
18 27 36

输出例子：

3

思路：HashMap

import java.util.Scanner;
import java.util.HashMap;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            int[][] items = new int[a][b];

            for(int i = 0 ; i < a ; i++){
                for(int j = 0 ; j < b ; j++){
                    items[i][j] = in.nextInt();
                }
            }

            int res = 0;
            HashMap<String,Integer> map = new HashMap<String,Integer>();
            for(int i = 0 ; i < a ; i++){
                StringBuilder str_1 = new StringBuilder();
                StringBuilder str_2 = new StringBuilder();
                for(int j = 1 ; j < b ;j++){
                    int diff = items[i][j] - items[i][j-1];
                    str_1.append(String.valueOf(diff)).append(",");
                    str_2.append(String.valueOf(-diff)).append(",");
                }
                if(map.containsKey(str_2.toString())){
                    res += map.get(str_2.toString());
                    
                }
                map.put(str_1.toString(),map.getOrDefault(str_1.toString(),0)+1);
            }
            System.out.println(res);
        }
    }
}

蚂蚁笔试真题

一、小红的小踏前斩

有nn个怪物排成一排，每只怪物的血量为aia**i。
小红有一个技能：小踏前斩。效果是：选择一只怪物，对这只怪物造成1点伤害，并发出剑气，对下一个怪物造成2点伤害。（注：若下一个怪物已死亡，则剑气会打在尸体上，并不会向后穿透）。
小红可以对尸体发出踏前斩，剑气同样可以溅射到后面的怪物。但小红无法对第一个怪物前面的空气发出踏前斩用来溅射第一个怪物。
小红想至少击杀2只怪物，她想知道自己需要最少发出多少次小踏前斩？

输入例子：

2
2 6

输出例子：

3

例子说明：

对第一个怪物释放两次踏前斩，然后对它的尸体再放一次踏前斩。

思路：直接模拟

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();

            int[] monster = new int[a];
            for (int i = 0 ; i < a ; i++) {
                monster[i] = in.nextInt();
            }

            int left = 0, res = Integer.MAX_VALUE;
            for (int right = 1 ; right < a ; right++) {
                if (monster[left] * 2 >= monster[right]) {
                    if(right > 1){
                        res = Math.min(res, (monster[right]+1)/2+((monster[left]-(monster[right]+1)/2)+1)/2);
                    left++;
                    }else{
                        res = Math.min(res,monster[left]);
                    }
                }else{
                    res = Math.min(res,(monster[right]+1)/2);
                    left++;
                }
            }

            System.out.println(res);
        }
    }
}

二、小红的排列构造

小红希望你构造一个排列，满足对于排列中的每一项aia**i都满足：ai+ia**i+i均不是质数（下标ii从1开始）。你能帮帮她吗？

长度为nn的排列是指：一个长度为nn的数组，其中1到nn每个正整数恰好出现1次。例如[2,1,3]是排列，而[1,3,4,3]不是排列。

思路：特殊处理

直接对1、2两个数字特殊处理，放到最后两个位置。然后其他位置：奇数放奇数位，偶数放偶数位。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int[] res = new int[a];
            if(a <= 2 ){
                System.out.println(-1);
                return;
            }
            if( a % 2 == 0){
                res[a-1] = 2;
                res[a-2] = 1;
            }else{
                res[a-1] = 1;
                res[a-2] = 2;
            }
            for(int i = 0 ; i < a - 2 ; i++){
                res[i] = i+3;
            }
            for(int i = 0 ; i < a ; i++){
                System.out.println(res[i]);
            }
            
        }
    }
}