当前位置：首页 > news >正文

牛客笔试训练

news 2025/8/28 6:28:13

牛客.过桥

在函数

 public static int n;public static  int[]arr=new int[2001];public static int bfs(){int left=1;int right=1;int ret=0;while(left<=right){ret++;int r=right;for(int i=left;i<=right;i++){r=Math.max(r,arr[i]+i);if(r>=n){return ret;}}left=right+1;right=r;}return -1;}public  static void main(String[]args){Scanner in=new Scanner(System.in);n=in.nextInt();for(int i=1;i<=n;i++){arr[i]=in.nextInt();}System.out.println(bfs());}

不在函数中，

import java.util.*;
public class Main{public  static void main(String[]args){Scanner in=new Scanner(System.in);int n=in.nextInt();int[]a=new int[n+1];for(int i=1;i<=n;i++){a[i]=in.nextInt();}int left=1;int right=1;int flag=0;int sum=0;
//这个只是提供循环次数，说是具体作用，实则不大while(left<=right){int r=right;sum++;
//这块是规定范围，并且在范围内，准备更新新的右侧范围，因为i+a[i]是区间内能达到的最大值for(int i=left;i<=right;i++){if(r<i+a[i]){r=i+a[i];}}if(r>=n){break;}
//left更新成right+1left=right+1;
//right更新成最新的r位置，下一次遍历就可以直接获取最大的位置了right=r;if(left>right){flag=1;break;}}if(flag==1){System.out.println(-1);}else{System.out.println(sum);}} 
}

牛客.最大差值

正确答案

public int getDis (int[] A, int n) {int min=A[0];int max=0;for(int i=0;i<n;i++){//无论如何我们都是先找到最小值，然后不断的减去，来求最大值，而不是单纯的求最大值和最小值，这里面max代表的是最大差值min=Math.min(min,A[i]);max=Math.max(A[i]-min,max);}return max;}

时间过于复杂，于是研究了上面的操作

public int getDis (int[] A, int n) {int sum=0;for(int a=0;a<n;a++){for(int b=a;b<n;b++){sum=Math.max(A[b]-A[a],sum);}}return sum;}

牛客.兑换零钱（一)(完全背包问题)

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 最少货币数* @param arr int整型一维数组 the array* @param aim int整型 the target* @return int整型*/public int minMoney (int[] arr, int aim) {int n=arr.length;//dp表，动态规划:[0,i]位置组成总和为j的最小质数.int[][]dp=new int[n+1][aim+1];for(int i=0;i<=aim;i++){dp[0][i]=0x3f3f3f3f;}dp[0][0]=0;if(aim==0){return 0;}for(int i=1;i<=n;i++){for(int j=1;j<=aim;j++){dp[i][j]=dp[i-1][j];if(j-arr[i-1]>=0){dp[i][j]=Math.min(dp[i][j-arr[i-1]]+1,dp[i-1][j]);}}}if(dp[n][aim]==0x3f3f3f3f){return -1;}return dp[n][aim];}
}