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





#华为机试##笔经##Java##华为#
全部评论
第一题可以使用回溯优化,没必要每次搜索时开一个list然后再逐个相加
点赞 回复
分享
发布于 2021-10-11 10:07
点赞 回复
分享
发布于 2021-10-11 10:08
小红书
校招火热招聘中
官网直投
点赞 回复
分享
发布于 2021-10-11 10:10
题目2可以通过位运算来做吧。 把当前楼层和目标楼层补足到同样的长度,再直接看前面有几位是相同的,后面不同的位数就是操作次数。
点赞 回复
分享
发布于 2021-10-11 11:53
第二题蒙了一会,题主代码肯是对的,但总感觉自己不太踏实,后来索性证明一下~ -------------------------------------- 直觉是动态规划, 子问题拆解碰到问题: 从第N层到第i层, 方式只可能有三条: 1)先到第i-1层, 再上一层, 即d[i-1]+1 2)先到i+1层, 再下一层, 即d[i+1]+1  3)如果i是偶数, 还可能是从i/2层坐电梯上来, 即d[i/2]+1 但这样d[i]依赖d[i+1]无法使用动态规划(d为最短路径函数) 下面证明方式2中到i+1层的方式一定是坐电梯直接到的, 否则一定不是最短路径: 要到i+1层同样只有三种方式: 1)从第i层上来, 不可能 快递员要到i层, 因此不可能是从i层走上来的, 除非傻了 2)从坐电梯到第i+1+k层走下来, 注意下楼只有一种方式, 一定是一路走下来 2.1)如果i为偶数, k定为奇数, 总路程s1为: d[(i+1+k)/2]+1+(k+1) 到第i/2层的最短路径一定小于等于先到d[i/2+(k+1)/2]再下楼到i/2层, 因为这是其中的一条路径 即, d[i/2] <= d[i/2+(k+1)/2] + (k+1)/2 因此先到i/2层再坐电梯到i层的路程s2有: s2 = d[i/2]+1 <= d[i/2+(k+1)/2]+1+(k+1)/2 <d[(i+1+k)/2]+1+(k+1) = s1 所以此时s1一定不是最短路径 2.2)如果i为奇数, k一定为偶数, 总路程s1为: d[(i+1+k)/2]+1+(k+1) 到(i+1)/2层的最短路径一定小于等于其中的一条: 到(i+1)/2+k/2层然后再走下楼 即: d[(i+1)/2] <= d[(i+1)/2+k/2]+k/2 因此因此先到(i+1)/2层再坐电梯到i+1层再到第i层的路程s2有: s2 = d[(i+1)/2] + 1 + 1 <= d[(i+1)/2+k/2]+k/2+1+1 <= d[(i+1+k)/2]+1+(k+1)=s1 当且仅当k=0时等号成立 2.3)综上, 最短路径中, 到i+1层然后下楼到i层只有一种情况, 即先坐电梯到i+1层然后走下来
点赞 回复
分享
发布于 2021-10-21 17:28
input.substring(1,input.length()-1).split(","); 这为啥是从1到input.length()-1啊
点赞 回复
分享
发布于 2022-04-01 21:29

相关推荐

头像
03-18 09:09
Java
点赞 评论 收藏
转发
10 79 评论
分享
牛客网
牛客企业服务