记录

sicilianee 发表于 2017-12-10 15:58
1029 12. Longest Palindromic Substring

/**

感觉分配矩阵空间耗费了很多时间。实际上矩阵只有一半用到了，可能是这个原因。

1210 1. Clone Graph

/**
* Definition for undirected graph.
* function UndirectedGraphNode(label) {
*     this.label = label;
*     this.neighbors = [];   // Array of UndirectedGraphNode
* }
*/

/**
* @param {UndirectedGraphNode} graph
* @return {UndirectedGraphNode}
*/
var cloneGraph = function(graph) {
    if (graph == null) {
        return null;
    }
    const map = new Map();
    return clone(graph);
   
    function clone (node) {
        if (node == null) {return null}
        if (map.has(node)) {
            return map.get(node);
        } else {
            const cloned = new UndirectedGraphNode(node.label);
            map.set(node, cloned);
            const clonedNeighbors = [];
            for (let neighbor of node.neighbors) {
                clonedNeighbors.push(clone(neighbor));
            }
            cloned.neighbors = clonedNeighbors;
            return cloned;
        }
    }
   
};

1210 2. Rotate List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
    if (head == null) {return null}
    // first get len
    let len = 0;
    let node = head;
    while (node != null) {
        len++;
        node = node.next;
    }
    k = k % len;
    if (k === 0) { // !!! special, can we uniform this?
        return head;
    }
    let slow = head;
    let fast = head;
    for (let i = 0; i < k; i++) {
        fast = fast.next;
    }
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    const newHead = slow.next;
    slow.next = null;
    fast.next = head;
    return newHead;
};

sicilianee 发表于 2017-12-11 11:55
1210 2. Rotate List

/**

Using a dummy node could avoid 0 being excluded

1210 3.  Add and Search Word - Data structure design

/**
* Initialize your data structure here.
*/
var WordDictionary = function() {
    this.root = new TrieNode();
};

class TrieNode {
    constructor () {
        this.map = new Map();
        this.isEnd = false;
    }
}

/**
* Adds a word into the data structure.
* @param {string} word
* @return {void}
*/
WordDictionary.prototype.addWord = function(word) {
    let node = this.root;
    for (let c of word) {
        if (node.map.has(c)) {
            node = node.map.get(c);
        } else {
            const newNode = new TrieNode();
            node.map.set(c, newNode);
            node = node.map.get(c);
        }
    }
    node.isEnd = true;
};

/**
* Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function(word) {
    return doSearch(0, this.root);

    function doSearch (i, node) {
        if (i === word.length) {
            return node.isEnd;
        } else if (word[i] === '.') {
            for (let val of node.map.values()) {
//          for (let entry of node.map.entries()) {   // !!! this one caused memory limit exceeded error, why ???
                if (doSearch(i + 1, val)) {
                    return true;
                }
            }
            return false;
        } else {
            if (node.map.has(word[i])) {
                return doSearch(i + 1, node.map.get(word[i]));
            } else {
                return false;
            }
        }
    }
};

/**
* Your WordDictionary object will be instantiated and called as such:
* var obj = Object.create(WordDictionary).createNew()
* obj.addWord(word)
* var param_2 = obj.search(word)
*/

1210 4. Validate Binary Search Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
    const result = recurse(root)
    return result.valid;
   
    function recurse (node) {
        if (node == null) {
            return {max: -Infinity, min: Infinity, valid: true}
        }
        const left = recurse(node.left);
        const right = recurse(node.right);
        if (left.valid && right.valid && node.val > left.max && node.val < right.min) {
            return {
                max: node.right ? right.max : node.val,
                min: node.left ? left.min : node.val,
                valid: true
            }
        } else {
            return {
                max: 0,
                min: 0,
                valid: false
            }
        }
    }

   
   
};

sicilianee 发表于 2017-12-11 14:01
1210 4. Validate Binary Search Tree

/**

两种其他解法， 见discussion，常见的是讲范围pass 下去而不是像我们一样bubble上来

1210 5. Missing Ranges

/**
* @param {number[]} nums
* @param {number} lower
* @param {number} upper
* @return {string[]}
*/
var findMissingRanges = function(nums, lower, upper) {
    // if (lower === upper) {
    //     return [String(lower)]; // !!! its an array not a single str
    // }
    // if (nums == null || nums.length === 0) { // !!! if three are all the same, don't need to include anything
    //     return [`${lower}->${upper}`];
    // }
    nums = nums || [];
    const ans = [];
    nums.unshift(lower - 1);
    nums.push(upper + 1);
    for (let i = 0; i < nums.length - 1; i++) {
        const num = nums[i];
        const start = num + 1;
        const end = nums[i + 1] - 1;
        let str;
        if (start === end) {
            ans.push(`${start}`);
        } else if (start < end) {
            ans.push(`${start}->${end}`);
        }
    }
    return ans;
};

这个解法还蛮不错的。将所有的corner case都包含在内了。

1210 6. Continuous Subarray Sum

/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
// !!!!如果中间加起来是零呢?零也算是一个multiple of k
var checkSubarraySum = function(nums, k) {
    if (nums == null || nums.length < 2) {
        return false;
    }
    const map = new Map([[0, -1]]); // !!! why 0, -1 ? including the first one
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        sum += num;
        if (k !== 0) {
            sum = sum % k;
        }
        if (map.has(sum)) {
            if (i - map.get(sum) > 1) { // !!!! 1. > 1 this is important, think why !!!
                // !!! 2. need an if, not just return this, if false, we continue, not return !!!
                return true;
            }
        } else {
            map.set(sum, i);
        }
    }
    return false;
};

1211 1.  Find Smallest Letter Greater Than Target

/**
* @param {character[]} letters
* @param {character} target
* @return {character}
*/
var nextGreatestLetter = function(letters, target) {
    if (letters == null || letters.length === 0) {
        throw new Error('invalid input');
    }
    let low = 0;
    let high = letters.length - 1;
    while (low <= high) {
        const mid = low + Math.trunc((high - low) / 2);
        const val = letters[mid];
        if (target >= val) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    if (low >= letters.length) {
        return letters[0];
    } else {
        return letters[low];
    }
};