网易雷火笔试算法题解

第一题,宝石题

用人话翻译题目

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

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

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

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

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

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

最小时是,23, 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);
    }
}

可跳转阅读原文

网易 笔试 雷火 算法 开发

#网易##笔试#
全部评论
第一题相邻俩元素求和,得到n-1的数组,然后最大的k-1个数-最小的k-1个数就是答案。不需要那么麻烦。 比如[2,3,5,4],相邻相加得到[5,8,9]。k=2时就是最大的1个数-最小的一个数=9-5=4。k=3时就是(9+8)-(5+8)=4
3 回复 分享
发布于 2023-04-22 16:29 天津
老哥,能找到原题不,想自己试着做一下
1 回复 分享
发布于 2023-04-25 09:27 湖北

相关推荐

百度oc啦,结束秋招!
坚定的度孝子:看他别的帖子,值得怀疑一下
点赞 评论 收藏
分享
Atica:笑死了我也收到这个,第一时间还以为是婉拒我,然后一看他把卖课名片推过来大彻大悟
点赞 评论 收藏
分享
2 14 评论
分享
牛客网
牛客企业服务