记录

1217 2. Surrounded Regions

/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
    if (board == null || board.length === 0 || board[0].length === 0) {
        return;
    }
    // go bfs, first, put all border Os into the q
    const q = [];
    const rowLen = board.length;
    const colLen = board[0].length;
    for (let i = 0; i < rowLen; i++) { // !!!! < rowLen, not < rowLen -1, what the heck
        if (board[i][0] === 'O') {
            board[i][0] = 'M';
            q.push([i, 0]);
        }
        if (board[i][colLen - 1] === 'O') {
            board[i][colLen - 1] = 'M';
            q.push([i, colLen - 1]);
        }
    }
    for (let j = 0; j < colLen; j++) {
        if (board[0][j] === 'O') {
            board[0][j] = 'M';
            q.push([0, j]);
        }
        if (board[rowLen - 1][j] === 'O') {
            board[rowLen - 1][j] = 'M';
            q.push([rowLen - 1, j]);
        }
    }
    const moves = [[0, 1], [0, -1], [-1, 0], [1, 0]]
    while (q.length > 0) {
        const node = q.shift();
        for (let [mx, my] of moves) {
            const x = node[0] + mx;
            const y = node[1] + my;
            if (x >= 0 && x < rowLen && y >= 0 && y < colLen && board[x][y] === 'O') {
                board[x][y] = 'M';
                q.push([x, y]);
            }
        }
    }
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (board[i][j] === 'M') {
                board[i][j] = 'O';
            } else {
                board[i][j] = 'X';
            }
        }
    }
};

1217 3. Sequence Reconstruction

/**
* @param {number[]} org
* @param {number[][]} seqs
* @return {boolean}
*/
var sequenceReconstruction = function(org, seqs) {
    if (org == null || org.length === 0 || seqs == null || seqs.length === 0) {
        return false;
    }
    const adjMap = new Map();
    for (let seq of seqs) {
        for (let i = 0; i < seq.length; i++) {
            const start = seq[i];
            const set = adjMap.get(start) || new Set();
            adjMap.set(start, set);
            if (i + 1 < seq.length) {
                const end = seq[i + 1];
                set.add(end);
            }
        }
    }
    // all edges are included in the path
    for (let [start, set] of adjMap.entries()) {
        const startIndex = org.indexOf(start);
        if (startIndex < 0) {
            return false;
        }
        for (let end of set) {
            const endIndex = org.indexOf(end);
            if (!(endIndex >= 0 && startIndex < endIndex)) {
                return false;
            }
        }
    }
    // all path edges exist in the edges
    for (let i = 0; i < org.length; i++) {
        const start = org[i];
        if (!adjMap.has(start)) {
            return false;
        }
        if (i + 1 < org.length) {
            const end = org[i + 1];
            if (!adjMap.get(start).has(end)) {
                return false;
            }
        }
    }
    return true;
};

1217 4.  Contains Duplicate III

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2) { // !!!! at least 2 els to fulfill the condition
            return false;
        }
        TreeSet<Integer> set = new TreeSet<Integer>();
        int low = -1;
        int high = 0;
        while (high < nums.length) {
            // !!!! 1. you check before you add it otherwise it would have itself !!!!.
            if (set.ceiling(nums[high]) != null && set.ceiling(nums[high]) <= t + nums[high]
               || set.floor(nums[high]) != null && nums[high] <= t + set.floor(nums[high])) { // !!!! change the sequence to avoid overlfow !!!!
                return true;
            }
            set.add(nums[high]);
            if (high - low > k) { // !!! index diff at most k, then the window size is at most k + 1, but we do before we check,
                // so the set size is then at most k +
                low++;
                set.remove(nums[low]);
            }
            high++;
        }
        return false;
    }
}

1217 5. Fraction to Recurring Decimal

/**
* @param {number} numerator
* @param {number} denominator
* @return {string}
*/
var fractionToDecimal = function(numerator, denominator) {
    let prefix = '';
    if (numerator / denominator < 0) { // !!!! well, needed
        numerator = Math.abs(numerator);
        denominator = Math.abs(denominator);
        prefix = '-'
    }
    const intPart = String(Math.trunc(numerator / denominator));
    let rem = numerator % denominator;
    const map = new Map();
    map.set(rem, -1); // !!! this is important
    let fractionPart = '';
    let index = 0;
    while (rem !== 0) {
        const num = 10 * rem;
        const digit = Math.trunc(num / denominator);
        rem = num % denominator; // !!! here % not /
        // !!!!! we don't break here immediately, still need to add that digit if rem === 0, just stop after adding it
        // !!! also even start recurring, the current one you still need to add it, rem repeat means the next one digit will repeat, not the current one, the currrent one is under the prev rem
        fractionPart = fractionPart + digit;
        if (map.has(rem)) {
            const startIndex = map.get(rem) + 1; // !!! plus one
            fractionPart = fractionPart.slice(0, startIndex) + '(' + fractionPart.slice(startIndex) + ')';
            return prefix + intPart + '.' + fractionPart;
        } else {
            map.set(rem, index);
            index++;
        }
    }
    if (fractionPart.length > 0) {
        return prefix + intPart + '.' + fractionPart;
    } else {
        return prefix + intPart;
    }
};

1217 6.  Unique Word Abbreviation

/**
* @param {string[]} dictionary
*/
var ValidWordAbbr = function(dictionary) {
    this.set = new Set(dictionary);
    this.map = new Map();
    for (let word of this.set) { // !!! loop the set, not the dict !!!
        const abbr = getAbbr(word);
        const val = this.map.get(abbr) || 0;
        this.map.set(abbr, val + 1);
    }
};

function getAbbr (word) {
    if (word == null || word.length < 3) {
        return word;
    }
    return word[0] + String(word.length - 2) + word[word.length - 1];
}

/**
* @param {string} word
* @return {boolean}
*/
ValidWordAbbr.prototype.isUnique = function(word) {
    const abbr = getAbbr(word);
    const count = this.map.get(abbr) || 0;
    console.log(this.set)
    console.log(count)
    return !this.set.has(word) && count === 0 || this.set.has(word) && count === 1;
};

/**
* Your ValidWordAbbr object will be instantiated and called as such:
* var obj = Object.create(ValidWordAbbr).createNew(dictionary)
* var param_1 = obj.isUnique(word)
*/

蛮奇怪的一道题

sicilianee 发表于 2017-12-18 12:49
1217 6.  Unique Word Abbreviation

/**

one map is enough

1218 1.  Divide Two Integers

class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean neg = divisor > 0 ^ dividend > 0;
        long dvd = Math.abs((long) dividend); // !!!! 1. need to convert to long, otherwise still overflow the same thing
        long dvs = Math.abs((long) divisor);
        long ans = 0;
        while (dvd >= dvs) {
            long tmp = dvs; // !!!! 2. oh, that's the reason they don't overflow, they use long here. !!!! while in js it is treated as 32-bit signed int
            long multiplier = 1;
            while ( (tmp << 1) < dvd ) {
                tmp = tmp << 1;
                multiplier = multiplier << 1;
            }
            dvd = dvd - tmp;
            ans = ans + multiplier;
        }
        return (int) (neg ? -ans : ans);
    }
}

sicilianee 发表于 2017-12-19 12:18
1218 1.  Divide Two Integers

class Solution {

只能用java做，要练熟

1218 2. Shortest Completing Word

/**
* @param {string} licensePlate
* @param {string[]} words
* @return {string}
*/
var shortestCompletingWord = function(licensePlate, words) {
    if (licensePlate == null || words == null) {throw new Error()}
    if (words.length === 0) {
        return '';
    }
    licensePlate = licensePlate.toLowerCase();
    words = words.map(w => w.toLowerCase());
    const map = new Map();
    for (let c of licensePlate) {
        if (c >= 'a' && c <= 'z') {
            const count = map.get(c) || 0;
            map.set(c, count + 1);
        }
    }
    let minWord = null;
    for (let word of words) {
        const newMap = new Map();
        for (let c of word) {
            const count = newMap.get(c) || 0;
            newMap.set(c, count + 1);
        }
        let good = true;
        for (let [key, val] of map) {
            if (!newMap.has(key) || newMap.get(key) < val) {
                good = false;
                break;
            }
        }
        if (good) {
            if (minWord == null || word.length < minWord.length) {
                minWord = word;
            }
        }
    }
    return minWord;
};

1218 3. Reverse Words in a String

/**
* @param {string} str
* @returns {string}
*/
var reverseWords = function(str) {
    if (str == null || str.length === 0) {return str}
    str = str.split(' ').filter(s => s).join(' ');
    const chars = str.split('');
    console.log(chars);
    for (let i = 0; i < chars.length; i++) {
        if (chars[i] !== ' ') {
            let j = i;
            while (j < chars.length && chars[j] !== ' ') {j++;} // !!! chars[j], not chars[i]. again vars mix
            reverse(i, j - 1);
            // !!! this update !!!
            i = j - 1;
        }
    }
    console.log(chars);
    reverse(0, chars.length - 1);
    return chars.join('');
   
   
    function reverse (i, j) {
        while (i < j) {
            ;[chars[i], chars[j]] = [chars[j], chars[i]];
            i++;
            j--;
        }
    }
};

the loop pattern needs practicing.