记录

Make up

0810 2. Binary Tree Level Order Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
    if (root == null) {return []}
    const queue = [root];
    const res = [];
    while (queue.length > 0) {
        const len = queue.length;
        const level = [];
        for (let i = 0; i < len; i++) {
            const node = queue.shift();
            level.push(node.val);
            if (node.left != null) {queue.push(node.left)}
            if (node.right != null) {queue.push(node.right)}
        }
        res.push(level);
    }
    return res;
};

1005 1. Power of Three

/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfThree = function(n) {
    while (n >= 3) {
        n = n / 3;
    }
    return n === 1;
};

TODO:
The follow up is worth thinking about. They have a solution. Read it.
Need to think about floating point and precision in js.

1005 2. Set Mismatch

/**
* @param {number[]} nums
* @return {number[]}
*/
var findErrorNums = function(nums) {
    const map = new Map();
    nums.forEach(num => {
        const count = map.has(num) ? map.get(num) + 1 : 1;
        map.set(num, count);
    });
    let a;
    let b;
    for (let i = 1; i <= nums.length; i++) {
        if (!map.has(i)) {
            b = i;
        } else if (map.get(i) === 2) {
            a = i;
        }
    }
    return [a, b];
};

sicilianee 发表于 2017-10-6 13:18
1005 2. Set Mismatch

/**

/**
* @param {number[]} nums
* @return {number[]}
*/
var findErrorNums = function(nums) {
    let xor = nums.reduce((prev, curr) => prev ^ curr);
    for (let i = 1; i <= nums.length; i++) {
        xor ^= i;
    }
    const rightMostBit = xor & ~(xor - 1);
    let xor0 = 0;
    let xor1 = 0;
    nums.forEach(num => {
        if ((rightMostBit & num) === 0) { // !!!!!!!!!!!!!! shit again !!!!!!!!!!!!!!!!! BITWISE PRECEDENCE
            xor0 ^= num;
        } else {
            xor1 ^= num;
        }
    });
    for (let i = 1; i <= nums.length; i++) {
        if ((rightMostBit & i) === 0) {
            xor0 ^= i;
        } else {
            xor1 ^= i;
        }
    }
    if (nums.includes(xor0)) {
        return [xor0, xor1];
    } else {
        return [xor1, xor0];
    }
};

sicilianee 发表于 2017-10-6 14:32
/**
* @param {number[]} nums
* @return {number[]}

So an array using o(n) space
- reduce to o(1) space: usually operate on the same array with negative or alike
- reduce to o(1) space without modifying original array, usually using bitwise manipulations. Either ^ or alike or using 32 bit character.

1006 1. Contiguous Array

/**
* @param {number[]} nums
* @return {number}
*/
var findMaxLength = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    let count = 0;
    let max = 0;
    const map = new Map([[0, -1]]);
    for (let i = 0; i < nums.length; i++) {
        const value = nums[i] === 1 ? 1 : -1;
        count += value;
        if (map.has(count)) {
            max = Math.max(max, i - map.get(count));
        } else {
            map.set(count, i);
        }
    }
    return max;
};

1006 2.  Subarray Sum Equals K

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
    if (nums == null) {return 0;}
    let sum = 0;
    let count = 0;
    const map = new Map([[0, 1]]); // !!! target sum, and count, this is what we store !!!
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        const target = sum - k;
        if (map.has(target)) {
            count += map.get(target);
        }
        const value = map.has(sum) ? map.get(sum) + 1 : 1;
        map.set(sum, value);
    }
    // if (k === 0) {count++;}   they don't count empty array as count is zero, or as subarray
    return count;
};

1007 1. Power of Two

/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
    if (n <= 0) {return false;} // !!! could even be negative
    return n === (n & (~(n - 1)));
};

1007 2. Climbing Stairs

/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
    if (n <= 0) {return 0;}
    const dp = Array(n + 1).fill(0);
    dp[0] = 1; // !!!! because we need to use it
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

1008 1. Find Minimum in Rotated Sorted Array

/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
    if (nums == null || nums.length === 0) {
        return null;
    }
    let start = 0;
    let end = nums.length - 1;
    if (nums[start] < nums[end]) { // !!!! this situation does happen!!!!
        return nums[start];
    }
    while (start < end) {
        let mid = Math.floor((start + end) / 2);
        if (nums[mid] > nums[start]) {
            start = mid;
        } else if (nums[mid] < nums[start]) {
            end = mid;
        } else {
            start++;   // this is also very important, midVal === starVal, we increase start
        }
    }
    return nums[start];
};