阿里笔试2023-3-15

太菜了,记录一下笔试题目,代码有更好解法欢迎分享。

1、满二叉子树的数量。

给定一颗二叉树,试求这课二叉树有多少个节点满足以该节点为根的子树是满二叉树?满二叉树指每一层都达到节点最大值。

第一行输入n表示节点数量,接下来n行第一个代表左儿子,第二个代表右儿子。

注意:由于没有说明1号节点就是根节点,因此需要寻找入度为0的节点作为根节点。

import java.util.*;

public class Main {

    static int res = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] nums = new int[n][2];
        int root = -1;
        int[] inDegree = new int[n + 1];
        for (int i = 0; i < n; i ++) {
            nums[i][0] = in.nextInt();
            nums[i][1] = in.nextInt();
            if (nums[i][0] != -1) {
                inDegree[nums[i][0]] ++;
            }
            if (nums[i][1] != -1) {
                inDegree[nums[i][1]] ++;
            }
        }
        for (int i = 1; i <= n; i ++) {
            if (inDegree[i] == 0) {
                root = i;
                break;
            }
        }
        new Main().isFullTree(nums, root);
        System.out.println(res);
    }

    public int height(int[][] nums, int root) {
        if (root == -1) {
            return 0;
        }
        return Math.max(height(nums, nums[root - 1][0]), height(nums, nums[root - 1][1])) + 1;
    }

    public boolean isFullTree(int[][] nums, int root) {
        if (root == -1) {
            return true;
        }
        boolean lb = isFullTree(nums, nums[root - 1][0]);
        boolean rb = isFullTree(nums, nums[root - 1][1]);
        if (lb && rb && height(nums, nums[root - 1][0]) == height(nums, nums[root - 1][1])) {
            res ++;
            return true;
        } else {
            return false;
        }
    }
}

上述解法时间复杂度O(nlog(n)),空间复杂度o(log(n))。

另外,可以掌握根据数组进行二叉树建树

class TreeNode {
    TreeNode left;
    TreeNode right;
    int val;
    public TreeNode() {}
    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode (TreeNode left, TreeNode right, int val) {
        this.left = left;
        this.right = right;
        this.val = val;
    }
}

public static void main(String[] args) {
    List<TreeNode> nodeList = new ArrayList<>();
    nodeList.add(null);
    for (int i = 1; i <= n; i ++) {
        nodeList.add(new TreeNode(i));
    }
    for (int i = 0; i < n; i ++) {
        if (nums[i][0] == -1) {
            nodeList.get(i + 1).left = null;
        } else {
            nodeList.get(i + 1).left = nodeList.get(nums[i][0]);
        }
        if (nums[i][1] == -1) {
            nodeList.get(i + 1).right = null;
        } else {
            nodeList.get(i + 1).right = nodeList.get(nums[i][1]);
        }
    }
}

2、三元组计数。

给定一个数组,计算有多少个三元组0<=i<j<k<n,且max(nums[i], nums[j], nums[k]) - min(nums[i], nums[j], nums[k]) = 1。

第一行输入n表示数组个数,第二行输入n个整数。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        Map<Integer, Long> map = new HashMap<>();
        long res = 0;
        for (int i = 0; i < n; i ++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0l) + 1);
        }
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            long low = entry.getValue();
            if (map.containsKey(entry.getKey() + 1)) {
                long high = map.get(entry.getKey() + 1);
                res += low * high * (high - 1) / 2;
                res += high * low * (low - 1) / 2;
            }
        }
        System.out.println(res);
    }
}

上述解法时间复杂度O(n),需要空间复杂度O(n)。

3、乘2除2。

在n个元素的数组中选择k个元素,每个元素要么乘以2,要么除以2并向下取整,使得操作完后数组的极差尽可能小,并且输出极差。极差为最大值减去最小值。

第一行输入整数n和k。第二行输入n个整数表示数组。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        };
        Arrays.sort(nums);
        PriorityQueue<Integer> queueMin = new PriorityQueue<>(comparator);
        PriorityQueue<Integer> queueMid = new PriorityQueue<>(comparator);
        PriorityQueue<Integer> queueMax = new PriorityQueue<>(comparator);
        int minMin = Integer.MAX_VALUE, midMin = Integer.MAX_VALUE, maxMin = Integer.MAX_VALUE;
        for (int i = 0; i < k ; i ++) {
            minMin = Math.min(minMin, 2 * nums[i]);
            queueMin.add(2 * nums[i]);
        }
        for (int i = k; i < n; i ++) {
            midMin = Math.min(midMin, nums[i]);
            queueMid.add(nums[i]);
        }
        int res = Integer.MAX_VALUE;
        if (k == 0) {
            res = Math.min(res, queueMid.peek() - midMin);
        } else {
            res = Math.min(res, Math.max(queueMin.peek(), queueMid.peek()) - Math.min(minMin, midMin));
        }
        for (int i = 0; i < k; i ++) {
            int tempMin = queueMin.poll();
            queueMid.add(tempMin / 2);
            midMin = Math.min(midMin, tempMin / 2);
            int tempMid = queueMid.poll();
            queueMax.add(tempMid / 2);
            maxMin = Math.min(maxMin, tempMid / 2);
            if (i == k - 1) {
                res = Math.min(res, Math.max(queueMid.peek(), queueMax.peek()) - Math.min(Math.min(minMin, midMin), maxMin));
            } else {
                res = Math.min(res, Math.max(Math.max(queueMin.peek(), queueMid.peek()), queueMax.peek()) - Math.min(Math.min(minMin, midMin), maxMin));
            }
        }
        System.out.println(res);
    }
}

上述解法时间复杂度O(nlog(n)),空间复杂度O(n)。

#软件开发2023笔面经#
全部评论
我觉得第三题可以简单一点,就是先排序,然后分成3部分,前面小的*2,中间不变,最后大的除以2,这样总共k+1种情况(前面0个-前面k个)。这样,新的最小值就在三个数之间选出来(3个部分的第一个数,都能O(1)取到),新的最大值也在三个数之间。然后取出最小和最大算一下。这样就是排序nlogn,后面O(k)就可以
5 回复 分享
发布于 2023-03-16 21:09 浙江
第一题每个节点都要求高度那时间复杂度应该是nlogn吧
1 回复 分享
发布于 2023-03-17 08:07 上海
请问是什么岗位的笔试啊,开发还是算法
点赞 回复 分享
发布于 2023-03-16 21:36 江苏
static int res = 0; public static void main2(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] nums = new int[n][2]; for (int i = 0; i < n; i ++) { nums[i][0] = in.nextInt(); nums[i][1] = in.nextInt(); } isFUllTree2(nums, 1); System.out.println(res); } public static int[] isFUllTree2(int[][] nums, int root) { if (-1 == root) { return new int[] {0, 1}; // 走到了叶子结点时,高度为0,也是满树 } int[] left = isFUllTree2(nums, nums[root - 1][0]); // 递归的遍历左子树 int[] right = isFUllTree2(nums, nums[root - 1][1]); // 递归地遍历右子树 int curHeight = Math.max(left[0], right[0]) + 1; // 计算当前结点高度 if (left[0] == right[0] && 1 == left[1] && 1 == right[1]) { // 如果左右子树的高度相同且都是满树,则当前树也是满树 res++; return new int[] {curHeight, 1}; } else { return new int[] {curHeight, 0}; } }
点赞 回复 分享
发布于 2023-03-17 10:08 广东
做的时候可以先看看后面的算法题题目,再去做选择吗?这样做选择的时候脑子能构思一下
点赞 回复 分享
发布于 2023-03-19 09:30 四川
想问下笔试是给你发邮件了吗?还是自己进官网找入口呀?
点赞 回复 分享
发布于 2023-03-19 11:14 香港
楼主这是春招的笔试还是的实习的笔试
点赞 回复 分享
发布于 2023-03-20 15:48 四川

相关推荐

无敌虾孝子:喜欢爸爸还是喜欢妈妈
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
14
93
分享
牛客网
牛客企业服务