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