记录

0523 1. LRU Cache

class Node {
  constructor (key, val) {
    this.key = key
    this.val = val
    this.prev = null
    this.next = null
  }
  insertAfter (node) {
    const next = this.next
    this.next = node
    node.prev = this
    node.next = next
    next.prev = node
  }
  removeSelf () {
    // console.log('myself is', this)
    const prev = this.prev
    const next = this.next
    prev.next = next
    next.prev = prev
    this.prev = this.next = null
  }
}
class List {
  constructor () {
    this.sentinel = new Node(-1, -1)
    const sentinel = this.sentinel
    sentinel.next = sentinel.prev = sentinel
  }
  get head () {
    return this.sentinel.next
  }
  get tail () {
    return this.sentinel.prev
  }
  addBack (node) {
    this.tail.insertAfter(node)
  }
  removeFront () {
    // !!!! note head is a getter function, then it changes in between your two calls
    // need to save a reference
    const head = this.head
    head.removeSelf()
    return head
  }
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
  if (capacity < 1) {
    throw new Error('Invalid arg')
  }
  this.size = capacity
  this.map = new Map()
  this.list = new List()
};

/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
  if (this.map.has(key)) {
    const node = this.map.get(key)
    node.removeSelf()
    this.list.addBack(node)
    return node.val
  } else {
    return -1
  }
};

/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
  if (this.map.has(key)) {
    const node = this.map.get(key)
    node.val = value
    node.removeSelf()
    this.list.addBack(node)
  } else {
    if (this.map.size === this.size) {
      const node = this.list.removeFront()
      this.map.delete(node.key)
    }
    const node = new Node(key, value)
    this.map.set(key, node)
    this.list.addBack(node)
  }
};

const cache = new LRUCache(2)

cache.put(1, 1);
cache.put(2, 2);
const val1 = cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
const val2 = cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
const val3 = cache.get(1);       // returns -1 (not found)
const val4 = cache.get(3);       // returns 3
const val5 = cache.get(4);

console.log(val1 === 1)
console.log(val2 === -1)
console.log(val3 === -1)
console.log(val4 === 3)
console.log(val5 === 4)


// head and tail, front and back, define and stick to them. confusing.
// tail is like top of a stack

0526 1.  Strong Password Checker

/**
* @param {string} s
* @return {number}
*/
var strongPasswordChecker = function(s) {
  if (s == null || s.length === 0) {
    return 6
  }
  const len = s.length

  // condition2
  let has1 = false
  let has2 = false
  let has3 = false // !!! name c duplicates the loop variable
  for (const c of s) {
    if (c >= 'a' && c <= 'z') {
      has1 = true
    } else if (c >= 'A' && c <= 'Z') {
      has2 = true
    } else {
      has3 = true
    }
  }
  const need = 3 - [has1, has2, has3].filter(bol => bol).length // !!! length not size for array

  // condition3
  let repeats = []
  let count = 1
  for (let i = 1; i <= len; i++) {
    if (i === len || s[i] !== s[i - 1]) {
      if (count >= 3) {
        repeats.push(count)
      }
      count = 1
    } else {
      count++
    }
  }

  // condition1
  if (len < 6) {
    const need1 = 6 - len
    const need2 = repeats.map(count => Math.ceil(count / 2) - 1).reduce((a, b) => a + b, 0)
    return Math.max(need, need1, need2)
  } else if (len >= 6 && len <= 20) {
    const replace = repeats.map(count => Math.floor(count / 3)).reduce((a, b) => a + b, 0)
    return Math.max(need, replace)
  } else {
    const toDelete = len - 20
    const buckets = Array(3).fill().map(() => [])
    repeats = repeats.map(num => num - 2) // remove the leading 2
    repeats.forEach(num => {
      const index = (num - 1) % 3
      buckets[index].push(num)
    })
      // first apply on section1, then 2, then 1, 2, 3
      // then the replace elements
      // then if still needed, add more replace, by ceil((count) / 3)
      // this, you can think of the replacement always happens from the first element, and go in cycle of 3
      // not like before it happens on the last one of a 3 (also go in cycle of 3)
    // !!! in order to know delta, you still need to divide them into 3 buckets
    let remainDelete = toDelete
    const applySpecialDeletions = () => {
      for (let i = 0; i < buckets.length; i++) {
        const delta = Math.min(remainDelete, i + 1)
        const bucket = buckets[i]
        for (let j = 0; j < bucket.length; j++) {
          if (remainDelete > 0) {
            remainDelete -= delta
            bucket[j] -= delta
          } else {
            return
          }
        }
      }
    }
    applySpecialDeletions()
    repeats = buckets.reduce((a, b) => [...a, ...b], [])
    let toReplace = 0
    if (remainDelete > 0) {
      // all cost 3, apply the rest deletions
      const repeatCount = repeats.reduce((a, b) => a + b, 0)
      const canApply = remainDelete - remainDelete % 3
      toReplace = (repeatCount - canApply) / 3 // we know it is multiple of 3, result could be neg
    } else {
      // all delete applied, only replacement
      toReplace = repeats.map(num => Math.ceil(num / 3)).reduce((a, b) => a + b, 0)
    }
    const val = toDelete + Math.max(toReplace, need)
    return val
  }
};


Lit man!

sicilianee 发表于 2018-5-27 05:55
0526 1.  Strong Password Checker

/**

they have shorter solutions though. The top voted only 35 lines. Check out later.

0527 1. Find the Closest Palindrome

/**
* @param {string} n
* @return {string}
*/
var nearestPalindromic = function(n) {
  // !!!! not including itself !!
  if (!n) {
    return ''
  }
  const len = n.length
  if (len === 1) {
    return String(Number.parseInt(n, 10) - 1)
  }
  const number = Number.parseInt(n, 10)
  const hasExtra = len % 2 === 1
  const end = Math.trunc((len - 1) / 2)
  const left = n.slice(0, end + 1)
  const numLeft = Number.parseInt(left, 10)

  const mirror = getMirror(left, hasExtra)

  let lessMirror
  // !!! note 11 is a special case of oneZeros, but it fits into what is here. But you
  // need to explicitly consider this one
  if (isOneZeros(left)) { // one digit less
    lessMirror = '9'.repeat(len - 1)
  } else {
    lessMirror = getMirror(String(numLeft - 1), hasExtra)
  }

  let moreMirror
  if (isAllNine(left)) { // one digit more
    moreMirror = `1${'0'.repeat(len + 1 - 2)}1`
  } else {
    moreMirror = getMirror(String(numLeft + 1), hasExtra)
  }

  // !!! seems use associative array would be much easier and cleaner, filter on the first one
  // and then map to generate more
  // 1. create more vars
  // 2. use associative array
  const strs = [mirror, lessMirror, moreMirror].filter(str => str !== n) // !!! filter out self
  const nums = strs.map(str => Number.parseInt(str, 10))
  const abss = nums.map(num => Math.abs(num - number))
  let [minStr, minNum, minAbs] = [null, null, null]
  for (let i = 0; i < strs.length; i++) {
    const [str, num, abs] = [strs[i], nums[i], abss[i]]
    let swap = false
    if (minStr == null) {
      swap = true
    } else {
      if (abs < minAbs) {
        swap = true
      } else if (abs === minAbs) {
        if (num < minNum) {
          swap = true
        }
      }
    }
    if (swap) {
      [minStr, minNum, minAbs] = [str, num, abs]
    }
  }
  return minStr
};

function getMirror (str, hasExtra) {
  const [left, extra] = hasExtra ? [str.slice(0, str.length -1), str[str.length - 1]] : [str, '']
  const val = left + extra + [...left].reverse().join('')
  return val
}

function isOneZeros (str) {
  if (str[0] === '1') {
    const rest = str.slice(1)
    return [...rest].every(c => c === '0')
  }
  return false
}

function isAllNine (str) {
  return [...str].every(c => c === '9')
}




// those that will chang size, depending on left half not full
// 1000 0 xxxx
//  999 9 xxxx -> 9999 9999
// 9999 _ xxxx -> 9999_9999
// 100 xxx
//  99 xxx -> 99 9 99
// 99

//  9999 9 xxxx
// 10000 0 xxxx -> 10000 00001
//  9999 xxxx
// 10000 xxxx -> 1000 0 0001


// 因为一个special case 让所有流程都变得非常复杂
// what we want to do is to remove the special cases
// we either pre handle the special case or we generalize them into a general solution


console.log(nearestPalindromic('123') === '121')
console.log(nearestPalindromic('999') === '1001')
console.log(nearestPalindromic('100345') === '100001')
console.log(nearestPalindromic('2335') === '2332')

sicilianee 发表于 2018-5-28 03:47
0527 1. Find the Closest Palindrome

/**

Check the writeup. The main idea should be similar but they seem to have different tricks.

sicilianee 发表于 2018-5-28 03:49
Check the writeup. The main idea should be similar but they seem to have different tricks.

check the most voted answer. It is surprisingly short. Though I think the main idea is the same.

0527 2.  Guess the Word

My best try, still exceed 10 times.

/**
* // This is the master's API interface.
* // You should not implement it, or speculate about its implementation
* function Master() {
*
*     @param {string[]} wordlist
*     @param {Master} master
*     @return {integer}
*     this.guess = function(word) {
*         ...
*     };
* };
*/
/**
* @param {string[]} wordlist
* @param {Master} master
* @return {void}
*/
function getCount (str1, str2) {
  let count = 0
  for (let i = 0; i < 6; i++) {
    if (str1[i] === str2[i]) {
      count++
    }
  }
  return count
}

var findSecretWord = function(wordlist, master) {
  if (wordlist == null || wordlist.length === 0 || master == null) {
    return
  }
  // build adj matrix for lookup
  wordlist = [...new Set(wordlist)]
  const matrix = {}
  wordlist.forEach(word => matrix[word] = {})
  for (let i = 0; i < wordlist.length; i++) {
    const wordi = wordlist[i]
    for (let j = i; j < wordlist.length; j++) {
      const wordj = wordlist[j]
      const count = getCount(wordi, wordj)
      matrix[wordi][wordj] = count
      matrix[wordj][wordi] = count
    }
  }
  while (true) {
    // build categorized adj list
    const adjList = {}
    const createList = () => Array(6).fill().map(() => [])
    wordlist.forEach(word => adjList[word] = createList())
    for (let i = 0; i < wordlist.length; i++) {
      const wordi = wordlist[i]
      for (let j = i + 1; j < wordlist.length; j++) { // !!! j from i + 1 f***, not 0
        const wordj = wordlist[j]
        const count = getCount(wordi, wordj)
        adjList[wordi][count].push(wordj)
        adjList[wordj][count].push(wordi)
      }
    }
    // now choose the most balanced one
    // for each, calc the variances
    const variances = wordlist.map(word => {
      const lens = adjList[word].map(list => list.length)
      return getVariance(lens)
    })
    // use the word with the smallest variance
    let [minVar, minWord] = [null, null]
    for (let i = 0; i < wordlist.length; i++) {
      const [variance, word] = [variances[i], wordlist[i]]
      if (minVar == null || variance < minVar) {
        ;[minVar, minWord] = [variance, word]
      }
    }
    const minCount = master.guess(minWord)
    if (minCount === 6) {
      return
    }
    const lists = adjList[minWord]
    const newList = lists[minCount]
      .filter(word => {
        for (let i = 0; i < 6; i++) {
          if (i !== minCount) {
            const list = lists[i]
            for (const aWord of list) {
              const aCount = matrix[aWord][word]
              // x: minCount, y: i, z: aCount
              // z <= 6 - |x - y|
              const good = aCount <= 6 - Math.abs(minCount - i)
              if (!good) {
                return false
              }
            }
          }
        }
        return true
      })
    wordlist = newList
  }
};

function getVariance (arr) {
  const sum = arr.reduce((a, b) => a + b, 0)
  const avg = sum / arr.length
  return arr.map(el => el - avg)
    .reduce((a, b) => a + b, 0)
}

sicilianee 发表于 2018-5-28 08:03
0527 2.  Guess the Word

My best try, still exceed 10 times.

var findSecretWord = function (wordlist, master) {
  while (true) {
    let [bestScrore, bestWord] = [Infinity, ''] // !!! safer to not use null to indicate
    wordlist.forEach(word => {
      const score = getScore(wordlist, word)
      if (score < bestScrore) {
        ;[bestScrore, bestWord] = [score, word]
      }
    })
    const matchCount = master.guess(bestWord)
    if (matchCount === 6) { return }
    wordlist = wordlist.filter(word => getSameCount(word, bestWord) === matchCount)
  }
}

function getScore (words, word) {
  const counts = new Array(7).fill(0)
  words.forEach(w => {
    counts[getSameCount(w, word)]++
  })
  return Math.max(...counts) // !!! max, not min, we'll need the min of max
}

function getSameCount (word1, word2) {
  let count = 0
  for (let i = 0; i < word1.length; i++) {
    if (word1[i] === word2[i]) {
      count++
    }
  }
  return count
}

确实更快收敛。
同一个testcase我11次他只需要8次。强。

sicilianee 发表于 2018-5-29 05:22
var findSecretWord = function (wordlist, master) {
  while (true) {
    let  =  // !!! safer to  ...

// 为什么这样选更好，最大的最小
// 我们不想让某一组数据太多，这样如果选中这个多的就没有起到筛选的作用
// 这样我们取最大的最小，保证最坏的情况是最好的
// 而之前我们是取方差， 选的是分布最均匀的，这样就把最少的一组太少的这种情况排除在外了。而在最好的情况下，
// 这一组是收敛最快的。而我们之前的算法把最快的这个排除了。

0528 1. Word Break II

// 超时。为什么？loop本身已经是cubic complexity, 而每次loop中要loop之前的answer, 而answer本身
// 最坏是O(2**n), exponential, 可以想像非常糟糕。


/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
  const len = s.length
  const map = new Map()
  const set = new Set(wordDict)
  for (let size = 1; size <= len; size++) {
    console.log('one round')
    for (let i = 0; i + size - 1 < len; i++) {
      const j = i + size - 1
      const str = s.slice(i, j + 1)
      if (!map.has(str)) {
        const res = []
        if (set.has(str)) {
          res.push(str)
        }
        // break down
        for (let k = i; k < j; k++) {
          const leftStr = s.slice(i, k + 1)
          const rightStr = s.slice(k + 1, j + 1) // !! + 1
          if (set.has(leftStr) && map.get(rightStr)) {
            const right = map.get(rightStr)
            right.forEach(reOrg => {
              res.push(`${leftStr} ${reOrg}`)
            })
          }
        }
        map.set(str, res.length > 0 ? res : null)
      }
    }
  }
  const res = map.get(s)
  return res ? res : []
};

// ---- test

const a = "aaaaaaaaaaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
console.log(a.length)
const b = ["aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","ba"]
console.log(wordBreak(a, b))

console.log(wordBreak('catsanddog', ["cat", "cats", "and", "sand", "dog"]).length === 2)
console.log(wordBreak('pineapplepenapple', ["apple", "pen", "applepen", "pine", "pineapple"]).length === 3)
console.log(wordBreak('catsandog',  ["cats", "dog", "sand", "and", "cat"]).length === 0)