Leetcode暑假训练100题———第一题
剑指Offer 64
求 1+2+…+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
题目分析: ①由于无法使用循环,所以我们考虑通过递归来解决问题。
②因为递归需要限制边界条件,且不能通过if来限制边界条件,所以我们考虑通过位运算来限制。我们使用&&运算,&&运算中,当第一个条件是false时,就不再考虑第二个条件,直接判断为false。所以我们可以将 n>0 这个判断条件作为第一个判断条件,第二个条件则为 (n += sumNums(n-1)) > 0
③综上,判断条件如下:boolean judge = (n>0) && ((n += sumNums(n-1)) > 0)
// 代码如下所示:
//java
class Solution {
public int sumNums(int n) {
boolean judge = (n>0) && ((n+=sumNums(n-1))>0);
return n;
}
}
注:本题有点脑筋急转弯的味道!
方法二: 利用求和公式 sum = (n+1)*n/2
代码如下:
//C++
class Solution {
public:
int sumNums(int n) {
bool num[n][n+1];
return sizeof(num)>>1;
}
};