数据结构与算法（回溯法） --javascript语言描述

Bamboy 发布于2019-08-26 11:45 / 2851人阅读

摘要：思路这是一个可以用回朔法解决的典型题。由于回朔法的递归特性，路径可以被开成一个栈。机器人的运动范围地上有一个行和列的方格。当它准备进入坐标为的格子时，通过检查坐标的数位和来判断机器人是否能够进入。

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

思路：

这是一个可以用回朔法解决的典型题。

1.首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。

2.由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。

3.由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符

4.如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。

5.一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置。

function hasPath(matrix, rows, cols, str) {
  let visited = [];
  for (let i = 0; i < rows * cols; i++) {
    visited[i] = false;
  }
  let pathLen = 0;
  for (let i = 0; i < rows; i++) {    
    for (let j = 0; j < cols; j++) {      
      if (hasPathCore(matrix,rows,cols,i,j,str,pathLen,visited)) {        
        return true;        
      }      
    }  
  }
  return false;
}

function hasPathCore(matrix,rows,cols,i,j,str,pathLen,visited) {
  if(str.length === pathLen) {
    return true;
  }
  let hasPath = false;
  if(i>=0 && i=0 && j
机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路：
和前面的题目类似，这个方格也可以看出一个m*n的矩阵。同样在这个矩阵中，除边界上的格子之外其他格子都有四个相邻的格子。
机器人从坐标(0,0)开始移动。当它准备进入坐标为(i,j)的格子时，通过检查坐标的数位和来判断机器人是否能够进入。如果机器人能够进入坐标为(i,j)的格子，我们接着再判断它能否进入四个相邻的格子(i,j-1)、(i-1,j),(i,j+1)和(i+1,j)。
function movingCount(threshold, rows, cols)
{
  let visited = [];
  for(let i = 0; i < rows * cols; i++) {
    visited[i] = false;
  }
  let count = movingCountCore(threshold,rows,cols,0,0,visited);
  return count;
}

function movingCountCore(threshold,rows,cols,i,j,visited) {
  let count = 0;
  if(check(threshold,rows,cols,i,j,visited)) {
    visited[i*cols+j] = true;
    count = 1 + movingCountCore(threshold,rows,cols,i,j-1,visited)
              + movingCountCore(threshold,rows,cols,i,j+1,visited)
              + movingCountCore(threshold,rows,cols,i-1,j,visited)
              + movingCountCore(threshold,rows,cols,i+1,j,visited);
  }
  return count;
}

//check函数用来判断机器人能否进入坐标为(i,j)的方格
function check(threshold,rows,cols,i,j,visited) {
  if(i>=0 && i=0 && j0) {
    sum += number%10;
    number = Math.floor(number/10);
  }
  return sum;
}

console.log(movingCount(18,5,5));

GPU服务器云服务器回溯法最优化算法与方法的共轭梯度法字典法破解密码算法最大简约法的算法

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

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

回溯算法讲解--适用于leetcode绝大多数回溯题目

摘要：什么是回溯算法回溯法是一种系统搜索问题解空间的方法。解空间定义为与数字长度相同。最后，为什么要掌握回溯法因为懂了回溯法之后笔试里的很多题就算不了，起码成功运行到之间是没问题的。什么是回溯算法？回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。而往往所谓的dfs，bfs都是在图或者树这种数据...

saucxs 2019-08-16 15:23 评论0 收藏0
回溯算法

摘要：回溯算法主要思想回溯算法的基本思想是从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯算法说白了就是穷举法。回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。用回溯算法解决问题的一般步骤为定义一个解空间，它包含问题的解。回溯算法主要思想回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇...

ctriptech 2019-08-16 10:33 评论0 收藏0
算法思想

摘要：基础算法思想类别递推枚举递归分治贪婪回溯试探模拟递推递推分类顺推法从已知条件出发，逐步推算出要解决问题的方法。贪心算法的局限不能保证最后的解是最优的不能求最大最小解问题只能求满足某些约束条件的可行解范围。基础算法思想类别递推枚举递归分治贪婪回溯（试探）模拟递推递推分类顺推法：从已知条件出发，逐步推算出要解决问题的方法。逆推法：从已知结果出发，用迭代表达式...

sshe 2019-08-15 17:50 评论0 收藏0
校招社招必备核心前端面试问题与详细解答

摘要：本文总结了前端老司机经常问题的一些问题并结合个人总结给出了比较详尽的答案。网易阿里腾讯校招社招必备知识点。此外还有网络线程，定时器任务线程，文件系统处理线程等等。线程核心是引擎。主线程和工作线程之间的通知机制叫做事件循环。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文总结了前端老司机经常问题的一些问题并结合个...

DevTalking 2019-08-02 15:31 评论0 收藏0