记录

1226 2. Encode String with Shortest Length

/**
* @param {string} s
* @return {string}
*/
var encode = function(s) {
    // 这是一道有感觉的题。
    // 0. if not simply backOne, backTwo, use a k to do a loop
    // 1. not only dp, but also include other cases in the middle of a dp iteration
    // 2. part of the string repeat, included in other sub problems.
    // 3. not focus on a single char repetition, but substrings' repetition
    if (s == null || s.length === 0) {
        return s;
    }
    const len = s.length;
    const dp = Array(len).fill().map(() => Array(len).fill());
    for (let l = 1; l <= s.length; l++) { // !!! l ++, not i ++
        for (let i = 0; i + l - 1 < s.length; i++) {
            const j = i + l - 1;
            dp[i][j] = s.slice(i, j + 1);
            for (let k = i; k < j; k++) {
                const newStr = dp[i][k] + dp[k + 1][j];
                if (newStr.length < dp[i][j].length) {
                    dp[i][j] = newStr;
                }
            }
            for (let k = i; k < j; k++) {
                const sub = s.slice(i, k + 1);
                const divisible = l % sub.length === 0;
                const count = Math.trunc(l / sub.length);
                if (divisible && sub.repeat(count) === s.slice(i, j + 1)) {
                    const newStr = `${count}[${dp[i][k]}]`;
                    if (newStr.length < dp[i][j].length) {
                        dp[i][j] = newStr;
                    }
                }
            }
        }
    }
    return dp[0][s.length - 1];
   
};

1226 3. Longest Substring with At Most Two Distinct Characters

/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstringTwoDistinct = function(s) {
    if (s == null || s.length === 0) {
        return 0;
    }
    if (s.length < 3) {
        return s.length
    }
    const map = new Map();
    let left = -1;
    let right = 0;
    let longest = 0;
    while (right < s.length) {
        const c = s[right];
        const count = map.get(c) || 0;
        map.set(c, count + 1);
        while (map.size > 2) { // !!! new api learned, map.size
            left++;
            const aChar = s[left];
            let count = map.get(aChar);
            count--;
            if (count === 0) {
                map.delete(aChar);
            } else {
                map.set(aChar, count);
            }
        }
        longest = Math.max(longest, right - left);
        right++; // !!! f***!!!!
    }
    return longest;
};

1230 1. Parse Lisp Expression

/**
* @param {string} expression
* @return {number}
*/
var evaluate = function(expression) {
    // our thoughts is:
    // 1. separate parens into its own parts
    // 2. start the parse, only exps, 3 cases: let, add, mult
    // for each case, start when hit (, use a list to save all the els, until we hit ),
    // we get all current list els and calc the result, and calc it and return
    if (expression == null || expression.length === 0) {
        throw new Error('invalid');
    }
    const exp = expression.split('').map(c => {
        if (c === '(') {
            return ' ( ';
        } else if (c === ')') {
            return ' ) ';
        } else {
            return c;
        }
    }).join('').split(' ').filter(str => str);
    const c = exp[0][0];
    if (c >= '0' && c <= '9' || c === '-') {
        return Number.parseInt(exp[0], 10);
    }
    exp.shift();
    return myEval(new Map());
   
    function myEval (map) {
        map = new Map(map);
        const operator = exp.shift();
        const isLet = operator === 'let';
        const list = [];
        while (exp.length > 0) {
            const el = exp.shift();
            if (el === '(') {
                const val = myEval(map);
                exp.unshift(String(val)); // !!!!! let the third case handle this, this is a good trick !!!!! GOOD GOOD GOOD. using this
                // you might even not need the list
            } else if (el === ')') {
                if (operator === 'let') {
                    return parseVal(list[list.length - 1], map);
                } else if (operator === 'add') {
                    return parseVal(list[0], map) + parseVal(list[1], map);
                } else {
                    return parseVal(list[0], map) * parseVal(list[1], map);
                }
            } else {
                list.push(el);
                if (isLet && list.length % 2 === 0) { // if is let, will need to
                    const key = list[list.length - 2];
                    const valStr = list[list.length - 1];
                    const val = parseVal(valStr, map);
                    map.set(key, val);
                }
            }
        }
    }
   
    function parseVal (valStr, map) {
        if (valStr[0] >= '0' && valStr[0] <= '9' || valStr[0] === '-') {
            return Number.parseInt(valStr, 10);
        } else {
            return map.get(valStr);
        }
    }
};

1230 2. Number of Distinct Islands II

/**
* @param {number[][]} grid
* @return {number}
*/
var numDistinctIslands2 = function(grid) {
    // so how it works is:
    // loop the grid, dfs each one with a list
    // after the dfs, if the list is valid, then add canonical value of this list to the set
    // in the end, return the size of the set
   
    // how to dfs:
    // check self, up, down, left, right, visit one and set itself to 0 (or use set)
    // for each point, add [x, y] to the list
   
    // how to get canonical value:
    // we have the list right?
    // loop 0 - 7, 8 times, for each code, we have a function to return the current form of the point
    // for each point of the list, loop under the code loop, get the new list
    // now for each list, we get the anchor point of that list, get the relative points representation of the list
    // it is still a point list
    // now we have a relative list, now we calc this list into a value, why not just concatenate everything into a str?
    // that should work. now we have the string key for each possible list, we get the smallest of the 8 keys and add it to the
    // set
    if (grid == null || grid.length === 0 || grid[0].length === 0) {
        return 0;
    }
    const rowLen = grid.length;
    const colLen = grid[0].length;
    const set = new Set();
    for (let i = 0; i < rowLen; i++) {
        for (let j = 0; j < colLen; j++) {
            const list = [];
            dfs(i, j, list);
            if (list.length > 0) {
                const val = getCanonical(list);
                set.add(val);
            }
        }
    }
    return set.size;
   
    function dfs (i, j, list) {
        if (i >= 0 && i < rowLen && j >= 0 && j < colLen && grid[i][j] === 1) {
            grid[i][j] = 0;
            list.push([i, j]);
            const moves = [[0, 1], [0, -1], [-1, 0], [1, 0]];
            for (let move of moves) {
                const x = i + move[0];
                const y = j + move[1];
                dfs(x, y, list);
            }
        }
    }
   
    function getCanonical (list) {
        let minVal = null;
        for (let i = 0; i < 8; i++) {
            const newList = [];
            for (let point of list) {
                const newPoint = getNewPoint(point, i);
                newList.push(newPoint);
            }
            // !!! for each of the lists, all of the points in the list, we need to normalize them
            // find the origin point and get the relative value of all points to this origin point
            let minX = Infinity;
            let minY = Infinity;
            for (let [x, y] of newList) {
                minX = Math.min(x, minX);
                minY = Math.min(y, minY);
            }
            const val = newList.map(([x, y]) => [x - minX, y - minY]).map(([x, y]) => `${x}:${y}`).sort().join(',');
            if (minVal == null || val < minVal) {
                minVal = val;
            }
        }
        return minVal;
    }
   
   
    function getNewPoint ([i, j], code) {
        switch (code) {
            case 0:
                return [i, j];
            case 1:
                return [i, -j];
            case 2:
                return [-i, j];
            case 3:
                return [-i, -j];
            case 4:
                return [j, i];
            case 5:
                return [j, -i];
            case 6:
                return [-j, i];
            case 7:
                return [-j, -i];
            default:
                throw new Error('No such type');
        }
    }
   
   
   
   
};

1231 1. Cracking the Safe

/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var crackSafe = function(n, k) {
    // get one less node
    // consider 1, 1
    // now start from one node
    // keep a seen set for edges
    // dfs
    // get all neighbors, start visiting them
    // when we visit one, we will first put it into the visited set
    // then we visit all its neightbors, then after done the loop of neighbors, we add itself the current x to the list
    // in the end we reverse the list or we just use unshift to add
   
    // construct one less, the basic one all 0
    let str = '';
    for (let i = 0; i < n - 1; i++) {
        str += '0';
    }
    const visited = new Set();
    const path = [];
    dfs(str);
    return str + path.join(''); // !!! need to add the starting point
   
    function dfs (str) {
        for (let i = 0; i < k; i++) {
            const newStr = str + i;
            if (!visited.has(newStr)) {
                visited.add(newStr);
                dfs(newStr.slice(1)); // !!! newStr.slice, not str.slice
                path.unshift(String(i)); // !!! the post order is important
            }
        }
    }
};

1231 2. Closest Binary Search Tree Value II

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} target
* @param {number} k
* @return {number[]}
*/
var closestKValues = function(root, target, k) {
    const preList = [];
    const postList = [];
    traverse(root);
    const ans = [];
    while ((preList.length > 0 || postList.length > 0) && k > 0) {
        if (preList.length === 0) {
            ans.push(postList.shift()); // !!!!! poping is from the back of the list, if you use pop, you might change the order you add the nodes
        } else if (postList.length === 0) {
            ans.push(preList.shift());
        } else {
            const a = preList[0];
            const b = postList[0]; // !!! same as above, you are using the first el, not the last el
            if (Math.abs(a - target) < Math.abs(b - target)) {
                ans.push(preList.shift());
            } else {
                ans.push(postList.shift());
            }
        }
        k--;
    }
    return ans;
   
    function traverse (node) {
        if (node == null) {
            return;
        }
        traverse(node.left);
        if (node.val <= target) {
            preList.unshift(node.val);
        } else {
            postList.push(node.val);
        }
        traverse(node.right);
    }
};


follow up how?

1231 3. Number of Islands II

/**
* @param {number} m
* @param {number} n
* @param {number[][]} positions
* @return {number[]}
*/
// !!! class is not hoisted, put it in the beginning
class DisjointSet {
    constructor (size) {
        this.parent = Array(size).fill().map((e, i) => i);
    }
    find (x) { // find the root
        while (this.parent[x] !== x) { // !!!! wtf, this is while, not if
            x = this.parent[x];
        }
        return x;
    }
    union (x, y) {
        this.parent[this.find(x)] = this.find(y);
    }
}
var numIslands2 = function(m, n, positions) {
    // we keep a union set and whenever we add a new island, we first add it, increase the count
    // then we see if we need to union it with someone. whenever we do that, we decrease the count
    // however, if two are unioned, then we check if the root is the same, if it is not the same, then we decrease the count again
    // basically we could union it with different nodes and each time we record the root of the set and put it into a set
    // in the end we count the size of the set to see how many numbers we need to decrease from the count
    // 0 - m * n - 1;
    const size = m * n;
    const dSet = new DisjointSet(size);
    const matrix = Array(m).fill().map(() => Array(n).fill(0));
    let count = 0;
    const ans = [];
    for (let [x, y] of positions) {
        matrix[x][y] = 1;
        count++;
        const moves = [[0, 1], [0, -1], [-1, 0], [1, 0]];
        const set = new Set();
        const index = x * n + y;
        for (let move of moves) {
            const newX = x + move[0];
            const newY = y + move[1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] === 1) {
                const newIndex = newX * n + newY;
                const root = dSet.find(newIndex);
                set.add(root); // !!! before we do the union, check the root. (after we union in the end they will all be the same root, not point)
                dSet.union(index, newIndex);
            }
        }
        count = count - set.size;
        ans.push(count);
    }
    return ans;
};

2018:
0102 1. Longest Substring with At Most K Distinct Characters

/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var lengthOfLongestSubstringKDistinct = function(s, k) {
    // check
    // keep a left & right, a hashmap, get the size of the map as the limit of k
    // each time we update right, update left and maxLen
    if (s == null || s.length === 0) {
        return 0;
    }
    let left = -1;
    let right = 0;
    const map = new Map();
    let max = 0;
    while (right < s.length) {
        const count = map.get(s[right]) || 0;
        map.set(s[right], count + 1);
        while (map.size > k) {
            left++;
            let count = map.get(s[left]);
            count--;
            if (count === 0) {
                map.delete(s[left]);
            } else {
                map.set(s[left], count);
            }
        }
        const len = right - left;
        max = Math.max(max, len);
        right++; // !!!! f*** it
    }
    return max;
};

0102 2. Maximum Vacation Days

/**
* @param {number[][]} flights
* @param {number[][]} days
* @return {number}
*/
var maxVacationDays = function(flights, days) {
    // key: from city i and week j, the value is fixed -- doesn't depend on what was before
    // it is ok you might never be able to reach most of the cells in the dp array
    if (flights == null || days == null || flights.length === 0 || days.length === 0) {
        return 0;
    }
    const numCity = days.length;
    const numWeek = days[0].length;
    const dp = Array(numCity).fill().map(() => Array(numWeek).fill(0));
    // the last week, just itself, loop all cities
    for (let i = 0; i < numCity; i++) {
        dp[i][numWeek - 1] = days[i][numWeek - 1];
    }
    // before, loop weeks
    for (let j = numWeek - 2; j >= 0; j--) {
        for (let i = 0; i < numCity; i++) {
            // 1. stay in the same city in the next week
            dp[i][j] = days[i][j] + dp[i][j + 1];
            // 2. change to another city in the next week
            for (let k = 0; k < numCity; k++) {
                if (flights[i][k] === 1) {
                    const value = days[i][j] + dp[k][j + 1];
                    dp[i][j] = Math.max(dp[i][j], value);
                }
            }
        }
    }
    // !!!! 1. because we can switch city on the first day
    // !!!! 2. we cannot choose any city, need to check the flights matrix
    let max = dp[0][0];
    for (let i = 0; i < numCity; i++) {
        if (flights[0][i]) {
            max = Math.max(max, dp[i][0]);
        }
    }
    return max;
};

sicilianee 发表于 2018-1-3 12:24
0102 2. Maximum Vacation Days

/**

1. increase num of weeks could normalize the last week
2. put the switch on the same day/week could normalize the first week