记录

0227 1. Non-negative Integers without Consecutive Ones

/**
* @param {number} num
* @return {number}
*/
var findIntegers = function(num) {
  // num = num || 0 // the question said num will be positive
  // if (num === 0) {
  //   return 1
  // }
  const str = num.toString(2)
  const len = str.length
  const one = Array(len + 1) // most significant bit is 1
  const zero = Array(len + 1) // most significant bit is 0
  one[1] = 1
  zero[1] = 1
  for (let i = 2; i <= len; i++) {
    one[i] = zero[i - 1]
    zero[i] = zero[i - 1] + one[i - 1]
  }
  let total = one[len] + zero[len]
  const bits = str.split('').reverse()
  for (let i = len - 2; i >= 0; i--) {
    if (bits[i] === '0' && bits[i + 1] === '0') {
      total -= one[i + 1] // !!!! because in 'one[i]' represents length i, but here we count from 0, so ith has length i + 1
    }
    if (bits[i] === '1' && bits[i + 1] === '1') {
      break;
    }
  }
  return total


};

sicilianee 发表于 2018-2-28 12:01
0227 1. Non-negative Integers without Consecutive Ones

/**

Not the best solution but...

0227 2.  Reverse Nodes in k-Group

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
  if (head == null) {return head}
  if (k <= 0) {return head}
  const dummy = new ListNode(0)
  dummy.next = head
  let prev = dummy
  while (prev != null) {
    prev = reverseNext(prev)
  }
  return dummy.next

  function reverseNext (dummy) {
    let node = dummy
    for (let i = 0; i < k; i++) {
      node = node.next
      if (node == null) {
        return null
      }
    }
    const lastNode = node
    const allNext = lastNode.next
    const firstNode = dummy.next
    let curr = firstNode
    let prev = dummy
    while (curr !== allNext) {
      const next = curr.next
      curr.next = prev
      prev = curr
      curr = next
    }
    dummy.next = lastNode
    firstNode.next = allNext
    return firstNode // !!! here return the first one not the last one
  }

};

0227 3. Design Search Autocomplete System

// default to min heap conforming to Java's priority queue
// push, pop, top, size
class Heap {
  constructor (data, compare) {
    this.data = data || []
    this.compare = compare || ((a, b) => a - b)
    const lastParent = this.getParent(this.data.length - 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]]
  }
  siftDown (i) {
    let min = i
    const left = 2 * i + 1
    const right = 2 * i + 2
    for (let index of [left, right]) {
      if (index < this.data.length && this.compare(this.data[index], this.data[min]) < 0)  { // !!! min, not i
        min = index
      }
    }
    if (min !== i) {
      this.swap(i, min)
      this.siftDown(min)
    }
  }
  siftUp (i) {
    // found a bug???? if it is the only one, how do you siftUp?
    // then parent is itself, just remove equal?
    const parent = this.getParent(i)
    if (this.compare(this.data[parent], this.data[i]) > 0) { // !!! remove === ?
      this.swap(parent, i)
      this.siftUp(parent)
    }
  }
  get size () {
    return this.data.length
  }
  peak () {
    return this.data[0]
  }
  push (val) {
    this.data.push(val)
    this.siftUp(this.data.length - 1)
  }
  pop () {
    if (this.size > 0) {
      const val = this.peak()
      this.swap(0, this.data.length - 1)
      this.data.pop()
      this.siftDown(0)
      return val
    } else {
      throw new Error('Heap is empty')
    }
  }
}

module.exports = Heap


class MyTrieNode {
    constructor () {
        this.map = new Map()
        this.isEnd = false
    }
}
var AutocompleteSystem = function(sentences = [], times = []) {
  this.root = new MyTrieNode()
  this.map = new Map()
  for (let i = 0; i < sentences.length; i++) {
    this.insert(sentences[i])
    const count = this.map.get(sentences[i]) || 0
    this.map.set(sentences[i], count + times[i])
  }
  this.node = this.root
  this.tmp = ''
};
AutocompleteSystem.prototype.insert = function (setence) {
  let node = this.root
  for (let c of setence) {
    if (c === '#') {
      break
    }
    if (node.map.has(c)) {
      node = node.map.get(c)
    } else {
      const newNode = new MyTrieNode()
      node.map.set(c, newNode)
      node = newNode
    }
  }
  node.isEnd = true
}
AutocompleteSystem.prototype.input = function(c) {
  // when you input a character, we move the node down the trie for one node if it exist
  // or set it to null if it doesn't?
  if (c === '#') {
    this.insert(this.tmp)
    const count = this.map.get(this.tmp) || 0 // !!! need to guard with 0
    this.map.set(this.tmp, count + 1)
    this.node = this.root
    this.tmp = ''
    return []
  }
  this.tmp += c
  if (this.node == null) {
    return []
  }
  if (this.node.map.has(c)) {
    this.node = this.node.map.get(c) // !!! this.node not node
    // !!! you are looking for top biggest 3, so it is a max heap
    const pq = new Heap([], ((str1, str2) => {
        const val = this.map.get(str2) - this.map.get(str1) // !!!! for number you want max heap so you revers, but
        // for pure string you just compare by lexicographical order no need to reverse
        if (val === 0) {
            if (str1 > str2) {
                return 1
            } else if (str1 < str2) {
                return -1
            } else {
                return 0
            }
        } else {
            return val
        }
    }))
    findTop(this.tmp, this.node, pq)
    const res = []
    for (let i = 0; i < 3; i++) {
      if (pq.size > 0) {
        res.push(pq.pop())
      }
    }
    return res
  } else { // !!! you are missing this part shit!!!
    this.node = null
    return []
  }
  // put all of the strs into the pq
  function findTop (str, node, pq) {
    if (node.isEnd) {
      pq.push(str)
    }
    for (let [c, cNode] of node.map.entries()) {
      findTop(str + c, cNode, pq)
    }
  }
};



Important thing is to have the big picture written down in pseudo code first.

0228 1.  Minimum Window Subsequence

/**
* @param {string} S
* @param {string} T
* @return {string}
*/
var minWindow = function(S, T) {
  // dp[i][j], S, T
  const sLen = S.length
  const tLen = T.length
  const dp = Array(sLen).fill().map(() => Array(tLen).fill(-1))
  if (S[0] === T[0]) {
    dp[0][0] = 0
  }
  for (let i = 1; i < sLen; i++) {
    dp[i][0] = S[i] === T[0] ? i : dp[i - 1][0]
  }
  // the other row is all -1
  for (let i = 1; i < sLen; i++) {
    for (let j = 1; j < tLen; j++) {
      if (S[i] === T[j]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = dp[i - 1][j]
      }
    }
  }
  // when j = tLen - 1
  let min = Infinity
  let res = ''
  for (let i = 0; i < sLen; i++) {
    if (dp[i][tLen - 1] >= 0) {
      const len = i - dp[i][tLen - 1] + 1
      if (len < min) {
        min = len
        res = S.slice(dp[i][tLen - 1], i + 1)
      }
    }
  }
  return res

};

0228 2. Recover Binary Search Tree

Simple solution first:

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function(root) {
  if (root == null) {return}
  let a = null
  let b = null
  let prev = null
  traverse(root)
  // swap
  ;[a.val, b.val] = [b.val, a.val]

  function traverse (node) {
    if (node == null) {return}
    traverse(node.left)
    if (prev && prev.val > node.val) {
      if (a == null) {a = prev}
      b = node
    }
    prev = node // !!! important here!!1
    traverse(node.right)
  }

};


At least in order traversal you should be very familiar with

sicilianee 发表于 2018-3-1 14:54
0228 2. Recover Binary Search Tree

Simple solution first:

O 1 space



/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function(root) {
    // here we do two things, 1. morris traversal
    // 2. keep track of variants, first keep the bigger one, second keep the smaller one, keep updating second
    if (root == null) {return}
    let prev = null
    let first = null
    let second = null
    traverse(root)
    ;[first.val, second.val] = [second.val, first.val]
   
    function traverse (node) {
        function visitSelf () {
            if (prev != null && node.val < prev.val) {
                if (first == null) {
                    first = prev
                }
                second = node
            }
            prev = node // !!! important
        }
        while (node != null) {
            if (node.left == null) {
                // no left, visit self, go right
                visitSelf()
                node = node.right
            } else {
                // has left
                // try to find the pred
                let pred = node.left
                while (pred.right !== null && pred.right !== node) { // !!! pred.right, not pred itself.
                    pred = pred.right
                }
                if (pred.right == null) {
                    pred.right = node
                    node = node.left
                } else {
                    pred.right = null
                    // visit self, move right
                    visitSelf()
                    node = node.right
                }
            }
        }
    }

};

Morris traversal

back to 70 shit

0304 1. Tag Validator


// More efficient then we'll have more time for rest



// !!! 1.  there is one problem, if the cData part is inside a tag
// in their code, it is invalid, even a cdata

// !!! 2. one condition is everything needs to be wrapped inside
// __ONE__ tag


// one workaround to solve the two issues (only regarding cdata): just replace cdata part with sth else
// that is not a valid char inside a tag


var isValid = function(code) {
  let list
  try {
    list = parseTags(removeCData(code))
  } catch (e) {
    return false
  }
  console.log('the list', list)
  if (list.length === 0) {return false}
  const stack = [] // no need to put content into the stack, only tags is ok
  for (let [index, el] of list.entries()) { // !!! entries will give you [index, value] not [value, index]
    if (el instanceof Tag) {
      if (el.open) {
        stack.push(el)
      } else {
        if (stack.length > 0) {
          const top = stack.pop()
          if (!top.open || top.name !== el.name) {
            return false
          }
        } else {
          return false
        }
      }
    }
    // !!! this part is really tricky
    if (stack.length === 0) {
      const good = index === list.length - 1 && list.length >= 2
      if (!good) {return false}
    }
  }
  // !!!! important here, multiple places in this problem, you need to do sth after the loop
  return stack.length === 0
};

// now we have passed the first two phases, we move to the third phase
// the final phase, validate the tag list, the tag matching and content wrapping


class Tag {
  constructor (name, open) {
    this.name = name
    this.open = open
  }
  static create (str) {
    let tag
    if (str[0] === '/') {
      tag = new Tag(str.slice(1), false)
    } else {
      tag = new Tag(str, true)
    }
    // !!! have to exclude <
    if (tag.name.length < 1 || tag.name.length > 9) {
      throw new Error('Invalid')
    }
    for (let c of tag.name) {
      const good = c >= 'A' && c <= 'Z'
      if (!good) {
        throw new Error('Invalid')
      }
    }

    return tag
  }
}

// str -> list of str/tags
function parseTags (str) {
  const list = []
  while (str.indexOf('<') >= 0) {
    const openIndex = str.indexOf('<')
    const closeIndex = str.indexOf('>', openIndex)
    if (closeIndex < 0) {
      throw new Error('Invalid')
    }
    const prev = str.slice(0, openIndex)
    const middle = str.slice(openIndex + 1, closeIndex)
    const after = str.slice(closeIndex + 1)
    list.push(prev)
    list.push(Tag.create(middle))
    str = after
  }
  list.push(str)
  return list.filter(val => val)
}



function removeCData (str) {
  let toKeep = ''
  while (str.indexOf('<![CDATA[') >= 0) {
    const openIndex = str.indexOf('<![CDATA[')
    const closeIndex = str.indexOf(']]>', openIndex) //! the startIndex here is very important
    if (closeIndex < 0) {
      throw new Error('Invalid')
    }
    toKeep = toKeep + str.slice(0, openIndex) + 'cdata'
    str = str.slice(closeIndex + 3)
  }
  return toKeep + str // !!! in the end shall still keep str as the last one
}



难搞定。情况太多太复杂了

0304 2. Concatenated Words


// !!! put classes outside because classes have orders
class Node {
  constructor () {
    this.map = new Map()
    this.isEnd = false
  }
}

var findAllConcatenatedWordsInADict = function(words) {
  if (words == null || words.length === 0) {
    return []
  }
  words = words.sort((a, b) => a.length - b.length) // !!!sort by length not str themselves

  const root = new Node()
  root.isEnd = true // we treat empty string as dividable
  const res = []
  let is = false

  for (let word of words) {
    if (canDivide(word)) {
      res.push(word)
    } else {
      insert(root, word)
    }
  }
  return res.filter(str => str) // !!! because we mark empty as dividable, we shall remove them in the end


  function canDivide (str) {
    let node = root
    for (let [i, c] of str.split('').entries()) {
      if (node.map.has(c)) {
        node = node.map.get(c)
        // cut from here or continue, you have two options
        if (node.isEnd) {
          const post = str.slice(i+ 1)
          if (canDivide(post)) {
            return true
          }
        }
      } else {
        return false
      }
    }
    return node.isEnd // no dup, if in the end we found, it is comprisable
  }

  function insert (root, str) {
    let node = root
    for (let c of str) {
      if (node.map.has(c)) {
        node = node.map.get(c)
      } else {
        const newNode = new Node()
        node.map.set(c, newNode)
        node = newNode
      }
    }
    node.isEnd = true
  }





};