记录

0516 1. Substring with Concatenation of All Words

/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
  if (s == null || s.length === 0 || words == null || words.length === 0) {
    return []
  }
  const sLen = s.length
  const totalWordsLen = words.length * words[0].length
  if (totalWordsLen > sLen) {
    return []
  }
  // start
  const map = new Map()
  words.forEach(word => {
    const count = map.get(word) || 0
    map.set(word, count + 1)
  })
  const res = []
  const wLen = words[0].length
  let k = words.length
  for (let i = 0; i < s.length; i++) {
    const usedMap = new Map()
    let count = 0
    while (count < k && i + (count + 1) * wLen <= s.length) {
      const j = i + count * wLen
      const curr = s.slice(j, j + wLen)
      const usedCount = usedMap.get(curr) || 0 // !!! could be 0, can't directly put in the comparision
      if (map.has(curr) && map.get(curr) > usedCount) {
        const val = usedMap.get(curr) || 0
        usedMap.set(curr, val + 1)
        count++
      } else {
        break
      }
    }
    if (count === k) {
      res.push(i)
    }
  }
  return res
};

NOTE: could have duplicates, so use map instead of set.

0519 1. Bricks Falling When Hit

class DisjointSet {
  constructor (n) {
    this.parent = Array(n).fill(-1)
  }
  union (x, y) {
    let xRoot = this.find(x)
    let yRoot = this.find(y)
    // !!! important
    if (xRoot === yRoot) {
      return
    }
    const xSize = this.getSize(xRoot)
    const ySize = this.getSize(yRoot)
    if (xSize > ySize) {
      ;[xRoot, yRoot] = [yRoot, xRoot]
    }
    // !!! tricky, order matters if you use root parent to represent size.
    // you must reassign root after you calc size
    this.parent[yRoot] = this.parent[yRoot] + this.parent[xRoot]
    this.parent[xRoot] = yRoot
  }
  getSize (root) {
    return -this.parent[root]
  }
  find (x) {
    // !!!! this few lines are tricky
    // and you can't simply turn it into a while loop because you need the calc'd value to set parent, that effectively require a stack for the bottom up part
    if (this.parent[x] < 0) {
      return x
    }
    this.parent[x] = this.find(this.parent[x])
    return this.parent[x]
  }
}
/**
* @param {number[][]} grid
* @param {number[][]} hits
* @return {number[]}
*/
var hitBricks = function(grid, hits) {
  // grid and hits
  // we'll copy the grid, apply the hits, get a final grid
  // normalize that grid into one demension. Add a dummy root. Build a forest from that grid.
  // backwards on that final one, apply the hits, only when there is a brick in the original one
  // apply it, union any side it touches
  // each time we calc the delta size of root
  // in the end just reverse the array we have and return
  if (hits == null || hits.length === 0) {
    return []
  }
  if (grid == null || grid.length === 0 || grid[0].length === 0) {
    return hits.map(i => 0)
  }
  const aGrid = grid.map(row => row.map(el => el))
  hits.forEach(([i, j]) => aGrid[i][j] = 0)
  // just use the total size of the array? lots of unused items, 0s
  // or build a two-way mapping?
  const rowLen = grid.length
  const colLen = grid[0].length
  const size = rowLen * colLen
  const dSet = new DisjointSet(size + 1) // !!! + 1 because we added one more node
  const getNode = (i, j) => colLen * i + j
  const getIndices = node => [Math.trunc(node / colLen), node % colLen]
  const top = size
  // connect top
  for (let j = 0; j < colLen; j++) {
    if (aGrid[0][j] === 1) {
      dSet.union(getNode(0, j), top)
    }
  }
  // connect any
  const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      const node = getNode(i, j)
      if (aGrid[i][j] === 1) {
        for (const [dx, dy] of moves) {
          const x = i + dx
          const y = j + dy
          if (x >= 0 && x < rowLen && y >= 0 && y < colLen && aGrid[x][y] === 1) {
            dSet.union(node, getNode(x, y))
          }
        }
      }
    }
  }
  // apply one by one backwards
  const res = []
  const getTopSize = () => {
    const root = dSet.find(top)
    return dSet.getSize(root)
  }
  let prevSize = getTopSize() // !!! pre is before an operation, prev is previous, different. Use the right word
  hits = hits.reverse()
  for (const [i, j] of hits) {
    if (grid[i][j] === 1) {
      aGrid[i][j] = 1
      const node = getNode(i, j)
      // top
      if (i === 0) {
        dSet.union(node, top)
      }
      // four directions
      for (const [dx, dy] of moves) {
        const [x, y] = [i + dx, j + dy]
        if (x >= 0 && x < rowLen && y >= 0 && y < colLen && aGrid[x][y] === 1) {
          dSet.union(node, getNode(x, y))
        }
      }
      // get new top size and get delta
      const size = getTopSize()
      const delta = Math.max(0, size - prevSize - 1)
      res.push(delta)
      prevSize = size
    } else { // !!!! don't omit the else, else you have missing points
      res.push(0)
    }
  }
  res.reverse()
  return res
};


const grid = [[1,0,0,0],[1,1,1,0]]
const hits = [[1,0]]
console.log(hitBricks(grid, hits))

console.log(hitBricks([[1,0,0,0],[1,1,0,0]], [[1,1],[1,0]]))

0519 2. Wildcard Matching

/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
  if (s == null || p == null) {
    return false
  }
  const sLen = s.length
  const pLen = p.length
  const set = new Set()
  const getKey = (i, j) => `${i}_${j}`
  return doMatch(0, 0)


  function doMatch (i, j) {
    const key = getKey(i, j)
    if (set.has(key)) {
      return false
    }
    if (i === sLen && j === pLen) {
      return true
    }
    if (j >= pLen) {
      return false
    }
    const cs = s[i] // could be undefined
    const cp = p[j]
    if (cp === '*') {
      const remainLen = sLen - i
      for (let matchLen = 0; matchLen <= remainLen; matchLen++) {
        if (doMatch(i + matchLen, j + 1)) {
          return true
        }
      }
    } else {
      const matched = (cp === '?' && cs != undefined) || (cs === cp)
      if (matched && doMatch(i + 1, j + 1)) {
        return true
      }
    }
    set.add(key)
    return false
  }

};


停止条件部分挺tricky的。

sicilianee 发表于 2018-5-20 08:14
0519 2. Wildcard Matching

/**

sure they'll have dp solution for this.
The most voted answer even have an iterative version of the dfs. But no need to have a stack, just a index var and go backwards for *.

0519 3. Reverse Pairs

/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
  if (nums == null || nums.length === 0) {
    return 0
  }
  return mergeSortCount(0, nums.length - 1)

  function mergeSortCount (i, j) {
    if (i === j) {
      return 0
    }
    // sort, merge and calc count
    const mid = i + Math.trunc((j - i) / 2)
    const count1 = mergeSortCount(i, mid)
    const count2 = mergeSortCount(mid + 1, j)
    // i - mid, mid + 1 - j
    let count = count1 + count2
    const size = j - i + 1
    // now we do two rounds of comparision: one for counting, one for merging
    // count: ends when any side ends
    let p1 = i
    let p2 = mid + 1
    while (p1 <= mid && p2 <= j) {
      const [v1, v2] = [nums[p1], nums[p2]]
      if (v1 > 2 * v2) {
        count += mid + 1 - p1
        p2++
      } else {
        p1++
      }
    }
    // merge: ends when both sides end
    p1 = i
    p2 = mid + 1
    const arr = Array(size)
    for (let k = 0; k < size; k++) {
      const v1 = p1 > mid ? Infinity : nums[p1]
      const v2 = p2 > j ? Infinity : nums[p2]
      if (v1 < v2) {
        arr[k] = v1
        p1++
      } else {
        arr[k] = v2
        p2++
      }
    }
    // copy back sorted array
    for (let k = 0; k < size; k++) {
      nums[i + k] = arr[k]
    }
    return count
  }
};

sicilianee 发表于 2018-5-20 10:55
0519 3. Reverse Pairs

/**

Other solutions, bit, bst, check them out. But how to solve it using segment tree?

sicilianee 发表于 2018-5-20 10:58
Other solutions, bit, bst, check them out. But how to solve it using segment tree?

segment tree:
https://stackoverflow.com/questi ... using-segment-trees
first init seg tree with 0s. sort the array but keep the index. insert elements into original index into the backing array of seg tree, and query before each insert. sum all the queries up for the total value.

0520 1. Similar String Groups

class DisjointSet {
  constructor (size) {
    this.parent = Array(size).fill(-1)
  }
  find (x) { // path compression
    if (this.parent[x] < 0) {
      return x
    } else {
      this.parent[x] = this.find(this.parent[x])
      return this.parent[x]
    }
  }
  union (x, y) { // rank by size
    let xRoot = this.find(x)
    let yRoot = this.find(y)
    if (xRoot === yRoot) { // !!!! very important, you hit it !!!
      return
    }
    const xSize = -this.parent[xRoot]
    const ySize = -this.parent[yRoot]
    // assume x is smaller
    if (xSize > ySize) {
      ;[xRoot, yRoot] = [yRoot, xRoot]
    }
    // attach x to y
    this.parent[yRoot] += this.parent[xRoot]
    this.parent[xRoot] = yRoot
  }
}

/**
* @param {string[]} A
* @return {number}
*/
var numSimilarGroups = function(A) {
  if (A == null || A.length === 0) {
    return 0
  }
  const n = A.length
  const k = A[0].length
  const dSet = new DisjointSet(n)
  if (n > k * k) {
    // loop k
    // we assume no duplicate
    const map = new Map(A.map((val, index) => [val, index]))
    // !!!! ATTENTION: entries() method return [key, value], not [value, key].
    // forEach, map, reduce, filter gives you (value, key) as parameter.
    // when you convert from `for(const val of arr)` into `for (const [index, val] of arr.entries())`, be cautious!!!
    for (const [index, str] of A.entries()) {
      const chars = [...str]
      for (let i = 0; i < chars.length; i++) {
        for (let j = i + 1; j < chars.length; j++) {
          swap(chars, i, j)
          const nStr = chars.join('')
          swap(chars, i, j)
          if (map.has(nStr)) {
            dSet.union(map.get(nStr), index)
          }
        }
      }
    }
  } else {
    // loop n
    for (let i = 0; i < n; i++) {
      for (let j = i + 1; j < n; j++) {
        if (isSimilar(A[i], A[j])) {
          dSet.union(i, j) // add all edges
        }
      }
    }
  }
  // count how many trees are there
  const set = new Set()
  for (let i = 0; i < A.length; i++) {
    set.add(dSet.find(i))
  }
  return set.size
};

function swap (arr, i, j) {
  ;[arr[i], arr[j]] = [arr[j], arr[i]]
}

// 1. i don't think their solution considered dups
// 2. if no dup, could just use a diff counter and check diff <=2 (even diff === 2), check their solution.
// cause 2 is the smallest diff you could ever have (0 is dup, 1 is not possible as all are anagrams)
function isSimilar (str1, str2) {
  const diff = []
  for (let i = 0; i < str1.length; i++) {
    if (str1[i] !== str2[i]) {
      diff.push(i)
    }
  }
  if (diff.length !== 2) {
    return false
  }
  const [left, right] = diff
  return str1[left] === str2[right] && str1[right] === str2[left]
}

0522 1. Split Array With Same Average

class Fraction {
  constructor (x, y) {
    if (y === 0) {
      throw new Error('cannot be 0')
    }
    if (x === 0) {
      this.x = 0
      this.y = 1
    } else {
      const aGcd = safeGcd(x, y)
      this.x = x / aGcd
      this.y = y / aGcd
    }
  }
  getKey () {
    return `${this.x}_${this.y}`
  }
}

const add = (frac1, frac2) => {
  const newX = frac1.x * frac2.y + frac2.x * frac1.y
  const newY = frac1.y * frac2.y
  return new Fraction(newX, newY)
}

const subtract = (frac1, frac2) => {
  frac2 = new Fraction(-frac2.x, frac2.y)
  return add(frac1, frac2)
}

// assume both positive
function gcd (a, b) {
  return a % b === 0 ? b : gcd(b, a % b)
}

function safeGcd (a, b) {
  a = Math.abs(a)
  b = Math.abs(b)
  if (a === 0 || b === 0) {
    throw new Error('Cannot be 0')
  }
  return gcd(a, b)
}

/**
* @param {number[]} A
* @return {boolean}
*/
var splitArraySameAverage = function(A) {
  if (A == null || A.length < 2) {
    return false
  }
  const sum = A.reduce((a, b) => a + b)
  const avg = new Fraction(sum, A.length)
  const fracs = A.map(el => subtract(new Fraction(el, 1), avg))
  // !!! you used the wrong mid, possible one array is empty another is the full set
  // then the other has 0 would not count
  // (len - 1) / 2 not len / 2
  const mid = Math.trunc((fracs.length - 1 ) / 2)
  const fracs1 = fracs.slice(0, mid + 1)
  const fracs2 = fracs.slice(mid + 1)
  // use map as a set for objects for faster lookup from key since js doesn't have value comparision for set
  const createSumMap = (fracs) => {
    const map = new Map()
    for (const curr of fracs) {
      const existing = [...map.values()]
      map.set(curr.getKey(), curr)
      for (const ex of existing) {
        const next = add(ex, curr)
        map.set(next.getKey(), next)
      }
      if (map.has(`0_1`)) {
        return null
      }
    }
    return map
  }
  const map1 = createSumMap(fracs1)
  if (!map1) {
    return true
  }
  const map2 = createSumMap(fracs2)
  if (!map2) {
    return true
  }
  const sum1 = fracs1.reduce(add)
  const sum2 = fracs2.reduce(add)
  for (const [key, val] of map1) {
    const negate = new Fraction(-val.x, val.y)
    if (map2.has(negate.getKey()) && !(sum1.getKey() === key && sum2.getKey() === negate.getKey())) {
      return true
    }
  }
  return false
};



很多很纠结的地方这道题。 有一些是decision to make, 有一些是用js很不方便的地方，比如object set (in which case just use map), 有一些是general的比如want early termination but has duplicate code and need to wrap the loop inside a function which has a meaningful return value.

0522. 2. Text Justification

/**
* @param {string[]} words
* @param {number} maxWidth
* @return {string[]}
*/
var fullJustify = function(words, maxWidth) {
  if (words == null || words.length === 0) {
    return []
  }
  // walk through all the words one by one
  // create a line array
  // push into line one by one, and keep a counter of length
  // while adding next word would not overflow, add it and continue
  // else, finished one line
  // if is last line meaning no more words, just simply join them and add to res
  // else calc remaining spaces, and get floor of distribute value, and remaining,
  // then create an array of num representing spaces, and distribute remaining to the nums
  // then take turns adding str and space
  //
  // !!!! 最后多一个题型, 然而这个比较幸运最后一个总是多出来，而且和前面的处理不一样，没有重复。
  let i = 0
  const res = []
  let count = 0
  let line = []
  while (i < words.length) {
    const word = words[i]
    const nextLen = count === 0 ? word.length : word.length + 1
    if (count + nextLen <= maxWidth) {
      line.push(word)
      count += nextLen
      i++
    } else {
      // !!!! 1. always provide default otherwise error for empty array
      // 2. not a.length + b.length, you'll see if you provided default
      const spaceCount = maxWidth - line.reduce((sum, curr) => sum + curr.length, 0)
      if (line.length === 1) {
        const space = ' '.repeat(spaceCount)
        res.push(line[0] + space)
      } else {
        const size = line.length - 1
        const numEach = Math.trunc(spaceCount / size)
        const remain = spaceCount - numEach * size
        const nums = Array(size).fill(numEach)
        for (let i = 0; i < remain; i++) {
          nums[i]++
        }
        const spaces = nums.map(num => ' '.repeat(num))
        const parts = [line[0]]
        for (let i = 0; i < spaces.length; i++) {
          parts.push(spaces[i] + line[i + 1]) // !!! here space first word second
        }
        res.push(parts.join(''))
      }
      // !!!! these two shall be outside of the if else, otherwise infinite loop
      // 典型
      line = []
      count = 0
    }
  }
  // last line
  if (line.length > 0) {
    const half1 = line.join(' ')
    const remain = maxWidth - half1.length
    res.push(half1 + ' '.repeat(remain))
  }
  return res
};

// --- test
let val
let res
val = fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16)
console.log(val.join() === [
   "This    is    an",
   "example  of text",
   "justification.  "
].join()
)

val = fullJustify(["What","must","be","acknowledgment","shall","be"], 16)
res = [
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
console.log(val.join() === res.join())

val = fullJustify(["Science","is","what","we","understand","well","enough","to","explain",
         "to","a","computer.","Art","is","everything","else","we","do"], 20)
res = [
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]
console.log(val.join() === res.join())