记录

1026 3. Verify Preorder Serialization of a Binary Tree

/**
* @param {string} preorder
* @return {boolean}
*/
var isValidSerialization = function(preorder) {
    if (preorder == null || preorder.length === 0) {
        return true;
    }
    const nodes = preorder.split(',');
    let diff = 1;
    for (let node of nodes) {
        diff--;
        if (diff < 0) {
            return false;
        }
        if (node !== '#') {
            diff += 2;
        }
    }
    return diff === 0;
};
// !!!! why is this solution correct?

1026 4. IPO

class Solution {
    class Project {
        int capital;
        int profit;
        Project (int capital, int profit) { // Declare type here!!!  For Java
            this.capital = capital;
            this.profit = profit;
        }
    }
   
    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        if (Profits.length == 0 || Capital.length == 0) {
            return 0;
        }
        PriorityQueue<Project> pq1 = new PriorityQueue<Project>((p1, p2) -> p1.capital - p2.capital);
        PriorityQueue<Project> pq2 = new PriorityQueue<Project>((p1, p2) -> p2.profit - p1.profit);
        for (int i = 0; i < Profits.length; i++) {
            pq1.add(new Project(Capital[i], Profits[i]));
        }
        while (k > 0) {
            while (!pq1.isEmpty() && pq1.peek().capital <= W) {   // !!! it is peek, not top  !!! it is possible that all projects are moved to another q, so need to test for empty!!!
                pq2.add(pq1.remove());
            }
            if (pq2.isEmpty()) {
                break;
            } else {
                Project p = pq2.remove();
                W += p.profit;
                k--;
            }
        }
        return W;
    }
}

1026 5. Factorial Trailing Zeroes

/**
* @param {number} n
* @return {number}
*/
var trailingZeroes = function(n) {
    if (n <= 0) {
        return 0;
    }
    let count = 0;
    while (n != 0) {
        n = Math.floor(n / 5);
        count += n;
    }
    return count;
};

1026 6. Arranging Coins

/**
* @param {number} n
* @return {number}
*/
var arrangeCoins = function(n) {
    if (n === 0) {return 0;}
    const target =  2 * n;
    let x = 1;
    while (x * (x + 1) <= target) {
        x++;
    }
    return x - 1;
};

sicilianee 发表于 2017-10-27 11:41
1026 6. Arranging Coins

/**

可以直接求根公式做

1026 7. Remove Duplicates from Sorted Array II

/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    let count = 1;
    let removeCount = 0;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            count++;
            if (count > 2) {
                removeCount++;
            }
        } else {
            count = 1;
        }
        nums[i - removeCount] = nums[i];
    }
    return nums.length - removeCount;
};

1026 8. Valid Sudoku

/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
    if (board == null || board.length === 0) {
        return false;
    }
    for (let i = 0; i < board.length; i++) {
        if (!isRowValid(board, i)) {return false;}
    }
    console.log('row good')
    for (let j = 0; j < board[0].length; j++) {
        if (!isColValid(board, j)) {return false;}
    }
    console.log('col good')
    for (let i = 0; i < board.length; i += 3) {   // !!!! for a matrix, it is 3, not 9, the length of each segment
        for (let j = 0; j < board[0].length; j += 3) {
            if (!isMatrixValid(board, i, j)) {return false;}
        }
    }
    console.log('all good')
    return true;
};

function isRowValid (board, i) {
    const row = board[i];
    const set = new Set();
    // assume only 1-9
    for (let el of row) {
        if (el != '.' && set.has(el)) {
            return false;
        } else {
            set.add(el);
        }
    }
    return true;
}

function isColValid (board, col) {
    const set = new Set();
    for (let row = 0; row < board.length; row++) {
        if (board[row][col] != '.' && set.has(board[row][col])) {
            return false;
        } else {
            set.add(board[row][col]);
        }
    }
    return true;
}

function isMatrixValid (board, startI, startJ) {
    const set = new Set();
    for (let i = startI; i < startI + 3; i++) {
        for (let j = startJ; j < startJ + 3; j++) {
            if (board[i][j] != '.' && set.has(board[i][j])) {
                return false;
            } else {
                set.add(board[i][j]);
            }
        }
    }
    return true;
}

sicilianee 发表于 2017-10-27 12:09
1026 8. Valid Sudoku

/**

They can do it in one single round: loop all elements and map the index
http://www.cnblogs.com/grandyang/p/4421217.html

1026 9. Super Washing Machines

/**
* @param {number[]} machines
* @return {number}
*/
var findMinMoves = function(machines) {
    if (machines == null || machines.length == 0) {
        return 0;
    }
    const sum = machines.reduce((a, b) => a + b);
    if (sum % machines.length !== 0) {return -1} // !!! return -1, not false
    const avg = sum / machines.length;
    let max = 0;
    let diffSum = 0;
    for (let i = 0; i < machines.length; i++) {
        const diff = machines - avg;
        diffSum += diff;
        max = Math.max(Math.abs(diffSum), diff, max);
    }
    return max;
};

From:
http://www.cnblogs.com/grandyang/p/6648557.html
See the comment

sicilianee 发表于 2017-10-27 12:45
1027 9. Super Washing Machines

/**

为什么一个要加绝对值一个不要加很巧妙
对于正数，要分发出去。虽然可以向两边分发，但是一次只能进行一个，所以找自己多的和自己流量最大值的最大值。
对于负数，要拿回来，可以同时从两边拿，所以找流量的最大值。