满帮笔试9月6日

选择题25道，50分

选择题不容易做，乱七八糟什么都有考。

编程题2道，50分

第一道题：

给一个字符串"133333", 问1后面有几个3？

如果“1”则返回-1，如果1后面有不为3的其他数字，也返回-1

测试用例：注意，如果是“23333”这样的用例也返回-1。

第二道题：

题目是，给出一个数组，保存学生的分数，其中可以1人分1组，2人分1组，只要满足两个人中分数差距在20分之内；3人分一组，三人中最大差距在10分之内。

解法：考虑用递归的方式求解，最后过了96%的用例，还有点是超时了，递归的老毛病了，剪枝技术又没想出来啊哈哈。

import java.util.Scanner;
import java.util.*;
public class Main {
    //突然想到了，如果用个记忆数组，应该能过，Map<Integer,Integer>，其中key保存begin的位置
    public static int split(int[]nums, int begin){
        if(nums.length<1) return 0;
        if(begin>=nums.length){
            return 0;
        }
        if(nums.length-begin==1){
            return 1;
        }
        //只有两个学生的情况
        if(nums.length-begin==2){
            if(Math.abs(nums[begin]-nums[begin+1])<=20){
                return 1;
            }else{
                return 2;
            }
        }
        //?
        if(nums.length-begin==3){
            if(Math.abs(nums[begin]-nums[begin+2])<=10){
                return 1;
            }else if(Math.abs(nums[begin]-nums[begin+1])<=20 ||
                    Math.abs(nums[begin+1]-nums[begin+2])<=20){
                return 2;
            }else{
                return 3;
            }
        }
        //有三个及其以上的学生，
        int one = 1+split(nums, begin+1);
        int two = Integer.MAX_VALUE;
        if(Math.abs(nums[begin+1]-nums[begin])<=20){
            two = 1+split(nums, begin+2);
        }
        int three = Integer.MAX_VALUE;
        if(Math.abs(nums[begin+2]-nums[begin])<=10){
            three = 1+split(nums, begin+3);
        }
        int res = Math.min(Math.min(one, two), three);;
        //        int[] score = {100,110,120,140,160,180};
        System.out.println("begin:"+begin+":::"+one+","+two+","+three);
        return res;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] score = new int[n];
        for(int i=0;i<n;i++){
            score[i] = in.nextInt();
        }
        //
        Arrays.sort(score);
        int sp_n = split(score,0);
        System.out.println(sp_n);
    }
}

#满帮#