2020春招-阿里笔试-编程题2道

阿里笔试编程题

Posted by weber on April 8, 2020

公司:阿里

岗位:算法工程师-机器学习(实习生)

笔试:在线笔试(牛课网)

题型:2编程

题1 功夫特训

小强开始了他的功夫特训。共有m个木头人,进攻时间为n秒,每个木头人的血量为a,每次攻击会让木头人的血量-1;小强的攻击范围为b,即每次可以同时攻击b个木头人。问最多消灭多少个木头人?

第一行输入一个整数T,表示接下来有T组样例。接下来输入 n,m,a,b

输入示例:

1

5 5 2 2

输出示例:

5

解释:

(2,2,2,2,2) -> (1,1,2,2,2)->(1,0,1,2,2)->(0,0,0,2,2)->(0,0,0,1,1)->(0,0,0,0,0)

思路:

如果攻击范围 b > m,令 b = m;

分情况讨论:如果 n < a,结果为 0;如果 n >= a,结果为 (n*b)//a 和 m 的最小值。

public int calMoodMan(int n, int m, int a, int b){
	if(b>m) b=m;
  if(n<a) return 0;
  else return Math.min((n*b)/a,m);
}

题2 方阵最大路径

有一个 N x N 的方阵,从左上角出发,每次可以移动不超过 k 步。每次可以移动的方向为上下左右,每个格子上都有值,如果要进入的方格的值不超过当前方格的值,则不能移动。每次移动的值累加,求最大累加值。

第一行输入一个整数T,表示接下来有T组样例。接下来输入 n, k ,再接着输入 n x n 的方阵

1<=n<=100

输入示例:

1

3 1

1 2 5 10 11 6 12 12 7

输出示例:

37

解释:

1->2->5->6->11->12 = 37

思路:

DP之记忆化搜素。用一个二维 dp 数组表示从 i,j 开始走能获得的最大路径,状态转移方程为:

知识点回顾:算法导论学习-动态规划之记忆化搜索

import java.util.*;

public class QuestionTwo {

    static int[][] dp = new int[100][100];
    static int[][] A = new int[100][100];
    static int N;
    static int K;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        for (int t = 0; t < T; t++) {
            N = scan.nextInt();
            K = scan.nextInt();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    A[i][j] = scan.nextInt();
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dp[i][j] = 0;
                }
            }
            System.out.println(dfs(0, 0));
        }
    }

    private static int dfs(int i, int j) {
        if (dp[i][j] > 0) return dp[i][j];
        int temp = 0;
        for (int k = 1; k <= K; k++) {
            if (i + k < N && A[i + k][j] > A[i][j]) temp = Math.max(temp, dfs(i + k, j));
            if (j + k < N && A[i][j + k] > A[i][j]) temp = Math.max(temp, dfs(i, j + k));
            if (i - k >= 0 && A[i - k][j] > A[i][j]) temp = Math.max(temp, dfs(i - k, j));
            if (j - k >= 0 && A[i][j - k] > A[i][j]) temp = Math.max(temp, dfs(i, j - k));
        }
        dp[i][j] = A[i][j] + temp;
        return dp[i][j];
    }
}

总结

两道题考察的知识点:

数学,动态规划(记忆化搜索)