当前位置: 首页 > news >正文

阿里笔试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

太菜了&#xff0c;记录一下笔试题目&#xff0c;代码有更好解法欢迎分享。 1、满二叉子树的数量。 给定一颗二叉树&#xff0c;试求这课二叉树有多少个节点满足以该节点为根的子树是满二叉树&#xff1f;满二叉树指每一层都达到节点最大值。 第一行输入n表示节点数量&#xff…...

STM32:TIM定时器输出比较(OC)

一、输出比较简介 1、输出比较 OC&#xff08;Output Comapre&#xff09;输出比较输出比较可以通过比较CNT&#xff08;时基单元&#xff09;和CCR&#xff08;捕获单元&#xff09;寄存器值的关系&#xff0c;来对输出电平进行置1、置0或翻转的操作&#xff0c;用于输出一定频…...

HTTPS 加密协议

✏️作者&#xff1a;银河罐头 &#x1f4cb;系列专栏&#xff1a;JavaEE &#x1f332;“种一棵树最好的时间是十年前&#xff0c;其次是现在” 目录HTTPS"加密" 是什么HTTPS 的工作过程引入证书HTTPS http 安全层 (SSL) SSL 用来加密的协议&#xff0c;也叫 TLS …...

分布式锁和分布式事务

分布式锁 没有图形&#xff0c;只通过大量文字进行说明。分布式锁&#xff1a;redis分布式锁&#xff0c; zk分布式锁&#xff0c; 数据库做分布式锁 redis分布式锁 setnx key value ex 10 原子操作 AB两个线程减库存业务&#xff0c;假设库存是10 A线程获取锁&#xff0c;…...

RK3568平台开发系列讲解(驱动基础篇)I2C协议介绍

🚀返回专栏总目录 文章目录 一、I2C基本读写过程二、通讯的起始和停止信号三、数据有效性四、地址及数据方向五、响应沉淀、分享、成长,让自己和他人都能有所收获!😄 📢I2C的协议定义了通讯的起始和停止信号、数据有效性、响应、仲裁、时钟同步和地址广播等环节。 一、…...

HTML 音频(Audio)

HTML 音频(Audio) 声音在HTML中可以以不同的方式播放. 问题以及解决方法 在 HTML 中播放音频并不容易&#xff01; 您需要谙熟大量技巧&#xff0c;以确保您的音频文件在所有浏览器中&#xff08;Internet Explorer, Chrome, Firefox, Safari, Opera&#xff09;和所有硬件上…...

什么是Vue

✅作者简介&#xff1a;CSDN一位小博主&#xff0c;正在学习前端&#xff0c;欢迎大家一起来交流学习&#x1f3c6; &#x1f4c3;个人主页&#xff1a;白月光777的CSDN博客 &#x1f525;系列专栏&#xff1a;Vue从入门到进阶 &#x1f4ac;个人格言&#xff1a;但行好事&…...

python 内置函数和多线程

以下是Python的一些内置函数。这些函数是Python语言提供的基本功能&#xff0c;可以在不需要导入任何其他模块的情况下直接使用。这些函数可以完成广泛的任务&#xff0c;例如数学运算&#xff0c;序列和集合操作&#xff0c;类型转换&#xff0c;文件操作等等。透彻理解这些函…...

【Spring】我抄袭了Spring,手写一套MySpring框架。。。

这篇博客实现了一个简单版本的Spring&#xff0c;主要包括Spring的Ioc和Aop功能 文章目录这篇博客实现了一个简单版本的Spring&#xff0c;主要包括Spring的Ioc和Aop功能&#x1f680;ComponentScan注解✈️Component注解&#x1f681;在spring中ioc容器的类是ApplicationConte…...

vue中的生命周期

前言 很多时候我们希望能在 vue 生命周期的过程中执行一些操作&#xff0c;生命周期钩子函数也因此诞生了。相信使用过 vue 框架的同学都知道&#xff0c;生命周期的钩子函数允许我们在实例的不同阶段执行各种操作&#xff0c;便于我们更好的控制和使用实例。 生命周期钩子函数…...

硬件原理图设计规范(二)

1、可编程逻辑器件 编号 级别 条目内容 备注 1 推荐 FPGA的LE资源利用率要保证在50%&#xff5e;80%之间&#xff0c;EPLD的MC资源的利用率要保证在50%&#xff5e;90%之间。对于FPGA中的锁相环、RAM、乘法器、DSP单元、CPU核等资源&#xff0c;经过精确预算&#xff0c;…...

复旦微ZYNQ7020全国产替代方案设计

现在国产化进度赶人&#xff0c;进口的芯片只做了个功能验证&#xff0c;马上就要换上国产的。国内现在已经做出来zynq的只有复旦微一家&#xff0c;已经在研制的有上海安路&#xff0c;还有成都华微&#xff08;不排除深圳国威也在做&#xff0c;毕竟这个市场潜力很大&#xf…...

蓝桥杯真题——自动售水机

2012年第四届全国电子专业人才设计与技能大赛“自动售水机”设计任务书1. 系统框图接下来我们将任务分块&#xff1a; 1. 按键控制单元 设定按键 S7 为出水控制按键&#xff0c;当 S7 按下后&#xff0c;售水机持续出水&#xff08;继电器接通&#xff0c;指示 灯 L10 点亮&…...

软件质量保证与测试 课程设计 测试报告 缺陷报告撰写方法

测 试 报 告 2020年 6月 1日 测试项目 程序员 测试人 测试阶段&#xff1a; □集成 √系统 □ 测试日志编号清单 1,2,3,4,5,6,7,8,9,10 遗留错误说明&#xff1a;&#xff08;测试后仍然遗留下来未解决的错误及其说明&#xff09; 1.系统界面不够友好&…...

vue2和vue3中路由的区别和写法?

前言&#xff1a;Vue 2 和 Vue 3 中路由的主要区别在于使用的路由库不同。在 Vue 2 中&#xff0c;通常使用 Vue Router 作为路由库&#xff1b;而在 Vue 3 中&#xff0c;Vue Router 仍然是官方推荐的路由库&#xff0c;但也可以选择使用新的路由库 - Vue Router Next。下面分…...

【数据结构】第四站:单链表力扣题(一)

目录 一、移除链表元素 二、链表的中间结点 三、链表中倒数第k个结点 四、反转链表 五、合并两个有序链表 六、分割链表 一、移除链表元素 题目描述&#xff1a;力扣 法一&#xff1a;直接循环依次判断 对于这个题目&#xff0c;我们最容易想到的一种思路就是&#xff0c…...

SAP BPC简介

BPC是SAP在financial application领域主推的产品&#xff0c;由于从原有产品线发展而来&#xff0c;产品本身有两个版本&#xff0c;分别是基于MS OLAP平台和Netweaver OLAP平台。 整个系统分为.net前台和abap后台。由于abap端的数据结构与.net数据结构的差异&#xff0c;所以没…...

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关键字 &#x1f525;前言&#xff1a; C是在C的基础之上&#xff0c;容纳进去了面向对象编程思想&#xff0c;并增加了许多有用的库&#xff0c;以及编程范式等。熟悉C语言之后&#xff0c;对C学习有一定的帮助。今天的主要目标&#xff1a; 1️⃣ 补充C语言语法的不足&…...

斯坦福+哈佛医学院:虚拟细胞图像生成基础模型

摘要 构建能在计算机中模拟细胞行为的虚拟细胞&#xff0c;是计算生物学的核心目标。本文提出&#xff11;款图像生成模型CellFluxV2&#xff0c;可预测化学与遗传扰动下细胞形态的变化。CellFluxV2的核心创新在于&#xff0c;通过流匹配&#xff08;flow matching&#xff09…...

TOAST UI Chart折线图实战:实时数据更新与同步工具提示完整指南

TOAST UI Chart折线图实战&#xff1a;实时数据更新与同步工具提示完整指南 【免费下载链接】tui.chart &#x1f35e;&#x1f4ca; Beautiful chart for data visualization. 项目地址: https://gitcode.com/gh_mirrors/tu/tui.chart TOAST UI Chart是一款功能强大的数…...

机器人学前沿技术探索:robotics-coursework项目高级应用指南

机器人学前沿技术探索&#xff1a;robotics-coursework项目高级应用指南 【免费下载链接】robotics-coursework &#x1f916; Places where you can learn robotics (and stuff like that) online &#x1f916; 项目地址: https://gitcode.com/gh_mirrors/ro/robotics-cour…...

3分钟上手VSCode Mermaid Preview:在IDE中实现可视化图表实时预览

3分钟上手VSCode Mermaid Preview&#xff1a;在IDE中实现可视化图表实时预览 【免费下载链接】vscode-mermaid-preview Previews Mermaid diagrams 项目地址: https://gitcode.com/gh_mirrors/vs/vscode-mermaid-preview 还在为编写Mermaid图表时需要在代码编辑器与预览…...

被百度网盘限速逼疯了?用这款开源工具让下载速度提升70倍

被百度网盘限速逼疯了&#xff1f;用这款开源工具让下载速度提升70倍 【免费下载链接】BaiduNetdiskPlugin-macOS For macOS.百度网盘 破解SVIP、下载速度限制~ 项目地址: https://gitcode.com/gh_mirrors/ba/BaiduNetdiskPlugin-macOS &#x1f575;️‍♂️ 问题溯源&…...

013、部署篇:从本地开发到云原生(Docker/K8s)服务化部署

013、部署篇&#xff1a;从本地开发到云原生&#xff08;Docker/K8s&#xff09;服务化部署一、从一次深夜调试说起 上周三凌晨两点&#xff0c;我被报警短信吵醒——线上RAG服务的响应时间从200ms飙到了5秒。登录服务器一看&#xff0c;CPU跑满了&#xff0c;内存倒是还剩不少…...

3分钟上手PCL2-CE:打造专属Minecraft启动环境的完整指南

3分钟上手PCL2-CE&#xff1a;打造专属Minecraft启动环境的完整指南 PCL2-CE社区版是一款开源游戏配置工具&#xff0c;致力于为Minecraft玩家提供高效、灵活的游戏环境管理方案。通过智能化配置和模块化设计&#xff0c;让玩家告别繁琐设置&#xff0c;轻松掌控游戏入口&…...

SecGPT-14B提示工程:提升OpenClaw安全报告可读性的秘诀

SecGPT-14B提示工程&#xff1a;提升OpenClaw安全报告可读性的秘诀 1. 当安全报告遇上OpenClaw&#xff1a;我的真实痛点 上周五凌晨2点&#xff0c;我被OpenClaw的告警邮件惊醒——它发现我的个人服务器存在一个高危漏洞。但当我打开那份自动生成的安全报告时&#xff0c;眼…...

django做动态【个人主页】

一、项目概述与目标动态个人主页的定义与核心功能&#xff08;博客展示、项目集、联系表单等&#xff09;Django框架的优势&#xff08;MTV模式、ORM、Admin后台等&#xff09;技术栈预览&#xff08;Python 3.x, Django 3.x, Bootstrap 5, SQLite/PostgreSQL&#xff09;二、环…...

手机也能跑Llama?聊聊移动端/边缘设备部署LLM的现状、挑战与未来展望

手机也能跑Llama&#xff1f;移动端大语言模型部署实战指南 当ChatGPT掀起生成式AI浪潮时&#xff0c;大多数人都认为这类技术只能依赖云端算力。但2023年Meta开源Llama系列模型后&#xff0c;一个令人兴奋的问题开始被频繁讨论&#xff1a;我们能否在手机这样的移动设备上本地…...