记录

0304 3. Expression Add Operators

// this is an expression with only + - /, no parentheses
// this kind of expression can be evaluated in order, that is the key
var addOperators = function(num, target) {
  if (num == null || num.length === 0) {return []}
  const list = []
  dfs(0, '', 0, 0)
  return list

  function dfs (i, path, res, prev) {
    if (i === num.length) {
      if (res === target) {
        list.push(path)
      }
      return
    }
    for (let end = i + 1; end <= num.length; end++) {
      const currStr = num.slice(i, end)
      if (currStr.length > 1 && currStr[0] === '0') {break} // !!! important: 1. cannot have leading 0s in a number except 0 itself; 2. break not return
      const curr = Number.parseInt(currStr, 10)
      if (i === 0) {
        dfs(end, currStr, res + curr, curr) // !!! the first one has no preceding and no operators
      } else {
        dfs(end, `${path}+${currStr}`, res + curr, curr)
        dfs(end, `${path}-${currStr}`, res - curr, -curr)
        dfs(end, `${path}*${currStr}`, res - prev + prev * curr, prev * curr)
      }
    }
  }

};

Whole week not doing shit

0310  Count of Range Sum

// first, prepare the acc array, then have the invariants
// then we divide, until one el, ret
// then, we have two arrays, start the work
// after we count it up,
// merge the two arrays into one
// for readability, we don't use the original array
var countRangeSum = function(nums, lower, upper) {
  if (nums == null || nums.length === 0) {return 0}
  const len = nums.length
  const acc = Array(len)
  acc[-1] = 0 // !!! Trcik1: this is for caculating the acc array
  for (let i = 0; i < nums.length; i++) {
    acc[i] = acc[i - 1] + nums[i]
  }
  let count = 0
  acc.unshift(0) // !!! Trcik2: we acually need one dummy node because
  // we need co calc any sum starting from the first node. But starting from
  // -1 is harder to use, since we don't care about actual indices, just the count
  // we could just push one 0 into the front of the array
  mergeCount(acc)
  return count

  // you have two things to return, both the array and the count
  function mergeCount (array) {
    if (array.length === 1) {
      return array
    }
    // divide the array into 2
    const low = 0
    const high = array.length - 1
    const mid = low + Math.trunc((high - low) / 2)
    const left = mergeCount(array.slice(0, mid + 1))
    const right = mergeCount(array.slice(mid + 1))
    // now both left and right are sorted, we now deal with the count
    let first = 0
    let second = 0
    for (let el of left) {
      while (first < right.length && right[first] - el < lower) {
        first++
      }
      while (second < right.length && right[second] - el <= upper) {
        second++
      }
      count += second - first
    }
    // now count is ready, let's merge the array
    const newArray = []
    let p1 = 0
    let p2 = 0
    while (p1 < left.length || p2 < right.length) {
      const val1 = p1 === left.length ? Infinity : left[p1]
      const val2 = p2 === right.length ? Infinity : right[p2]
      if (val1 <= val2) {
        newArray.push(val1)
        p1++
      } else {
        newArray.push(val2)
        p2++
      }
    }
    return newArray
  }
};

0310 2. Remove Duplicate Letters



// each time we fix the current next character, and go on the recursion
// decide which character we are going to use next, use that character,
// and recurse on the rest of it.
var removeDuplicateLetters = function(s) {
  if (s == null || s.length === 0) {return ''}
  const map = new Map()
  for (let c of s) {
    const count = map.get(c) || 0
    map.set(c, count + 1)
  }
  let index = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] < s[index]) {
      index = i
    }
    const count = map.get(s[i]) - 1
    map.set(s[i], count) // !!! still need to update the count, otherwise like 'bbbbacddd'
    if (count === 0) {
      break
    }
  }
  // we use s[index] as the starting char, and __remove all occurence from remaining__
  const rest = s.slice(index + 1).split(s[index]).join('')
  return s[index] + removeDuplicateLetters(rest)
};

0311 1. Maximum Gap

var maximumGap = function(nums) {
  // last step, just loop sorted nums and calc gap for each one
  nums = radixSort(nums)
  let max = 0
  for (let i = 1; i < nums.length; i++) {
    max = Math.max(max, nums[i] - nums[i - 1])
  }
  return max
};

function radixSort (array) {
  const max = Math.max(...array)
  let base = 1
  while (base <= max) {
    const getKey = num => Math.trunc(num / base) % 10
    array = countingSort(array, getKey)
    base = base * 10
  }
  return array
}

function countingSort (array, getKey) {
  const counts = Array(10).fill(0)
  for (let el of array) {
    counts[getKey(el)]++
  }
  const indices = Array(10).fill(0)
  for (let i = 1; i < 10; i++) {
    indices[i] = indices[i - 1] + counts[i - 1]
  }
  const res = Array(array.length)
  for (let el of array) {
    const key = getKey(el)
    const index = indices[key]
    indices[key]++
    res[index] = el
  }
  return res
}

About sorting:

Counting sort O(n + k), k is the range max, stable
Bucket sort, need subroutine to sort inside buckets
Radix sort:
O(d*n) -> O(d * (n + b)) -> O(log b k * (n + b)). If d, b fixed, becomes O(n)

0311 2. Scramble String

var isScramble = function(s1 = '', s2 = '') {
  if (s1 === s2) {return true}
  if (s1.length !== s2.length) {
    return false
  }
  const map = new Map()
  for (let c of s1) {
    const count = map.get(c) || 0
    map.set(c, count + 1) // !!!! I don't know what you are doing with the map dude. It is map.set(key, value), not just value
  }
  for (let c of s2) {
    const count = map.get(c) || 0
    map.set(c, count - 1)
  }
  for (let count of map.values()) {
    if (count !== 0) {
      return false
    }
  }
  for (let i = 0; i < s1.length - 1; i++) { // !!! not until length
    if (isScramble(s1.slice(0, i + 1), s2.slice(0, i + 1)) && isScramble(s1.slice(i + 1), s2.slice(i + 1))
      || isScramble(s1.slice(0, i + 1), s2.slice(s1.length - 1 - i , s1.length)) && isScramble(s1.slice(i + 1), s2.slice(0, s1.length - 1 - i))
      ) {
      return true
    }
  }
  return false // !!! you need to return false if not met
};

0313 1. Insert Delete GetRandom O(1) - Duplicates allowed


/**
* Initialize your data structure here.
*/
var RandomizedCollection = function() {
  this.map = new Map()
  this.list = []
};

/**
* Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.insert = function(val) {
  const index = this.list.length
  const has = this.map.has(val)
  this.list.push(val)
  const set = this.map.get(val) || new Set()
  set.add(index)
  this.map.set(val, set)
  return !has
};

/**
* Removes a value from the collection. Returns true if the collection contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.remove = function(val) {
  const has = this.map.has(val)
  if (!has) {
    return false
  }
  const currSet = this.map.get(val)
  const len = this.list.length
  const lastVal = this.list[len - 1]
  const lastSet = this.map.get(lastVal)
  const currIndex = currSet.values().next().value
  // !!! divide it into two steps explicitly to avoid last val being the val to delete
  // (in which case two sets will be the same, if combined order really tricky)
  if (currIndex !== len - 1) {
    ;[this.list[currIndex], this.list[len - 1]] = [this.list[len - 1], this.list[currIndex]]
    currSet.delete(currIndex)
    currSet.add(len - 1)
    lastSet.delete(len - 1)
    lastSet.add(currIndex)
  }
  this.list.pop()
  currSet.delete(len - 1)
  // !!! if not exist anymore
  if (currSet.size === 0) {
    this.map.delete(val)
  }
  return has
};

/**
* Get a random element from the collection.
* @return {number}
*/
RandomizedCollection.prototype.getRandom = function() {
  const len = this.list.length
  const index = Math.trunc(Math.random() * len) //  !!!! need to trunc !!!
  return this.list[index]
};

0315 1.  Preimage Size of Factorial Zeroes Function

var preimageSizeFZF = function(K) {
  let low = 0
  let high = K * 5
  while (low <= high) {
    const mid = low + Math.trunc((high - low) / 2)
    const midVal = numZeros(mid)
    if (K === midVal) {
      return 5
    } else if (K < midVal) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return 0

  function numZeros (num) {
    let count = 0
    while (num > 0) {
      count = count + Math.trunc(num / 5)
      num = Math.trunc(num / 5)
    }
    return count
  }

};

0316 1. Maximal Rectangle

var maximalRectangle = function(matrix) {
  // for each point, try to go up as far as possible.
  // extend left, and extend right
  // how many consecutive ones currently on the left, compare with prev, choose smaller
  // how many consecutive ones currently on the right, compare with prev, choose smaller
  // if is zero, just set to zero?
  // when you compare and is zero, just discard it
  // you need a left array
  // a right array
  // a height array, all with colLen long.
  if (matrix == null || matrix.length === 0 || matrix[0].length === 0) {
    return 0
  }
  const rowLen = matrix.length
  const colLen = matrix[0].length
  const left = Array(colLen).fill(Infinity)
  const right = Array(colLen).fill(Infinity)
  const height = Array(colLen).fill(0)
  let max = 0
  for (let i = 0; i < rowLen; i++) {
    // compute left
    let count = 0
    for (let j = 0; j < colLen; j++) {
      if (matrix[i][j] === '1') {
        count++
        left[j] = Math.min(count, left[j])
      } else {
        count = 0
        left[j] = Infinity
      }
    }
    // compute right
    count = 0
    for (let j = colLen - 1; j >= 0; j--) {
      if (matrix[i][j] === '1') {
        count++
        right[j] = Math.min(count, right[j])
      } else {
        count = 0
        right[j] = Infinity
      }
    }
    // compute height
    console.log(left, right)
    for (let j = 0; j < colLen; j++) {
      if (matrix[i][j] === '1') {
        height[j] = height[j] + 1
      } else {
        height[j] = 0
      }
      const area = height[j] === 0 ? 0 : (left[j] + right[j] - 1) * height[j] // !!!! Infinity * 0 = NaN
      max = Math.max(max, area)
    }
  }
  return max
};