首页 > 华为机试8.25ak代码
头像
相依相随
编辑于 2021-08-26 11:17
+ 关注

华为机试8.25ak代码

55分钟ak,九点钟更新代码
------------分割线-----------

第一题

题目大意:
给你一个矩阵,求最大子矩阵和
package nowcoder;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main47 {
    public static void main(String[] args) {
        new Solve47().solve();
    }
}
class Solve47{
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        int m=s.nextInt();
        int n=s.nextInt();
        int[][] martrix=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                martrix[i][j]=s.nextInt();
            }
        }
        int ans=Integer.MIN_VALUE;
        for (int i = 0; i <m ; i++) {
            int[] dp=new int[n];
            for (int j = i; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    dp[k]+=martrix[j][k];
                }
                int[] sum=new int[n];
                int min=0;
                for (int k = 0; k < n; k++) {
                    sum[k]+=dp[k];
                    if (k>0)sum[k]+=sum[k-1];
                    ans=Math.max(ans,sum[k]-min);
                    min=Math.min(min,sum[k]);
                }
//                System.out.println(Arrays.toString(sum));
            }

        }
        System.out.println(ans);
    }
}

第二题

题目大意:
给你一个矩阵代表一个闯关方格,英雄最开始在(0,0)处,移动一次耗费1s,闯关方格上的数字代表着倒计时,每过一秒减一,当减到0时该格子无法通过,求到右下角的最短时间

BFS搜索加剪枝即可
package nowcoder;

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main48 {
    public static void main(String[] args) {
        new Solve48().solve();
    }
}

class Solve48{
    int row,col;
    int[] dx={-1,1,0,0};
    int[] dy={0,0,1,-1};
    private class Node{
        int x;
        int y;
        int hop;

        public Node(int x, int y, int hop) {
            this.x = x;
            this.y = y;
            this.hop = hop;
        }
    }
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        row=s.nextInt();
        col=s.nextInt();
        int[][] grid=new int[row][col];
        for (int i = 0; i <row ; i++) {
            for (int j = 0; j < col; j++) {
                grid[i][j]=s.nextInt();
            }
        }
        System.out.println(getAns(grid));

    }
    private int getAns(int[][] grid){
        if (grid[0][0]<=0){
            return -1;
        }
        int[][] minTime=new int[row][col];
        for (int i = 0; i < row; i++) {
            Arrays.fill(minTime[i],Integer.MAX_VALUE);
        }
        Queue<Node> queue=new LinkedList<>();
        queue.add(new Node(0,0,0));
        while (!queue.isEmpty()){
            Node node=queue.poll();
            int x=node.x;
            int y=node.y;
            int hop=node.hop;
//            System.out.println(x+" "+y+" "+hop);
            if (minTime[x][y]<=hop||grid[x][y]<hop)continue;
            minTime[x][y]=hop;
            if (x==row-1&&y==col-1)return hop;
            for (int i = 0; i < dx.length; i++) {
                int nextX=dx[i]+x;
                int nextY=dy[i]+y;
                if (!inGrid(nextX,nextY))continue;
                queue.add(new Node(nextX,nextY,hop+1));
            }
        }
        return -1;
    }
    private boolean inGrid(int x,int y){
        return x>=0&&x<row&&y>=0&&y<col;
    }
}

第三题

题目大意:给你一系列任务的完成时间及其前置依赖,任务可以并行,求完成所有任务的最短时间
输入:
第一行一个数n代表有n个任务,接下来n行代表每个任务的信息
当没有前置依赖的时候,这一行为-1 t,t代表完成时间
当有前置依赖的时候,前置依赖间用逗号隔开,1,2 t,t代表完成时间
Java split处理字符串yyds
拓扑排序加dp,其中dp[i]代表完成第i个任务需要的时间
package nowcoder;

import java.io.BufferedInputStream;
import java.util.*;

public class Main49 {
    public static void main(String[] args) {
        new Solve49().solve();
    }
}

class Solve49{
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        int n=s.nextInt();
        int[] times=new int[n];
        s.nextLine();
        List<List<Integer>> graph=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            String str=s.nextLine();
            String[] strs=str.split(",");
            for (int j = 0; j <strs.length-1 ; j++) {
                int a=Integer.parseInt(strs[j]);
                graph.get(a).add(i);
            }
            String[] curr=strs[strs.length-1].split(" ");
            if (!curr[0].equals("-1")){
                int a=Integer.parseInt(curr[0]);
                graph.get(a).add(i);
            }
            int t=Integer.parseInt(curr[1]);
            times[i]=t;
        }
        System.out.println(getAns(times,graph,n));
    }
    private int getAns(int[] times,List<List<Integer>> graph,int n){
        int[] in=new int[n];
        for(List<Integer> list:graph){
            for(int i:list)in[i]++;
        }
        Queue<Integer> queue=new LinkedList<>();
        int[] dp=new int[n];
        Arrays.fill(dp,0);
        int cnt=0;
        for (int i = 0; i < n; i++) {
            if (in[i]==0){
                dp[i]=times[i];
                queue.add(i);
            }
        }
        while (!queue.isEmpty()){
            int curr=queue.poll();
            cnt++;
            for(int i:graph.get(curr)){
                in[i]--;
                dp[i]=Math.max(dp[i],dp[curr]+times[i]);
                if (in[i]==0)queue.add(i);
            }
        }
        if (cnt!=n)return -1;
        int ans=0;
        for (int i = 0; i <dp.length ; i++) {
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }

}


全部评论

(43) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐