记录

1128 1.  Generalized Abbreviation

/**
* @param {string} word
* @return {string[]}
*/
var generateAbbreviations = function(word) {
    if (word == null || word.length === 0) {return [word]}
    const len = word.length;
    const limit = 1 << len;
    const res = [];
    for (let i = 0; i < limit; i++) {
        // !!!! 1. not directly to string, that's 10-based. You need to convert it to 2-based
        // 2. not directly to 2-based string because you need to pad it with zeros!!!!
        const str = i.toString(2).padStart(len, '0');
        const list = [];
        let k = 0; // !!!! you define i again, and in line 11, you got ReferenceError
        while (k < str.length) {
            if (str[k] === '0') {
                list.push(word[k]);
                k++;
            } else {
                let j = k;
                while (j < str.length && str[j] === '1') {
                    j++;
                }
                const count = j - k;
                list.push(String(count));
                k = j;
            }
        }
        res.push(list.join(''));
    }
    return res;
};

1128 2. Binary Tree Upside Down

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var upsideDownBinaryTree = function(root) {
    if (root == null) {return root}
    let node = root;
    let left = node.left;
    let right = node.right;
    node.left = node.right = null; // !!! Clean this up or you'll have circular reference. The root one is not processed
    while (left != null) {
        // 1. !!! don't be afraid to use tmp vars
        // 2. sure you can delete them later, !!! but that might also cause problems because the result might depend on the order
        const nextLeft = left.left;
        const nextRight = left.right;
        const nextNode = left;
        left.left = right;
        left.right = node;
        left = nextLeft;
        right = nextRight;
        node = nextNode;
        console.log(left);
    }
    console.log(left)
    return node;
};

1128 3. Walls and Gates

/**
* @param {number[][]} rooms
* @return {void} Do not return anything, modify rooms in-place instead.
*/
var wallsAndGates = function(rooms) {
    // check
    // loop and find i, j with 0, put them into q
    // bfs, for each room, get its value and next value, test all four directions, if is INF, put the next value to it, and
    // put that room into the q until the q is empty
    if (rooms == null || rooms.length === 0) {
        return;
    }
    const q = [];
    const rowLen = rooms.length;
    const colLen = rooms[0].length;
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (rooms[i][j] === 0) {
                q.push([i, j]);
            }
        }
    }
    const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    while (q.length > 0) {
        const [x, y] = q.shift();
        const val = rooms[x][y];
        const newVal = val + 1;
        for (let move of moves) {
            const newX = x + move[0];
            const newY = y + move[1];
            if (newX >= 0 && newX < rowLen && newY >= 0 && newY < colLen && rooms[newX][newY] === 2147483647) {
                rooms[newX][newY] = newVal;
                q.push([newX, newY]);
            }
        }
    }
};

1128 4. Lonely Pixel II

/**
* @param {character[][]} picture
* @param {number} N
* @return {number}
*/
var findBlackPixel = function(picture, N) {
    if (picture == null || picture.length === 0) {
        return 0;
    }
    const rowLen = picture.length;
    const colLen = picture[0].length;
    const map = new Map();
    const colCounts = Array(colLen).fill(0);
    for (let i = 0; i < rowLen; i++) {
        let rowCount = 0;
        for (let j = 0; j < colLen; j++) {
            if (picture[i][j] === 'B') {
                rowCount++;
                colCounts[j]++;
            }
        }
        if (rowCount === N) {
            const signature = picture[i].join('');
            const val = map.get(signature) || 0;
            map.set(signature, val + 1);
        }
    }
    let validCount = 0;
    for (let [signature, count] of map.entries()) {
        if (count === N) {
            for (let i = 0; i < signature.length; i++) {
                if (signature[i] === 'B' && colCounts[i] === N) {
                    validCount++;
                }
            }
        }
    }
    return validCount * N;
};

1128 5.  Sort Transformed Array

/**
* @param {number[]} nums
* @param {number} a
* @param {number} b
* @param {number} c
* @return {number[]}
*/
var sortTransformedArray = function(nums, a, b, c) {
    if (nums == null || nums.length === 0) {return nums;}
    const isNegative = a < 0;
    let inputs = [];
    if (a === 0) { // !!!! a is 0.
        inputs = b >= 0 ? nums : nums.reverse();
    } else {
        const x = -b / (2 * a);
        let i = 0;
        for (; i < nums.length; i++) {
            if (nums[i] >= x) {break;}
        }
        let left = i - 1;
        let right = i;
        while (left >= 0 || right < nums.length) {
            const leftDiff = left >= 0 ? Math.abs(nums[left] - x) : Infinity;
            const rightDiff = right < nums.length ? Math.abs(nums[right] - x) : Infinity;
            if (leftDiff <= rightDiff) {
                inputs.push(nums[left]);
                left--;
            } else {
                inputs.push(nums[right]);
                right++;
            }
        }
    }
    const calc = num => a * num * num + b * num + c;
    const vals = inputs.map(num => calc(num));
    return isNegative ? vals.reverse() : vals;
   
};

sicilianee 发表于 2017-11-29 13:34
1128 5.  Sort Transformed Array

/**

可以从最大的数（两边）开始。可以不用算对称轴，直接计算出每一个的结果，从两边向中间移动，每次比较取较大的一个，一直加到最小的那个。

1128 6. Number of Distinct Islands

/**
* @param {number[][]} grid
* @return {number}
*/
var numDistinctIslands = function(grid) {
    // keep a set
    // double loop the grid, i, j if is 1, go recursive, i, j, str
    // inside recursive, add self, set self to visited, move four directions,
    // for each direction, if valid index and is 1, visit it
    // if none of them is 1, this is the last point, add the key to set
    // last return the set size
    if (grid == null || grid.length === 0) {return 0}
    const rowLen = grid.length;
    const colLen = grid[0].length;
    const set = new Set();
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (grid[i][j] === 1) {
                const list = []; // !!! this list is important. You cannot just give it a string key and let it decide when to add it because you need to make sure you only add it once for the whole connected graph, not add it once for each leaf node. Thus you have to find a single exit point, that is when all this dfs is finished. So you need a global list for each dfs. Thus pass it.
                recurse(i, j, i, j, list);
                set.add(list.join('_'));
            }
        }
    }
    return set.size;
   
   
    function recurse (x, y, i, j, list) {
        // assume self is valid
        const ix = i - x;
        const jy = j - y; // !!!! j - y and you put i - y. same variable mix again and again and again.
        // No1 mistake: loop variable update No2 mistake: variable mix
        list.push(`${ix}_${jy}`);
        grid[i][j] = 0;
        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];
            if (newi >= 0 && newi < rowLen && newj >= 0 && newj < colLen && grid[newi][newj] === 1) {
                recurse(x, y, newi, newj, list);
            }
        }
    }
};

1129 1. Android Unlock Patterns

/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var numberOfPatterns = function(m, n) {
    // keep a used array
    // double loop the board, for each el, start the dfs with a count == 0
    // dfs: for each el, check and visit itself, mark visited, add up count, check if we add to final global res count
    // after self, loop the whole board, see if that position is valid, is, visit it
    // (note each time the current count is valid, we add it to the res count)
    // when we need to return, reset used  (count is auto reset)
    // 3, 3
    const used = Array(3).fill().map(() => Array(3).fill(false));
    let res = 0;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            recurse(i, j, 0);
        }
    }
    return res;
   
    function recurse (x, y, count) {
        // assume self is valid
        used[x][y] = true;
        count++;
        if (count >= m && count <= n) {
            res++;
        }
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (isValid(x, y, i, j)) {
                    recurse(i, j, count);
                }
            }
        }
        used[x][y] = false;
    }
   
    function isValid (x1, y1, x2, y2) {
        if (used[x2][y2]) {
            return false;
        }
        const diffx = Math.abs(x1 - x2);
        const diffy = Math.abs(y1 - y2);
        if (diffx + diffy === 1) { // adjacent
            return true;
        } else if (diffx === 1 && diffy === 1) { // diagonal
            return true;
        } else if (diffx === 1 && diffy === 2 || diffx === 2 && diffy === 1) { // knight move
            return true;
        } else { // one el in between
            const midx = (x1 + x2) / 2;
            const midy = (y1 + y2) / 2;
            return used[midx][midy];
        }
    }
};

1129 2. The Maze

/**
* @param {number[][]} maze
* @param {number[]} start
* @param {number[]} destination
* @return {boolean}
*/
var hasPath = function(maze, start, destination) {
    // keep a used array
    // from the start position, start dfs
    // the dfs: put the current position into used
    // from the current position, try moving four directions,
    // if one direction is allowed, keep moving until you hit a wall, stop there,
    // if that one is the dest, return true
    // if that one is not used, dfs it
    // after all four dfss, return false
    if (maze == null || maze.length === 0 || maze[0].length === 0) {return false}
    const rowLen = maze.length;
    const colLen = maze[0].length;
    const used = Array(rowLen).fill().map(() => Array(colLen).fill(false));
    if (start[0] === destination[0] && start[1] === destination[1]) {
        return true;
    }
    return recurse(...start);
   
    function recurse (i, j) {
        // i j must be a valid stop point and is not the destination
        used[i][j] = true;
        const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]];
        for (let move of moves) {
            let x = i;
            let y = j;
            const mx = move[0];
            const my = move[1];
            while (x + mx >= 0 && x + mx < rowLen && y + my >= 0 && y + my < colLen
                  && maze[x + mx][y + my] === 0) {
                x = x + mx;
                y = y + my;
            }
            // stopped at a wall
            if (x === destination[0] && y === destination[1]) {
                return true;
            }
            if (!used[x][y]) {
                if (recurse(x, y)) {
                    return true;
                }
            }
        }
        return false;
    }
};

1130 1. Factor Combinations

/**
* @param {number} n
* @return {number[][]}
*/
var getFactors = function(n) {
    // dfs i n, i is the current start element, i > 1, n is the remaining number
    // for each dfs, if i === n return true
    // loop from i to n / i, ===, floor, if n / j % 0, dfs j, n / j
    // after loop, return false
    const res = [];
    const list = []; // !!! need a list
    for (let i = 2; i * i <= n; i++) {
        if (n % i === 0) {
            list.push(i);
            recurse(i, n / i);
            list.pop();
        }
    }
    return res;
    function recurse (i, n) {
        // i is the last used element. When you enter recurse, you must have already used some el, so n is no longer the original n
        // take self as the last
        // or not the last, loop
        if (n < i) {return}
        list.push(n);
        res.push([...list]);
        list.pop();
        for (let j = i; j * i <= n; j++) {
            if (n % j === 0) {
                list.push(j);
                recurse(j, n / j);
                list.pop();
            }
        }
    }
};
// feel each key stroke. feel each key stroke, and you will be very clear about what you are doing right now and you won't make
// any mistakes. Feel now. now-conscious


这个做法太蠢。有没有好点的办法？