记录

0830 1. Roman to Integer

/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
    let sum = 0;
    for (let i = 0; i < s.length; i++) {
        sum += getValue(s, i);   
    }
    return sum;
};

function getValue (str, index) {
    const c = str[index];
    switch (c) {
        case 'I':
            if (index + 1 < str.length && ['V', 'X'].includes(str[index + 1])) {
                return -1;
            } else {
                return 1;
            }
        case 'V':
            return 5;
        case 'X':
            if (index + 1 < str.length && ['L', 'C'].includes(str[index + 1])) {
                return -10;
            } else {
                return 10;
            }
        case 'L':
            return 50;
        case 'C':
            if (index + 1 < str.length && ['D', 'M'].includes(str[index + 1])) {
                return -100;
            } else {
                return 100;
            }
        case 'D':
            return 500;
        case 'M':
            return 1000;
    }
}

TODO: there is an easier solution by comparing the current value and the next value to get its sign.

0830 2.  Diagonal Traverse

/**
* @param {number[][]} matrix
* @return {number[]}
*/
var findDiagonalOrder = function(matrix) {
    const result = [];
    if (matrix == null || matrix.length === 0) {
        return result;
    }
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    let up = true;
    let i = 0;
    let j = 0;
    while (i >= 0 && i < rowLen && j >= 0 && j < colLen) {
        // visit
        result.push(matrix[i][j]);
        // turn to next
        if (j === colLen - 1 && up) {
            i++;
            up = !up;
        } else if (i === rowLen - 1 && !up) {
            j++;
            up = !up;
        } else if (j === 0 && !up) {
            i++;
            up = !up;
        } else if (i === 0 && up) {
            j++;
            up = !up;
        }  else {
            if (up) {
                i--;
                j++;
            } else {
                j--;
                i++;
            }
        }
    }
    return result;
};

0831 1.  Image Smoother

/**
* @param {number[][]} M
* @return {number[][]}
*/
var imageSmoother = function(M) {
    if (M == null || M.length === 0 || M[0].length === 0) {
        return M;
    }
    // !!! shallow copy on two dimensional array won't work!!!
    // !!! how to create 2D array in js
    const result = new Array(M.length).fill().map(() => new Array(M[0].length));
    for (let i = 0; i < M.length; i++) {
        for (let j = 0; j < M[0].length; j++) {
            calcOne(i, j, M, result);
        }
    }
    return result;
};

// !!! you are changing the original one in the loop which affects your later iteration!!!

function calcOne (i, j, M, result) {
    const rowLen = M.length;
    const colLen = M[0].length;
    let sum = 0;
    let count = 0;
    for (let p = i - 1; p <= i + 1; p++) {
        for (let q = j - 1; q <= j + 1; q++) {
            if (p >= 0 && p < rowLen && q >= 0 && q < colLen) {
                sum = sum + M[p][q];
                count++;
            }
        }
    }
    result[i][j] = Math.floor(sum / count);
}

0831 2. Contains Duplicate

/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
    const set = new Set();
    for (let num of nums) {
        if (set.has(num)) {
            return true;
        } else {
            set.add(num);
        }
    }
    return false;
};

0901 1. Minimum Time Difference

/**
* @param {string[]} timePoints
* @return {number}
*/
var findMinDifference = function(timePoints) {
    timePoints = timePoints.map(convert).sort((a, b) => a - b);
    let min = Number.MAX_VALUE;
    for (let i = 0; i < timePoints.length - 1; i++) {
        let diff = timePoints[i + 1] - timePoints[i];
        min = Math.min(diff, min);
    }
    min = Math.min(min, timePoints[0] + 60 * 24 - timePoints[timePoints.length - 1]);
    return min;
};

function convert (str) {
    const [hour, minute] = str.split(':').map(numStr => Number.parseInt(numStr, 10));
    return hour * 60 + minute;
}

0901 2. Longest Palindrome

/**
* @param {string} s
* @return {number}
*/
var longestPalindrome = function(s) {
    // put into map
    // loop map, even, add. odd, add - 1, set a flag for has odd
    // add 1 for hasOdd
    const map = new Map();
    s.split('').forEach(c => {
        if (map.has(c)) {
            map.set(c, map.get(c) + 1);
        } else {
            map.set(c, 1);
        }
    });
    let sum = 0;
    let hasOdd = false;
    map.forEach((count) => {
        if (count % 2 === 0) {
            sum += count;
        } else {
            hasOdd = true;
            sum += count - 1;
        }
    });
    if (hasOdd) {sum++;}
    return sum;
};

0902 1.  Combination Sum III

/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
    const list = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    const result = [];
    const combination = [];
    const recurse = (i) => {
        for (let j = i; j < list.length; j++) {
            combination.push(list[j]);
            if (combination.length === k) {
                const sum = combination.reduce((sum, num) => sum + num);
                if (sum === n) {
                    result.push([...combination]);
                }
            } else {
                recurse(j + 1);
            }
            combination.pop();
        }
    }
    recurse(0);
    return result;
   
};
TODO: the current solution is a bit weird. Redo it.

0902. 2. Longest Continuous Increasing Subsequence

/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function(nums) {
    let i = 0;
    let max = 0;
    while (i < nums.length) {
        let j = i + 1;
        while (j < nums.length && nums[j] > nums[j - 1]) {
            j++;
        }
        max = Math.max(max, j - i);
        i = j;
    }
    return max;
};

sicilianee 发表于 2017-9-12 11:47
0902. 2. Longest Continuous Increasing Subsequence

/**

Single loop.

/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function(nums) {
    if (nums == null) {
        return 0;
    }
    let max = 0;
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i === 0 || nums[i] > nums[i - 1]) {
            count++;
        } else {
            count = 1;
        }
        max = Math.max(count, max);
    }
    return max;
};

sicilianee 发表于 2017-9-12 10:47
0902 1.  Combination Sum III

/**

/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
    const result = [];
    const combination = [];
    const recurse = (i, left) => {
        if (left <= 0 || combination.length === k) {
            if (left === 0 && combination.length === k) {
                result.push([...combination]);
            }
            return;
        }
        for (let j = i; j <= 9; j++) {
            combination.push(j);
            recurse(j + 1, left - j);
            combination.pop();
        }
    }
    recurse(1, n);
    return result;
};