蓝桥杯31天冲刺 Day7

相乘

链接: 相乘.

题目很简单，直接枚举就好

public class 相乘 {
    public static void main(String[] args) {
    // TODO Auto-generated method stublong x = 2L;long n = 1000000007L;boolean flag = true;while(flag) {
    if(x*2021%n == 999999999) {
    System.out.println(x);flag = false;}x++;}}}

空间

链接: 空间.

根据上述的单位换算就可以很好地解决这一问题了

import java.util.*;
public class 空间 {
    public static void main(String[] args) {
    // TODO Auto-generated method stublong bit =0L;bit=(long) (256*Math.pow(2, 10)*Math.pow(2, 10)*Math.pow(2, 3));long res = bit/32;System.out.println(res)}}

发现环

拓扑排序

在解决这道题之前，要先弄清拓扑排序的原理和实现方法，这里，我拿 力扣210. 课程表 II这题举例

拓扑排序可以有效地根据先后顺序，来对有向图进行排序。还有很重要的一点是：它可以有效判断图中是否有环存在
先简单说一下拓扑排序的思路吧

如下，是一个有向图

拓扑排序大致思路就是：找到入度为0的结点，再去掉它对应出度的箭头。
如上图，就是先找一个入度为0的结点，也就是4，再去掉它出度对应的一条边：

此时我们可以看到，找不出来入度为0的结点了，也就证明：图中有环

相反，如果一直这样进行下去，一直能找到入度为0的结点，也就证明图中没有环

依照这个原理，我们可以进行具体的代码实现了

选用的数据结构
怎样实现重复查找入度为0的结点呢？

解决这一问题使用while循环+队列的方式就再合适不过了
方法与层序遍历二叉树的方法相似

实现过程
代码实现，详细的思路已经注释出来了：

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
    //返回的结果int[] res = new int[numCourses];//存储对应课程的出度指向的课程List<Integer>[] beforeCorses = new List[numCourses];for(int i =0;i<numCourses;i++){
    beforeCorses[i] = new ArrayList<>();}//记录入度int[] cnt = new int[numCourses];//遍历给出的数据，记下每个元素的入度和对应的出度for(int[] a : prerequisites){
    int after = a[0];int before = a[1];beforeCorses[before].add(after);cnt[after]++;}//创建拓扑排序的队列Queue<Integer> queue = new LinkedList<>();//找出入度为0的元素并入队for(int i =0;i<numCourses;i++){
    if(cnt[i]==0){
    queue.offer(i);}}//辅助指针，用来将数据放入resint index = 0;//开始循环进行拓扑排序while(!queue.isEmpty()){
    int i=queue.poll();res[index] = i;index++;for(int l : beforeCorses[i]){
    cnt[l]--;if(cnt[l] == 0)queue.offer(l);}}if(numCourses!=index){
    return new int[0];}return res;}
}

题解

题解明天更~~（狗头