阿里笔试2023-3-15
太菜了,记录一下笔试题目,代码有更好解法欢迎分享。
1、满二叉子树的数量。
给定一颗二叉树,试求这课二叉树有多少个节点满足以该节点为根的子树是满二叉树?满二叉树指每一层都达到节点最大值。
第一行输入n表示节点数量,接下来n行第一个代表左儿子,第二个代表右儿子。
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];for (int i = 0; i < n; i ++) {nums[i][0] = in.nextInt();nums[i][1] = in.nextInt();}new Main().isFullTree(nums, 1);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;}if (isFullTree(nums, nums[root - 1][0]) && isFullTree(nums, nums[root - 1][1]) && height(nums, nums[root - 1][0]) == height(nums, nums[root - 1][1])) {res ++;return true;} else {return false;}}
}
上述解法时间复杂度O(n),空间复杂度o()
另外,可以掌握根据数组进行二叉树建树
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个整数。
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();}Arrays.sort(nums);Map<Integer, Integer> map = new HashMap<>();int res = 0;for (int i = 0; i < n; i ++) {map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);}for (int i = 0; i < n; i ++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if (map.containsKey(nums[i] + 1)) {int low = map.get(nums[i]);int high = map.get(nums[i] + 1);if (low == 1 && high == 1) {continue;}if (high > 1) {res += low * high * (high - 1) / 2;}if (low > 1) {res += high * low * (low - 1) / 2;}}}System.out.println(res);
}
上述解法时间复杂度O(nlog(n)),空间复杂度O(n)。
3、乘2除2。
在n个元素的数组中选择k个元素,每个元素要么乘以2,要么除以2并向下取整,使得操作完后数组的极差尽可能小,并且输出极差。极差为最大值减去最小值。
第一行输入整数n和k。第二行输入n个整数表示数组。
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>() {@Overridepublic 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-15
太菜了,记录一下笔试题目,代码有更好解法欢迎分享。 1、满二叉子树的数量。 给定一颗二叉树,试求这课二叉树有多少个节点满足以该节点为根的子树是满二叉树?满二叉树指每一层都达到节点最大值。 第一行输入n表示节点数量ÿ…...
STM32:TIM定时器输出比较(OC)
一、输出比较简介 1、输出比较 OC(Output Comapre)输出比较输出比较可以通过比较CNT(时基单元)和CCR(捕获单元)寄存器值的关系,来对输出电平进行置1、置0或翻转的操作,用于输出一定频…...
HTTPS 加密协议
✏️作者:银河罐头 📋系列专栏:JavaEE 🌲“种一棵树最好的时间是十年前,其次是现在” 目录HTTPS"加密" 是什么HTTPS 的工作过程引入证书HTTPS http 安全层 (SSL) SSL 用来加密的协议,也叫 TLS …...
分布式锁和分布式事务
分布式锁 没有图形,只通过大量文字进行说明。分布式锁:redis分布式锁, zk分布式锁, 数据库做分布式锁 redis分布式锁 setnx key value ex 10 原子操作 AB两个线程减库存业务,假设库存是10 A线程获取锁,…...
RK3568平台开发系列讲解(驱动基础篇)I2C协议介绍
🚀返回专栏总目录 文章目录 一、I2C基本读写过程二、通讯的起始和停止信号三、数据有效性四、地址及数据方向五、响应沉淀、分享、成长,让自己和他人都能有所收获!😄 📢I2C的协议定义了通讯的起始和停止信号、数据有效性、响应、仲裁、时钟同步和地址广播等环节。 一、…...
HTML 音频(Audio)
HTML 音频(Audio) 声音在HTML中可以以不同的方式播放. 问题以及解决方法 在 HTML 中播放音频并不容易! 您需要谙熟大量技巧,以确保您的音频文件在所有浏览器中(Internet Explorer, Chrome, Firefox, Safari, Opera)和所有硬件上…...
什么是Vue
✅作者简介:CSDN一位小博主,正在学习前端,欢迎大家一起来交流学习🏆 📃个人主页:白月光777的CSDN博客 🔥系列专栏:Vue从入门到进阶 💬个人格言:但行好事&…...
python 内置函数和多线程
以下是Python的一些内置函数。这些函数是Python语言提供的基本功能,可以在不需要导入任何其他模块的情况下直接使用。这些函数可以完成广泛的任务,例如数学运算,序列和集合操作,类型转换,文件操作等等。透彻理解这些函…...
【Spring】我抄袭了Spring,手写一套MySpring框架。。。
这篇博客实现了一个简单版本的Spring,主要包括Spring的Ioc和Aop功能 文章目录这篇博客实现了一个简单版本的Spring,主要包括Spring的Ioc和Aop功能🚀ComponentScan注解✈️Component注解🚁在spring中ioc容器的类是ApplicationConte…...
vue中的生命周期
前言 很多时候我们希望能在 vue 生命周期的过程中执行一些操作,生命周期钩子函数也因此诞生了。相信使用过 vue 框架的同学都知道,生命周期的钩子函数允许我们在实例的不同阶段执行各种操作,便于我们更好的控制和使用实例。 生命周期钩子函数…...
硬件原理图设计规范(二)
1、可编程逻辑器件 编号 级别 条目内容 备注 1 推荐 FPGA的LE资源利用率要保证在50%~80%之间,EPLD的MC资源的利用率要保证在50%~90%之间。对于FPGA中的锁相环、RAM、乘法器、DSP单元、CPU核等资源,经过精确预算,…...
复旦微ZYNQ7020全国产替代方案设计
现在国产化进度赶人,进口的芯片只做了个功能验证,马上就要换上国产的。国内现在已经做出来zynq的只有复旦微一家,已经在研制的有上海安路,还有成都华微(不排除深圳国威也在做,毕竟这个市场潜力很大…...
蓝桥杯真题——自动售水机
2012年第四届全国电子专业人才设计与技能大赛“自动售水机”设计任务书1. 系统框图接下来我们将任务分块: 1. 按键控制单元 设定按键 S7 为出水控制按键,当 S7 按下后,售水机持续出水(继电器接通,指示 灯 L10 点亮&…...
软件质量保证与测试 课程设计 测试报告 缺陷报告撰写方法
测 试 报 告 2020年 6月 1日 测试项目 程序员 测试人 测试阶段: □集成 √系统 □ 测试日志编号清单 1,2,3,4,5,6,7,8,9,10 遗留错误说明:(测试后仍然遗留下来未解决的错误及其说明) 1.系统界面不够友好&…...
vue2和vue3中路由的区别和写法?
前言:Vue 2 和 Vue 3 中路由的主要区别在于使用的路由库不同。在 Vue 2 中,通常使用 Vue Router 作为路由库;而在 Vue 3 中,Vue Router 仍然是官方推荐的路由库,但也可以选择使用新的路由库 - Vue Router Next。下面分…...
【数据结构】第四站:单链表力扣题(一)
目录 一、移除链表元素 二、链表的中间结点 三、链表中倒数第k个结点 四、反转链表 五、合并两个有序链表 六、分割链表 一、移除链表元素 题目描述:力扣 法一:直接循环依次判断 对于这个题目,我们最容易想到的一种思路就是,…...
SAP BPC简介
BPC是SAP在financial application领域主推的产品,由于从原有产品线发展而来,产品本身有两个版本,分别是基于MS OLAP平台和Netweaver OLAP平台。 整个系统分为.net前台和abap后台。由于abap端的数据结构与.net数据结构的差异,所以没…...
Linux网络概述
写咋前面 今天,我们需要初步的认识一下Linux中网络的基本原理,只有大家对这个有一个初步的认识,后面我们学习起来才会更加的简单容易.计算机语言知识那么多,但是Linux不是.面试时,面试官总是会有问题难住你,我们后面需要看看书,这一点非常重要.我们现在谈的是脉络,.是框架.这些…...
Mybatis --- 获取参数值和查询功能
一、MyBatis的增删改查 1.1、新增 <!--int insertUser();--> <insert id"insertUser">insert into t_user values(null,admin,123456,23,男) </insert> 1.2、删除 <!--int deleteUser();--> <delete id"deleteUser">dele…...
【C++】C++入门,你必须要知道的知识
1.C关键字 🔥前言: C是在C的基础之上,容纳进去了面向对象编程思想,并增加了许多有用的库,以及编程范式等。熟悉C语言之后,对C学习有一定的帮助。今天的主要目标: 1️⃣ 补充C语言语法的不足&…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
