用友 笔试 09.09 easy题

题目有点简单

第一题 兔子生宝贝

兔子第3个月开始，每个月都会产下一个兔子，问第 i 月的兔子数。简单dp。

例子：
1 - 1，2 - 1， 3 - 2， 4 - 3， 5 - 5.

// 迭代关系如下，可以不用数组
tmp[0] = arr[1]+arr[2]; // 刚出生的，第1个月
tmp[1] = arr[0]; // 第2个月
tmp[2] = arr[1]+arr[2]; // 第3~n个月

return arr[0]+arr[1]+arr[2];

第二题 连续的最大岛屿面积

补一个输入

Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
    list.add(sc.next());
}
int n = list.size();
int m = list.get(0).split(",").length;

第三题 能看到楼顶的个数

给定楼高，[50, 20, 80, 30, 27, 57]，判断在位置 i 能够看到的楼顶的个数。例如，站在 80 的位置，能看到左侧 50，20，自己 80，右侧 30，57 共 5 个楼的楼顶。

竟然题目还提示使用栈，栈顶元素最小。没见过这么好心的公司。

    public int[] findBuilding (int[] heights) {
        // write code here
        LinkedList<Integer> stack = new LinkedList<>();
        int n = heights.length;
        int ret[] = new int[n];
        for(int i = n-1; i>=0; i--){
            if(stack.isEmpty()){
                ret[i] = 1; // 1是把自己这层楼带上
            }else{
                ret[i] = stack.size()+1; // 1是把自己这层楼带上
            }
            while(!stack.isEmpty() && stack.peekLast() <= heights[i]){
                stack.pollLast();
            }
            stack.offerLast(heights[i]);
        }
        stack = new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(!stack.isEmpty()){
                ret[i] += stack.size();
            }
            while(!stack.isEmpty() && stack.peekLast() <= heights[i]){
                stack.pollLast();
            }
            stack.offerLast(heights[i]);
        }
        return ret;
    }