记录

0503 1.  Shortest Palindrome

/**
* @param {string} s
* @return {string}
*/
var shortestPalindrome = function(s) {
  s = s || ''
  const reversed = [...s].reverse().join('') // !!!! join with "", or it is ','
  const str = `${s}_${reversed}`
  // build the partial match table
  const table = Array(str.length).fill(-1)
  for (let i = 0; i + 1 < str.length; i++) {
    let j = table[i]
    let found = false
    while (!found) {
      if (str[i + 1] === str[j + 1]) {
        table[i + 1] = j + 1
        found = true
      } else {
        if (j === -1) {
          table[i + 1] = -1
          found = true
        } else {
          j = table[j]
        }
      }
    }
  }
  const len = table[str.length - 1] + 1
  const rest = s.slice(len)
  return [...rest].reverse().join('') + s
};

0506 1. LFU Cache

class Node {
  constructor () {
    this.prev = null
    this.next = null
  }
  insertAfter (node) {
    // check
    const next = this.next
    this.next = node
    node.prev = this
    node.next = next
    next.prev = node
  }
  removeSelf () {
    // check
    const prev = this.prev
    const next = this.next
    prev.next = next
    next.prev = prev
    this.prev = this.next = null
  }
}
class List {
  constructor (sentinel) {
    this.sentinel = sentinel
    sentinel.next = sentinel.prev = sentinel
  }
  add (node) {
    this.sentinel.prev.insertAfter(node)
  }
  get head () {
    return this.sentinel.next
  }
  get tail () {
    return this.sentinel.prev
  }
  isEmpty () {
    return this.sentinel.next === this.sentinel
  }
}
class ValNode extends Node {
  constructor (key, val) {
    super()
    this.key = key
    this.val = val
    this.bucket = null
  }
}
class Bucket extends Node {
  constructor (freq) {
    super()
    this.freq = freq
    this.nodes = new List(new ValNode(-1, -1))
  }
  add (valNode) {
    this.nodes.add(valNode)
    valNode.bucket = this
  }
  remove (valNode) {
    valNode.removeSelf()
    valNode.bucket = null
  }
}

/**
* @param {number} capacity
*/
var LFUCache = function(capacity) {
  this.buckets = new List(new Bucket(-1))
  this.map = new Map()
  this.capacity = capacity
};

/**
* @param {number} key
* @return {number}
*/
LFUCache.prototype.get = function(key) {
  if (this.map.has(key)) {
    const valNode = this.map.get(key)
    this.bump(valNode)
    return valNode.val
  } else {
    return -1
  }
};

LFUCache.prototype.bump = function (valNode) {
  const bucket = valNode.bucket
  const nextFreq = bucket.freq + 1
  let nextBucket
  if (bucket.next.freq === nextFreq) {
    nextBucket = bucket.next
  } else {
    nextBucket = new Bucket(nextFreq)
    bucket.insertAfter(nextBucket)
  }
  bucket.remove(valNode)
  nextBucket.add(valNode)
  this.checkEmpty(bucket)
}

LFUCache.prototype.checkEmpty = function (bucket) {
  if (bucket.nodes.isEmpty()) {
    bucket.removeSelf()
  }
}


/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LFUCache.prototype.put = function(key, value) {
  if (this.capacity === 0) {
    return
  }
  if (this.map.has(key)) {
    const valNode = this.map.get(key)
    valNode.val = value
    this.bump(valNode)
  } else {
    if (this.map.size === this.capacity) {
      const toRemove = this.buckets.head.nodes.head
      // !!!! also need to delete from map
      this.buckets.head.remove(toRemove)
      this.map.delete(toRemove.key)
    }
    const valNode = new ValNode(key, value)
    this.map.set(key, valNode)
    let bucket
    if (this.buckets.head.freq === 1) {
      bucket = this.buckets.head
    } else {
      bucket = new Bucket(1)
      this.buckets.sentinel.insertAfter(bucket)
    }
    bucket.add(valNode)
  }
};

sicilianee 发表于 2018-5-7 05:57
0506 1. LFU Cache

class Node {

TODO: they have shorter code. check if there is a better solution.

0506 2. Unique Letter String

/**
* @param {string} S
* @return {number}
*/
var uniqueLetterString = function(S) {
  if (!S) {
    return 0
  }
  const chars = Array(26).fill().map((val, index) => index).map(i => String.fromCharCode(i + 'A'.charCodeAt(0)))
  const map = new Map()
  chars.forEach(c => {
    map.set(c, [-1, -1])
  })
  const mod = Math.pow(10, 9) + 7
  let count = 0
  for (let i = 0; i < S.length; i++) {
    const [m, n] = map.get(S[i])
    count = (((n - m) * (i - n)) % mod + count) % mod
    map.set(S[i], [n, i])
  }
  const len = S.length
  chars.forEach(c => {
    const [m, n] = map.get(c)
    count = (((n - m) * (len - n)) % mod + count) % mod
  })
  return count
};
console.log(uniqueLetterString('ABC') === 10)
console.log(uniqueLetterString('ABA') === 8)


TODO: checkout the other solution in the solution section.

0509 1. Create Maximum Number

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} k
* @return {number[]}
*/
var maxNumber = function(nums1, nums2, k) {
  if (k === 0) {
    return 0
  }
  let max = null
  for (let i = 0; i <= k; i++) { // !!! and can equal, this i is length, not index, might use a better name
    const j = k - i
    if (i > nums1.length || j > nums2.length) { // !!! there is a range of valid i, we put it here instead of on the loop for easier implementation
      continue
    }
    const a = getMax(nums1, i)
    const b = getMax(nums2, j)
    const c = merge(a, b)
    if (max == null || greater(c, max, 0, 0)) {
      max = c
    }
  }
  return max
};

function greater (nums1, nums2, i1, i2) {
  const len = Math.max(nums1.length - i1, nums2.length - i2)
  for (let i = 0; i < len; i++) {
    // !!!! shit the problem of this is that it turns 0 into -1
    // when it is a number, you cannot use || to set default unless default is 0
    const a = i1 + i < nums1.length ? nums1[i1 + i] : -1
    const b = i2 + i < nums2.length ? nums2[i2 + i] : -1
    if (a !== b) {
      return a > b
    }
  }
  return true
}

// return a list
function getMax (nums, k) {
  const res = []
  const indices = []
  const reversed = [...nums].reverse()
  const getTop = () => res[res.length - 1]
  for (const num of reversed) {
    if (res.length < k) {
      if (res.length > 0 && num < getTop()) {
        indices.push(res.length)
      }
      res.push(num)
    } else {
      if (num >= getTop()) { // !!!! the equal case is important. In the end it can just fit
        // into the flow. Otherwise you compare one by one would cause time complexity to grow
        // go through it two cases you'll see why it can fit into the existing flow
        if (indices.length > 0) {
          // !!! if one is removed, check the new one if it is a bad one
          const index = indices.pop()
          res.splice(index, 1)
          res.push(num)
          if (res[index] < res[index - 1]) {
            indices.push(index)
          }
        } else {
          res.push(num)
          res.shift()
        }
      }
    }
  }
  return res.reverse()
}

// returns a single array
function merge (nums1, nums2) {
  const res = []
  const len = nums1.length + nums2.length
  let i = 0
  let j = 0
  for (let k = 0; k < len; k++) { // !!!! cannot use i again
    const val = greater(nums1, nums2, i, j) ? nums1[i++] : nums2[j++]
    res.push(val)
  }
  return res
}

const val = maxNumber([6,5,4,6,3,7,5,6,4,5,6,4],
[8,8,6,0],
16)

sicilianee 发表于 2018-5-10 11:02
0509 1. Create Maximum Number

/**

getMax can be simplified. Check the standard solution.

sicilianee 发表于 2018-5-10 11:06
getMax can be simplified. Check the standard solution.

I guess going forwards is easier than going backwards.

0509 2. Dungeon Game

/**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function(dungeon) {
  if (dungeon == null || dungeon.length === 0 || dungeon[0].length === 0) {
    return 0
  }
  const rowLen = dungeon.length
  const colLen = dungeon[0].length
  const dp = dungeon.map(row => row.map(el => -Infinity))
  dp[rowLen - 1][colLen - 1] = dungeon[rowLen - 1][colLen - 1]
  for (let i = rowLen - 1; i >= 0; i--) {
    for (let j = colLen - 1; j >= 0; j--) {
      // left, up
      const currVal = dp[i][j]
      const moves = [[-1, 0], [0, -1]]
      for (const [dx, dy] of moves) {
        const [x, y] = [i + dx, j + dy]
        if (x >= 0 && y >= 0) {
          const cost = dungeon[x][y]
          const nextVal = currVal + cost
          const val = Math.min(cost, nextVal)
          dp[x][y] = Math.max(dp[x][y], val)
        }
      }
    }
  }
  const val = dp[0][0]
  if (val > 0) {
    return 1 // !!! same here, cannot be 0, at least 1
  } else {
    return -val + 1 // !!! cannot be 0, so + 1
  }
};

sicilianee 发表于 2018-5-10 12:19
0509 2. Dungeon Game

/**

check the most voted solution. That is a different way of thinking:
our solution more like the knapsack problem, where each time we use the current val to generate new vals to update other positions.
While their solution is like traditional dp: on each cell, we look for previous calculated cells and build current cell value from previous ones.
It is like one is from current and update next, one is from prev get current.
In some cases you cannot ensure you've calculated all previous values then the knapsack pattern is more useful. It only updates if it find a better value.

sicilianee 发表于 2018-5-10 12:19
0509 2. Dungeon Game

/**

ensure always bigger than 0, 想象一个线性规划，linear programming, 就是一条经过最低点的线在平移。