牛客网算法——名企高频面试题143题（6）

题目描述

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：

package 名企高频面试题143;

/**
 * @Classname 合并二叉树
 * @Description TODO
 * @Date 2020/12/13 20:32
 * @Created by xjl
 */
public class 合并二叉树 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        t1.val = t1.val + t2.val;
        if (t1.left != null && t2.left != null) {
            mergeTrees(t1.left, t2.left);
        } else if (t1.left == null && t2.left != null) {
            t1.left = t2.left;
        }
        if (t1.right != null && t2.right != null) {
            mergeTrees(t1.right, t2.right);
        } else if (t1.right == null && t2.right != null) {
            t1.right = t2.right;
        }
        return t1;
    }

    /**
     * @description TODO 代码的复现代码
     * @param: t1
     * @param: t2
     * @date: 2020/12/13 21:01
     * @return: 名企高频面试题143.合并二叉树.TreeNode
     * @author: xjl
     */
    public TreeNode mergeTrees1(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        t1.val += t2.val;
        if (t1.left != null && t2.left != null) {
            mergeTrees(t1.left, t2.left);
        } else if (t1.left == null && t2.left != null) {
            t1.left = t2.left;
        }
        if (t1.right != null && t2.right != null) {
            mergeTrees(t1.right, t2.right);
        } else if (t1.right == null && t2.right != null) {
            t1.right = t2.right;
        }
        return t1;
    }
}

题目描述

给定一个由0和1组成的2维矩阵，返回该矩阵中最大的由1组成的正方形的面积

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 最大的正方形
 * @Description TODO
 * @Date 2020/12/13 21:08
 * @Created by xjl
 */
public class 最大的正方形 {
    public int solve(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] - '0';
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i] - '0';
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    //表示的边长的位置
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
                    //表示的是位置的表示的长度
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]) + 1;
                    //最大位置的长度
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }

    @Test
    public void test() {
        solve(new char[][]{{1, 0, 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0}});
    }
}

题目描述

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下： 1. 每个孩子不管得分多少，起码分到一个糖果。 2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制) 给定一个数组arr代表得分数组，请返回最少需要多少糖果。 [要求] 时间复杂度为On, 空间复杂度为O1

package 名企高频面试题143;

import java.util.Arrays;

/**
 * @Classname 分糖果
 * @Description TODO
 * @Date 2020/12/13 21:23
 * @Created by xjl
 */
public class 分糖果 {
    /**
     * @description TODO 空间复杂度是不符合要求的  时间复杂度是可以的
     * @param: arr
     * @date: 2020/12/13 21:49
     * @return: int
     * @author: xjl
    */
    public int candy(int[] arr) {
        int n = arr.length;
        int l[] = new int[n];
        int r[] = new int[n];
        Arrays.fill(l, 1);
        Arrays.fill(r, 1);
        for (int i = 1; i < l.length; i++) {
            if (arr[i] > arr[i - 1])
                l[i] = l[i - 1] + 1;
        }
        for (int i = r.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1])
                r[i] = r[i + 1] + 1;
        }
        int count = 0;
        for (int i = 0; i < l.length; i++) {
            count += Math.max(l[i], r[i]);
        }
        return count;
    }
}