leetcode [面试题64. 求1+2+…+n]

(https://leetcode-cn.com/problems/qiu-12n-lcof/)

这题挺好玩的，猛的一看我真的没想起来怎么做，瞄了两眼题解明白了

方法一：用递归代替迭代

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

方法二：快速乘+递归

快速乘可以把乘法换成加法和位运算

class Solution {
public:
    int solve(int a,int b,int res){
        if(b == 0) return res;
        if(b & 1) res += a;
        return solve(a+a,b>>1,res);
    }
    int sumNums(int n) {
        int ans = solve(n,n+1,0);
        return ans>>1;
    }
};

总结：1：迭代可以用递归来代替。2：快速乘可以将乘法用加法和位运算来代替