有谁能做出这道算法题？？

Question

字节一面算法题目：
这题目看着简单，但写不出来，哪位高手不吝赐教，写下你的代码，谢谢

Answer 1

之前错误， 着急去吃饭逻辑没理顺就贴出来了。 想着楼主不着急看，我先记着回头再改， 现在新版本把加戏的代码干掉，看起来符合要求了。

const list = 'h3,h2,h3,h1,h2,h3,h3,h2,h3,h1,h2,h4,h2,h3'.split(',')
const fn = (list) => {
    let result = []
    let last = null
    let root = { child: result }
    list.map(name => {
        const item = { name, child: [], parent: root }
        if (!last) {
            result.push(item)
        } else if (last.name < name) {
            item.parent = last
            last.child.push(item)
        } else if (last.name === name) {
            item.parent = last.parent
            last.parent.child.push(item)
        } else {
            let t = last
            while (t.name >= name) {
                t = t.parent
            }
            t.child.push(item)
        }
        return last = item
    }).map(m => {
        delete m.parent
    })
    return result
}
fn(list)

Answer 2

用树状结构，记住最近添加的节点，对每一个输入值，遍历从该节点到树根的每一个节点，尝试加入。

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()

Answer 3

有点糙，感觉应该是符合要求的

代码如下

用数字替换了一下标签

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;
}

浏览器运行效果

Answer 4

`

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));

`