755. Pour Water

755. Pour Water

Medium

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After Vunits of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

If the droplet would eventually fall by moving left, then move left.

Otherwise, if the droplet would eventually fall by moving right, then move right.

Otherwise, rise at it's current position.

Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, "level" means the height of the terrain plus any water in that column.

We can assume there's infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.

Example 1:

Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
#       #
#       #
##  # ###
#########
 0123456    <- index

The first drop of water lands at index K = 3:

#       #
#   w   #
##  # ###
#########
 0123456    

When moving left or right, the water can only move to the same level or a lower level.
(By level, we mean the total height of the terrain plus any water in that column.)
Since moving left will eventually make it fall, it moves left.
(A droplet "made to fall" means go to a lower height than it was at previously.)

#       #
#       #
## w# ###
#########
 0123456    

Since moving left will not make it fall, it stays in place.  The next droplet falls:

#       #
#   w   #
## w# ###
#########
 0123456  

Since the new droplet moving left will eventually make it fall, it moves left.
Notice that the droplet still preferred to move left,
even though it could move right (and moving right makes it fall quicker.)

#       #
#  w    #
## w# ###
#########
 0123456  

#       #
#       #
##ww# ###
#########
 0123456  

After those steps, the third droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would eventually make it fall, it moves right.

#       #
#   w   #
##ww# ###
#########
 0123456  

#       #
#       #
##ww#w###
#########
 0123456  

Finally, the fourth droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would not eventually make it fall, it stays in place:

#       #
#   w   #
##ww#w###
#########
 0123456  

The final answer is [2,2,2,3,2,2,2]:

    #    
 ####### 
 ####### 
 0123456 

Example 2:

Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.

Example 3:

Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]

Note:

1. heights will have length in [1, 100] and contain integers in [0, 99].
2. V will be in range [0, 2000].
3. K will be in range [0, heights.length - 1].

---------------------
暴解
O(m * n), heights的长度 ＊ 水滴个个数

class Solution {
    public int[] pourWater(int[] heights, int water, int pos) {
        
        while (water > 0) {
            water--;
            int left = pos;
            
            while (left > 0 && heights[left - 1] <= heights[left]) {
                left--;
            }
            
            if (heights[left] < heights[pos]) {
                heights[left]++;
                continue;
            }
            
            int right = pos;
            while (right < heights.length - 1 && heights[right + 1] <= heights[right]) {
                right++;
            }
            
            if (heights[right] < heights[pos]) {
                heights[right]++;
            }else {
                heights[pos]++;
            }            
        }
        
        return heights;
    }
}

Airbnb

airbnb_2017_fall

-------------------------
倒水

往一个int array 代表海拔的格子里倒水，打印出倒水后的

int[] 海拔， int 水数量， int

倒得位置。

Example:
int[] 海拔 {5,4,2,1,2,3,2,1,0,1,2,4}
水数量8， 倒在位置5

比较开放的题，一些条件要跟面试官探讨，比如左边还是右边优先。

例子：

handle the water drop by drop。 there are infinitely high walls on the left and right 

水先向左走，走到不能走。call it leftMost 

如果leftmost的水比开始点低，leftMost水+1，done 

如果leftmost的水不比开始点低，水向右走，走到不能走，call it rightMost 

如果rightmost的水比开始点低，rightMost水+1，done 

如果rightmost的水不比开始点低，leftMost水+1，done

public static void main(String[] ss) {
        int[] a = {5,4,2,1,2,3,2,1,0,1,2,4};
        fillWater(a, 5,8);

        for (int i : a) {
            System.out.println(i);
        }
    }

    public static void fillWater(int[] land, int pos, int water) {

        while (water > 0) {
            int left = pos;
            while (left > 0 && land[left - 1] <= land[left]) {
                left--;
            }

            if (land[left] < land[pos]) {
                land[left]++;
                water--;
                continue;
            }

            int right = pos;
            while (right < land.length - 1 && land[right + 1] <= land[right]) {
                right++;
            }

            if (land[right] < land[pos]) {
                land[right]++;
            }else {
                land[left]++;
            }

            water--;
        }
    }

另一个变种是把最终的图形（墙跟水）都打印出来

-----------------------------
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=273149

题目是给你公式，比如偶数的话除2，奇数的话就变成3*n+1，对于任何一个正数，数学猜想是最终他会变成1。每变一步步数加1，给一个上限，让找出范围内最长步数。
第一题是这样的：比如7，变换到1是如下顺序：7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1, 总共需要17步。

很直接， 没什么好说的。用一个map减少重复计算

public static void main(String[] ss) {
//        int[] a = {5,4,2,1,2,3,2,1,0,1,2,4};

        System.out.println(findLongestSteps(7));
    }

    private static int findLongestSteps(int num) {
        Map<Integer, Integer> map = new HashMap<>();

        int longest = 0;

        for (int i = 1; i <= num; i++) {
            longest = Math.max(findSteps(i, map), longest);
        }

        return longest;
    }

    private static int findSteps(int num, Map<Integer, Integer> map) {
        if (num <= 1) return 0;

        if (map.containsKey(num)) return map.get(num);

        int rt = 0;
        if (num % 2 == 1) rt = findSteps(3 * num + 1, map);
        else rt = findSteps(num / 2, map);

        rt++;
        map.put(num, rt);
        return rt;
    }

----------------------------------------------------
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=279191

Design a Queue with arrayList, 但是有限制条件, arraylist的长度最多为10, queue不限制长度。纠结了很久不知道怎么做，是不是先把max size设置成10，然后发现overflow了在扩大成10个arraylist，以此类推到100, 1000... 但是这样的话，queue的remove操作要从头开始，好像记录起来比较麻烦。求大家讨论！

用linked list来做，每个node包含一个list，长度不能超过定值

class MyQueue {

    private Node head;
    private Node tail;
    private int indexHead;
    private int indexTail;

    public MyQueue() {
        head = new Node();
        tail = head;
        indexHead = 0;
        indexTail = 0;
    }

    public int pop() {
        int rt = head.list.get(indexHead);
        indexHead++;

        if (indexHead == 5) {
            head = head.next;
            indexHead = 0;
        }

        return rt;
    }

    public int peek() {
        return head.list.get(indexHead);
    }

    public void push(int val) {
        tail.list.add(val);
        indexTail++;
        if (indexTail == 5) {
            tail.next = new Node();
            tail = tail.next;
            indexTail = 0;
        }
    }
}

----------------------------------------------------



----------------------------------------------------



----------------------------------------------------