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

OnlyLing 发布于2019-08-22 18:41 / 2461人阅读

摘要：更多的小算法练习，可以查看我的文章。规则使用语言，使用函数读取，它将是一个字符串，指的是棋盘上点的位置。使用递归函数去解决，需要清楚判断的临界点，比如和时，只有一种选择。

虽然都是很简单的算法，每个都只需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

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

思路

个人思路：

8*8在本题中只做了数值的大小限制，无其他作用

把最小点（如（2 2））作为方格的最左下角，最大点（如（4 3））作为方格的右上角，构成一个3*2的方格，实质上就是求从方格最左下方到方格最右上方有多少条路径。

使用递归函数去解决，需要清楚判断的临界点，比如（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

云服务器 GPU云服务器 javascript算法题字符串算法题最难的算法题 java有趣算法题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96090.html

每日一道算法题 - LetterChanges(easy-4)

摘要：更多的小算法练习，可以查看我的文章。规则使用语言，使用函数获取传递的参数并使用以下算法对其进行修改。将字符串中的每个字母替换为字母表后面的字母即变为，变为。然后将这个新字符串，，，，中的每个元音大写，并最终返回此修改后的字符串。虽然都是很简单的算法，每个都只需5分钟左右，但写起来总会遇到不同的小问题，希望大家能跟我一起每天进步一点点。更多的小算法练习，可以查看我的文章。规则 Usi...

mo0n1andin 2019-08-22 18:36 评论0 收藏0
每日一道算法题 - 反转字符串(easy-3)

摘要：规则使用语言，让函数获取传递的参数，并以相反的顺序返回字符串。测试用例思路方法通过把字符串转换成数组，并使用数组的反转数组，然后使用重新拼接成字符串方法向后循环字符串或字符数组以生成新字符串虽然都是很简单的算法，每个都只需5分钟左右，但写起来总会遇到不同的小问题，希望大家能跟我一起每天进步一点点。更多的小算法练习，可以查看我的文章。规则 Using the JavaScript l...

xfee 2019-08-22 18:36 评论0 收藏0
每日一道算法题 - LongestWord(easy-1)

摘要：规则使用语言，让函数获取传递的参数并返回字符串中的最大单词。忽略字符串中标点符号并假设不会为空。测试用例思路通过过滤字符串，并把字符串根据空格符转换成字符串数组通过循环把获取字符串数组中的长度最长的字符串虽然都是很简单的算法，每个都只需5分钟左右，但写起来总会遇到不同的小问题，希望大家能跟我一起每天进步一点点。更多的小算法练习，可以查看我的文章。规则 Using the JavaS...

plokmju88 2019-08-22 18:35 评论0 收藏0
每日一道算法题

摘要：遇到的坑刚拿到这道题就直接做了这样的判断，可是万一是这个判断就是错误的了。思路二上述算法遍历了两次链表，还额外申请了一个数组空间，效率不高，不如直接就地反转链表，更改每个节点自身的指针。 2018.10.14 来源：剑指offer 题目：反转链表输入一个链表，反转链表后，输出新链表的表头。思路一：把所有链表内容都输入到一个数组，再次遍历链表，得到数组反转后的值，最后输出原来的head...

The question 2019-08-23 12:21 评论0 收藏0
每日一道算法题--二维数组中的查找--python

摘要：题目描述代码思路思路一按行执行二分查找，只要该行的第一个元素小于目标，就对该行二分查找。思路二从数组的左下角开始查找，如果当前值小于目标，就向右，即如果当前值大于目标，就向上，即。【题目描述】 showImg(https://user-gold-cdn.xitu.io/2019/5/22/16addf094e0320ca); 【代码思路】思路一：按行执行二分查找，只要该行的第一个元素小于目...

番茄西红柿 2019-05-23 16:08 评论0 收藏0