记录

0922 2. Exclusive Time of Functions

/**
* @param {number} n
* @param {string[]} logs
* @return {number[]}
*/
var exclusiveTime = function(n, logs) {
    if (logs == null || logs.length == 0) {return [];}
    logs = logs.map(log => {
        const parts = log.split(':');
        parts[0] = Number.parseInt(parts[0], 10);
        parts[2] = Number.parseInt(parts[2], 10);
        return parts;
    });
    const map = new Map();
    const stack = [logs[0]];
    // id, type, time
    for (let i = 1; i < logs.length; i++) {
        const curr = logs[i];
        const prev = logs[i - 1];
        // !!!!! it is also possible that no function is executing at this time: stack is empty!!!
        if (stack.length > 0) {
            let id = stack[stack.length - 1][0];
            let time = curr[2] - prev[2];
            if (prev[1] === 'start' && curr[1] === 'end') {
                time = time + 1;
            }
            // !!!! 1. could be still executing
            // 2. time is also special
            if (prev[1] === 'end' && curr[1] === 'start') {
                time = time - 1;
                }
            if (map.has(id)) {
                map.set(id, map.get(id) + time);
            } else {
                map.set(id, time);
            }  
        }
        if (curr[1] === 'start') {
            stack.push(curr);
        } else {
            stack.pop();
        }  
    }
    return [...map.entries()].sort((a, b) => a[0] - b[0]).map(([id, count]) => count); // !!!!!!
};

0923 1. Convert Sorted Array to Binary Search Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
    if (nums == null || nums.length === 0) {return null;}
    const midIndex = Math.floor((0 + nums.length) / 2);
    const node = new TreeNode(nums[midIndex]);
    node.left = sortedArrayToBST(nums.slice(0, midIndex));
    node.right = sortedArrayToBST(nums.slice(midIndex + 1, nums.length));
    return node;
};

0923 2. Longest Repeating Character Replacement

Post a solution from grandyang and my comments:

class Solution {
public:
    int characterReplacement(string s, int k) {
        int res = 0, maxCnt = 0, start = 0;
        vector<int> counts(26, 0);
        for (int i = 0; i < s.size(); ++i) {
            maxCnt = max(maxCnt, ++counts[s - 'A']);
            while (i - start + 1 - maxCnt > k) {
                --counts[s[start] - 'A'];
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};
The solution itself is short but not very clear. It is confusing actually.
Check the other post:
https://scottduan.gitbooks.io/leetcode-review/longest_repeating_character_replacement.html
We care about the max, so the current window might not be valid.

sicilianee 发表于 2017-9-25 09:13
0923 2. Longest Repeating Character Replacement

Post a solution from grandyang and my comments:

/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var characterReplacement = function(s, k) {
    if (s == null || s.length === 0) {
        return 0;
    }
    let max = 0;
    let len = 0;
    let start = 0;
    const map = new Map();
    for (let end = 0; end < s.length; end++) {
        if (map.has(s[end])) {
            map.set(s[end], map.get(s[end]) + 1);
        } else {
            map.set(s[end], 1);
        }
        max = Math.max(max, map.get(s[end]));
        if (end - start + 1 - max > k) {
            map.set(s[start], map.get(s[start]) - 1); // 1. the order matters!!!. 2. mind the parenthesis! of map get operation!
            start++;
        }
        len = Math.max(len, end - start + 1);
    }
    return len;
};

0924 1. Task Scheduler

/**
* @param {character[]} tasks
* @param {number} n
* @return {number}
*/
var leastInterval = function(tasks, n) {
    if (tasks == null || tasks.length === 0) {
        return 0;
    }
    const map = new Map();
    tasks.forEach(task => {
        const count = map.has(task) ? map.get(task) + 1 : 1;
        map.set(task, count);
    });
    const entries = [...map.entries()].sort((a, b) => b[1] - a[1]);
    console.log(entries);
    const len = entries[0][1];
    let sameCount = 0;
    let i = 0;
    while (i < entries.length && entries[1] === len) {
        i++;
        sameCount++;
    }
    return Math.max(tasks.length, (len - 1) * (n + 1) + sameCount);
};
Note: could have more diff chars than the cooling interval need. Then we can just insert it there. It's the min limit, not max limit.

0924 2. Combination Sum IV


/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var combinationSum4 = function(nums, target) {
    let dp = Array(target + 1).fill(0); // !!!! the length here is target + 1 not nums.length!!!
    dp[0] = 1;
    for (let i = 1; i <= target; i++) {
        nums.forEach(num => {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        });
    }
    console.log(dp)
    return dp[target];
};

0925 1. Smallest Range

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        if (nums == null || nums.size() == 0) {
            return new int[]{0, 0};
        }
        int[] indices = new int[nums.size()];
        int min = 0;
        int max = Integer.MIN_VALUE;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(nums.size(), (i, j) -> nums.get(i).get(indices[i]) - nums.get(j).get(indices[j]));
        for (int i = 0; i < nums.size(); i++) {
            pq.add(i);
            max = Math.max(max, nums.get(i).get(0));
        }
        int minIndex = pq.remove();
        min = nums.get(minIndex).get(indices[minIndex]);
        int range = max - min;
        int globalMin = min;
        int globalMax = max;
        indices[minIndex]++;
        while (indices[minIndex] < nums.get(minIndex).size()) {
            max = Math.max(max, nums.get(minIndex).get(indices[minIndex]));
            pq.add(minIndex);
            minIndex = pq.remove();
            min = nums.get(minIndex).get(indices[minIndex]);
            // range = Math.min(range, max - min);
            if (max - min < range || ((max - min == range) && min < globalMin)) {
                range = max - min;
                globalMin = min;
                globalMax = max;
            }
            indices[minIndex]++;
        }
        return new int[]{globalMin, globalMax};
    }
}

0925 2. Serialize and Deserialize BST

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

/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
    if (root) {
        const left = serialize(root.left);
        const right = serialize(root.right);
        return `${root.val},${left},${right}`;
    } else {
        return '#';
    }
};

/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
    const parts = data.split(',');
    let counter = 0;
    const recurse = () => {
        if (counter > parts.length || parts[counter] === '#') {
            counter++; // should increase the counter even if it's null
            return null;
        }
        const self = new TreeNode(Number.parseInt(parts[counter]), 10); // !!! should parse from string
        counter++;
        const left = recurse();
        const right = recurse();
        self.left = left;
        self.right = right;
        return self;
    }
    return recurse();
};

/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/

0926 1. Elimination Game

/**
* @param {number} n
* @return {number}
*/
var lastRemaining = function(n) {
    return n === 1 ? 1 : 2 * (Math.floor(n / 2) + 1 - lastRemaining(Math.floor(n / 2)));
};

0926 2. Flatten Nested List Iterator

/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
*     Return true if this NestedInteger holds a single integer, rather than a nested list.
*     @return {boolean}
*     this.isInteger = function() {
*         ...
*     };
*
*     Return the single integer that this NestedInteger holds, if it holds a single integer
*     Return null if this NestedInteger holds a nested list
*     @return {integer}
*     this.getInteger = function() {
*         ...
*     };
*
*     Return the nested list that this NestedInteger holds, if it holds a nested list
*     Return null if this NestedInteger holds a single integer
*     @return {NestedInteger[]}
*     this.getList = function() {
*         ...
*     };
* };
*/
/**
* @constructor
* @param {NestedInteger[]} nestedList
*/
var NestedIterator = function(nestedList) {
    this.stack = [{list: nestedList, i: 0}]
};



/**
* @this NestedIterator
* @returns {boolean}
*/
NestedIterator.prototype.hasNext = function() {
    if (this.stack.length === 0) {return false;}
    const current = this.stack[this.stack.length - 1];
    if (current.i >= current.list.length) {
        this.stack.pop();
        return this.hasNext();
    } else {
        // if is list and the list is empty, we shall skip it
        const el = current.list[current.i];
        if (el.isInteger()) {
            return true;
        } else {
            current.i++;
            this.stack.push({list: el.getList(), i: 0});
            return this.hasNext();
        }
    }
};

/**
* @this NestedIterator
* @returns {integer}
*/
NestedIterator.prototype.next = function() {
    if (!this.hasNext()) {
        throw new Error('No next');
    }
    const current = this.stack[this.stack.length - 1];
    const el = current.list[current.i];
    current.i++;
    if (el.isInteger()) {
        return el.getInteger();
    } else {
        this.stack.push({list: el.getList(), i: 0});
        return this.next();
    }
};

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

TODO: Other people's solutions seem shorter?