山西制作网站,生活中优秀的产品设计,多少钱的英文,建行官方网站首页题目 普通的伞在二维平面世界中#xff0c;左右两侧均有一条边#xff0c;而两侧伞边最下面各有一个伞坠子#xff0c;雨滴落到伞面#xff0c;逐步流到伞坠处#xff0c;会将伞坠的信息携带并落到地面#xff0c;随着日积月累#xff0c;地面会呈现伞坠的信息。 1、为了…题目 普通的伞在二维平面世界中左右两侧均有一条边而两侧伞边最下面各有一个伞坠子雨滴落到伞面逐步流到伞坠处会将伞坠的信息携带并落到地面随着日积月累地面会呈现伞坠的信息。 1、为了模拟伞状雨滴效应用二叉树来模拟二维平面伞(如下图所示)现在输入一串正整数数组序列(不含0数组成员至少是1个)若此数组序列是二叉搜索树的前序遍历的结果那么请输出一个返回值1否则输出0. 2、同时请将此序列构成的伞状效应携带到地面的数字信息输出来(左边伞坠信息右边伞坠信息详细参考示例图地面上数字)若此树不存在左或右扇坠则对应位置返回0。同时若非二叉排序树那么左右伞坠信息也返回0. 输入描述: 1个通过空格分割的整数序列字符串数组不含0数组成员至少1个输入的数组的任意两个数字都互不相同最多1000个正整数正整数值范围1~65535 输出描述: 输出如下三个值以空格分隔:是否二叉排序树左侧地面呈现的伞坠数字值右侧地面呈现的伞坠数字值.若是二叉排序树则输出1否则输出0(其左右伞坠值也直接赋值0)。 若不存存在左侧或者右侧伞坠值那么对应伞坠值直接赋值0。 示例1 输入: 8 3 1 6 4 7 10 14 13 输出: 1 1 13 说明: 1 表示是二叉搜索树前序遍历结果1表示左侧地面呈现的伞坠数字值13表示右侧地面呈现的伞坠数字值 思路 本题化解为两个问题 根据前序遍历数组中左右判断其是否能构成二叉搜索树左节点中间节点右节点 以示例数据为例8 3 1 6 4 7 10 14 13 根据前序遍历及二叉搜索树的特点第一个数8应该为根节点其后面小于8的所有数3 1 6 4 7在8的左边大于8的所有数10 14 13 在8的右边。问题化解为两个字数组是否为二叉搜索树用同样的办法递归判断即可。 设计dfs方法为dfs(nums,start,end)当前节点为nums[start]设istart1,不断右移i先找到第一个比当前节点大的数在索引【start1,i-1】就是左节点的部分继续右移i直到i越界或者nums[i]小于当前值。如果最后i是越界的iend1说明后面的数都比nums[start]大满足二叉搜索树的规律继续递归两个子数组【start1,i-1】和【i,end】递归中止条件是startend即只有一个数字返回true否则不满足直接返回false 求左右伞坠关键在于理解左右伞坠的定义题目并没有明确说明我的理解如下 如果不是二叉搜索树左右伞坠直接置0如果根节点没有左子树那么左伞坠为0如果没有右子树那么右伞坠为0寻找左伞坠的方法优先寻找左子树当左节点为空时再找右节点寻找右伞坠的方法优先寻找右子树当右节点为空时再找左节点 比如示例数据8 3 1 6 4 7 10 14 13输出1 1 13 删除一个节点8 3 6 4 7 10 14 13输出1 4 13 只要左子树8 3 1 6 4 7输出1 1 0 只要右子树8 10 14 13输出1 0 13 只要根节点8输出:1 0 0 题解
package hwod;import java.util.Arrays;
import java.util.Scanner;public class UmbrellaRainDrop {public static void main(String[] args) {Scanner sc new Scanner(System.in);int[] nums Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();int[] res umbrellaRainDrop(nums);for (int i 0; i res.length; i) {if (i ! 0) System.out.print( );System.out.print(res[i]);}System.out.println();}private static int[] umbrellaRainDrop(int[] nums) {boolean isSearchTree recur(nums, 0, nums.length - 1);if (!isSearchTree) return new int[]{0, 0, 0};int leftNum findLastNum(nums, 0, nums.length - 1, true);int rightNum findLastNum(nums, 0, nums.length - 1, false);return new int[]{1, leftNum, rightNum};}private static int findLastNum(int[] nums, int start, int end, boolean isLeft) {if (start end) return start 0 ? 0 : nums[start];int i start 1;while (i end nums[i] nums[start]) i;//处理没有左右伞坠的情况if (isLeft i start 1 start 0) return 0;if (!isLeft i end 1 start 0) return 0;if (isLeft) {//先找左边如果没有左节点就找右节点return i start 1 ? findLastNum(nums, i, end, isLeft) : findLastNum(nums, start 1, i - 1, isLeft);} else {//先找右边如果没有右节点就找左节点return i end 1 ? findLastNum(nums, start 1, i - 1, isLeft) : findLastNum(nums, i, end, isLeft);}}private static boolean recur(int[] nums, int start, int end) {if (start end) {return true;}int i start 1;while (i end nums[i] nums[start]) i;int tmp i;while (i end nums[i] nums[start]) i;if (i ! end 1) return false;return recur(nums, start 1, tmp - 1) recur(nums, tmp, end);}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
