记录

1019 3. Maximum Average Subarray I

/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function(nums, k) {
    if (nums == null || nums.length === 0) {
        return 0;
    }
    let curr = 0;
    for (let i = 0; i < k; i++) {
        curr += nums[i];
    }
    let max = curr;
    for (let i = k; i < nums.length; i++) {
        curr = curr + nums[i] - nums[i - k];
        max = Math.max(max, curr);
    }
    return max / k;
};

1019 4.  Zuma Game

/**
* @param {string} board
* @param {string} hand
* @return {number}
*/
var findMinStep = function(board, hand) {
    // build a map from the hand
    // for each continuous board char, if you can remove, remove it and update the map, recurse
    // backtrack, change map, loop to the next one
    const map = new Map();
    for (let c of hand) {
        const count = map.has(c) ? map.get(c) + 1 : 1;
        map.set(c, count);
    }
    let min = Infinity;
    recurse(board, 0);
    return min === Infinity ? -1 : min;
   
    function recurse (board, step) {
        let count = 0;
        for (let i = 0; i <= board.length; i++) {
            if (i === 0 || (i < board.length && board[i] === board[i - 1])) {
                count++;
            } else {
                const c = board[i - 1];
                const need = 3 - count;
                if (map.get(c) >= need) {
                    map.set(c, map.get(c) - need);
                    const res = removeThree(board.slice(0, i - count) + board.slice(i))
                    if (!res) {
                        min = Math.min(min, need + step);
                    } else {
                        recurse(res, step + need);
                    }
                    map.set(c, map.get(c) + need);
                }
                count = 1;
            }
        }
    }
   
    function removeThree (board) {
        let count = 0;
        // two ways to solve the last iteration of group inside loop problem
        // 1. do the group operation at every iteration
        // 2. add one more iteration, like nums.length, and test for this last iteration, only do group operation, don't do single operation on it.
        // this is for when the group operation won't operate on single element.
        for (let i = 0; i <= board.length; i++) {
            if (i === 0 || (i < board.length && board[i] === board[i - 1])) {
                count++;
            } else {
                if (count >= 3) {
                    return removeThree(board.slice(0, i - count) + board.slice(i));
                }
                count = 1;
            }
        }
        return board;
    }
};

今天心里很烦啊……不顺

next:
Find Minimum in Rotated Sorted Array II   
Trapping Rain Water II   
Perfect Squares   
Pascal's Triangle II

Let's do the easy ones first

1020 1. Pascal's Triangle II

/**
* @param {number} rowIndex
* @return {number[]}
*/
var getRow = function(rowIndex) {
    let list = [1];
    for (let i = 1; i <= rowIndex; i++) {
        const newList = [];
        for (let j = 0; j <= i; j++) {
            const left = j === 0 ? 0 : list[j - 1];
            const right = j === i ? 0 : list[j];
            newList[j] = left + right;
        }
        list = newList;
    }
    return list;
};

1020 2.  Perfect Squares

/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
    const dp = Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 1; i + j * j <= n; j++) {
            dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1); // !!!! min, not max, need to think!!!
        }
    }
    return dp[n];
};

The code itself is simple. But need to prove it's correct.
This is the first kind of dp, where when you use dp[i], you need to make sure it is already calculated.
Proof:
dp[1] is calculated.
Assume i - 1 is calculated:
j will first reach 1, so when you are in i - 1, you i - 1 + j * j === i, so you will have initialized i. And i must be broken down into nums smaller than it. When you reached i, you already looped through all nums smaller than i. So the min of dp[i] is already found. Thus you can use dp[i].

1020 3. Find Minimum in Rotated Sorted Array II

/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
    if (nums == null || nums.length === 0) {
        return null;
    }
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        if (nums[left] < nums[right]) {
            return nums[left];
        }
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[left]) {
            left = mid + 1;
        } else if (nums[mid] < nums[left]) {
            right = mid; // !!!!! could be itself if it is less than left
        } else {
            left++;
        }
    }
    return nums[left]; // !!! not the index, but the element !!!!
};


1. when you do mid + 1 or mid - 1, be careful whether it could be mid it self
2. left++ could eventually change the assumption for this specific problem

sicilianee 发表于 2017-10-20 13:48
1020 3. Find Minimum in Rotated Sorted Array II

/**

You could change right instead of changing left: would make it simpler:

http://bangbingsyb.blogspot.com/ ... rotated-sorted.html

But notice the notes:
https://www.jiuzhang.com/solutio ... ed-sorted-array-ii/

sicilianee 发表于 2017-10-20 13:48
1020 3. Find Minimum in Rotated Sorted Array II

/**

You could change right instead of changing left: would make it simpler:

http://bangbingsyb.blogspot.com/ ... rotated-sorted.html

But notice the notes:
https://www.jiuzhang.com/solutio ... ed-sorted-array-ii/

1020 4. Trapping Rain Water II

class Solution {
    class Node {
        int row;
        int col;
        int height;
        Node (int row, int col, int height) {
            this.row = row;
            this.col = col;
            this.height = height;
        }
    }
   
    public int trapRainWater(int[][] heightMap) {
        if (heightMap.length == 0 || heightMap[0].length == 0) {return 0;}
        int rowLen = heightMap.length;
        int colLen = heightMap[0].length;
        int[][] moves = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean[][] visited = new boolean[rowLen][colLen];
        PriorityQueue<Node> pq = new PriorityQueue<Node>((node1, node2) -> node1.height - node2.height);
        // !!!! you are only putting the four corners, not four boundaries !!!!!
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (i == 0 || i == rowLen - 1 || j == 0 || j == colLen - 1) {
                    visited[i][j] = true;
                    pq.add(new Node(i, j, heightMap[i][j]));
                }
            }
        }
        int sum = 0;
        while (!pq.isEmpty()) {
            int size = pq.size();
            for (int i = 0; i < size; i++) {
                Node node = pq.remove();
                for (int j = 0; j < moves.length; j++) {
                    int row = node.row + moves[j][0];
                    int col = node.col + moves[j][1];
                    if (row >= 0 && row < rowLen && col >= 0 && col < colLen && !visited[row][col]) {
                        visited[row][col] = true;
                        if (heightMap[row][col] < node.height) {
                            sum += node.height - heightMap[row][col];
                        }
                        pq.add(new Node(row, col, Math.max(node.height, heightMap[row][col])));   // !!!! get the bigger one
                    }
                }
            }
        }
        return sum;
    }
}

ffffffff!!!!

1. need to think through this problem again
2. how does this work?
http://bookshadow.com/weblog/2016/09/25/leetcode-trapping-rain-water-ii/
Without priorityQueue