记录

Saturday

1.  Replace Words

/**
* @param {string[]} dict
* @param {string} sentence
* @return {string}
*/
var replaceWords = function(dict, sentence) {
    const words = sentence.split(' ')
    words.forEach((word, index) => {
        dict.forEach(pre => {
            if (words[index].startsWith(pre)) { // !!! you are modifying it, cannot use the original one
                words[index] = pre
            }
        })
    })
    return words.join(' ')
};

TODO
Cheating. Get the trie based solution.

2.  Construct the Rectangle

/**
* @param {number} area
* @return {number[]}
*/
var constructRectangle = function(area) {
    let pair
    for (let i = 1; i * i <= area; i++) {
        if (area % i === 0) {
            l = area / i
            pair = [l, i]
        }
    }
    return pair
};

NOTE:
1. the square trick.

Sunday:

1. Range Addition II

/**
* @param {number} m
* @param {number} n
* @param {number[][]} ops
* @return {number}
*/
var maxCount = function(m, n, ops) {
    const mins = ops.reduce(([minA, minB],[a, b]) => {
        return [Math.min(a, minA), Math.min(b, minB)]
    }, [Infinity, Infinity])
    // check the f***
    if (mins[0] === Infinity || mins[1] === Infinity) {
        return m * n
    }
    return mins[0] * mins[1]
};

TODO:
You missed empty ops at first.
Could just change m and n so that won't be a problem:
http://www.cnblogs.com/grandyang/p/6974232.html

Sunday:

2. Minimum Moves to Equal Array Elements

/**
* @param {number[]} nums
* @return {number}
*/
var minMoves = function(nums) {
    nums.sort((a, b) => a - b)
    return nums.reduce((memo, num) => {
        return memo + (num - nums[0])
    }, 0)
};


NOTE!!!!
Default sorting behavior for js array is to convert each el to string and sort by unicode value. NOT NUMBERS!!!

Monday

1. Intersection of Two Arrays

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
    const set = new Set()
    const result = new Set()
    nums1.forEach(num => set.add(num))
    nums2.filter(num => set.has(num)).forEach(num => result.add(num))
    return [...result]
};

去重，得用两个set

最后一题，今天一定要做出来：

Monday:

2. Top K Frequent Elements

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // first, get the count map
        // then, put into queue
        // then, get all out from q
        Map<Integer, Integer> countMap = new HashMap();
        for (int num : nums) {
            if (countMap.containsKey(num)) {
                countMap.put(num, countMap.get(num) + 1);
            } else {
                countMap.put(num, 1);
            }
        }
        Comparator<Map.Entry<Integer, Integer>> comparator = (a, b) ->  b.getValue() - a.getValue();
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue(comparator);
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            queue.add(entry);
        }
        List<Integer> list = new LinkedList();
        int count = 0;
        while (count < k) {
            // catch exception if any
            Map.Entry<Integer, Integer> entry = queue.remove();
            list.add(entry.getKey());
            count++;
        }
        return list;
    }
}


Exhausting.

Tuesday:

1. Maximum Length of Pair Chain

/**
* @param {number[][]} pairs
* @return {number}
*/
var findLongestChain = function(pairs) {
    pairs.sort((pair1, pair2) => pair1[1] - pair2[1]);
    if (pairs.length < 2) {
        return pairs.length;
    }
    let count = 1;
    let right = pairs[0][1];
    for (let i = 1; i < pairs.length; i++) {
        if (pairs[0] > right) {
            count++;
            right = pairs[1];
        }
    }
    return count;
};
NOTE:
1. 如何证明是重点。证明要从第一个pair开始。使用归纳法递推很多时候需要一个开始的点，初始的正确值。动态规划也属于归纳法的一种。

Tuesday

2. Ransom Note

/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
var canConstruct = function(ransomNote, magazine) {
    const ransomMap = new Map();
    const magazineMap = new Map();
    putStringToMap(ransomNote, ransomMap);
    putStringToMap(magazine, magazineMap);
    // if you need to break or return inside a loop, use a loop, not for each
    return [...ransomMap.entries()].every(([key, value]) => magazineMap.has(key) && (magazineMap.get(key) >= ransomMap.get(key)));
   
    function putStringToMap (str, map) {
        [...str].forEach(c => {
            if (map.has(c)) {
                map.set(c, map.get(c) + 1);   
            } else {
                map.set(c, 1);
            }
        })
    }
};

Loop through Map is painful in both java and js
TODO:
Better solution: use one map, increase and decrease. Use object for map might be shorter?

Missed about a whole week. Went on 3 day road trip last weekend and didn't got time to catch up.

0816 Wednesday

1. Assign Cookies

/**
* @param {number[]} g
* @param {number[]} s
* @return {number}
*/
var findContentChildren = function(g, s) {
    const sortNumber = (a, b) => a - b
    g.sort(sortNumber);
    s.sort(sortNumber);
    let gIndex = 0
    let count = 0;
    s.forEach((value) => {
        if (gIndex < g.length) {
            const gValue = g[gIndex];
            if (value >= gValue) {
                count++;
                gIndex++;
            } else {
                // continue
            }
        }
    });
    return count;
};
NOTE: js sort is for strings; if it is number, need to provide a predicate!!!

TODOS:
1. for each cannot break