记录

f*** they have an O(logn) solution. 矩阵快速幂优化.
https://leetcode.com/problems/student-attendance-record-ii/discuss/101633/Improving-the-runtime-from-O(n)-to-O(log-n)?page=1

Skip for now, mark the code for reference:
final int MOD = 1000000007;
final int M = 6;

int[][] mul(int[][] A, int[][] B) {
    int[][] C = new int[M][M];
    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < M; k++)
                C[i][j] = (int) ((C[i][j] + (long) A[i][k] * B[k][j]) % MOD);
    return C;
}


int[][] pow(int[][] A, int n) {
    int[][] res = new int[M][M];
    for (int i = 0; i < M; i++)
        res[i][i] = 1;
    while (n > 0) {
        if (n % 2 == 1)
            res = mul(res, A);
        A = mul(A, A);
        n /= 2;
    }
    return res;
}

public int checkRecord(int n) {
    int[][] A = {
            {0, 0, 1, 0, 0, 0},
            {1, 0, 1, 0, 0, 0},
            {0, 1, 1, 0, 0, 0},
            {0, 0, 1, 0, 0, 1},
            {0, 0, 1, 1, 0, 1},
            {0, 0, 1, 0, 1, 1},
    };
    return pow(A, n + 1)[5][2];
}

0602 1. Sliding Window Median

// use two treeSets nlogk, use two heaps nlogn.
// use heaps: either keep a reference/flag for parent on node, or swap on equal
// or: like writeup, use hashmap. Essentially also swap
class Heap {
  constructor (data, customCompare) {
    this.data = data
    this.compare = (i, j) => customCompare(this.data[i], this.data[j])
    const lastParent = this.getParent(this.size - 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]]
  }
  siftUp (i) {
    const parent = this.getParent(i) // 0 -> 0
    if (this.compare(i, parent) < 0) {
      this.swap(i, parent)
      this.siftUp(parent)
    }
  }
  siftDown (i) {
    let min = i
    const left = 2 * i + 1
    const right = 2 * i + 2
    ;[left, right].forEach(index => {
      if (index < this.size && this.compare(index, min) < 0) {
        min = index
      }
    })
    if (min !== i) {
      this.swap(min, i)
      this.siftDown(min)
    }
  }
  push (val) {
    this.data.push(val)
    this.siftUp(this.size - 1)
  }
  pop () {
    if (this.size === 0) {
      return undefined
    }
    const val = this.top
    this.swap(this.size - 1, 0)
    this.data.pop()
    this.siftDown(0)
    return val
  }
  get size () {
    return this.data.length
  }
  get top () { // peek
    // !!!! is data[0], not data[this.size - 1], is the top not the last
    return this.data[0]
  }
}

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var medianSlidingWindow = function(nums, k) {
  const nodes = nums.map(num => ({val: num, valid: true}))
  const big = new Heap([], (a, b) => a.val - b.val)
  const small = new Heap([], (a, b) => b.val - a.val)
  for (let i = 0; i < k; i++) {
    big.push(nodes[i])
  }
  for (let i = 0; i < Math.trunc(k / 2); i++) {
    small.push(big.pop())
  }
  const res = []
  const isEven = k % 2 === 0
  const calcMedian = () => {
    if (isEven) {
      res.push((big.top.val + small.top.val) / 2)
    } else {
      res.push(big.top.val)
    }
  }
  calcMedian()
  // @trap又遇到了这个loop多一个怎么处理的问题了。找不到好的办法，只好extract函数来dedup了。
  // !! 首先要保证一开始是balance的
  for (let i = k; i < nums.length; i++) {
    let balance = 0
    const toAdd = nodes[i]
    const toRemove = nodes[i - k]
    // add
    if (toAdd.val >= big.top.val) {
      big.push(toAdd)
      balance++
    } else {
      small.push(toAdd)
      balance--
    }
    // remove
    if (toRemove.val > big.top.val) {
      toRemove.valid = false
      balance--
    } else if (toRemove.val < big.top.val) {
      toRemove.valid = false
      balance++
    } else { // value equal, remove big.top instead of toRemove because we don't know exactly wher toRemove is
      big.top.valid = false
      balance--
    }
    // rebalance
    if (balance > 0) {
      small.push(big.pop())
    } else if (balance < 0) {
      big.push(small.pop())
    }
    // flush
    while (big.size > 0 && !big.top.valid) {
      big.pop()
    }
    while (small.size > 0 && !small.top.valid) {
      small.pop()
    }

    // calc
    calcMedian()
  }
  return res
};

0602 2. Best Time to Buy and Sell Stock III

// 思考的过程还是很痛苦的，不过有可以借鉴的地方。
// 1. divide conquer时候注意子问题要是子问题，不能子问题包含自身，没有缩小范围反而扩大了，就变成死循环了
// 2. 关键就在与divide的时候注意转化后问题的特性，会有新的与原问题不同的特性，这个特性有可能将范围缩小了，这样就能够实现divide了
//    比如在这里这个特性就是最大上升序列的开头就是min，结尾就是max

/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
  // use biggest
  const [start, end, val] = getBiggestSequence(0, prices.length - 1, true)
  if (val === 0) { // no increasing
    return 0
  }
  const [, , leftVal] = getBiggestSequence(0, start - 1, true)
  const [, , rightVal] = getBiggestSequence(end + 1, prices.length - 1, true)

  // break biggest
  const [decS, decE, decVal] = getBiggestSequence(start, end, false)


  return Math.max(val + leftVal, val + rightVal, val + decVal)


  function getBiggestSequence (start, end, isIncrease) {
    // !!! be explicit, keep it simple. Rather duplicate code then refactor, don't
    // do complex if/else/branch logic
    // 先分开写，在看能否合并
    if (isIncrease) {
      let min = start // same as below
      let [resStart, resEnd, res] = [start, start, 0] // !!! start from start not 0
      for (let i = start; i <= end; i++) {
        if (prices[i] - prices[min] > res) {
          resStart = min
          resEnd = i
          res = prices[resEnd] - prices[resStart] // !end - start
        }
        if (prices[i] <= prices[min]) {
          min = i
        }
      }
      return [resStart, resEnd, res]
    } else {
      let max = start // same
      let [resStart, resEnd, res] = [start, start, 0] // !!! start from start
      for (let i = start; i <= end; i++) {
        if (prices[max] - prices[i] > res) {
          resStart = max
          resEnd = i
          res = prices[resStart] - prices[resEnd]
        }
        if (prices[i] >= prices[max]) {
          max = i
        }
      }
      return [resStart, resEnd, res]
    }
  }

};

// test

console.log(maxProfit([3,3,5,0,0,3,1,4]) === 6)
console.log(maxProfit([1,2,3,4,5]) === 4)
console.log(maxProfit([7,6,4,3,1]) === 0)

已经知道解法，写起来错误还是很多，捉急

sicilianee 发表于 2018-6-3 11:39
0602 2. Best Time to Buy and Sell Stock III

// 思考的过程还是很痛苦的，不过有可以借鉴的地方。

check the dp based solution. That is better.

0603 1. Course Schedule III

class Heap {
  constructor (data, customCompare) {
    this.data = data
    this.compare = (i, j) => customCompare(this.data[i], this.data[j])
    const lastParent = this.getParent(this.size - 1)
    for (let i = lastParent; i >= 0; i--) {
      this.siftDown(i)
    }
  }
  swap (i, j) {
    ;[this.data[i], this.data[j]] = [this.data[j], this.data[i]]
  }
  getParent (i) {
    return Math.trunc((i - 1) / 2)
  }
  get size () {
    return this.data.length
  }
  get top () {
    return this.data[0]
  }
  push (val) {
    this.data.push(val)
    this.siftUp(this.size - 1)
  }
  pop () {
    if (this.size === 0) {
      return undefined
    }
    const val = this.top
    this.swap(0, this.size - 1)
    this.data.pop()
    this.siftDown(0)
    return val
  }
  siftUp (i) {
    const parent = this.getParent(i) // 0 -> 0
    if (this.compare(i, parent) < 0) {
      this.swap(i, parent)
      this.siftUp(parent)
    }
  }
  siftDown (i) {
    let min = i
    const left = 2 * i + 1
    const right = 2 * i + 2
    for (let index of [left, right]) {
      if (index < this.size && this.compare(index, min) < 0) {
        min = index
      }
    }
    if (min != i) {
      this.swap(min, i)
      this.siftDown(min)
    }
  }
}




var scheduleCourse = function(courses) {
  // [time, end]
  //  build a heap
  // sort input based on end time
  // add one by one, to the pq, ordered by duration
  // we track total time
  // if we can add, add
  // if we cannot, add, remove top (if it won't work, itself will be popped, so it is guaranteed to work)
  const heap = new Heap([], (a, b) => b - a)
  courses.sort((a, b) => a[1] - b[1])
  let totalTime = 0
  courses.forEach(([time, end]) => {
    heap.push(time)
    totalTime += time
    if (totalTime > end) {
      const toRemove = heap.pop()
      totalTime -= toRemove
    }
  })
  return heap.size
};

// Key points
// 1. one rule: if two courses are __both taken__, we can always put the one with earlier
//    ends time before. Means it is always good to take the earlier end courses first
//    if we are going to take both courses.
//    (if reversed, you could always swap to the right order; but if already in right order you cannot always do the same)
//    - this can be extended to multiple courses. We can always rearrange courses to be in the order
//    sorted by end time if an arrangement could be made. So it is best we take courses in the order of
//    end time if we are going to take them all.
// 2. recursion, dp, to prove the greedy. The key here is that when we take potential courses one by
//    one in the order of end time, the new added courses will not change the existing arrangement of
//    old courses because of 1 -- the new courses have the latest end time, if we are going to take
//    it, it is always gonna be the last one. Whatever comes before it won't be affected.
//    If we can take it, just take it. Can't produce a bigger number from prev because prev is already the largest by definition provided that we don't change any constraints of it which we won't because the new one is only gonna be after everything.
//    If we cannot take it, then we are gonna delete some courses to make room for this course. Note that this course is still gonna be the last one. If we ignore this new one, pay attention to the existing ones, it is gonna reduce some time but would not be able to come up with an arrangement that will yield more courses, because by definition prev is the biggest. So the best is to keep the same course count, but we can reduce the duration if we can remove one that is larger than the current one and make it in.
//    EMPHASIZE: the key is that the newly added course will not affect previuos courses, it will only be added to the tail of the queue/ top of the stack and won't affect existing ones.


console.log(scheduleCourse([[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]) === 3)

0603 2. Shortest Path Visiting All Nodes

/**
* @param {number[][]} graph
* @return {number}
*/
var shortestPathLength = function(graph) {
  const n = graph.length
  // cover:head
  const set = new Set()
  // initial states: cover is 0, head is any 0 - n - 1, total n nodes
  const q = []
  const getKey = (i, j) => `${i}:${j}`
  if (n === 1) {
    return 0
  }
  for (let i = 0; i < n; i++) {
    q.push([1 << i, i]) // !!! should consider that digit visited when head is there already, initial not 0 but head is 1
    set.add(getKey(1 << i, i))
  }
  let step = 0
  while (q.length > 0) {
    // take a step, get all children, check if in the children, put children into the q, exclude self
    step++
    const size = q.length
    for (let i = 0; i < size; i++) {
      const state = q.shift()
      // get children
      // where is head? get head's neighbors, generate new state
      const neighbors = graph[state[1]]
      for (const neighbor of neighbors) {
        const cover = state[0] | (1 << neighbor)
        if (cover === (1 << n) - 1) { // !!! -1
          return step
        }
        const key = getKey(neighbor, cover)
        if (!set.has(key)) {
          set.add(key)
          q.push([cover, neighbor])
        }
      }
    }
  }
  return -1
};

// our state:
// [cover, head]
// when cover reached, we good return
// visited[cover][head]
// cover 2 ** n, head n



// ---
console.log(shortestPathLength([[1,2,3],[0],[0],[0]]) === 4)
console.log(shortestPathLength([[1],[0,2,4],[1,3,4],[2],[1,2]]) === 4)

1604 1. Arithmetic Slices II - Subsequence

TLE brute force

/**
* @param {number[]} A
* @return {number}
*/
var numberOfArithmeticSlices = function(A) {
  // map: val -> index
  // !!! duplicates
  const map = new Map()
  A.forEach((num, index) => {
    const set = map.get(num) || new Set()
    set.add(index)
    map.set(num, set)
  })
  let res = 0
  //
  let all = 0
  const calcCount = (i, d) => {
    const next = A[i] + d
    if (map.has(next)) {
      const set = map.get(next)
      for (const index of [...set]) {
        if (index > i) {
          all++
          calcCount(index, d)
        }
      }
    }
  }
  //
  for (let i = 0; i < A.length - 2; i++) {
    const num = A[i]
    for (let j = i + 1; j < A.length - 1; j++) {
      all = 0
      list = [i, j]
      calcCount(j, A[j] - A[i])
      res += all
    }
  }
  return res
};

console.log(numberOfArithmeticSlices([1, 2, 3, 4]) === 3)
console.log(numberOfArithmeticSlices([2, 4, 6, 8, 10]) === 7)
console.log(numberOfArithmeticSlices([2, 2, 2]) === 1)
console.log(numberOfArithmeticSlices([1, 1, 1, 1, 1]) === 16)
console.log(numberOfArithmeticSlices([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]) === 4194050)

sicilianee 发表于 2018-6-5 13:16
1604 1. Arithmetic Slices II - Subsequence

TLE brute force

AC after special handle d === 0


/**
* @param {number[]} A
* @return {number}
*/
var numberOfArithmeticSlices = function(A) {
  // map: val -> index
  // !!! duplicates
  const map = new Map()
  A.forEach((num, index) => {
    const set = map.get(num) || new Set()
    set.add(index)
    map.set(num, set)
  })
  let res = 0
  //
  let all = 0
  const calcCount = (i, d) => {
    const next = A[i] + d
    if (map.has(next)) {
      const set = map.get(next)
      for (const index of [...set]) {
        if (index > i) {
          all++
          calcCount(index, d)
        }
      }
    }
  }
  //
  for (let i = 0; i < A.length - 2; i++) {
    const num = A[i]
    for (let j = i + 1; j < A.length - 1; j++) {
      all = 0
      list = [i, j]
      if (A[i] !== A[j]) { // don't count d === 0 case
        calcCount(j, A[j] - A[i])
        res += all
      }
    }
  }
  // handle d === 0 case
  const dupCount = [...map.values()].map(set => set.size).filter(num => num > 2)
    .map(num => getSameCount(num)).reduce((a, b) => a + b, 0)
  return res + dupCount
};

function getSameCount (n) {
  // !! don't use 1 << n, will overflow
  return Math.pow(2, n) - (1 + n * (n + 1) / 2)
}

console.log(numberOfArithmeticSlices([1, 2, 3, 4]) === 3)
console.log(numberOfArithmeticSlices([2, 4, 6, 8, 10]) === 7)
console.log(numberOfArithmeticSlices([2, 2, 2]) === 1)
console.log(numberOfArithmeticSlices([1, 1, 1, 1, 1]) === 16)
console.log(numberOfArithmeticSlices([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]) === 4194050)

sicilianee 发表于 2018-6-5 13:39
AC after special handle d === 0

They have a dp solution, need to check that out.
It seems quite simple.

0607 1. Redundant Connection II

const _ = require('lodash')

var findRedundantDirectedConnection = function(edges) {
  // first, find indegree two
  const inMap = new Map()
  let inNode = null
  let extraIn = null
  for (const [from, to] of edges) {
    if (inMap.has(to)) {
      extraIn = from
      inNode = to
    } else  {
      inMap.set(to, from)
    }
  }

  // second, find circle
  const circleMap = new Map() // edges, key-val
  const getKey = edge => `${edge[0]}:${edge[1]}`
  const findCircle = (node) => {
    // walk all the way up until you find existing node
    const existing = new Set([node])
    while (inMap.has(node) && !existing.has(inMap.get(node))) {
      node = inMap.get(node)
      existing.add(node)
    }
    if (!inMap.has(node)) { // reached root, no circle
      return
    } else { // found start of circle
      const start = inMap.get(node)
      let aNode = start // !!! don't shadow vars, you'll get wierd bugs like this, because you might still use the outside var before you shadow it, and it is still hoisted
      do {
        const parent = inMap.get(aNode)
        circleMap.set(getKey([parent, aNode]), [parent, aNode])
        aNode = parent
      } while (aNode !== start)
    }
  }
  const start = inNode ? inNode : edges[0][0]
  findCircle(start)
  if (inNode) { // has indegree two node, swap, search again
    const tmp = inMap.get(inNode)
    inMap.set(inNode, extraIn)
    extraIn = tmp
    findCircle(start)
  }

  // third, find intersection
  const edge1 = [extraIn, inNode]
  const edge2 = [inMap.get(inNode), inNode]
  const key1 = getKey(edge1)
  const key2 = getKey(edge2)
  if (inNode && circleMap.size > 0) {
    return circleMap.has(key1) ? circleMap.get(key1) : circleMap.get(key2)
  }

  // fourth, find latest
  let edgeMap = new Map()
  if (inNode) {
    edgeMap.set(key1, edge1)
    edgeMap.set(key2, edge2)
  } else {
    edgeMap = circleMap
  }
  for (const edge of edges.reverse()) { // backwards
    const key = getKey(edge)
    if (edgeMap.has(key)) {
      return edge
    }
  }
};


console.log(_.isEqual(findRedundantDirectedConnection([[1,2], [1,3], [2,3]]),[2,3]))
console.log(_.isEqual(findRedundantDirectedConnection([[1,2], [2,3], [3,4], [4,1], [1,5]]), [4,1]))