蓝桥杯算法记录

算法记录

因为最近快到蓝桥杯了 所以跟练了几道题 今天就来记录一下

信号覆盖

信号覆盖

解题思路：这题将输入的x,y的进行储存 然后将每个点用check方法进行检测

int t1=x-X[i];
 int t2=y-Y[i];
 //用这个进行判断
 t1*t1+t2*t2<=r*r

答案

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main { static int[] X = new int[101];
  static int[] Y = new int[101];
  static int n = 0;
  static int r = 0;
  public static void main(String[] args) { Scanner scan = new Scanner(System.in);
    int w = scan.nextInt();
    int h = scan.nextInt();
    n = scan.nextInt();
    r = scan.nextInt();
    for (int i = 0; i < n; i++) { X[i] = scan.nextInt();
      Y[i] = scan.nextInt();
    }
    scan.close();
    int res = 0;
    for (int i = 0; i <= w; i++) { for (int j = 0; j <= h; j++) { if (check(i, j)) { res++;
        }
      }
    }
    System.out.println(res);
  }
  public static boolean check(int x, int y) { for (int i = 0; i < n; i++) { int t1 = x - X[i];
      int t2 = y - Y[i];
      if (t1 * t1 + t2 * t2 <= r * r) { return true;
      }
    }
    return false;
  }
}

并查集

幼儿园

第一个是初始化

将数组初始化下标为本身

 for(int i=1;i arr[i]=i;
            }

合并 如果他俩不是一个父节点再将

public static void merge(int x,int y){ int prex=findRoot(x);
          int prey=findRoot(y);
          if(prex!=prey){ arr[prey]=prex;
          }

查找

传入查找的数字 不然继续往下查找

 public static int findRoot(int key){ if(key==arr[key]){ return key;
          }
          return arr[key]=findRoot(arr[key]);
        }

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main { private static int[] arr = null;
    public static void main(String[] args) { Scanner scan = new Scanner(System.in);
            int n=scan.nextInt();
            int m=scan.nextInt();
            arr=new int[n+1];
            for(int i=1;i arr[i]=i;
            }
            while(m-->0){ int op=scan.nextInt();
              int x=scan.nextInt();
              int y=scan.nextInt();
              if(op==1){ merge(x,y);
              }else{ int x1=findRoot(x);
                int y1=findRoot(y);
                if(x1!=y1){ System.out.println("NO");
                }else{ System.out.println("YES");
                }
              }
            }
            scan.close();
        }
        public static int findRoot(int key){ if(key==arr[key]){ return key;
          }
          return arr[key]=findRoot(arr[key]);
        }
        public static void merge(int x,int y){ int prex=findRoot(x);
          int prey=findRoot(y);
          if(prex!=prey){ arr[prey]=prex;
          }
        }
}

简单的动态规划

台阶问题

答案：

动态规划是这次的状态由前几次状态或者上次状态推导出来的

阶 走法

1 1

2 2

3 4

4 7

5 13

看出 f(n) = f(n-1) + f(n-2) + f(n-3)

然后用这个列方程就行

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int []dp=new int[n+1];
        if(n<=0){ System.out.println(0);
         return;
        }
        if(n<=2){ System.out.println(n);
         return;
        };
        if(n==3){ System.out.println(4);
         return;
        }
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        System.out.println(dp[n]);
        scan.close();
    }
}

二分求区间最大值的最小值

跳石头

这题思路是在起点和终点之间不断地寻找缩小范围 如果当前每次记录下来的的值进入 check方法进行判断

如果当前的距离小于最小值搬去不做影响 对搬去的数字++ 否则就从此处开始计算后续的有没有距离更小的

 static boolean check(int d){ int cnt=0,pos=0;
      for(int i=0;i if(arr[i]-pos cnt++;
        }else{ pos=arr[i];
        }
      }
      if(cnt<=m){ return true;
      }
      return false;
    }

答案

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main { static int l,n,m;
    static int[] arr;
    public static void main(String[] args) { Scanner scan = new Scanner(System.in);
        l = scan.nextInt();
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n];
        for(int i=0;i arr[i] = scan.nextInt();
        }
        int left=0,right=l;
        int mid,result=0;
        while(left<=right){ mid=(left+right)>>1;
          if(check(mid)){ result=mid;
            left=mid+1;
          }else{ right=mid-1;
          }
        }
         System.out.println(result);
        scan.close();
    }
    static boolean check(int d){ int cnt=0,pos=0;
      for(int i=0;i if(arr[i]-pos cnt++;
        }else{ pos=arr[i];
        }
      }
      if(cnt<=m){ return true;
      }
      return false;
    }
}

总结

直播挺难写的 算法也挺难写的 感觉算法基础还是不行 但是面试也要问 还是每天多写点吧