记录

1206 5. Minimum Height Trees

/**
* @param {number} n
* @param {number[][]} edges
* @return {number[]}
*/
var findMinHeightTrees = function(n, edges) {
    // build the adj list
    // get all leaves
    // start loop
    // remove all leaves, find new leaves
    // till only 2 / 1 left
    // return the leaves
    if (n === 1) {return [0]} // !!!! special case how to uniform?
    const adj = Array(n).fill().map(() => Array()); // !!! TODO: use set, not list, cuz you need to remove elements based on value
    for (let [a, b] of edges) {
        adj[a].push(b);
        adj[b].push(a);
    }
    let leaves = [];
    for (let [i, list] of adj.entries()) { // !!! array.entries(), not Object.entries(). The latter will turn it into string
        if (list.length === 1) {
            leaves.push(i);
        }
    }
    while (n > 2) {
        n = n - leaves.length;
        const newLeaves = [];
        for (let leaf of leaves) {
            const next = adj[leaf][0];
            // newLeaves.push(next);
            const index = adj[next].indexOf(leaf);
            adj[next].splice(index, 1);
            if (adj[next].length === 1) {
                newLeaves.push(next);
            }
        }
        console.log(leaves)
        leaves = newLeaves;
    }
    return leaves;
};

1206 6. Next Permutation

/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function(nums) {
    // 4327654321
    // 4331224567
    if (nums == null || nums.length < 2) {
        return;
    }
    // find the first smaller one from back to front
    let i
    for (i = nums.length - 2; i >= 0 && nums[i] >= nums[i + 1]; i--);
    console.log(i)
    if (i === -1) { // !!! -1, not 0
        nums.reverse(); // !!! don't return anything!!!
        return; // !! but still need to return
    }
    let j;
    for (j = i + 1; j < nums.length && nums[j] > nums[i]; j++); // !!! this one is ++
    j--;
    console.log(j)
    ;[nums[i], nums[j]] = [nums[j], nums[i]];
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
        ;[nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--; // !!! shit update the loop
    }
};

1207 1. Reverse Words in a String II

/**
* @param {character[]} str
* @return {void} Do not return anything, modify str in-place instead.
*/
var reverseWords = function(str) {
    if (str == null || str.length === 0) {
        return;
    }
    let start = 0;
    for (let i = 0; i <= str.length; i++) {
        if (i === str.length || str[i] === ' ') {
            reverse(str, start, i - 1);
            start = i + 1;
        }
    }
    reverse(str, 0, str.length - 1);
};

function reverse (chars, i, j) {
    let left = i;
    let right = j;
    while (left < right) {
        ;[chars[left], chars[right]] = [chars[right], chars[left]];
        left++;
        right--;
    }
}

1207 2. Sentence Screen Fitting

/**
* @param {string[]} sentence
* @param {number} rows
* @param {number} cols
* @return {number}
*/
var wordsTyping = function(sentence, rows, cols) {
    if (sentence == null || sentence.length === 0) {
        return 0;
    }
    const all = sentence.join(' ') + ' ';
    const len = all.length;
    let start = 0;
    for (let i = 0; i < rows; i++) {
        start += cols;
        if (all[start % len] === ' ') {
            console.log('got here');
            start++;
        } else {
            while (start > 0 && all[(start - 1) % len] !== ' ') { // 1. start > 0
                // 2. !!! all[(start - 1) % len !== ' '], never found this !!!! Wrong parenthesis !!!!
                start--;
            }
        }
    }
    return Math.floor(start / len);
};

1207 3. Design Snake Game

/**
* Initialize your data structure here.
        @param width - screen width
        @param height - screen height
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
* @param {number} width
* @param {number} height
* @param {number[][]} food
*/
var SnakeGame = function(width, height, food) {
    this.width = width;
    this.height = height;
    this.board = new Set();
    this.board.add('0:0');
    this.list = [[0, 0]];
    // !!! food is a list of food, it is not one food
    this.food = food || [];
};

/**
* Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
        @return The game's score after the move. Return -1 if game over.
        Game over when snake crosses the screen boundary or bites its body.
* @param {string} direction
* @return {number}
*/
SnakeGame.prototype.move = function(direction) {
    const top = this.list[this.list.length - 1];
    const moves = {
        'U': [-1, 0],
        'D': [1, 0],
        'L': [0, -1],
        'R': [0, 1]
    };
    const aFood = this.food.length > 0 ? this.food[0] : [-1, -1];
    const move = moves[direction];
    const nextx = top[0] + move[0];
    const nexty = top[1] + move[1];
    if (nextx >= 0 && nextx < this.height && nexty >= 0 && nexty < this.width) { // !!!! width, height, row, col, you mixed them
        // !!!!!!! there is a sequence matter, you need to first remove the last one then test if hit self
        if (nextx === aFood[0] && nexty === aFood[1]) { // hit food
            this.food.shift();
        } else {
            const bottom = this.list.shift();
            // this.board[bottom[0]][bottom[1]] = false;
            this.board.delete(`${bottom[0]}:${bottom[1]}`);
            if (this.board.has(`${nextx}:${nexty}`)) { // after remove last one, hit self?
                return -1;
            }
        }
        this.list.push([nextx, nexty]);
        this.board.add(`${nextx}:${nexty}`);
        return this.list.length - 1;
    } else {
        return -1;
    }
};

/**
* Your SnakeGame object will be instantiated and called as such:
* var obj = Object.create(SnakeGame).createNew(width, height, food)
* var param_1 = obj.move(direction)
*/

1207 4. Remove Comments

/**
* @param {string[]} source
* @return {string[]}
*/
var removeComments = function(source) {
    if (source == null || source.length === 0) {
        return source;
    }
    const ans = [];
    while (source.length > 0) {
        const line = source.shift();
        let i;
        for (i = 0; i <= line.length - 2; i++) {
            const str = line.slice(i, i + 2);
            if (str === '//' || str === '/*') {
                break;
            }
        }
        if (i === line.length - 1) {
            ans.push(line);
        } else {
            if (line.slice(i, i + 2) === '//') {
                const remain = line.slice(0, i);
                if (remain) {ans.push(remain)}
            } else {
                const firstPart = line.slice(0, i);
                const secondPart = line.slice(i + 2);
                source.unshift(secondPart);
                let found = false;
                while (!found) {
                    const aLine = source.shift();
                    let j;
                    for (j = 0; j <= aLine.length - 2; j++) {
                        if (aLine.slice(j, j + 2) === '*/') {
                            found = true;
                            break;
                        }
                    }
                    if (found) {
                        const remain = aLine.slice(j + 2);
                        const all = firstPart + remain;
                        if (all) {
                            source.unshift(all);
                        }
                    }
                }
            }
        }
    }
    return ans;
};

sicilianee 发表于 2017-12-8 15:41
1207 4. Remove Comments

/**

难搞 多加练习

1209 1.  Range Sum Query 2D - Immutable

/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix) {
    if (matrix == null || matrix.length === 0 || matrix[0].length === 0) { // !!! this kind of check, they really do
        this.nothing = true;
        return;
    }
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    const dp = Array(rowLen).fill().map(() => Array(colLen).fill(0));
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            const top = i === 0 ? 0 : dp[i - 1][j];
            const left = j === 0 ? 0 : dp[i][j - 1];
            const topLeft = i === 0 || j === 0 ? 0 : dp[i - 1][j - 1];
            dp[i][j] = top + left - topLeft + matrix[i][j];
        }
    }
    this.dp = dp;
};

/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    if (this.nothing) {
        return 0;
    }
    const self = this.dp[row2][col2];
    const top = row1 === 0 ? 0 : this.dp[row1 - 1][col2];
    const left = col1 === 0 ? 0 : this.dp[row2][col1 - 1];
    const topLeft = row1 === 0 || col1 === 0 ? 0 : this.dp[row1 - 1][col1 - 1];
    return self - top - left + topLeft;
};

/**
* Your NumMatrix object will be instantiated and called as such:
* var obj = Object.create(NumMatrix).createNew(matrix)
* var param_1 = obj.sumRegion(row1,col1,row2,col2)
*/

1209 2. Maximum Product Subarray

/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    const len = nums.length;
    let max = nums[0];
    let imax = max;
    let imin = max;
    for (let i = 1; i < len; i++) {
        const num = nums[i];
        // !!! the sequence matters !!!!
        ;[imax, imin] = [Math.max(num, imax * num, imin * num), Math.min(num, imax * num, imin * num)];
        max = Math.max(imax, imin, max);
    }
    return max;
};

1209 3. Wiggle Sort II

/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var wiggleSort = function(nums) {
    const tmp = [...nums];
    tmp.sort((a, b) => a - b);
    let j = Math.floor((nums.length - 1) / 2);
    let k = nums.length - 1;
    for (let i = 0; i < nums.length; i++) { // !! how many times
        if (i % 2 === 0) {
            nums[i] = tmp[j]; // !!! separate them
            j--;
        } else {
            nums[i] = tmp[k];
            k--;
        }
    }
};