滴滴编程题两道AC

第一题,地下迷宫,直接dfs



第二题,leetcode原题,0的个数是有10决定的,10只能通过2和5产生,2的个数比5要充足,只需计算5的个数,需要注意25、125、...的个数,其中5会产生1个0,25会产生2个0,125会产生3个0

全部评论
今天的编程题挺简单的~ 如果过的不多的话估计悬了、
点赞 回复 分享
发布于 2016-09-18 17:27
走迷宫Java代码个人整理,供有需要的人参考。(可以求出所有路径和最优路径,以及最优路径下所耗的能量) import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Scanner; import java.util.Stack; class Pair{ public int x; public int y; public Pair(int x,int y) { this.x = x; this.y = y; } } public class Main { public static Stack<Pair> res = new Stack<>(); public static int[][] book;//用来标记改点是否走过,走过为1,没走为0 public static int[][] arr;//测试数组 public static int max = 0; public static Map<Integer, Stack<Pair>> map = new HashMap<>();//存放路径 public static void main(String ars[]) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int m = s.nextInt(); int P = s.nextInt(); arr = new int[n][m];// 初始化数组 book = new int[n][m];// 初始化数组 for (int i = 0; i < n; i++)// 循环输入 for (int j = 0; j < m; j++) arr[i][j] = s.nextInt(); Stack<Pair> path = new Stack<>(); dfs(path,0,0,P); if (map.size() == 0) { System.out.println("Can not escape!"); }else { System.out.println("可以找到最优路径如下所示:"); System.out.print("[0,0]"); Iterator<Pair> iter = map.get(max).iterator(); while (iter.hasNext()) { Pair pairTmp = iter.next(); System.out.print(",["+pairTmp.x+","+pairTmp.y+"]"); } System.out.println("\n最优路径所耗能量为:"+(P-max)); } } public static void dfs(Stack<Pair> path, int x, int y, int P) { int n = arr.length; int m = arr[0].length; int next[][] = { {0,1}, {1,0}, {0,-1}, {-1,0} };//定义四个方向(分别是向右、向下、向左、向右) if (P <= 0 && x != 0 && y != m-1) { return; } //找到符合条件的路径 if (x == 0 && y == m-1) { if (P>=0) { Stack<Pair> pathTmp = new Stack<>(); Iterator<Pair> iter = path.iterator(); while (iter.hasNext()) { pathTmp.add(iter.next()); } map.put(P, pathTmp); } if (max < P) {//判断是否为最优路径 max = P; } return; } int tx,ty; //枚举四种走法 for (int k = 0; k <= 3; k++) { tx = x+next[k][0]; ty = y+next[k][1]; //判断是否越界 if (tx < 0 || tx >= n || ty < 0 || ty >= m) { continue; } if (arr[tx][ty] == 1 && book[tx][ty] == 0) { if (k == 0 || k==2) {//如果是水平方向走 book[tx][ty] = 1; path.add(new Pair(tx, ty)); dfs(path, tx, ty, P-1); path.pop(); book[tx][ty] = 0; } if (k==1) {//如果是向下走 book[tx][ty] = 1; path.add(new Pair(tx, ty)); dfs(path, tx, ty, P); path.pop(); book[tx][ty] = 0; } if (k==3) {//如果是向上走 book[tx][ty] = 1; path.add(new Pair(tx, ty)); dfs(path, tx, ty, P-3); path.pop(); book[tx][ty] = 0; } } } } }
点赞 回复 分享
发布于 2016-09-19 11:31
我考虑最小体力消耗搞得程序很复杂只ac了一部分,估计有bug但是没时间调试。如果用dfs全部ac只能说测试用例有问题。
点赞 回复 分享
发布于 2016-09-19 11:29
地下迷宫那道,你不判断哪条路径消耗体力最小么?
点赞 回复 分享
发布于 2016-09-19 11:20
编程题AC是什么意思`````````
点赞 回复 分享
发布于 2016-09-18 18:42
第一题 ,x-1 的时候  p-3 , 向下不消耗, 你刚好搞反了?
点赞 回复 分享
发布于 2016-09-18 17:47
第一题怎么保证得到的是剩余体力最多的路径?
点赞 回复 分享
发布于 2016-09-18 17:41
不是要求消耗体力最少的路径吗?你代码里好像没体现最少啊?
点赞 回复 分享
发布于 2016-09-18 17:24
第一题 只过了 80% 晕了... 不知道怎么回事
点赞 回复 分享
发布于 2016-09-18 17:12
第一题我sb了 往上走一直搞成x+1了,只ac了30%
点赞 回复 分享
发布于 2016-09-18 17:12
恭喜恭喜
点赞 回复 分享
发布于 2016-09-18 17:11
叼啊
点赞 回复 分享
发布于 2016-09-18 17:10
大大大大大神啊!为什么这个运维也要写这样的题目啊
点赞 回复 分享
发布于 2016-09-18 17:07
太着急。wa了3发
点赞 回复 分享
发布于 2016-09-18 17:04

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务