【笔试复盘】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;
}
} 
