记录

1126 5. Shortest Word Distance III

/**
* @param {string[]} words
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var shortestWordDistance = function(words, word1, word2) {
    if (words == null || words.length === 0) {return -1}
    let i1 = null;
    let i2 = null;
    let min = Infinity;
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        if (word === word1) {
            i1 = i;
        }
        if (word === word2) {
            if (word1 === word2) {
                i1 = i2;
                i2 = i;
            } else {
                i2 = i;
            }
        }
        // !!! Infinity - Infinity becomes null, so we shall use null and test the two
        if (i1 != null && i2 != null) {
            min = Math.min(min, Math.abs(i2 - i1));
        }
        // !!! you forgot the 'min = ' part of the assignment. What a bug is this?
    }
    return min;
};

1126 6. Kill Process

/**
* @param {number[]} pid
* @param {number[]} ppid
* @param {number} kill
* @return {number[]}
*/
var killProcess = function(pid, ppid, kill) {
    const map = new Map(pid.map(aPid => [aPid, []])); // pid, []
    for (let i = 0; i < pid.length; i++) {
        const parentId = ppid[i];
        const childId = pid[i];
        if (parentId !== 0) { // !!! there is one with 0 meaning no parent
            map.get(parentId).push(childId);
        }
    }
    const res = [];
    let nodes = [kill]; // ## use an array to form a recursive condition for the loop
    while (nodes.length > 0) {
        res.push(...nodes);
        const children = [];
        for (let node of nodes) {
            children.push(...map.get(node));
        }
        nodes = children;
    }
    return res;
   
};

1127 1. Path Sum IV

/**
* @param {number[]} nums
* @return {number}
*/
var pathSum = function(nums) {
    // check
    // put all nums into a map: index -> value
    // from the root node, start recurse
    // keep the sum
    // till leave, add to res
    if (nums == null || nums.length === 0) {return []}
    const map = new Map();
    for (let num of nums) {
        const numStr = `${num}`;
        const key = numStr.slice(0, 2);
        const val = Number.parseInt(numStr[2], 10);
        map.set(key, val);
    }
    const res = []; // then there is no need for the list, just a global sum work sufficent.
    recurse(0, `${nums[0]}`.slice(0, 2));
    return res.reduce((a, b) => a + b);

   
    function recurse (sum, key) {
        // caller: make sure key node is not null
        sum += map.get(key);
        const nextLevel = Number.parseInt(key[0], 10) + 1;
        const i = Number.parseInt(key[1], 10);
        const left = 2 * i - 1;
        const right = 2 * i;
        const leftKey = `${nextLevel}${left}`;
        const rightKey = `${nextLevel}${right}`;
        if (!map.has(leftKey) && !map.has(rightKey)) {
            res.push(sum);
            return;
        } else {
            if (map.has(leftKey)) { // !! neet to check to make sure no null value is passed.
                recurse(sum, leftKey);
            }
            if (map.has(rightKey)) {
                recurse(sum, rightKey)
            }
        }
    }
};

1127 2. 4 Keys Keyboard

/**
* @param {number} N
* @return {number}
*/
var maxA = function(N) {
    // key: how to find recursion concept
    // 这题很巧，一开始就从子问题的角度着眼
    // !!! 为什么算最后po多少次的时候当做子问题不对？因为那时你如果copy不仅会copy后面po的，也会copy之前（在你ca，cc之前）po的呀
    // need 2 steps to prepare, so how many do you do initially, if you do paste,
    // originally from 0 -> N - 1, do from 0 -> N - 3
    let max = N;
    for (let i = 1; i < N - 2; i++) {
        max = Math.max(max, (N - i - 1) * maxA(i)); // !!! counting the first one is N - i - 1
    }
    return max;
};

sicilianee 发表于 2017-11-28 12:18
1127 2. 4 Keys Keyboard

/**

还有dp的解法

1127 3. Design Log Storage System


var LogSystem = function() {
    this.logs = [];
};

/**
* @param {number} id
* @param {string} timestamp
* @return {void}
*/
LogSystem.prototype.put = function(id, timestamp) {
    this.logs.push([id, timestamp]);
};

/**
* @param {string} s
* @param {string} e
* @param {string} gra
* @return {number[]}
*/
LogSystem.prototype.retrieve = function(s, e, gra) {
    const res = [];
    for (let log of this.logs) {
        if (isBigger(log[1], s, gra) && isBigger(e, log[1], gra)) {
            res.push(log[0]); // !!! only the log id, not the pair
        }
    }
    return res;
};


function isBigger (time1, time2, gra) {
    // 2017:01:01:23:59:59
    // Year:Month:Day:Hour:Minute:Second
    const dict = {
        'Year': 4,
        'Month': 7,
        'Day': 10,
        'Hour': 13,
        'Minute': 16,
        'Second': 19
    }
    const count = dict[gra];
    time1 = time1.slice(0, count);
    time2 = time2.slice(0, count);
    return time1 >= time2;
}

/**
* Your LogSystem object will be instantiated and called as such:
* var obj = Object.create(LogSystem).createNew()
* obj.put(id,timestamp)
* var param_2 = obj.retrieve(s,e,gra)
*/

有更优解法

1127 4. Number of Connected Components in an Undirected Graph

/**
* @param {number} n
* @param {number[][]} edges
* @return {number}
*/
var countComponents = function(n, edges) {
    // create the ds class
    // for each of the nodes, set it points to itself
    // now add edge one by one. for each edges added, just union two nodes
    // after all that, create a set and loop all the nodes and find its parent and put to the set
    // check the size of the set
   
    // about the class
    // find, find the root of the current path, do path compressoin along the way
    // union, union two nodes, basically set one node's root to point to another one's root
    // constructor
    const dSet = new DisjointSet(n);
    for (let edge of edges) {
        dSet.union(...edge);
    }
    const set = new Set();
    for (let i = 0; i < n; i++) {
        set.add(dSet.find(i));
    }
    return set.size;
};

class DisjointSet {
    constructor (size) {
        this.parent = Array(size).fill().map((v, i) => i);
    }
    find (x) {
        if (this.parent[x] !== x) {
            return this.find(this.parent[x]);
        } else {
            return x;
        }
    }
    union (x, y) {
        this.parent[this.find(x)] = this.find(y);
    }
}

1127 5. Flip Game II

/**
* @param {string} s
* @return {boolean}
*/
var canWin = function(s) {
    if (s == null || s.length < 2) {
        return false;
    }
    for (let i = 1; i < s.length; i++) {
        // !!! need to flip it !!!
        if (s[i] === '+' && s[i - 1] === '+' && !canWin(s.slice(0, i - 1) + '--' + s.slice(i + 1, s.length))) {
            return true;
        }
    }
    return false;
};

1127 6. Design Tic-Tac-Toe

/**
* Initialize your data structure here.
* @param {number} n
*/
var TicTacToe = function(n) {
    this.rows = Array(n).fill(0);
    this.cols = Array(n).fill(0);
    this.diag1 = 0;
    this.diag2 = 0;
};

/**
* Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins.
* @param {number} row
* @param {number} col
* @param {number} player
* @return {number}
*/
TicTacToe.prototype.move = function(row, col, player) {
    // assume valid move
    if (player === 1) {
        this.rows[row]++;
        this.cols[col]++;
        if (row === col) {
            this.diag1++;
        }
        if (row + col === this.rows.length - 1) {
            this.diag2++;
        }
    } else {
        this.rows[row]--;
        this.cols[col]--;
        if (row === col) {
            this.diag1--;
        }
        if (row + col === this.rows.length - 1) {
            this.diag2--;
        }
    }
    const n = this.rows.length;
    const rowVal = this.rows[row];
    const colVal = this.cols[col];
    for (let val of [rowVal, colVal, this.diag1, this.diag2]) { // !! return the winner or 0, not 0 or 1
        if (val === n) {
            return 1;
        } else if (val === -n) {
            return 2;
        }
    }
    return 0;
   
};

/**
* Your TicTacToe object will be instantiated and called as such:
* var obj = Object.create(TicTacToe).createNew(n)
* var param_1 = obj.move(row,col,player)
*/

1127 7. Max Consecutive Ones II

/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function(nums) {
    // check
    // sliding window, left and right, left ex it, right inc it
    if (nums == null || nums.length === 0) {
        return 0;
    }
    let left = -1;
    let right = -1;
    let count = 0;
    let max = 0;
    for (right = 0; right < nums.length; right++) {
        if (nums[right] === 0) {
            count++;
        }
        while (count > 1) {
            left++;
            if (nums[left] === 0) {
                count--;
            }
        }
        max = Math.max(max, right - left);
    }
    return max;
};