剑指offer 面试题64. 求1+2+…+n（中）

发散思维的特点是思维活动的多向性和变通性，也就是我们在思考问题时注重运用多思路、多方案、多途径来解决问题。对于同一个问题，我们可以从不同的方向、侧面和层次，采用探索、转换、迁移、组合和分解等方法，提出多种创新的解法。

Question

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

示例 1： 

1
2
输入: n = 3
输出: 6
示例 2： 
1
2
输入: n = 9
输出: 45
限制：1 <= n <= 10000

测试用例

功能测试（输入5、10求1+2…+5和1+2+…+10）。 边界值测试（输入0和1）。

本题考点

考查应聘者的发散思维能力。当习以为常的方法被限制使用的时候，应聘者是否能发挥创造力，打开思路想出新的办法，是能否通过面试的关键所在。 考查应聘者的知识面的广度和深度。上面提供的几种解法涉及构造函数、静态变量、虚拟函数、函数指针、模板类型的实例化等知识点。只有深刻理解了相关的概念，才能在需要的时候信手拈来。这就是厚积薄发的过程。

Intuition

通用特性解法

基本方法： 递归 

1
2
3
4
5
class Solution:
    def sumNums(self, n: int) -> int:
        if n == 1:  return 1
        n += sumNums(n-1)
        return n
问题： 终止条件需要使用 if ，因此本方法不可取。 思考： 除了 if 和 switch 等判断语句外，是否有其他方法可用来终止递归？

利用逻辑运算符的短路效应 常见的逻辑运算符有三种，即 “与 && ”，“或 || ”，“非 ! ” ；而其有重要的短路效应，如下所示： 1、f(A && B)，若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false 2、if(A || B)，若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true 本题需要实现 “当 n = 1 时终止递归” 的需求，可通过短路效应实现。

1
n > 1 and sumNums(n - 1) # 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归

复杂度分析 时间复杂度： \(O(n)\)， 计算 \(n + (n-1) + ... + 2 + 1\) 需要开启 \(n\) 个递归函数；
空间复杂度 ：\(O(n)\) ， 递归深度达到 \(n\) ，系统使用 \(O(n)\) 大小的额外空间。

参考链接 作者：Krahets 链接：https://leetcode-cn.com/problems/qiu-12n-lcof/solution/mian-shi-ti-64-qiu-1-2-nluo-ji-fu-duan-lu-qing-xi-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。1

C++特性解法

解法一：利用构造函数求解

我们仍然围绕循环做文章。循环只是让相同的代码重复执行n遍而已，我们完全可以不用for和while来达到这个效果。比如我们先定义一个类型，接着创建n个该类型的实例，那么这个类型的构造函数将确定会被调用n次。我们可以将与累加相关的代码放到构造函数里。

解法二：利用虚函数求解

解法三：利用函数指针求解

解法四：利用模板类型求解

Code

通用特性解法

  • Python版本
1
2
3
4
5
6
7
8
class Solution:
    def __init__(self):
        self.res = 0

    def sumNums(self, n: int) -> int:
        n > 1 and self.sumNums(n-1)
        self.res += n
        return self.res
  • C++版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    static int res;
    Solution() {res=0;}
    int sumNums(int n) {
        if(n>1 && sumNums(n-1)){
            // 空语句 类似 python中的pass
        }
        res += n;
        return res;
    }
};

int Solution::res=0;

C++特性解法

  • 利用构造函数求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Temp {
public:
    Temp() {++N; Sum += N;}
    static void Reset() {N=0; Sum=0;}
    static unsigned GetSum() {return Sum;}
    private:
        static unsigned int N;
        static unsigned int Sum;
};

unsigned int Temp::N=0;
unsigned int Temp::Sum=0;

class Solution {
public:
    int sumNums(int n) {
        Temp::Reset();
        Temp *a=new Temp[n];
        delete []a;
        a=nullptr;
        return Temp::GetSum();
    }
};