# 回溯法
> 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
>
~~~
function hasPathCore(matrix, rows, cols, row, col, path, pathIndex, visited) {
var hasPath = false;
if (row < rows && col < cols && row >= 0 && col >= 0 && visited[row][col] === false) {
if (matrix[row * cols + col] === path[pathIndex]) { // 是否是路径中的item
visited[row][col] = true; // 表示该点已经走过
if (pathIndex === path.length - 1) {
hasPath = true;
} else {
hasPath = hasPathCore(matrix, rows, cols, row - 1, col, path, pathIndex + 1, visited) ||
hasPathCore(matrix, rows, cols, row + 1, col, path, pathIndex + 1, visited) ||
hasPathCore(matrix, rows, cols, row, col - 1, path, pathIndex + 1, visited) ||
hasPathCore(matrix, rows, cols, row, col + 1, path, pathIndex + 1, visited);
if (!hasPath) {
visited[row][col] = false;
}
}
}
}
return hasPath;
}
function hasPath(matrix, rows, cols, path) {
// write code here
if (path.length <= 0) {
return true;
}
var visited = [];
var temp = [];
var i, j;
for (i = 0; i < rows; i++) {
temp = [];
for (j = 0; j < cols; j++) {
temp.push(false);
}
visited.push(temp);
}
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
if (hasPathCore(matrix, rows, cols, i, j, path, 0, visited)) {
return true;
}
}
}
return false;
}
~~~
> 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
~~~
function getNumSum(a, b) {
var str = [].concat(a, b).join('');
var sum = 0;
for (var i = 0; i < str.length; i++) {
sum = sum + Number(str[i])
}
return sum
}
function movingCount(threshold, rows, cols) {
// write code here
if (threshold < 0 || rows < 1 || cols < 1) {
return 0
}
var count = 0;
var visited = [];
for (var i = 0; i < rows; i++) {
visited[i] = [];
for (var j = 0; j < cols; j++) {
visited[i][j] = false;
}
}
count = movingCountSum(threshold, 0, 0, rows, cols, visited);
return count
}
function movingCountSum(threshold, row, col, rows, cols, visited) {
var count = 0;
if (row < rows && col < cols && row >= 0 && col >= 0 && getNumSum(row, col) <= threshold && visited[row][col] === false) {
visited[row][col] = true;
count = 1 + movingCountSum(threshold, row + 1, col, rows, cols, visited) + movingCountSum(threshold, row - 1, col, rows, cols, visited) + movingCountSum(threshold, row, col + 1, rows, cols, visited) + movingCountSum(threshold, row, col - 1, rows, cols, visited)
}
return count;
}
~~~
- html
- 冒泡/捕获/委托
- 前端路由
- Dom
- 创建节点API
- 页面修改型API
- 节点查询型API
- 节点关系型API
- 元素属性API
- DOM事件
- classList
- 性能优化
- 节流防抖
- localStorage sessionStorage
- BOM
- meta
- data属性
- js实现拖拽
- html5
- 关于meta
- 轮播图
- js实现拖放
- 电话号inputFormater
- js
- es6
- promise
- iterator
- generator
- async
- proxy
- Set
- Map
- Object的扩展
- String
- Iterator
- Symbol
- 解构赋值
- 函数式编程
- module
- 基本数据类型
- 数组相关codings
- for of/for in
- this
- call bind apply
- 闭包
- 作用域
- prototype与继承
- 深浅拷贝
- setTimeOut/setInterval
- 垃圾处理机制
- 设计模式
- 观察者模式
- 单例模式
- 策略模式
- RegExp
- with
- 其他玩意
- Error/Stack Trace
- 面向对象
- css
- 回流重绘
- %取值
- 属性继承/属性优先级
- flex
- BFC
- 盒模型
- 设置css的方法
- 定位机制
- 块级/行内元素
- hack和一些别的玩意
- css动画
- 几个布局
- 画图形
- css3
- animation对比transform
- 点击不同图片区域跳转不同
- css选择器性能问题
- vh rem em
- css选择器
- 伪类伪元素
- css匹配原理
- 数据结构与算法
- 数据结构
- 树
- 链表
- 栈和队列
- 排序
- 归并排序
- 插入排序
- 选择排序
- 冒泡排序
- 快速排序
- 递归
- 回溯法
- 搜索算法
- 动态规划
- http
- 跨域问题
- CORS
- GET/POST
- ajax
- ajax上传文件
- http缓存
- https
- TCP/UDP
- cookie/session
- http2.0
- spdy
- websocket
- React
- redux
- 生命周期
- 虚拟dom与diff
- 双向数据绑定
- mvvm
- setState
- contextApi props reudx
- 高阶组件
- react-redux
- Fiber
- react-router
- 受控/非受控组件
- 待整理
- webpack
- loader实现
- 前端安全
- 移动端适配
- Vue
- 传值
- 其他