记录

0903 1. Generate Parentheses

/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
    const combination = [];
    const result = [];
    let leftParenCount = 0;
    const recurse = (remain) => {
        if (leftParenCount === 0 && remain === 0) {
            result.push([...combination]);
            return;
        }
        // left
        if (remain > 0) {
            combination.push('(');
            leftParenCount++;
            recurse(remain - 1);
            combination.pop();
            leftParenCount--;
        }
        if (leftParenCount > 0) {
            combination.push(')');
            leftParenCount--;
            recurse(remain);
            combination.pop();
            leftParenCount++;
        }
    }
    recurse(n);
    return result.map(arr => arr.join(''));
};
TODO: you can also keep a leftCount and a rightCount. This might be easier.

0903 2. Magical String

/**
* @param {number} n
* @return {number}
*/
var magicalString = function(n) {
    const list = [1];
    let i = 0;
    while (list.length < n) {
        const count = list;
        const value = list[list.length - 1];
        const next = getNext(value, count);
        list.push(...next);
        i++; // again, forgot to update loop
    }
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (list[i] === 1) {
            count++;
        }
    }
    return count;
   
   
    function getNext (value, count) {
        const theOther = value === 1 ? 2 : 1;
        return count === 1
            ? [theOther]
            : [value, theOther];
    }
};[/i]

[i]TODO: they have other solutions. But I think this one is easier to understand.[/i]

0904  1. Number of Boomerangs

/**
* @param {number[][]} points
* @return {number}
*/
var numberOfBoomerangs = function(points) {
    if (points == null) {return 0;}
    let num = 0;
    for (let i = 0; i < points.length; i++) {
        const point = points;
        const map = new Map();
        for (let j = 0; j < points.length; j++) {
            if (i !== j) {
                const aPoint = points[j];
                const x = point[0] - aPoint[0];
                const y = point[1] - aPoint[1];
                const dist = x * x + y * y;
                if (map.has(dist)) {
                    map.set(dist, map.get(dist) + 1);
                } else {
                    map.set(dist, 1);
                }
            }
        }
        map.forEach((count) => {
            if (count >= 2) {
                num += count * (count - 1);
            }
        });
     }
    return num;
};

NOTE: problems like this one is misleading. Sometimes the brute force solution is the only practical solution.

0904 2. Binary Tree Preorder Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
    const stack = [];
    const list = [];
    let node = root;
    while (node != null || stack.length > 0) {
        if (node == null) {
            node = stack.pop().right;
        } else {
            list.push(node.val);
            stack.push(node);
            node = node.left;            
        }
    }
    return list;
};

0905 1.  Maximum Product of Three Numbers

/**
* @param {number[]} nums
* @return {number}
*/
var maximumProduct = function(nums) {
    if (nums.length <= 3) {
        return nums.reduce((memo, num) => num * memo);
    }
    nums.sort((a, b) => a - b); // !!! attention when you use js to sort!!!
    const len = nums.length;
    const right = nums[len - 1] * nums[len - 2] * nums[len - 3];
    const left = nums[0] * nums[1] * nums[len - 1];
    return Math.max(left, right);
};

0905 2. Brick Wall

/**
* @param {number[][]} wall
* @return {number}
*/
var leastBricks = function(wall) {
    wall.forEach(row => {
        for (let i = 0; i < row.length; i++) {
            const prev = i === 0 ? 0 : row[i - 1];
            row = row[i] + prev;
        }
    });
    // !!!!! should ignore the last one
    const list = [];
    wall.forEach(row => {
        list.push(...row.slice(0, row.length - 1));
    });
    list.sort((a, b) => a - b);
    let max = 0;
    let count = 0;
    for (let i = 0; i < list.length; i++) {
        if (i === 0 || list[i] !== list[i - 1]) {
            count = 1;
        } else {
            count++;
        }
        max = Math.max(count, max);
    }
    return wall.length - max;
};[/i][/i][i][/i]
TODO: you can just use a hashmap to calculate instead of creating a list and sort it.

0906 1. Integer to Roman

/**
* @param {number} num
* @return {string}
*/
var intToRoman = function(num) {
    const list = [
        {ten: '', five: '', one: 'M'},
        {ten: 'M', five: 'D', one: 'C'},
        {ten: 'C', five: 'L', one: 'X'},
        {ten: 'X', five: 'V', one: 'I'}
    ];
    let base = 1000;
    let result = '';
    for (let i = 0; i < list.length; i++) {
        let value = Math.floor(num / base);
        const item = list[i];
        if (value === 9) {
            result += `${item.one}${item.ten}`;
        } else if (value === 4) {
            result += `${item.one}${item.five}`;
        } else if (value > 0 && value <= 3) {
            while (value > 0) {
                result += `${item.one}`;
                value--;      
            }
        } else if (value >= 5 && value < 9) {
            result += `${item.five}`;
            while (value > 5) {
                result += `${item.one}`;
                value--;
            }
        }
        num = num % base;
        base = base / 10;
    }
    return result;
};

0906 2. Bulb Switcher II

/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var flipLights = function(n, m) {
    if (m * n === 0) {return 1;}
    if (n === 1) {return 2;}
    if (n === 2 && m === 1) {return 3;}
    if (n === 2) {return 4;}
    if (m === 1) {return 4;}
    if (m === 2) {return 7;}
    return 8;
};

0907 1. Predict the Winner

/**
* @param {number[]} nums
* @return {boolean}
*/
var PredictTheWinner = function(nums) {
    const len = nums.length;
    const dict = Array(len).fill().map(() => Array(len));
    for (let step = 0; step < len; step++) {
        for (let i = 0; i + step < len; i++) {
            let j = i + step;
            if (step === 0) {
                dict[i][j] = {first: nums[i], second: 0};
            } else {
                let takeI = nums[i] + dict[i + 1][j].second;
                let takeJ = nums[j] + dict[i][j - 1].second;
                if (takeI > takeJ) {
                    dict[i][j] = {
                        first: takeI,
                        second: dict[i + 1][j].first
                    }
                } else {
                    dict[i][j] = {
                        first: takeJ,
                        second: dict[i][j - 1].first
                    }
                }
            }
        }
    }
    const {first, second} = dict[0][len - 1];
    return first >= second; // !!! should include equals
};

sicilianee 发表于 2017-9-15 12:00
0907 1. Predict the Winner

/**

TODO: since the only thing that we care is the difference. So we can store only the difference in the DP cells.