阿里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);
    }
#阿里笔试2020##笔试题目##Java##阿里巴巴#
全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
点赞
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务