记录

0927 1. Next Closest Time

/**
* @param {string} time
* @return {string}
*/
var nextClosestTime = function(time) {
    const nums = [time[0], time[1], time[3], time[4]].map(str => Number.parseInt(str, 10));
    const sorted = [...nums].sort((a, b) => a - b);
    for (let i = nums.length - 1; i>= 0; i--) {
        for (let j = 0; j < sorted.length; j++) {
            if (sorted[j] > nums[i]) {
                const cache = nums[i];
                nums[i] = sorted[j];
                if (isValid(nums)) {
                    let start = i + 1;
                    // !!!! need to change all smaller to smallest
                    while (start < nums.length) {
                        nums[start] = sorted[0];
                        start++;
                    }
                    return `${nums[0]}${nums[1]}:${nums[2]}${nums[3]}`;
                }
                // !!!!! need to restore it if not successful
                nums[i] = cache;
            }
        }
    }
    const smallest = sorted[0];
    return `${smallest}${smallest}:${smallest}${smallest}`;   
};

function isValid (nums) {
    const hour = nums[0] * 10 + nums[1];
    const minute = nums[2] * 10 + nums[3];
    return hour < 24 && minute < 60;
}

sicilianee 发表于 2017-9-28 11:30
0927 1. Next Closest Time

/**

You could do without replacement, just put it together manually and return?

0927 2. Binary Search Tree Iterator

/**
* Definition for binary tree
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/

/**
* @constructor
* @param {TreeNode} root - root of the binary search tree
*/
var BSTIterator = function(root) {
    this.stack = [];
    this.node = root;
};


/**
* @this BSTIterator
* @returns {boolean} - whether we have a next smallest number
*/
BSTIterator.prototype.hasNext = function() {
    if (this.node) {
        this.stack.push(this.node);
        this.node = this.node.left;
        this.hasNext();
        return true;
    } else {
        if (this.stack.length > 0) {
            return true;
        } else {
            return false;
        }
    }
};

/**
* @this BSTIterator
* @returns {number} - the next smallest number
*/
BSTIterator.prototype.next = function() {
    if (!this.hasNext()) {
        throw new Error('No next item');
    }
    const node = this.stack.pop();
    this.node = node.right;
    return node.val; // !!!!!! ask you to return the number, not the node itself
};

/**
* Your BSTIterator will be called like this:
* var i = new BSTIterator(root), a = [];
* while (i.hasNext()) a.push(i.next());
*/

0918. Make up . Single Number II

/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
    let result = 0;
    for (let i = 0; i <= 31; i++) { // !!! 32 bits, what the heck is 26?
        const mask = 1 << i;
        let count = 0;
        for (let num of nums) {
            if ((num & mask) !== 0) {
                count++;
            }
        }
        if (count % 3 !== 0) {
            result += mask;
        }
    }
    return result;
};

0928 1.  License Key Formatting

/**
* @param {string} S
* @param {number} K
* @return {string}
*/
var licenseKeyFormatting = function(S, K) {
    const chars = S.split('').filter(c => c !== '-').map(c => c.toUpperCase());
    let i = chars.length - 1;
    let count = 0;
    while (i >= 0) {
        count++;
        if (count === K && i !== 0) { // !!! i cannot be the first one
            chars.splice(i, 0, '-');
            count = 0;
        }
        i--;
    }
    return chars.join('');
};

0928 2. Best Time to Buy and Sell Stock

/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
    if (prices == null || prices.length == 0) {return 0;}
    let max = 0;
    let gain = 0;
    for (let i = prices.length - 1; i >= 0; i--) {
        max = Math.max(max, prices[i]);
        gain = Math.max(gain, max - prices[i]);
    }
    return gain;
};

sicilianee 发表于 2017-9-29 13:20
0928 2. Best Time to Buy and Sell Stock

/**

http://www.cnblogs.com/grandyang/p/4280131.html

simpler

0917. Make up.  Add Strings

/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var addStrings = function(num1, num2) {
    const nums1 = num1.split('').map(str => Number.parseInt(str, 10)).reverse();
    const nums2 = num2.split('').map(str => Number.parseInt(str, 10)).reverse();
    const len = Math.max(nums1.length, nums2.length);
    let shorter = nums1.length > nums2.length ? nums2 : nums1;
    shorter.push(...Array(len - shorter.length).fill(0));
    const results = Array(len);
    let carry = 0;
    for (let i = 0; i < len; i++) {
        const value = nums1 + nums2[i] + carry;
        carry = value > 9 ? 1 : 0;
        results[i] = value > 9 ? (value - 10) : value;
    }
    if (carry > 0) {
        results.push(1);
    }
    return results.reverse().join('');
   
};[/i][/i]

sicilianee 发表于 2017-9-29 13:42
0917. Make up.  Add Strings

/**

Using index no need to revese the list.  See grandyang solution.

0825. Make up. Unique Paths

/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
    const dp = Array(m).fill().map(() => Array(n));
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i === m - 1 && j === n - 1) {
                dp[i][j] = 1
            } else {
                const down = i + 1 < m ? dp[i + 1][j] : 0;
                const right = j + 1 < n ? dp[i][j + 1] : 0;
                dp[i][j] = down + right;      
            }

        }
    }
    return dp[0][0];
};


Better:

http://bangbingsyb.blogspot.com/2014/11/leetcode-unique-paths-i-ii.html

1. start from top left is the same
2. init all with 1 and start from second row/col