MetaApp笔试题-在二维数组中查找值/检察树是否是镜像对称树

问题1，在二维数组中查找值

问题描述

现有一个n*n的二维正整数数组nums，每行元素保证递增，每列元素保证递增，求某正整数x是否存在于该二维数组中，需要尽量优化时间和空间复杂度

输入描述:
输入一个int的二维数组，目标值

输出描述:
输出目标值在二维数组中是否存在

示例

示例1

输入
1,2,3
2,3,4
3,4,5
3

输出
true

解决思路

分析

题目很明显是不希望我们通过两次遍历查找到目标数字是否存在，而是需要根据规律去判断。

方法

1.根据规律判断，依次查找
2.采用二分超找的方法

代码实现

// 思路1实现
public class Main{
    public static boolean searchMatrix(int[][] nums, int x) {
        if (nums == null || nums[0] == null) return false;
        // 从最右侧的最大值开始判断，小于直接跳行，大于，则依次递减查找
        int i = 0, j = nums[0].length - 1;
        while (i < nums.length && j >= 0) {
            if (nums[i][j] == x) return true;
            else if (nums[i][j] > x) --j;
            else ++i;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

问题2，检察树是否是镜像对称树

问题描述

给定一个二叉树, 检查它是否是镜像对称的

输入描述:
输入一棵树

输出描述:
输出这棵树是否是镜像对称

示例

示例1

输入
例如以下是镜像对称的
1
/ \
2 2
/ \ / \
3 4 4 3
输出
true

解决思路

分析

1. 通过镜像树的对称性质可以发现，节点的左节点比较的是同层对称节点的右节点，节点的右节点比较的是同层对称节点的左节点

方法

1. 通过递归的方式判断

代码实现

public class IP地址校验 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static boolean isTreeSymmetric(TreeNode root) {
        return isSame(root, root);
    }

    public static boolean isSame(TreeNode t1,TreeNode t2){
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        // 根节点值的比较，左节点和右节点比较，右节点和左节点比较
        return t1.val == t2.val && isSame(t1.left,t2.right) && isSame(t1.right,t2.left);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20