记录

0820 Sunday

2. Majority Element

/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
    // key of an object cannot be a number, it will be converted to a string!!!
    const map = new Map();
    nums.forEach(num => {
        if (map.has(num)) {
            map.set(num, map.get(num) + 1);
        } else {
            map.set(num, 1);
        }
    });
    let maxPair = [0, 0];
    map.forEach((value, key) => {
        if (value >= maxPair[1]) {
            maxPair = [key, value];   
        }
    });
    return maxPair[0];
};
NOTE:
1. js object dict can only have string keys. If you use number as keys, it will be converted to string and when you retrieve it you will get a string not a number!


Better Solution:

/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
    // if set to 1, it still works for majority: why? because everyone needs to defeat the hero, but the hero
    // always needs to fight back and win one back. So other people will win at most one more element, but the hero
    // has one more element from the right begining, so he will always win the last battle and has the crown.
    // note: whoever wins the battle will win one element
    // However, set to 0 is the easist way.

    if (nums == null || nums.length === 0) {
        throw new Error('Illegal argument');
    }
    let majority = nums[0];
    let count = 0;
    nums.forEach(num => {
        if (count === 0) {
            majority = num;
            count = 1;
        } else {
            if (num === majority) {
                count++;
            } else {
                count--;
            }
        }
    });
    return majority;
};

0823 Wednesday

1. Binary Tree Inorder Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
    const stack = [];
    const results = [];
    let node = root;
    while (node != null || stack.length > 0) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            results.push(node.val);
            node = node.right;
        }
    }
    return results;
};

0823 Wednesday

2.  4Sum II

/**
* @param {number[]} A
* @param {number[]} B
* @param {number[]} C
* @param {number[]} D
* @return {number}
*/
var fourSumCount = function(A, B, C, D) {
    const map1 = new Map();
    const map2 = new Map();
    buildMap(A, B, map1);
    buildMap(C, D, map2);
    let count = 0;
    map1.forEach((count1, sum1) => {
        if (map2.has(-sum1)) {
            count += count1 * map2.get(-sum1);
        }
    });
    return count;
   
   
    function buildMap(nums1, nums2, map) {
        nums1.forEach(num1 => {
            nums2.forEach(num2 => {
                const sum = num1 + num2;
                if (map.has(sum)) {
                    map.set(sum, map.get(sum) + 1);
                } else {
                    map.set(sum, 1);
                }
            });
        });
    }
};
When you don't know what to do, try hashmap.

0824 Thursday

1. First Unique Character in a String

/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function(s) {
    const map = new Map();
    s.split('').forEach((c, index) => {
        if (map.has(c)) {
            map.set(c, -1)
        } else {
            map.set(c, index);
        }
    });
    let minIndex = Number.MAX_VALUE;
    map.forEach(index => {
        if (index >= 0) {
            minIndex = Math.min(index, minIndex);
        }
    });
    return minIndex === Number.MAX_VALUE ? -1 : minIndex;
};

Just set count to map.
Second loop loop the string, not the map. That is more straightforward.
Good way to convert min of array in js: spread operator.

0824 Thursday

2. Relative Ranks

/**
* @param {number[]} nums
* @return {string[]}
*/
var findRelativeRanks = function(nums) {
    // first make a copy and sort the array
    // second, for the copy, count and put each into map
    // loop the original and turn into result
    let copyNums = [...nums].sort((num1, num2) => num2 - num1);
    const map = new Map();
    copyNums.forEach((num, index) => {
        if (!map.has(num)) {
            map.set(num, index + 1);
        }
    });
    return nums.map(num => map.get(num)).map(rank => getRankString(rank));
   
   
    function getRankString (rank) {
        switch (rank) {
            case 1:
                return 'Gold Medal';
            case 2:
                return 'Silver Medal';
            case 3:
                return 'Bronze Medal';
            default:
                return `${rank}`;
        }
    }
                                    
};

0825 Friday

1. Shuffle an Array

It shows my solution was wrong. Don't know why.

/**
* @param {number[]} nums
*/
var Solution = function(nums) {
    this.nums = nums;
    const permutations = [];
    buildPermutations(nums, 0);
    this.permutations = permutations;
    console.log(permutations)
    let size = 1;
    for (let i = 1; i <= nums.length; i++) {
       size = size * i;
    }
    this.size = size;
    console.log(size);
   
   
    function buildPermutations (nums, i) {
        if (i === nums.length - 1) {
            permutations.push([...nums]);
        }
        for (let j = i; j < nums.length; j++) {
            ;[nums[i], nums[j]] = [nums[j], nums[i]];
            buildPermutations(nums, i + 1);
            ;[nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }
};

/**
* Resets the array to its original configuration and return it.
* @return {number[]}
*/
Solution.prototype.reset = function() {
    return this.nums;
};

/**
* Returns a random shuffling of the array.
* @return {number[]}
*/
Solution.prototype.shuffle = function() {
    // 0 - N - 1
    const num = Math.floor(Math.random() * this.size);
    return this.permutations[num];
};

/**
* Your Solution object will be instantiated and called as such:
* var obj = Object.create(Solution).createNew(nums)
* var param_1 = obj.reset()
* var param_2 = obj.shuffle()
*/

sicilianee 发表于 2017-8-28 03:17
0825 Friday

1. Shuffle an Array

Another version:This shuffle is what underscore uses.
Passed when I submit again.

/**
* @param {number[]} nums
*/
var Solution = function(nums) {
    this.nums = nums;
};

/**
* Resets the array to its original configuration and return it.
* @return {number[]}
*/
Solution.prototype.reset = function() {
    return this.nums;
};

/**
* Returns a random shuffling of the array.
* @return {number[]}
*/
Solution.prototype.shuffle = function() {
    const numsCopy = [...this.nums];
    for (let i = 0; i < numsCopy.length; i++) {
        const random = Math.floor(Math.random() * (i + 1));
        ;[numsCopy, numsCopy[random]] = [numsCopy[random], numsCopy[i]];
    }
    return numsCopy;
};

/**
* Your Solution object will be instantiated and called as such:
* var obj = Object.create(Solution).createNew(nums)
* var param_1 = obj.reset()
* var param_2 = obj.shuffle()
*/[/i]

sicilianee 发表于 2017-8-28 03:17
0825 Friday

1. Shuffle an Array

Accepted using Fisher-Yates algorithm

/**
* @param {number[]} nums
*/
var Solution = function(nums) {
    this.nums = nums;
};

/**
* Resets the array to its original configuration and return it.
* @return {number[]}
*/
Solution.prototype.reset = function() {
    return this.nums;
};

/**
* Returns a random shuffling of the array.
* @return {number[]}
*/
Solution.prototype.shuffle = function() {
    const numsCopy = [...this.nums];
    for (let i = numsCopy.length - 1; i >= 0; i--) {
        const random = Math.floor(Math.random() * (i + 1));
        ;[numsCopy[i], numsCopy[random]] = [numsCopy[random], numsCopy[i]];
    }
    return numsCopy;
};

/**
* Your Solution object will be instantiated and called as such:
* var obj = Object.create(Solution).createNew(nums)
* var param_1 = obj.reset()
* var param_2 = obj.shuffle()
*/

0826 Saturday

1. Fraction Addition and Subtraction

/**
* @param {string} expression
* @return {string}
*/
var fractionAddition = function(expression) {
    if (!expression) {
        return '';
    }
    expression = expression[0] === '-' ? expression : `+${expression}`;
    const signs = expression.split('').filter(c => ['+', '-'].includes(c)).map(str => {
        return str === '+' ? 1 : -1;
    });
    const nums = expression.split(/\+|-/).filter(num => num); // not includeing first
    console.log(nums);
    const items = nums.map(num => num.split('\/').map(part => Number.parseInt(part, 10)))
        .map(([num, den], index) => ({num: signs[index] * num, den}));
    console.log(items);
    const item = items.reduce((sum, item) => {
        let den = sum.den * item.den;
        let num = sum.num * item.den + item.num * sum.den;
        console.log(den);
        console.log(num);
        // zero and neg
        if (num === 0) {
            den = 1;
        } else {
            const aGcd = gcd(Math.abs(num), den);
            num = num / aGcd;
            den = den / aGcd;            
        }
        return {num, den};
    });
    return item < 0
        ? `-${item.num}/${item.den}`
        : `${item.num}/${item.den}`;

};
// positive
function gcd (a, b) {
    let bigger, smaller;
    console.log(a);
    console.log(b);
    if (a >= b) {
        bigger = a;
        smaller =b;
    } else {
        bigger = b;
        smaller = a;
    }
    if (bigger % smaller === 0) {
        return smaller;
    } else {
        return gcd(smaller, bigger % smaller);
    }
}
TODO: revisit


补充内容 (2017-8-31 12:05):
The return part is wrong. But it returns the correct answer because item < 0 is never truthy

sicilianee 发表于 2017-8-30 15:48
0826 Saturday

1. Fraction Addition and Subtraction

/**
* @param {string} expression
* @return {string}
*/
var fractionAddition = function(expression) {
    if (expression == null || expression.length === 0) {return '';}
    expression = expression[0] === '-' ? expression : `+${expression}`;
    const signs = expression.split('').filter(c => ['+', '-'].includes(c)).map(sign => {
        return sign === '+' ? 1 : -1;
    });
    const items = expression.split(/\+|-/).filter(str => str).map(str => str.split('/')
        .map(numStr => Number.parseInt(numStr, 10)))
        .map(([num, den], index) => ({num: num * signs[index], den}));
    const sum = items.reduce((sum, item) => {
        let den = sum.den * item.den;
        let num = sum.num * item.den + item.num * sum.den;
        const aGcd = gcd(Math.abs(num), den);
        den = den / aGcd;
        num = num / aGcd;
        return {num, den};
    });
    return `${sum.num}/${sum.den}`;
};

function gcd (a, b) { // non-neg
    while (b !== 0) {
        ;[a, b] = [b, a % b];
    }
    return a;
}