还好我面试没遇到这题…脑洞得大!
你好,我是yes。
今天刷到一道比较有意思的算法题,下次我打算拿这题去面面候选人,我觉得这题得开下脑洞,需要发散下思维。
我们来看一下题目:
求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
classSolution{
publicintsumNums(int n){
//你需要实现的逻辑
}
}
比如 n 为 5,则结果返回 15。
题目不绕,理解起来应该没有歧义,题目重点如下:
不能乘除
所以 n*(n +1) /2 这种公式就用不上了。
各种条件判断语句不能用,包括(A?B:C)这种三目运算。
这好像有点麻,看起来啥都不能用了,所以怎么搞?
你可以划到上面再看下题目,先自行思考两分钟。
是不是觉得条件有点苛刻?
那我们就先放自己一马,把条件先删减一下,我们先忽略条件判断语句的限制,先满足不用乘除的实现。对吧,饭要一口一口的吃,一开始不要太心急。
这样一来就挺简单的,一个递归就搞定。
publicintsumNums(int n){
if (n == 0) {
return n;
}
return n += sumNums(n - 1);
}
不过不要太高兴,这个 if 我们无法用,所以我们需要想办法把这个 if 给干掉才能 A 这个题。
这也是这题的难点所在,所以这题是一道中等题。
此时就需要开始发散思维了,我们不能依赖条件语句但又需要判断递归的跳出条件,怎么办?
不卖关子了,经验丰富的同学可能会想到 &&,与逻辑运算符。
这个运算符具有短路功能,相信很多同学都知道这个功能,我来简单的介绍一下,这个对于平时代码的简洁性有很大的帮助。
短路功能是指前面的条件如果是 true 则会执行后面的条件,如果前面的条件已经是 false 则不会执行后面的条件。
如果经常看源码的同学会发现在各大中间件或者类库中会频繁使用到 && 的短路功能。
比如,线程池类库 ThreadPoolExecutor 实现的例子,在它的
execute
即提交方法中,就用到了短路功能:workQueue.offer
这个方法。所以利用 && 短路机制就把可以这两个判断集中在一个 if 中,使得代码更加简洁,不然就得写两个 if,代码的层级就更多了:
if (isRunning(c)) {
if (workQueue.offer(command)) {
....
}
}
想必现在你已经清晰 && 的短路功能了,我们再回到这个题目中,可以看到,跳出条件其实可以换成
(n>0) && (n+=sums(n-1) > 0)
这样当 n = 0 的时候就短路了,后面的计算就不会进行,n 就不会被减到负数了。
但是这样不是一个语句,会抛错,不过这很简单,我们搞个布尔值赋值一下就ok了。
所以最终的答案是:
classSolution{
publicintsumNums(int n){
boolean flag = ((n > 0) && ((n += sumNums(n-1)) > 0));
return n;
}
}
我特意加上了括号,看着清晰一些。
时间复杂度:O(n),空间复杂度:O(n)
好了,这题就这样 A 了!其实这题我去年六月就刷过,记忆深刻,哈哈。
publicstaticintsumNums(int n){
try {
int a = 1 % n;
} catch (ArithmeticException e) { //捕捉除0错误。
return0;
}
return n + sumNums(n - 1);
}
不过平日里面的业务实现不推荐用异常来进行逻辑控制。
官方题解里面我看到一个用快速乘来实现的,一般这种从数学角度来解的我都不看的,第一看不懂,第二面试考察的也不是这玩意。
好了,今天就到这了,对算法有兴趣的可以关注下我的小号
我是yes,从一点点到亿点点,我们下篇见。
关键词
线程池
代码
方法
逻辑
题目
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。