记录

sicilianee 发表于 2017-12-1 12:07
1130 1. Factor Combinations

/**

主要是第一轮取数的时候不能够取n自己，而后面取得时候是可以的，这样就不是一个完全的recursion了， 不是完全的子问题。要转换成子问题来做的话，我看到一种方法是test list 的size
http://www.cnblogs.com/grandyang/p/5332722.html
解法一

sicilianee 发表于 2017-12-1 12:24
主要是第一轮取数的时候不能够取n自己，而后面取得时候是可以的，这样就不是一个完全的recursion了， 不 ...

而且还要注意直接取的时候，要判断n >= i, 总之就是有很多麻烦的地方。

1130 2. Maximum Size Subarray Sum Equals k

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxSubArrayLen = function(nums, k) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    const map = new Map();
    let maxLen = 0;
    for (let i = 0; i < nums.length; i++) {
        const prev = i === 0 ? 0 : nums[i - 1];
        nums[i] = prev + nums[i];
        if (nums[i] === k) {
            maxLen = i + 1;
        } else {
            const target = nums[i] - k; // !!!! which one goes first !!!!
            if (map.has(target)) {
                maxLen = Math.max(maxLen, i - map.get(target));
            }
        }
        // map.set(nums[i], (map.get(nums[i]) || i)); // !!!! IMPORTANT !!!!! Here is one example where you cannot just use || to
        // simulate the putIfAbsent: it could be 0 and you don't want it to update !!!
        if (!map.has(nums[i])) {
            map.set(nums[i], i);
        }
    }
    return maxLen;
};

1130 3. Count Univalue Subtrees

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countUnivalSubtrees = function(root) {
    if (root == null) {return 0;} // !!! test null
    let count = 0;
    isUnivalSubtree(root);
    return count;
   
    function isUnivalSubtree (node) {
        let good = true;
        if (node.left != null) {
            const val = isUnivalSubtree(node.left);
            if (node.val !== val) {
                good = false; // !!!! don't return early. Even if self is not, children could still be
                // !!! The problem demonstrates itself when: the name of the function doesn't necessarily tell what exactly
                // what the function does, as in this case. If you were jut checking if this is univalue subtree, you could
                // return early. But you are also traversing and counting along the way, and you just use that return value
                // to identify if it is. !!! So better change the name of the function to traverse.
            }
        }
        if (node.right != null) {
            const val = isUnivalSubtree(node.right);
            if (node.val !== val) {
                good = false;
            }
        }
        if (good) {
            count++;
            return node.val;
        } else {
            return null;
        }
    }
};

1130 4.  Construct Binary Tree from String

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {string} s
* @return {TreeNode}
*/
var str2tree = function(s) {
    if (s == null || s.length === 0) {return null}
    // get self value
    let i = 0;
    while (i < s.length && s[i] !== '(') {
        i++;
    }
    const selfPart = s.slice(0, i);
    let count = 0;
    let j = i;
    while (j < s.length) {
        if (s[j] === '(') {
            count++;
        } else if (s[j] === ')') {
            count--;
        }
        if (count === 0) {
            break;
        }
        j++
    }
    const leftPart = s.slice(i + 1, j);
    const rightPart = s.slice(j + 2, s.length - 1);
    const self = new TreeNode(Number.parseInt(selfPart, 10));
    if (leftPart) {
        self.left = str2tree(leftPart);
    }
    if (rightPart) {
        self.right = str2tree(rightPart);
    }
    return self;
};

1130 5. Group Shifted Strings

/**
* @param {string[]} strings
* @return {string[][]}
*/
var groupStrings = function(strings) {
    if (strings == null || strings.length === 0) {
        return [];
    }
    const single = [];
    const map = new Map();
    for (let str of strings) {
        if (str.length === 1) {
            single.push(str);
        } else {
            let diffs = [];
            for (let i = 1; i < str.length; i++) {
                const curr = str[i].charCodeAt(0);
                const prev = str[i - 1].charCodeAt(0);
                const diff = curr > prev ? curr - prev : curr + 26 - prev;
                diffs.push(diff);
            }
            const key = diffs.join(',');
            const val = map.get(key) || [];
            val.push(str);
            map.set(key, val);
        }
    }
    // !!!! single could be empty !!!  ?? how to uniform it?
    const res = [...map.values()]
    if (single.length > 0) {
        res.push(single);
    }
    return res;
};

sicilianee 发表于 2017-12-1 13:48
1130 5. Group Shifted Strings

/**

有一个uniform的办法，但是做法变了：
不用错位比较，所有位都和第一位比较，第一位也算上，这样一位的就不用单独拎出来了。

1130 6. Binary Tree Longest Consecutive Sequence II

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var longestConsecutive = function(root) {
    let maxLen = 0;
    recurse(root);
    return maxLen;
   
    function recurse (node) {
        if (node == null) {
            return {
                inc: [],
                dec: []
            }
        } else {
            const left = recurse(node.left);
            const right = recurse(node.right);
            let leftInc, leftDec, rightInc, rightDec;
            if (node.left && node.val - node.left.val === 1) {
                leftInc = left.inc;
            } else {
                leftInc = [];
            }
            if (node.left && node.val - node.left.val === -1) {
                leftDec = left.dec;
            } else {
                leftDec = [];
            }
            if (node.right && node.val - node.right.val === 1) {
                rightInc = right.inc;
            } else {
                rightInc = [];
            }
            if (node.right && node.val - node.right.val === -1) {
                rightDec = right.dec;
            } else {
                rightDec = [];
            }
            maxLen = Math.max(leftInc.length + rightDec.length + 1, leftDec.length + rightInc.length + 1, maxLen); // !!! and the maxLen itself, or what are you comparing with? !!!
            const inc = leftInc.length > rightInc.length ? [...leftInc, node.val] : [...rightInc, node.val];
            const dec = leftDec.length > rightDec.length ? [...leftDec, node.val] : [...rightDec, node.val];
            return {
                inc,
                dec
            };
        }
    }
};

处理不过来就分类

sicilianee 发表于 2017-12-1 14:31
1130 6. Binary Tree Longest Consecutive Sequence II

/**

1. 分类讨论，增和减
2. 只用存count，不用存实际list

sicilianee 发表于 2017-12-1 14:37
1. 分类讨论，增和减
2. 只用存count，不用存实际list

https://leetcode.com/articles/bi ... cutive-sequence-ii/