【笔试复盘】2021.8.4-华为机试
题目1：最大岛屿体积
输入： 5 5 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 2 3 0 0 1 3 9 输出： 19注意先输入宽度，再输入高度
import java.util.*;
public class code1 {
static ArrayList<Integer> list=new ArrayList<Integer>();
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
int[][] matrix=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
matrix[i][j]=sc.nextInt();
}
}
System.out.println(getResult(matrix));
}
public static int getResult(int[][] matrix){
if(matrix.length==0 ||matrix[0]==null){
return 0;
}
int max=0;
int nr = matrix.length;
int nc = matrix[0].length;
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
if (matrix[r][c] != 0 ) {
dfs(matrix, r, c);
max=Math.max(max,getValue(list));
list=new ArrayList<Integer>();
}
}
}
return max;
}
public static void dfs(int[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] <= 0) {
return ;
}
list.add(grid[r][c]);
grid[r][c] = 0;
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public static int getValue(ArrayList<Integer> list){
int max=0;
for(int i=0;i<list.size();i++){
max=max+list.get(i);
}
return max;
}
} 题目2：机制的外卖员
外卖员每天在大厦中送外卖，大厦共有L层（0<L<=10^5），当他处于第N层楼时，可以每分钟通过步行梯向上达到N+1层，或向下达到N-1层，或者乘坐电梯达到2*N层。给定他所处位置N，以及外卖配送的目的楼层M，计算他送达的最短时间
输入：5 17 输出：4动态规划：
import java.util.Arrays;
import java.util.Scanner;
public class code2 {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String input=sc.nextLine();
int N=Integer.parseInt(input.split(" ")[0]);
int M=Integer.parseInt(input.split(" ")[1]);
int result=getResult(N,M);
System.out.println(result);
}
public static int getResult(int n,int m){
if(n>=m){
return 0;
}
int down=0,el=0;
int[] dp=new int[m+1];
Arrays.fill(dp,0);
for(int i=0;i<=n;i++){
dp[i]=n-i;
}
for(int i=n+1;i<=m;i++){
down=1+dp[i-1];
if(i%2==0){
el=dp[i/2]+1;
}
else{
el=2+dp[(i+1)/2];
}
dp[i]=Math.min(down,el);
}
return dp[m];
}
} 题目3：寻找完全相同的子树
在一颗二叉树中找出完全相同的两颗子树（子树层数必须大于或者等于2）。如果存在多对子树完全相同，返回层数最大的子树，如果不存在输出“-1”
与leetcode652的改编：自己处理输入+最大的子树
import java.util.*;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class code2 {
public static class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val){
this.val = val;
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String input=sc.nextLine();
String[] strArr=input.substring(1,input.length()-1).split(",");
TreeNode treeNode = Deserialize(strArr,0);
List<TreeNode> list=findDuplicateSubtrees(treeNode);
String result=null;
int max=0;
for(int i=0;i<list.size();i++){
String str=Serialize(list.get(i));
if(str.length()>max){
result=str;
}
max=Math.max(max,str.length());
}
if(result==null || result.length()<=2){
System.out.println("-1");
}
else{
System.out.println("["+result.substring(0,result.length()-1)+"]");
}
}
static Map<String, Integer> count;
static List<TreeNode> ans;
public static List<TreeNode> findDuplicateSubtrees(TreeNode root) {
count = new HashMap();
ans = new ArrayList();
collect(root);
return ans;
}
public static String collect(TreeNode node) {
if (node == null) return "null";
String serial = node.val + "," + collect(node.left) + "," + collect(node.right);
count.put(serial, count.getOrDefault(serial, 0) + 1);
if (count.get(serial) == 2)
ans.add(node);
return serial;
}
//层次序列化
public static String Serialize(TreeNode root) {
if(root == null){
return null;
}
StringBuffer sb = new StringBuffer();
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
int count = (1 << treeDepth(root)) - 1;//计数，拿到此树的深度后计算对应完全二叉树节点数
list.add(root);
count--;
TreeNode tmpNode = null;
//层次遍历二叉树，开始序列化
while(list.size() > 0 && count >= 0){
tmpNode = list.remove(0);
if(tmpNode != null){
sb.append(tmpNode.val+",");
list.add(tmpNode.left);
list.add(tmpNode.right);
}else{
sb.append("null,");//#作为空节点占位符
list.add(null);
list.add(null);
}
count --;
}
return sb.toString();
}
public static int treeDepth(TreeNode root){
int depth = 0;
if(root == null){
return depth;
}else{
int lDepth = treeDepth(root.left) + 1;
int rDepth = treeDepth(root.right) + 1;
return lDepth > rDepth ? lDepth : rDepth;
}
}
//层次序列化还原
public static TreeNode Deserialize(String[] strings, int index){
TreeNode newNode = null;
if(index < strings.length){
if(!strings[index].equals("null")){
newNode = new TreeNode(Integer.parseInt(strings[index]));
newNode.left = Deserialize(strings, 2 * index + 1);
newNode.right = Deserialize(strings, 2 * index + 2);
}
}
return newNode;
}
//[1,2,3,4,#,5,6,#,#,#,#,#,#]
//[1,4,3,1,#,2,#,#,#,#,#,1,#,#,#]
//[1,2,3,1,null,2,null,null,null,null,null,1,null,null,null]
} 
投递京东等公司10个岗位