记录

0509 3. Regular Expression Matching

/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/


// !!! ask questions is important. Clarify edge cases.
// you cannot have starting *, or consecutive *s
// !!! also, * means zero or more of the prev element -- not accurate, prev* together means
// zero or more of the `prev`. Think about it. That means * must go together with what is
// preceding it whenever.
var isMatch = function(s, p) {
  if (s == null || p == null || p[0] === '*') {
    return false
  }
  return match(0, 0)

  function match (i, j) {
    if (i === s.length && j === p.length) {
      return true
    }
    if (j >= p.length) {
      return false
    }
    const cs = s[i]
    const cp = p[j]
    const cpNext = p[j + 1]
    if (cpNext === '*') {
      // combine the two cases
      const remainLen = s.length - i
      for (let matchLen = 0; matchLen <= remainLen; matchLen++) {
        const toUse = cp.repeat(matchLen)
        const toMatch = s.slice(i, i + matchLen)
        const good = cp === '.' || toMatch === toUse
        if (good && match(i + matchLen, j + 2)) {
          return true
        }
      }
      return false
    } else {
      if (cp === '.') {
        return match(i + 1, j + 1)
      } else {
        if (cs === cp) {
          return match(i + 1, j + 1)
        } else {
          return false
        }
      }
    }
  }

};

console.log(isMatch('aa', 'a') === false)
console.log(isMatch('aa', 'a*') === true)
console.log(isMatch('ab', '.*') === true)

sicilianee 发表于 2018-5-10 13:40
0509 3. Regular Expression Matching

/**

check the dp solution.

0511 1. Cherry Pickup

/**
* @param {number[][]} grid
* @return {number}
*/
var cherryPickup = function(grid) {
  if (grid == null || grid.length === 0 || grid[0].length === 0) {
    return 0
  }
  // convert to two persons going from start to end. Relative time when they start is not significant. We can choose.
  // If we choose to let them start at the same time, they would go through duplicate path at the same time, so we can easily remove duplicates.
  // (why? The time it takes to reach a certain point is fixed because of the way they walk. Thus the start point and end point time is the same. Thus they go through the dup path at the exact same time)
  // now we loop steps (they move as the diagnal moves). And we use the knapsack pattern.
  // step from 0 -> 2N - 2, inclusive
  const rowLen = grid.length
  const colLen = grid[0].length
  const N = rowLen // in fact is a square not a random rectangle
  const maxStep = 2 * N - 2
  // only a fraction of this 3d array is used
  const dp = grid.map(row => row.map(el => Array(maxStep + 1).fill(-1))) // from step 0 -> maxStep, so + 1
  const isValid = (x, y) => x >= 0 && x < rowLen && y >= 0 && y < colLen && grid[x][y] >= 0
  dp[0][0][0] = grid[0][0]
  const moves = [[0, 1], [1, 0]]
  for (let step = 0; step < maxStep; step++) { // we based on current value generate next one, initial step = 0 at the first cell
    for (let r1 = 0; r1 <= Math.min(step, N - 1); r1++) {
      for (let r2 = 0; r2 <= Math.min(step, N - 1); r2++ ) {
        // now we have the two points, generate 4 other point combinations for then next step
        const [c1, c2] = [step - r1, step - r2]
        const currVal = dp[r1][r2][step]
        // !!! either current status is not valid, or valid but cannot reach here (previous didn't reach here)
        if (!isValid(r1, c1) || !isValid(r2, c2) || currVal < 0) {
          continue
        }
        for (const [dx, dy] of moves) {
          const [x1, y1] = [r1 + dx, c1 + dy]
          if (isValid(x1, y1)) {
            for (const [dx, dy] of moves) {
              const [x2, y2] = [r2 + dx, c2 + dy]
              if (isValid(x2, y2)) {
                // this is a valid x1, x2 combination
                const val1 = grid[x1][y1]
                const val2 = grid[x2][y2]
                const val = currVal + (x1 === x2 && y1 === y2 ? val1 : val1 + val2)
                dp[x1][x2][step + 1] = Math.max(dp[x1][x2][step + 1], val)
              }
            }
          }
        }
      }
    }
  }
  const val = dp[N - 1][N - 1][2 * N - 2] // !!! -1 needs to be changed to 0
  return val > 0 ? val : 0
};



Interesting part is that you need to add constraint to this problem to reduce it to an easier one: A and B can start at anytime. The key is that their relative start time is not significant so you can pick any one.

sicilianee 发表于 2018-5-12 11:25
0511 1. Cherry Pickup

/**

knapsack pattern is easier to understand

0511 2.  Longest Valid Parentheses

/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
  if (s == null|| s.length === 0) {
    return 0
  }
  // left+, right-, get the accumulation array
  let max = 0
  let count = 0
  const map = new Map() // count -> latest index
  map.set(0, -1)
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    if (c === '(') {
      count++
    } else {
      count--
      // only check when it is a closing
      if (map.has(count)) {
        max = Math.max(max, i - map.get(count))
      }
    }
    const next = s[i + 1]
    const isLocalMinimum = c === ')' && next === '('
    // !!! don't record on a minimum if already have it
    if (isLocalMinimum && map.has(count)) {
      continue
    } else {
      map.set(count, i)
    }
  }
  return max
};
console.log(longestValidParentheses('(()') === 2)
console.log(longestValidParentheses(')()())') === 4)
// 数形结合, with the help of Geometry
// accumulation array for range query

sicilianee 发表于 2018-5-12 12:21
0511 2.  Longest Valid Parentheses

/**

Many other solutions, checkout the writeup.

0512 1.  Reaching Points

/**
* @param {number} sx
* @param {number} sy
* @param {number} tx
* @param {number} ty
* @return {boolean}
*/
var reachingPoints = function(sx, sy, tx, ty) {
  const isRight = () => tx === sx && ty === sy
  const isWrong = () => tx < sx || ty < sy
  while (!isRight() && !isWrong()) {
    if (sx !== tx && sy !== ty) {
      if (tx > ty) {
        const n = Math.ceil(tx / ty) - 1
        tx = tx - n * ty
      } else if (tx < ty) {
        const n = Math.ceil(ty / tx) - 1
        ty = ty - n * tx
      } else {
        if (sx === 0) { // if equal, one of the target must be 0
          tx = 0
        } else {
          ty = 0
        }
      }
    } else {
      if (tx === sx) {
        const cond1 = tx !== 0
        const cond2 = (ty - sy) % tx === 0
        return cond1 && cond2
      } else {
        const cond1 = ty !== 0
        const cond2 = (tx - sx) % ty === 0
        return cond1 && cond2
      }
    }
  }
  return isRight()
};

// 1. 两方都不等，就必须一直减大的直到攻守易势，否则小的永远不可能等， 自己相等是一种特殊情况
// 2. 像这种两个branch很相似，但是细节又很麻烦，在一些细节的地方不同，实际操作中最好不要一开始上来
// 就统一。先用最原始的分情况的方式写，写完以后看需不需要重构。DRY在重构的时候再考虑。



console.log(reachingPoints(1, 1, 3, 5) === true)
console.log(reachingPoints(1, 1, 2, 2) === false)
console.log(reachingPoints(1, 1, 1, 1) === true)

sicilianee 发表于 2018-5-13 02:17
0512 1.  Reaching Points

/**

Because they both start from 1, not 0, the code could be greatly simplified. Checkout the writeup or other posts. In particular, we could terminate equal case early and use % instead of calculating manually and worrying about ceiling or floor.

0514 1. Integer to English Words


/**
* @param {number} num
* @return {string}
*/
var numberToWords = function(num) {
  const map = new Map([
    [1000000000, 'Billion'],
    [1000000, 'Million'],
    [1000, 'Thousand'],
    [1, ''],
  ])
  const keys = [...map.keys()]
  const parts = []
  for (const base of keys) {
    const unit = map.get(base)
    const count = Math.trunc(num / base)
    if (count > 0) {
      parts.push(`${getCountStr(count)} ${unit}`.trim())
    }
    num = num % base
  }

  const str = parts.filter(str => str).join(' ')
  return str ? str : 'Zero'


  function getCountStr (count) {
    let hundredStr = ''
    let tensStr = ''
    let unitsStr = ''

    const numHundred = Math.trunc(count / 100)
    if (numHundred > 0) {
      hundredStr = `${getSingle(numHundred)} Hundred`
    }

    let numRemain = count % 100
    if (numRemain >= 20) {
      const numTens = Math.trunc(numRemain / 10)
      tensStr = getTens(numTens)
      numRemain = numRemain % 10
    }

    if (numRemain > 0) {
      unitsStr = getSingle(numRemain)
    }

    return [hundredStr, tensStr, unitsStr].filter(str => str).join(' ')
  }

};

function getTens (num) {
  const dict = {
    2: 'Twenty',
    3: 'Thirty',
    4: 'Forty',
    5: 'Fifty',
    6: 'Sixty',
    7: 'Seventy',
    8: 'Eighty',
    9: 'Ninety'
  }
  return dict[num]
}

function getSingle (num) {
  const str = 'Zero,One,Two,Three,Four,Five,Six,Seven,Eight,Nine,Ten,Eleven,Twelve,Thirteen,Fourteen,Fifteen,Sixteen,Seventeen,Eighteen,Nineteen'
  const nums = str.split(',')
  const dict = {}
  nums.forEach((num, index) => {
    dict[index] = num
  })
  return dict[num]
}

// trick: push to an array in order and filter on that array and join.
// TODO: use associative arrays instead of a map, that would be shorter


console.log(numberToWords(123))
console.log(numberToWords(12345))
console.log(numberToWords(1234567))

0514 2. Sum of Distances in Tree

/**
* @param {number} N
* @param {number[][]} edges
* @return {number[]}
*/
var sumOfDistancesInTree = function(N, edges) {
  const sums = Array(N).fill(0)
  const counts = Array(N).fill(0)
  const adj = Array(N).fill().map(() => [])
  const reEdges = edges.map(([a, b]) => [b, a]) // !!! typoish for map array destruct
  edges = [...edges, ...reEdges] // !!! typoish for spread
  edges.forEach(([a, b]) => {
    adj[a].push(b)
  })
  sums[0] = dfs(0, -1)
  // !!! think about this: DRY initial iteration
  // put this extra loop into the dfs? know self, calc each child.
  adj[0].forEach(child => calcSums(child, 0))
  return sums

  function calcSums (node, parent) {
    const toSubtract = counts[node]
    const toAdd = N - counts[node]
    sums[node] = sums[parent] + toAdd - toSubtract
    const children = adj[node].filter(child => child !== parent)
    children.forEach(child => {
      calcSums(child, node)
    })
  }

  // 1. calc counts
  // 2. sum up
  function dfs (node, parent) {
    let sum = 0
    counts[node] = 1
    const children = adj[node].filter(child => child !== parent)
    children.forEach(child => {
      sum += dfs(child, node) + counts[child] // !!! and the counts[child]
      counts[node] += counts[child]
    })
    return sum
  }
};

console.log(sumOfDistancesInTree(6, [[0,1],[0,2],[2,3],[2,4],[2,5]]))