阿里4.3面试题解答

4.3题目解答
能不能AC不太清楚，没参加4.3的笔试，自己做了一些测试，结果跟网上大佬的代码对比是一样的。
第一题：排序加单调栈，时间复杂度在nlogn，用暴力查找为n2

  //排序加单调栈
    public int LuckyNum(int[] array){
        if(array.length <= 2){
            return 0;
        }
        List list = new ArrayList();
        for(int i = 0; i < array.length; i++){
            list.add(new stack(array[i], i));
        }
        //将list排序，使用的时归并排序，时间复杂度为 nlogn
        list.sort(Comparator.comparingInt(a -> a.num));
        //创建单调栈
        stack[] stacks = new stack[array.length];
        //用来存放左边最小，右边最大的数组
        int[] leftMin = new int[array.length];
        int[] rightMax = new int[array.length];
        //寻找左边最小的数组，此部分为单调递增栈
        int top = 0;
        for (stack vStack : list) {
            //栈为空直接入栈
            if(top == 0){
                stacks[top++] = vStack;
            }
            else{
                //栈不为空
                while(top >= 0){
                    //判断当前的vStack存放数的序号是否小于栈顶的元素，小则说明当前vStack里的值就是所需要的值，始终保持栈内允许的pos递增
                    if(vStack.pos < stacks[top - 1].pos){
                        leftMin[stacks[--top].pos] = vStack.num;
                        //栈为空则直接将当前元素入栈
                        if(top == 0){
                            stacks[top++] = vStack;
                            break;
                        }
                    }
                    else{
                        stacks[top++] = vStack;
                        break;
                    }
                }
            }
        }
        //此时还在栈内的元素，就是没有满足左边有大于它的数，直接填入0
        while(top != 0){
            leftMin[stacks[--top].pos] = 0;
        }
        //寻找右边最大的数组，此部分为单调递减栈，原理同上
        for (int i = list.size() - 1; i >=0; i--) {
            stack vStack = list.get(i);
            if(top == 0){
                stacks[top++] = vStack;
            }
            else{
                while(top > 0){
                    if(vStack.pos > stacks[top - 1].pos){
                        rightMax[stacks[--top].pos] = vStack.num;
                        if(top == 0){
                            stacks[top++] = vStack;
                            break;
                        }
                    }
                    else{
                        stacks[top++] = vStack;
                        break;
                    }
                }
            }
        }
        while(top != 0){
            rightMax[stacks[--top].pos] = 0;
        }
        int count = 0;
        for(int i = 0; i < rightMax.length; i++){
            if(leftMin[i] != 0 && rightMax[i] != 0){
                if(leftMin[i] % rightMax[i] == 0){
                    count++;
                }
            }
        }
        return count;
    }

第二题：dp

    public int minPath(int[][] matrix, int x, int y, int[][] dp, int[][] mark){
        mark[x][y] = 1;
        if(x == matrix.length - 1){
            return matrix[x][y];
        }
        if(dp[x][y] != 0){
            return dp[x][y];
        }
        int ret = Integer.MAX_VALUE;
        if(y + 1 < matrix[0].length && mark[x][y+1] == 0){
            ret = Math.min(ret, minPath(matrix, x, y + 1, dp, mark));
            mark[x][y + 1] = 0;
        }
        if(x + 1 < matrix.length && mark[x+1][y] == 0){
            ret = Math.min(ret, minPath(matrix, x + 1, y, dp, mark));
            mark[x + 1][y] = 0;
        }
        if(y >= 1 && mark[x][y-1] == 0){
            ret = Math.min(ret, minPath(matrix, x, y - 1, dp, mark));
            mark[x][y - 1] = 0;
        }
        return dp[x][y] = ret + matrix[x][y];
    }

    public static void main(String[] args) {
        int[][] matrix = {{3, 1, 3},
                          {3, 1, 3},
                          {3, 1, 3},
                          {1, 10, 2}};
        int[][] dp = new int[4][3];
        int[][] mark = new int[4][3];
        minPath(matrix, 0, 0, dp, mark);
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < dp[0].length; i++){
            min = Math.min(dp[0][i], min);
        }
        System.out.println(min);
    }