当前位置:   article > 正文

LeetCode 剑指 Offer 64. 求1+2+…+n_int sumnums(int n) { n&&(n+=sumnums(n-1)); return

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

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

示例 1:

输入: n = 3
输出: 6

限制:

1 <= n <= 10000

解法一:利用逻辑运算符的短路:

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

        return n;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

此算法时间复杂度为O(n),空间复杂度为O(n)。

解法二:利用虚函数求解:

class base;
vector<base *> arr;

class base {
public:
    virtual int plus(int i) {
        return 0;
    }
};

class derived : public base {
public:
    virtual int plus(int i) override {
        return i + arr[!!i]->plus(i - 1);
    }
};

class Solution {
public:
    int sumNums(int n) {
        arr.push_back(new base());
        arr.push_back(new derived());

        return arr[!!n]->plus(n);
    }
};
  • 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

此算法时间复杂度为O(n),空间复杂度为O(n)。

解法三:纯C环境下没有虚函数,可以使用函数指针代替:

// 函数指针数组,数组元素类型为int (*)(int)
int (*funcArr[2])(int);

int sum(int i) {
    return i + funcArr[!!(i - 1)](i - 1);
}

int sumTerminator(int i) {
    return i;
}

class Solution {
public:
    Solution() {
        funcArr[0] = sumTerminator;
        funcArr[1] = sum;
    }

    int sumNums(int n) {
        return funcArr[!!n](n);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

此算法时间复杂度为O(n),空间复杂度为O(n)。

解法四:利用static成员:

class Solution {
public:
    Solution() {
        sum += i;
        ++i;
    }

    int sumNums(int n) {
        vector<Solution *> temp;
        for (int i = 0; i < n; ++i) {
            temp.push_back(new Solution);
        }

        return sum;
    }

    static int i;
    static int sum;
};

// Solution::i初始化为0而非1,因为sumNums方法是非static的,调用前还需要创建一个Solution对象
int Solution::i = 0;
int Solution::sum = 0;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

此算法时间复杂度为O(n),空间复杂度为O(n)。

解法五:利用模板,在编译期计算出结果,但这种方式需要输入是constexpr的,LeetCode平台上无法完成,因为LeetCode平台上会传给sumNums方法参数:

class Solution {
public:
    template<int N> struct ans {
        enum {sum = N + ans<N - 1>::sum};
    };

    template<> struct ans<1> {
        enum {sum = 1};
    };

    int sumNums() {
        return ans<5>::sum;    // 模板参数需要是constexpr的
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

此算法时间复杂度为O(1),空间复杂度为O(1)。

解法六:将解法五中的enum改为const static int,在较老的不支持类内const static的编译器上,常用enum代替const static,这种方法也需要模板参数是constexpr的:

class Solution {
public:
    template<int N> struct ans {
        const static int sum = N + ans<N - 1>::sum;
    };

    template<> struct ans<1> {
        const static int sum = 1;
    };

    int sumNums() {
        return ans<3>::sum;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

此算法时间复杂度为O(1),空间复杂度为O(1)。

解法七:利用数组大小,根据求和公式sum = i(i+1)/2

class Solution {
public:
    int sumNums(int i) {
        bool arr[i][i+1];

        return sizeof(arr) >> 1;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

此算法时间复杂度为O(n),空间复杂度为O(n)。

解法八:对于相乘的两个数A和B,将B转换为二进制,如果B中的第i位为1,这位1对结果的贡献为A * (1 << i),这个方法也被称作俄罗斯农民乘法,经常被用于两数相乘取模的场景,如果两数相乘已经超过数据范围,但取模后不会超过,我们就可以利用这个方法来拆位取模计算贡献,保证每次运算都在数据范围内。将其应用到求和公式:

class Solution {
public:
    int sumNums(int i) {
        int a = i, b = i + 1;

        int ans = 0;
        while (b) {
            if (b & 1) {
                ans += a;
            }
            b >>= 1;
            a <<= 1;
        }
        // 到此ans等于n(n+1),还需要除2才是求和公式
        return ans >> 1;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

但是题目要求不能使用while循环,由于题目要求中对输入有限制,n最大为10000,因此最多循环14次,我们把循环中内容写14次即可:

class Solution {
public:
    int sumNums(int i) {
        int a = i, b = i + 1;
        int ans = 0;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        (b & 1) && (ans += a);
        b >>= 1;
        a <<= 1;

        return ans >> 1;
    }
};
  • 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
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65

此算法时间复杂度为O(lgn),空间复杂度为O(1)。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/182449
推荐阅读
相关标签
  

闽ICP备14008679号