网易雷火笔试算法题解
第一题,宝石题
用人话翻译题目
给长度为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); } }
网易 笔试 雷火 算法 开发
#网易##笔试#