[数据结构与算法]蓝桥杯31天冲刺 Day7

相乘

链接: 相乘.

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

public class 相乘 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        long 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 stub
		long 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);
            }
        }
        //辅助指针，用来将数据放入res
        int 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;

    }
}

题解

题解明天更~~（狗头