记录

0929 1. Lexicographical Numbers

/**
* @param {number} n
* @return {number[]}
*/
var lexicalOrder = function(n) {
    let cur = 1;
    const result = [];
    // it is interesting: if you don't use a for loop (the i counter), how do you know when you should
    // stop? A: 9999... is the last one. Next one would reach 1 and repeat.
    for (let i = 0; i < n; i++) {
        result.push(cur);
        if (cur * 10 <= n) {
            cur = cur * 10;
        } else {
            if (cur >= n) {
                cur = Math.floor(cur / 10); // !!!! the cur has been visited already, we are calculating the next one!
            }
            cur = cur + 1;
            while (cur % 10 === 0) {
                cur = Math.floor(cur / 10);
            }
        }
    }
    return result;
};

0929 2. Subsets

/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
    if (nums == null || nums.length === 0) {return []}
    const results = [[]];
    const result = [];
    const recurse = (i) => {
        if (i >= nums.length) {return}
        for (let j = i; j < nums.length; j++) {
            result.push(nums[j]);
            results.push([...result]);
            recurse(j + 1); // !!!! j + 1 not i + 1
            result.pop();
        }
    }
    recurse(0);
    return results;
};

TODO:
One solution: iterative.

0930 1. Decode String

/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
    // [number, str]
    if (s == null || s.length === 0) {
        return '';   
    }
    const stack = [];
    let cur = '';
    for (let i = 0; i < s.length; i++) {
        if (isDigit(s[i])) {
            let str = '';
            let j = i;
            while (j < s.length && isDigit(s[j])) {
                str += s[j];
                j++;
            }            
            const count = Number.parseInt(str, 10);
            stack.push([count, cur]);
            cur = '';
            i = j;
        } else if (s[i] === ']') {
            const [count, prevStr] = stack.pop();
            const curStr = cur.repeat(count);
            cur = prevStr + curStr;
        } else {
            cur += s[i];
        }
    }
    return cur;
};

function isDigit (c) {
    // !!!!!! shit! the number could be more than one digit!!!!
    return c.charCodeAt(0) >= '0'.charCodeAt(0) && c.charCodeAt(0) <= '9'.charCodeAt(0);
}

0930 2. Gray Code

/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function(n) {
    if (n === 0) {return [0]}
    let results = [0, 1];
    for (let i = 2; i <= n; i++) { // !!!! including n, this is not a array.length sort of thing !!!
        let copy = [...results].reverse();
        const digit = 1 << (i - 1);
        copy = copy.map(num => num + digit);
        results = [...results, ...copy];
    }
    return results;
};

Make up
0821 1. Non-overlapping Intervals

/**
* Definition for an interval.
* function Interval(start, end) {
*     this.start = start;
*     this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @return {number}
*/
var eraseOverlapIntervals = function(intervals) {
    if (intervals == null || intervals.length === 0) {return 0;}
    intervals.sort((a, b) => a.start - b.start);
    let end = intervals[0].end;
    let res = 0;
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i].start < end) {
            res++;
            end = Math.min(end, intervals[i].end);
        } else {
            end = intervals[i].end;
        }
    }
    return res;
};

Make up
0821 2. Valid Triangle Number

/**
* @param {number[]} nums
* @return {number}
*/
var triangleNumber = function(nums) {
    nums = nums.filter(num => num > 0);
    // !!!!!! Not the first time!!! You didn't sort!!!!!
    nums.sort((a, b) => a - b);
    let res = 0;
    for (let i = 0; i < nums.length - 2; i++) {
        let k = i + 2; // !!!!! Important here!!!! we keep the last value of k when looping j, because
                        // when j++, the new value is surely bigger than before so we don't need to start over
        for (let j = i + 1; j < nums.length - 1; j++) {
            while (k < nums.length && nums[i] + nums[j] > nums[k]) {
                k++;
            }
            res += k - j - 1; // the last k doesn't match the condition, so we subtract one!!!!
        }
    }
    return res;
};

    // we have only 3 numbers, so we don't need to recurse, just do it

Make up

0822 1. Find Right Interval

/**
* Definition for an interval.
* function Interval(start, end) {
*     this.start = start;
*     this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @return {number[]}
*/
var findRightInterval = function(intervals) {
    // first, store the index in the intervals
    // sort the interval
    // for each interval, loop right and find the first of it.
    intervals = intervals.map((item, index) => ({start: item.start, end: item.end, index}));
    // !!!!!!!!! again and again and again!!!! You forgot to sort!!!!!
    intervals.sort((a, b) => a.start - b.start);
    let indices = Array(intervals.length).fill(-1);
    for (let i = 0; i < intervals.length - 1; i++) {
        for (let j = i + 1; j < intervals.length; j++) {
            if (intervals[j].start >= intervals.end) {
                indices[intervals[i].index] = intervals[j].index;
                break;
            }
        }
    }
    return indices;
};
[/i]

[i]NOTE: leetcode uses nodejs to evaluate code which doesn't have some features like object spread. [/i]

1001 1. Binary Tree Right Side View

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
    if (root == null) {return [];}
    const q = [];
    let children = [root];
    const res = [];
    while (q.length > 0 || children.length > 0) {
        if (q.length === 0) {
            res.push(children[children.length - 1].val);   // !!!!! get the value, not the node
            q.push(...children);
            children = [];
        } else {
            const curr = q.shift();
            if (curr.left) {children.push(curr.left);}
            if (curr.right) {children.push(curr.right)}
        }
    }
    return res;
};

1001 2. Unique Binary Search Trees

/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
    const dp = Array(n + 1).fill(0);
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            const left = dp[j - 1];
            const right = dp[i - j];
            dp[i] += left === 0
                ? right
                : right === 0
                    ? left
                    : left * right;
        }
    }
    return dp[n];
};

sicilianee 发表于 2017-10-2 02:07
1001 2. Unique Binary Search Trees

/**

just let d[0] = 1, it would be much simpler.