记录

sicilianee 发表于 2018-6-10 07:05
Key is:

1. read the requirement, they allow error, not exact, consider binary search

有一个很变态的O(n)的解法，数形结合，应用lower convext hull的一些性质。

0610 1. Rectangle Area II

/**
* @param {number[][]} rectangles
* @return {number}
*/
var rectangleArea = function(rectangles) {
  // discretize points, build a map from points to compressed points
  // convert rects to new coordinate system
  // convert rects to area points
  // create an area board
  // for each rect, put into the board and mark it
  // after all, iterate and get all area points and translate into real areas

  const mod = Math.pow(10, 9) + 7
  const xSet = new Set()
  const ySet = new Set()
  rectangles.forEach(([x1, y1, x2, y2]) => {
    // !!!! set cannot add two same time
    xSet.add(x1); xSet.add(x2)
    ySet.add(y1); ySet.add(y2)
  })
  // from index to points // !!! NEED TO SORT FOR COMPRESSION/ DISCRETIZATION
  const xPoints = [...xSet].sort((a, b) => a - b)
  const yPoints = [...ySet].sort((a, b) => a - b)
  // from points to index
  const xMap = new Map(xPoints.map((val, index) => [val, index]))
  const yMap = new Map(yPoints.map((val, index) => [val, index]))
  // index rects
  const rects = rectangles.map(([x1, y1, x2, y2]) => [xMap.get(x1), yMap.get(y1), xMap.get(x2), yMap.get(y2)])
  // index area board, init empty
  const area = Array(xPoints.length - 1).fill()
    .map(() => Array(yPoints.length - 1).fill(false))
  // put rect to board
  for (const [x1, y1, x2, y2] of rects) {
    for (let x = x1; x < x2; x++) {
      for (let y = y1; y < y2; y++) {
        area[x][y] = true
      }
    }
  }
  // you can actually restore point by point, no need to care about areas
  let res = 0
  for (let x = 0 ; x < xPoints.length - 1; x++) {
    for (let y = 0; y < yPoints.length - 1; y++) {
      if (area[x][y]) {
        // restore the area this point represents
        const dx = xPoints[x + 1] - xPoints[x]
        const dy = yPoints[y + 1] - yPoints[y]
        res = (res + (dx * dy) % mod) % mod
      }
    }
  }
  return res
};

console.log(rectangleArea([[0,0,2,2],[1,0,2,3],[1,0,3,1]]) === 6)
console.log(rectangleArea([[0,0,1000000000,1000000000]]) === 49)
console.log(rectangleArea([[0,0,2,2],[1,1,3,3]]) === 7)

sicilianee 发表于 2018-6-11 06:24
0610 1. Rectangle Area II

/**

Index compression / discretization.

sicilianee 发表于 2018-6-11 06:29
Index compression / discretization.

That one is N**3
Further:
N**2logN
NlogN

Check the write up. Sweep line and Segment tree.

0611 1. Best Time to Buy and Sell Stock IV


/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
  if (prices.length === 0) {return 0}
  // !!! an optimization you have to make for some inputs.
  // we assume you don't buy and sell on the same day because that is not going to make any difference on the final result
  // so if k is bigger than half the number of days, we can just asssume we can make any number of transactions
  if (Math.trunc(prices.length / 2) <= k) {
    return freeProfit(prices)
  }
  // pre day
  let buy = Array(k + 1).fill(-prices[0]) // -prices[0], not pirces[0]
  let sell = Array(k + 1).fill(0)
  for (const price of prices) {
    const newBuy = Array(k + 1).fill(0)
    const newSell = Array(k + 1).fill(0)
    for (let i = 0; i <= k; i++) {
      newBuy[i] = Math.max(sell[i] - price, buy[i])
      newSell[i] = i === 0 ? 0 : Math.max(buy[i - 1] + price, sell[i])
    }
    buy = newBuy
    sell = newSell
  }
  return Math.max(...sell)
};

function freeProfit (prices) {
  let res = 0
  for (let i = 1; i < prices.length; i++) {
    const diff = prices[i] - prices[i - 1]
    res += diff > 0 ? diff : 0
  }
  return res
}

sicilianee 发表于 2018-6-12 14:53
0611 1. Best Time to Buy and Sell Stock IV

If num of days < K, values after the possible date would be same as the last one.

0612 1. Read N Characters Given Read4

As a preparation for the follow up one. To understand what the problem is about.

/**
* Definition for read4()
*
* @param {character[]} buf Destination buffer
* @return {number} The number of characters read
* read4 = function(buf) {
*     ...
* };
*/

/**
* @param {function} read4()
* @return {function}
*/
var solution = function(read4) {
    /**
     * @param {character[]} buf Destination buffer
     * @param {number} n Maximum number of characters to read
     * @return {number} The number of characters read
     */
    return function(buf, n) {
        if (n <= 0) {return 0}
        const doCount = Math.ceil(n / 4)
        let len = 0
        for (let i = 0; i < doCount; i++) {
            const tmp = []
            len += read4(tmp)
            buf.push(...tmp)
        }
        const minCount = Math.min(len, n)
        const popCount = len - minCount
        for (let i = 0; i < popCount; i++) {
            buf.pop()
        }
        return minCount
    };
};

In a word, the buf is the destination buf; user passes it to your function and you fill the buf with chars you read. That is, you modify the input. Very strange  but if you study the function signature a bit you should understand what it means.

0612 2. Read N Characters Given Read4 II - Call multiple times

Feels strange to do this in js

/**
* Definition for read4()
*
* @param {character[]} buf Destination buffer
* @return {number} The number of characters read
* read4 = function(buf) {
*     ...
* };
*/

/**
* @param {function} read4()
* @return {function}
*/
var solution = function(read4) {
    /**
     * @param {character[]} buf Destination buffer
     * @param {number} n Maximum number of characters to read
     * @return {number} The number of characters read
     */
    let cache = []
    return function(buf, n) {
        if (n <= 0) {return 0}
        const needCount = n - cache.length
        if (needCount > 0) {
            const doCount = Math.ceil(needCount / 4)
            for (let i = 0; i < doCount; i++) {
                const tmp = []
                read4(tmp)
                cache.push(...tmp)
            }
        }
        const minCount = Math.min(cache.length, n)
        buf.push(...cache.slice(0, minCount))
        cache = cache.slice(minCount)
        return minCount
    };
};

0613 1. Decode Ways II


stackoverflow == :


/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
  if (!s) {
    return 0
  }
  const map = new Map()
  const len = s.length
  const res = conquer(0)
  return res

  // from index i (inclusive), to the end, the count
  function conquer (i) {
    if (i >= len) {
      // !!! ends normal, is a valid end, should return 1 instead of 0
      return 1
    }
    if (map.has(i)) {
      return map.get(i)
    }
    // get the first char list
    const first = []
    const second = []
    const c = s[i]
    if (c === '0') {
      return 0
    } else if (c === '*') {
      for (let i = 1; i <= 9; i++) {
        first.push(String(i))
      }
    } else {
      first.push(c)
    }
    let res = 0
    // just use a single char
    res += conquer(i + 1) * first.length
    // get the second char list
    if (i + 1 <= len) {
      if (s[i + 1] === '*') {
        for (let i = 1; i <= 9; i++) {
          second.push(String(i))
        }
      } else {
        const digit = Number.parseInt(s[i + 1], 10)
        if (digit <= 6) {
          second.push(digit)
        }
      }
    }
    // try using both chars
    for (const c of first) {
      if (['1', '2'].includes(c)) {
        // 10, 11 - 19
        // 20, 21 - 26
        for (const sc of second) {
          const str = c + sc
          const numStr = Number.parseInt(str, 10)
          if (numStr <= 26) {
            res += conquer(i + 2)
          }
        }
      }
    }
    // after all, cache
    map.set(i, res)
    return res
  }
};

sicilianee 发表于 2018-6-14 12:42
0613 1. Decode Ways II

One thing you missed is the mod, which means it could be pretty big.