记录

1112 8. K-diff Pairs in an Array

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findPairs = function(nums, k) {
    // todo: check
    const map = new Map();
    for (let num of nums) {
        const count = map.has(num) ? map.get(num) + 1 : 1;
        map.set(num, count);
    }
    let res = 0;
    for (let [num, count] of map.entries()) {
        if (k === 0 && count > 1) {
            res++;
        }
        if (k > 0 && map.get(num + k) > 0) { // 我们加上k而不是用绝对值，这样就不必担心重复了
            res++;
        }
    }
    return res;
};

1112 9. Sqrt(x)

/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
    let left = 0;
    let right = x;
    while (left <= right) { // !!!! can equal
        // take right in the end
        const mid = left + Math.floor((right - left) / 2);
        const val = mid * mid;
        console.log(mid, val)
        if (val === x) {
            return mid; // !!! not return the val!
        } else if (x < val) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
        // !!!! what the heck is this? don't do the update blindly ??? Just check loop vars each time you exit a loop
        // left++;
        // right--;
    }
    return right;
};

sicilianee 发表于 2017-11-13 07:55
1112 9. Sqrt(x)

/**

Maybe we can automate it? like programming or driving?
check
1. loop, vars

1112 10.  Third Maximum Number

/**
* @param {number[]} nums
* @return {number}
*/
var thirdMax = function(nums) {
    // check
    if (nums.length < 3) {
        return Math.max(...nums);
    }
    let first = -Infinity;
    let second = -Infinity;
    let third = -Infinity;
    for (let num of nums) {
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second && num < first) { // !!! because we have equal, must check < here
            third = second;
            second = num;
        } else if (num > third && num < second) {
            third = num;
        }
    }
    // !!! f, s, t they could all equal !!!!
    return third !== -Infinity ? third : first;
};

1112 11. Number of Atoms

/**
* @param {string} formula
* @return {string}
*/
var countOfAtoms = function(formula) {
    // 这种傻逼题目最大的阻碍是怎么样先把有效的输入元素parse出来。然后才能写算法
    // valid els: H, (), 2
    // H3O6H
    // H3(O6H)4
    // K4(ON(SO3)2)2
   
    // check
    if (formula == null) {throw new Error()}
    if (formula.length === 0) {return 0}
    const list = [];
    let i = 0;
    while (i < formula.length) {
        if (formula[i] >= 'A' && formula[i] <= 'Z') {
            let j = i + 1;
            while (j < formula.length && formula[j] >= 'a' && formula[j] <= 'z') {
                j++;
            }
            const str = formula.slice(i, j);
            list.push(str);
            i = j;
        } else if (formula[i] === '(' || formula[i] === ')') {
            list.push(formula[i]);
            i++;
        } else {
            let j = i;
            while (j < formula.length && formula[j] >= '0' && formula[j] <= '9') {
                j++;
            }
            const str = formula.slice(i, j);
            list.push(Number.parseInt(str, 10));
            i = j;
        }
    }
    // algorithm starts
    const stack = [{}];
    let dict = stack[stack.length - 1];
    for (let [i, el] of list.entries()) {
        // (), number, str
        if (Number.isInteger(el)) {
            // do nothing
        } else if (el === '(') {
            dict = {};
            stack.push(dict);
        } else if (el === ')') {
            let count = (i + 1 === list.length || !Number.isInteger(list[i + 1])) ? 1 : list[i + 1];
            stack.pop();
            const topDict = stack[stack.length - 1];
            for (let [key, val] of Object.entries(dict)) {
                val = val * count;
                topDict[key] = (topDict[key] || 0) + val; // !!!! add value, not count !!! shit. One variable ruins all
            }
            dict = topDict;
        } else {
            dict[el] = dict[el] || 0;
            let count = (i + 1 === list.length || !Number.isInteger(list[i + 1])) ? 1 : list[i + 1];
            dict[el] = dict[el] + count;
        }
        i++;
    }
    // should have only one dict left in the stack
    const keys = Object.keys(dict).sort();
    return keys.map(key => dict[key] === 1 ? key : `${key}${dict[key]}`).join('');
   
};


这种傻逼题目之所以傻逼，
第一是你要parse输入到你可以操作的element
第二是代码太长，有一个变量搞错了，整个都错了。而且关键是这种i用成j ，val用成count，太难发现。错了就gg了。

第一点我们可以先过一遍，第二点怎么避免呢？

sicilianee 发表于 2017-11-13 09:45
1112 11. Number of Atoms

/**

第一点我们也可以建立class数据结构来装operands

1112 12. Serialize and Deserialize Binary Tree

bfs比pre order 难很多呀

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/

/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
    if (root == null) {return '#'}
    const list = [];
    const q = [root];
    while (q.length > 0) {
        const size = q.length;
        const level = [];
        for (let i = 0; i < size; i++) {
            const node = q.shift();
            const val = node == null ? '#' : node.val;
            list.push(val);
            if (node != null) {
                level.push(node.left);
                level.push(node.right);
            }
        }
        const has = level.some(node => node != null);
        if (has) {
            q.push(...level);
        }
    }
    console.log(list.join(','))
    return list.join(',')
};

/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
    const list = data.split(',').filter(str => str);
    if (list.length === 0 || list[0] === '#') {return null}
    const root = new TreeNode(Number.parseInt(list[0], 10));
    const q = [root];
    let i = 1;
    while (q.length > 0) {
        const node = q.shift();
        if (node != null && i < list.length) {
            const leftVal = list[i];
            const rightVal = list[i + 1];
            // console.log(leftVal, rightVal)
            i = i + 2;
            if (leftVal == '#') {
                node.left = null;
            } else {
                node.left = new TreeNode(Number.parseInt(leftVal, 10)); // !!!!! create a new node and assign, not just the number value !!!!
                q.push(node.left);
            }
            if (rightVal == '#') {
                node.right = null;
            } else {
                node.right = new TreeNode(Number.parseInt(rightVal, 10));
                q.push(node.right);
            }
            // console.log('the node')
            // console.log(node)
        }
    }
    console.log(root)
    return root;
};

/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/

sicilianee 发表于 2017-11-13 13:21
1112 12. Serialize and Deserialize Binary Tree

bfs比pre order 难很多呀

需要再多想想这道题

1113 1. Count Primes

/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
    if (n < 2) {return 0;}
    const arr = Array(n).fill(true);
    const limit = Math.floor(Math.sqrt(n));
    for (let i = 2; i <= limit; i++) { // !!! why can equal? because we use floor.
        if (arr[i]) {
            for (let j = i * i; j < n; j = j + i) {
                arr[j] = false;
            }
        }
    }
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (arr[i]) {count++;}
    }
    return count;
};

1113 2. Excel Sheet Column Title

/**
* @param {number} n
* @return {string}
*/
var convertToTitle = function(n) {
    let str = '';
    while (n != 0) {
        n = n - 1;
        const current = n % 26;
        const c = String.fromCharCode('A'.charCodeAt(0) + current);
        str = c + str; // !!!! newly added put in front
        n = Math.floor(n / 26);
    }
    return str
};