记录

0816 Wednesday

2. Two Sum II - Input array is sorted

/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
    const dict = {};
    for (let i = 0; i < numbers.length; i++) {
        const number = numbers;
        const complement = target - number;
        if (dict[complement] != undefined) {
            return [dict[complement], i + 1];
        } else {
            dict[number] = i + 1;
        }
    }
    throw new Error('Not found');
};

TODO:
1. Two pointers could do without extra space

8017 Thursday

1. Best Time to Buy and Sell Stock II

/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
    let memo = 0;
    for (let i = 1; i < prices.length; i++) {
        const curr = prices[i];
        const prev = prices[i - 1];
        if (curr > prev) {
            memo += curr - prev;
        }
    }
    return memo;
};

0817

2. Next Greater Element II

/**
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElements = function(nums) {
    const doubleNums = [...nums, ...nums];
    const result = [];
    const stack = [];
    let i = 0;
    while (i < doubleNums.length) {
        if (stack.length === 0) {
            stack.push(i);
            i++;
            continue;
        }
        const top = doubleNums[stack[stack.length - 1]];
        const value = doubleNums;
        if (value > top) {
            const index = stack.pop();
            result[index] = value;
        } else {
            stack.push(i);
            i++;
        }
    }
    while (stack.length > 0) {
        const index = stack.pop();
        result[index] = -1;
    }
    return result.slice(0, doubleNums.length / 2);
};
TODOS:
Combine the continue into the else branch. Otherwise it is likely that you miss the 'continue' keyword.

0818 Friday

1. Minimum Index Sum of Two Lists

/**
* @param {string[]} list1
* @param {string[]} list2
* @return {string[]}
*/
var findRestaurant = function(list1, list2) {
    // first put list1 into dict
    // then, loop list 2 and collect min while you loop
    const dict = {};
    list1.forEach((value, index) => dict[value] = index);
    let min = Number.MAX_VALUE;
    let results = [];
    list2.forEach((value, index) => {
        if (dict[value] != undefined) {
            const sum = index + dict[value];
            if (sum === min) {
                results.push(value);
            } else if (sum < min) {
                results = [value];
                min = sum; // !!! you still need to update it!!!
            }
        }
    });
    return results;
};


要注意更新最小值

0818 Friday
2. Sum of Left Leaves

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumOfLeftLeaves = function(root) {
    if (root == null) {
        return 0;
    }
    return getSum(root, false);
   
   
    function getSum (node, left) {
        // stop:
        if (node == null) {
            throw new Error('Illegal Argument');
        }
        if (node.left == null && node.right == null) {
            return left ? node.val : 0;
        }
        const leftSum = node.left != null ? getSum(node.left, true) : 0;
        const rightSum = node.right != null ? getSum(node.right, false) : 0;
        return leftSum + rightSum;
    }
};

For last Tuesday:
1. Add One Row to Tree


/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} v
* @param {number} d
* @return {TreeNode}
*/
var addOneRow = function(root, v, d) {
    if (d === 1) {
        const newRoot = new TreeNode(v);
        newRoot.left = root;
        return newRoot;
    }
    const target = d - 1;
    doModify(root, 1);
    return root;
   
    function doModify (node, depth) {
        if (node == null) {return;}
        if (depth === target) {
            const left = node.left;
            const right = node.right;
            node.left = new TreeNode(v);
            node.left.left = left;
            node.right = new TreeNode(v);
            node.right.right = right;
        } else {
            doModify(node.left, depth + 1);
            doModify(node.right, depth + 1);
        }
    }
};
1. You could actually use the original signature to do recursion, but this one is easier for me to understand.

0819 Saturday

1. Linked List Random Node

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
* @param {ListNode} head
*/
var Solution = function(head) {
    this.head = head;
};

/**
* Returns a random node's value.
* @return {number}
*/
Solution.prototype.getRandom = function() {
    let poolNode = this.head;
    let node = poolNode;
    let index = 0;
    while (node !== null) {
        const randomIndex = Math.floor(Math.random() * (index + 1));        
        if (randomIndex === 0) {
            poolNode = node;  
        }
        // update
        node = node.next;
        index++;
    }
    return poolNode.val;
};

/**
* Your Solution object will be instantiated and called as such:
* var obj = Object.create(Solution).createNew(head)
* var param_1 = obj.getRandom()
*/

0819

2. Binary Tree Tilt

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findTilt = function(root) {
    buildSum(root);
    let tiltSum = 0;
    getTilt(root);
    return tiltSum;
   
    function getTilt (node) {
        if (node == null) {
            return;
        }
        const left = node.left != null ? node.left.sum : 0;
        const right = node.right != null ? node.right.sum : 0;
        tiltSum += Math.abs(left - right);
        getTilt(node.left);
        getTilt(node.right);
    }
   
    function buildSum (node) {
        if (node == null) {
            return 0;
        }
        if (node.sum != undefined) {
            return node.sum;
        }
        const left = buildSum(node.left);
        const right = buildSum(node.right);
        node.sum = node.val + left + right;
        return node.sum;
    }
};

0820 Sunday

1. Total Hamming Distance

class Solution {
    public int totalHammingDistance(int[] nums) {
        int size = nums.length;
        int count = 0;
        for (int i = 0; i < 32; i++) {
            int numOfOnes = 0;
            int mask = 1 << i;
            for (int num : nums) {
                int increment = (num & mask) == 0 ? 0 : 1;
                numOfOnes += increment;
            }
            count += numOfOnes * (size - numOfOnes);
        }
        return count;
    }
}

Sadly this problem can only be solved by Java because js doens't have integers like Java or c++.

楼主加油