今天是小浩算法“365刷题计划”第53天。为大家分享一道本应很简单的题目,但是却因增加了特殊条件,而大幅增加了难度。话不多说,直接看题。
01 PART
简单的题目
该题很容易出现在各大厂的面试中,属于必须掌握的题型。
求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
示例 1:
输入: n = 3 输出: 6
示例 2:
输入: n = 9 输出: 45
限制:
1 <= n <= 10000
02 PART
题目分析
这道题目出自《贱指offer》,因为比较有趣,就拿来分享给大家。
题目上手,因为不能使用公式直接计算(公式中包含乘除法),所以考虑使用递归进行求解,但是递归中一般又需要使用if来指定返回条件(这里不允许使用if),所以没办法使用普通的递归思路。那该怎么办呢?这里我们直接上代码(本题将展示多个语言),再进行分析。
//JAVA
class Solution {
public int sumNums(int n) {
boolean b = n > 0 && ((n += sumNums(n - 1)) > 0);
return n;
}
}
首先我们了解一下 && 的特性,比如有 A&&B
利用这一特性,我们将递归的返回条件取非然后作为 && 的第一个条件,递归主体转换为第二个条件语句。我知道肯定有人又会懵圈了,所以我们绘图说明。假若这里n=3,大概就是下面这样:
(我就说这个是图....我没有偷懒)
这里还有一点要强调的就是,受制于各语言的语法规则,我们需要做一些额外的处理。比如Java,这里如果去掉前面的变量申明,就会直接报错。
但是如果是C++就没有这样的问题:
//c++
int sumNums(int n) {
n && (n += sumNums(n-1));
return n;
}
python就是下面这样:
//py3
class Solution:
def sumNums(self, n: int) -> int:
return n and n+ self.sumNums(n-1)
Go怎么搞?
//go
func plus(a *int, b int) bool {
*a += b
return true
}
func sumNums(n int) int {
_ = n > 0 && plus(&n, sumNums(n - 1))
return n
}
什么,还要我给一个PHP的?惹不起..惹不起...大佬请拿走...
//PHP
class Solution {
function sumNums($n) {
$n > 0 && $n += $this->sumNums($n - 1);
return $n;
}
}
郑重申明(读我的文章必看):
03 PART
额外福利
另外,我还看到这样一个解法,感觉很有趣(思想很简单)。因为不是自己写的,所以这里得额外说明,咱不能白嫖,对不?(所以你们这些白嫖的不去给我点个在看嘛...)
//go
func sumNums(n int) int {
return (int(math.Pow(float64(n),float64(2)))+n)>>1
}