面试题64. 求1+2+...+n¶

描述¶

求 1+2+...+n, 要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C).

题解¶

分析¶

这道题本身不难，主要是添加了各种限制条件，归纳为3个限制

1. 不能用循环
2. 不能用乘除运算
3. 不能用if判断

不考虑限制条件的情况下，可以直接使用等差数列的求和公式 n*(n+1)/2，也可以使用for循环。考虑限制条件的情况下，可以通过递归避免循环和乘除运算。

int sumNums(int n){
    if (n==1)
        return 1;
    return n + sumNums(n-1);
}

但是这样还是会用到if，那可以通过什么避免if呢，答案是逻辑运算

int sumNums(int n){
    int sum = n;
    sum && (sum += sumNums(n-1)); // 逻辑运算，sum为0时停止递归
    return sum;
}

这其实不算是算法题，而是对基础知识掌握程度的考察。

实现¶

具体实现如下，其中Python实现可以直接返回and运算结果，这是因为and返回的不是0和1，而是具体的值。

int sumNums(int n){
    int sum = n;
    sum && (sum += sumNums(n-1));
    return sum;
}

class Solution {
public:
    int sumNums(int n) {
        int sum = n;
        sum && (sum += sumNums(n-1));
        return sum;
    }
};

class Solution:
    def sumNums(self, n: int) -> int:
        return n and (n + self.sumNums(n-1))