蚂蚁笔试 算法 0919
1. 有一个长度为n的数组,每次可以对某一个数减去x,或者对所有数-1,请问最少多少次操作可以让数组所有数小于等于0
解法(A100):贪心算法,贪心思路为:计算当前数组中>0的个数,并计算min(x, 数组最大值),两者比较,如果前者大,则数组都-1,否则,将数组中最大的元素-x。注意这里的数组动态变化。
本质上是计算两者的效率,看-1总体上能减多少,以及减x在正半轴减了多少
2. K近邻算法(A100),先计算测试样本和训练样本点的欧式距离,再把最近的k个训练样本拿出来,看他们的标签,计算标签的众数即为测试样本的标签
3. 给定一颗树及其子节点,第一行输入为节点数量n,第二行输入为n-1个数代表第二个到第n个节点的父节点,求这棵树的每个节点作为根节点的节点个数之和
(A 0,来不及了,有没有大佬来解释下
)
解法(A100):贪心算法,贪心思路为:计算当前数组中>0的个数,并计算min(x, 数组最大值),两者比较,如果前者大,则数组都-1,否则,将数组中最大的元素-x。注意这里的数组动态变化。
本质上是计算两者的效率,看-1总体上能减多少,以及减x在正半轴减了多少
2. K近邻算法(A100),先计算测试样本和训练样本点的欧式距离,再把最近的k个训练样本拿出来,看他们的标签,计算标签的众数即为测试样本的标签
3. 给定一颗树及其子节点,第一行输入为节点数量n,第二行输入为n-1个数代表第二个到第n个节点的父节点,求这棵树的每个节点作为根节点的节点个数之和
(A 0,来不及了,有没有大佬来解释下
全部评论
第三题就是一个递归,一棵树的权值等于所有 (子树权值)乘(2**其他子树总节点数)的累加 再加上2**所以子树节点数
什么叫做每个节点作为根节点的节点数之和?没看太懂![](https://uploadfiles.nowcoder.com/images/20220815/318889480_1660553763490/62AF11E48344D159DA608796DA7D39E5)
第一题怎么贪心呀
相关推荐
点赞 评论 收藏
分享