记录

0106 1. Minimum Unique Word Abbreviation

/**
* @param {string} target
* @param {string[]} dictionary
* @return {string}
*/
var minAbbreviation = function(target, dictionary) {
    // ！！！！1. 注意，二进制编码的pattern和字符串的patttern顺序是反过来的，而且注意你得到的是数字，用的时候可能要转换成字符串，
    // 而且转换的时候要明确表明使用二进制来转换
    // 2. 转换成bit manipulation 来做真的是，虽然会判断上简单一些，写起来有太多的弯要转，更容易出错。
    // convert to int, so that 1. reduce the len; 2. bit manipulation supposedly faster
    if (target == null || target.length === 0) {return ''}
    if (dictionary == null || dictionary.length === 0) {return String(target.length)}
    // only keep same len words
    const len = target.length;
    dictionary = dictionary.filter(word => word.length === len);
    // convert words to bits
    const dict = dictionary.map(word => {
        let bit = 0;
        for (let i = 0; i < len; i++) {
            if (word[i] !== target[i]) { // !!! keep diff, not same chars
                bit += (1 << i);
            }
        }
        return bit;
    });
    // get the base of all bits
    // !!! the dict could be f***ing empty, so we must provide an initial value for reduce !!!
    const base = dict.reduce((prev, curr)  => prev | curr, 0);
   
    // 1.
    // https://discuss.leetcode.com/topic/61457/c-bit-manipulation-dfs-solution
    // 他们这个解法实际上是做了一些剪枝，每次都测试，当当前的值大于已经有的最小值，就不再继续当前的dfs了，注意并不是直接结束搜索，只是终止当前这一分支
    // 其他的搜索仍旧继续。（有一点值得注意的是他们在判断是否valid之前先判断长度，如果长度比当前答案大不管是不是valid直接就停止）(剪枝中间还有一些
    // 问题值得思考，参考stepen的评论)
    // 我们这里就不剪枝了。
    // 2.
    // 注意leetcode的tag，这题也可以不用bit manipulation
    // http://www.cnblogs.com/grandyang/p/5935836.html
    // 复杂度感觉应该是一样的，但是肯定要慢些，你要符合出题人考察的点，所以要看tag
   
    let ans = [base, getLen(base)];
    dfs(0, 0);
    // restore the ans bit
    const bit = ans[0];
    let str = '';
    for (let i = 0; i < len; i++) {
        const mask = 1 << i;
        if ( (mask & bit) > 0 ) {
            // use this char
            str += target[i];
        } else {
            // ignore this one, start from this one, do a loop and count number of 0s
            let j = i + 1;
            while ( j < len && ((1 << j) & bit) === 0 ) {
                j++;
            }
            const count = j - i;
            str += String(count);
            // !!! update it !
            i = j - 1;
        }
    }
    return str;
   
   
    function getLen (bit) {
        const str = bit.toString(2).padStart(len, '0'); // !!!! 1. use base-2, 2. pad it to full length
        const parts = str.split('1').filter(str => str);
        const ones = str.split('').filter(c => c === '1');
        return parts.length + ones.length;
    }
   
    function dfs (bit, i) {
        if (i === len) {
            // we got one pattern, verify it
            // !!! not only do we compute the length, we need to first verify it is a valid answer
            const good = dict.every(aBit => (aBit & bit) > 0);
            if (good) {
                const currLen = getLen(bit);
                if (currLen < ans[1]) {
                    ans = [bit, currLen];
                }   
            }
            return;
        }
        dfs(bit, i + 1);
        if ( (base & (1 << i)) > 0) { // NOTE: > 0, not 1
            dfs(bit + (1 << i), i + 1);
        }
    }
};

1. 这题要反复练习，bit manipulation，简直了，错的太多了
2. 这两天心有点飞啊……只做了一道题，有点慢那

0108 1. Employee Free Time

/**
* Definition for an interval.
* function Interval(start, end) {
*     this.start = start;
*     this.end = end;
* }
*/
/**
* @param {Interval[][]} schedule
* @return {Interval[]}
*/
var employeeFreeTime = function(schedule) {
    // !!! note they defined interval, not a pair !!!!
    // first, flatten schedule
    if (schedule == null || schedule.length === 0) {
        return [];
    }
    schedule = schedule.reduce((arr1, arr2) => [...arr1, ...arr2], []);
    // {start, end}
    const events = schedule.map(({start, end}) => [{time: start, val: 1}, {time: end, val: -1}]).reduce((prev, curr) => [...prev, ...curr], []);
    events.sort((e1, e2) => e1.time - e2.time); // !!! need to sort
    let count = 0;
    const ans = [];
    // !!!! need to remove those that are 0 length
    for (let i = 0; i < events.length - 1; i++) {
        const {time, val} = events[i];
        count += val;
        if (count === 0) {
            const endTime = events[i + 1].time;
            if (time !== endTime) {
                ans.push(new Interval(time, endTime));
            }
        }
    }
    return ans;
};

0108 2.  Set Intersection Size At Least Two

/**
* @param {number[][]} intervals
* @return {number}
*/
var intersectionSizeTwo = function(intervals) {
    // !!! the return value is a real set, could be disjoint, while the input intervals are pairs representing continuous values
    if (intervals == null || intervals.length === 0) {
        return 0;
    }
    intervals.sort((ia, ib) => {
        return ia[0] - ib[0] === 0
            ? ib[1] - ia[1]
            : ia[0] - ib[0];
    });
    const stack = [];
    for (let interval of intervals) {
        if (stack.length > 0) {
            while (stack.length > 0 && stack[stack.length - 1][0] <= interval[0] && stack[stack.length - 1][1] >= interval[1]) {
                stack.pop();
            }
        }
        stack.push(interval);
    }
    const list = stack;
    let lastTwo = null;
    let count = 0;
    for (let interval of list) {
        if (lastTwo == null || lastTwo[1] < interval[0]) {
            count += 2;
            lastTwo = [interval[1] - 1, interval[1]];
        } else if (lastTwo[0] < interval[0] && lastTwo[1] >= interval[0]) { // !!!! note that both lastTwo and interval might not be two consecutive numbers, so you cannot just use lastTwo[1] === interval[0]
            count += 1;
            lastTwo = [lastTwo[1], interval[1]]; // !!! same reason
        }
        // else, both inside, ignore
    }
    return count;
};

0113

/**
* @param {number[][]} maze
* @param {number[]} start
* @param {number[]} destination
* @return {number}
*/
var shortestDistance = function(maze, start, destination) {
    // let's try the dijkstra's solution, with heap
    class Heap {
        constructor (data, compare) {
            this.data = data || [];
            this.compare = compare || ((a, b) => a - b);
            const lastParent = this.getParent(this.data.length - 1);
            for (let i = lastParent; i >= 0; i--) {
                this.siftDown(i);
            }
        }
        getParent (i) {
            return Math.trunc((i - 1) / 2);
        }
        siftDown (i) {
            let min = i;
            const left = 2 * i + 1;
            const right = 2 * i + 2;
            for (let index of [left, right]) {
                if (index < this.data.length && this.compare(this.data[index], this.data[min]) < 0) {
                    min = index;
                }
            }
            if (i !== min) {
                this.swap(i, min);
                this.siftDown(min);
            }
        }
        swap (i, j) {
            ;[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
        }
        siftUp (i) {
            const parent = this.getParent(i);
            if (this.compare(this.data[i], this.data[parent]) < 0) {
                this.swap(i, parent);
                this.siftUp(parent);
            }
        }
        get size () {
            return this.data.length;
        }
        peak () {
            return this.data[0];
        }
        push (val) {
            this.data.push(val);
            this.siftUp(this.data.length - 1);
        }
        pop () {
            if (this.size === 0) {return undefined}
            const val = this.peak();
            this.swap(0, this.data.length - 1);
            this.data.pop();
            this.siftDown(0)
            return val;
        }
    }
    // put the start into the heap
    // pop one from heap, get all neighbors, update the dist, if smaller than current dist, put into the heap
    // each time you get one from the heap, if it is bigger than current dist, ignore it. Won't have same one, because we only
    // push if current one is smaller than dist. get all its neighbors, update the neibor dist, and put into heap
    // in the end, dist start -> end is what we wanted
    if (maze == null || maze.length === 0) {
        return -1;
    }
    const rowLen = maze.length;
    const colLen = maze[0].length;
    // x, y, dist
    const dist = Array(rowLen).fill().map(() => Array(colLen).fill(Infinity));
    dist[start[0]][start[1]] = 0;
    const heap = new Heap([], (a, b) => a[2] - b[2]);
    heap.push([...start, 0]);
    while (heap.size > 0) {
        let [x, y, aDist] = heap.pop();
        if (aDist > dist[x][y]) {continue}
        const moves = [[0, 1], [0, -1], [-1, 0], [1, 0]];
        for (let [dx, dy] of moves) {
            let newDist = aDist;
            // !!! you must make a copy of x and y, otherwise on each move direction you are changing the original x and y
            let newX = x;
            let newY = y;
            while (newX + dx >= 0 && newX + dx < rowLen && newY + dy >= 0 && newY + dy < colLen && maze[newX + dx][newY + dy] === 0) {
                newX = newX + dx;
                newY = newY + dy;
                newDist++;
            }
            if (newX === destination[0] && newY === destination[1]) {
                return newDist;
            }
            if (newDist < dist[newX][newY]) {
                dist[newX][newY] = newDist;
                heap.push([newX, newY, newDist]);
            }
        }
    }
    const val = dist[destination[0]][destination[1]]; // !!!! pull 2d array el from pair !!!
    return val === Infinity ? -1 : val;
};

0114 The Maze III

/**
* @param {number[][]} maze
* @param {number[]} ball
* @param {number[]} hole
* @return {string}
*/
var findShortestWay = function(maze, ball, hole) {
    // !!! this is a shortest path problem
    // 1. if is unweighted graph, use BFS (in this case just degenerated Dijkstra)
    // 2. if is weighted graph, use Dijkstra,
    // consult the maze II, why BFS has the same complexity as DFS? Because this kind of problems are weighted graph, so you
    // cannot just use BFS to solve it fast. You need to use Dijkstra. Thus using BFS you just brute force search, which is the
    // same as DFS.
    // use dijkistra with pq
   
    // now the challenge is: 1. stop at any time, that's not too difficult,
    // 2. need to get the path. how? need to backtrack since we are not using dfs.
    // need to keep a backtrack map
    // for each node, keep the smallest path to this current node using the prev map.
    // but they don't want the node path, they want the direction path, we could still get it, but is there a way to get it directly? we store the complete path on each node? that is also doable.
    class Heap {
        constructor (data, compare) {
            this.data = data || []
            this.compare = compare || ((a, b) => a - b);
            const lastParent = this.getParent(this.data.length - 1);
            for (let i = lastParent; i >= 0; i--) {
                this.siftDown(i);
            }
        }
        getParent (i) {
            return Math.trunc((i - 1) / 2);
        }
        swap (i, j) {
            ;[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
        }
        siftDown (i) {
            let min = i;
            const left = 2 * i + 1;
            const right = 2 * i + 2;
            for (let index of [left, right]) {
                if (index < this.data.length && this.compare(this.data[index], this.data[min]) < 0) {
                    min = index;
                }
            }
            if (min !== i) {
                this.swap(min, i);
                this.siftDown(min);
            }
        }
        siftUp (i) {
            const parent = this.getParent(i);
            if (this.compare(this.data[i], this.data[parent]) < 0) {
                this.swap(parent, i);
                this.siftUp(parent);
            }
        }
        push (val) {
            this.data.push(val);
            this.siftUp(this.data.length - 1);
        }
        get size () {
            return this.data.length;
        }
        peak () {
            return this.data[0];
        }
        pop () {
            if (this.size === 0) {return undefined}
            const val = this.peak();
            this.swap(0, this.data.length - 1);
            this.data.pop();
            this.siftDown(0);
            return val;
        }
    }
   
    if (maze == null || maze.length === 0) {
        return 'impossible';
    }
    const rowLen = maze.length;
    const colLen = maze[0].length;
    const dist = Array(rowLen).fill().map(() => Array(colLen).fill(Infinity));
    const path = Array(rowLen).fill().map(() => Array(colLen).fill('z')); // !!! init to z for infinity
    dist[ball[0]][ball[1]] = 0;
    path[ball[0]][ball[1]] = '';
    const compare = (dist1, path1, dist2, path2) => {
        if (dist1 === dist2) {
            if (path1 < path2) {
                return -1;
            } else if (path1 > path2) {
                return 1
            } else {
                return 0;
            }
        } else {
            return dist1 - dist2;
        }
    }
    const heap = new Heap([], (a, b) => compare(a[2], a[3], b[2], b[3]));
    heap.push([...ball, 0, '']); // !!! have 4 els now
    while (heap.size > 0) {
        const [x, y, aDist, aPath] = heap.pop();
        if (compare(aDist, aPath, dist[x][y], path[x][y]) > 0) {continue;}
        const moves = [[0, 1, 'r'], [0, -1, 'l'], [1, 0, 'd'], [-1, 0, 'u']];
        for (let [dx, dy, dir] of moves) {
            let newX = x;
            let newY = y;
            let newDist = aDist;
            // !!! all newX + dx, newY + dy
            let found = false;
            while (newX + dx >= 0 && newX + dx < rowLen && newY + dy >= 0 && newY + dy < colLen && maze[newX + dx][newY + dy] === 0) {
                newX += dx;
                newY += dy;
                newDist++;
                // !!!!! cannot just stop here, because you not only need to find it, but you need to find the lexically smallest
                // but you need to test here
                if (newX === hole[0] && newY === hole[1]) {
                    found = true;
                    break;
                }
            }
            // 1. compare the dist; 2. if that equal, compare the path
            const newPath = path[x][y] + dir;
            if (compare(newDist, newPath, dist[newX][newY], path[newX][newY]) < 0) { // !!!newX, newY not x, y in the 2d array !!!!
                // !!! that's because we are comparing with the prev value of same point, not values of this and prev point
                dist[newX][newY] = newDist;
                path[newX][newY] = newPath;
                if (!found) {
                    heap.push([newX, newY, newDist, newPath]);
                }
            }
        }
    }
    const val = path[hole[0]][hole[1]];
    return val === 'z' ? 'impossible' : val;
};

0114  Special Binary String

/**
* @param {string} S
* @return {string}
*/
var makeLargestSpecial = function(S) {
    if (S == null || S.length === 0) {return S}
    const list = [];
    let count = 0;
    let start = 0;
    for (let i = 0; i < S.length; i++) {
        if (S[i] === '1') {
            count++;
        } else {
            count--;
        }
        if (count === 0) {
            list.push('1' + makeLargestSpecial(S.slice(start + 1, i)) + '0');
            start = i + 1;
        }
    }
    return list.sort().reverse().join(''); // !!! this time you did sort, but: they want lexicographically LARGER, not SMALLLER, native is smaller. !!!! Then here is the problem, it is string, not number, so in the comparator you cannot use
    // - directly, but we can use reverse here.
    // but if inside a sort comparator you need to write sort for a string, you have no other options.
};

0114 3. Couples Holding Hands

/**
* @param {number[]} row
* @return {number}
*/
var minSwapsCouples = function(row) {
    if (row == null || row.length === 0) {
        return 0;
    }
    const map = new Map();
    for (let i = 0; i < row.length; i = i + 2) {
        insert(Math.trunc(row[i] / 2), Math.trunc(row[i + 1] / 2));
    }
    return map.size;
   
    function insert (a, b) {
        const min = Math.min(a, b);
        const max = Math.max(a, b);
        if (min != max) {
            if (map.has(min)) {
                insert(map.get(min), max);
            } else {
                map.set(min, max);
            }
        }
    }
};

sicilianee 发表于 2018-1-15 14:09
0114 3. Couples Holding Hands

/**

Though I copied it and run it, still don't totally understand how it works.

Another version using formula: total number of nodes - total number of cycles:

/**
* @param {number[]} row
* @return {number}
*/
var minSwapsCouples = function(row) {
    // count number of cycles (including self cycle), N - # is answer
    const total = row.length / 2;
    const map = new Map();
    let count = 0;
    for (let i = 0; i < row.length; i = i + 2) {
        const a = Math.trunc(row[i] / 2);
        const b = Math.trunc(row[i + 1] / 2);
        let min = Math.min(a, b);
        let max = Math.max(a, b);
        while (map.has(min)) {
            const val = map.get(min); // cut the min node out, until we form a cycle of only one node
            min = Math.min(val, max);
            max = Math.max(val, max);
        }
        if (min === max) {
            count++; // a cycle found, ++
        } else {
            map.set(min, max); // not yet, add the edge
        }
    }
    return total - count;
};

0116 1. Longest Increasing Subsequence

/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    const tail = [];
    for (let num of nums) {
        // binary search the list to find the index to insert
        let left = 0;
        let right = tail.length - 1;
        while (left <= right) { // !!!! shit the equal sign. we are not looking for some value that we are sure is in the array, must put equal here.
            const mid = left + Math.trunc((right - left) / 2);
            const midVal = tail[mid]; // !!! tail[mid], not nums[mid], shit, very prone
            if (midVal < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // use left
        tail[left] = num;
    }
    return tail.length;
};

This one isn't easy to understand. Gotta find another one.

0116 2. Russian Doll Envelopes

/**
* @param {number[][]} envelopes
* @return {number}
*/
var maxEnvelopes = function(envelopes) {
    if (envelopes == null || envelopes.length === 0) {
        return 0;
    }
    envelopes.sort((a, b) => {
        return a[0] === b[0]
            ? b[1] - a[1]
            : a[0] - b[0];
    });
    return findLongestIncreasingSubsequence(envelopes.map(e => e[1])); // envelopes itself is a 2d array not 1d
};


function findLongestIncreasingSubsequence (nums) {
    const tails = [];
    for (let num of nums) {
        let left = 0;
        let right = tails.length - 1;
        while (left <= right) {
            const mid = left + Math.trunc((right - left) / 2);
            const midVal = tails[mid];
            // find the smallest one that is bigger/equal to num
            if (midVal < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        tails[left] = num;
    }
    return tails.length;
}