记录

0912 2. Delete Operation for Two Strings

/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
    const len1 = word1.length;
    const len2 = word2.length;
    if (len1 === 0) {return len2;}
    if (len2 === 0) {return len1;}
    const dp = Array(len1).fill().map(() => Array(len2));
    for (let i = 0; i < len1; i++) {
        for (let j = 0; j < len2; j++) {
            let dpij1 = j === 0 ? 0 : dp[i][j - 1];
            let dpi1j = i === 0 ? 0 : dp[i - 1][j];
            let dpi1j1 = (i === 0 || j === 0) ? 0 : dp[i - 1][j - 1];
            if (word1[i] === word2[j]) {
                dp[i][j] = dpi1j1 + 1;
            } else {
                dp[i][j] = Math.max(dpi1j, dpij1);
            }
        }
    }
    return len1 + len2 - dp[len1 - 1][len2 - 1] * 2;
};

0913 1. Minimum Number of Arrows to Burst Balloons

/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function(points) {
    if (points == null || points.length === 0) {return 0;}
    points.sort((a, b) => {
        return a[0] === b[0]
            ? a[1] - b[1]
            : a[0] - b[0];
    });
    let end = points[0][1];
    let count = 1;
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] <= end) {
            end = Math.min(end, points[i][1]);
        } else {
            count++;
            end = points[i][1];
        }
    }
    return count;
};

0913 2. Kth Smallest Element in a BST


/**
* 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 kthSmallest = function(root, k) {
    let result;
    const inOrder = (node) => {
        if (node == null) {return;}
        inOrder(node.left);
        k--;
        if (k === 0) {
            result = node.val;
            return;
        }
        inOrder(node.right);
    }
    inOrder(root);
    return result;
};

0914 1. Diameter of Binary Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
    const getLen = node => {
        if (node == null) {
            return -1;
        }
        const left = getLen(node.left) + 1;
        const right = getLen(node.right) + 1;
        return Math.max(left, right);
    }
    if (root == null) {return 0;}
    const self = getLen(root.left) + 1 + getLen(root.right) + 1;
    const left = diameterOfBinaryTree(root.left);
    const right = diameterOfBinaryTree(root.right);
    return Math.max(self, left, right);

};
It IS hard.

0914 2. Student Attendance Record I

/**
* @param {string} s
* @return {boolean}
*/
var checkRecord = function(s) {
    let countL = 0;
    let countA = 0;
    const chars = s.split('');
    for (let c of chars) {
        if (c === 'L') {
            countL++;
            if (countL > 2) {
                return false;
            }
        } else {
            countL = 0;
            if (c === 'A') {
                countA++;
                if (countA > 1) {
                    return false;
                }
            }
        }
    }
    return true;
};

0915 1. Odd Even Linked List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var oddEvenList = function(head) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    let mark = dummy;
    while (prev != null && prev.next != null) { // !!! need to check two
        const target = prev.next;
        prev.next = target.next;
        prev = prev.next;
        target.next = mark.next;
        mark.next = target;
        mark = mark.next;
    }
    return dummy.next;
};

0915 2. Reverse String II

/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var reverseStr = function(s, k) {
    const chars = s.split('');
    for (let start = 0; start < chars.length; start += 2 * k) {
        let end = Math.min(start + k - 1, chars.length - 1);
        let [left, right] = [start, end];
        while (left < right) {
            ;[chars[left], chars[right]] = [chars[right], chars[left]];
            left++;
            right--;
        }
    }
    return chars.join('');
};

0916 1. House Robber III

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function(root) {
    const map = new Map();
    const pair = recurse(root);
    return Math.max(...pair);
   
    function recurse (node) {
        if (node == null) {
            return [0, 0];
        }
        if (map.has(node)) {
            return map.get(node);
        }
        const left = recurse(node.left);
        const right = recurse(node.right);
        const withSelf = node.val + left[1] + right[1];
        const withoutSelf = left[0] + right[0];
        const result = [Math.max(withSelf, withoutSelf), withoutSelf]; // !!!!! The first one is if we include the possibility of having myself, what's the maximum, but in practice we may not actually use myself. The second one is exclude the possibility of having myself.
        map.set(node, result);
        return result;
    }
};

0916 2. Find the Duplicate Number

/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
    // note the binary search has nothing to do with the nums, the range is according to 1 - n.
    let start = 1;
    let end = nums.length - 1;
    while (start < end) {
        let mid = Math.floor((start + end) / 2);
        let selfCount = 0;
        let lessCount = 0;
        nums.forEach(num => {
            if (mid === num) {
                selfCount++;
            }
            if (num < mid) {
                lessCount++;
            }
        });
        if (selfCount > 1) {
            return mid;
        }
        if (lessCount < mid) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return start;
};

NOTE: there is an O(n) solution! Figure that out.

0917 1. Target Sum

/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
var findTargetSumWays = function(nums, S) {
    const map = new Map();
    return recurse(0, 0);
   
    function recurse (i, sum) {
        if (i === nums.length) {
            if (sum === S) {
                return 1;
            } else {
                return 0;
            }
        }
        const key = `${i}:${sum}`;
        if (map.has(key)) {
            return map.get(key);
        }
        let num = nums;
        const positive = recurse(i + 1, sum + num);
        const negative = recurse(i + 1, sum - num);
        map.set(key, positive + negative);
        return positive + negative;
    }
   
};

TODO: USE DP