记录

0328 3. Basic Calculator



/**
* @param {string} s
* @return {number}
*/



//  "1 + 1"
// " 2-12 + 2 "
// "(1+(4+5+2)-3)+(6+8)"
var calculate = function(s) {
  // first, preprocess into elements, each being
  // num, operator, parenthesis
  const tokens = []
  for (let i = 0; i < s.length; i++) {
    if (isDigit(s[i])) {
      let j = i + 1
      while (isDigit(s[j])) {
        j++
      }
      const num = Number.parseInt(s.slice(i, j), 10)
      tokens.push(num)
      i = j - 1
    } else if (s[i] !== ' ') {
      tokens.push(s[i])
    }
  }
  // ---------------------------
  // now do shunting yard algorithm to convert it to RPN
  const output = []
  const stack = []
  const dict = {
    '+': 1,
    '-': 1,
    '(': 0
  }



  const calcOne = (operator) => {
    const b = output.pop()
    const a = output.pop()
    const val = (() => {
        switch (operator) {
          case '+':
            return a + b
          case '-':
            return a - b
          default:
            throw new Error('No such type')
        }
    })()
    output.push(val)
  }

  for (let el of tokens) {
    if (Number.isInteger(el)) {
      output.push(el)
    } else if (el === '(') {
      stack.push(el)
    } else if (el === ')') {
      while (true) {
        const top = stack.pop()
        if (top === '(') {
          break
        }
        calcOne(top)
      }
    } else {
        while (stack.length > 0 && dict[stack[stack.length - 1]] - dict[el] >= 0) {
          const top = stack.pop()
          calcOne(top)
        }
        stack.push(el)
    }
  }
  while (stack.length > 0) {
    const top = stack.pop()
    calcOne(top)
  }
  return output[0]
};

function isDigit (c) {
  return c >= '0' && c <= '9'
}


checkout normal solutions. shunting yard might not be necessary for this simple one.

0330 1. All O`one Data Structure

class Node {
  constructor (count) {
    this.count = count
    this.set = new Set()
    this.prev = null
    this.next = null
  }
}

/**
* Initialize your data structure here.
*/
var AllOne = function() {
  this.sentinel = new Node(0)
  this.sentinel.next = this.sentinel // !!! set up it self
  this.sentinel.prev = this.sentinel
  this.keyToNode = new Map()
};

/**
* Inserts a new key <Key> with value 1. Or increments an existing key by 1.
* @param {string} key
* @return {void}
*/
AllOne.prototype.inc = function(key) {
  // add
  const node = this.keyToNode.has(key) ? this.keyToNode.get(key) : this.sentinel
  const newCount = node.count + 1
  let newNode
  if (node.next.count === newCount) {
    newNode = node.next
  } else {
    newNode = new Node(newCount)
    this.insertAfter(node, newNode)
  }
  newNode.set.add(key)
  this.keyToNode.set(key, newNode)
  // remove
  if (newCount !== 1) {
    node.set.delete(key)
    if (node.set.size === 0) {
      this.remove(node)
    }
  }
};

AllOne.prototype.insertAfter = function (prev, node) {
  const next = prev.next
  prev.next = node
  node.prev = prev
  node.next = next
  next.prev = node
}

AllOne.prototype.remove = function (node) {
  const prev = node.prev
  const next = node.next
  prev.next = next
  next.prev = prev
}


/**
* Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
* @param {string} key
* @return {void}
*/
AllOne.prototype.dec = function(key) {
  // change
  if (!this.keyToNode.has(key)) {return}
  const node = this.keyToNode.get(key)
  const newCount = node.count - 1
  if (newCount === 0) {
    this.keyToNode.delete(key)
  } else {
    let newNode
    if (node.prev.count === newCount) {
      newNode= node.prev
    } else {
      newNode = new Node(newCount)
      this.insertAfter(node.prev, newNode)
    }
    newNode.set.add(key)
    this.keyToNode.set(key, newNode)
  }
  // remove
  node.set.delete(key)
  if (node.set.size === 0) {
    this.remove(node)
  }
};

/**
* Returns one of the keys with maximal value.
* @return {string}
*/
AllOne.prototype.getMaxKey = function() {
  if (this.sentinel.next === this.sentinel) {
    return ''
  } else {
    const [val] = this.sentinel.prev.set
    return val
  }
};

/**
* Returns one of the keys with Minimal value.
* @return {string}
*/
AllOne.prototype.getMinKey = function() {
  if (this.sentinel.next === this.sentinel) {
    return ''
  } else {
    const [val] = this.sentinel.next.set
    return val
  }
};


想清楚很难，要写伪代码。写不难

0331 1. Design Excel Sum Formula
/**
* @param {number} H
* @param {character} W
*/
var Excel = function(H, W) {
  const rowLen = H
  const colLen = W.charCodeAt(0) - 'A'.charCodeAt(0) + 1 // !!! charCodeAt, not charAt
  this.cells = Array(rowLen).fill().map(() => Array(colLen).fill(0))
  this.getByIndices = (row, col) => {
    const cellVal = this.cells[row][col]
    if (Number.isInteger(cellVal)) {
      return cellVal
    } else {
      return cellVal()
    }
  }
};

function getIndices (r, c) {
  const row = r - 1
  const col = c.charCodeAt(0) - 'A'.charCodeAt(0)
  return [row, col]
}

/**
* @param {number} r
* @param {character} c
* @param {number} v
* @return {void}
*/
Excel.prototype.set = function(r, c, v) {
  const [row, col] = getIndices(r, c)
  this.cells[row][col] = v
};

/**
* @param {number} r
* @param {character} c
* @return {number}
*/
Excel.prototype.get = function(r, c) {
  const [row, col] = getIndices(r, c)
  return this.getByIndices(row, col)
};

/**
* @param {number} r
* @param {character} c
* @param {string[]} strs
* @return {number}
*/
Excel.prototype.sum = function(r, c, strs) {
  const [row, col] = getIndices(r, c)
  this.cells[row][col] = this.buildGetter(strs) // [row][col], not [row, col]
  return this.getByIndices(row, col)
};

function getIndicesFromStr (str) {
  const colStr = str[0]
  const rowStr = str.slice(1)
  return getIndices(Number.parseInt(rowStr, 10), colStr)
}


Excel.prototype.buildGetter = function (strs) {
  // A1, A1:B2
  // !!!! you will use the get call from the class, not directly access -- to support
  // nested getters
  // thus you keep the indices in their format, not direct number format
  strs = strs.map(str => str.trim())
  const indices = []
  for (const str of strs) {
    if (str.includes(':')) {
      const [startStr, endStr] = str.split(':')
      indices.push({
        start: getIndicesFromStr(startStr),
        end: getIndicesFromStr(endStr)
      })
    } else {
      const colStr = str[0]
      const rowStr = str.slice(1)
      indices.push(getIndices(Number.parseInt(rowStr), colStr))
    }
  }
  return () => {
    let sum = 0
    for (const el of indices) {
      if (Array.isArray(el)) {
        const [r, c] = el
        sum += this.getByIndices(r, c)
      } else {
        const {start, end} = el
        for (let i = start[0]; i <= end[0]; i++) {
          for (let j = start[1]; j <= end[1]; j++) {
            sum += this.getByIndices(i, j)
          }
        }
      }
    }
    return sum
  }
}


// we have a 2d array representing each cell
// we have a getKey and getIndices function
// when we set a field, if it is a derived cell, we set it as a function
// when we get from it, if it is a function, we will call. otherwise return the value

sicilianee 发表于 2018-4-1 03:32
0331 1. Design Excel Sum Formula
/**
* @param {number} H

There is a solution using topology sort, basically the push mechanism. Take a look. That might be what the interviewer is expecting.

0331 2. Largest Rectangle in Histogram

/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights = []) {
  heights.push(0)
  const stack = []
  const getStackTop = () => stack[stack.length - 1]
  let max = 0 // !!! init it
  for (let i = 0; i < heights.length; i++) {
    const val = heights[i]
    while (stack.length > 0 && heights[getStackTop()] >= val) {
      const top = stack.pop() // this one, we are gon extend it, to the right is i, to the left is the prev one on stack, both exclsv
      const h = heights[top]
      // !!! it is possible that at this time the stack is empty, shit
      // which means no element on stack is smaller, current one is the smallest of all (or equal), extend to the far left, -1
      const leftBound = stack.length > 0 ? getStackTop() : -1
      max = Math.max(max, h * (i - leftBound - 1)) // !!! use i, not top
      // note top and i are not necessarily connected: when we are in the process of popping,
      // we popped some, so the current top could be in the middle of the area that is bigger than ith
    }
    // !!! important, push the current one onto stack
    stack.push(i)
  }
  return max
};

0410 1. Perfect Rectangle

/**
* @param {number[][]} rectangles
* @return {boolean}
*/
var isRectangleCover = function(rectangles) {
const map = new Map()
  const getKey = (x, y) => `${x}_${y}`

  const setMap = (x, y, side) => {
    const key = getKey(x, y)
    const val = map.get(key) || {
      topLeft: false,
      topRight: false,
      bottomLeft: false,
      bottomRight: false
    }
    map.set(key, val)
    if (val[side]) { // duplicate
      return false
    } else {
      val[side] = true
      return true
    }
  }

  let left = Infinity
  let right = -Infinity
  let top = -Infinity
  let bottom = Infinity
  for (const [x1, y1, x2, y2] of rectangles) {
    const bols = [
      setMap(x1, y1, 'bottomLeft'),
      setMap(x1, y2, 'topLeft'),
      setMap(x2, y1, 'bottomRight'),
      setMap(x2, y2, 'topRight')
    ]
    if (bols.includes(false)) {
      return false
    }
    left = Math.min(left, x1)
    right = Math.max(right, x2)
    top = Math.max(top, y2)
    bottom = Math.min(bottom, y1)
  }

  // next, merge points, if a point can be merged, delete it from map, or mark as merged
  // but since we need to delete, we will
  const keys = [...map.keys()]
  for (const key of keys) {
    const val = map.get(key)
    const leftSame = !(val.topLeft ^ val.bottomLeft)
    const rightSame = !(val.topRight ^ val.bottomRight)
    const topSame = !(val.topLeft ^ val.topRight)
    const bottomSame = !(val.bottomLeft ^ val.bottomRight)
    if (leftSame && rightSame || topSame && bottomSame) {
      map.delete(key)
    }
  }
  // after all, should have only four corners left
  // get left two, right two,
  // left, topLeft, bottomLeft,
  // right, topRight, bottomRight
  // compare left and right
  if (map.size !== 4) {return false}
  for (const [key, val] of map) {
    let count = 0
    const [x, y] = key.split('_').map(str => Number.parseInt(str, 10)) // !!!! str to number after split
    let good = false
    if (val.topLeft) {
      good = x === left && y === top
      count++
    }
    if (val.topRight) {
      good = x === right && y === top
      count++
    }
    if (val.bottomLeft) {
      good = x === left && y === bottom
      count++
    }
    if (val.bottomRight) {
      good = x === right && y === bottom
      count++
    }
    if (count !== 1 || !good) {return false}
  }
  return true
};

0411 1. Chalkboard XOR Game

/**
* @param {number[]} nums
* @return {boolean}
*/
var xorGame = function(nums = []) {
  const res = nums.reduce((a, b) => a ^ b, 0)
  return res === 0 || nums.length % 2 === 0
};

// the key is this: if two numbers xor to 0, they equal.
// then: at any point in time, if a group of numbers xor to not zero, then we take
// one out -- as a, the rest xor to a number. all xor not zero, we know this number and the
// rest xor result not equal. If the rest is not zero, that is ok we take this num.
// if the rest xor to zero, then we take one out from that rest -- as b, then the rest of the
// rest xor to another num c. if c xor a === 0, then c === a. but c xor b === 0, means
// c === b. then a === b. then a xor c xor b should be zero. contradiction.

// so as long as current xor is not 0 and length is even, we won't lose this round.
// same for opponent, so if current length is odd, we will lose.

// also: xor 1 flip, xor 0 no change.

0411 2.  Bus Routes



/**
* @param {number[][]} routes
* @param {number} S
* @param {number} T
* @return {number}
*/
var numBusesToDestination = function(routes = [], S, T) {
  if (S === T) {return 0}
  const stopToBuses = new Map()
  // !!!! in the same route, we coud have duplicate stops -- the bus could go through the
  // same stop multiple times with different next stop, so have to use set
  for (const [bus, stops] of routes.entries()) {
    for (const stop of stops) {
      const buses = stopToBuses.get(stop) || new Set()
      stopToBuses.set(stop, buses) // !!! oh put it back, there are two steps for this shit
      buses.add(bus)
    }
  }
  // !!!! bfs on graph we need a visited set, bfs on tree we don't need that.
  if (!stopToBuses.has(S) || !stopToBuses.has(T)) {return false} // invalid
  const set = new Set([...stopToBuses.get(T)]) // ending buses set
  const visited = new Set()
  const q = [...stopToBuses.get(S)] // initial starting buses
  q.forEach(el => visited.add(el))
  const reached = q => q.some(bus => set.has(bus))
  let level = 1
  while (q.length > 0) {
    if (reached(q)) {return level}
    const size = q.length
    for (let i = 0; i < size; i++) {
      const bus = q.shift()
      const stops = routes[bus]
      for (const stop of stops) {
        // !!!! duplications, not only with self, but on any bus, should use a set
        const buses = stopToBuses.get(stop)
        for (const bus of buses) {
          if (!visited.has(bus)) {
            visited.add(bus)
            q.push(bus)
          }
        }
      }
    }
    level++
  }
  return -1
};

sicilianee 发表于 2018-4-12 13:19
0411 2.  Bus Routes

// ----- keep
// graph and shortest path problem. BFS or dijkstra
// __the key of this one is__:
// 1.
// for shortest path problem, we don't have to start from a single one, we could start
// from multiple ones and go in parallel. oh yeah.

// 2.
// we don't need to actually connect buses, if we build the stop to busese map.
// from bus we have all stops, and from stops we have all other buses. that is
// essentially a hidden adjacency list.
// -----

0414 1. Count The Repetitions



/**
* @param {string} s1
* @param {number} n1
* @param {string} s2
* @param {number} n2
* @return {number}
*/
var getMaxRepetitions = function(s1, n1, s2, n2) {
  const s1Set = new Set([...s1])
  const haveAll = [...s2].every(c => s1Set.has(c))
  if (!haveAll) {return 0} // !!! return number, not true false
  const len1 = s1.length
  const len2 = s2.length
  const total1 = len1 * n1
  let index1 = 0
  let index2 = 0
  const map = new Map()
  const getKey = (i1, i2) => `${i1}_${i2}`
  let prevCount = 0
  let addedCount = 0
  let found = false
  for (let i = 0; i < total1; i++) {
    const c2 = s2[index2]
    const c1 = s1[index1]
    if (c1 === c2) {
      const key = getKey(index1, index2)
      if (map.has(key)) {
        const [prevIndex, oldCount] = map.get(key) // start to repeat
        const countPerRepeat = prevCount - oldCount
        const repeatLen = i - prevIndex
        const remainingLen = total1 - i
        const count = Math.trunc((remainingLen / repeatLen))
        // !!! count === 0 is a special case. why.
        // if count not 0, current is counted as part of the repetition, it will be used.
        // if count is 0, current is already consumed and will be dumped.
        if (count > 0) {
          // from another perspective, will only fast forward if count > 0
          addedCount = count * countPerRepeat
          i = i + count * repeatLen - 1
          // !!! count > 0 means you fast foward it. Then you also need to change index1 and index2
          // here it is no change, so just end this iteration
          continue
        }
        // !!! another thing is how many s2 does the repeat content have?
      } else {
        map.set(key, [i, prevCount])
      }
      // !!!! if detected repetition, would use the current one in that patterns, then the current one would have already been used.
      // move the current addition here to prevent duplication
      if (index2 === s2.length - 1) { // !!! might have repeat, cannot test for char value. test for index
        prevCount++
      }
      index2 = (index2 + 1) % len2
    }
    index1 = (index1 + 1) % len1
  }
  return Math.trunc((prevCount + addedCount) / n2)
};

//


// aaa aaa aaa

// aa

console.log(getMaxRepetitions('a', 2, 'a', 1))


// the start of the solution makes it seem like that is is very complicated, plust it
// doesn't explain things very clearly. Not that easy to follow as other algorithm-ish
// problems. T

// 1. understand the problem ->
// 2. transfer into another well-defined algo problem (usually simpler), can also say
//    this is the modeling process
// 3. solve the other problem using any algorithms/data structurs
//
// For problems like this one, the second step is probably the blocker step.
//

// for this specific one, the key is:
// 1. s1 n1, s2, n2, you could remove n2, just s1 n1 and s2.
//    and s2 doesn't have to appear in the same pattern in s1 each time.
// 2. assume s1 repeats forever, then there gotta be a point where s2 starts to
//    repeat. After that point, all remaining is just repeat the same pattern.

// 无理数，无限不循环小数，不能写成两个整数之比。
// 这就好像做除法一样的， 不是吗，找到无限循环小数从哪里开始循环。

// so find the place where it starts to repeat (the point where it appeared before),
// get the previous appeared point, and what is in the middle is the repeating stuff

// get count before repeating. what after repeating we just calculate it.
// add the two parts up we got the total count.