记录

1219 1. String to Integer (atoi)

/**
* @param {string} str
* @return {number}
*/
var myAtoi = function(str) {
    // first, trim to remove white space
    // then, take the first char to see if any +-
    // if yes, take it
    // if no, nothing
    // then from the processed first one, go one until the last char is num
    // add all these together
    // and return considering the sign bit
    const max_32_int = ~(1 << 31);
    const min_32_int = 1 << 31;
    if (str == null) {return 0;}
    str = str.trim()
    if (str.length === 0) {return 0;}
    let neg = false; // !!! consider neg case
    if (str[0] === '+') {
        str = str.slice(1);
    } else if (str[0] === '-') { // !!! is a else if, not a separate if because the previous if didn't directly return
        str = str.slice(1);
        neg = true;
    }
    let res = 0;
    for (let i = 0; i < str.length && isDigit(str[i]); i++) {
        res = res * 10 + getDigit(str[i]);
    }
    if (neg) {
        return -res < min_32_int ? min_32_int : -res; // !!! 1. consider overflow; 2. -res, here all -res
    } else {
        return res > max_32_int ? max_32_int : res;
    }
   
    function getDigit (c) {
        return c.charCodeAt(0) - '0'.charCodeAt(0);
    }
   
    function isDigit (c) {
        return c >= '0' && c <= '9';
    }
   
};

1219 2.  Min Cost Climbing Stairs

/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
    if (cost == null || cost.length < 1) {return 0;} // !!! only one also return 0
    const dp = Array(cost.length).fill(0);
    for (let i = 0; i < cost.length; i++) {
        const backOne = i === 0 ? 0 : dp[i - 1];
        const backTwo = i < 2 ? 0 : dp[i - 2]; // !!!1.  > 1 not >= 1; 2. originally, the backOne and backTwo are diff, one test for good, one test for bad. That's not good. should all test for good, so change to < 2
        dp[i] = Math.min(backOne, backTwo) + cost[i];
    }
    return Math.min(dp[cost.length - 1], dp[cost.length - 2]); // !!!! last two, not the last one because we paid we can go 2 steps.
};

1220 1. Range Sum Query - Mutable

class SegmentNode {
    constructor (start, end) {
        this.start = start;
        this.end = end;
        this.sum = 0;
        this.left = this.right = null;
    }
}

/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
    nums = nums || [];
    this.root = buildTree(nums, 0, nums.length - 1);
};


function buildTree (nums, start, end) {
    if (start > end) {return null}
    const root = new SegmentNode(start, end);
    if (start === end) {
        root.sum = nums[start];
    } else {
        const mid = start + Math.trunc( (end - start) / 2 ); // !!!! here this pattern, which one where, made mistakes !!
        root.left = buildTree(nums, start, mid);
        root.right = buildTree(nums, mid + 1, end);
        root.sum = root.left.sum + root.right.sum;
    }
    return root;
}

function updateTree (node, i, val) { // i within node.start and node.end
    if (node.start > i || node.end < i) {throw new Error('Out of range');}
    if (node.start === node.end && node.start === i) {
        node.sum = val;
    } else {
        const mid = node.start + Math.trunc( (node.end - node.start) / 2 );
        if (i <= mid) {
            updateTree(node.left, i, val);
        } else {
            updateTree(node.right, i, val);
        }
        node.sum = node.left.sum + node.right.sum;
    }
}

/**
* @param {number} i
* @param {number} val
* @return {void}
*/
NumArray.prototype.update = function(i, val) {
    if (!this.root) {return;}
    updateTree(this.root, i, val);
};

function sumRangeFromTree (node, i, j) {
    if (i <= node.start && j >= node.end) {
        return node.sum;
    } else {
        const mid = node.start + Math.trunc( (node.end - node.start) / 2);
        if (j <= mid) {
            return sumRangeFromTree(node.left, i, j);
        } else if (i >= mid + 1) {
            return sumRangeFromTree(node.right, i, j);
        } else {
            return sumRangeFromTree(node.left, i, mid) + sumRangeFromTree(node.right, mid + 1, j);
        }
    }
}

/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
    if (!this.root) {return 0;}
    return sumRangeFromTree(this.root, i, j);
};

/**
* Your NumArray object will be instantiated and called as such:
* var obj = Object.create(NumArray).createNew(nums)
* obj.update(i,val)
* var param_2 = obj.sumRange(i,j)
*/

1220 2. Word Squares

/**
* @param {string[]} words
* @return {string[][]}
*/
var wordSquares = function(words) {
    // check
    // build the map
    // keep a list of words to use
    // for each word, as the start, add to the list
    // then, loop that word
    // with i, get the prefix and get other words in,
    // for each word, put in the list and do dfs
    // the dfs: i,
    if (words == null || words.length === 0) {
        return [];
    }
    const len = words[0].length;
    const map = new Map();
    for (let word of words) {
        for (let i = 0; i < word.length; i++) {
            const prefix = word.slice(0, i + 1);
            const list = map.get(prefix) || [];
            list.push(word); // !!! push, not add
            map.set(prefix, list);
        }
    }
    const ans = [];
    const list = [];
    recurse(0);
    return ans;
   
    function recurse (i) {
        if (i === len) { // !!! len, not list.length
            ans.push([...list]);
            return;
        }
        const prefix = list.map(str => str[i]).join('');
        const candidates = prefix ? (map.get(prefix) || []) : words; // !!! possible that prefix not in the map !!!
        for (let str of candidates) {
            // !!! not considering duplicates; it will be tricky because: string are considered primitives in js,
            // we might create another wrapper class over original string to solve this: so we can mark a string used or visited.
            list.push(str);
            recurse(i + 1);
            list.pop();
        }
    }
};

1220 3. Word Search II


擦，用map也能过

/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(board, words) {
    // can we use hashmap? will the memory explode?
    if (board == null || board.length === 0 || words == null || words.length === 0) {
        return [];
    }
    const rowLen = board.length;
    const colLen = board[0].length;
    const map = new Map();
    for (let word of words) {
        for (let i = 0; i < word.length; i++) {
            const prefix = word.slice(0, i + 1);
            const isEnd = i === word.length - 1 || !!map.get(prefix); // !!!! could already have it and isEnd
            map.set(prefix, isEnd);
        }
    }
    const ans = [];
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (map.has(board[i][j])) {
                const val = board[i][j];
                board[i][j] = null;
                if (map.get(val)) {
                    ans.push(val);
                }
                recurse(i, j, val);
                board[i][j] = val;
            }
        }
    }
    const set = new Set(ans); // !!! they don't allow dup
    return [...set];
   
    function recurse (i, j, str) {
        const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        for (let [x, y] of moves) {
            const newX = i + x;
            const newY = j + y;
            if (newX >= 0 && newX < rowLen && newY >= 0 && newY < colLen && board[newX][newY] != null) {
                const val = board[newX][newY];
                board[newX][newY] = null;
                const newStr = str + val;
                if (map.has(newStr)) {
                    if (map.get(newStr)) {
                        ans.push(newStr);
                    }
                    recurse(newX, newY, newStr);
                }
                board[newX][newY] = val;
            }
        }
    }
   
};

两个问题，
1. 题目要考的是trie
2. 这解法有一个重复，把本身的判断放到dfs里面去，避免第一次loop board时候的代码重复。这种情况比较常见。

1220 4. Best Meeting Point

/**
* @param {number[][]} grid
* @return {number}
*/
var minTotalDistance = function(grid) {
    if (grid == null || grid.length === 0) {
        return 0;
    }
    const rows = [];
    const cols = [];
    const rowLen = grid.length;
    const colLen = grid[0].length;
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (grid[i][j] === 1) {
                rows.push(i);
                cols.push(j);
            }
        }
    }
    // !!!! you need to sort it f***!!!
    return getSum(rows) + getSum(cols);
   
    function getSum (list) {
        if (list.length === 0) {return 0}
        list.sort((a, b) => a - b)
        let left = 0;
        let right = list.length - 1;
        let sum = 0;
        while (left < right) {
            sum += list[right] - list[left];
            left++;
            right--;
        }
        return sum;
    }
};

1220 5. Remove 9

/**
* @param {number} n
* @return {number}
*/
var newInteger = function(n) {
    return Number.parseInt(n.toString(9), 10); // !!! note interpreted as 10 based and return
};

1220 6. Smallest Rectangle Enclosing Black Pixels

/**
* @param {character[][]} image
* @param {number} x
* @param {number} y
* @return {number}
*/
var minArea = function(image, x, y) {
    if (image == null || image.length === 0) {
        return 0;
    }
    const rowLen = image.length;
    const colLen = image[0].length;
    let minX = Infinity;
    let maxX = -Infinity;
    let minY = Infinity;
    let maxY = -Infinity;
    recurse(x, y);
    return (maxY - minY + 1) * (maxX - minX + 1); // !!!! + 1 !!!!
   
    function recurse (i, j) {
        if ( !(i >= 0 && i < rowLen && j >= 0 && j < colLen && image[i][j] === '1') ) { // !!! not only !== null, but == 1, so actaully here we could just set invalid value to 0 because we won't use it again
            // !!! and, it is char, string, not number !!!
            return;
        }
        image[i][j] = null; // !!! important, might forget
        minX = Math.min(i, minX);
        minY = Math.min(j, minY);
        maxX = Math.max(i, maxX);
        maxY = Math.max(j, maxY);
        const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]];
        for (let [x, y] of moves) {
            const newX = i + x;
            const newY = j + y;
            recurse(newX, newY);
        }
    }
};

sicilianee 发表于 2017-12-21 16:27
1220 6. Smallest Rectangle Enclosing Black Pixels

/**

another binary search solution

1226 1.  Word Abbreviation

/**
* @param {string[]} dict
* @return {string[]}
*/
var wordsAbbreviation = function(dict) {
    // !!! the ending also matters, the trie count only applies to words with same start and ending, so we need to group them !!!
    // !!! however you still need to keep the same order as the input array, so you need the original index
    class TrieNode {
        constructor () {
            this.map = new Map();
            this.count = 0;
        }
    }
   
    if (dict == null || dict.length === 0) {
        return [];
    }
    const indexMap = new Map();
    const map = new Map();
    for (let [index, word] of dict.entries()) {
        const key = abbrev(word, 0);
        const list = map.get(key) || [];
        list.push(word);
        map.set(key, list);
        indexMap.set(word, index);
    }
    const ans = [];
    for (let list of map.values()) {
        helper(list);
    }
    return ans;
   
    function helper (dict) {
        const root = new TrieNode();
        for (let word of dict) {
            let node = root;
            for (let c of word) {
                const newNode = node.map.get(c) || new TrieNode();
                newNode.count++;
                node.map.set(c, newNode);
                node = newNode;
            }
        }
        for (let word of dict) {
            let node = root;
            let i = 0;
            for (; i < word.length; i++) {
                const c = word[i];
                const count = node.map.get(c).count;
                if (count === 1) {
                    break;
                } else {
                    node = node.map.get(c);
                }
            }
            const newWord = abbrev(word, i);
            // ans.push(newWord);
            ans[indexMap.get(word)] = newWord;
        }
    }
   
    function abbrev (word, i) { // !!!! if ith is 1, you must abbrev from the next one because you have to use it to distinguish them
        if (i >= word.length - 3) {
            return word;
        }
        const newWord = word.slice(0, i + 1) + String(word.length - i - 2) + word[word.length - 1]; // !!! plus the count part
        return newWord.length > word.length ? word : newWord;
    }
};