바이트 댄스 bytecamp 여름 캠프 온라인 필기시험 프로 그래 밍 문제 2

두 번 째 문 제 는 제목 이 뭔 지 잊 어 버 렸 어 요. 어차피 개인 적 으로 'True' 나 'False' 로 돌아 가 는 느낌 이 라면 그냥 return 하나 로 도 많은 케이스 를 넘 길 수 있 을 것 같 아 요.첫 번 째 문제 와 세 번 째 문제 의 해법 을 제시 하 다.그 가 준 환경 에서 벗 어 났 기 때문에 js 는 getline 과 print 로 입 출력 을 모 의 할 방법 이 없다.아니면 말 을 안 해? 왜 하위 함수 형식 으로 문 제 를 내지 않 아? 습관 이 됐어.

// bytedance-q1
function BinaryTree(left = null, right = null) {
  this.left = left
  this.right = right
}
let root = new BinaryTree()
function createTree(root, b, w, layer) {
  // left->black, right->white
  if(b >= layer) {
    let left = new BinaryTree()
    root.left = left
    createTree(left, b - layer, w, layer + 1)
  }
  if(w >= layer) {
    let right = new BinaryTree()
    root.right = right
    createTree(right, b, w - layer, layer + 1)
  }
  if(layer === maxLayer + 1) {
    n++
  }
  else if(layer > maxLayer + 1) {
    maxLayer = layer - 1
    n = 1
  }
}
let maxLayer = 0, n = 0
createTree(root, 9, 6, 1)
console.log('maxLayer:', maxLayer, 'n:', n)

첫 번 째 문 제 는 나무 로 모든 상황 을 들 고 성능 을 작은 최적화 시 켰 다. 나 무 를 지 을 때 최대 층수 와 종 류 를 직접 통계 하면 더 이상 옮 겨 다 니 지 않 아 도 된다.

// bytedance-q3
const n = 6, q = 6
let tree = []
for(let i = 0; i < n + 1; i++) {
  tree.push({})
}
const val_arr = [1, 2, 3, 4, 5, 6]
for(let i = 1; i <= n; i++) {
  tree[i].val = val_arr[i - 1]
  tree[i].children = []
}
const relation = [[
  1, 2, 'q'
], [
  1, 3, 'q'
], [
  3, 4, 'a'
], [
  3, 5, 'a'
], [
  3, 6, 'a'
]]
for(let i = 0; i < n - 1; i++) {
  let root = relation[i][0]
  let child = relation[i][1]
  tree[root].children.push(child)
  tree[child].flag = relation[i][2]
}
for(let i = 1; i <= n; i++) {
  let children = tree[i].children
  let sec = true
  if(children.length === 0) {
    sec = false
  }
  for(let child of children) {
    if(tree[child].children.length !== 0) {
      sec = false
      break
    } 
  }
  if(sec) {
    tree[i].sec = true
  }
  else {
    tree[i].sec = false
  }
  
}
const qArray = [1, 2, 3, 4, 5, 6]
for(let q of qArray) {
  console.log(getMax(q))
}
function getMax(root) {
  if(tree[root].children.length === 0) {
    return tree[root].val
  }
  if(tree[root].sec){
    let children = tree[root].children
    let sum = 0
    for(let child of children) {
      sum += getMax(child)
    }
    return sum
  }
  else {
    let children = tree[root].children
    let max = 0
    for(let child of children) {
      const cur = getMax(child)
      if(max < cur) {
        max = cur
      } 
    }
    return max
  }
}

세 번 째 문 제 는 제 생각 에 따 르 면 꼴찌 1 층 의 결 과 는 바로 자신의 가치 이 고 꼴찌 2 층 의 노드 이 며 그 가 치 는 아이의 가치 의 합 입 니 다.나머지 노드 는 아이들 중 가장 큰 부분 이다.여 기 는 성능 최 적 화 를 할 수 있 습 니 다. MAP 캐 시 로 이미 얻 은 노드 의 result 를 사용 할 수 있 습 니 다. 부모 노드 의 값 은 하위 노드 에 달 려 있 기 때 문 입 니 다. 하지만 하하 하 하기 귀 찮 습 니 다. 이렇게 할 수 있다 는 것 을 알 면 됩 니 다.