【笔试复盘】2021.8.11-华为机试

题目1：叠积木

给出一个列表如[[6,7,],[5,4],[3,2]],表示木块的长和宽，当木块的长和宽不大于另个木块的长和宽时，就可以放在上面，此外数组还可以左右翻转。当长宽都大于等于上一个积木时才可以搭到上一个积木上，此外数组还可以左右翻转。求最多能搭多少层。（与leetcode354：俄罗斯套娃相似，不过添加了翻转，增加了难度）。

输入：
[[5,4], [6,3], [6,7], [6,6], [4,6]]
输出：
4

解析：

积木数据处理，大的做长，小的做宽
所有积木从大到小排序
动态规划求最大：可以定义一个 dp 数组，dp[i] 表示如果积木为 i 时，最大积木嵌套数为多少。其状态的转移，即这个 dp[i] 的获得，需要从前面 dp[0] ~ dp[i - 1] 中找到宽大于当前积木，同时 dp 值是所找到的里面最大的dpMax，dp[i] = dpMax + 1

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        str = str.replaceAll("\\[", "");
        str = str.replaceAll("\\]", "");
        str = str.replaceAll("\\s+", "");
        String[] arrStr = str.split(",");
        int[][] arr=new int[arrStr.length/2][2];
        for(int i=0;i<arr.length;i++){
            int a=Integer.parseInt(arrStr[2*i]);
            int b=Integer.parseInt(arrStr[2*i+1]);
            arr[i][0]=Math.max(a,b);//大的是长度
            arr[i][1]=Math.min(a,b);//小的是宽度
        }
        int result=getResult(arr);
        System.out.println(result);
    }

    public static int getResult(int[][] arr){
        if(arr.length==0 || arr==null){
            return 0;
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]){
                    return o2[1]-o1[1];
                }
                else{
                    return o2[0]-o1[0];
                }
            }
        });
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int maxCount = 1;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j][1] >= arr[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxCount = Math.max(maxCount, dp[i]);
        }
        return maxCount;
    }
}
//[[5,4],[6,3],[6,7],[6,6],[4,6]]  output:4
//[[5,4],[6,3],[6,7],[6,6]]  output:3

题目2：加密字符串

字符串中没有数字，全是小写字母，对该二进制文件进行压缩

规则1：连续相同的字母，使用数字来表示重复出现的个数，bbbccc压缩成b3c3，但是如果只有两个连续的字母，压缩之后没有收益，不压缩，如bb就不再压缩:
规则2：对于重复出现的连续子串，压缩为大写子串加重复数字，例如abcabcabc压缩成ABC3;
规则3：重复字母和重复子串同时出现，优先进行重复子串的压缩，例如aaaabcabc,压缩成a3ABC2;
规则4：有多个重复子串时，优先压缩最长的重复子串，例如aaaabcabcaaaabcabc,压缩成AAAABCABC2;

输入： "aaaabcaabcaabcaabc" 
输出： aaAABC4

题目3：往仓库放货物的最大数量

有一个天然形成的大坑，为台阶状结构，每个台阶的长度都为1,每个都的值为整数(正整数表示高于地平面，零表示与地平面平齐，负整数表示低于地平面)。有一批同等规格的货品(长度为N,高度为1)，货品只能平故，且货物的上表面不能招过地平面(保度为零) ,或者说，高于地平面的地中也不可存故

货物。计算一个给定的大坑中影多可以放多少个货品?

输入：【第一行（物品的宽度），第二行（坑的宽度），第三行（坑的深度）】
2 
4 
0,-1,-2,0
输出：1

3
8
0,-1,-2,2,1,1,1,2
输出：0

import java.util.*;

public class newCode3 {

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int l=Integer.parseInt(sc.nextLine());
        int n=Integer.parseInt(sc.nextLine());
        String input=sc.nextLine();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=Integer.parseInt(input.split(",")[i]);
        }
        int result=getResult(l,n,arr);
        System.out.println(result);
    }

    public static int getResult(int l,int n,int[] arr){
        int res = 0;
        //求每个深度对应的最大宽度就可以了
        //当宽度满足要求时，最大深度的相反数就为可以放的最多的物品 
        for(int i=0;i<arr.length;i++){
            int w=1;
            for(int k=i-1;k>=0;k--){
                if(arr[k]<=arr[i]){
                    w++;
                }
            }
            for(int k=i+1;k<arr.length;k++){
                if(arr[k]<=arr[i]){
                    w++;
                }
            }
            //和接雨水关键的不同就在于这一步，这个负深度就很巧妙，完美避开了正深度
            if(w>=l){
                res=Math.max(res,-arr[i]);
            }
        }
        return res;
    }
}

#华为机试##笔经##Java##华为#