1252. 奇数值单元格的数目 / 剑指 Offer II 113. 课程顺序

1252. 奇数值单元格的数目【简单题】【每日一题】

思路：【模拟】

定义行数组rows和列数组cols，用来记录当前行的+1次数和当前列的+1次数，遍历indices数组用来给rows和cols赋值。
定义奇数值单元格数目为ans，初值为0。
那么遍历矩阵每个位置，如果当前行和当前列的+1次数和是奇数，则ans+1

代码：

class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int ans = 0;
        int[] rows = new int[m],cols = new int[n];
        for (int[] index : indices) {
            rows[index[0]]++;
            cols[index[1]]++;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((rows[i] + cols[j]) % 2 != 0){
                    ans++;
                }
            }
        }
        return ans;
    }
}

剑指 Offer II 113. 课程顺序【中等题】

思路：【拓扑排序+BFS】【注释官方题解】

对每门课和选这门课前的必修课之前的关系建图。
记录每门课的入度，即选择当前这门课前的必须课数目。

将所有入度为0的课程节点加入队列，每次BFS搜索取出队首节点，将当前队首节点加入可选路线，然后根据拓扑关系遍历当前队首节点的后置节点，将后置节点入度减1，之后如果后置节点入度为0的话，将后置节点加入可选队列。

当可选队列为空时，搜索结束，此时如果课程修满了，则返回可选的课程路线，否则说明不可能完成所有课程，返回空数组。

代码：

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //存储有向图
        List> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        //存储每个节点的入度，入度表示某个节点前必须要有的节点个数
        int[] indeg = new int[numCourses];
        //存储答案
        int[] result = new int[numCourses];
        //答案下标
        int index = 0;
        for (int[] prerequisite : prerequisites) {
            //记 prerequisite[0] 为 want，prerequisite[1] 为 need
            //拓扑排序，need在want之前，因此 need列表后追加 want
            edges.get(prerequisite[1]).add(prerequisite[0]);
            //记录want节点的入度，即want节点前的need节点数+1
            indeg[prerequisite[0]]++;
        }

        Queue queue = new LinkedList<>();
        //将所有入度为0的节点放入队列中
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0){
                queue.offer(i);
            }
        }

        //开启BFS搜索,由于queue队列表示的是可以进行学习的队列，因此当队列为空时，说明所有可学习的课程均已被学习
        while (!queue.isEmpty()){
            //取出队首节点
            int u = queue.poll();
            //节点u入度为0，表示选这个节点不需要前置条件，因此可将节点u加入答案数组
            result[index++] = u;
            //遍历节点u可以指向的所有节点，即学习了节点u之后可以学习哪些节点
            for (Integer v : edges.get(u)) {
                //将节点v的入度减1，表示学习v节点前必须要学习的节点已经少了一个（u节点已被学习）
                indeg[v]--;
                //如果此时节点v的入度为0，说明节点v可以准备学习了，将其加入可学习队列
                if (indeg[v] == 0){
                    queue.offer(v);
                }
                //如果节点v的入度不为0，说明要学习节点v，除了节点u之外，还有其他节点需要学习，因此不能将节点v加入可学习队列
            }
        }
        //如果此时待学习的课程下标刚好等于 numCourse，说明这 numCourse 门课均已被学习完毕，返回学习路线result即可
        //否则，说明不可能完成所有课程，此时根据题意需要返回一个空数组
        return index == numCourses ? result : new int[0];
    }
}