JS | 教练，我想做习题12 - 起源地下载网

? 前言

大家好呀，我是毛小悠，可以叫我二毛，在家中排行老二，是一名前端开发工程师。

本系列文章旨在通过练习来提高JavaScript的能力，一起愉快的做题吧。???

以下每道题，二毛我都有尝试做一遍。建议限时训练，比如限定为半小时，如果半小时内想不出来，可以结合文章末尾的参考答案来思考。

可以在下方评论区留言或者加我的微信：code_maomao。期待你的到来。

求关注求点赞?~~~???

? 题目1：二进制搜索树验证

一个二叉搜索树是有序的二叉树。这意味着，如果要使用有序遍历将树转换为数组，则该数组将按排序顺序。这种排序的好处是，当树平衡时，搜索是对数时间操作，因为您查看的每个节点都不是您要搜索的节点，因此您可以丢弃搜索树的另一半。

您将编写一个函数来验证给定的二叉树是否为二叉搜索树。排序顺序不是预定义的，因此两者均可使用。

这些是有效的二进制搜索树：

这些不是：

习题代码：

// This is here as documentation. The nodes in the tree are instances of
// this class. You don't need to change this implementation.
class Node {
  constructor(value, left = null, right = null){
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const isBST = node => {
  // Your solution here.
  return false;
};

? 题目2：简单的乐趣：原始编号

任务

约翰有一个重要的数字，他不希望其他人看到它。

他决定使用以下步骤对数字进行加密：

His number is always a non strict increasing sequence
ie. "123"

He converted each digit into English words.
ie. "123"--> "ONETWOTHREE"

And then, rearrange the letters randomly.
ie. "ONETWOTHREE" --> "TTONWOHREEE"

约翰觉得这样做很安全。实际上，这种加密可以很容易地解密:(

给定加密的字符串s，您的任务是解密它，并以字符串格式返回原始数字。

注意，您可以假定输入字符串s始终有效；它仅包含大写字母；解密后的数字按升序排列；前导零是允许的。

例

对于s =“ ONE”，输出应为1。

对于s =“ EON”，输出也应为1。

对于s =“ ONETWO”，输出应为12。

对于s =“ OONETW”，输出也应该为12。

对于s =“ ONETWOTHREE”，输出应为123。

对于s =“ TTONWOHREEE”，输出也应该为123。

习题代码：

function originalNumber(s){
  //coding and coding..
  
}

答案

? 题目1的答案

参考答案1：

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

function isBST(node) {
  const g = inOrder(node);
  const a = g.next();
  if (a.done) return true;
  const b = g.next();
  if (b.done) return true;
  var p = b.value;
  const asc = a.value < p;
  for (const v of g) {
    if (asc ? p > v : p < v) return false;
    p = v;
  }
  return true;
}

function* inOrder(n) {
  if (n !== null) {
    yield* inOrder(n.left);
    yield n.value;
    yield* inOrder(n.right);
  }
}

参考答案2：

class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

const isMinFirstBST = (node, min, max) => {
    return (
        (min === undefined || min < node.value) &&
        (max === undefined || node.value < max) &&
        (node.left === null || isMinFirstBST(node.left, min, node.value)) &&
        (node.right === null || isMinFirstBST(node.right, node.value, max)));
};

const isMaxFirstBST = (node, min, max) => {
    return (
        (min === undefined || node.value > min) &&
        (max === undefined || max > node.value) &&
        (node.left === null || isMaxFirstBST(node.left, node.value, max)) &&
        (node.right === null || isMaxFirstBST(node.right, min, node.value)));
};

const isBST = (node, min, max) => {
    return node === null || isMinFirstBST(node) || isMaxFirstBST(node);
};

参考答案3：

// This is here as documentation. The nodes in the tree are instances of
// this class. You don't need to change this implementation.
class Node {
  constructor(value, left = null, right = null){
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const isBST = node => {
  const list = inOrder(node);
  return isSorted(list, 1) || isSorted(list, -1);
};

const inOrder = node => {
  if (node == null) {
    return [];
  }
  if (node instanceof Node) {
    return [...inOrder(node.left), node.value, ...inOrder(node.right)];
  }
  return [node];
}
const isSorted = (list, order) => {
  return list.every((x,i) => i == 0 || Math.sign(x - list[i - 1]) == order);
}

参考答案4：

// This is here as documentation. The nodes in the tree are instances of
// this class. You don't need to change this implementation.
class Node {
  constructor(value, left = null, right = null){
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const isBST = node => {
  const arr = inOrder(node);
  
  return arr.every( (v, i, a) => i == 0 ? true : v > a[i-1])
    || arr.every( (v, i, a) => i == 0 ? true : v < a[i-1]);
  
  function inOrder(node) { 
    if (node == undefined) return [];
    return inOrder(node.left).concat(node.value).concat(inOrder(node.right)); 
  }
};

参考答案5：

function Node(v,l=null,r=null) { this.value = v, this.left = l, this.right = r; }

const ino = (n,a=[]) => (n.left && ino(n.left,a), a.push(n.value), n.right && ino(n.right,a), a),
      isBST = n => !n || ino(n).every((v,i,a) => !i || (a[0]<a[1] ? a[i-1]<v : v<a[i-1]));

? 题目2的答案

参考答案1：

function originalNumber(s){
  let digits = []
  s = s.split('');
  [ ['Z','ZERO',0],
    ['W','TWO',2],    // Order matters!
    ['G','EIGHT',8],
    ['X','SIX',6],    
    ['S','SEVEN',7],  // For example, must count and splice all SEVENs
    ['V','FIVE',5],   // _before_ using 'V' to search for FIVEs
    ['F','FOUR',4],
    ['H','THREE',3],
    ['O','ONE',1],
    ['I','NINE',9]
  ].forEach(([unique,all,d]) => {
    let n = s.filter(c => c == unique).length
    for (let i = 0; i < n; i++) {
      all.split('').forEach(c => s.splice(s.indexOf(c),1))
      digits.push(d)
    }
  })
  return digits.sort().join``
}

参考答案2：

function originalNumber(s) {
  const r = []
  const d = {E: 0, F: 0, G: 0, H: 0, I: 0, N: 0, O: 0, R: 0, S: 0, T: 0, U: 0, V: 0, W: 0, X: 0, Z: 0}
  for (const c of s) ++d[c]
  for (; d.Z; d.Z--, d.O--) r.push(0)
  for (; d.W; d.W--, d.O--) r.push(2)
  for (; d.U; d.F--, d.O--, d.U--) r.push(4)
  for (; d.F; d.F--, d.I--, d.V--) r.push(5)
  for (; d.X; d.I--, d.X--) r.push(6)
  for (; d.V; d.V--) r.push(7)
  for (; d.G; d.I--, d.G--, d.H--) r.push(8)
  for (; d.I; d.I--) r.push(9)
  for (; d.O; d.O--) r.push(1)
  for (; d.H; d.H--) r.push(3)
  return r.sort().join("")
}

参考答案3：

function originalNumber(s){
  const c=l=> ( s.match(new RegExp(l,'g')) || []).length;
 
  return '0'.repeat(c('Z')) +
         '1'.repeat(c('O')- c('Z')-  c('W') - c('U') ) +
         '2'.repeat(c('W')) +
         '3'.repeat(c('H')-c('G')) +
         '4'.repeat(c('U')) +
         '5'.repeat(c('F')-c('U')) +
         '6'.repeat(c('X')) +
         '7'.repeat(c('V')-c('F')+ c('U')) +
         '8'.repeat(c('G')) +
         '9'.repeat(c('I')-c('F')+ c('U')-c('X')-c('G')) ;
}

参考答案4：

const originalNumber = (_ => {

  let search = [ 
    [ 0, 'Z', 'ZERO' ], 
    [ 8, 'G', 'EIGHT' ], 
    [ 6, 'X', 'SIX' ],
    [ 4, 'U', 'FOUR' ], 
    [ 5, 'F', 'FIVE' ], 
    [ 7, 'V', 'SEVEN' ], 
    [ 9, 'I', 'NINE' ], 
    [ 2, 'W', 'TWO' ], 
    [ 3, 'H', 'THREE' ], 
    [ 1, 'N', 'ONE' ]
  ];

  return str => {

    let res = []
    ,  freq = [ ...str ].reduce((a, b) => (a[b] = (a[b] || 0) + 1, a), {})
    , count = 0;
    
    for (let [ value, key, word ] of search) {
      let count = freq[key];
      
      if (!count)
        continue;
      
      for (let char of word)
        freq[char] -= count;
      
      while (count--)
        res.push(value);
  
    }
    
    return res.sort((a, b) => a - b).join('');
  
  }

})();

参考答案5：

function originalNumber(s) {

    const pairs = {
        0: {string: 'ZERO', key: 'Z', num: 0},
        1: {string: 'TWO', key: 'W', num: 2},
        2: {string: 'FOUR', key: 'U', num: 4},
        3: {string: 'SIX', key: 'X', num: 6},
        4: {string: 'EIGHT', key: 'G', num: 8},
        5: {string: 'ONE', key: 'O', num: 1},
        6: {string: 'THREE', key: 'H', num: 3},
        7: {string: 'FIVE', key: 'F', num: 5},
        8: {string: "SEVEN", key: 'S', num: 7},
        9: {string: 'NINE', key: 'N', num: 9}
    };

    let decoded = [];

    Object.keys(pairs).forEach(function (key) { // for each key in pairs object
        if (s.includes(pairs[key].key)) { // includes returns true/false, based on if char is in string
            let result = contains(s, pairs[key], decoded);
            s = result[0];
            decoded = result[1];
        }
    });
    return decoded.sort().join('').toString();
}

function contains(s, pair_index, decoded) { // removes char at index
    while (s.includes(pair_index.key)) { // if string contains object key, remove full number
        decoded.push(pair_index.num);
        for (let i = 0; i < pair_index.string.length; i++) {
            s1 = s.slice(0, s.indexOf(pair_index.string[i]));
            s2 = s.slice(s.indexOf(pair_index.string[i]) + 1);
            s = s1 + s2;
        }
    }
    return [s, decoded];
}

?后序

本系列会定期更新的，题目会由浅到深的逐步提高。

求关注求点赞 ?~~???

可以关注我的公众号：前端毛小悠。欢迎阅读 JS | 教练，我想做习题12

JS | 教练，我想做习题12

? 前言

? 题目1：二进制搜索树验证

? 题目2：简单的乐趣：原始编号

答案

? 题目1的答案

? 题目2的答案

?后序

常见问题FAQ

掘金(毛小悠) SVIP

发表评论

如需帝国cms功能定制以及二次开发请联系我们

升级SVIP会员

工作时间

? 前言

? 题目1：二进制搜索树验证

? 题目2：简单的乐趣：原始编号

答案

? 题目1的答案

? 题目2的答案

?后序

常见问题FAQ

掘金(毛小悠) SVIP

相关推荐

发表评论

如需帝国cms功能定制以及二次开发请联系我们

升级SVIP会员

工作时间

请选择支付方式