华为机试

第一题
面试题 17.24. 最大子矩阵题目

package HuaWei;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            int[][] array = new int[m][n];
            for(int i = 0;i<m;i++){
                for(int j = 0;j<n;j++){
                    array[i][j] = scanner.nextInt();
                }
            }
            System.out.println(getMaxs(array));
        }
    }

    private static int getMaxs(int[][] array) {
        int m = array.length;
        int n = array[0].length;
        int max= array[0][0];
        int[][] preSums = new int[m+1][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                preSums[i+1][j] = preSums[i][j] + array[i][j];
            }
        }
        for(int t = 0;t<m;t++){
            for(int b = t;b<m;b++){
                int[] temp = new int[n];
                for(int i = 0;i<n;i++){
                    temp[i] = preSums[b+1][i] - preSums[t][i];
                }
                int sum = temp[0];
                for(int i = 1;i<n;i++){
                    if(sum > 0){
                        sum = sum + temp[i];
                    }else{
                        sum = temp[i];
                    }
                    if(sum > max){
                        max = sum;
                    }
                }
            }
        }
        return max;
    }
}

第二题：
在大小为row*col的方格区域地图上，处处暗藏杀机，地图上每一个格子均有一个倒计时转置，当时间变为0时会触发机关，使得该格子区域变为一处死地，该区域无法通过，英雄每移动一个格子消耗1s。英雄可以上下左右四个方向移动，请设置一条最佳路线，让英雄最短时间从[0,0]到达[row-1,col-1]离开。
注意：英雄在出生点和出口时，该区域不能为死地。

输入
首行输入单个空格分隔的两个正整数row和col，row代表行数（0<row<=15），col代表列数（0<col<=15）接下来row行，每一行包含col个以当个空格分隔的数字，代表对应时间的区域倒计时装置设定时间time，单位为秒（0<=time<=100）

输出
英雄从起点到终点的最短用时，若无法到达，则输出-1
样例
输入

输出
4

输入

输出
-1

思路：刚开始是想dfs，但是超时；只能bfs啊

package HuaWei;

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

public class Test1 {
    static int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()){
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            int[][] arr = new int[m][n];
            for(int i = 0;i<m;i++){
                for(int j = 0;j<n;j++){
                    arr[i][j] = scanner.nextInt();
                }
            }
            int bf = bfs(arr);
            System.out.println(bf);
        }
    }

    private static int bfs(int[][] arr) {
        int m = arr.length;
        int n = arr[0].length;
        int[][] minTime = new int[m][n];
        for(int i = 0;i<m;i++){
            Arrays.fill(minTime[i],Integer.MAX_VALUE);
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0,0,0));
        while(!queue.isEmpty()){
            Node node = queue.poll();
            int x = node.x;
            int y = node.y;
            int count = node.count;

            if(minTime[x][y] <= count || arr[x][y] < count){
                continue;
            }
            if(x == arr.length-1 && y == arr[0].length-1){
                return count;
            }
            minTime[x][y] = count;
            for(int[] dir : dirs){
                int newX= x + dir[0];
                int newY= y + dir[1];
                if(!valid(arr,newX,newY)){
                    continue;
                }
                queue.offer(new Node(newX,newY,count+1));
            }
        }
        return -1;
    }

    private static boolean valid(int[][] arr,int newX, int newY) {
        if(newX < 0 || newY < 0 || newX >= arr.length || newY >= arr[0].length){
            return false;
        }
        return true;
    }
}

class Node{
    int x;
    int y;
    int count;

    public Node(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}

第三题
在一个任务调度系统中,需要调度执行一系列的任务,任务之间存在依赖关系,如任务A依赖任务B，则任务A必须在任务B完成后才能开始启动执行。
现在给出n个任务的依赖关系与执行时间,n<=10000,请计算这n个任务执行完成所需要的时间(假设计算资源充足，允许任意多的任务并行执行)，如果任务存在循环依赖则输出-1
输入描述:
第一行输入任务个数n，正整数数字
第二行开始为n个任务的信息,任务信息分为两部分，第一部分是所依赖的任务工ID(整形，索引顺序，从)开始)，第二部分为计算所需时间（正整数)。两都分以空格分隔

华为机试

全站热榜