记录

1013 1. Symmetric Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
    if (root == null) {return true;}
    return recurse(root.left, root.right);
   
    function recurse (left, right) {
        if (left == null && right == null) {return true;}
        if (left == null || right == null) {return false;}
        if (left.val != right.val) {return false;}
        const leftRes = recurse(left.left, right.right);
        const rightRes = recurse(left.right, right.left);
        return leftRes && rightRes;
    }
};

1013 2. Solve the Equation

/**
* @param {string} equation
* @return {string}
*/
var solveEquation = function(equation) {
    const [left, right] = equation.split('=');
    const [xCoeLeft, numCoeLeft] = parse(left);
    const [xCoeRight, numCoeRight] = parse(right);
    const xCoe = xCoeLeft - xCoeRight;
    const numCoe = numCoeRight - numCoeLeft;
    if (xCoe === 0) {
        return numCoe === 0 ? 'Infinite solutions' : 'No solution';
    } else {
        return `x=${numCoe / xCoe}`;
    }
   
   
    function parse (exp) {
        const operators = exp.split('').filter(c => ['+', '-'].includes(c)).map(c => c === '+' ? 1 : -1);
        const operands = exp.split(/\+|-/).filter(c => c); // !!! remove empty ones
        if (operators.length !== operands.length) { // !!!!! canot decide by if first one is -1, cause second one could be -1
            operators.unshift(1); // !!!! here it is already number, not string any more!!! !!! unshift not push !!!!!
        }
        let xCoe = 0;
        let numCoe = 0;
        for (let i = 0; i < operands.length; i++) {
            const operand = operands[i];
            if (operand[operand.length - 1] === 'x') {
                let coe = 0;
                if (operand === 'x') {
                    coe = 1;
                } else {
                    coe = Number.parseInt(operand.slice(0, operand.length - 1));
                }
                xCoe += coe * operators[i];
            } else {
                const coe = Number.parseInt(operand, 10);
                numCoe += coe * operators[i];
            }
        }
        return [xCoe, numCoe];
    }
};


Too many details.

1014 1. Pascal's Triangle

/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(numRows) {
    if (numRows < 1) {return [];}
    const res = [[1]];
    for (let i = 1; i < numRows; i++) {
        const list = [];
        for (let j = 0; j < i + 1; j++) {
            const prev = j - 1 >= 0 ? res[i - 1][j - 1] : 0;
            const next = j < i ? res[i - 1][j] : 0
            list[j] = prev + next;
        }
        res.push(list);
    }
    return res;
};

1014 2.  Ones and Zeroes

/**
* @param {string[]} strs
* @param {number} m
* @param {number} n
* @return {number}
*/
// 10, 0001, 111001, 1, 0  ...  5, 3
var findMaxForm = function(strs, m, n) {
    if (strs == null || strs.length === 0) {return 0;}
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    for (let str of strs) {
        const [zero, one] = count(str);
        for (let i = m; i >= zero; i--) {
            for (let j = n; j >= one; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
            }
        }
    }
    return dp[m][n];
};

function count (str) {
    let one = 0;
    let zero = 0;
    for (let c of str) {
        if (c === '1') {
            one++;
        } else {
            zero++;
        }
    }
    return [zero, one]; // !!!!!! It is an array, not object, you must change here if you want to change order, not just the place of destructruing!!!! Stupid.
}

Make up
0815 1. Plus One

/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
    digits.reverse();
    // !!!! the most important one, add the 1
    let carry = 1;
    for (let i = 0; i < digits.length; i++) {
        const val = carry + digits[i];
        digits[i] = val % 10;
        carry = Math.floor(val / 10);
    }
    if (carry > 0) {
        digits.push(1);
    }
    return digits.reverse();
};

Make up

0815 2. Increasing Subsequences

/**
* @param {number[]} nums
* @return {number[][]}
*/
var findSubsequences = function(nums) {
    if (nums == null || nums.length < 2) {
        return [];
    }
    let res = [[]];
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const start = map.has(num) ? map.get(num) : 0;
        const len = res.length;
        map.set(num, len);
        for (let i = start; i < len; i++) {
            const list = res[i];
            if (list.length === 0 || list[list.length - 1] <= num) {  // !!!! the empty case
                const listCopy = list.slice();
                listCopy.push(num);
                res.push(listCopy);
            }
        }
    }
    return res.filter(list => list.length > 1);
};

This last one is exhausting. So hard to get right.

Mark. Cleaned up all our debts today. Could have a fresh start from tomorrow.

1015 1. Search a 2D Matrix II

/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
    if (matrix == null || matrix.length === 0) {
        return false;
    }
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    let i = rowLen - 1;
    let j = 0;
    while (i >= 0 && j < colLen) {
        const num = matrix[i][j];
        if (num === target) {
            return true;
        } else if (target < num) { // !!! which one goes first !!!
            i--;
        } else {
            j++;
        }
    }
    return false;
};

1015 2. Power of Four

/**
* @param {number} num
* @return {boolean}
*/
var isPowerOfFour = function(num) {
    if (num <= 0) {return false;}
    while (num !== 1) {
        if (num % 4 !== 0) {return false;}
        num = num >>> 2;
    }
    return true;
};

sicilianee 发表于 2017-10-16 11:59
1015 2. Power of Four

/**

Better solutions:
http://www.cnblogs.com/grandyang/p/5403783.html