记录

0316 2.  Find Median from Data Stream


class Heap {
  constructor (data = [], _compare) {
    this.data = [...data]
    this._compare = _compare || ((a, b) => a - b)
    const lastParent = this.getParent(this.size - 1)
    for (let i = lastParent; i >= 0; i--) {
      this.siftDown(i)
    }
  }
  compare (i, j) {
    return this._compare(this.data[i], this.data[j])
  }
  getParent (i) {
    return Math.trunc((i - 1) / 2)
  }
  get size () {
    return this.data.length
  }
  peek () {
    return this.data[0]
  }
  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 (this.compare(index, min) < 0) {
        min = index
      }
    }
    if (min !== i) {
      this.swap(i, min)
      this.siftDown(min)
    }
  }
  siftUp (i) {
    const parent = this.getParent(i)
    if (this.compare(i, parent) < 0) {
      this.swap(i, parent)
      this.siftUp(parent)
    }
  }
  push (val) {
    this.data.push(val)
    this.siftUp(this.size - 1)
  }
  pop () {
    if (this.size === 0) {return undefined}
    const val = this.peek()
    this.swap(0, this.size - 1)
    this.data.pop()
    this.siftDown(0)
    return val
  }
}

var MedianFinder = function() {
  this.low = new Heap([], (a, b) => b - a)
  this.high = new Heap([]) // !!! the first time you find out this issue shit!!!
  // 2. !!! and this one is reverse order, shit
  // 3. !!! low is max heap and high is min heap, not the other way around
};

MedianFinder.prototype.addNum = function(num) {
  const low = this.low // !!! well, didn't write this.low, this.high. Just being lazy here
  const high = this.high
  if (this.low.size <= this.high.size) {
    // add to low
    if (this.high.size === 0 || num <= this.high.peek()) {
      this.low.push(num)
    } else {
      this.high.push(num)
      this.low.push(this.high.pop())
    }
  } else {
    // add to high
    if (num >= low.peek()) {
      high.push(num)
    } else {
      low.push(num)
      high.push(low.pop())
    }
  }
};

MedianFinder.prototype.findMedian = function() {
  const low = this.low
  const high = this.high
  const size = low.size + high.size
  if (size % 2 === 0) {
    return (low.peek() + high.peek()) / 2
  } else {
    return low.peek()
  }
};

0318 1. Smallest Rotation with Highest Score

var bestRotation = function(A) {
  A = A || []
  const len = A.length
  const change = Array(len).fill(0)
  for (let i = 0; i < len; i++) {
    const k = (i + len - A[i] + 1) % len
    change[k]-- // !!!! -- not ++
  }
  let val = 0
  let max = 0
  for (let k = 1; k < len; k++) {
    change[k] = change[k] + change[k - 1] + 1 // !!! you have to change each of them to be able to compare, or you have to keep both the value and index of the biggest one
    if (change[k] > change[max]) {
      max = k
    }
  }
  return max
};



// one remaining problem is:
// now we gain points when value is less or smaller than
// we are assuming this is true, so we lose points when value becomes bigger than index
// what if we are bigger than from the beginning, then there would be no losing points?
// [4,4,4,4,4,4,4,4,4]
// then we are going for the reverse direction, since we are doing it backwards, we will
// never reach there if we go on that direction, so we will cross the line and got to the
// other side, that is when it becomes increasing, and then you can decrease again

0318 2. Minimize Max Distance to Gas Station

var minmaxGasDist = function(stations, K) {
  // do binary search
  stations = stations || []
  let low = 0
  let high = 0
  for (let i = 1; i < stations.length; i++) {
    high = Math.max(high, stations[i] - stations[i - 1])
  }
  while (low + 1e-6 <= high) {
    const mid = low + (high - low) / 2
    // get count for mid as D
    let count = 0
    for (let i = 1; i < stations.length; i++) {
      count += Math.ceil((stations[i] - stations[i - 1]) / mid - 1)
    }
    // !!!! this comparision is out of the loop, not inside the loop!!!
    // !!! rethink the comparision, and the equal condition. !!!
    if (count <= K) {
      // count required is less than K, we can do it, we can even do smaller, go smaller
      // equal is the same, we can achieve it
      high = mid
    } else {
      // no, cannot do it, increase D
      low = mid
    }
  }
  return high
};

0319 1. Number of Digit One




var countDigitOne = function(n) {
  if (n <= 0) {return 0} // !!!!! could be less than 0
  let base = 1
  while (base <= n) {
    base = base * 10
  }
  base = base / 10
  let oneBase = 1
  let count = 0
  while (oneBase <= base) {
    count += calc(true, oneBase, base)
    oneBase *= 10
  }
  return count

  function calc (still, oneBase, base) {
    if (base === 0) {return 1}
    const digit = getDigit(base)
    if (oneBase === base) {
      if (digit > 1) {
        return calc(false, oneBase, Math.trunc(base / 10))
      } else if (digit === 1) {
        // !!! no no no, why do you give it a true? you could be coming from false ??? just f***ing carry on whatever is there
        const res = calc(still, oneBase, Math.trunc(base / 10))
        return res
      } else {
        return still ? 0 : calc(false, oneBase, Math.trunc(base / 10)) // !!! don't just return 1, still continue !!!!
      }
    } else {
      if (still) {
        const countStill = calc(true, oneBase, Math.trunc(base / 10))
        let notStill = 0
        if (digit > 0) {
          notStill = (digit) * calc(false, oneBase, Math.trunc(base / 10)) // digit not digit - 1 because 0 is possible
        }
        return countStill + notStill
      } else {
        const res =  10 * calc(false, oneBase, Math.trunc(base / 10))
        return res
      }
    }
  }


  function getDigit (base) {
    return Math.trunc(n / base) % 10
  }
};




My own solution. Seems the official one is much simpler

sicilianee 发表于 2018-3-20 14:47
0319 1. Number of Digit One

var countDigitOne = function(n) {
   n = n || 0 // we will consider n === 0 later
  // for each digit to be 1
  let count = 0
  let base = 1 // each digit on base
  while (base <= n) {
    const higherHalf = Math.trunc((n / (base * 10)))
    const lowerHalf = n % base
    const digit = Math.trunc(n / base) % 10
    if (digit > 1) {
      // no need to consider lower half, all 10
      count += (higherHalf + 1) * base
    } else if (digit === 1) {
      // higher half two parts, the the last one and the rest
      // the rest is the same, while the last one needs to consider the lower part
      count += higherHalf * base + lowerHalf + 1
    } else { // digit === 0
      count += higherHalf * base // remove the last one just
    }
    base = base * 10
  }
  return count
};

0327 1. The Skyline Problem

// [2, 10, 20], [3, 4, 6], [4, 5, 6]

var getSkyline = function(buildings = []) {
  // [2, 3, 20]
  // process to [2, 2, 20]
  // collect all the points, discretize them, put into points
  // map point value to point index
  // now transform buildings to index buildings
  // apply each of them on the vals array
  // go through the vals array one more time
  buildings = buildings.map(([left, right, val]) => [left, right - 1, val])
  const set = new Set()
  for (let [left, right, val] of buildings) {
    set.add(left)
    set.add(right)
    set.add(right + 1)
  }
  const points = [...set].sort((a, b) => a - b)
  const map = new Map()
  for (const [index, val] of points.entries()) {
    map.set(val, index)
  }
  buildings = buildings.map(([left, right, val]) => [map.get(left), map.get(right), val])
  const vals = Array(points.length).fill(0)
  for (const [left, right, val] of buildings) {
    for (let i = left; i <= right; i++) {
      vals[i] = Math.max(vals[i], val)
    }
  }
  const res = []
  for (let i = 0; i < vals.length; i++) {
    if (i === 0) {
      res.push([points[i], vals[i]])
    } else {
      if (vals[i] !== vals[i - 1]) {
        res.push([points[i], vals[i]])
      }
    }
  }
  return res
};





回头看下其他解法怎么做的

0327 2. Insert Interval

/**
* Definition for an interval.
* function Interval(start, end) {
*     this.start = start;
*     this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @param {Interval} newInterval
* @return {Interval[]}
*/
var insert = function(intervals, newInterval) {
  // first, insert into it
  // then, merge it

  // how to insert?
  // binary search to find the position, logn
  // how to merge?
  // it is sorted based on start, now we walk through one by one, or we can start
  // from the one we inserted, the one before it because no overlap before
  // then walk through one by one and merge them into new ones and push into a new array
  // the process will take On.
  const start = newInterval.start
  let i
  for (i = 0; i < intervals.length; i++) {
    if (intervals[i].start >= start) {
      break
    }
  }
  intervals.splice(i, 0, newInterval)
  const res = []
  for (let i = 0; i < intervals.length; i++) {
    const curr = intervals[i]
    if (res.length > 0) {
      const top = res[res.length - 1]
      if (curr.start <= top.end) {
        top.end = Math.max(top.end, curr.end)
      } else {
        res.push(curr)
      }
    } else {
      res.push(curr)
    }
  }
  return res
};


先插入，再merge。注意merge的时候有点tricky要新建一个数组。

0328 1. K-th Smallest Prime Fraction


class Heap333 {
    constructor (data = [], customCompare) {
        this.data = [...data]
        customCompare = customCompare || ((a, b) => a - b )
        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)
    }
    get size () {
        return this.data.length
    }
    peek () {
        return this.data[0]
    }
    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 (const index of [left, right]) {
            if (index < this.size && this.compare(index, min) < 0) {
                min = index
            }
        }
        if (min !== i) {
            this.swap(i, min)
            this.siftDown(min)
        }
    }
    siftUp (i) {
        const parent = this.getParent(i)
        if (this.compare(i, parent) < 0) {
            this.swap(i, parent)
            this.siftUp(parent)
        }
    }
    push (val) {
        this.data.push(val)
        this.siftUp(this.size - 1)
    }
    pop () {
        if (this.size === 0) {return undefined}
        const val = this.peek()
        this.swap(0, this.size - 1)
        this.data.pop()
        this.siftDown(0)
        return val
    }
}




var kthSmallestPrimeFraction = function(A, K) {

  if (A.length === 0) {
    return null
  }
  const compare = (a, b) => A[a[0]] / A[a[1]] - A[b[0]] / A[b[1]]
  const heap = new Heap333([],compare)
  // const heap = new Heap2(compare)
  for (let i = 1; i < A.length; i++) {
    heap.push([0, i])
  }
  for (let i = 0; i < K - 1; i++) {
    const [pi, qi] = heap.pop()
    if (pi + 1 < qi) {
      heap.push([pi + 1, qi])
    }
  }
  // !!! need to process, wheat you have here is index, they need value
  return heap.pop().map(i => A[i])
};




Putting the class declaration inside the function body will significantly slow down the program.

0328 2. Merge k Sorted Lists

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists = []) {
  if (lists.length === 0) {return null}
  while (lists.length > 1) {
    const node1 = lists.shift()
    const node2 = lists.shift()
    lists.push(merge2(node1, node2))
  }
  return lists[0]
};

function merge2 (node1, node2) {
  const dummy = new ListNode(0)
  let prev = dummy
  while (node1 !== null || node2 !== null) {
    const val1 = node1 === null ? Infinity : node1.val
    const val2 = node2 === null ? Infinity : node2.val
    if (val1 <= val2) {
      prev.next = node1
      node1 = node1.next
    } else {
      prev.next = node2
      node2 = node2.next
    }
    prev = prev.next
  }
  return dummy.next
}

sicilianee 发表于 2018-3-29 13:06
0328 2. Merge k Sorted Lists

/**

how to cut down the complexity still, don't use shift and just calculate the gap for reach iteration