记录

1025 3. Populating Next Right Pointers in Each Node

/**
* Definition for binary tree with next pointer.
* function TreeLinkNode(val) {
*     this.val = val;
*     this.left = this.right = this.next = null;
* }
*/

/**
* @param {TreeLinkNode} root
* @return {void} Do not return anything, modify tree in-place instead.
*/
var connect = function(root) {
    if (root == null) {
        return;
    }
    const q = [root];
    while (q.length > 0) {
        const level = [];
        const size = q.length;
        for (let i = 0; i < size; i++) {
            const node = q.shift();
            const next = q.length > 0 ? q[q.length - 1] : null;
            node.next = next;
            if (node.left != null) {level.push(node.left)}
            if (node.right != null) {level.push(node.right)}
        }
        q.push(...level);
    }
};

1025 4. Longest Absolute File Path

/**
* @param {string} input
* @return {number}
*/
var lengthLongestPath = function(input) {
    if (input == null || input.length === 0) {
        return 0;
    }
    const list = input.split('\n');
    const map = new Map([[0, 0]]);
    let max = 0;
    for (let item of list) {
        let level = 0;
        for (let i = 0; i < item.length; i++) {
            if (item[i] === '\t') {
                level++;
            } else {
                break;
            }
        }
        item = item.slice(level);
        if (item.includes('.')) {
            const levelLen = map.get(level);
            max = Math.max(max, levelLen + item.length);
        } else {
            // !!!! note the folder level has one shift
            map.set(level + 1, map.get(level) + item.length + 1); // !!!!  1. a folder doesn't always end with /n, 2. read the problem, if there is no file in the folder, return 0.  --- so we don't need to update max if it is a folder
        }
    }
    return max;
};

1025 5.  Container With Most Water

/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
    if (height == null || height.length < 2) {
        return 0;
    }
    let left = 0;
    let right = height.length - 1;
    let max = 0;
    while (left < right) {
        const current = Math.min(height[left], height[right]) * (right - left);
        max = Math.max(max, current);
        if (height[left] <= height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max;
};

1025 6.  K Empty Slots

class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        if (flowers == null || flowers.length == 0) {
            return -1;
        }
        TreeSet<Integer> set = new TreeSet();
        for (int i = 0; i < flowers.length; i++) {
            int flower = flowers[i];
            set.add(flower);
            Integer lower = set.lower(flower);
            Integer higher = set.higher(flower);
            if (lower != null && flower - lower - 1 == k || higher != null && higher - flower - 1 == k) { // !!!! need to subtract one more, both sides exclusive
                return i + 1; // !!!! this is weird, they start at day 1. so flower[i] means day i + 1
            }
        }
        return -1;
    }
}

sicilianee 发表于 2017-10-26 13:36
1025 6.  K Empty Slots

class Solution {

So many different solutions. Need to check them out.

next 4:
Longest Increasing Path in a Matrix
Permutation in String   
Number of Segments in a String   
Redundant Connection   

1025 7. Longest Increasing Path in a Matrix

/**
* @param {number[][]} matrix
* @return {number}
*/
var longestIncreasingPath = function(matrix) {
        if (matrix == null || matrix.length === 0 || matrix[0].length === 0) {
            return 0;
        }
        // put the whole matrix into a list
        const list = [];
        let rowLen = matrix.length;
        let colLen = matrix[0].length;
        for (let i = 0; i < rowLen; i++) {
            for (let j = 0; j < colLen; j++) {
                list.push({i, j, value: matrix[i][j]});
            }
        }
        list.sort((item1, item2) => item1.value - item2.value);
        const dp = Array(rowLen).fill().map(() => Array(colLen).fill(1));
        const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        let max = 1;
        for (let item of list) {
            for (let move of moves) {
                const row = item.i + move[0];
                const col = item.j + move[1];
                if (row >= 0 && row < rowLen && col >= 0 && col < colLen && item.value > matrix[row][col]) {
                    dp[item.i][item.j] = Math.max(dp[item.i][item.j], dp[row][col] + 1);
                    max = Math.max(max, dp[item.i][item.j]);
                }
            }
        }
        return max;
};

1025 8. Permutation in String

/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var checkInclusion = function(s1, s2) {
        if (s1 == '') {return true}
        const dict = {};
        [...s1].forEach(c => {
            dict[c] = dict[c] || 0;
            dict[c]++;
        });
        let left = -1;
        let right = 0;
        while (right < s2.length) {
            dict[s2[right]] = dict[s2[right]] || 0;
            dict[s2[right]]--;
            if (dict[s2[right]] < 0) {
                while (dict[s2[right]] < 0) {
                    left++;
                    dict[s2[left]]++;  // !!!! here you are adding it back, it is ++, not --
                }
            } else if (dict[s2[right]] === 0 && right - left === s1.length) {
                return true;
            }
            right++;
        }
        return false;
};

1026 1. Number of Segments in a String

/**
* @param {string} s
* @return {number}
*/
var countSegments = function(s) {
    return s.split(' ').filter(str => str).length;
};

1026 2. Redundant Connection

/**
* @param {number[][]} edges
* @return {number[]}
*/
var findRedundantConnection = function(edges) {
    if (edges == null || edges.length === 0) {
        return null;
    }
    const path = [];
    for (let [a, b] of edges) {
        const aNext = find(path, a);
        const bNext = find(path, b);
        if (aNext === bNext) {
            return [a, b];
        } else {
            path[aNext] = bNext;
        }
    }
    return null
};

function find (path, i) {
    while (path[i] != null) {
        i = path[i]
    }
    return i;
}