记录

1114 9. Number of Longest Increasing Subsequence

/**
* @param {number[]} nums
* @return {number}
*/
var findNumberOfLIS = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    let count = 0;
    let max = 0;
    const dp = Array(nums.length).fill().map(() => ({len: 1, count: 1}));
    for (let i = nums.length - 1; i >= 0; i--) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] < nums[j]) {
                const newLen = dp[j].len + 1;
                if (newLen > dp[i].len) {
                    dp[i].len = newLen;
                    dp[i].count = dp[j].count;
                } else if (newLen === dp[i].len) { // !!!! already changed to dp[i].len, not max anymore. If you change your
                    // code in place, it is hard to correctly spot all places
                    dp[i].count += dp[j].count;
                }
            }
        }
        if (dp[i].len > max) {
            max = dp[i].len;
            count = dp[i].count;
        } else if (dp[i].len === max) {
            count += dp[i].count;
        }
    }
    return count;
};

不知道别人是怎么做的，要查一下。

1114 10.  Reverse Linked List II

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
var reverseBetween = function(head, m, n) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let node = dummy;
    for (let i = 0; i < m - 1; i++) {
        node = node.next;
    }
    const start = node;
    const size = n - m;
    let prev = start.next;
    for (let i = 0; i < size; i++) {
        const curr = prev.next;
        prev.next = curr.next;
        const startNext = start.next;
        start.next = curr;
        curr.next = startNext;
    }
    return dummy.next; //  ！！！注意用dummy是有原因的，可能从第一个开始反转
};

不错！

1116 1. Find K Pairs with Smallest Sums

class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((pair1, pair2) -> {
            // !!!!! note queue: first in, first out
            // each time you need to peek the largest element in the queue, thus you need to have a decreasing queue because
            // you'll see the head of the queue and the head is the largest.
            return pair2[0] + pair2[1] - pair1[0] - pair1[1];
        });
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            for (int j = 0; j < Math.min(k, nums2.length); j++) {
                int sum = nums1[i] + nums2[j];
                if (pq.size() < k) {
                    pq.add(new int[]{nums1[i], nums2[j]});
                } else {
                    int[] top = pq.peek();
                    if (top[0] + top[1] > sum) {
                        pq.remove();
                        pq.add(new int[]{nums1[i], nums2[j]});
                    }
                }
            }
        }
        return new ArrayList<int[]>(pq);
    }
}

1116 2.  Linked List Cycle II

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
    // first, get the length of the list?
    if (head == null) {
        return null;
    }
    let slow = head;
    let fast = head;
    let hasCycle = false;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast === slow) {
            hasCycle = true;
            break;
        }
    }
    if (!hasCycle) {
        return null;
    }
    // has cycle
    let another = head;
    while (another != slow) {
        another = another.next;
        slow = slow.next;
    }
    return slow;
};

这题理解了不难，但是思路还是要回顾一下：
1. 如果有环，快慢指针，一定会相遇。
  why？ at first, diff === 0, each step, diff++, so diff will reach the number that equals number of nodes in the cycle, and they will meet.
2. 如果有环，快慢指针一起走，那么会在同一地点相遇，快指针走两圈，慢指针走一圈。那么可以把多出来的那部分映射到环里面，两个以同样速度走，最后会在交汇处相遇。

1116 3. Summary Ranges

/**
* @param {number[]} nums
* @return {string[]}
*/
var summaryRanges = function(nums) {
    if (nums == null || nums.length === 0) {
        return [];
    }
    const res = [];
    let start = nums[0];
    for (let i = 1; i <= nums.length; i++) {
        if (i === nums.length || nums[i] !== nums[i - 1] + 1) {
            if (nums[i - 1] !== start) {
                res.push(`${start}->${nums[i - 1]}`);
            } else {
                res.push(`${start}`);
            }
            start = i === nums.length ? 0 : nums[i];
        }
    }
    return res;
};

1116 4. Out of Boundary Paths

/**
* @param {number} m
* @param {number} n
* @param {number} N
* @param {number} i
* @param {number} j
* @return {number}
*/
var findPaths = function(m, n, N, i, j) {
    const dp = Array(m).fill().map(() => Array(n).fill().map(() => Array(N + 1).fill(0)));
    let moves = [[-1, 0], [1, 0], [0, 1], [0, -1]];
    const M = Math.pow(10, 9) + 7;
    for (let k = 1; k < N + 1; k++) {
        for (let ii = 0; ii < m; ii++) {
            for (let jj = 0; jj < n; jj++) {
                for (let move of moves) {
                    const row = ii + move[0];
                    const col = jj + move[1];
                    let val;
                    if (row >= 0 && row < m && col >= 0 && col < n) {
                        val = dp[row][col][k - 1];
                    } else {
                        val = 1;
                    }
                    dp[ii][jj][k] = (dp[ii][jj][k] + val) % M; // !!!! do it in each run, otherwise still overflow !!!!
                    
                }
            }
        }
    }
    return dp[i][j][N]; // !!!! the requirement!!! need to mod
   
    // !!!! need to discuss about overflow
};

1116 5. Word Break

/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
    if (s == null || s.length === 0 || wordDict == null || wordDict.length === 0) {
        return false;
    }
    const set = new Set(wordDict);
    const map = new Map(); // 直接跑tle，所以加memorization
    return canBreak(s);
   
    function canBreak (str) {
        if (map.has(str)) {
            return map.get(str);
        }
        if (set.has(str)) {
            map.set(str, true);
            return true;
        } else {
            for (let i = 1; i < str.length; i++) {
                const firstPart = str.slice(0, i); // !!! this is exclusive. We use the end point exclusive, so start from 1
                const secondPart = str.slice(i);
                if (set.has(firstPart) && canBreak(secondPart)) {
                    map.set(str, true);
                    return true;
                }
            }
        }
        map.set(str, false);
        return false;
    }
};

1116 6. Integer Replacement

/**
* @param {number} n
* @return {number}
*/
    var integerReplacement = function(n) {
//         // !!!! why this does't work:
//         // when you are at i, you assume dp[i] is already computed and you compute others based on i.
//         // but dp i could be from dp i + 1, so the current dp i you have at hand might not be the biggest one, so
//         // you cannot compute other dp values based on the current value
        
//         const dp = Array(n + 2).fill(Infinity);// we'll consider n + 1 // !!!! need to init it, cause you will compare them !!!!
//         dp[1] = 0;
//         for (let i = 1; i < n + 2; i++) {
//             dp[i * 2] = Math.min(dp[i] + 1, dp[i * 2]);
//             if (i % 2 === 0) { // !!! when it is odd, you cannot + 1 or -1, can only / 2
//                 dp[i + 1] = Math.min(dp[i] + 1, dp[i + 1]);
//                 dp[i - 1] = Math.min(dp[i] + 1, dp[i - 1]);   
//             }
//         }
//         return dp[n];
        
        let count = 0;
        while (n !== 1) {
            if (n % 2 === 0) {
                n = n / 2;
                count++;
            } else {
                // 没有环，因为奇数和偶数处理不一样的
                const up = integerReplacement(n + 1);
                const down = integerReplacement(n - 1);
                return count + Math.min(up, down) + 1; // !!! one more since you need one more to get there
            }
        }
        return count;
    };

1116 7. Lowest Common Ancestor of a Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
    if (root == null) {
        return null;
    }
    if (root == p || root == q) {
        return root;
    }
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    if (left != null) {
        return left; // !!!! left, not node.left
    }
    if (right != null) {
        return right // !!! same here
    }
    return null;
};

1118 1.  Gas Station

/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function(gas, cost) {
    // check
    const len = gas.length;
    if (len === 0) {
        return 0;
    }
    const arr = Array(len);
    for (let i = 0; i < len; i++) {
        arr[i] = gas[i] - cost[i];
    }
    const sum = arr.reduce((a, b) => a + b);
    if (sum < 0) {return -1}
    let min = arr[0];
    let minIndex = 0;
    for (let i = 0; i < len; i++) {
        arr[i] = i === 0 ? arr[i] : arr[i] + arr[i - 1];
        if (arr[i] < min) {
            min = arr[i];
            minIndex = i;
        }
    }
    return min >= 0 ? 0 : minIndex + 1;
};


网上的解法没看懂。要再看。

不过我的这个解法还是比较新的：
数形结合，画平面直角坐标系，画从原点开始的油的走势曲线。
若最后大于零，则可以走完，因为我们可以从最低点之后开始走，相当于将图形向上平移。
最后点大于零的情况下：找最低点，若最低点大于零，则可以从零走。若最低点小于零，则去最低点后一个点。