3.20刷题--备赛ing

距离十五届蓝桥杯还有23天，奶奶的拼了。备赛ing

今天刷题 5道

有序分数递归方法

如何1/2 2/4都是相同的结果，但是需要的是1/2，如何解决这个问题呢，可以看出分子和分母约分最简的时候，他们的gcd==1，所以求出gcd即可。

对于从小到大需要进行排序，可以用一个Node节点来存储这些结果，node节点分为三个值，分子，分母，和对应的分子除以分母得到的结果，这个是doule类型的。
实现comparable接口进行排序。
添加进集合的条件就是如果i<=j，并且最大公约数等于1.就添加进去集合中，然后对集合进行排序，最后遍历集合即可。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        //最后还需要按照大小进行排序的
        List<Node> list=new ArrayList<>();
        for (int i = 0; i <=n; i++) {
            for (int j = i; j <=n ; j++) {
                if (i<=j&&gcd(i,j)==1){
                    double res=1.0*i/j;
                    Node node=new Node(i,j,res);
                    list.add(node);
                }
            }
        }
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            Node node=list.get(i);
            System.out.println(node.x+"/"+node.y);
        }
    }
    public static  int gcd(int x,int y){ //x小 y大
        if (x==0){
            return y;
        }
        //时间复杂度要低一些
        return  gcd(y%x,x);
    }
    static class Node implements Comparable<Node>{
        int x,y;
        double res;

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

        @Override
        public int compareTo(Node o) {
            double  re=this.res-o.res;
            if (re>0){
                return  1;
            }else if (re<0){
                return -1;
            }else{
                return 0;
            }
        }
    }
}

海洋变暖，需要溶解对应的陆地，采用bfs遍历，如果当前是四周只要有海洋，那么陆地就会被溶解。这个可以这样计算，遇到一个岛屿，计算这个岛屿有多少块陆地，和被溶解了多少块陆地，如果两个相等，说明了这个岛屿就全被溶解了，结果就需要++。如果不等，说明有一个陆地是没有被溶解的。

BFS采用优先队列的形式。

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static  int n;
    static Scanner scanner=new Scanner(System.in);
    static  int dirs[][]={{0,1},{1,0},{-1,0},{0,-1}}; //方向
    static  char a[][];
    static  boolean visited[][];
    public static void main(String[] args) {
         n=scanner.nextInt();
         a=new char[n][n];
         visited=new boolean[n][n];
        for (int i = 0; i <n; i++) {
           a[i]=scanner.next().toCharArray();
        }
        int cnt=0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
              if (a[i][j]=='#'&&visited[i][j]==false){
                  if (bfs(i,j)==true){
                      cnt++;
                  }
              }
            }
        }
        System.out.println(cnt);

     }
     public static boolean bfs(int x,int y){
         PriorityQueue<Node>queue=new PriorityQueue<>();
         queue.add(new Node(x,y));
         visited[x][y]=true;//表示研究访问过了
         int total = 0;//当前位置连通陆地的数量
         int bound = 0;//被淹没陆地的数量
         while (!queue.isEmpty()){
             Node cur=queue.poll();
             total++; boolean is_bound = false;
             for (int i = 0; i < dirs.length; i++) {
                 int newx=cur.x+dirs[i][0];
                 int newy=cur.y+dirs[i][1];
                 if (newx<0||newx>=n||newy<0||newy>n){
                     continue;
                 }
                 if (visited[newx][newy]==true){
                     continue;
                 }
                 if (a[newx][newy]=='.'){
                     is_bound=true; //如果时海洋 淹没了
                     continue;
                 }
                 queue.add(new Node(newx,newy));
                 visited[newx][newy]=true;
             }if(is_bound){
                 bound++;
             }
         }
         return total==bound;
     }
     static  class  Node implements Comparable<Node>{
         int x,y;

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

         @Override
         public int compareTo(Node o) {
             return 0;
         }
     }
}

模拟散列表，实现插入和查询操作。

散列表的底层是链表＋数组。