• 1

  • 485

  • Favorite

JS | 教练,我想做习题12

1 month ago

🚀 前言

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

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

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

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

求关注求点赞👍~~~😘😘😘

📖 题目1:二叉搜索树验证

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

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

这些是有效的二叉搜索树:

    5
   / \
  2   7
 / \   \
1   3   9


  7
 / \
9   2
复制代码

这些不是:

  1
 / \
2   3


  5
 / \
2   9
 \
  7
复制代码

习题代码:

// 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];
}
复制代码

🍁后序

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

求关注求点赞 👍~~🍭🍭🍭

可以关注我的公众号:前端毛小悠。欢迎阅读

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

php

485

Relevant articles

未登录头像

No more data