网易雷火笔试算法题解

第一题，宝石题

用人话翻译题目

给长度为n的数组，和一个k

请将数组分为k段，每个元素都要属于一个段，且只能属于一个段

每个段的价值为，最左边的元素值+最右边的元素值

返回所有分段方法中最大的价值减去最小价值的结果。

如：[2, 3, 5, 4] k = 2

可以分为两段，最大时是，2, 3, 5 和 4 价值为2 + 5 + 4 + 4 = 15

最小时是，2, 3, 5, 4价值为2 + 2 + 3 + 4 = 11

所以返回答案为15 - 11 = 4

用动态规划解

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param price int整型一维数组 宝石价格列表
     * @param k     int整型 行囊个数
     * @return int整型
     */
    public int putGems(int[] price, int k) {
        // write code here
        //dp[i][j] 表示前i个装j个包
        int[][] dp2 = new int[price.length][k];
        for (int i = 0; i < price.length; i++) {
            for (int j = 0; j < k; j++) {
                dp2[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < price.length; i++) {
            dp2[i][0] = price[0] + price[i];
        }
        int[][] dp = new int[price.length][k];
        for (int i = 0; i < price.length; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 0; i < price.length; i++) {
            dp[i][0] = price[0] + price[i];
        }
        for (int i = 1; i < k; i++) {
            for (int j = i; j < price.length; j++) {
                //更新dp[i][j] 表示前i个装j个包
                //由前i - 1 装 j - 1  和 i 装1
                // 前i - 2 装j - 1 和  i-1  i装1
                for (int l = i - 1; l < j; l++) {
                    dp[j][i] = Math.max(dp[j][i], dp[l][i - 1] + price[l + 1] + price[j]);
                    dp2[j][i] = Math.min(dp2[j][i], dp2[l][i - 1] + price[l + 1] + price[j]);
                }
            }
        }
        return dp[dp2.length - 1][k - 1] - dp2[dp2.length - 1][k - 1];
    }
}

第二题，永劫无间相遇问题

题目，给一个由0和1构成的二维数组，如果是1表示这个位置可以走，如果是0就不能走。

给a_x, a_y表示a的位置，b_x, b_y表示b的位置

请返回a和b相遇，最少需要多少步，如果不能相遇返回-1

经典的dfs

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param map int整型二维数组 代表地图的二维数组
     * @param a_x int整型 小 A 出生点的 x 坐标
     * @param a_y int整型 小 A 出生点的 y 坐标
     * @param b_x int整型 小 B 出生点的 x 坐标
     * @param b_y int整型 小 B 出生点的 y 坐标
     * @return int整型
     */
    int res;

    public int getEstTime(int[][] map, int a_x, int a_y, int b_x, int b_y) {
        // write code here
        int[][] vis = new int[map.length][map[0].length];
        res = map.length + map[0].length + 2;
        dfs(map, vis, a_x, a_y, b_x, b_y, 0);
        if(res == map.length + map[0].length + 2) {
            return -1;
        }
        return (res + 1) / 2;
    }

    private void dfs(int[][] map, int[][] vis, int x, int y, int b_x, int b_y, int had) {
        if (x < 0 || y < 0 || x >= map.length || y >= map[0].length) {
            return;
        }
        if (vis[x][y] == 1 || map[x][y] == 0) {
            return;
        }
        if (x == b_x && y == b_y) {
            res = Math.min(had, res);
            return;
        }
        vis[x][y] = 1;
        dfs(map, vis, x + 1, y, b_x, b_y, had + 1);
        dfs(map, vis, x, y + 1, b_x, b_y, had + 1);
        dfs(map, vis, x - 1, y, b_x, b_y, had + 1);
        dfs(map, vis, x, y - 1, b_x, b_y, had + 1);
    }
}

可跳转阅读原文

网易笔试雷火算法开发

#网易##笔试#