【刷题】牛客 JZ64 求1+2+3+...+n

叫我龙翔

发布于 2024-02-23 08:45:52

1430

题目描述

根据题目描述，会有两个主要难点： 1 如何控制遍历，2 如何计算。因为我们不能使用for while if else switch case等关键字，对于如何实现1 到 n 的遍历就显得十分困难。对此想出的策略有类构造函数，递归两种办法。如何计算注意规避掉公式法就好。

思路一（暴力递归版）

首先我们想到使用递归来实现：我们遇到的首要问题就是如何成功遍历：递归不难，但是如何保证遍历范围是 1 到 n 呢。这里使用短路处理 在函数中，如果与运算成立，则继续，否则终止函数直接返回false。

class Solution {
public:
    int Sum_Solution(int n) {
    	//只有 与运算 返回true 才会继续进行 模拟短路
    	//保证 n 大于 0
        n && (n+=Sum_Solution(n - 1));
        return n ;
    }
};

来看运行效果：

成功运行！！！过啦！！！

思路二（妙用内存版）

虽然我们无法使用乘法运算，但是我们可以利用程序内部进行的运算，比如开辟二维空间就可以模拟二阶乘法，三维数组可以模拟三阶乘法。所以原理非常简单，开辟一个 n * (n+1) 的二维数组然后通过位运算得到一半即可。

class Solution {
public:

    int Sum_Solution(int n) {
        char add[n][n+1];
        return (sizeof(add) >> 1);
    }
};

顺利运行！！！这种思路我愿称之为最美

思路三（快速乘法版）

这道题也可以使用快速乘法来解决。快速乘法的思路很简单

把其中一个乘数 a 转换为二进制
把每一位都与另一个乘数 b 相乘并乘以相应阶数
把每次结果加入结果中 我们先用while写一个通用版本，这道题只需在200以内就可以，即11位

//通用版本
class Solution {
public:

    int Sum_Solution(int n) {
        int a = n ;
        int b = n + 1;
        int sum = 0;
        int level = 1;
        while(b){
            int i = b & 1;
            if(i) sum += a * level;
            b = b >> 1;
            level *= 2;
        }
        return sum / 2;
    }
};

题目适配版

class Solution {
public:

    int Sum_Solution(int n) {
        int a = n ;
        int b = n + 1;
        int sum = 0;
        int level = 1;

        int i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;

        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;

        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;
        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;

        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;
        
        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;

        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;

        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;
        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;

        i = b & 1;
        if(i) sum += a * level;
        b >>= 1;
        level <<= 1;               
        
        return sum / 2;
    }
};

来看效果：

过啦！！！

思路四（构造巧解版）

我们可以通过构造一个类，然后创建一个类数组，就会使用 n 次构造函数，这里就可以帮助我们解决无法使用关键字的问题。 注意使用静态成员变量，帮助成功完成遍历求和。

#include <type_traits>
class add{
    public:
        add(){
            i+=j;
            j++;
        }

        static int i,j;
    };
int add::i = 0;

int add:: j = 1;
class Solution {
public:
    int Sum_Solution(int n) {
        add sum[n];
        return add::i;
    }
};

来看效果：