热乎着,昨晚阿里这题真太绝了

原创
2022/03/06 01:04
阅读数 345

前言

大家好,我是bigsai,好久不见甚是想念。

昨晚有个同学参加了阿里的笔试题,笔试完后同学说这次笔试感觉难,跟我说了其中一道题,我看了感觉还是挺有质量的,看着这个难度都是第二题,总共三题感觉还是有难度的(瑟瑟发抖),想着还是和大家分享一下。

9df1e5f3966f8d4dcc10ce6340717be7.png

描述

一个正m边形,他想知道多边形中等腰锐角三角形的数量。(三角形的顶点要在多边形的顶点上)
不同的三角形的定义:两个三角形,只要有一个点不在同一个位置上就算做不同的三角形。

数据范围3-10^7

分析

昨天看到这个问题,觉得还是比较新颖,也有很多细节,但是刚拿到这个问题自己懵逼的画了好久也才想出来,这里给大家share一下。

752ce626aaf81e938697e9e5804ede51.png 瞎折腾

问题的描述很简单,边为n的正多边形有多少等腰锐角三角形。

遇到这种问题我们该怎么分析呢?当然是先画几个案例分析一下。

26d80eb08236f62f37ee79c52582392e.png

这么一看,你可能觉得好像没啥规律哇。

你可能对奇数的有点眉目:奇数的每个边直直的就是对应一个点,那么有多少条边就有多少个等腰锐角三角形?

但是这个显然是错误的,有可能以不同的顶点作为等腰锐角三角形它刚好是个等边三角形,这样就会出现重复,然后还有的底边可能并不是恰好是多边形的一个边,而是多边形多个边组成底边(参考上图的正6边型)。

并且从这来看奇数边和偶数边还是有点区别的:放正来看,奇数的是点对边,而偶数的是点对点,结构上有些区别,那么有可能奇偶在结果上是有点区别的。

上面都是一个懵懵懂懂的状态,咱们整理一下有用的信息:

  • 正多边形,多少边就是多少个顶点

  • 正多边形,有轴对称的特性,等腰锐角三角形,也有轴对称的特性。

  • 等腰锐角三角形,腰有两个,而底边有一个,要么从底边考虑,要么从顶点考虑,这里底边如上面的正6边型甚至更多边型显然不容易考虑,但是各个顶点都是多边形的顶点,所以肯定从顶点考虑。算出一个顶点为等腰锐角顶角的所有三角形乘以顶点数量(如正五边形)然后减去重复(如正3、正6边形)的就是总结果了

  • 奇数偶数分开讨论。

偶数情况

我们先用偶数的情况分析,先不考虑重复情况(考虑太多脑子混淆),将 图形摆一下成这样:

5b6af70ab7d5557237f85bb943b07693.png

因为为正多边形,所以也就相当于各个顶点在圆上,这样更容易分析是不是锐角,这样的分析每个点,就很容易看出每个顶点对应多少个锐角了,正6、正8每个顶点都对应一个锐角,其实有的人可能已经看出规律了,就是在直角下方的线都能组成锐角

为了更清晰的观察,看下面这个图更清晰:

91d34a8c6c8d914b849ed8a24fa79844.png

其实就是计算直角下面的蓝色线的数量,这个直观一点是所有横线数量的一半(向下取整),每个横线由两个点组成,我们计算一下:

总共n个点,去掉两个顶点和最底下单个点,n-2个点组成(n-2)/2的线。其中直角下面的占一半就是[(n-2)/2]/2=(n-2)/4个,然后乘以顶点数量n,那么在偶数情况不考虑重复所有等腰锐角三角形数量为:

total=n*((n-2)/4))

奇数情况

回了偶数分析,奇数也很简单,奇数顶点不变,底边固定,也就是找能够组成锐角三角形的边数。

27d704d6e95b2f1c6e47220ab392c4dc.png

对于横线数量,如果是偶数个没疑问下面是锐角(上面多个顶点所以角度比直角小),而奇数个中间那条线同样也是锐角(如果去掉顶点才在中央),所以这种情况是横线数量的一半(向上取整),我们计算一下:

总计n个点,一个顶点,n-1个点组成线。那么有(n-1)/2个线,其中组成锐角三角形的一半向上取整那就是(n-1)/2+1,然后乘以顶点数量n,那么在奇数情况不考虑重复所有等腰锐角三角形数量为:

total=n*(((n-1)/2+1)/2))

重复三角形

上面考虑了不重复的三角形的情况,那么重复的三角形该怎么考虑了,上面看到正三角形、正6边型都遇到等边三角形而导致重复计算。

而正5、正7好像没有重复的等边三角形。

我们认真分析一下:等腰锐角三角形三个顶点都在正多边形的边上,其实也在一个圆上,如果构成等边三角形,说明这三个顶点能够将空间均分分开(也就是顶点、圆可以均匀分成三份)。那么顶点数量 n必须是三的倍数才可以啊

顶点数量n是3的倍数,那么具体重复了多少呢?

就是看这种等边三角形每个作为顶点,本来应该有n个,但是每种情况出现了三次,所以只考虑其中1/3作为顶点的等边三角形才不重复!所以我们要总次数去掉n的(2/3)。

那么总次数:

total-=(n/3)*2;

具体代码

这里代码有个小坑,n是10^7,那么这个数量级会越界int范围,需要用long,但是输入有的人用int计算这么样代码:

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();

    long total;
    if(n%2==0)
       total=n*((n-2)/4);
    else
       total=n*(((n-1)/2+1)/2);
    if(n%3==0){
            total-=(n/3)*2;
    }
    System.out.println(total);
}

但是还是错了,有的人还不知道为啥,主要的原因是下面这两句越界了:

total=n*((n-2)/4);
total=n*(((n-1)/2+1)/2);

有人说我已经total设成total设成long为啥还是错的,因为赋值运算符是先计算右侧n*((n-2)/4)此时相当于这么一个流程:

int temp=n*((n-2)/4);
long total=temp;

因为计算的数值范围都是int,所以最后结果也是int已经越界,然后将越界的这个int结果赋值给long范围的total。

和这个很类似的还有:

double a=3/2;
 System.out.println(a);

会输出1.0而不是1.5,如果想要正确计算那么要提前将计算的值转成double计算:

double a=(double) 3/2;

同样这个问题正确的代码为:

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    long total;
    if(n%2==0)
      total=(long)n*((n-2)/4);
    else
      total=(long)n* (((n-1)/2+1)/2);
    if(n%3==0){
      total-=(n/3)*2;
    }
    System.out.println(total);
}

总结

这种数学题、或者找规律的题还是偶尔可能碰到,多会一题多长个经验!当前还是以积累为主。

大家一起加油,有需要的也欢迎一起打卡力扣。

我是bigsai,肝了一本数据结构与算法pdf和一本动态规划pdf

欢迎添加 「bigsai66」,备注[pdf]领取

bac129d2d4bc662d5925dfac606ad1ee.png

原创不易,希望路过彦祖仙女点个赞、再看

本文同步分享在 博客“Big sai”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
0 评论
0 收藏
0
分享
返回顶部
顶部