记录

1205 4. Palindrome Permutation II

/**
* @param {string} s
* @return {string[]}
*/
var generatePalindromes = function(s) {
    if (s == null || s.length === 0) {
        return [];
    }
    const map = new Map();
    for (let c of s) {
        const val = map.get(c) || 0;
        map.set(c, val + 1);
    }
    if (map.size === 1) { // !!!!! this special check help us pass oj
        // 1. when only one element, wrong answer if we don't guard
        // 2. when long s but all same char, tle if we don't guard
        return [s];
    }
    let oddCount = 0;
    for (let val of map.values()) {
        if (val % 2 === 1) {
            oddCount++;
            if (oddCount > 1) {
                return [];
            }
        }
    }
    let str = '';
    let mid = '';
    for (let [c, val] of map.entries()) {
        const count = Math.trunc(val / 2);
        const aStr = c.repeat(count);
        if (val % 2 === 1) {
            mid = c;
        }
        str += aStr;
    }
    const set = new Set();
    const list = str.split('');
    permute(0);
    return [...set].map(str => str + mid + str.split('').reverse().join(''));
   
   
    function permute (start) {
        if (start === list.length - 1) {
            set.add(list.join(''));
            return;
        }
        for (let i = start; i < list.length; i++) {
            // !!! if we just use a set to deal with duplicates, no need to test for the start
            swap(start, i);
            permute(start + 1);
            swap(start, i);
        }
    }
   
   
    function swap (i, j) {
        ;[list[i], list[j]] = [list[j], list[i]];
    }
   
};

sicilianee 发表于 2017-12-6 13:54
1205 4. Palindrome Permutation II

/**

version 1

/**
* @param {string} s
* @return {string[]}
*/
var generatePalindromes = function(s) {
    if (s == null || s.length === 0) {
        return [];
    }
    const map = new Map();
    for (let c of s) {
        const val = map.get(c) || 0;
        map.set(c, val + 1);
    }
    if (map.size === 1) { // !!!!! this special check help us pass oj
        // 1. when only one element, wrong answer if we don't guard
        // 2. when long s but all same char, tle if we don't guard
        return ;
        // ??? maybe we can also do pruning, read the article.
    }
    let oddCount = 0;
    for (let val of map.values()) {
        if (val % 2 === 1) {
            oddCount++;
            if (oddCount > 1) {
                return [];
            }
        }
    }
    let str = '';
    let mid = '';
    for (let [c, val] of map.entries()) {
        const count = Math.trunc(val / 2);
        const aStr = c.repeat(count);
        if (val % 2 === 1) {
            mid = c;
        }
        str += aStr;
    }
    const set = new Set();
    const list = str.split('');
    permute(0);
    return [...set].map(str => str + mid + str.split('').reverse().join(''));
   
   
    function permute (start) {
        if (start === list.length - 1) {
            set.add(list.join(''));
            return;
        }
        for (let i = start; i < list.length; i++) {
            // !!! if we just use a set to deal with duplicates, no need to test for the start
            swap(start, i);
            permute(start + 1);
            swap(start, i);
        }
    }
   
   
    function swap (i, j) {
        ;[list[i], list[j]] = [list[j], list[i]];
    }
   
};

// !!! note: how does the article handle the case of a single char?
// they stop at start === length, and add the mid there. So that will be executed once. For your case it won't be executed a single time.

version 2

果然剪枝之后是可以过的，不需要判断都是一样的case

/**
* @param {string} s
* @return {string[]}
*/
// !!! version 2
var generatePalindromes = function(s) {
    if (s == null || s.length === 0) {
        return [];
    }
    const map = new Map();
    for (let c of s) {
        const val = map.get(c) || 0;
        map.set(c, val + 1);
    }
    let oddCount = 0;
    for (let val of map.values()) {
        if (val % 2 === 1) {
            oddCount++;
            if (oddCount > 1) {
                return [];
            }
        }
    }
    let str = '';
    let mid = '';
    for (let [c, val] of map.entries()) {
        const count = Math.trunc(val / 2);
        const aStr = c.repeat(count);
        if (val % 2 === 1) {
            mid = c;
        }
        str += aStr;
    }
    const set = new Set();
    const list = str.split('');
    permute(0);
    return [...set].map(str => str + mid + str.split('').reverse().join(''));
   
   
    function permute (start) {
        if (start === list.length) {
            set.add(list.join(''));
            return;
        }
        for (let i = start; i < list.length; i++) {
            if (i !== start && list[i] === list[start]) {continue}
            swap(start, i);
            permute(start + 1);
            swap(start, i);
        }
    }
   
   
    function swap (i, j) {
        ;[list[i], list[j]] = [list[j], list[i]];
    }
   
};

// !!! note: how does the article handle the case of a single char?
// they stop at start === length, and add the mid there. So that will be executed once. For your case it won't be executed a single time.

sicilianee 发表于 2017-12-6 14:05
version 2

果然剪枝之后是可以过的，不需要判断都是一样的case

两点不同：
1. 剪枝
2. stop at length， not length -1， 针对single char的情况

1205 5. Boundary of Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var boundaryOfBinaryTree = function(root) {
    // left bound
    // leaves
    // right bound, using stack
    if (root == null) {return []}
    const res = [];
    if (!isLeaf(root)) {
        res.push(root.val);
    }
    // go left
    let node = root.left;
    while (node != null) {
        if (!isLeaf(node)) {
            res.push(node.val);
        }
        if (node.left != null) {
            node = node.left;
        } else {
            node = node.right;
        }
    }
    addLeaves(root);
    const stack = [];
    node = root.right;
    while (node != null) {
        if (!isLeaf(node)) {
            stack.push(node.val);
        }
        if (node.right != null) {
            node = node.right;
        } else {
            node = node.left;
        }
    }
    while (stack.length > 0) {
        res.push(stack.pop());
    }
    return res;
   
    function addLeaves (node) {
        if (isLeaf(node)) {
            res.push(node.val);
        }
        if (node.left != null) {
            addLeaves(node.left);
        }
        if (node.right != null) {
            addLeaves(node.right);
        }
    }
   
   
};

function isLeaf (node) {
    return node !== null && node.left == null && node.right == null;
}

1205 6. One Edit Distance

/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isOneEditDistance = function(s, t) {
    if (s == null || t == null) {return false}
    const sLen = s.length;
    const tLen = t.length;
    if (Math.abs(sLen - tLen) > 1) {return false;}
    if (s === t) {return false;} // !!! exactly one edit aprt, cannot be the same
    const len = Math.min(sLen, tLen);
    for (let i = 0; i < len; i++) {
        if (s[i] !== t[i]) {
            if (sLen === tLen) {
                return s.slice(0, i) + s.slice(i + 1) === t.slice(0, i) + t.slice(i + 1);
            } else if (sLen > tLen) {
                return s.slice(0, i) + s.slice(i + 1) === t;
            } else {
                return t.slice(0, i) + t.slice(i + 1) === s;
            }
        }
    }
    // !!! you know why we could reach here? cuz it could be the last one more char that's diff
    return true;
};

1206 1. Minimum Factorization



/**
* @param {number} a
* @return {number}
*/
var smallestFactorization = function(a) {
    if (a === 1) {return 1}
    let str = '';
    for (let i = 9; i >= 2; i--) { // !!!! must start with bigger ones
        while (a % i === 0) {
            a = a / i;
            str = i + str;
        }
    }
    if (a > 1) {return 0}
    const num = Number.parseInt(str, 10);
    return num > Math.pow(2, 31) - 1 ? 0 : num; // !!! cannot use (2 << 31) - 1, cuz 2 << 31 that would be 0
};

1206 2. Mini Parser

/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
*     Return true if this NestedInteger holds a single integer, rather than a nested list.
*     @return {boolean}
*     this.isInteger = function() {
*         ...
*     };
*
*     Return the single integer that this NestedInteger holds, if it holds a single integer
*     Return null if this NestedInteger holds a nested list
*     @return {integer}
*     this.getInteger = function() {
*         ...
*     };
*
*     Set this NestedInteger to hold a single integer equal to value.
*     @return {void}
*     this.setInteger = function(value) {
*         ...
*     };
*
*     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
*     @return {void}
*     this.add = function(elem) {
*         ...
*     };
*
*     Return the nested list that this NestedInteger holds, if it holds a nested list
*     Return null if this NestedInteger holds a single integer
*     @return {NestedInteger[]}
*     this.getList = function() {
*         ...
*     };
* };
*/
/**
* @param {string} s
* @return {NestedInteger}
*/
var deserialize = function(s) {
    // 324
    // [123,[456,[789]]]
    // 0-9, [, - ,, ].
    if (s == null || s.length === 0) {
        return null;
    }
    const list = [];
    const isNum = c => c === '-' || c >= '0' && c <= '9';
    for (let i = 0; i < s.length; i++) {
        if (isNum(s[i])) {
            let j = i;
            while (j < s.length && isNum(s[j])) {
                j++;
            }
            const str = s.slice(i, j);
            list.push(Number.parseInt(str, 10));
            i = j - 1;
        } else if (s[i] === ',') {
            continue;
        } else {
            list.push(s[i]);
        }
    }
    // [, ], num
    // single num
    // !!! the idea is to create a dummmy nested list to hold everything and return the content of it in the end
    const dummy = new NestedInteger();
    const stack = [dummy]; // stack of lists
    for (let i = 0; i < list.length; i++) {
        const el = list[i];
        if (el === '[') {
            const nested = new NestedInteger();
            stack.push(nested);
        } else if (el === ']') {
            const top = stack.pop();
            stack[stack.length - 1].add(top);
        } else {
            const nested = new NestedInteger();
            nested.setInteger(el);
            stack[stack.length - 1].add(nested);
        }
    }
    return dummy.getList()[0]
};

傻逼题，傻逼题，傻逼题
建一个dummy nested integer

1206 3. Largest BST Subtree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var largestBSTSubtree = function(root) {
    let max = 0;
    recurse(root);
    return max;
   
    // max, min, size
    function recurse (node) {
        if (node == null) {
            return {
                max: -Infinity,
                min: Infinity,
                size: 0
            };
        }
        const left = recurse(node.left);
        const right = recurse(node.right);
        const self = {max: 0, min: 0, size: 0};
        if (left.size >= 0 && right.size >= 0 && node.val > left.max && node.val < right.min) { // !!! equal to 0
            self.size = left.size + right.size + 1;
            self.min = Math.min(node.val, left.min); // !!!! might have null node returned value
            self.max = Math.max(node.val, right.max);
        } else {
            self.size = -1;
        }
        max = Math.max(max, self.size);
        return self;
    }
};

1206 4. Line Reflection

/**
* @param {number[][]} points
* @return {boolean}
*/
var isReflected = function(points) {
    if (points == null || points.length === 0) {
        return true; // ???
    }
    let min = Infinity;
    let max = -Infinity;
    const set = new Set();
    for (let [x, y] of points) {
        min = Math.min(x, min);
        max = Math.max(x, max);
        set.add(`${x}:${y}`);
    }
    const mid = (max + min) / 2;
    for (let [x, y] of points) {
        const newX = 2 * mid - x;
        if (!set.has(`${newX}:${y}`)) {
            return false;
        }
    }
    return true;
};