[学习报告]《算法零基础100讲》(第2讲) 数列

Question

1.509. 斐波那契数

class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        int a=0,b=1;
        for(int i=2;i<=n;i++)
        {
            int t=a+b;
            a=b;
            b=t;
        }
        return b;
    }
};

2.1137. 第 N 个泰波那契数

class Solution {
public:
    int tribonacci(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        if(n==2)
            return 1;
        int a=0,b=1,c=1;
        for(int i=3;i<=n;i++)
        {
            int t=a+b+c;
            a=b;
            b=c;
            c=t;
        }
        return c;
    }
};

3.剑指 Offer 64. 求1+2+…+n

class Solution {
public:
    int sumNums(int n) {
        return (1LL*n*(n+1))/2;
    }
};

4.896. 单调数列

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        if(nums.size()<=2)
            return true;
        int f1=0;
        int f2=0;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]-nums[i-1]>0) f1=1;
            if(nums[i]-nums[i-1]<0) f2=1;
        }
        return f1+f2<=1;
    }
};

5.剑指 Offer 57 - II. 和为s的连续正数序列

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        map<int,int>mp;
        int sum=0;
        vector<vector<int>>ans;
        for(int i=1;i<=target;i++)
        {
            long long  sum=0;
            vector<int>v;
            for(int j=i;;j++)
            {
                sum+=j;
                v.push_back(j);
                if(sum>=target)
                    break;
            }
            if(sum==target&&v.size()>1)
                ans.push_back(v);
        }
        return ans;
    }
};

6.829. 连续整数求和

 

class Solution {
public:

    int consecutiveNumbersSum(int n) {
        int res=0;
        for(int k=1;k*(k+1)<=2*n;k++)
        {
             if((n-k*(k+1)/2)%k==0) res++;
        }
        return res;
    }
};

Answer 1

谢谢分享！