Leetcode 練習:2021-12-30

December 30, 2021

Binary Tree Preorder Traversal

題號:141

var preorderTraversal = function(root) {
  if (!root) return []
  const stack = [root]
  const result = []
  while (stack.length !== 0) {
    const node = stack.pop()
    result.push(node.val)
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  } 
  return result
}

Binary Tree Postorder Traversal

題號:145

var postorderTraversal = function(root) {
  if (!root) return []
  const stack = [root]
  const result = []
  while (stack.length !== 0) {
    const node = stack.pop()
    if (node.left) stack.push(node.left)
    if (node.right) stack.push(node.right)
    result.unshift(node.val)
  } 
  return result
}

Binary Tree Inorder Traversal

題號:94

var inorderTraversal = function(root) {
  if (!root) return []
  const stack = []
  const result = []
  let current = root
  while (stack.length !== 0 || current) {
    if (current) {
      stack.push(current)
      current = current.left
    } else {
      const node = stack.pop()
      result.push(node.val)
      current = node.right
    }
  } 
  return result
}

Smallest Integer Divisible by K

題號:1015

var smallestRepunitDivByK = function(k) {
  if(k % 2 === 0 && k % 5 === 0) return -1
  let temp = 0
  for(var i = 1; i <= k; i++){
    temp = (temp * 10 + 1) % k
    if(temp === 0) return i
  }
  return -1
}

更快的寫法:

var smallestRepunitDivByK = function(k) {
  if(k % 2 === 0 && k % 5 === 0) return -1
  let temp = 0
  const arr = new Set ()
  for(var i = 1; i <= k; i++){
    temp = (temp * 10 + 1) % k
    if(temp === 0) return i
    if (arr.has(temp)) return -1 
    arr.add(temp)
  }
  return -1
}

Profile picture

Wei Hung 的筆記 / 部落格。