记录

1008 2. Combinations

/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
    const res = [];
    const list = [];
    const recurse = (start, used) => {
        if (used === k) {
            res.push([...list]);
            return;
        }
        for (let i = start; i <= n; i++) {
            list.push(i);
            recurse(i + 1, used + 1);
            list.pop();
        }
    }
    recurse(1, 0);
    return res;
};

sicilianee 发表于 2017-10-9 09:32
1008 2. Combinations

/**

Seems like there is an iterative solution.

Make up.
0811 1. Spiral Matrix II

/**
* @param {number} n
* @return {number[][]}
*/
var generateMatrix = function(n) {
    if (n <= 0) {
        return [];
    }
    let i = 1;
    let x = 0;
    let y = 0;
    const res = Array(n).fill().map(() => Array(n).fill(0));
    res[0][0] = i;
    i++;
    while (i <= n * n) {
        // !!!! Need to test the next step before we enter the next step: x, y. We only enter if it is valid. The first one would be omitted
        while (y + 1 < n && res[x][y + 1] === 0) {
            res[x][y + 1] = i;
            i++;
            y++;
        }
        while (x + 1 < n && res[x + 1][y] === 0) {
            res[x + 1][y] = i;
            i++;
            x++;
        }
        while (y - 1 >= 0 && res[x][y - 1] === 0) {
            res[x][y - 1] = i;
            i++;
            y--;
        }
        while (x - 1 >= 0 && res[x - 1][y] === 0) {
            res[x - 1][y] = i;
            i++;
            x--;
        }
    }
    return res;
};
TODO: This solution is too fragile: subtle details. Check the other one.

Make up.

0811 2.  Valid Square

/**
* @param {number[]} p1
* @param {number[]} p2
* @param {number[]} p3
* @param {number[]} p4
* @return {boolean}
*/
var validSquare = function(p1, p2, p3, p4) {
    const set = new Set();
    const pairs = [[p1, p2], [p1, p3], [p1, p4], [p2, p3], [p2, p4], [p3, p4]];
    for (let i = 0; i < pairs.length; i++) {
        const pair = pairs[i];
        const distance = getDistance(pair[0], pair[1]);
        if (distance === 0) {
            return false;
        } else {
            set.add(distance);
        }
    }
    return set.size === 2;
};

function getDistance (p1, p2) {
    const dx = p1[0] - p2[0];
    const dy = p1[1] - p2[1];
    return dx * dx + dy * dy;
}

Make up
0812 1. Remove Duplicates from Sorted List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
    if (head == null) {return head;}
    let node = head;
    while (node.next != null) {
        if (node.val === node.next.val) {
            node.next = node.next.next;
        } else {
            node = node.next;
        }
    }
    return head;
};

Make up

0812 2. Path Sum III

/**
* 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 0;
    }
    const self = startFrom(root, sum);
    const left = pathSum(root.left, sum);
    const right = pathSum(root.right, sum);
    return self + left + right;
};

function startFrom (node, num) {
    if (node == null) {
        return 0;
    }
    const self = node.val === num ? 1 : 0;
    const left = startFrom(node.left, num - node.val);
    const right = startFrom(node.right, num - node.val);
    return self + left + right;
}

Make up

0813 1. Search Insert Position

/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
    let start = 0;
    let end = nums.length - 1;
    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (nums[mid] === target) {
            return mid; // !!!!! Equal just self, not prev !!! Insert will push the current backward!!!
        } else if (target < nums[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return start;
};

Make up

0813 2. Number of 1 Bits

/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
    let count = 0;
    while (n !== 0) {
        if ((n & 1) === 1) {count++;}
        n = n >>> 1;
    }
    return count;
};

Make up
0814 1. Maximum Subarray

/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
    if (nums == null || nums.length === 0) {throw new Error('Invalid input')}
    let max = nums[0];
    let curSum = nums[0];
    for (let i = 1; i < nums.length; i++) { // !!! must start with 1, prepare the first one. Pretty tricky
        curSum = Math.max(curSum + nums, nums[i]);
        max = Math.max(curSum, max);
    }
    return max;
};[/i]
Pretty tricky.
Must start with the second one: i === 1, cause we need to prepare the max sum.

Make up

0814 2. Increasing Triplet Subsequence

/**
* @param {number[]} nums
* @return {boolean}
*/
var increasingTriplet = function(nums) {
    let a = null
    let b = null
    for (let num of nums) {
        if (a == null || num <= a) { // !!!! equals
            a = num;
        } else if (b == null || num <= b) { // !!!! equals
            b = num;
        } else {
            return true;
        }
    }
    return false;
};

Still need to think about his. Not fully understand why.