讨论/算法和数据结构/哪位可以作出这个算法题目?/
哪位可以作出这个算法题目?

字节一面题目:
这题目看着简单,但就是不知道怎么写出来,哪位不吝赐教,写下你的代码
WechatIMG3.png

展开讨论
共 4 个讨论

递归生成n叉树,虽然难度是中等,但是n叉树很少写,写了差不多1小时,但是面试紧张难写出来。

let listToTree = function(list) {
  if (list === null || list.length === 0) {
    return []
  }

  let TreeNode = function(name) {
    this.name = name
    this.child = []
  }

  let generateTree = function(start, end) {
    let node = new TreeNode(list[start])
    node.child = listToTree(list.slice(start + 1, end + 1))

    return node
  }

  let core = function(start, end) {
    let slow = start
    let fast = start
    while (fast <= end) {
      fast++
      while (fast <= end && list[slow].slice(1) < list[fast].slice(1)) {
        fast++
      }
      result.push(generateTree(slow, fast - 1))
      slow = fast
    }
  }

  let result = []
  core(0, list.length - 1)

  return result
}
var list = [
  'h1', 'h2', 'h3', 'h3', 'h2', 'h3',
]
var shunxu = [
  'h4', 'h3', 'h2', 'h1'
]

class Node {
  constructor (name) {
    this.name = name
    this.child = []
  }
}

var temp = {}
var h1 = new Node('h1')
for (let i = 0; i < list.length; i++) {
  var key = list[i];
  temp[key] = new Node(key)  // 创建对应的对象和key  如果有了直接就覆盖就行
  var shunxuIndex = shunxu.indexOf(key)  // 找出顺序的 位置
  for (let j = shunxuIndex + 1; j < shunxu.length; j++) {  // 找到了以后 找出最近的父节点 推如父节点的 对应的子数组中
    if (shunxu[j] in temp) {
      temp[shunxu[j]]['child'] = temp[shunxu[j]]['child'] || []
      temp[shunxu[j]]['child'].push(temp[key])
      break
    }
  }
}
console.log(temp['h1']);

有个简单的思路 得往下完善完善

太菜了 T T, 研究了我快两个小时,用了个最蠢的方法做出来。。
主要的思路是:

  1. 把生成的新节点数据推到栈里面
    2)数组取出来的新数据,要和栈顶元素比较大小
    如果数组的数字大于栈顶元素存放的数字,新节点存放到栈顶元素的 child 中,继续取下一个数组数字进行比较
    如果数组的数字小于等于栈顶元素存放的数字,栈顶元素弹出,继续比较
    栈如果为空的话,把新节点存放到根节点
    希望对你有帮助 :)

function hToNumber(value) {
	return parseInt(value.split('').reverse().join());
}

function transformer(array = []) {
	return array.reduce(
		(ctx, value) => {
			const { stack, result } = ctx;
			const pending = { name: value, child: [] };

			if (result.length === 0) {
				result.push(pending);
				stack.push(pending);
			} else {
				while (1) {
					let item = stack.pop();
					if (item) {
						if (hToNumber(value) > hToNumber(item.name)) {
							item.child.push(pending);
							stack.push(item);
							stack.push(pending);
							break;
						} else {
							continue;
						}
					} else {
						result.push(pending);
						stack.push(pending);
						break;
					}
				}
			}

			return {
				stack,
				result
			};
		},
		{
			stack: [],
			result: []
		}
	).result;
}

transformer(["h3", "h2", "h3", "h1", "h2", "h3", "h3", "h2", "h3", "h1", "h2", "h4", "h2", "h3"]);

可能是我太笨了,题目都看不明白。
list是一个数组吧?那怎么区分出行呢?每行又不是一个子数组。为啥第二行不能是第一行的子节点呢?
就算能区分出行,然后同一行里面,比如第三行,题目也没说最多有几个子节点,为啥不能一个根,其他都是子节点呢?

让我猜一猜,可能h1,h2,h3这些代表层次吧,h1必须在h2的上一层,以此类推吧,这样才能解释
不过这个到底是考编程还是考智商。。