机考[31-40]

程序员小明坐出租车上班。出于职业敏感，他注意到出租车的计费表有问题，总是太大。 出租车司机解释说他不喜欢数字4，所以他修改了计费表，直接跳过任何数字位置，其余功能正常。 比如： 23多一块钱就变成25； 39多一块钱变成50； 399多一块钱变成500； 小明看穿了司机的伎俩，准备用自己的知识打败司机的阴谋。 给出计费表的表面读数，并返还实际费用。 输入描述: 只有一行，数字N，表示里程表的读数。 (1<=N<=888888888)。 输出描述: 一个数字表示实际成本。以回车结束。 示例1： 输入 5 输出 4 说明 5表示计费表的表面读数。 实际费用只有4元。 示例2： 输入 17 输出 15 说明 17表示计费表的表面读数。 15意味着实际费用只有15元。 示例3： 输入 100 输出 81 说明 100表示计费表的表面读数。 81意味着实际费用只有81元。

public class ZT31 { 
             public static void main(String[] args) { 
                 Scanner sc = new Scanner(System.in);         int input = sc.nextInt();         int reduce = 0;         int idx = 0;         while (idx < input){ 
                     int next = idx  1 ;             String temp = String.valueOf(next);             String newTemp = "";             if (temp.contains("4")) { 
                         int fourIdx = temp.indexOf("4");                 if (fourIdx == temp.lengh()-1){ 
        
                    newTemp = temp.substring(0,fourIdx) + 5;
                }else { 
        
                    newTemp = temp.substring(0,fourIdx) + 5 + temp.substring(fourIdx+1);
                }
                reduce += Integer.parseInt(newTemp) - idx -1;
                idx = Integer.parseInt(newTemp);
            }else { 
        
                idx++;
            }
        }
        System.out.println(input - reduce);
    }

上述算法遇到大位数据会超时，优化如下

public class ZT3102 { 
        
    public static void main(String[] args) { 
        
        Scanner in = new Scanner(System.in);
        int input = in.nextInt();
       //求司机多算了多少[0,10][10,100][100,1000]
        int temp = 0;
        int total = input;
        int k = 0;//记录当前位
        int j = 1;//记录个位？
        //13
        while (total > 0){ 
        
            if (total % 10 >4) { 
        //当前位大于4
                temp += (total % 10 - 1) * k + j ;
            }else { 
        //当前位小于4
                temp += (total % 10) * k;
            }
            k = k * 9 + j;
            j *= 10;
            total = total/10;
        }
        System.out.println(input - temp);
    }
}

一辆运送快递的货车，运送的快递均放在大小不等的长方体快递盒中，为了能够装载更多的快递，同时不能让货车超载，需要计算最多能装多少个快递。 注：快递的体积不受限制，快递数最多1000个，货车载重最大50000。 输入描述: 第一行输入每个快递的重量，用英文逗号分隔，如：5,10,2,11 第二行输入货车的载重量，如：20 不需要考虑异常输入。 输出描述: 输出最多能装多少个快递，如：3 示例1： 输入 5,10,2,11 20 输出 3 说明 货车的载重量为20，最多只能放三个快递5、10、2，因此输出3

public class ZT32 { 
        
    public static void main(String[] args) { 
        
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(",");//2 5 10 11 2510
        int max = Integer.parseInt(sc.nextLine());//20
        int[] arr = new int[input.length];
        for (int i = 0; i < input.length; i++) { 
        
            arr[i] = Integer.parseInt(input[i]);
        }
        Arrays.sort(arr);
        System.out.println(calc(arr,0,0,0,max));
    }

    private static int calc(int[] arr,int idx,int count,int total,int max){ 
        
        if (total > max || idx>= arr.length){ 
        
            return count-1;
        }
        int cl1 = calc(arr, idx+1, count+1,total + arr[idx],max);
        int cl2 = calc(arr, idx+1, count, total,max);
        return Math.max(cl1,cl2);
    }
}

给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 k 长的子串的长度，相同字母只取最长的那个子串。 输入描述: 第一行有一个子串(1<长度<=100)，只包含大写字母。 第二行为 k的值 输出描述: 输出连续出现次数第k多的字母的次数。 示例1 输入 AAAAHHHBBCDHHHH 3 输出 2 说明 同一字母连续出现的最多的是A和H，四次；第二多的是H，3次，但是H已经存在4个连续的，故不考虑；下个最长子串是BB，所以最终答案应该输出2。 示例2 输入 AABAAA 2 输出 1 说明 同一字母连续出现的最多的是A，三次；第二多的还是A，两次，但A已经存在最大连续次数三次，故不考虑；下个最长子串是B，所以输出1 示例3 输入 ABC 4 输出 -1 说明 只含有3个包含同一字母的子串，小于k，输出-1 示例4 输入 ABC 2 输出 1 说明 三个子串长度均为1，所以此时k = 1，k=2，k=3这三种情况均输出1。特此说明，避免歧义。 备注: 若子串中只包含同一字母的子串数小于k，则输出-1

public class ZT33 { 
        
    public static void main(String[] args) { 
        
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        int k1 = Integer.parseInt(sc.nextLine());
        int[] arr = new int[26];
        int temp = 0;
        char pre = ' ';
        for (int i = 0; i < input.length(); i++) { 
        
            if (i == 0){ 
        
                temp++;
                pre = input.charAt(i);
            }else if (input.charAt(i) == pre){ 
        
                temp++;
                int count = arr[pre - 'A'];
                arr[pre - 'A'] = Math.max(temp, count);
            }else { 
        //换代
                temp = 1;
                pre = input.charAt(i);
                arr[input.charAt(i) - 'A'] = Math.max(temp, arr[input.charAt(i) - 'A'] );;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) { 
        
            if (arr[i] != 0){ 
        
                list.add(arr[i]);
            }
        }
        list.sort((a1,b1) -> b1 - a1);
        if (list.size()<k1){ 
        
            System.out.println(-1);
        }else { 
        
            System.out.println(list.get(k1-1));
        }
    }
}

给定一个从小到大的有序整数序列（存在正整数和负整数）数组 nums ，请你在该数组中找出两个数，其和的绝对值(|nums[x]+nums[y]|)为最小值，并返回这个绝对值。 每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 输入描述: 一个通过空格分割的有序整数序列字符串，最多1000个整数，且整数数值范围是 -65535~65535。 输出描述: 两数之和绝对值最小值 示例1 输入 -3 -1 5 7 11 15 输出 2 说明 因为 |nums[0] + nums[2]| = |-3 + 5| = 2 最小，所以返回 2

public class ZT34 { 
        
    public static void main(String[] args) { 
        
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int[] arr = new int[input.length];
        for (int i = 0; i < input.length; i++) { 
        
            arr[i] = Integer.parseInt(input[i]);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) { 
        
            for (int j = 0; j < arr.length; j++) { 
        
                min = Math.min(min,Math.abs(arr[i]+arr[j]));
            }
        }
        System.out.println(min);
    }
}

一个工厂有m条流水线，来并行完成n个独立的作业，该工厂设置了一个调度系统，在安排作业时，总是优先执行处理时间最短的作业。 现给定流水线个数m，需要完成的作业数n, 每个作业的处理时间分别为t1,t2…tn。请你编程计算处理完所有作业的耗时为多少？ 当n>m时，首先处理时间短的m个作业进入流水线，其他的等待，当某个作业完成时，依次从剩余作业中取处理时间最短的进入处理。 输入描述: 第一行为2个整数（采用空格分隔），分别表示流水线个数m和作业数n； 第二行输入n个整数（采用空格分隔），表示每个作业的处理时长t1,t2…tn。 0< m,n<100，0<t1,t2…tn<100。 注：保证输入都是合法的。 输出描述: 输出处理完所有作业的总时长 示例1 输入 3 5 8 4 3 2 10 输出 13 说明 1、先安排时间为2、3、4的3个作业。 2、第一条流水线先完成作业，然后调度剩余时间最短的作业8。 3、第二条流水线完成作业，然后调度剩余时间最短的作业10。 4、总工耗时就是第二条流水线完成作业的时间13（3+10）。

public class ZT35 { 
        
    public static void main(String[] args) { 
        
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        String[] job = sc.nextLine().split(" ");
        int med = Integer.parseInt(input[0]);
        int[] arr = new int[job.length];
        for (int i = 0; i < job.length; i++) { 
        
            arr[i] = Integer.parseInt(job[i]);
        }
        Arrays.sort(arr);
        List<Medic> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) { 
        
            if (list.size() <med){ 
        
                list.add(new Medic(arr[i],arr[i]));
            }else { 
        
                //找到数组中 total最小的medic 加进去
                Collections.sort(list);
                Medic medic = list.get(0);
                medic.total += arr[i];
            }
        }
        Collections.sort(list);
        System.out.println(list.get(list.size()-1).total);
    }
    static class Medic implements Comparable{ 
        
        private int end;
        private int total;

        public Medic(int end, int total) { 
        
            this.end = end;
            this.total = total;
        }

        @Override
        public int compareTo(Object obj) { 
        
            Medic medic= (Medic)obj;
            return this.total - medic.total;
        }
    }
}

有一个简易内存池，内存按照大小粒度分类，每个粒度有若干个可用内存资源，用户会进行一系列内存申请，需要按需分配内存池中的资源，返回申请结果成功失败列表。分配规则如下： 1、分配的内存要大于等于内存申请量，存在满足需求的内存就必须分配，优先分配粒度小的，但内存不能拆分使用。 2、需要按申请顺序分配，先申请的先分配。 3、有可用内存分配则申请结果为true，没有可用内存分配则返回false。 注：不考虑内存释放。 输入描述: 输入为两行字符串： 第一行为内存池资源列表，包含内存粒度数据信息，粒度数据间用逗号分割，一个粒度信息内部用冒号分割，冒号前为内存粒度大小，冒号后为数量。资源列表不大于1024，每个粒度的数量不大于4096 第二行为申请列表，申请的内存大小间用逗号分隔。申请列表不大于100000 如： 64:2,128:1,32:4,1:128 50,36,64,128,127 输出描述: 输出为内存池分配结果。 如： true,true,true,false,false 示例1 输入 64:2,128:1,32:4,1:128 50,36,64,128,127 输出 true,true,true,false,false 说明 内存池资源包含：64K共2个、128K共1个、32K共4个、1K共128个的内存资源； 针对50,36,64,128,127的内存申请序列，分配的内存依次是：64,64,128,NULL,NULL,第三次申请内存时已经将128分配出去， 因此输出结果是：true,true,true,false,false