记录

1212 1. Network Delay Time

/**
* @param {number[][]} times
* @param {number} N
* @param {number} K
* @return {number}
*/
var networkDelayTime = function(times, N, K) {
    // lets first do the basic solution
    // from point k, adding 1 - N one by one
    // we create an adj list map for all edges based on times
    // we build a map for each of the nodes tracking the min dist
    // we start from k, loop all connected and update, find a min, add to the set
    // now we start from the newly added one, loop all connected and update the map, find a min and add to the set
    // until set has all elements, or we cannot go any further
    // in the end we return the max one in the map
    if (N === 1) {return 0;}
    if (times == null || times.length === 0) {
        return -1;
    }
    const map = new Map();
    const distMap = new Map();
    for (let i = 1; i <= N; i++) {
        map.set(i, []);
        distMap.set(i, Infinity);
    }
    distMap.set(K, 0) // !!!!! 1. itself should have 0 to start with 2. must be after the prev loop otherwise it is overriden
    for (let [u, v, w] of times) {
        map.get(u).push([v, w]); // !!!!! push not add for list
    }
    const set = new Set();
    let curr = K;
    while (set.size < N) {
        const edges = map.get(curr);
        // update based on curr
        for (let [node, dist] of edges) {
            const oldDist = distMap.get(node);
            const newDist = Math.min(oldDist, distMap.get(curr) + dist); // !!!! get curr, not node, you go through curr
            distMap.set(node, newDist);
        }
        // put curr into set
        set.add(curr);
        // find the next one to add to the set
        let min = Infinity;
        for (let i = 1; i <= N; i++) {
            if (!set.has(i) && distMap.get(i) <= min) { // !!!! not in the set yet
                min = distMap.get(i);
                curr = i;
            }
        }
    }
    let max = -Infinity;
    for (let i = 1; i <= N; i++) {
        max = Math.max(max, distMap.get(i));
    }
    return max === Infinity ? -1 : max;
};

1212 2. Closest Leaf in a Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var findClosestLeaf = function(root, k) {
    // !!!!!! IMPORTANT: not a binary SEARCH tree, read the instructions carefully !!!!!
    // first, mark the closest leaf for each node
    if (root == null) {
        return 0;
    }
    const map = new Map();
    dfs(root);
    const list = [];
    let minPair = [Infinity, null];
    buildPath(root);
    return minPair[1].val;
   
    function buildPath (node) {
        if (node == null) {return}
        list.unshift(node);
        if (node.val === k) {
            for (let i = 0; i < list.length; i++) {
                const aNode = list[i];
                const dist = map.get(aNode)[0] + i;
                if (dist < minPair[0]) {
                    minPair = [dist, map.get(aNode)[1]];
                }
            }
            return true;
        } else {
            if (buildPath(node.left)) {
                return true;
            }
            if (buildPath(node.right)) {
                return true;
            }
        }
        list.shift();
        return false;
    }
   
    function dfs (node) {
        let self = null;
        if (node.left == null && node.right == null) {
            self = [0, node];
        } else {
            let left = [Infinity, node];
            let right = [Infinity, node];
            if (node.left) {
                left = dfs(node.left);
            }
            if (node.right) {
                right = dfs(node.right);
            }
            if (left[0] < right[0]) { // !!!! opposite, < not >
                self =  [left[0] + 1, left[1]];
            } else {
                self = [right[0] + 1, right[1]];
            }
        }
        map.set(node, self);
        return self;
    }
};


做的很恶心啊🤢

1214 1. Largest Number

/**
* @param {number[]} nums
* @return {string}
*/
var largestNumber = function(nums) {
    if (nums == null || nums.length === 0) {
        return '';
    }
    nums = nums.map(num => String(num));
    nums.sort((str1, str2) => {
        str1 = str1 + str2;
        str2 = str2 + str1;
        if (str1 > str2) {
            return -1;
        } else if (str1 < str2) {
            return 1;
        } else {
            return 0;
        }
    });
    const str = nums.join('');
    if (str.split('').every(c => c === '0')) {
        return '0'
    } else {
        return str;
    }
};

怎么证明？怎么理解数学证明的物理意义？

1214 2. 3Sum

/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
    if (nums == null || nums.length < 3) {
        return [];
    }
    const ans = [];
    nums.sort((a, b) => a - b) // !!!! f***ing important !!!!
    for (let i = 0; i <= nums.length - 3; i++) {
        if (i != 0 && nums[i] === nums[i - 1]) { // !!! 1. for dup
            continue;
        }
        const sum = 0 - nums[i];
        let low = i + 1;
        let high = nums.length - 1;
        while (low < high) {
            const aSum = nums[low] + nums[high];
            const lowNum = nums[low];
            const highNum = nums[high];
            if (aSum === sum) {
                ans.push([nums[i], lowNum, highNum]);
                while (nums[low] === lowNum) { // !!! 2. for dup
                    low++;
                }
                while (nums[high] == highNum) { // !!! 3. for dup
                    high--;
                }
            } else if (aSum < sum) {
                low++;
            } else {
                high--;
            }
        }
    }
    return ans;
};

1214 3. Validate IP Address

/**
* @param {string} IP
* @return {string}
*/
var validIPAddress = function(IP) {
    if (IP == null || IP.length === 0) {
        return 'Neither';
    }
    if (isIPV4(IP)) {
        return 'IPv4';
    }
    if (isIPV6(IP)) {
        return 'IPv6';
    }
    return 'Neither';
};

function isIPV6 (ip) {
    if (ip.includes('.')) {return false;}
    const strs = ip.split(':');
    if (strs.length !== 8) {
        return false;
    }
    for (let str of strs) {
        str = str.toLowerCase(); // !!!! case insensitive
        if (str.length > 4 || str === '') {return false;}
        for (let c of str) {
            if (!((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f'))) {
                return false;
            }
        }
        const num = Number.parseInt(str, 16); // !!!! Number.parseInt won't test for incorrect chars
        if (! (num >= 0 && num <= 0xffff)) {
            return false;
        }
    }
    return true;
}

function isIPV4 (ip) {
    if (ip.includes(':')) {return false}
    const strs = ip.split('.');
    if (strs.length !== 4) {
        return false;
    }
    for (let str of strs) {
        if (str === '') {
            return false;
        }
        if (str.length > 1 && str[0] === '0') {
            return false;
        }
        for (let c of str) { // !!!! all chars need to be 0 - 9
            if (! (c >= '0' && c <= '9')) {
                return false;
            }
        }
        const num = Number.parseInt(str, 10);
        if (!(num >= 0 && num < 256)) {
            return false;
        }
    }
    return true;
}

1214 4. Compare Version Numbers

/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
var compareVersion = function(version1, version2) {
    version1 = version1 || '';
    version2 = version2 || '';
    const list1 = version1.split('.');
    const list2 = version2.split('.');
    const len = Math.max(list1.length, list2.length);
    for (let i = 0; i < len; i++) {
        const v1 = i < list1.length ? Number.parseInt(list1[i], 10) : 0;
        const v2 = i < list2.length ? Number.parseInt(list2[i], 10) : 0;
        const diff = v1 - v2;
        // !!! 1, -1, 0, cannot be others
        if (diff !== 0) {
            return diff > 0 ? 1 : -1;
        }
    }
    return 0;
};

1214 5. Decode Ways

/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
    if (s == null || s.length === 0) {
        return 0;
    }
    const len = s.length;
    const dp = Array(len).fill(0);
    for (let i = 0; i < s.length; i++) {
        const prev = i === 0 ? -1 : Number.parseInt(s[i - 1], 10);
        const curr = Number.parseInt(s[i], 10);
        const backOne = i > 0 ? dp[i - 1] : 1;
        const backTwo = i > 1 ? dp[i - 2] : 1;
        dp[i] = curr === 0 ? 0 : backOne;
        if (prev === 1 || prev === 2 && curr >= 0 && curr <= 6) {
            dp[i] = dp[i] + backTwo;
        }
    }
    return dp[len - 1];
};

1214 6.  Word Ladder


/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
    // !!! 不能够用dfs，为啥， 实际是求最短路径，unweighted graph, 最短路径直接bfs
    if (wordList == null || wordList.length === 0) {
        return 0;
    }
    const all = 'abcdefghijklmnopqrstuvwxyz'.split('');
    const dictSet = new Set(wordList);
    const visited = new Set();
    let len = 0;
    const q = [beginWord];
    while (q.length > 0) {
        const qLen = q.length;
        len++;
        for (let i = 0; i < qLen; i++) {
            const node = q.shift();
            // if (node === endWord) {
            //     return len;
            // }
            visited.add(node);
            const children = getChildren(node);
            for (let child of children) {
                if (child === endWord) {
                    return len + 1;
                }
            }
            q.push(...children);
        }
    }
    return 0;

    function getChildren (word) {
        const chars = word.split('');
        const ans = [];
        for (let i = 0; i < chars.length; i++) {
            const c = chars[i];
            for (let j = 0; j < 26; j++) {
                const ac = all[j];
                if (ac !== c) {
                    chars[i] = ac;
                    const newWord = chars.join('');
                    if (dictSet.has(newWord) && !visited.has(newWord)) {
                        visited.add(newWord); // !!!!! that's the reason for tle!!!!!
                        // !!!! if we don't add the child to set immediately, ans is still correct but will get tle,
                        // this is because we will have duplicates on the same level
                        ans.push(newWord);
                    }
                    chars[i] = c;
                }
            }
        }
        return ans;
    }
};

1217 1. Number Of Corner Rectangles

/**
* @param {number[][]} grid
* @return {number}
*/
var countCornerRectangles = function(grid) {
    if (grid == null || grid.length === 0) {
        return 0;
    }
    const map = new Map();
    let sum = 0;
    for (let row of grid) {
        for (let i = 0; i < row.length; i++) {
            if (row[i] === 1) {
                for (let j = i + 1; j < row.length; j++) {
                    if (row[j] === 1) {
                        const val = map.get(`${i}:${j}`) || 0;
                        sum += val;
                        map.set(`${i}:${j}`, val + 1);
                    }
                }
            }
        }
    }
    return sum;
};

1217 2. 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;
};

实际上是判断哈密顿路径，属于拓扑排序里面的。