4399 3月19日的java笔试 算法题

三道算题均只能提交样例 思路不一定对

1.有n座基地并排相连，每座基地有一定数额的财宝，对应一定的价值。一个小偷可以拿走任意座基地的财宝，为了不被发现他不能拿走相邻基地的财宝。求出它可以获得的最大财报价值。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] data = in.nextLine().split(",");
        data[data.length - 1] = data[data.length - 1].trim();//去掉最后一个数后可能会有的空格
        int[] nums = new int[data.length + 5];
        for (int i = 0; i < data.length; ++i) {
            nums[i + 1] = Integer.parseInt(data[i]);
        }
        int[] get = new int[data.length + 5];
        int result = 0;
		//首先拿取的基地的价值要相邻周围基地的价值
        for (int i = 1; i <= data.length; ++i) {
            if (nums[i] > nums[i - 1] + nums[i + 1]) {
                result += nums[i];
                get[i] = 1;
            }
        }
		//然后拿取一下剩余还可以拿的其它基地的价值
        for (int i = 1; i <= data.length; ++i) {
            if (get[i] != 1 && get[i - 1] != 1 && get[i + 1] != 1) {
                result += nums[i];
                get[i] = 1;
            }
        }
        System.out.println(result);

    }

2.一个大数a减去一个大数b（a>=b），用字符串来接收数据，然后计算a-b的结果。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a=in.next();
        String b=in.next();
        int la=a.length();
        int lb=b.length();
        int[] A=new int[la+1];
        int[] B=new int[lb+1];
        for (int i = 1; i <= la; i++) A[i]=Integer.parseInt(""+a.charAt(i-1));
        for (int i = 1; i <= lb; i++) B[i]=Integer.parseInt(""+b.charAt(i-1));
        int result=0;
        int p=1;
		//手算加减法的模拟
        for (int i = la,j=lb; i >=1&&j>=1; i--,j--) {
            int temp=A[i]-B[j];
            if(temp>=0) result+=p*temp;
            else {
                int k=i-1;
                while (k>=1){
                    if (A[k]>0) {
                        A[k++]--;
                        while(k!=i) {
                            A[k++]+=9;
                        }
                        A[k]+=10;
                        result+=p*(A[k]-B[j]);
                        break;
                    }
                    else --k;
                }
            }
            p=p*10;
        }
        System.out.println(result);

3.有n+1座基地，从0到n编号，从1号基地到n号基地每座基地有一定的高度。一个人位于第0号基地,他的初始能量为E，他需要从0号基地逐个跳到第n号基地。如果下一座要跳的第i号基地的高度比自身的能量E大，那么他会损失（height[i]-E）的能量，反之他会获得（E-height[i]）的能量。在跳至n号基地的过程中，他的E值不能为负数，求出满足题意的最小能量值。

public class Main10 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int[] height=new int[n+5];
        int maxHeight=0;
        for (int i = 1; i <=n; i++) {
            height[i]=in.nextInt();
            maxHeight=Math.max(maxHeight,height[i]);
        }

		//可以用二分找出满足条件的最小值
        int left=0,right=maxHeight;
        int result=right;
        while (left<right){
            int mid=(left+right)>>1;
            int curE=mid;
            boolean flag=true;
            for(int i=1;i<=n;++i){
                if (mid>=height[i]) mid+=mid-height[i];
                else mid-=height[i]-mid;
                if (mid<0) {
                    flag=false;
                    break;
                }
            }
            if (flag) {
                result=Math.min(result,curE);
                right=mid;
            }else {
                left=curE+1;
            }

        }
        System.out.println(result);
    }