记录

1109 6. Map Sum Pairs

/**
* Initialize your data structure here.
*/
var MapSum = function() {
    this.dict = {};
    this.root = new TrieNode();
};

class TrieNode {
    constructor () {
        this.children = {};
        this.score = 0;
    }
}

/**
* @param {string} key
* @param {number} val
* @return {void}
*/
MapSum.prototype.insert = function(key, val) {
    const delta = val - (this.dict[key] || 0); // yuck !!!!! I diddn't thought it was operator precedence !!!!!
    this.dict[key] = val;
    let node = this.root;
    for (let c of key) {
        node.children[c] = node.children[c] || new TrieNode();
        node.children[c].score += delta;
        node = node.children[c];
    }
};

/**
* @param {string} prefix
* @return {number}
*/
MapSum.prototype.sum = function(prefix) {
    if (prefix == null) {return 0}
    let node = this.root;
    for (let c of prefix) {
        if (node.children[c] != null) {
            node = node.children[c];
        } else {
            return 0;
        }
    }
    return node.score;
};

/**
* Your MapSum object will be instantiated and called as such:
* var obj = Object.create(MapSum).createNew()
* obj.insert(key,val)
* var param_2 = obj.sum(prefix)
*/

1110 1.  Count Binary Substrings


/**
* @param {string} s
* @return {number}
*/
var countBinarySubstrings = function(s) {
    if (s == null || s.length === 0) {
        return 0;
    }
    let num = 0;
    let prev = 0;
    let curr = 1;
    for (let i = 1; i <= s.length; i++) {
        if (i === s.length || s[i] !== s[i - 1]) {
            num += Math.min(prev, curr);
            prev = curr;
            curr = 1;
        } else {
            curr++;
        }
    }
    return num;
};

1110 2. Two Sum IV - Input is a BST


/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {boolean}
*/
var findTarget = function(root, k) {
    // 不管什么数据结构都是可以用set来做的。但是这样实际上没有用到bst的性质。想来出这道题一定是要我们不额外创建set，用binary search来做。
    if (root == null) {return false;}
    const set = new Set();
    return recurse(root);

    function recurse (node) {
        if (node == null) {
            return false;
        }
        const target = k - node.val;
        if (set.has(target)) {
            return true;
        } else {
            set.add(node.val);
            const left = recurse(node.left);
            const right = recurse(node.right);
            return left || right;
        }
    }
};

1110 3. Minimum ASCII Delete Sum for Two Strings

/**
* @param {string} s1
* @param {string} s2
* @return {number}
*/
var minimumDeleteSum = function(s1, s2) {
    // sea, eat
    if (s1 == null || s2 == null) {
        throw new Error('Invalid args');
    }
    const len1 = s1.length;
    const len2 = s2.length;
    const dp = Array(len1 + 1).fill().map(() => Array(len2 + 1).fill(0));
    for (let j = len2 - 1; j >= 0; j--) {
        dp[len1][j] = dp[len1][j + 1] + s2.charCodeAt(j); // !!! here is s2!!!!
    }
    for (let i = len1 - 1; i >= 0; i--) { // !!! why you put - 2 here?
        dp[i][len2] = dp[i + 1][len2] + s1.charCodeAt(i); // !!! here is s1!!!!
    }
    for (let i = len1 - 1; i >= 0; i--) {
        for (let j = len2 - 1; j >= 0; j--) {
            if (s1[i] === s2[j]) {
                dp[i][j] = dp[i + 1][j + 1];
            } else {
                dp[i][j] = Math.min(dp[i + 1][j] + s1.charCodeAt(i), dp[i][j + 1] + s2.charCodeAt(j));
            }
        }
    }
    return dp[0][0];
};

1110 4.  Beautiful Arrangement II

/**
* @param {number} n
* @param {number} k
* @return {number[]}
*/
var constructArray = function(n, k) {
    const res = [];
    for (let i = 0; i < n - k - 1; i++) {
        res[i] = i + 1;
    }
    for (let i = 0; i < k + 1; i++) {
        res[n - k - 1 + i] = i % 2 === 0
            ? n - k + Math.floor(i / 2) // !!!! i === 0 is the first one is odd
            : n - Math.floor(i / 2)
    }
    return res;
};

Followed leetcode solution. Isn't very easy to understand.
Checkout this:
http://www.cnblogs.com/grandyang/p/7577878.html
Might be easier to understand.

1110 5.  Print Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {string[][]}
*/
var printTree = function(root) {
    const depth = findDepth(root);
    console.log(depth);
    let width = 0;
    for (let i = 0; i < depth; i++) { // !!!! no depth itself !!!!
        width += 1 << i;
    }
    console.log(width)
    const matrix = Array(depth).fill().map(() => Array(width).fill('')); // !!! carefull man
    recurse(root, 0, 0, width - 1);
    return matrix;
   
    function recurse (node, i, start, end) {
        if (i >= depth) {
            return;
        }
        if (node == null) {
            return;
        }
        const j = Math.floor((start + end) / 2);
        matrix[i][j] = String(node.val); // !!! they want string, not number !!!!
        recurse(node.left, i + 1, start, j - 1);
        recurse(node.right, i + 1, j + 1, end);
    }
};


function findDepth (node) {
    if (node == null) {
        return 0;
    }
    const left = findDepth(node.left);
    const right = findDepth(node.right);
    return Math.max(left, right) + 1;
}

1110 6. Minimum Absolute Difference in BST

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var getMinimumDifference = function(root) {
    // just in order traversal, left self right
    let prevVal = null;
    let min = Infinity;
    recurse(root);
    return min;
   
    function recurse (node) {
        if (node == null) {
            return;
        }
        recurse(node.left);
        if (prevVal != null) {
            const diff = Math.abs(node.val - prevVal);
            min = Math.min(min, diff);
        }
        // !!!! you f***ing update prev!!!!!  
        prevVal = node.val; // !!!! how to prevent this from happening ???
        recurse(node.right);
    }
};

1111 1. Degree of an Array

/**
* @param {number[]} nums
* @return {number}
*/
var findShortestSubArray = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    const dict = {};
    let maxCount = 0;
    let minLen = nums.length;
    nums.forEach((num, i) => {
        dict[num] = dict[num] || {count: 0, start: i};
        dict[num].count++;
        // !!!!! if count is bigger, you will replace minLen, not pick min minLen; only when count equals do you pick min !!!!!
        const len = i - dict[num].start + 1;
        if (dict[num].count === maxCount) {
            minLen = Math.min(minLen, len);
        } else if (dict[num].count > maxCount) {
            maxCount = dict[num].count;
            minLen = len;
        }
    });
    return minLen;
};

1111 2. Longest Word in Dictionary

/**
* @param {string[]} words
* @return {string}
*/
var longestWord = function(words) {
    // TODO: brute force. Need to Checkout the leetcode articles for trie solution.
    const set = new Set(words);
    let resWord = '';
    for (let word of words) {
        let i;
        for (i = 0; i < word.length; i++) {
            const aWord = word.slice(0, i + 1);
            if (!set.has(aWord)) {
                break;
            }
        }
        if (i === word.length) {
            if (resWord.length < word.length || (resWord.length === word.length && word < resWord)) {
                resWord = word;
            }
        }
    }
    return resWord;
};
// I have another solution haven't tried yet.
// use a set to store all words
// then bfs, put all one char words into q,
// get one from q, get next char, (26) children and test if is in the set
// is, put into q and go on
// each time test the longest and earliest.
// return the longest.

NOTE FINISHED

1111 3. String Compression

/**
* @param {character[]} chars
* @return {number}
*/
var compress = function(chars) {
    // I guess it doesn't matter what is in the array after the new length
    if (chars == null || chars.length === 0) {
        return 0;
    }
    if (chars.length === 1) {
        return 1;
    }
    let count = 1;
    let write = 0;
    for (let i = 1; i <= chars.length; i++) {
        if (i === chars.length || chars[i] !== chars[i - 1]) {
            // end group, need to write
            if (count === 1) {
                // !!!! you still need to write, cannot just update count and continue, the char doesn't change but its position changed!!!!,
                chars[write] = chars[i - 1];
                write += count;
            } else {
                const list = [chars[i - 1], ...`${count}`.split('')];
                for (let j = 0; j < list.length; j++) {
                    chars[write + j] = list[j];
                }
                write += list.length;
            }
            count = 1;
        } else {
            count++;
        }
        console.log(write);
    }
    console.log(chars);
    return write;
};