记录

0907 2. Kth Smallest Element in a Sorted Matrix

/**
* @param {number[][]} matrix
* @param {number} k
* @return {number}
*/
var kthSmallest = function(matrix, k) {
    const len = matrix.length;
    let left = matrix[0][0];
    let right = matrix[len - 1][len - 1];
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const count = lessEqualCount(mid);
        if (count < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
   
   
    function lessEqualCount (num) {
        let i = len - 1;
        let j = 0;
        let count = 0;
        while (i >= 0 && j < len) {
            const value = matrix[i][j];
            if (value <= num) {
                j++;
                count += i + 1;
            } else {
                i--;
            }
        }
        return count;
    }
};

TODO: not totally understand yet.

0908 1. Binary Watch

/**
* @param {number} num
* @return {string[]}
*/
var readBinaryWatch = function(num) {
    const list = [];
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m < 60; m++) {
            const bitsCount = countBits(h) + countBits(m);
            
            if (bitsCount === num) {
                const mStr = m < 10 ? `0${m}` : `${m}`;
                list.push(`${h}:${mStr}`);
            }
        }
    }
    return list;
};

function countBits (num) {
    let count = 0;
    for (let i = 0; i < 32; i++) {
        const mask = 1 << i;
        if ((mask & num) !== 0) {
            count++;
        }
    }
    return count;
}

IMPORTANT: bitwise &, |, <<, >> in js, has very low precedence, must put parentheses around them.
mask & num !== 0 gives you wrong answer

TODO:
I still don't understand the complexity of this thing. What about picking n from 10 bits to light up? Won't that has fewer cases?

0908 2. Intersection of Two Arrays II

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
    const map = new Map();
    nums1.forEach(num => {
        if (map.has(num)) {
            map.set(num, map.get(num) + 1);
        }  else {
            map.set(num, 1);
        }
    });
    const list = [];
    nums2.forEach(num => {
        if (map.has(num) && map.get(num) > 0) {
            list.push(num);
            map.set(num, map.get(num) - 1);
        }
    });
    return list;
};

0909 1.  Is Subsequence

/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
    if (!s) {return true;}
    if (!t) {return false;}
    if (s.length > t.length) {return false;}
    let ps = 0;
    let pt = 0;
    while (ps < s.length) {
        const cs = s[ps];
        while (pt < t.length && cs !== t[pt]) {
               pt++;
        }
        if (pt >= t.length) {
            return false;
        } else {
            ps++;
            pt++;
        }
    }
    return true;
};

0909 2. Maximum Product of Word Lengths

/**
* @param {string[]} words
* @return {number}
*/
var maxProduct = function(words) {
    const bins = words.map(word => {
        let bin = 0;
        word.split('').forEach(c => {
            const mv = c.charCodeAt(0) - 'a'.charCodeAt(0); // !!!
            bin = (bin | (1 << mv)); // !!!
        });
        return bin;
    });
    console.log(bins)
    let max = 0;
    for (let i = 0; i < bins.length; i++) {
        for (j = i + 1; j < bins.length; j++) {
            if ((bins & bins[j]) === 0) { // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! REDICULOUS! PAY ATTENTION TO THIS!!!
                max = Math.max(max, words[i].length * words[j].length);
            }
        }
    }
    return max;
};


Many things to pay attention to in this problem.
Basically using js to bo bit-wise manipulation is very error-prone. Should be super careful.[/i]
[i]1. put parenthesis around bit-wise & | << ^ etc.[/i]
[i]2. no char in js. get ascii code of char: str.charCodeAt(index)[/i]

0910 1. Different Ways to Add Parentheses

/**
* @param {string} input
* @return {number[]}
*/
var diffWaysToCompute = function(input) {
    const nums = input.split(/\+|-|\*/).map(numStr => Number.parseInt(numStr, 10));
    const operators = input.split('').filter(c => ['+', '-', '*'].includes(c));
    const len = nums.length;
    const matrix = Array(len).fill().map(() => Array(len));
    for (let step = 0; step < len; step++) {
        for (let start = 0; start + step < len; start++) {
            if (step === 0) {
                matrix[start][start] = [nums[start]];
            } else {
                const end = start + step;
                matrix[start][end] = [];
                for (let midEnd = start; midEnd < end; midEnd++) { // start and end, not 0 and len - 1
                    const firstResults = matrix[start][midEnd];
                    const secondResults = matrix[midEnd + 1][end];
                    const operator = operators[midEnd];
                    matrix[start][end].push(...getResults(firstResults, secondResults, operator));
                }
            }
        }
    }
    return matrix[0][len - 1];
};

function getResults (nums1, nums2, operator) {
    const results = [];
    nums1.forEach(num1 => {
        nums2.forEach(num2 => {
            let result;
            switch (operator) {
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num1 - num2;
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                default:
                    throw new Error('Unknow type');
            }
            results.push(result);
        })
    });
    return results;
}

0910 2. Reconstruct Original Digits from English

/**
* @param {string} s
* @return {string}
*/
var originalDigits = function(s) {
    const map = new Map();
    const nums = [];
    const chars = s.split('');
    chars.forEach(c => {
        if (map.has(c)) {
            map.set(c, map.get(c) + 1);
        } else {
            map.set(c, 1);
        }
    });
    const decreaseCount = charList => charList.forEach(c => map.set(c, map.get(c) - 1));
    chars.forEach(c => {
        switch (c) {
            case 'z':
                nums.push(0);
                decreaseCount(['z', 'e', 'r', 'o']);
                break;
            case 'w':
                nums.push(2);
                decreaseCount(['t', 'w', 'o']);
                break;
            case 'u':
                nums.push(4);
                decreaseCount(['f', 'o', 'u', 'r']);
                break;
            case 'x':
                nums.push(6);
                decreaseCount(['s', 'i', 'x']);
                break;
            case 'g':
                nums.push(8);
                decreaseCount(['e', 'i', 'g', 'h', 't']);
                break;
            default:
                break;
        }
    });
    const dict = {
        o: {num: 1,str: 'one'},
        h: {num: 3, str: 'three'},
        f: {num: 5, str: 'five'},
        s: {num: 7, str: 'seven'},
        i: {num: 9, str: 'nine'}
    }
    Object.keys(dict).forEach(c => {
        if (map.has(c)) {
            const count = map.get(c);
            for (let i = 0; i < count; i++) {
                nums.push(dict[c].num);
                dict[c].str.split('').forEach(c => {
                    map.set(c, map.get(c) - 1);
                });
            }
        }
    });
    const nineCount = map.get('i') || 0;
    for (let i = 0; i < nineCount; i++) {
        nums.push(9);
    }
    nums.sort((a, b) => a - b);
    return nums.join('');
};

TODO: your code is so complex. Redo it. 1. the two rounds could merge
2. no need for the loop. You could just do the math.

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

0911 1. Base 7

/**
* @param {number} num
* @return {string}
*/
var convertToBase7 = function(num) {
    if (num === 0) {return '0';}
    const neg = num < 0;
    num = Math.abs(num);
    const list = [];
    while (num > 0) {
        list.push(num % 7);
        num = Math.floor(num / 7); // attention!!!!!
    }
    const str = list.reverse().join('')
    return neg ? `-${str}` : str;
};

0911 2. Permutations

/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
    const list = [];
    const recurse = (i) => {
        if (i === nums.length - 1) {
            list.push([...nums]);  // copy the list to ANOTHER list, not directly push to the result list
            return;
        }
        for (let j = i; j < nums.length; j++) {
            ;[nums, nums[j]] = [nums[j], nums[i]];
            recurse(i + 1);
            ;[nums[j], nums[i]] = [nums[i], nums[j]];
        }
    }
    recurse(0);
    return list;
};[/i][/i][/i]

0912 1. Missing Number

/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
    const n = nums.length;
    let sum = 0;
    for (let i = 0; i <= n; i++) {
        sum += i;
    }
    nums.forEach(num => {
        sum -= num;
    })
    return sum;
};