柚子快報(bào)激活碼778899分享：java 藍(lán)橋杯算法記錄

http://yzkb.51969.com/

算法記錄

因?yàn)樽罱斓剿{(lán)橋杯了 所以跟練了幾道題 今天就來(lái)記錄一下

信號(hào)覆蓋

信號(hào)覆蓋 解題思路：這題將輸入的x,y的進(jìn)行儲(chǔ)存 然后將每個(gè)點(diǎn)用check方法進(jìn)行檢測(cè)

int t1=x-X[i];

int t2=y-Y[i];

//用這個(gè)進(jìn)行判斷

t1*t1+t2*t2<=r*r

答案

import java.util.Scanner;

// 1:無(wú)需package

// 2: 類(lèi)名必須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;

}

}

并查集

幼兒園 第一個(gè)是初始化 將數(shù)組初始化下標(biāo)為本身

for(int i=1;i

arr[i]=i;

}

合并 如果他倆不是一個(gè)父節(jié)點(diǎn)再將

public static void merge(int x,int y){

int prex=findRoot(x);

int prey=findRoot(y);

if(prex!=prey){

arr[prey]=prex;

}

查找 傳入查找的數(shù)字 不然繼續(xù)往下查找

public static int findRoot(int key){

if(key==arr[key]){

return key;

}

return arr[key]=findRoot(arr[key]);

}

import java.util.Scanner;

// 1:無(wú)需package

// 2: 類(lèi)名必須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;

}

}

}

簡(jiǎn)單的動(dòng)態(tài)規(guī)劃

臺(tái)階問(wèn)題 答案： 動(dòng)態(tài)規(guī)劃是這次的狀態(tài)由前幾次狀態(tài)或者上次狀態(tài)推導(dǎo)出來(lái)的 階 走法 1 1 2 2 3 4 4 7 5 13 看出 f(n) = f(n-1) + f(n-2) + f(n-3) 然后用這個(gè)列方程就行

import java.util.Scanner;

// 1:無(wú)需package

// 2: 類(lèi)名必須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();

}

}

二分求區(qū)間最大值的最小值

跳石頭 這題思路是在起點(diǎn)和終點(diǎn)之間不斷地尋找縮小范圍 如果當(dāng)前每次記錄下來(lái)的的值進(jìn)入 check方法進(jìn)行判斷 如果當(dāng)前的距離小于最小值搬去不做影響 對(duì)搬去的數(shù)字++ 否則就從此處開(kāi)始計(jì)算后續(xù)的有沒(méi)有距離更小的

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:無(wú)需package

// 2: 類(lèi)名必須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;

}

}

總結(jié)

直播挺難寫(xiě)的 算法也挺難寫(xiě)的 感覺(jué)算法基礎(chǔ)還是不行 但是面試也要問(wèn) 還是每天多寫(xiě)點(diǎn)吧

柚子快報(bào)激活碼778899分享：java 藍(lán)橋杯算法記錄

http://yzkb.51969.com/

精彩文章