字节一面算法题目:
这题目看着简单,但写不出来,哪位高手不吝赐教,写下你的代码,谢谢
用树状结构,记住最近添加的节点,对每一个输入值,遍历从该节点到树根的每一个节点,尝试加入。
python 示例
#-*- coding: utf-8 -*-
class Node(object):
@classmethod
def top(cls):
return cls(None, None)
def __init__(self, parent, name):
self._parent = parent
self._name = name
self._child = []
def add(self, name):
if self._name is None or name > self._name:
newNode = Node(self, name)
self._child.append(newNode)
return newNode
return self._parent.add(name)
def __str__(self):
if self._parent is None:
return '[{0}]'.format(','.join(map(str, self._child)))
return '{{name: \'{0}\', child: [{1}]}}'.format(self._name, ','.join(map(str, self._child)))
def foo():
input = [
'h3',
'h2', 'h3',
'h1', 'h2', 'h3', 'h3', 'h2', 'h3',
'h1', 'h2', 'h4', 'h2', 'h3',
]
top = Node.top()
lastNode = top
for item in input:
lastNode = lastNode.add(item)
print(top)
foo()
有点糙,感觉应该是符合要求的
用数字替换了一下标签
function render(list){
let array = [];
let item = {};
list.map((n, i)=>{
if(i === 0 || n<=item.name){
item = {
name: n,
child: []
}
array.push(item);
}else{
item.child = arrayChild(item.child, n);
}
})
function arrayChild(child, num){
if(child.length === 0 || child[0].name >= num){
child.push({
name: num,
child: []
})
return child;
}else{
child[child.length-1].child = arrayChild(child[child.length-1].child, num);
return child;
}
}
function printArray(arr, index=1){
arr.map((n, i)=>{
console.log("--".repeat(index)+String(n.name));
if(n.child.length){
printArray(n.child, index+1)
}
})
}
printArray(array)
return array;
}
`
class Node {
constructor(name) {
this.name = name;
this.child = [];
}
appendChild(name) {
if (this.name < name) {
const child = new Node(name);
this.child.push(child);
return child;
}
return false;
}
}
function toTree(arr, node, parentNodes = [node]) {
const [firstNode, ...others] = arr;
if (!arr.length) {
return parentNodes[parentNodes.length - 1];
}
if (!node) {
node = new Node(firstNode);
return toTree(others, node)
} else {
const result = node.appendChild(firstNode);
if (result) {
return toTree(others, result, [node, ...parentNodes]);
} else {
for (let parent of parentNodes) {
const presult = parent.appendChild(firstNode);
if (presult) {
return toTree(others, presult, parentNodes);
}
}
}
}
return node;
}
function splitArr(arr) {
let index = 0;
const result = [];
for(let a of arr) {
if (!result.length) {
result.push([a]);
} else if (a <= result[index][0]) {
result[++index] = [a];
} else {
result[index].push(a);
}
}
return result;
}
const list = [
'h3',
'h2', 'h3',
'h1', 'h2', 'h3', 'h3', 'h2', 'h3',
'h1', 'h2', 'h4', 'h2', 'h3'
]
const arr = splitArr(list);
const result = arr.map(item => toTree(item));
`
10 回答11.1k 阅读
15 回答8.4k 阅读
5 回答4.8k 阅读✓ 已解决
4 回答3.1k 阅读✓ 已解决
8 回答6.2k 阅读
2 回答2.6k 阅读✓ 已解决
3 回答5.1k 阅读✓ 已解决
之前错误, 着急去吃饭逻辑没理顺就贴出来了。 想着楼主不着急看,我先记着回头再改, 现在新版本把加戏的代码干掉,看起来符合要求了。