hi,你好!欢迎访问本站!登录
本站由简数采集腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 文章 - 后端开发 - 正文 看Cosplay古风插画小姐姐,合集图集打包下载:炫龙网 · 炫龙图库

JavaScript中二叉树,动态计划和回溯法(案例剖析)_WEB前端开发

2019-11-29后端开发ki4网26°c
A+ A-
写的比较急忙,测试用例是能悉数跑通的,不过斟酌内存和效力的话,另有很多须要革新的处所,所以请多指教

题目形貌

给定一个二叉树,根节点为第1层,深度为 1。在其第 d 层追加一行值为 v 的节点。

增加划定规矩:给定一个深度值 d (正整数),针对深度为 d-1 层的每一非空节点 N,为 N 建立两个值为 v 的左子树和右子树。

将 N 本来的左子树,衔接为新节点 v 的左子树;

将 N 本来的右子树,衔接为新节点 v 的右子树。

假如 d 的值为 1,深度 d - 1 不存在,则建立一个新的根节点 v,本来的整棵树将作为 v 的左子树。

Example

【相干课程引荐:JavaScript视频教程】

Input: 
A binary tree as following:       4
     /   \    2     6
   / \   / 
  3   1 5   v = 1d = 2Output: 
       4
      / \     1   1
    /     \   2       6
  / \     / 
 3   1   5

基础思想

二叉树的先序遍历

代码的基础构造

不是终究构造,而是大致的构造

/**
 * @param {number} cd:current depth,递归当前深度
 * @param {number} td:target depth, 目的深度
 */
var traversal = function (node, v, cd, td) {
    // 递归到目的深度,建立新节点并返回
  if (cd === td) {
    // return 新节点
  }
  // 向左子树递归
  if (node.left) {
    node.left = traversal (node.left, v, cd + 1, td);
  }
  // 向右子树递归
  if (node.right) {
    node.right = traversal (node.right, v, cd + 1, td);
  }
  // 返回旧节点
  return node;
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} v
 * @param {number} d
 * @return {TreeNode}
 */
var addOneRow = function (root, v, td) {
    // 从根节点入手下手递归
  traversal (root, v, 1, td);
  return root;
};

细致剖析

我们能够分类议论,分三种状况处置惩罚

第1种状况:目的深度<=当前递归途径的最大深度

处置惩罚要领:val节点替代该目的深度对应的节点,而且

● 假如目的节点原来是左子树,那末重置后目的节点是val节点的左子树

● 假如目的节点原来是右子树,那末重置后目的节点是val节点的右子树

第2种状况:目的深度>当前递归途径的最大深度

浏览题目发明,有这么一个形貌:“输入的深度值 d 的局限是:[1,二叉树最大深度 + 1]”

所以呢,当目的深度恰比如当前途径的树的深度再深一层时,处置惩罚方式是:

在最底下那一层节点的摆布分支新增val节点

第3种状况:目的深度为1

我们再剖析题意,题目里说:“假如 d 的值为 1,深度 d - 1 不存在,则建立一个新的根节点 v,本来的整棵树将作为 v 的左子树。”

这申明当:目的深度为1时,我们的处置惩罚方式是如许的

悉数代码

/**
 * @param {v} val,插进去节点照顾的值
 * @param {cd} current depth,递归当前深度
 * @param {td} target depth, 目的深度
 * @param {isLeft}  推断原目的深度的节点是在左子树照样右子树
 */
var traversal = function (node, v, cd, td, isLeft) {
  debugger;
  if (cd === td) {
    const newNode = new TreeNode (v);
    // 假如原来是左子树,重置后目的节点照样在左子树上,不然相反
    if (isLeft) {
      newNode.left = node;
    } else {
      newNode.right = node;
    }
    return newNode;
  }
  // 处置惩罚上述的第1和第2种状况
  if (node.left || (node.left === null && cd + 1 === td)) {
    node.left = traversal (node.left, v, cd + 1, td, true);
  }
  if (node.right || (node.right === null && cd + 1 === td)) {
    node.right = traversal (node.right, v, cd + 1, td, false);
  }
  return node;
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} v
 * @param {number} d
 * @return {TreeNode}
 */
var addOneRow = function (root, v, td) {
  // 处置惩罚目的深度为1的状况,也就是上述的第3种状况
  if (td === 1) {
    const n = new TreeNode (v);
    n.left = root;
    return n;
  }
  traversal (root, v, 1, td);
  return root;
};

单词拆分

题目形貌

给定一个非空字符串 s 和一个包括非空单词列表的字典 wordDict,剖断 s 是不是能够被空格拆分为一个或多个在字典中涌现的单词。

申明:

1.拆分时能够反复应用字典中的单词。

2.你能够假定字典中没有反复的单词。

Example

example1
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true诠释: 返回 true 由于 "applepenapple" 能够被拆分红 "apple pen apple"。
注重: 你能够反复应用字典中的单词。

example2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false泉源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-break

基础思想

动态计划

细致剖析

动态计划的症结点是:寻觅状况转移方程

有了这个状况转移方程,我们就能够依据上一阶段状况和决议计划效果,去求出本阶段的状况和效果

然后,就能够从初始值,不停递推求出终究效果。

在这个问题里,我们应用一个一维数组来寄存动态计划历程的递推数据

假定这个数组为dp,数组元素都为true或许false,

dp[N] 寄存的是字符串s中从0到N截取的子串是不是是“可拆分”的布尔值

让我们从一个细致的中心场景出发来思索盘算历程

假定我们有

wordDict = ['ab','cd','ef']
s ='abcdef'

而且假定如今我们已得出了N=1到N=5的状况,而如今须要盘算N=6的状况

或许说,我们已求出了dp[1] 到dp[5]的布尔值,如今须要盘算dp[6] = ?

该怎样盘算呢?

如今新的字符f被加入到序列“abcde”的背面,云云以来,就新增了以下几种6种须要盘算的状况

A序列 + B序列1.abcdef + ""
2.abcde + f3.abcd + ef4.abc + def5.ab + cdef6.a + bcdef
注重:当A可拆且B可拆时,则A+B也是可拆分的

从中我们不难发明两点

1. 当A可拆且B可拆时,则A+B也是可拆分的

2. 这6种状况只需有一种组合序列是可拆分的,abcdef就一定是可拆的,也就得出dp[6] = true了

下面是依据依据已有的dp[1] 到dp[5]的布尔值,动态盘算dp[6] 的历程

(注重只需盘算到可拆,就能够break轮回了)

细致代码

var initDp = function (len) {
  let dp = new Array (len + 1).fill (false);
  return dp;
};
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  // 处置惩罚空字符串
  if (s === '' && wordDict.indexOf ('') === -1) {
    return false;
  }
  const len = s.length;
  // 默许初始值悉数为false
  const dp = initDp (len);
  const a = s.charAt (0);
  // 初始化动态计划的初始值
  dp[0] = wordDict.indexOf (a) === -1 ? false : true;
  dp[1] = wordDict.indexOf (a) === -1 ? false : true;
  // i:end
  // j:start
  for (let i = 1; i < len; i++) {
    for (let j = 0; j <= i; j++) {
      // 序列[0,i] = 序列[0,j] + 序列[j,i]
      // preCanBreak示意序列[0,j]是不是是可拆分的
      const preCanBreak = dp[j];
      // 截取序列[j,i]
      const str = s.slice (j, i + 1);
      // curCanBreak示意序列[j,i]是不是是可拆分的
      const curCanBreak = wordDict.indexOf (str) !== -1;
      // 状况1: 序列[0,j]和序列[j,i]都可拆分,那末序列[0,i]一定也是可拆分的
      const flag1 = preCanBreak && curCanBreak;
      // 状况2: 序列[0,i]自身就存在于字典中,所以是可拆分的
      const flag2 = curCanBreak && j === 0;
      if (flag1 || flag2) {
        // 设置bool值,本轮盘算完毕
        dp[i + 1] = true;
        break;
      }
    }
  }
  // 返回末了效果
  return dp[len];
};

全分列

题目形貌

给定一个没有反复数字的序列,返回其所有大概的全分列。

Example

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

基础思想

回溯法

细致剖析

1. 深度优先搜刮搞一波,index在递归中向前推动

2. 当index即是数组长度的时刻,完毕递归,收集到results中(数组记得要深拷贝哦)

3. 两次数字交流的应用,盘算出两种状况

总结

想不通没紧要,套路一波就完事了

细致代码

var swap = function (nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
};

var recursion = function (nums, results, index) {
  // 剪枝
  if (index >= nums.length) {
    results.push (nums.concat ());
    return;
  }
  // 初始化i为index
  for (let i = index; i < nums.length; i++) {
    // index 和 i交流??
    // 统计交流和没交流的两种状况
    swap (nums, index, i);
    recursion (nums, results, index + 1);
    swap (nums, index, i);
  }
};
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const results = [];
  recursion (nums, results, 0);
  return results;
};

本文来自 js教程 栏目,迎接进修!

以上就是JavaScript中二叉树,动态计划和回溯法(案例剖析)的细致内容,更多请关注ki4网别的相干文章!

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  选择分享方式
  移步手机端
JavaScript中二叉树,动态计划和回溯法(案例剖析)_WEB前端开发

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
推荐阅读

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>