记录

0102 3. Optimal Account Balancing

/**
* @param {number[][]} transactions
* @return {number}
*/
var minTransfers = function(transactions) {
    // check
    // first, build the account map of each person
    // then, get the values as a list, filter out the 0 values
    // start dfs it, from the first one !!! note if the current one is 0, we are f***ed up. Need to skip 0s
    // start the transaction with num 0
    // for the current one, loop the remaining to find one that is different size with this one
    // we put this current one on that one, and dfs from i + 1
    // if no records after the current one could start the dfs, then all of them are 0, which means we reached the end then we should update the global min
    // also if we are at the last one, there is nothing to loop this could be reduced to the previous condition so good.
    if (transactions == null || transactions.length === 0) {
        return 0;
    }
    const map = new Map();
    transactions.forEach(([a, b, val]) => {
        const aVal = map.get(a) || 0;
        const bVal = map.get(b) || 0;
        map.set(a, aVal - val);
        map.set(b, bVal + val);
    });
    const values = [...map.values()].filter(val => val);
    let min = values.length > 1 ? values.length - 1 : 0; // !!! it could be 0
    dfs(0, 0);
    return min;
   
   
    function dfs (i, num) {
        while (values[i] === 0) {i++}
        let found = false;
        for (let j = i + 1; j < values.length; j++) {
            if (values[j] * values[i] < 0) {
                found = true;
                const oldValue = values[j];
                values[j] = values[j] + values[i];
                dfs(i + 1, num + 1);
                values[j] = oldValue;
            }
        }
        if (!found) {
            min = Math.min(num, min);
        }
    }
};


Need to learn more about this sort of problem, np complete.

0103 1. Contain Virus

/**
* @param {number[][]} grid
* @return {number}
*/
var containVirus = function(grid) {
    // we have the grid
    // we loop the grid
    // met 1, we start dfs, with the start as key
    // get all of the frontiers and put to the map value using the key
    // after a loop, we loop the map to find the max sized value, and start dfs that key, turn all values into 2
    // then the rest of it, we turn the frontiers into 1
    // then we start another game
    // when all entries in the map got size == 0, end the game
    if (grid == null || grid.length === 0) {
        return 0;
    }
    const rowLen = grid.length;
    const colLen = grid[0].length;
    const visited = new Set();
    const map = new Map();
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (grid[i][j] === 1 && !visited.has(`${i}:${j}`)) {
                const nextCells = [];
                dfs(i, j, nextCells);
                if (nextCells.length > 0) {
                    map.set(`${i}:${j}`, nextCells);
                }
            }
        }
    }
    if (map.size === 0) { // when the game ends: no new cells to contaminate
        return 0;
    }
    // now find the biggest
    let maxEntry = null;
    for (let entry of map.entries()) {
        const [key, list] = entry;
        const set = new Set(list);
        const maxSet = maxEntry == null ? new Set() : new Set(maxEntry[1]);
        if (set.size > maxSet.size) {
            maxEntry = entry;
        }
    }
    // fill the max area with 2
    const maxKey = maxEntry[0];
    const maxSize = maxEntry[1].length;
    const [x, y] = maxKey.split(':').map(str => Number.parseInt(str, 10));
    fillMax(x, y);
    // then, got all the other areas and develop them
    for (let [key, list] of map.entries()) {
        if (key !== maxKey) {
            for (let str of list) {
                const [x, y] = str.split(':').map(str => Number.parseInt(str, 10));
                grid[x][y] = 1;
            }
        }
    }
    const rest = containVirus(grid);
    return rest + maxSize;
   
   
    function fillMax (i, j) {
        if (i < 0 || i >= rowLen || j < 0 || j >= colLen) {
            return;
        }
        if (grid[i][j] === 1) {
            grid[i][j] = 2;
            const moves = [[0, 1], [0, -1], [-1, 0], [1, 0]];
            for (let move of moves) {
                const newI = i + move[0];
                const newJ = j + move[1];
                fillMax(newI, newJ);
            }
        }
    }
   
    function dfs (i, j, nextCells) {
        if (i < 0 || i >= rowLen || j < 0 || j >= colLen) {
            return;
        }
        if (grid[i][j] === 2) { // already quarantined
            return;
        }
        if (grid[i][j] === 0) { // can contaminate
            nextCells.push(`${i}:${j}`);
            return;
        }
        if (visited.has(`${i}:${j}`)) { // !!! need to test visited here
            return;
        }
        if (grid[i][j] === 1) {
            visited.add(`${i}:${j}`);
            const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
            for (let move of moves) {
                const newI = i + move[0];
                const newJ = j + move[1];
                dfs(newI, newJ, nextCells);
            }
        }
    }
   
};

0103 2. Paint House II

/**
* @param {number[][]} costs
* @return {number}
*/
var minCostII = function(costs) {
    // !!! better to use meaningful variable names, here you got confused about rows and cols multiple times
    if (costs == null || costs.length === 0) {
        return 0;
    }
    const rowLen = costs.length;
    const colLen = costs[0].length;
    const dp = costs.map(arr => [...arr]);
    // !!! you confused the row and column
    // loop the house
    for (let i = 0; i < rowLen; i++) { // house
        for (let j = 0; j < colLen; j++) { // color
            if (i !== 0) {
                let min = Infinity;
                for (let k = 0; k < colLen; k++) { // color
                    if (k !== j) {
                        min = Math.min(min, dp[i - 1][k]);
                    }
                }
                dp[i][j] = dp[i][j] + min;
            }
        }
    }
    // now get the min of the last house of all colors
    return Math.min(...dp[rowLen - 1]);
};

0103 3. Word Pattern II

/**
* @param {string} pattern
* @param {string} str
* @return {boolean}
*/
var wordPatternMatch = function(pattern, str) {
    // check
    // just dfs, keep a map and a set for visited values
    // start dfs
    // get one letter, if not in the map, loop the str for each case to do a match, put it in the map, dfs on
    // if in the map, check if it is valid or not, if true, dfs on, false, return false
    if (pattern == null || str == null) {
        return false;
    }
    const map = new Map();
    const set = new Set(); // !!!! you missed the set
    return dfs(0, 0);
   
    function dfs (i, j) {
        // ith in pattern, jth in str
        if (i === pattern.length && j === str.length) {
            return true;
        }
        if (i >= pattern.length || j >= str.length) {
            return false;
        }
        const c = pattern[i];
        if (map.has(c)) {
            const val = map.get(c);
            const len = val.length;
            if (val === str.slice(j, j + len)) {
                return dfs(i + 1, j + len);
            } else {
                return false;
            }
        } else {
            for (let len = 1; j + len - 1 < str.length; len++) {
                const val = str.slice(j, j + len);
                if (set.has(val)) {continue;}
                set.add(val);
                map.set(c, val);
                if (dfs(i + 1, j + len)) {
                    return true;
                }
                // !!! need to restore when backtracking. we have a loop inside the dfs, each val is diff. should backtrack and restore
                set.delete(val);
                map.delete(c);
            }
            return false;
        }
    }
};

0103 4. Falling Squares

/**
* @param {number[][]} positions
* @return {number[]}
*/
var fallingSquares = function(positions) {
    class TreeNode {
        constructor (start, end) {
            this.start = start;
            this.end = end;
            this.left = this.right = null;
            this.max = 0;
        }
    }
   
    if (positions == null || positions.length === 0) {
        return [];
    }
    // first, discretize the positions into a list of points, AND sort them
    const points = positions.map(([start, len]) => [start, start + len - 1]).reduce((prev, curr) => [...prev, ...curr]).sort((a, b) => a - b);
    const map = new Map(points.map((value, index) => [value, index]));
    // build a segment tree from the points
    const buildTree = (start, end) => {
        const node = new TreeNode(start, end);
        if (start === end) {
            return node;
        } else {
            const mid = start + Math.trunc( (end - start) / 2 );
            node.left = buildTree(start, mid);
            node.right = buildTree(mid + 1, end);
            return node;
        }
    }
    const root = buildTree(0, points.length - 1);
    // now get all the points loop them and update the tree
    const updateTree = (node, start, end, val) => {
        node.max = Math.max(node.max, val);
        if (node.start == node.end && start == end && start == node.start) { // leaf, stop
            node.max = val;
            return;
        } else { // not leaf, go left, right, or both
            const mid = node.start + Math.trunc( (node.end - node.start) / 2 ); // !!!! node.start, node.end, not start and end
            if (end <= mid) {
                // on the left
                updateTree(node.left, start, end, val);
            } else if (start > mid) {
                // on the right
                updateTree(node.right, start, end, val);
            } else {
                // spans both
                updateTree(node.left, start, mid, val);
                updateTree(node.right, mid + 1, end, val);
            }
        }
    }
    const queryTree = (node, start, end) => {
        // need a full match to guarantee
        if (node.start === start && node.end === end) {
            return node.max;
        } else {
            const mid = node.start + Math.trunc( (node.end - node.start) / 2 ); // !!!! start + , not end +, this could cause errors, 得不偿失，一定要熟悉才用。
            if (end <= mid) {
                // on the left
                return queryTree(node.left, start, end);
            } else if (start > mid) {
                // on the right
                return queryTree(node.right, start, end);
            } else {
                // both
                const leftVal = queryTree(node.left, start, mid);
                const rightVal = queryTree(node.right, mid + 1, end);
                return Math.max(leftVal, rightVal);
            }
        }
    }
    // we might need a map to get the index from the points values
    const ans = [];
    for (let [startPos, len] of positions) {
        // !!!! map values to indexed values !!!! index compression!!!
        const endPos = startPos + len - 1;
        const start = map.get(startPos);
        const end = map.get(endPos);
        // first, query the value to get the real value
        const val = len;
        const oldVal = queryTree(root, start, end);
        const newVal = oldVal + val;
        updateTree(root, start, end, newVal);
        ans.push(root.max);
    }
    return ans;
};



Learn more about lazy propagation

0104 1. Design In-Memory File System


class TrieNode {
    constructor (name) {
        this.isFile = false;
        this.content = '';
        this.name = name;
        this.map = new Map();
    }
}

var FileSystem = function() {
    this.root = new TrieNode();
};

/**
* @param {string} path
* @return {string[]}
*/
FileSystem.prototype.ls = function(path) {
    const node = this.findNode(path);
    if (node.isFile) { // !!! not its content, but the file name itself. This means we need to retrieve the name from the node,
        // which means we need to store the name on the node. A good example.
        return [node.name];
    } else {
        return [...node.map.keys()].sort();
    }
};

FileSystem.prototype.insert = function (path) {
    const list = path.split('/').filter(str => str);
    let node = this.root;
    for (let str of list) {
        if (node.map.has(str)) {
            node = node.map.get(str);
        } else {
            const newNode = new TrieNode(str);
            node.map.set(str, newNode);
            node = newNode;
        }
    }
    return node;
}

/**
* @param {string} path
* @return {void}
*/
FileSystem.prototype.mkdir = function(path) {
    this.insert(path);
};

FileSystem.prototype.findNode = function (path) {
    const list = path.split('/').filter(str => str); // !!! avoid '/'
    let node = this.root;
    for (let str of list) {
        if (node.map.has(str)) {
            node = node.map.get(str);
        } else {
            return null;
        }
    }
    return node;
}

/**
* @param {string} filePath
* @param {string} content
* @return {void}
*/
FileSystem.prototype.addContentToFile = function(filePath, content) {
    let node = this.findNode(filePath);
    if (node == null) {
        node = this.insert(filePath);
        node.isFile = true;
        node.content = content;
    } else {
        node.isFile = true;
        node.content += content;
    }
};

/**
* @param {string} filePath
* @return {string}
*/
FileSystem.prototype.readContentFromFile = function(filePath) {
    const node = this.findNode(filePath);
    return node.content;
};

/**
* Your FileSystem object will be instantiated and called as such:
* var obj = Object.create(FileSystem).createNew()
* var param_1 = obj.ls(path)
* obj.mkdir(path)
* obj.addContentToFile(filePath,content)
* var param_4 = obj.readContentFromFile(filePath)
*/

0104 2. Shortest Distance from All Buildings

/**
* @param {number[][]} grid
* @return {number}
*/
var shortestDistance = function(grid) {
    // check
    // create a dist matrix
    // create a visited matrix
    // loop the grid, encounter 1, start a bfs, with a fresh visited
    // each 0, add up the dist matrix, mark the visited matrix, after the dfs, check the visited matrix,
    // mark all unreachable in the dist to infinity
    // after the loop, find the min if any
    if (grid == null || grid.length === 0 || grid[0].length === 0) {
        return -1;
    }
    const rowLen = grid.length;
    const colLen = grid[0].length;
    const dist = Array(rowLen).fill().map(() => Array(colLen).fill(0));
    const visited = Array(rowLen).fill().map(() => Array(colLen).fill(false));
    const cleanVisited = () => {
        for (let i = 0; i < rowLen; i++) {
            for (let j = 0; j < colLen; j++) {
                visited[i][j] = false;
            }
        }
    }
    const bfs = (i, j) => {
        const q = [[i, j]];
        let aDist = 1; // !!!! we have a dist matrix, cannot have the same name !!!
        while (q.length > 0) {
            // get one node from q, find all valid children, visit all valid children, add up the distance
            const len = q.length;
            for (let i = 0; i < len; i++) {
                const node = q.shift();
                const moves = [[0, 1], [0, -1], [-1, 0], [1, 0]];
                for (let move of moves) {
                    const newI = node[0] + move[0];
                    const newJ = node[1] + move[1];
                    // !!!!! test visited to avoid circles !!!!!!
                    if (newI >= 0 && newI < rowLen && newJ >= 0 && newJ < colLen && grid[newI][newJ] === 0 && !visited[newI][newJ]) {
                        visited[newI][newJ] = true;
                        dist[newI][newJ] += aDist;
                        q.push([newI, newJ]);
                    }
                }
            }
            aDist++;
        }
    }
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (grid[i][j] === 1) {
                cleanVisited();
                bfs(i, j);
                for (let x = 0; x < rowLen; x++) {
                    for (let y = 0; y < colLen; y++) {
                        if (grid[x][y] === 0 && !visited[x][y]) {
                            dist[x][y] = Infinity;
                        }
                    }
                }
            }
        }
    }
    let min = Infinity;
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (grid[i][j] === 0) {
                min = Math.min(min, dist[i][j]);
            }
        }
    }
    return min === Infinity ? -1 : min;
};

0104 3. Stickers to Spell Word

/**
* @param {string[]} stickers
* @param {string} target
* @return {number}
*/
var minStickers = function(stickers, target) {
    // the hardest part is to figure out how to represent each state. It's not continuous: the sequence doesn't matter.
    // you could take the first one and the third char in the target str.
    // so use bitmap or just int to represent, up to 2^len state, each bit represent on or off, use or not.
    if (target == null || target.length === 0) {return 0}
    if (stickers == null || stickers.length === 0) {return -1}
    const len = target.length;
    const numStates = 1 << len;
    const dp = Array(numStates).fill(-1);
    dp[0] = 0; // all off, need no stickers
    for (let i = 0; i < numStates; i++) { // TODO: shall use 'state' to replace i, it will be clearer
        if (dp[i] === -1) {continue;} // cannot build upon this state, move on
        // loop each operation
        for (let str of stickers) {
            // use this str, we try to find use of each char of the str on the current state of target
            let newState = i;
            for (let c of str) {
                for (let j = 0; j < target.length; j++) {
                    const aChar = target[j];
                    if (c === aChar && ((newState >> j) & 1) === 0 ) { // !!! here equal 0, not 1, not -1, means this one is off right now, we are goona turn it on
                        newState = newState | (1 << j);
                        break; // this char is already used, we have only one, so break
                    }
                }
            }
            if (dp[newState] === -1 || dp[newState] > dp[i] + 1) {
                dp[newState] = dp[i] + 1;
            }
        }
    }
    return dp[numStates - 1];
};

0105 1. Count Different Palindromic Subsequences

/**
* @param {string} S
* @return {number}
*/
var countPalindromicSubsequences = function(S) {
    // check
    // the i, j, x, means from i to j, how many palindromes that have char x as the perimeter
    const mod = Math.pow(10, 9) + 7;
    if (S === null || S.length === 0) {
        return 0;
    }
    const len = S.length;
    const dp = Array(len).fill().map(() => Array(len).fill().map(() => Array(4).fill(0)));
    for (let range = 1; range <= len; range++) {
        for (let i = 0; i + range - 1 < len; i++) {
            const j = i + range - 1;
            for (let code = 0; code < 4; code++) {
                const c = String.fromCharCode(code + 'a'.charCodeAt(0)); // !!! plus a's code
                if (range === 1) {
                    dp[i][j][code] = S[i] === c ? 1 : 0;
                } else {
                    if (S[i] !== c) {
                        dp[i][j][code] = dp[i + 1][j][code];
                    } else if (S[j] !== c) {
                        dp[i][j][code] = dp[i][j - 1][code];
                    } else {
                        if (range === 2) {
                            // we know they both equal to the currrent color
                            dp[i][j][code] = 2; // !!! not 3, not duplicates
                        } else {
                            const prevI = i + 1;
                            const prevJ = j - 1;
                            dp[i][j][code] = dp[prevI][prevJ][0] % mod + dp[prevI][prevJ][1] % mod + dp[prevI][prevJ][2] % mod + dp[prevI][prevJ][3] % mod + 2;
                        }
                    }
                }
                dp[i][j][code] = dp[i][j][code] % mod;
            }
        }
    }
    // 如何理解这个递推公式，如何避免重复，这个是非常tricky的，比你想象的要复杂的多。
    // 这个非常类似于subsets, subsets with duplicate numbers, 但这个感觉更复杂。
    // 首先要理解i, j, x, 从i到j所有以x开头结尾的palindrome, 注意所有里面包含的palindrome 都是以x开头结尾的
    // 再加上两边的x，最后可能missing的只有x, xx, 这两个，而这两个本身就能够产生一定有。因此要+2
    return dp[0][len - 1].reduce((prev, curr) => prev + curr) % mod; // !!! 0 -> len - 1, not len - 1 -> len - 1
    // !!! the last one needs to mod, too.
    // MLE, shit!
};

MLE

sicilianee 发表于 2018-1-6 13:39
0105 1. Count Different Palindromic Subsequences

/**

/**
* @param {string} S
* @return {number}
*/
var countPalindromicSubsequences = function(S) {
    // check
    // the i, j, x, means from i to j, how many palindromes that have char x as the perimeter
    const mod = Math.pow(10, 9) + 7;
    if (S === null || S.length === 0) {
        return 0;
    }
    const len = S.length;
    const dp = Array(4).fill().map(() => Array(len).fill().map(() => Array(len).fill(0)));
    for (let range = 1; range <= len; range++) {
        for (let i = 0; i + range - 1 < len; i++) {
            const j = i + range - 1;
            for (let code = 0; code < 4; code++) {
                const c = String.fromCharCode(code + 'a'.charCodeAt(0)); // !!! plus a's code
                if (range === 1) {
                    dp[code][j] = S[i] === c ? 1 : 0;
                } else {
                    if (S[i] !== c) {
                        dp[code][i][j] = dp[code][i + 1][j];
                    } else if (S[j] !== c) {
                        dp[code][i][j] = dp[code][i][j - 1];
                    } else {
                        if (range === 2) {
                            // we know they both equal to the currrent color
                            dp[code][i][j] = 2; // !!! not 3, not duplicates
                        } else {
                            const prevI = i + 1;
                            const prevJ = j - 1;
                            dp[code][i][j] = dp[0][prevI][prevJ] % mod + dp[1][prevI][prevJ] % mod + dp[2][prevI][prevJ] % mod + dp[3][prevI][prevJ] % mod + 2;
                        }
                    }
                }
                dp[code][i][j] = dp[code][i][j] % mod;
            }
        }
    }
    // 如何理解这个递推公式，如何避免重复，这个是非常tricky的，比你想象的要复杂的多。
    // 这个非常类似于subsets, subsets with duplicate numbers, 但这个感觉更复杂。
    // 首先要理解i, j, x, 从i到j所有以x开头结尾的palindrome, 注意所有里面包含的palindrome 都是以x开头结尾的
    // 再加上两边的x，最后可能missing的只有x, xx, 这两个，而这两个本身就能够产生一定有。因此要+2
    // return dp[0][len - 1].reduce((prev, curr) => prev + curr) % mod; // !!! 0 -> len - 1, not len - 1 -> len - 1
    let sum = 0;
    for (let k = 0; k < 4; k++) {
        sum += dp[k][0][len - 1];
        sum %= mod;
    }
    return sum;
    // !!! the last one needs to mod, too.
    // MLE, shit!
};
// !!! it's weird how leetcode compute space complexity.
// 3d array, MLE
// 1. convert to 2d dp since we only need current, back one, back two, consult this: https://discuss.leetcode.com/top ... ry-with-explanation
// or the article
// 2. this is weird, just switch the order, put k (0 - 3) in the first and it will pass. 数目比较小的那个维度放在第一个维度，这样就能过了
// ！！！ 交换一下顺序，把k放在第一个，k只有1-3， 这样就能能过了。把最小的一维放在第一个。[/i][/i][/i][/i][/i][/i][/i][/i][/i][i][i][i][i][i][i][i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i]https://discuss.leetcode.com/topic/111241/c-o-n-2-time-o-n-memory-with-explanation/2[/i][/i][/i][/i][/i][/i][/i][/i][/i]
这个比article更易懂