???? 前言
大家好呀,我是毛小悠,能够叫我二毛,在家中排行老二,是一名前端开发工程师。
本系列文章旨在通过练习来进步 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
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];
}
???? 后序
本系列会定期更新的,题目会由浅到深的逐步提高。
求关注求点赞 ????~~????????????
能够关注我的公众号: 前端毛小悠 。欢送浏览