记录

1125 1. My Calendar III


var MyCalendarThree = function() {
    this.events = [];
};

/**
* @param {number} start
* @param {number} end
* @return {number}
*/
MyCalendarThree.prototype.book = function(start, end) {
    // new two events, start, end
    // insert these two into the existing events
    // then, loop and find max
    const insert = e => {
        let i = 0;
        for (; i < this.events.length; i++) {
            if (e.time < this.events[i].time ||
               e.time === this.events[i].time && e.type === 'end'
               ) {
                break;
            }
        }
        this.events.splice(i, 0, e);
    }
    const startEvent = {type: 'start', time: start};
    const endEvent = {type: 'end', time: end};
    insert(startEvent);
    insert(endEvent);
    let max = 0;
    let count = 0;
    for (let e of this.events) {
        if (e.type === 'start') {
            count++;
        } else {
            count--;
        }
        max = Math.max(max, count);
    }
    return max;
};

/**
* Your MyCalendarThree object will be instantiated and called as such:
* var obj = Object.create(MyCalendarThree).createNew()
* var param_1 = obj.book(start,end)
*/

1125 2. Output Contest Matches

/**
* @param {number} n
* @return {string}
*/
var findContestMatch = function(n) {
    let list = Array(n).fill().map((v, i) => i + 1); // !!!! cannot ignore the fill step or map won't work !!!
    while (list.length > 1) {
        let left = 0;
        let right = list.length - 1;
        const newList = [];
        while (left < right) {
            const str = `(${list[left]},${list[right]})`;
            newList.push(str);
            left++;
            right--;
        }
        list = newList;
    }
    return list[0];
};

1125 3. Find Leaves of Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var findLeaves = function(root) {
    // check
    // keep res,
    // recurse helper, get height as index, store val of the node, stop when null
    if (root == null) {
        return [];
    }
    const res = [];
    recurse(root);
    return res;
   
    function recurse (node) {
        if (node == null) {return -1;}
        const leftHeight = recurse(node.left);
        const rightHeight = recurse(node.right);
        const selfHeight = Math.max(leftHeight, rightHeight) + 1;
        res[selfHeight] = res[selfHeight] || [];
        res[selfHeight].push(node.val);
        return selfHeight;
    }
   
   
};

1125 4. Wiggle Sort

/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var wiggleSort = function(nums) {
    // check
    // from 1, compare and swap
    // !!!! tricky的点在于：交换i, i - 1之后，不仅i, i - 1问题解决了，i - 1 和 i - 2 的相对关系仍然hold ！！！！
    // 可以这样思考：因为中间点是极小或极大，左半边已经hold，那么不管右半边怎么弄左半边都仍然hold
    if (nums == null || nums.length === 0) {
        return;
    }
    for (let i = 1; i < nums.length; i++) {
        const isEven = i % 2 === 0;
        if (isEven && (nums[i] > nums[i - 1]) || !isEven && (nums[i] < nums[i - 1])) {
            ;[nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
        }
    }
};

1125 5. Range Addition

/**
* @param {number} length
* @param {number[][]} updates
* @return {number[]}
*/
var getModifiedArray = function(length, updates) {
    // !!! 这题和calender， 以及parenthesis类的题都有点像，有一个开始，一个结尾，中间都是一个range
    if (length <= 0) {return []}
    const array = Array(length).fill(0);
    if (updates == null || updates.length === 0) {return array;}
    for (let [start, end, val] of updates) {
        array[start] += val;
        if (end + 1 < length) {
            array[end + 1] -= val; // !!! need to + 1, inclusive end
        }
    }
    for (let i = 1; i < array.length; i++) {
        array[i] = array[i - 1] + array[i];
    }
    return array;
};

1125 6. Lonely Pixel I

/**
* @param {character[][]} picture
* @return {number}
*/
var findLonelyPixel = function(picture) {
    if (picture == null || picture.length === 0) {return 0}
    const rowMap = new Map();
    const colMap = new Map();
    const rowLen = picture.length;
    const colLen = picture[0].length;
    for (let i = 0; i < rowLen; i++) {
        let count = 0;
        for (let j = 0; j < colLen; j++) {
            if (picture[i][j] === 'B') {
                count++;
            }
        }
        rowMap.set(i, count);
    }
    for (let j = 0; j < colLen; j++) {
        let count = 0;
        for (let i = 0; i < rowLen; i++) {
            if (picture[i][j] === 'B') {
                count++;
            }
        }
        colMap.set(j, count);
    }
    let count = 0;
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (picture[i][j] === 'B' && rowMap.get(i) === 1 && colMap.get(j) === 1) {
                count++;
            }
        }
    }
    return count;
};

sicilianee 发表于 2017-11-26 10:13
1125 6. Lonely Pixel I

/**

行和列的遍历可以合成一个

1125 7. Find Permutation

/**
* @param {string} s
* @return {number[]}
*/
var findPermutation = function(s) {
    // check
    // produce the array
    // loop the s, (other index = sIndex + 1, compare with prev), if is I, just go on
    // if is D, go into a while loop until the last D, switch order in the middle
    if (s == null || s.length === 0) {
        return [1];
    }
    let i = 0;
    const res = [];
    while (i < s.length) {
        if (s[i] === 'I') {
            res.push(i + 1);
            i++; // !!!! this update!!!!
        } else {
            const start = i + 1;
            let j = i;
            while (j < s.length && s[j] === 'D') {
                j++;
            }
            const end = j + 1;  // !!! the one offset
            for (let num = end; num >= start; num--) {
                res.push(num);
            }
            i = j + 1;
        }
    }
    if (i === s.length) { // !!! how to avoid this ?
        res.push(i + 1);
    }
    return res;
};

这个解法不是很好，最后一个回合要单独列出来处理。

sicilianee 发表于 2017-11-26 10:47
1125 7. Find Permutation

/**

还是应该从第二个元素开始， 这样可能需要pop一个，当遇到第一个D的时候。

1125 8. Candy Crush

/**
* @param {number[][]} board
* @return {number[][]}
*/
var candyCrush = function(board) {
    // check
    // while true
    // double loop the board
    // for each, check if it is a middle of 3 of two orientations, if is, mark all 3 -,
    // (1. use abs, 2. not 0)
    // after the mark, start move. Note here if nothing marked, should break out of the loop
    // for each col, from bottom to top, keep count and calc each index, for visited ones change to 0 for others to overwrite
    // after break, return the board
    if (board == null || board.length === 0) {
        return board;
    }
    const rowLen = board.length;
    const colLen = board[0].length;
    while (true) {
        let marked = false;
        const markMatrix = Array(rowLen).fill().map(() => Array(colLen).fill(false));
        for (let i = 0; i < rowLen; i++) {
            for (let j = 0; j < colLen; j++) {
                if (board[i][j] === 0) {continue}
                const up = i === 0 ? 0 : board[i - 1][j];
                const down = i === rowLen - 1 ? 0 : board[i + 1][j];
                const left = j === 0 ? 0 : board[i][j - 1];
                const right = j === colLen - 1 ? 0 : board[i][j + 1];
                const self = board[i][j];
                if (up === self && self === down) {
                    marked = true;
                    markMatrix[i - 1][j] = true;
                    markMatrix[i][j] = true;
                    markMatrix[i + 1][j] = true;
                }
                if (left === self && self === right) {
                    marked = true;
                    markMatrix[i][j - 1] = true;
                    markMatrix[i][j] = true;
                    markMatrix[i][j + 1] = true;
                }
            }
        }
        if (!marked) {
            return board;
        }
        for (let j = 0; j < colLen; j++) {
            let count = 0;
            for (let i = rowLen - 1; i >= 0; i--) {
                if (markMatrix[i][j]) {
                    // !!!!! should convert to 0
                    board[i][j] = 0;
                    count++;
                } else {
                    board[i + count][j] = board[i][j];
                    if (count > 0) { // !!!! only set to 0 if it __IS__ moved.
                        board[i][j] = 0;
                    }
                    // !!!! after move, set it to 0, otherwise you'll keep doing it.
                }
            }
        }
    }
};