记录

添酒回灯重开站

0222

1. Median of Two Sorted Arrays

brute force

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
  nums1 = nums1 || []
  nums2 = nums2 || []
  if (nums2.length < nums1.length) {
    ;[nums1, nums2] = [nums2, nums1];
  }
  const len1 = nums1.length;
  const len2 = nums2.length;
  const even = (len1 + len2) % 2 === 0
  for (let i = 0; i <= len1; i++) {
    const j = Math.trunc((len1 + len2 + 1) / 2) - i
    const iLeft = i === 0 ? -Infinity : nums1[i - 1];
    const jLeft = j === 0 ? -Infinity : nums2[j - 1];
    const iRight = i === len1 ? Infinity : nums1[i];
    const jRight = j === len2 ? Infinity: nums2[j];
    const max = Math.max(iLeft, jLeft);
    const min = Math.min(iRight, jRight);
    if (max <= min) {
      return even ? (max + min) / 2 : max
    }
  }
  return null
};

sicilianee 发表于 2018-2-23 14:04
0222

1. Median of Two Sorted Arrays

Binary search version


/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
  // lets try binary search
  nums1 = nums1 || []
  nums2 = nums2 || []
  const len1 = nums1.length;
  const len2 = nums2.length;
  if (len2 < len1) {
    return findMedianSortedArrays(nums2, nums1);
  }
  let low = 0;
  let high = len1;
  const even = (len1 + len2) % 2 === 0
  while (low <= high) {
    const i = low + Math.trunc((high - low) / 2)
    const j = Math.trunc((len1 + len2 + 1) / 2) - i
    const iLeft = i === 0 ? -Infinity : nums1[i - 1]
    const jLeft = j === 0 ? -Infinity: nums2[j - 1]
    const iRight = i === len1 ? Infinity : nums1[i]
    const jRight = j === len2 ? Infinity: nums2[j]
    if (iLeft > jRight) {
      high = i - 1;
    } else if (jLeft > iRight) {
      low = i + 1;
    } else {
      return even ? (Math.max(iLeft, jLeft) + Math.min(iRight, jRight)) / 2 : Math.max(iLeft, jLeft)
    }
  }
  return null

};

sicilianee 发表于 2018-2-23 14:32
Binary search version

76        

0222 2. Swim in Rising Water

/**
* @param {number[][]} grid
* @return {number}
*/
// default to min heap conforming to Java's priority queue
// push, pop, top, size
class Heap {
  constructor (data, compare) {
    this.data = data || []
    this.compare = compare || ((a, b) => a - b)
    const lastParent = this.getParent(this.data.length - 1)
    for (let i = lastParent; i >= 0; i--) {
      this.siftDown(i)
    }
  }
  getParent (i) {
    return Math.trunc((i - 1) / 2)
  }
  swap (i, j) {
    ;[this.data[i], this.data[j]] = [this.data[j], this.data[i]]
  }
  siftDown (i) {
    let min = i
    const left = 2 * i + 1
    const right = 2 * i + 2
    for (let index of [left, right]) {
      if (index < this.data.length && this.compare(this.data[index], this.data[min]) < 0)  { // !!! min, not i
        min = index
      }
    }
    if (min !== i) {
      this.swap(i, min)
      this.siftDown(min)
    }
  }
  siftUp (i) {
    // found a bug???? if it is the only one, how do you siftUp?
    // then parent is itself, just remove equal?
    const parent = this.getParent(i)
    if (this.compare(this.data[parent], this.data[i]) > 0) { // !!! remove === ?
      this.swap(parent, i)
      this.siftUp(parent)
    }
  }
  get size () {
    return this.data.length
  }
  peak () {
    return this.data[0]
  }
  push (val) {
    this.data.push(val)
    this.siftUp(this.data.length - 1)
  }
  pop () {
    if (this.size > 0) {
      const val = this.peak()
      this.swap(0, this.data.length - 1)
      this.data.pop()
      this.siftDown(0)
      return val
    } else {
      throw new Error('Heap is empty')
    }
  }
}

var swimInWater = function(grid) {
  if (grid == null || grid.length === 0 || grid[0].length === 0) {
    return 0
  }
  const heap = new Heap([], (a, b) => grid[a[0]][a[1]] - grid[b[0]][b[1]])
  const set = new Set()
  const start = [0, 0]
  heap.push(start)
  set.add(`${start[0]}:${start[1]}`)
  let max = -Infinity
  const len = grid.length;
  while (heap.size > 0) {
    const node = heap.pop()
    const [x, y] = node
    const val = grid[x][y]
    max = Math.max(max, val)
    if (x === len - 1 && y === len - 1) {
      return max
    } else {
      const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]]
      for (let [dx, dy] of moves) {
        const newX = x + dx;
        const newY = y + dy;
        if (newX >= 0 && newX < len && newY >= 0 && newY < len && !set.has(`${newX}:${newY}`)) {
          set.add(`${newX}:${newY}`)
          heap.push([newX, newY])
        }
      }
    }
  }
  return null;
};



Heap implementation is copied from previous code.

0223

shunting yard algorithm, a shady implementation:

const yard = str => {
  const output = convert(str)
  const stack = []
  for (let token of output) {
    if (isNumber(token)) {
      stack.push(token)
    } else {
      const b = stack.pop()
      const a = stack.pop()
      const val = calc(a, b, token)
      stack.push(val)
    }
  }
  return stack[0]
}

function calc (a, b, oper) {
  switch (oper) {
    case '+':
      return a + b
    case '-':
      return a - b
    case '*':
      return a * b
    default:
      throw new Error('No such oper')
  }
}

function convert (input = '') {
  const tokens = input.split(' ')
  const stack = []
  const output = []
  for (let token of tokens) {
    if (isNumber(token)) {
      output.push(Number.parseInt(token, 10))
    } else if (token === '(') {
      stack.push(token) // !!! push to the stack, not the output queue, shit
    } else if (token === ')') {
      while (true) {
        const oper = stack.pop()
        if (oper === '(') {
          break;
        }
        if (oper === undefined) {
          break;
        }
        output.push(oper)
      }
    } else {
      while (stack.length > 0 && compare(token, stack[stack.length - 1]) <= 0) {
        output.push(stack.pop())
      }
      stack.push(token)
    }
  }
  while (stack.length > 0) {
    output.push(stack.pop())
  }
  return output
}

// + - *
function compare (a, b) {
  // !!!!! you didn't consider '('
  const map = new Map([
    ['(', -1],
    ['*', 1],
    ['+', 0],
    ['-', 0]
  ])
  return map.get(a) - map.get(b)
}

function isNumber (str) {
  const num = Number.parseInt(str, 10)
  return Number.isInteger(num)
}

// test convert
const input = '3 + ( 4 + 5 - 5 * ( 5 + 6 ) )'
const val = convert(input)
console.log(val)

// test yard
const cases = [
  ['1 + 3 + 4 * 5', 24],
  ['3 + 2 - 5 + 4', 4],
  ['3 + ( 4 + 5 - 5 * ( 5 + 6 ) )', -43],
  ['3 + ( 4 - 5 ) * 5', -2]
]
const res = cases.map(pair => yard(pair[0]) === pair[1])
console.log(...res)

sicilianee 发表于 2018-2-24 12:41
0223

shunting yard algorithm, a shady implementation:

Simplified version: converting and evaluation combined:

const yard = (str = '') => {
  const tokens = str.split(' ').filter(str => str).map(str => str.trim())
  const output = []
  const stack = []
  const calc = (oper) => {
    const b = output.pop()
    const a = output.pop()
    let val
    switch (oper) {
      case '+':
        val = a + b
        break
      case '-':
        val = a - b
        break
      case '*':
        val = a * b
        break
      default:
        throw new Error('No such type')
    }
    output.push(val)
  }
  for (let token of tokens) {
    // number, (, ), oper
    if (isNumber(token)) {
      output.push(Number.parseInt(token, 10))
    } else if (token === '(') {
      stack.push(token)
    } else if (token === ')') {
      while (true) {
        const oper = stack.pop()
        if (oper === '(') {
          break;
        }
        calc(oper)
      }
    } else {
      while (stack.length > 0 && compare(token, stack[stack.length - 1]) <= 0) { // !!! equals !!!
        const oper = stack.pop()
        calc(oper)
      }
      stack.push(token)
    }
  }
  while (stack.length > 0) {
    calc(stack.pop())
  }
  return output[0]
}

function compare (a, b) {
  const dict = {
    '+': 1,
    '-': 1,
    '*': 2,
    '(': -1
  }
  return dict[a] - dict[b]
}

// + - * () 5 66
function isNumber (str) {
  const val = Number.parseInt(str, 10)
  return Number.isInteger(val)
}


// test yard
const cases = [
  ['1 + 3 + 4 * 5', 24],
  ['3 + 2 - 5 + 4', 4],
  ['3 + ( 4 + 5 - 5 * ( 5 + 6 ) )', -43],
  ['3 + ( 4 - 5 ) * 5', -2]
]
const res = cases.map(pair => yard(pair[0]) === pair[1])
console.log(...res)

0224 1. Basic Calculator IV

/**
* @param {string} expression
* @param {string[]} evalvars
* @param {number[]} evalints
* @return {string[]}
*/
var basicCalculatorIV = function(expression, evalvars, evalints) {
    if (expression == null) {return ''}
    evalvars = evalvars || []
    evalints = evalints || []
    // !!! you cannot just directly replace with string, because there might be names containing the replace name
    const map = new Map()
    for (let i = 0; i < evalvars.length; i++) {
        map.set(evalvars[i], evalints[i]);
    }
    // !!! note they didn't separat parentheses out
    expression = expression.replace(/\(/g, ' ( ')
    expression = expression.replace(/\)/g, ' ) ')
    expression = expression.split(' ').filter(str => str).map(str => {
        return map.has(str) ? map.get(str) : str
    }).join(' ')
    return toList(shunt(expression))
};


function calc (e1, e2, oper) {
  const map = new Map()
  switch (oper) {
    case '*':
      // !!! otherwise the iterator will be exhausted in the double for loop
      const keys1 = [...e1.keys()]
      const keys2 = [...e2.keys()]
      for (let key1 of keys1) {
        const co1 = e1.get(key1)
        for (let key2 of keys2) {
          const co2 = e2.get(key2)
          const co = calcTwo(co1, co2, oper)
          const strs1 = key1.split('*')
          const strs2 = key2.split('*')
          // !!!! filter step is important, otherwise you'll have useless *s
          const key = [...strs1, ...strs2].filter(str => str).sort().join('*')
          const val = map.get(key) || 0
          map.set(key, val + co)
        }
      }
      break; // !!! automatic fall through !!! shit
    default:
      const keys = new Set([...e1.keys(), ...e2.keys()])
      for (let key of keys) {
        const a = e1.get(key) || 0
        const b = e2.get(key) || 0
        const res = calcTwo(a, b, oper)
        map.set(key, res)
      }
      break;
  }
    return map
}
function calcTwo (num1, num2, oper) {
  switch (oper) {
    case '+': return num1 + num2
    case '-': return num1 - num2
    case '*': return num1 * num2
    default: throw new Error('No such type')
  }
}
function toList (eMap) {
  const keys = [...eMap.keys()].sort((key1, key2) => {
    const strs1 = key1.split('*')
    const strs2 = key2.split('*')
    // !!! '' and a, both don't have the *, will have same length
    // so cope with '' first
    // !!! and note reverse order
    if (!key1) {return 1}
    if (!key2) {return -1}
    if (strs1.length !== strs2.length) {
      return strs2.length - strs1.length
    } else {
      if (key1 > key2) {
        return 1
      } else if (key1 < key2) {
        return -1
      } else {
        return 0
      }
    }
  })
  // !!! put the filter here because it could never enter the calc function, like: '0'
  return keys.filter(key => eMap.get(key)).map(key => {
    return key
      ? `${eMap.get(key)}*${key}`
      : `${eMap.get(key)}`
  })
}
// +, -, *, (, ), 45, abcde
function shunt (str) {
  const tokens = str.split(' ')
  const output = []
  const stack = []
  const calcNext = (oper) => {
    const b = output.pop()
    const a = output.pop()
    const res = calc(a, b, oper)
    output.push(res)
  }
  const compare = (a, b) => {
    const dict = {
      '+': 1,
      '-': 1,
      '*': 2,
      '(': -1
    }
    return dict[a] - dict[b]
  }
  for (let token of tokens) {
    if (isNumber(token)) {
      output.push(new Map([['', Number.parseInt(token, 10)]]))
    } else if (token === '(') {
      stack.push('(')
    } else if (token === ')') {
      while (true) {
        const aToken = stack.pop()
        if (aToken === '(') {
          break;
        }
        calcNext(aToken)
      }
    } else if (['+', '-', '*'].includes(token)) {
      while (stack.length > 0 && compare(token, stack[stack.length - 1]) <= 0) { // todo: check this // !!! and test for empty
        const aToken = stack.pop()
        calcNext(aToken)
      }
      stack.push(token)
    } else { // var
      output.push(new Map([[token, 1]]))
    }
  }
  while (stack.length > 0) {
    calcNext(stack.pop())
  }
  return output[0]
}

function isNumber (str) {
  const val = Number.parseInt(str, 10)
  return Number.isInteger(val)
}

0224 2. Basic Calculator III

// +-*/(), num
var calculate = function(s) {
  s = s || ''
  const tokens = tokenize(s)
  return shunt(tokens)
};
function tokenize (str = '') {
  let i = 0
  const list = []
  while (i < str.length) {
    if (isDigit(str[i])) {
      let j = i
      while (j < str.length && isDigit(str[j])) {
        j++
      }
      const num = Number.parseInt(str.slice(i, j), 10)
      list.push(num)
      i = j
    } else {
      if (str[i] !== ' ') { // !!! ' ' is not '', is not falsy !!! 这个还蛮重要的，蛮容易忽略的
        list.push(str[i])
      }
      i++ // !!! 1. update loop var
    }
  }
  return list
}
function isDigit (c) {
  return c >= '0' && c <= '9' // !!! 2. str, not number
}
function compute (a, b, oper) {
  switch (oper) {
    case '+': return a + b
    case '-': return a - b
    case '*': return a * b
    case '/': return Math.trunc(a / b) // !!!! they require trunc
    default:
      throw new Error('no such type')
  }
}
function compare (a, b) {
  const dict = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2,
    '(': -1
  }
  return dict[a] - dict[b]
}
function shunt (tokens = []) {
  // + - * / ( ) num
  const stack = []
  const output = []
  const calcNext = (oper) => {
    const b = output.pop()
    const a = output.pop()
    const res = compute(a, b, oper)
    output.push(res)
  }
  for (let token of tokens) {
    if (Number.isInteger(token)) {
      output.push(token)
    } else if (token === '(') {
      stack.push(token)
    } else if (token === ')') {
      while (true) {
        const aToken = stack.pop()
        if (aToken === '(') {
          break
        }
        calcNext(aToken)
      }
    } else {
      while (stack.length > 0 && compare(token, stack[stack.length - 1]) <= 0) {
        calcNext(stack.pop())
      }
      stack.push(token)
    }
  }
  while (stack.length > 0) { // !!! typo is also pretty difficult to find out
    calcNext(stack.pop())
  }
  return output[0]
}

0226 1. Transform to Chessboard

/**
* @param {number[][]} board
* @return {number}
*/
var movesToChessboard = function(board) {
  if (board == null || board.length === 0 || board[0].length === 0) {
    return 0
  }
  const len = board.length
  const rowMap = new Map()
  for (let row of board) {
    const str = row.join('')
    const num = Number.parseInt(str, 2)
    const count = rowMap.get(num) || 0
    rowMap.set(num, count + 1)
  }
  const colMap = new Map()
  for (let j = 0; j < len; j++) {
    const col = []
    for (let i = 0; i < len; i++) {
      col.push(board[i][j])
    }
    const str = col.join('')
    const num = Number.parseInt(str, 2)
    const count = colMap.get(num) || 0
    colMap.set(num, count + 1)
  }
  const mask = (1 << len) - 1

  function isValid (map) {
    // 1.
    if (map.size !== 2) {
      return false
    }
    const [e1, e2] = [...map.entries()]
    // 2.
    if (len % 2 === 0) {
      if (e1[1] !== e2[1]) {return false}
    } else {
      if (Math.abs(e1[1] - e2[1]) !== 1) {return false}
    }
    // 3.
    const flag = (e1[0] ^ e2[0]) === mask
    if (!flag) {return false}
    return true
  }
  if (!isValid(rowMap) || !isValid(colMap)) {
    return -1
  }
  function count (num, target) {
    return [...((num ^ target) & mask).toString(2)].filter(c => c === '1').length
  }
  function countMap (map) {
      const [e, ...rest] = [...map.entries()]
      const ca = count(e[0], 0xAAAAAAAA)
      const cb = count(e[0], 0x55555555)
      const res = []
      if (ca % 2 === 0) {res.push(ca)}
      if (cb % 2 === 0) {res.push(cb)}
      return Math.min(...res)
  }
  const res = (countMap(rowMap) + countMap(colMap)) / 2
  return res


};


TODO: check the discussion, how do they solve it using such short code?