记录

0414 2. K Inverse Pairs Array

/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var kInversePairs = function(n, k) {
  // the original one tle
  // const M = Math.pow(10, 9) + 7
  // const map = new Map()
  // const getKey = (n, k) => `${n}_${k}`
  // return doFind(n, k)

  // function doFind (n, k) {
  //   if (n === 1) {
  //     return k === 0 ? 1 : 0
  //   }
  //   if (k === 0) {
  //     return 1
  //   }
  //   const key = getKey(n, k)
  //   if (map.has(key)) {
  //     return map.get(key)
  //   }
  //   let res = 0
  //   for (let take = 0; take <= Math.min(n - 1, k); take++) {
  //     const newK  = k - take
  //     res += doFind(n - 1, newK) % M
  //   }
  //   res = res % M
  //   map.set(key, res)
  //   return res
  // }
  // start
  // n, k
  const dp = Array(n + 1).fill().map(() => Array(k).fill(0)) // !!! size n + 1, cause it starts from 1, ends at n
  const M = Math.pow(10, 9) + 7
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= k; j++) {
      if (i === 1) {
        dp[i][j] = j === 0 ? 1 : 0
      } else if (j === 0) { // !!! if you don't return, put them into if else
        dp[i][j] = 1
      } else { // !!! above
        const a = dp[i][j - 1]
        const b = dp[i - 1][j]
        const c = j >= i ? dp[i - 1][j - i] : 0 // !!! j >= i, not reverse
        dp[i][j] = (a + b + M - c) % M // !!! 1. need to % M, or you got infinity
        // !!! 2. IMPORTANT: because you mod'd and you need to subtract, it is possible
        // that you got negative!!! add another M to prevent that
      }
    }
  }
  return dp[n][k]
};

console.log(kInversePairs(1000, 1000))

0415 1. Palindrome Pairs

/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function(words = []) {
  // build the whole map
  // for each word, if another word can become a palindrome with it
  // 1. it is a palindrome and add an empty string to it. two can be formed
  // 2. the reverse of it is in the map. two can be formed
  // 3. loop a break point, left - right, left is palindrome and reverse right is in the map
  //    or right is palindrome and reverse left is in the map
  // we do use a set to deduplicate
  const map = new Map(words.map((word, index) => [word, index]))
  const set = new Set()
  const getKey = (i, j) => `${i}_${j}`
  for (const [index, word] of words.entries()) {
    // 1.
    if (isPalindrome(word)) {
      if (map.has('')) {
        const aIndex = map.get('')
        if (index !== aIndex) {
          set.add(getKey(index, aIndex))
          set.add(getKey(aIndex, index))
        }
      }
    }
    // 2.
    const reversed = [...word].reverse().join('')
    if (map.has(reversed)) {
      const aIndex = map.get(reversed)
      if (index !== aIndex) {
        set.add(getKey(index, aIndex))
        set.add(getKey(aIndex, index))
      }
    }
    // 3.
    for (let i = 0; i < word.length - 1; i++) {
      const left = word.slice(0, i + 1)
      const right = word.slice(i + 1)
      if (isPalindrome(left)) {
        const reverseRight = [...right].reverse().join('')
        if (map.has(reverseRight)) {
          const aIndex = map.get(reverseRight)
          set.add(getKey(aIndex, index))
        }
      }
      if (isPalindrome(right)) {
        const reverseLeft = [...left].reverse().join('')
        if (map.has(reverseLeft)) {
          const aIndex = map.get(reverseLeft)
          set.add(getKey(index, aIndex))
        }
      }
    }
  }

  const parsekey = key => key.split('_').map(str => Number.parseInt(str, 10))
  return [...set].map(key => parsekey(key))
};

// we exclude empty string from here
function isPalindrome (word) {
  const reversed = [...word].reverse().join('')
  return reversed === word
}

0415 2. Binary Tree Maximum Path Sum

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
  if (!root) {return 0}
  let max = -Infinity
  doRecurse(root)
  return max // !!! return max not doRecurse(root) which is the root val

  function doRecurse (root) {
    if (!root) {return 0}
    const left = doRecurse(root.left)
    const right = doRecurse(root.right)
    let meMax = root.val
    if (left > 0) {meMax = meMax + left} // !!! left and right might be empty
    if (right > 0) {meMax = meMax + right}
    max = Math.max(max, meMax)
    return Math.max(root.val, root.val + left, root.val + right) // !!! return it
  }
};

0416 1. Find K-th Smallest Pair Distance



/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var smallestDistancePair = function(nums = [], k) {
  // kth smallest distance is which?
  if (nums.length === 0) {
    return 0
  }
  nums.sort((a, b) => a - b)
  let low = 0
  let high = nums[nums.length - 1] - nums[0]
  while (low <= high) {
    // since we must find it
    const mid = low + Math.trunc((high - low) / 2)
    // get the distance
    let left = 0
    let right = 1
    let count = 0
    while (right < nums.length) {
      while (nums[right] - nums[left] <= mid) {
        count += right - left
        right++
      }
      left++
    }
    // where to put the equal case is a tricky thing. Think through
    if (count < k) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  return low
};

0416 2. Cut Off Trees for Golf Event



/**
* @param {number[][]} forest
* @return {number}
*/
var cutOffTree = function(forest = []) {
  // a point is rowIndex, colIndex. let us get all the indices
  const rowLen = forest.length
  const colLen = forest[0].length
  let nodes = []
  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      nodes.push([i, j])
    }
  }
  nodes = nodes.filter(([x, y]) => forest[x][y] !== 0) // remove obstacles
  nodes.sort(([x1, y1], [x2, y2]) => forest[x1][y1] - forest[x2][y2])
  nodes.unshift([0, 0])

  let total = 0
  for (let i = 0; i < nodes.length - 1; i++) {
    const node = nodes[i]
    const next = nodes[i + 1]
    const dist = getDist(node, next)
    if (dist < 0) {
      return -1
    }
    total += dist
  }
  return total


  function getDist (node1, node2) {
    const equal = (node1, node2) => node1[0] === node2[0] && node1[1] === node2[1]
    if (equal(node1, node2)) {return 0}
    const q = [node1]
    const set = new Set([node1])
    const getKey = (x, y) => `${x}_${y}`
    const addToSet = (node) => {
      const key = getKey(node[0], node[1])
      set.add(key)
    }
    let dist = 0
    while (q.length > 0) { // !!! q.length, it is a list, not a real queue f***
      dist++
      const size = q.length
      for (let i = 0; i < size; i++) {
        const node = q.shift()
        const [x, y] = node
        const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        for (const [dx, dy] of moves) {
          const newX = x + dx
          const newY = y + dy
          if (equal([newX, newY], node2)) {
            return dist
          }
          if (newX >= 0 && newX < rowLen && newY >= 0 && newY < colLen && !set.has(getKey(newX, newY)) && forest[newX][newY] !== 0) {
            q.push([newX, newY])
            addToSet([newX, newY])
          }
        }
      }
    }
    return -1
  }
};

0417 1. Minimum Window Substring

/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
  // !!! by all characters they mean all occurrence
  // duplicates!!!! use map instead of set
  // !!! this is a very common problem, you need to do something, then check the condition
  // then do something else
  // Many cases you could alleviate this by considering forward, like below, we check can
  // we take the next step? if yes, we take it
  // !!! if you cannot

  const baseMap = new Map()
  for (const c of t) {
    const val = baseMap.get(c) || 0
    baseMap.set(c, val + 1)
  }
  const map = new Map()
  let left = -1
  let right = -1
  let count = 0
  let len = t.length
  let min = s
  let found = false
  while (right + 1 < s.length) {
    right++
    if (baseMap.has(s[right])) {
      const val = (map.get(s[right]) || 0) + 1
      map.set(s[right], val)
      if (val <= baseMap.get(s[right])) {
        count++
      }
    }
    while (count === len) {
      found = true
      const str = s.slice(left + 1, right + 1)
      if (str.length < min.length) {
        min = str
      }
      left++
      const c = s[left]
      if (map.has(c)) {
        const val = map.get(c)
        map.set(c, val - 1)
        if (val <= baseMap.get(c)) {
          count--
        }
      }
    }
  }
  return found ? min : ''
};

const s = "a"
const t = "aa"
console.log(minWindow(s, t))

0417 2. Self Crossing

/**
* @param {number[]} x
* @return {boolean}
*/
var isSelfCrossing = function(x = []) {
  if (x.length === 0) {return false}
  const even = {
    last: null,
    lastLast: null
  }
  const odd = {
    last: null,
    lastLast: null
  }
  let prev, oPrev
  let lessCount = 0
  for (let i = 0; i < x.length; i++) {
    const val = x[i]
    if (i % 2 === 0) {
      prev = even
      oPrev = odd
    } else {
      prev = odd
      oPrev = even
    }
    if (prev.last != null && val <= prev.last) {
      lessCount++
      let shortRange = false
      const lastLast = prev.lastLast || 0
      if (lessCount === 1 && val + lastLast >= prev.last) {
        shortRange = true
      }
      const limit = shortRange ? (oPrev.last - oPrev.lastLast) : oPrev.last
      if (i + 1 < x.length) {
        const next = x[i + 1]
        if (next >= limit) {
          return true
        }
      }
    }
    // update
    prev.lastLast = prev.last
    prev.last = val
  }
  return false
};

console.log(isSelfCrossing([1, 1, 3, 2, 1, 1]))

// 顾此失彼，挂一漏万

sicilianee 发表于 2018-4-18 11:59
0417 2. Self Crossing

/**

there are shorter solutions.
And no need for even or odd, just keep 4 variables.

0417 3. Alien Dictionary


/**
* @param {string[]} words
* @return {string}
*/
var alienOrder = function(words = []) {
  const inMap = new Map()
  const adjMap = new Map()
  const used = new Set()
  const allChars = new Set(words.join(''))
  for (let i = 0; i < words.length - 1; i++) {
    const curr = words[i]
    const next = words[i + 1]
    const min = Math.min(curr.length, next.length)
    for (let j = 0; j < min; j++) {
      const a = curr[j]
      const b = next[j]
      if (a !== b) {
        // build adjacency list
        const list = adjMap.get(a) || []
        adjMap.set(a, list)
        list.push(b)
        // build in degree map
        const bVal = inMap.get(b) || 0
        inMap.set(b, bVal + 1)
        used.add(a)
        used.add(b)
        break
      }
    }
  }
  // now topological sort
  const q = [...used].filter(node => !inMap.has(node))
  const order = []
  while (q.length > 0) {
    const node = q.shift()
    order.push(node)
    const list = adjMap.get(node) || [] // !!! possible adjMap doesn't have node, if node doesn't point to any other node
    for (const aNode of list) {
      const val = inMap.get(aNode) - 1
      inMap.set(aNode, val)
      if (val === 0) {
        q.push(aNode)
      }
    }
  }
  if (order.length !== used.size) { // !!! used is set, size, order is array, length
    return ''
  }
  const remaining = [...allChars].filter(c => !used.has(c))
  return remaining.join('') + order.join('')
};

console.log(alienOrder(['z', 'x', 'z']))

0418 1. Range Sum Query 2D - Mutable

TLE ------

// first of f***ing all, we need a segment tree implementation

class SegmentTree {
  constructor (array, merge) {
    this.nodes = []
    this.merge = merge
    this.endIndex = array.length - 1
    this.buildTree(0, 0, array.length - 1, array)
  }
  buildTree (nodeIndex, nodeStart, nodeEnd, array) {
    if (nodeStart > nodeEnd) { // !!! this check
      return
    }
    if (nodeStart === nodeEnd) {
      this.nodes[nodeIndex] = array[nodeStart]
    } else {
      const nodeMid = nodeStart + Math.trunc((nodeEnd - nodeStart) / 2)
      this.buildTree(2 * nodeIndex + 1, nodeStart, nodeMid, array)
      this.buildTree(2 * nodeIndex + 2, nodeMid + 1, nodeEnd, array)
      // merge IMPORTANT
      this.nodes[nodeIndex] = this.merge(this.nodes[2 * nodeIndex + 1], this.nodes[2 * nodeIndex + 2])
    }
  }
  query (start, end) {
    // do some check we ignore
    return this.doQuery(0, 0, this.endIndex, start, end)
  }
  doQuery (nodeIndex, nodeStart, nodeEnd, start, end) {
    if (nodeStart === nodeEnd && start === end && nodeStart === start) {
      return this.nodes[nodeIndex]
    } else {
      const nodeMid = nodeStart + Math.trunc((nodeEnd - nodeStart) / 2)
      if (end <= nodeMid) {
        return this.doQuery(2 * nodeIndex + 1, nodeStart, nodeMid, start, end)
      } else if (start >= nodeMid + 1) {
        return this.doQuery(2 * nodeIndex + 2, nodeMid + 1, nodeEnd, start, end)
      } else {
        const left = this.doQuery(2 * nodeIndex + 1, nodeStart, nodeMid, start, nodeMid)
        const right = this.doQuery(2 * nodeIndex + 2, nodeMid + 1, nodeEnd, nodeMid + 1, end)
        return this.merge(left, right)
      }
    }
  }
  doUpdate (nodeIndex, nodeStart, nodeEnd, index, val) {
    if (nodeStart === nodeEnd && nodeStart === index) {
      this.nodes[nodeIndex] = val
    } else {
      const nodeMid = nodeStart + Math.trunc((nodeEnd - nodeStart) / 2)
      if (index <= nodeMid) {
        this.doUpdate(2 * nodeIndex + 1, nodeStart, nodeMid, index, val)
      } else {
        this.doUpdate(2 * nodeIndex + 2, nodeMid + 1, nodeEnd, index, val)
      }
      // !!! IMPORTANT: merge
      this.nodes[nodeIndex] = this.merge(this.nodes[2 * nodeIndex + 1], this.nodes[2 * nodeIndex + 2])
    }
  }
  update (index, val) {
    // check, we ignore
    this.doUpdate(0, 0, this.endIndex, index, val)
  }
  toString () {
    return 'why'
  }
}


// const arr = [3, 1, 4, 1, 3, 2, 5, 4, 7]
// const seg = new SegmentTree(arr, (a, b) => a + b)
// seg.update(3, 8)

/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix = []) {
  if (matrix.length === 0 || matrix[0].length === 0) {
    this.empty = true
    return
  }
  // first, build the segment tree for each row
  let rowTrees
  this.rowTrees = rowTrees = matrix.map(row => new SegmentTree(row, (a, b) => a + b))
  // now, build the tree of trees
  this.tree = new SegmentTree(rowTrees, (tree1, tree2) => { // merge two trees
    const newTree = new SegmentTree([], (a, b) => a + b)
    newTree.endIndex = tree1.endIndex // !!!! otherwise wrong since you give empty to constructor
    const merge = (nodeIndex) => {
      if (tree1.nodes[nodeIndex] == null) {
        return
      }
      newTree.nodes[nodeIndex] = tree1.nodes[nodeIndex] + tree2.nodes[nodeIndex]
      merge(2 * nodeIndex + 1)
      merge(2 * nodeIndex + 2)
    }
    merge(0)
    return newTree
  })
};



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

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



TLE --- WHY?????



const matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
const n = new NumMatrix(matrix)
console.log(n.sumRegion(2, 1, 4, 3) === 8)
n.update(3, 2, 2)
console.log(n.sumRegion(2, 1, 4, 3) === 10)