记录

0116 3. N-Queens

/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
    if (n === 0) {return null}
    const rows = []; // for each row, which col do we take
    const cols = Array(n).fill(false); // which cols are taken
    const diag1 = Array(2 * n - 1).fill(false);
    const diag2 = Array(2 * n - 1).fill(false);
    ans = [];
    recurse();
    return ans.map(rows => {
        const board = Array(n).fill().map(() => Array(n).fill('.'));
        rows.forEach((colIndex, rowIndex) => {
            board[rowIndex][colIndex] = 'Q'
        });
        return board.map(row => row.join(''));
    });
   
    function recurse () {
        if (rows.length === n) {
            ans.push([...rows]);
            return;
        }
        // on this row, for each col, let's test if it is possible
        const rowIndex = rows.length;
        for (let j = 0; j < n; j++) {
            // col?
            // diag1?
            // diag2?
            if (!cols[j] && !diag1[rowIndex + j] && !diag2[rowIndex - j + 3]) {
                // valid position, take this one
                // !!! since you use length of rows to get the current rowIndex, you cannot just set the value of the next
                // element in rows array, you must push and pop it while backtracking !!!
                rows.push(j);
                cols[j] = true;
                diag1[rowIndex + j] = true;
                diag2[rowIndex - j + 3] = true; // care about negative value?
                recurse();
                rows.pop(); // !!! must do, because we rely on the length to get the rowIndex
                cols[j] = false;
                diag1[rowIndex + j] = false;
                diag2[rowIndex - j + 3] = false;
            }
        }
    }
   
   
};

0117 Patching Array

/**
* @param {number[]} nums
* @param {number} n
* @return {number}
*/
var minPatches = function(nums, n) {
    // 不是一次过， 而是不断重复。
    // 一个一个元素往里面加，每次加下一个之前， 我们能够生成一个当前能够达到的1 -> edge, 每一个新的num进来，和前面所有的组合，可以达到
    // 1 -> edge -> 1 + num -> edge + num, 则edge被push到了edge + num. 其实这还是一个dp问题，类似于背包问题，而且还是顺序来的。
    // 这个解法真的是牛逼呀
    nums = nums || [];
    let edge = 1;
    let i = 0;
    let count = 0;
    while (edge <= n) {
        if (nums[i] <= edge) {
            edge = edge + nums[i];
            i++;
        } else {
            // patch the number edge to the array
            edge = edge + edge;
            count++;
        }
    }
    return count;
};

0117 2. Strobogrammatic Number III

/**
* @param {string} low
* @param {string} high
* @return {number}
*/
var strobogrammaticInRange = function(low, high) {
    // let's do a brute force one first
    let count = 0;
    const pairs = [['0', '0'], ['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']];
    for (let len = low.length; len <= high.length; len++) {
        dfs(0, len - 1, Array(len));
    }
    return count;
   
    function dfs (left, right, chars) {
        if (left > right) {
            const str = chars.join('').padStart(high.length, '0'); // !!!! str itself also needs to be padded
            const padLow = low.padStart(high.length, '0');
            if (str < padLow || str > high) {return}
            count++;
            return;
        }
        for (let pair of pairs) {
            chars[left] = pair[0];
            chars[right] = pair[1];
            if (chars.length !== 1 && chars[0] === '0') {continue} // !!! continue not return
            if (left === right && pair[0] !== pair[1]) {continue} // !!! continue not return
            dfs(left + 1, right - 1, chars);
        }
    }
};

0118 1. Edit Distance

/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
    word1 = word1 || '';
    word2 = word2 || '';
    // the reason they use dp[i][j] to represent 0 -> i - 1 to 0 -> j - 1 is, they want to include empty string.
    // if we do inclusive, we cannot have empty string because 0 is already the first element.
    // we could take i as to the ith element, whose index is i - 1
    // because we added one el, both sizes plus one
    const len1 = word1.length;
    const len2 = word2.length;
    const dp = Array(len1 + 1).fill().map(() => Array(len2 + 1).fill(0));
    // i -> 0
    for (let i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    // 0 -> j
    for (let j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }
    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            // 1. j comes from i
            const a = word1[i - 1] === word2[j - 1] // !!!!! because i, j exclusive !!!
                ? dp[i - 1][j - 1]
                : dp[i - 1][j - 1] + 1
            // 2. j comes from before i, i delete
            const b = dp[i - 1][j] + 1;
            // 3. j comes from after i, insersion
            const c = dp[i][j - 1] + 1
            dp[i][j] = Math.min(a, b, c);
        }
    }
    return dp[word1.length][word2.length];
};

0118 2. Distinct Subsequences


/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function(s, t) {
    s = s || '';
    t = t || '';
    const lenS = s.length;
    const lenT = t.length;
    const dp = Array(lenS + 1).fill().map(() => Array(lenT + 1).fill(0));
    // 0 -> j, 0
    for (let j = 0; j <= lenT; j++) {
        dp[0][j] = 0;
    }
    // i -> 0, 1
    for (let i = 0; i <= lenS; i++) {
        dp[i][0] = 1;
    }
    for (let i = 1; i <= lenS; i++) { // !!! starting from 1 not 0
        for (let j = 1; j <= lenT; j++) { // !!! same
            // 1. j comes from before i
            dp[i][j] = dp[i][j] + dp[i - 1][j];
            // 2. j comes from i, add these two
            if (s[i - 1] === t[j - 1]) { // !!!! again, f***ing again !!!
                dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
            }
        }
    }
    return dp[lenS][lenT];
};

same as edit distance. Both have the same trap: i, j and i - 1, j - 1 when comparing.

0118 3.  Rearrange String k Distance Apart

/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var rearrangeString = function(s, k) {
    if (s == null || s.length === 0) {
        return s;
    }
    const map = new Map();
    const valid = new Map();
    for (let c of s) {
        const val = map.get(c) || 0;
        map.set(c, val + 1);
        valid.set(c, 0);
    }
    const list = [];
    for (let i = 0; i < s.length; i++) {
        const c = getValidChar(i);
        if (c == null) {return '';}
        list.push(c); // !!! add it !!!
        map.set(c, map.get(c) - 1);
        valid.set(c, i + k); // !!! i + k not valid.get(c) + k
    }
    return list.join('');
   
    // whichever one has the most count so far, we use it
    function getValidChar (i) {
        let max = -Infinity;
        let candidate = null;
        for (let [key, val] of map.entries()) {
            if (val > 0 && val > max && i >= valid.get(key)) {
                candidate = key;
                max = val;
            }
        }
        return candidate;
    }
   
};

0118 4. Sudoku Solver

/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
    if (board == null || board.length === 0 || board[0].length === 0) {return}
    develop();
   
    function develop () {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] !== '.') {continue;}
                // choose a number
                for (let num = 1; num <= 9; num++) {
                    if (isValid(num, i, j)) {
                        board[i][j] = String(num);
                        if (develop()) {return true;}
                        board[i][j] = '.';
                    }
                }
                // cannot fulfil this cell, false;
                return false;
            }
        }
        // reached the end successfully, all valid, I guess we shouldn't reach here though.
        return true;
    }
   
   
    function isValid (num, row, col) {
        for (let i = 0; i < 9; i++) {
            // check the same row, with row index row, col index i
            if (board[row][i] === String(num)) {return false;}
            // check the same col, with col index col, row index i
            if (board[i][col] === String(num)) {return false;}
            const anchorRow = row - row % 3;
            const anchorCol = col - col % 3;
            const x = anchorRow + Math.trunc(i / 3);
            const y = anchorCol + i % 3;
            if (board[x][y] === String(num)) {return false;}
        }
        return true;
    }
};

sicilianee 发表于 2018-1-19 14:40
0118 4. Sudoku Solver

/**

could further optimize using hashtable/matrix

0205 1. Range Module



var RangeModule = function() {
    this.ranges = [];
};

RangeModule.prototype.addRange = function(left, right) {
    let index = this.ranges.findIndex(r => r[0] >= left);
    index = index < 0 ? this.ranges.length : index;
    this.ranges.splice(index, 0, [left, right]);
    this.merge()
};

// !!! error-prone
// 1. confuse list and this.ranges
// 2. consider 1 -> 5, 5 -> 10
RangeModule.prototype.merge = function () {
    const list = []
    for (let [left, right] of this.ranges) {
        if (list.length === 0) {
            list.push([left, right]);
        } else {
            const top = list[list.length - 1]
            if (top[1] >= left) { // !!! >= not <=
                list.pop();
                const newStart = top[0]
                const newEnd = Math.max(top[1], right);
                list.push([newStart, newEnd]);
            } else {
                list.push([left, right]);
            }
        }
    }
    this.ranges = list;
}

// now do the query
// this is the last part, can do this in lgn
// by left boundary, first find biggest one that is smaller/equal than it
// edge cases:
// 1. not found, no
// !!! binary search for position: still need to practice more
RangeModule.prototype.queryRange = function(left, right) {
    // find by left
    let low = 0;
    let high = this.ranges.length - 1;
    while (low <= high) {
        const mid = low + Math.trunc((high - low) / 2);
        const midVal = this.ranges[mid][0]; // !!!! [0] because that is a range, not a value
        // find a position, target not in the list, should put midVal on the left
        // equal is smaller
        if (midVal <= left) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    console.log(high)
    // use high
    if (high < 0) {
        return false
    } else {
        return this.ranges[high][1] >= right
    }
};

// also a bit complex:
// intersect or not, if intersect, more to do
RangeModule.prototype.removeRange = function(left, right) {
    const list = [];
    for (let range of this.ranges) {
        if (range[1] <= left || range[0] >= right) {
            list.push(range)
        } else {
            if (range[0] < left) {
                list.push([range[0], left]);
            }
            if (right < range[1]) {
                list.push([right, range[1]]);
            }
        }
    }
    this.ranges = list;
    console.log(this.ranges)
};

0205 2.  Sliding Puzzle


var slidingPuzzle = function(board) {
    if (board == null || board.length === 0 || board[0].length === 0) {
        return -1
    }
    const target = '1,2,3,4,5,0'
    let count = 0;
    const q = [board]
    const set = new Set([getKey(board)])
    while (q.length > 0) {
        const size = q.length;
        for (let i = 0; i < size; i++) {
            const node = q.shift();
            if (getKey(node) === target) {
                return count;
            }
            const [i, j] = (() => {
                for (let i = 0; i < 2; i++) {
                    for (let j = 0; j < 3; j++) {
                        if (node[i][j] === 0) {
                            return [i, j]
                        }
                    }
                }
            })();
            const moves = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            for (let [dx, dy] of moves) {
                // !!! construct a 2d array, not 1d
                const newNode = [[...node[0]], [...node[1]]];
                const newX = i + dx;
                const newY = j + dy;
                if (newX >= 0 && newX < 2 && newY >= 0 && newY < 3) {
                    ;[newNode[i][j], newNode[newX][newY]] = [newNode[newX][newY], newNode[i][j]];
                    const key = getKey(newNode);
                    if (!set.has(key)) {
                        set.add(key);
                        q.push(newNode);
                    }
                }
            }
        }
        count++;
    }
    return -1;
    function getKey (board) {
        const list = [...board[0], ...board[1]]
        return list.join(',')
    }
};