记录

1101 4. Convert Sorted List to Binary Search Tree

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function(head) {
    if (head == null) {return null}
    let len = 0;
    let node = head;
    while (node != null) {
        len++;
        node = node.next;
    }
    return inOrderBuild(1, len);
   
   
    function inOrderBuild (left, right) {
        if (left > right) {return null;}
        const mid = left + Math.floor((right - left) / 2);
        const leftNode = inOrderBuild(left, mid - 1);
        const selfNode = new TreeNode(head.val);
        head = head.next;
        const rightNode = inOrderBuild(mid + 1, right);
        selfNode.left = leftNode;
        selfNode.right = rightNode;
        return selfNode;
    }
   
};

1101 5. Path Sum II

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number[][]}
*/
var pathSum = function(root, sum) {
    if (root == null) {return [];}
    const res = [];
    const list = [];
    recurse(root, 0);
    return res;
   
    function recurse (node, memo) {
        // assume node is not null
        memo += node.val;
        list.push(node.val);
        if (node.left == null && node.right == null) {
            if (memo === sum) {
                res.push([...list]);
            }
        } else {
            if (node.left != null) {
                recurse(node.left, memo);
            }
            if (node.right != null) {
                recurse(node.right, memo);
            }
        }
        list.pop();
    }
};

feel weird. Find similar problems and practice more.

1101 6.  House Robber II

/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    const withLast = nums[nums.length - 1] + simpleRob(1, nums.length - 3);
    const withoutLast = simpleRob(0, nums.length - 2);
    return Math.max(withLast, withoutLast);
   
    function simpleRob (start, end) {
        console.log(start, end);
        if (start > end) {return 0;}  // !!!! wrong condition is > not <, you did too many binary search that you didn't even think
        if (start === end) {return nums[start]}
        const dp = Array(end - start + 1);
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1])
        for (let i = 2; start + i <= end; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[start + i], dp[i - 1]);
        }
        return dp[end - start];
    }
};

sicilianee 发表于 2017-11-2 12:42
1101 6.  House Robber II

/**

http://www.cnblogs.com/grandyang/p/4518674.html
alternative idea.

1101 7. Triangle

/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
    if (triangle == null || triangle.length === 0) {
        return 0;
    }
    const len = triangle.length;
    const dp = [...triangle[len - 1]];
    for (let j = len - 2; j >= 0; j--) { // !!! start from the second last row, not the last row !!!
        for (let i = 0; i <= j; i++) {
            dp[i] = Math.min(dp[i], dp[i + 1]) + triangle[j][i];
        }
    }
    return dp[0];
};

1101 8. Bitwise AND of Numbers Range

/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var rangeBitwiseAnd = function(m, n) {
    // !!!! need to find out the right pattern
    let mask = 0xffffffff; // !!!! how to represent hex numbers
    while ((m & mask) !== (n & mask)) {
        mask = mask << 1;
    }
    return mask & m;
   
};

1101 9. Palindrome Partitioning

/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
    if (s == null || s.length === 0) {
        return [];
    }
    let res = [];
    if (isPalindrome(s)) {
        res.push([s]);
    }
    for (let i = 1; i < s.length; i++) {
        let first = s.slice(0, i); // !!!!! including self will cause infinite loop
        let second = s.slice(i);
        if (isPalindrome(first)) {
            const secondRes = partition(second);
            if (secondRes.length > 0) {
                secondRes.forEach(arr => arr.unshift(first)); // !!!!! unshift into each of them
                res.push(...secondRes); // !!!! not the entire, but copy
            }
        }
    }
    return res;
};

function isPalindrome (s) {
    if (s == null || s.length === 0) {
        return true;
    }
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

没优化过。可以加记忆或者dp。研究一下dp

1101 10. Pacific Atlantic Water Flow
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var pacificAtlantic = function(matrix) {
    if (matrix == null || matrix.length === 0) {
        return [];
    }
    const res = [];
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    const pacific = Array(rowLen).fill().map(() => Array(colLen));
    const atlantic = Array(rowLen).fill().map(() => Array(colLen));
    const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (let i = 0; i < rowLen; i++) {
        dfs(pacific, i, 0);
        dfs(atlantic, i, colLen - 1);
    }
    for (let j = 0; j < colLen; j++) {
        dfs(pacific, 0, j);
        dfs(atlantic, rowLen - 1, j);
    }
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            if (pacific[j] && atlantic[i][j]) {
                res.push([i, j]);
            }
        }
    }
    return res;

    function dfs (visited, i, j) {
        const val = matrix[i][j];
        visited[i][j] = true;
        for (let move of moves) {
            const x = i + move[0];
            const y = j + move[1];
            // !!!! has to test if it has already been visited or you will get circles !!!
            if (x >= 0 && x < rowLen && y >= 0 && y < colLen && matrix[x][y] >= val && !visited[x][y]) {
                dfs(visited, x, y);
            }
        }
    }
};
[i][i][/i]

1102 1.  Find All Anagrams in a String

/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function(s, p) {
    if (s == null || p == null || s.length === 0 || p.length === 0) {
        return [];
    }
    const len = p.length;
    const dict = {};
    for (let c of p) { // !!! it is p, not s
        dict[c] = dict[c] || 0;
        dict[c]++;
    }
    let left = 0;
    let right = 0;
    let count = 0;
    const res = [];
    while (left <= right && right < s.length) {
        dict[s[right]] = dict[s[right]] || 0;
        dict[s[right]]--;
        count++;
        while (dict[s[right]] < 0) {
            dict[s[left]]++; // !!!! not directly right, but s[right]
            left++; // !!!! still !!! it is the issue of the loop variable !!!!
            count--;
        }
        if (count === len) {
            res.push(left);
        }
        right++;
    }
    return res;
};

1102 2. Perfect Number

/**
* @param {number} num
* @return {boolean}
*/
var checkPerfectNumber = function(num) {
    if (num === 1) {
        return false;
    }
    // !!!! read the instruction, except itself !!!
    const divs = [1];
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) {
            divs.push(i, num / i);
        }
    }
    return divs.reduce((a, b) => a + b) === num;
   
};