企业营销的网站,西安工装装修公司排名,石家庄网络推广,网站建设-好发信息网2018-09-24 14:19:58 问题描述#xff1a; 问题求解#xff1a; 初看到这个问题#xff0c;直觉上认为可以通过BFS遍历解空间进行求解#xff0c;因为本质上来说#xff0c;这个问题和棋盘上移动马的问题是一类问题#xff0c;都是可以转化成图的问题#xff0c;但是MLE…2018-09-24 14:19:58 问题描述 问题求解 初看到这个问题直觉上认为可以通过BFS遍历解空间进行求解因为本质上来说这个问题和棋盘上移动马的问题是一类问题都是可以转化成图的问题但是MLE了问题出在在本问题中是不能使用used来保存已经扩展过的节点的因为相同的节点在不同的阶段的移动步数是不一样的因此都需要进行入队列的操作。 当然看到数据规模就应该有意识这个问题是不能使用暴力搜索来求解的。 事实上这个问题是一个数学问题求解方案是 1首先负数和其相反数的步数是相同的因此只需要考虑正数的个数 2对于一个正数我们最先需要做的就是通过最短的步骤到达或将将超过这个target 3如果正好达到target或者diff为一个偶数那么我们可以直接返回step因为如果diff为偶数可以将前面的改变成-实现和为target 4问题就是如果diff为奇数那么就需要继续往后加直到diff为偶数 public int reachNumber(int target) {target Math.abs(target);int sum 0;int step 0;while (sum target) {step;sum step;}while ((sum - target) % 2 ! 0) {step;sum step;}return step;}转载于:https://www.cnblogs.com/TIMHY/p/9695448.html
