记录

sicilianee 发表于 2018-4-19 12:28
0418 1. Range Sum Query 2D - Mutable

TLE ------

--- Need some clean up, for the max/min
class Node {
  constructor (xStart, xEnd, yStart, yEnd) {
    this.xStart = xStart
    this.xEnd = xEnd
    this.yStart = yStart
    this.yEnd = yEnd
    this.val = 0
    this.a = null
    this.b = null
    this.c = null
    this.d = null
  }
}
class SegmentTree {
  constructor (matrix) {
    const rowLen = matrix.length
    const colLen = matrix[0].length
    this.root = new Node(0, rowLen - 1, 0, colLen - 1)
    this.buildTree(this.root, matrix)
  }
  buildTree (node, matrix) {
    const {xStart, xEnd, yStart, yEnd} = node // !!!! now you don't have standalone start and end, they reside on node
    if (node.xStart === node.xEnd && node.yStart === node.yEnd) {
      node.val = matrix[xStart][yStart]
    } else {
      let val = 0
      const xMid = xStart + Math.trunc((xEnd - xStart) / 2)
      const yMid = yStart + Math.trunc((yEnd - yStart) / 2)
      node.a = new Node(xStart, xMid, yStart, yMid)
      this.buildTree(node.a, matrix)
      val += node.a.val
      if (xEnd > xStart ) {
        node.b = new Node(xMid + 1, xEnd, yStart, yMid)
        this.buildTree(node.b, matrix)
        val += node.b.val
      }
      if (yEnd > yStart) {
        node.c = new Node(xStart, xMid, yMid + 1, yEnd)
        this.buildTree(node.c, matrix)
        val += node.c.val
      }
      if (xEnd > xStart && yEnd > yStart) {
        node.d = new Node(xMid + 1, xEnd, yMid + 1, yEnd)
        this.buildTree(node.d, matrix)
        val += node.d.val
      }
      node.val = val
    }
  }
  // !!! this parameter order is different from what they give you. error-prone
  query (node, xStart, xEnd, yStart, yEnd) {
    if (xStart > xEnd || yStart > yEnd) {
      return 0
    }
    if (node.xStart === xStart && node.yStart === yStart && node.xEnd === xEnd && node.yEnd === yEnd) {
      return node.val
    } else {
      // TODO: how to simplify this?
      const xMid = node.xStart + Math.trunc((node.xEnd - node.xStart) / 2)
      const yMid = node.yStart + Math.trunc((node.yEnd - node.yStart) / 2)
      const a = this.query(node.a, xStart, Math.min(xEnd, xMid), yStart, Math.min(yEnd, yMid))
      const b = this.query(node.b, Math.max(xMid + 1, xStart), xEnd, yStart, Math.min(yEnd, yMid)) // !!! second part start is mid + 1, not mid
      const c = this.query(node.c, xStart, Math.min(xEnd, xMid), Math.max(yMid + 1, yStart), yEnd)
      const d = this.query(node.d, Math.max(xStart, xMid + 1), xEnd, Math.max(yStart, yMid + 1), yEnd)
      return a + b + c + d
    }
  }
  update (node, i, j, val) {
    if (node == null || i < node.xStart || i > node.xEnd || j < node.yStart || j > node.yEnd) { // !!! node == null check
      return
    }
    if (node.xStart === node.xEnd && node.yStart === node.yEnd && i === node.xStart && j === node.yStart) {
      node.val = val
    } else {
      this.update(node.a, i, j, val)
      this.update(node.b, i, j, val)
      this.update(node.c, i, j, val)
      this.update(node.d, i, j, val)
      const aVal = node.a ? node.a.val : 0
      const bVal = node.b ? node.b.val : 0
      const cVal = node.c ? node.c.val : 0
      const dVal = node.d ? node.d.val : 0
      node.val = aVal + bVal + cVal + dVal
    }
  }
}


// const mat = [
//   [1, 2],
//   [3, 5]
// ]
// const seg = new SegmentTree(mat)
// // console.log(seg.root)

// seg.update(seg.root, 0, 1, 8)
// console.log(seg.root)


// // console.log('---')

// // const mat1 = [[1,3]]
// // const seg1 = new SegmentTree(mat1)
// // console.log(seg1.query(seg1.root))


/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix = []) {
  // !!! how to guard against invalid input?
  if (matrix == null || matrix.length === 0) {
    matrix = [[]]
  }
  this.tree = new SegmentTree(matrix)
};



/**
* @param {number} row
* @param {number} col
* @param {number} val
* @return {void}
*/
NumMatrix.prototype.update = function(row, col, val) {
  this.tree.update(this.tree.root, row, col, val)
};

/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
  return this.tree.query(this.tree.root, row1, row2, col1, col2)
};



// const test = new NumMatrix([[1, 2]])
// console.log(test.sumRegion(0, 0, 0, 0))
// console.log(test.sumRegion(0, 1, 0, 1))
// console.log(test.sumRegion(0, 0, 0, 1))
// console.log(test.update(0, 0, 3))
// console.log(test.update(0, 1, 5))
// console.log(test.sumRegion(0, 0, 0, 1))
// console.log(test.tree.root)

// --- need some clean up for the max/min part

0427 1. First Missing Positive

/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function(nums) {
  nums = nums || []
  let i = 0
  while (i < nums.length) {
    const val = nums[i]
    if (val > 0 && val <= nums.length && nums[val - 1] !== val) {
      ;[nums[val - 1], nums[i]] = [nums[i], nums[val - 1]]
    } else {
      i++
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }
  return nums.length + 1
};
// 1. constant space -- in place, use original array
// 2. len is n, the first missing, must be within n, only unless it is n + 1
// 3. this swap a trick so you don't have to pull another loop. after swapping you don't move
//    yet, you will process the just swapped element

const nums = [1, 2, 3, 4, 5]
console.log(firstMissingPositive(nums) === 6)

0427 2. Coin Path

/**
* @param {number[]} A
* @param {number} B
* @return {number[]}
*/
var cheapestJump = function(A, B) {
  // !!! if the last place is -1, you cannot jump to that place !!
  if (A == null || A.length === 0 || A[A.length - 1] === -1) {
    return []
  }
  const len = A.length
  const dp = A.map(() => ({cost: Infinity, next: -1}))
  dp[len - 1] = {cost: 0, next: -1}
  for (let i = len - 1; i > 0; i--) {
    const {cost, next} = dp[i]
    if (cost !== Infinity) { // can reach
      for (let step = 1; step <= B && i - step >= 0; step++) {
        const index = i - step
        if (A[index] !== -1) {
          const newCost = A[index] + cost
          const node = dp[index]
          if (newCost < node.cost || newCost === node.cost && node.next > i) {
            node.cost = newCost
            node.next = i
          }
        }
      }
    }
  }
  // console.log(dp)
  if (dp[0].cost === Infinity) {
    return []
  } else {
    let i = 0
    const path = [0]
    while (dp[i].next !== -1) {
      path.push(dp[i].next)
      i = dp[i].next
    }
    return path.map(el => el + 1) // !!! they index from 1 and they need the final path
  }
};

0429 1. K-th Smallest in Lexicographical Order


/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var findKthNumber = function(n, k) {
  let node = 1
  k = k - 1
  while (k > 0) {
    const steps = calcSteps(node, node + 1)
    if (steps <= k) {
      k = k - steps
      node = node + 1
    } else {
      k = k - 1
      node = node * 10
    }
  }
  return node


  function calcSteps (n1, n2) {
    let steps = 0
    while (n1 <= n) {
      steps += Math.min(n2, n + 1) - n1 // n + 1, not n - 1
      n1 *= 10
      n2 *= 10
    }
    return steps
  }
};

0429 2. Making A Large Island

/**
* @param {number[][]} grid
* @return {number}
*/
var largestIsland = function(grid) {
  if (grid == null || grid.length === 0 || grid[0].length === 0) {
    return 0
  }
  const moves = [[0, 1], [0, -1], [-1, 0], [1, 0]]
  const rowLen = grid.length
  const colLen = grid[0].length
  let max = 0
  const map = new Map()
  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      if (grid[i][j] === 1) {
        const currKey = `${i}_${j}`
        const visited = new Set()
        recurse(i, j, visited)
        const size = visited.size
        max = Math.max(size, max)
        visited.forEach(key => {
          const [a, b] = key.split('_').map(str => Number.parseInt(str, 10))
          grid[a][b] = currKey
        })
        map.set(currKey, size)
      }
    }
  }
  // after the loop, we marked everything to the correct number
  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      if (grid[i][j] === 0) {
        let count = 1
        const used = new Set()
        for (const [dx, dy] of moves) {
          const x = i + dx
          const y = j + dy
          // !!!! you created the used/visited set but you forget to check it in the condition
          if (x >= 0 && x < rowLen && y >= 0 && y < colLen && grid[x][y] != 0 && !used.has(grid[x][y])) {
            count += map.get(grid[x][y])
            used.add(grid[x][y])
          }
        }
        max = Math.max(count, max)
      }
    }
  }
  return max

  ///
  function recurse (i, j, visited) {
    if (i >= 0 && i < rowLen && j >= 0 && !visited.has(`${i}_${j}`)  && j < colLen && grid[i][j] === 1) {
      visited.add(`${i}_${j}`)
      for (const [dx, dy] of moves) {
        recurse(i + dx, j + dy, visited)
      }
    }
  }
};

sicilianee 发表于 2018-4-30 06:46
0429 2. Making A Large Island

/**

// 重要：这是一个典型的dfs，并不是完全straightforward，这个必须多练习。
// 第一个dfs，我们想单独求count，怎么求？不太好弄其实，因为需要一个global，
// 但是我们又在一个双重loop里， 每次定义一个函数不太经济。这个specific情况因为反正需要一个set，我们
// 可以直接放在set里面，但是general的情况怎么办呢

0430 1. Prefix and Suffix Search



class Node {
  constructor () {
    this.map = new Map()
    this.isEnd = false
  }
}

class Trie {
  constructor (words) {
    this.root = new Node()
    for (const word of words) {
      this.insert(word)
    }
  }
  insert (word) {
    let node = this.root
    for (const c of word) {
      if (node.map.has(c)) {
        node = node.map.get(c)
      } else {
        const newNode = new Node()
        node.map.set(c, newNode)
        node = newNode
      }
    }
    node.isEnd = true
  }
  find (str) {
    let node = this.root
    for (const c of str) {
      if (node.map.has(c)) {
        node = node.map.get(c)
      } else {
        return []
      }
    }
    const res = []
    findAll(str, node, res)
    return res
    function findAll (path, node, res) {
      if (node.isEnd) {
        res.push(path)
      }
      for (const [c, cNode] of node.map) {
        findAll(path + c, cNode, res)
      }
    }
  }
}


/**
* @param {string[]} words
*/
var WordFilter = function(words) {
  this.map = new Map(words.map((word, index) => [word, index]))
  const wrapped = []
  // !!! 后缀也是正着读的，并不是一个一个字母倒过来的。
  for (const word of words) {
    for (let i = 0; i <= word.length; i++) {
      const suffix = word.slice(i)
      wrapped.push(`${suffix}_${word}`)
    }
  }
  this.trie = new Trie(wrapped)
};


/**
* @param {string} prefix
* @param {string} suffix
* @return {number}
*/
WordFilter.prototype.f = function(prefix, suffix) {
  const search = `${suffix}_${prefix}`
  const wrapped = this.trie.find(search)
  const weights = wrapped.map(w => w.split('_')[1]).map(word => this.map.get(word))
  if (weights.length === 0) {
    return -1
  }
  return Math.max(...weights)
};

0430 2. Candy

/**
* @param {number[]} ratings
* @return {number}
*/
var candy = function(ratings) {
  if (ratings == null || ratings.length === 0) {
    return 0
  }
  const len = ratings.length
  const increase = Array(len).fill(0)
  const decrease = Array(len).fill(0)
  let inCount = 0
  let deCount = 0
  for (let i = 1; i < ratings.length; i++) {
    const j = len - 1 - i
    if (ratings[i] > ratings[i - 1]) {
      inCount++
    } else {
      inCount = 0
    }
    if (ratings[j] > ratings[j + 1]) { // !!!! j + 1, not j - 1
      deCount++
    } else {
      deCount = 0
    }
    increase[i] = inCount
    decrease[j] = deCount
  }
  let count = 0
  for (let i = 0; i < ratings.length; i++) {
    count += Math.max(increase[i], decrease[i]) + 1
  }
  return count
};

0430 3. Interleaving String

/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
  if (s1 == null || s2 == null || s3 == null || s3.length !== s1.length + s2.length) {
    return false
  }
  return recurse(0, 0, 0)

  function recurse (i1, i2, i3) {
    if (i1 === s1.length && i2 === s2.length && i3 === s3.length) {
      return true
    }
    if (i1 < s1.length && i3 < s3.length && s1[i1] === s3[i3]) {
      if (recurse(i1 + 1, i2, i3 + 1)) {
        return true
      }
    }
    if (i2 < s2.length && i3 < s3.length && s2[i2] === s3[i3]) {
      if (recurse(i1, i2 + 1, i3 + 1)) {
        return true
      }
    }
    return false
  }
};

sicilianee 发表于 2018-5-1 12:41
0430 3. Interleaving String

/**

dp version?
time complexity?