记录

1113 3. First Bad Version

/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
*     ...
* };
*/

/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        if (n < 1) {throw new Error()}
        let left = 1;
        let right = n;
        while (left <= right) {
            // use left
            const mid = left + Math.floor((right - left) / 2);
            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
};

1113 4. Rotate Array

/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
    if (nums == null || nums.length === 0 || k === 0) {return;} // !!! no return value
    const len = nums.length;
    k = k % len; // !!!!! when k bigger than len, not make sense
    // !!!! just keep a count, so we know when we should stop !!!!!
    let count = 0;
    for (let i = 0; count < nums.length; i++) {
        let tmp = nums[i];
        let j = i;
        while (getFromIndex(j, k, len) !== i) { // !!!! the getFromIndex has 3 parameters !!!! you just passed one
            nums[j] = nums[getFromIndex(j, k, len)];
            j = getFromIndex(j, k, len);
            count++;
        }
        nums[j] = tmp;
        count++;
    }
};

function getFromIndex (i, k, len) {
    if (i < k) {
        return len - (k - i);
    } else {
        return i - k;
    }
}

1113 5. Non-decreasing Array

/**
* @param {number[]} nums
* @return {boolean}
*/
var checkPossibility = function(nums) {
    if (nums == null || nums.length < 3) {
        return true;
    }
    let count = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) {
            if (count === 0) {return false;}
            if (i === 1 || nums[i - 2] < nums[i]) {
                nums[i - 1] = nums[i];
            } else {
                nums[i] = nums[i - 1];
            }
            count--; // !!! you didn't check !!!
        }
    }
    return true;
};

1113 6.  Encode and Decode TinyURL

/**
* Encodes a URL to a shortened URL.
*
* @param {string} longUrl
* @return {string}
*/
const list = [];
var encode = function(longUrl) {
    list.push(longUrl);
    return `http://tiny.com/${list.length -1}`;
};

/**
* Decodes a shortened URL to its original URL.
*
* @param {string} shortUrl
* @return {string}
*/
var decode = function(shortUrl) {
    const parts = shortUrl.split('/')
    const part = parts[parts.length - 1];
    return list[Number.parseInt(part)];
};

/**
* Your functions will be called as such:
* decode(encode(url));
*/

作弊答案。
需要重做。

1114 7. Implement Magic Dictionary

/**
* Initialize your data structure here.
*/
var MagicDictionary = function() {
    this.set = new Set();
};

/**
* Build a dictionary through a list of words
* @param {string[]} dict
* @return {void}
*/
MagicDictionary.prototype.buildDict = function(dict) {
    this.set = new Set(dict);
};

/**
* Returns if there is any word in the trie that equals to the given word after modifying exactly one character
* @param {string} word
* @return {boolean}
*/
MagicDictionary.prototype.search = function(word) {
    const chars = [...word];
    for (let i = 0; i < chars.length; i++) {
        const charI = chars[i];
        for (let j = 0; j < 26; j++) {
            const aChar = String.fromCharCode('a'.charCodeAt(0) + j);
            if (aChar !== charI) {
                chars[i] = aChar;
                const newWord = chars.join('');
                if (this.set.has(newWord)) {
                    return true;
                }
                chars[i] = charI;
            }
        }
    }
    return false;
};

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

再次作弊，直接暴力解==
需要看看正确的解法，还有leetcode的article

1114 8. Top K Frequent Words

/**
* @param {string[]} words
* @param {number} k
* @return {string[]}
*/
var topKFrequent = function(words, k) {
    if (words == null || words.length === 0) {
        return [];
    }
    const dict = {};
    for (let word of words) {
        dict[word] = dict[word] || 0;
        dict[word]++;
    }
    const entries = Object.entries(dict).sort((e1, e2) => {
        if (e1[1] === e2[1]) {
            if (e1[0] > e2[0]) {
                return 1;
            } else if (e1[0] === e2[0]) {
                return 0;
            } else {
                return -1;
            }
        } else {
            return e2[1] - e1[1]; // !!! need descending
        }
    });
    return entries.slice(0, k).map(entry => entry[0]);
};

暴力解。需要解follow up

1114 9. Split Linked List in Parts

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} root
* @param {number} k
* @return {ListNode[]}
*/
var splitListToParts = function(root, k) {
    // first get len
    let len = 0;
    let node = root;
    while (node != null) {
        node = node.next;
        len++;
    }
    let counts;
    if (len < k) {
        counts = Array(k).fill(1);
    } else {
        const aCount = Math.floor(len / k);
        counts = Array(k).fill(aCount);
        const remain = len - k * aCount;
        for (let i = 0; i < remain; i++) {
            counts[i]++;
        }
    }
    const res = [];
    let start = root;
    for (let i = 0; i < k; i++) {
        const aCount = counts[i];
        res.push(start);
        node = start;
        for (let j = 0; j < aCount - 1; j++) {
            if (node != null) {
                node = node.next;
            }
        }
        if (node != null) {
            start = node.next;
            node.next = null;
        } else {
            start = null; // shall not reach this
        }
    }
    return res;
   
};

1114 10. Search in Rotated Sorted Array

/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
    if (nums == null || nums.length === 0) {
        return -1;
    }
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        const midVal = nums[mid];
        if (midVal === target) {
            return mid;
        }
        if (midVal >= nums[left]) {
            if (target > midVal) {
                left = mid + 1;
            } else {
                if (target === nums[left]) {
                    return left
                } else {
                    left++;
                }
            }
        } else {
            if (target < midVal) {
                right = mid - 1;
            } else {
                if (target === nums[right]) {
                    return right;
                } else {
                    right--;
                }
            }
        }
    }
    return -1;
};

sicilianee 发表于 2017-11-14 16:03
1114 10. Search in Rotated Sorted Array

/**

正确答案：

/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
    // 正确的做法是找到有序的一般，判断在不在这一半里，重点是我们知道有序一段的首尾
    // 各种等号必须要注意。
    if (nums == null || nums.length === 0) {
        return -1;
    }
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) { // !!!! shold f***ing include =
        const mid = left + Math.floor((right - left) / 2);
        const midVal = nums[mid];
        if (midVal === target) {return mid}
        if (midVal >= nums[left]) { // !!!! include equal because they could be the same element
            if (nums[left] <= target && target < midVal) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (midVal < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
};

Previous dates are wrong

1114 1. Populating Next Right Pointers in Each Node II

/**
* Definition for binary tree with next pointer.
* function TreeLinkNode(val) {
*     this.val = val;
*     this.left = this.right = this.next = null;
* }
*/

/**
* @param {TreeLinkNode} root
* @return {void} Do not return anything, modify tree in-place instead.
*/
var connect = function(root) {
    if (root == null) {return}
    const dummy = new TreeLinkNode(0);
    let node = dummy;
    while (root != null) {
        if (root.left != null) {
            node.next = root.left;
            node = node.next;
        }
        if (root.right != null) { // !!! root.next, not node.next, still the same issue, mix variables
            node.next = root.right;
            node = node.next;
        }
        if (root.next != null) {
            root = root.next;
        } else {
            root = dummy.next;
            dummy.next = null;
            node = dummy;
        }
    }
};