记录

1031 2. Binary Tree Zigzag Level Order Traversal

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
    if (root == null) {return []}
    const q = [root];
    const res = [[root.val]];  // !!! same here, it is the value, not the node itself
    let left = true; // represent current traversing level
    while (q.length > 0) {
        const size = q.length;
        const level = [];
        for (let i = 0; i < size; i++) {
            const node = q.shift();
            if (left) {
                if (node.left) {level.push(node.left)}
                if (node.right) {level.push(node.right)}
            } else {
                if (node.right) {level.push(node.right)}
                if (node.left) {level.push(node.left)}
            }
        }
        left = !left // !!!!! flip it
        level.reverse();
        const values = level.map(item => item.val);
        if (values.length > 0) {
            res.push(values); // !!!! what we need to return is not the nodes, but the values !!!!!
        }
        q.push(...level);
    }
    return res;
};

1031 3. Bulls and Cows

/**
* @param {string} secret
* @param {string} guess
* @return {string}
*/
var getHint = function(secret, guess) {
    if (secret == null || secret.length === 0) {
        return ''
    }
    const dict1 = {};
    const dict2 = {};
    let count = 0;
    for (let i = 0; i < secret.length; i++) {
        const c1 = secret[i];
        const c2 = guess[i];
        if (c1 === c2) {
            count++;
        } else {
            dict1[c1] = dict1[c1] || 0;
            dict2[c2] = dict2[c2] || 0; // !!!! mixed them!!! when you have two, 1, 2, stuff, be careful
            dict1[c1]++;
            dict2[c2]++;
        }
    }
    let countB = 0;
    console.log(dict1)
    console.log(dict2)
    Object.entries(dict1).forEach(([c, count1]) => {
        const count2 = dict2[c] || 0;
        countB += Math.min(count1, count2);
    });
    return `${count}A${countB}B`
};

1031 4. Letter Combinations of a Phone Number

/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
    if (digits == null || digits.length === 0) {
        return [];
    }
    const dict = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z']
    }
    const res = [];
    const list = [];
    const len = digits.length;
    recurse(0);
    return res.map(arr => arr.join('')); // !!! they want strings, not lists
   
   
    function recurse (i) {
        if (i === len) {
            res.push([...list]);
            return;
        }
        const chars = dict[digits];
        for (let c of chars) {
            list.push(c);
            recurse(i + 1);
            list.pop();
        }
    }
   
};

1031 5. Search a 2D Matrix

/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
    if (matrix == null || matrix.length === 0 || matrix[0].length === 0) {
        return false;
    }
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    const size = rowLen * colLen;
    let left = 0;
    let right = size - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        const {i, j} = getIndices(mid); // !!!! (), not [], this is a function call, not normally an array
        const value = matrix[j];
        if (target < value) {
            right = mid - 1;
        } else if (target > value) {
            left = mid + 1;
        } else {
            return true;
        }
    }
    return false;
   

    function getIndices (index) {
        const i = Math.floor(index / colLen);
        const j = index - i * colLen;
        return {i, j}
    }
};

1031 6. UTF-8 Validation

/**
* @param {number[]} data
* @return {boolean}
*/
var validUtf8 = function(data) {
    if (data == null || data.length === 0) {
        return false;
    }
    const len = data.length;
    let i = 0;
    while (i < data.length) {
        const curr = data[i];
        let count = 0;
        let digit = 7;
        while (digit >= 0 && isOneAtDigit(curr, digit)) {
            count++;
            digit--;
        }
        console.log(count)
        if (count === 0) {
            i++; // !!!!! if you want to continue, check loop variable !!!
            continue;
        }
        if (count === 1 || count > 4) {return false;} // only 1 to 4 bytes long !!!! if larger than 4, false !!!
        const list = [];
        for (let j = i; j < i + count; j++) {
            list.push(data[j]);
        }
        if (!isValidSingleChar(list, count)) { // !!!! this should be after the loop
            return false;
        }
        i = i + count;
    }
    return true;
   
    function isValidSingleChar (list, count) {
        const len = list.length;
        const first = list[0];
        if (count !== len) {return false;}
        for (let i = 1; i < len; i++) {
            const num = list[i];
            const good = isOneAtDigit(num, 7) && !isOneAtDigit(num, 6);
            if (!good) {return false;}
        }
        return true;
    }
   
    function isOneAtDigit (num, i) {
        const mask = 1 << i;
        const res = num & mask;
        return res !== 0;
    }
};

They have shorter solutions.

1031 7. H-Index II

/**
* @param {number[]} citations
* @return {number}
*/
var hIndex = function(citations) {
    if (citations == null || citations.length === 0) {
        return 0;
    }
    let len = citations.length;
    let right = len;
    let left = 0;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        let count = 0;
        citations.forEach(c => {
            if (c >= mid) {
                count++;
            }
        });
        if (count === mid) { // !!! might be unnecessary !!! but this is more optimized
            return count;
        } else if (count < mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return right;
};

1031 8. Best Time to Buy and Sell Stock with Transaction Fee

/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function(prices, fee) {
    if (prices == null || prices.length === 0) {
        return 0;
    }
    let prevSold = 0;
    let prevHold = -prices[0];
    for (let i = 1; i < prices.length; i++) {
        let hold = Math.max(prevHold, prevSold - prices[i]);
        let sold = Math.max(prevSold, prevHold + prices[i] - fee);
        prevHold = hold;
        prevSold = sold;
    }
    return prevSold;
};

1031 9. Combination Sum II

/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
    if (candidates == null || candidates.length === 0) {
        return [];
    }
    candidates.sort((c1, c2) => c1 - c2);
    const res = [];
    const list = [];
    recurse(0, 0);
    return res;
   
    function recurse (i, sum) {
        if (sum > target) {
            return;
        }
        if (sum === target) {
            res.push([...list]);
            return;
        }
        if (i === candidates.length) {
            return;
        }
        for (let j = i; j < candidates.length; j++) {
            // !!!!! if == prev, cannot just allow if list top is same as prev, for things like 2, 2, 2, 2...
            // !!!!! note that i - 1 must be the prev element put into the list !!!! So we just do
            // j > i to allow continous adding
            if (j > i && candidates[j] === candidates[j - 1]) {
                continue;
            }
            if (j !== 0 && candidates[j] === candidates[j - 1]) {
                if (candidates[j] !== list[list.length - 1]) {
                    continue;
                }
            }
            list.push(candidates[j]); // !!!! shit !!! i and j, if you have them, make sure you use the right one!!!!  Maybe use start instead of i is better.
            recurse(j + 1, sum + candidates[j]);
            list.pop();
        }
    }
};

1101 1. Path Sum
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
    if (root == null) {
        return false;
    }
    sum -= root.val;
    if (root.left == null && root.right == null) {
        return sum === 0;
    }
    const left = hasPathSum(root.left, sum)
    const right = hasPathSum(root.right, sum);
    return left || right;
};


1101 2. Isomorphic Strings

/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isIsomorphic = function(s, t) {
    if (s == null || t == null || s.length != t.length) {
        return false;
    }
    // !!!!! another rule is two chars cannot map to the same char !!!!
    const set = new Set();
    const stDict = {};
    for (let i = 0; i < s.length; i++) {
        const sc = s[i];
        const tc = t[i];
        if (stDict[sc]) {
            if (tc !== stDict[sc]) {
                return false;
            }
        } else {
            if (set.has(tc)) {
                return false;
            }
            set.add(tc);
            stDict[sc] = tc;
        }
    }
    return true;
};

1101 3. Super Pow

/**
* @param {number} a
* @param {number[]} b
* @return {number}
*/
var superPow = function(a, b) {
    const mod = 1337;
    let ans = 1;
    const len = b.length;
    for (let i = len - 1; i >= 0; i--) {
        ans = ans * quickPow(a, b[i]) % mod; // !!! ans, multiply it !!!
        a = quickPow(a, 10); // !!! here no mod, is a
    }
    return ans;
   
    function quickPow (a, b) {
        a = a % mod;
        let ans = 1;
        while (b > 0) { // !!! 0
            if (b % 2 === 1) {
                ans = ans * a % mod; // !!!! will always reach this line in the end no matter what
            }
            a = a * a % mod;
            b = b >>> 1;
        }
        return ans;
    }
};


全是数学，有几个公式要记住。挺难的。