记录

1023 6.  Meeting Rooms II

/**
* Definition for an interval.
* function Interval(start, end) {
*     this.start = start;
*     this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
    if (intervals == null || intervals.length === 0) {
        return 0;
    }
    // {time, val}
    const events = [];
    for (let entry of intervals) { // !!! interval is an object not an array
        const start = entry.start;
        const end = entry.end;
        events.push({time: start, val: 1});
        events.push({time: end, val: -1});
    }
    let count = 0;
    let maxRooms = 0;
    events.sort((e1, e2) => e1.time === e2.time ? (e1.val === -1 ? -1 : 1) : e1.time - e2.time ); // !!! if time is the same !!!!
    // !!! the comparision is tricky: smaller ones goes first.
    for (let e of events) {
        count += e.val;
        maxRooms = Math.max(count, maxRooms);
    }
    return maxRooms;
};

1023 7. Add Bold Tag in String

/**
* @param {string} s
* @param {string[]} dict
* @return {string}
*/
var addBoldTag = function(s, dict) {
    if (s == null || s.length === 0 || dict == null || dict.length === 0) {return s}
    const bold = Array(s.length);
    for (let word of dict) {
        for (let i = 0; i < s.length; i++) {
            if (s[i] === word[0]) {
                const sWord = s.slice(i, word.length + i);
                if (word === sWord) {
                    for (let j = i; j < i + word.length; j++) {
                        bold[j] = true;
                    }
                }
            }
        }
    }
    const res = [];
    for (let i = 0; i < s.length; i++) {
        if (bold[i]) {
            res.push('<b>');
            let j = i;
            while (bold[j]) {
                res.push(s[j]); // !!! here is j, not i
                j++;
            }
            // the current j is not bold
            res.push('</b>');
            i = j - 1;
            
        } else {
            res.push(s[i]);
        }
    }
    return res.join('');
};

1023 8. The Maze II

/**
* @param {number[][]} maze
* @param {number[]} start
* @param {number[]} destination
* @return {number}
*/
var shortestDistance = function(maze, start, destination) {
    if (maze == null || maze.length === 0) {
        return 0;
    }
    const rowLen = maze.length;
    const colLen = maze[0].length;
    const dists = Array(rowLen).fill().map(() => Array(colLen).fill(Infinity));
    dists[start[0]][start[1]] = 0;
    recurse(...start); // !!! forget to call
    const val = dists[destination[0]][destination[1]];
    return val === Infinity ? -1 : val;
   
    function recurse (i, j) {
        // assume i, j is a valid stop position
        if (i === destination[0] && j === destination[1]) {return;}
        const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]];
        for (let move of moves) {
            let x = i;
            let y = j;
            let dist = dists[i][j];
            while (x >= 0 && x < rowLen && y >= 0 && y < colLen && maze[x][y] === 0) { // !!!! you totally forgot about the walls !!!
                x = x + move[0];
                y = y + move[1];
                dist++;
            }
            x = x - move[0];
            y = y - move[1];
            dist--;
            if (dist < dists[x][y]) { // !!!! this is how to avoid circle !!!!
                dists[x][y] = dist;
                recurse(x, y);
            }
        }
    }
};

1023 9. Graph Valid Tree

/**
* @param {number} n
* @param {number[][]} edges
* @return {boolean}
*/
var validTree = function(n, edges) {
    if (n <= 0) {return false}
    const dSet = new DisjointSet(n);
    for (let [x, y] of edges) {
        if (dSet.find(x) === dSet.find(y)) { // in the same set, already connected, means you have circle
            return false;
        }
        dSet.union(x, y);
    }
    const val = dSet.find(0);
    for (let i = 0; i < n; i++) {
        if (dSet.find(i) !== val) {
            return false;
        }
    } // all connected
    return true;
};

class DisjointSet {
    constructor (len) {
        this.parent = Array(len).fill().map((v, i) => i);
    }
    find (x) {
        if (x !== this.parent[x]) {
            return this.find(this.parent[x]);
        } else {
            return x;
        }
    }
    union (x, y) {
        this.parent[this.find(x)] = this.find(y);
    }
}

1023 10. Binary Tree Vertical Order Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var verticalOrder = function(root) {
    if (root == null) {
        return [];
    }
    // [node, col]
    const q = [[root, 0]];
    const map = new Map();
    map.set(0, [root.val]);
    while (q.length > 0) {
        const [node, col] = q.shift();
        if (node.left) {
            q.push([node.left, col - 1]);
            const list = map.get(col - 1) || [];
            list.push(node.left.val); // !!! node.left not node
            map.set(col - 1, list);
        }
        if (node.right) {
            q.push([node.right, col + 1]);
            const list = map.get(col + 1) || [];
            list.push(node.right.val); // !!! node.right not node
            map.set(col + 1, list);
        }
    }
    return [...map.entries()].sort((e1, e2) => e1[0] - e2[0]).map(entry => entry[1]);
};

1023 11. Split Array with Equal Sum

/**
* @param {number[]} nums
* @return {boolean}
*/

var splitArray = function(nums) {
    if (nums == null || nums.length < 7) {
        return false;
    }
    const len = nums.length;
    const sums = Array(len).fill(0);
    for (let i = 0; i < len; i++) {
        const prev = i === 0 ? 0 : sums[i - 1];
        sums[i] = prev + nums[i];
    }
    console.log(sums);
    for (let j = 3; j < len - 3; j++) {
        // const left = sums[j - 1];
        // const right = sums[len - 1] - sums[j]; // !!!!! sums, not nums
        // if (left === right) {
        // !!! why can't you have the above lines? because we don't include the pivot points in the sum, so that means
        // we don't sum the whole left or whole right
            console.log(j)
            const set = new Set();
            for (let i = 1; i < j - 1; i++) {
                if (sums[i - 1] === sums[j - 1] - sums[i]) {
                    set.add(sums[i - 1]);
                }
            }
            if (set.size > 0) {
                for (let k = j + 2; k < len - 1; k++) {
                    if (sums[k - 1] - sums[j] === sums[len - 1] - sums[k] && set.has(sums[k - 1] - sums[j])) {
                        return true;
                    }
                }
            }
        // }
    }
    return false;
};

1204 1. Split Concatenated Strings

/**
* @param {string[]} strs
* @return {string}
*/
var splitLoopedString = function(strs) {
    // first, loop strs and reverse and find max
    // then, loop each str,
    // for each str, get it and reversed one of it
    // for each of the two
    // loop each char of the str
    // for each char position, serve as the start
    // build the whole string
    // compare if it is the best
    // end
    if (strs == null || strs.length === 0) {
        return ''
    }
    for (let i = 0; i < strs.length; i++) {
        const str = strs[i];
        const reversed = str.split('').reverse().join('');
        if (reversed > str) {
            strs[i] = reversed;
        }
    }
    let biggest = strs.join('');
    for (let i = 0; i < strs.length; i++) {
        const str = strs[i];
        const reversed = str.split('').reverse().join('');
        ;[str, reversed].forEach(aStr => {
            for (let j = 0; j < aStr.length; j++) {
                const startPart = aStr.slice(j);
                const endPart = aStr.slice(0, j);
                let newStr = startPart;
                for (let k = i + 1; k < strs.length; k++) {
                    newStr += strs[k];
                }
                for (let k = 0; k < i; k++) {
                    newStr += strs[k];
                }
                newStr = newStr + endPart;
                if (newStr > biggest) {
                    biggest = newStr;
                }
            }
        })
    }
    return biggest;
};

1204 2. Daily Temperatures

/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
    // keep ans, stack, temperatures
    // loop temp, smaller, put into stack, bigger, while pop stack and update the ans array
    const len = temperatures.length;
    const ans = Array(len).fill();
    const stack = [];
    for (let i = 0; i < temperatures.length; i++) {
        const temp = temperatures[i];
        while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temp) {
            const j = stack.pop();
            ans[j] = i - j; // !!! they want the diff, not the index value
        }
        stack.push(i);
    }
    while (stack.length > 0) {
        const index = stack.pop();
        ans[index] = 0;
    }
    return ans;
};

1204 2. Daily Temperatures

/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
    // keep ans, stack, temperatures
    // loop temp, smaller, put into stack, bigger, while pop stack and update the ans array
    const len = temperatures.length;
    const ans = Array(len).fill();
    const stack = [];
    for (let i = 0; i < temperatures.length; i++) {
        const temp = temperatures[i];
        while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temp) {
            const j = stack.pop();
            ans[j] = i - j; // !!! they want the diff, not the index value
        }
        stack.push(i);
    }
    while (stack.length > 0) {
        const index = stack.pop();
        ans[index] = 0;
    }
    return ans;
};

1204 3. Monotone Increasing Digits

/**
* @param {number} N
* @return {number}
*/
var monotoneIncreasingDigits = function(N) {
    const list = String(N).split('').map(c => Number.parseInt(c, 10));
    let i = 1;
    while (i < list.length && list[i] >= list[i - 1]) {
        i++;
    }
    while (i > 0 && i < list.length && list[i] < list[i - 1]) {
        i--;
        list[i]--;
    }
    for (let j = i + 1; j < list.length; j++) {
        list[j] = 9;
    }
    return Number.parseInt(list.join(''), 10)
};