记录

0826 Saturday

2. Delete Node in a Linked List

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

0827 Monday

1. Same Tree

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
    const pNull = p == null;
    const qNull = q == null;
    if (pNull && qNull) {return true;}
    if (pNull && !qNull || !pNull && qNull || p.val !== q.val) {
        return false;
    }
    const left = isSameTree(p.left, q.left);
    const right = isSameTree(p.right, q.right);
    return left && right;
};

0827 Monday

2. Valid Anagram

/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function(s, t) {
    const mapS = new Map();
    const mapT = new Map();
    putToMap(mapS, s);
    putToMap(mapT, t);
    if (mapS.size !== mapT.size) {return false;}
    for (let [key, value] of mapS.entries()) {
        if (!mapT.has(key) || mapT.get(key) !== value) {
            return false;
        }
    }
    return true;
};

function putToMap (map, str) {
    str.split('').forEach(c => {
        if (map.has(c)) {
            map.set(c, map.get(c) + 1);
        } else {
            map.set(c, 1);
        }
    })
}

0828 Tuesday

1. Integer Break

/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
    const map = new Map();
    return findMax(n);
   
    function findMax (n) {
        if (map.has(n)) {
            return map.get(n);
        }
        if (n === 1) {return 1;}
        let max = 1;
        for (let i = 1; i < n; i++) {
            const multiplier = Math.max(n - i, findMax(n - i));  // !!! could also be n-1 !!!
            max = Math.max(max, i * multiplier);
        }
        map.set(n, max);
        return max;
    }
};

sicilianee 发表于 2017-8-31 14:34
0828 Tuesday

1. Integer Break

The dp solution

/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
    const dp = new Array(n + 1).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 1; j <= i; j++) {
            if (i + j <= n) {
                const left = Math.max(dp, i);
                const right = Math.max(dp[j], j);
                dp[i + j] = Math.max(left * right, dp[i + j]);
            }
        }
    }
    return dp[n];
};
The key: make sure when you use the element, it has already been calculated.

1. one number can be broken into to parts, and further
2. the two parts are both smaller than the number, and one is larger/equal to the other one.
3. thus, i and j where j <= i could fulfill all cases that could add up to a number, so when the first time you use it which is i reached it, it has already been calculated.

0828

2.  Maximum XOR of Two Numbers in an Array

/**
* @param {number[]} nums
* @return {number}
*/
var findMaximumXOR = function(nums) {
    let mask = 0;
    let result = 0;
    for (let i = 31; i >= 0; i--) {
        mask = mask | (1 << i);
        const set = new Set(nums.map(num => num & mask));
        const preResult = result | (1 << i); // here is not mask
        for (let prefix of set) {
            const preSelf = prefix ^ preResult;
            if (set.has(preSelf)) {
                result = preResult;   
                break;
            }
        }
    }
    return result;
};
Pretty hard.
1. a ^ b = c, a = b ^ c
2. many bitwise operations in this problem. Be careful with them

sicilianee 发表于 2017-9-5 07:55
0828

2.  Maximum XOR of Two Numbers in an Array

1. Considering the sign bit, we start from 30 not 31
2. should pay attention to (1 << i). error prone.


/**
* @param {number[]} nums
* @return {number}
*/
var findMaximumXOR = function(nums) {
    let result = 0;
    let mask = 0;
    for (let i = 30; i >= 0; i--) {
        mask = mask | (1 << i);
        const set = new Set(nums.map(num => num & mask));
        for (let prefix of set) {
            const newResult = result | (1 << i);
            const newSelf = prefix ^ newResult;
            if (set.has(newSelf)) {
                result = newResult;   
            }
        }
    }
    return result;
};

0829

1. Count Numbers with Unique Digits

/**
* @param {number} n
* @return {number}
*/
var countNumbersWithUniqueDigits = function(n) {
    let sum = 0;
    for (let i = 0; i <= n; i++) {
        sum = sum + countUnitInDigit(i);
    }
    return sum;
   
    function countUnitInDigit (n) {
        if (n === 0) {
            return 1;
        }
        let memo = 9;
        for (let i = 1; i < n; i++) {
            memo = memo * (10 - i);
        }
        return memo;        
    }
};

TODO: could combine into one loop; Reuse what's calculated

sicilianee 发表于 2017-9-5 09:03
0829

1. Count Numbers with Unique Digits

/**
* @param {number} n
* @return {number}
*/
var countNumbersWithUniqueDigits = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 9;
    for (let i = 2; i <= n; i++) {
        dp[i] = (11 - i) * dp[i - 1];
    }
    let sum = 0;
    for (let i = 0; i <= n; i++) {
        sum += dp[i];
    }
    return sum;
};

0829 2. Add Two Numbers II

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
    const len1 = getLen(l1);
    const len2 = getLen(l2);
    let shortNode, longNode;
    if (len1 >= len2) {
        shortNode = l2;
        longNode = l1;
    } else {
        shortNode = l1;
        longNode = l2;
    }
    const startIndex = Math.abs(len1 - len2);
    let dummy = new ListNode(0);
    let prev = dummy;
    for (let i = 0; i < Math.max(len1, len2); i++) {
        let value = 0;
        if (i < startIndex) {
            value = longNode.val;
        } else {
            value = longNode.val + shortNode.val;
            shortNode = shortNode.next;
        }
        longNode = longNode.next;
        prev.next = new ListNode(value);
        prev = prev.next;
    }
    let node = dummy;
    let next = dummy.next;
    while (next != null) {
        let carry = 0;
        if (next.val < 9) {
            carry = 0;
        } else if (next.val > 9) {
            carry = 1;           
            next.val = next.val - 10;
        } else { // === 9
            next = next.next;
            continue;
        }
        node.val = node.val + carry;
        node = node.next;
        while (node !== next) {
            node.val = carry === 1 ? 0 : node.val;
            node = node.next;
        }
        next = next.next;
    }
    return dummy.val === 0 ? dummy.next : dummy;
};

function getLen (node) {
    let count = 0;
    while (node != null) {
        count++;
        node = node.next;
    }
    return count;
}



Not easy.

TODO: there is a recursion solution which I think is also valid. I feel other solutions are kind of like cheating.