莉莉丝 2021.09.27 笔试

1、任务依赖判断

题目描述

你在设计游戏的任务体系，在完成一项任务前需要先完成一些前置任务。
给定任务总量以及他们的前置任务，请你判断任务依赖是否合理，即是否可能完成所有任务？
共task_count个任务，记为0到task_count-1。
前置任务，想完成任务0，必需先完成任务1，用一个两个数字的list来表示：[0,1]

分析设计

这是一个判断环的问题，应该是可以转换为矩阵来计算的，当时笔试的时候一直往DFS方向想解法，其实可以直接模拟然后暴力破解，先把入度为0的任务放入集合里，然后遍历还未访问过的任务，如果其前置任务都已经出现在集合中，则该任务可以完成，并放入集合中，直到所有任务都已经放入集合中退出并返回true，或者这个过程在一定时间里还没有结束，则退出并返回false。

代码实现

class Solution{
    public boolean can_tasks_finish(int tasks_count, int[][] task_request){
        ArrayList<Integer>[] graph = new ArrayList[tasks_count];
        for(int i = 0; i < tasks_count; ++i){
            graph[i] = new ArrayList<>();
        }
        for(int[] task : task_request){
            graph[task[0]].add(task[1]);
        }
        HashSet<Integer> seen = new HashSet<>();
        for(int i = 0; i < tasks_count; ++i){
            if(graph[i].size() == 0){
                seen.add(i);
            }
        }
        int cnt = 0;
        while(seen.size() < tasks_count && cnt < tasks_count){
            for(int i = 0; i < tasks_count; ++i){
                if(seen.contains(i)){
                    continue;
                }
                boolean flag = true;
                ArrayList<Integer> list = graph[i];
                for(int nei : list){
                    if(!seen.contains(nei)){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    seen.add(i);
                }
            }
            cnt++;
        }
        if(seen.size() == tasks_count){
            return true;
        }
        return false;
    }
}

2、逃出怪物房间

题目描述

给定一个m*n的房间，每个有不定数量的怪物，请找出一条从左上角到右下角的路径，使得整个过程中遇到的怪物的数量最少。
每次只能向右边走或者向下走一格。

分析设计

典型的动态规划问题。
每次向右走或者向下走，考虑最优子结构，对于当前下标[i,j]处的最小值来自其左边的值[i, j - 1]和上边的值[i - 1, j]中的最小值，定义dp[i][j]为当前下标所能取到的最小值，则dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。

代码实现

class Solution{
    public int minMonSum(int[][] grid){
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < m; ++i){
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int i = 1; i < n; ++i){
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}