每日一道算法题 - KaprekarsConstant(hard-2)

2018-07-13 admin

虽然都是很简单的算法,每个都只需5分钟左右,但写起来总会遇到不同的小问题,希望大家能跟我一起每天进步一点点。 更多的小算法练习,可以查看我的文章。

规则

Using the JavaScript language, have the function ChessboardTraveling(str) read str which will be a string consisting of the location of a space on a standard 8x8 chess board with no pieces on the board along with another space on the chess board. The structure of str will be the following: “(x y)(a b)” where (x y) represents the position you are currently on with x and y ranging from 1 to 8 and (a b) represents some other space on the chess board with a and b also ranging from 1 to 8 where a > x and b > y. Your program should determine how many ways there are of traveling from (x y) on the board to (a b) moving only up and to the right. For example: if str is (1 1)(2 2) then your program should output 2 because there are only two possible ways to travel from space (1 1) on a chessboard to space (2 2) while making only moves up and to the right.

使用JavaScript语言,使用ChessboardTraveling(str)函数读取str ,它将是一个字符串,指的是8x8棋盘上点的位置。str的结构如下:“(x y)(a b)”,其中(x y)代表你当前所处的位置x和y的范围是1到8,而(a b)代表棋盘上的其他点的位置,a和b也在1到8的范围内,其中a> x和b> y。您的程序应该确定从( xy)在棋盘上移动到(a b)并且移动方式只能是向上和向右移动的情况下,一共有多少条路径。 例如:如果str是(1 1)(2 2)然后你的程序应该输出2,因为只有两种可能的方式从棋盘上的(1 1)点移动到棋盘上的(2 2)点。

function ChessboardTraveling(str) { 

  // code goes here  
  return str;    
} 

测试用例

Input:"(1 1)(3 3)"
Output:6

Input:"(1 1)(2 2)"
Output:2

Input:"(2 2)(4 3)"
Output:3

my code

function ChessboardTraveling(str) { 
  var strArr = str.match(/([0-9]+\s+[0-9]+)/g)
  var minArr = strArr[0].split(' ')
  var maxArr = strArr[1].split(' ')
  var xDiff = maxArr[0] - minArr[0]
  var yDiff = maxArr[1] - minArr[1]

  return Steps(xDiff, yDiff);    
}

function Steps(x, y) {
  if (x < 0 || y < 0)
    return 0;
  if (x == 0 && y == 1)
    return 1;
  if (x == 1 && y == 0)
    return 1;

  return Steps(x - 1, y) + Steps(x, y - 1)
}

console.log(ChessboardTraveling("(1 1)(3 3)"));

other code

暂时没找到其他合适的解决方式,如果你们有自己的解决方法,请留言~

思路

个人思路:

  1. 8*8在本题中只做了数值的大小限制,无其他作用
  2. 把最小点(如(2 2))作为方格的最左下角,最大点(如 (4 3))作为方格的右上角,构成一个3*2的方格,实质上就是求从方格最左下方到方格最右上方有多少条路径。
  3. 使用递归函数去解决,需要清楚判断的临界点,比如(x === 0 && y === 1)(x === 1 && y === 0)时,只有一种选择。

另一种思路: 使用组合计算 (1 1)和(3,3),需要往上走2步,往右走2步,一共要走4步,C(2,4)= 6 (2 2)和(4,3),需要往上走1步,往右走2步,一共要走3步,C(1,3)= 3

原文链接:https://segmentfault.com/a/1190000015619469

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-35880.html

文章标题:每日一道算法题 - KaprekarsConstant(hard-2)

相关文章
2014年最流行前端开发框架对比评测
如今,各种开发框架层出不穷,各有千秋。哪些是去年较受开发者关注的呢?前不久,云适配根据Github上的流行程度整理了2014年最受欢迎的6个前端开发框架,并进行对比说明,希望帮助有需要的朋友选择合适自己的前端框架。 1. Bootstrap...
2015-11-12
2015年3月国内浏览器市场份额概括,chrome占32.97
本报告数据,来源于百度统计所覆盖的超过150万的站点,而不是baidu.com的流量数据。 注:奇虎360浏览器份额在2010年10月至2011年3月,和2012年9月以来,两次大幅下降,是因为360浏览器去掉了原本的浏览器特征(User...
2015-11-12
CSS2.0帮助文档(参考手册)chm下载
下载地址:CSS2.0帮助文档(参考手册)chm下载 友情提示:如果打开空白,在手册上右键属性解除锁定即可。 ...
2015-11-12
canvas图片绘制跨域问题解决方案Tainted canvases may not be exported
图片跨域问题的一般解决方法 当使用canvas绘制网络图片的时候,经常会出现“Tainted canvases may not be exported”报错,上网搜一下解决方案,应该给的都是给img添加crossOrigin属性,尝试了一下...
2018-04-19
ASP.NET 2.0 AJAX应用程序设计
ASP.NET Aiax技术是一种实现异步(Asynchronous)网络应用的技术,它被整合在ASP.NET 2.0之中,是As P.NET的一种扩展技术。通过ASENETAjax技术,开发人员或程序员可以将Web服务器控件和客户端脚本结...
2015-11-14
HTML5游戏2015年的开发趋势
在互联网行业中,一个行业从零到成熟,开发者生态也是对应的,我们今年看到很多大公司,包括像微软和Google,也参与到了HTML5 开发者生态的建设当中。关于HTML5移动游戏的开发和盈利生态的走向又该去往何处?下面我们来试着讨论一下。 《围...
2015-11-12
2015 Web 2.0和AJAX如何做好优化
2015如何让做好web2.0和ajax的优化?JavaScript中文网总结当下提出以下四大优化意见,旨在帮助W前端开发人员有效利用APM解决上述问题。 随着Web应用程序速度与效率快速增长,网站已经成为企业与其客户进行交互的第一途径——...
2015-11-12
2015年将会有大量基于HTML5和JS的WEB应用
随着HTML5的定稿,以及JS的迅速发展,我们有理由相信,在接下来的一年里,将会涌现出大量的WEB应用,网站的表现形式将不再仅仅局限于过去的形式,必将在2015年引来一次重大改革! ...
2015-11-12
HTML5移动应用开发的12大特性
1.离线缓存为HTML5开发移动应用提供了基础 HTML5 Web Storage API可以看做是加强版的cookie,不受数据大小限制,有更好的弹性以及架构,可以将数据写入到本机的ROM中,还可以在关闭浏览器后再次打开时恢复数据,以减少...
2015-11-11
2015年2月国内操作系统市场份额概况,xp占46.29%,
规则调整:2012年6月1日开始,Mac操作系统中不再包含ipad、iphone市场份额。 ...
2015-11-12
回到顶部