牛客网的三道简单练习

[编程题] 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。

class Solution {
public:
    int Fibonacci(int n) {
		if(n==0) return 0;
        else if(n==1) return 1;
        else
        {
            int dp1=0;
            int dp2=1;
            for(int i=2;i<=n;i++)
            {
                int tmp=dp2;
                dp2=dp2+dp1;
                dp1=tmp;
            }
            return dp2;
        }
    }
};

[编程题] 二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

class Solution {
public:
     int  NumberOf1(int n) {
         int result=0;
         int check=1;
         for(int i=0;i<sizeof(int)*8;i++)
         {
             if((check&n)!=0)
                 result++;
             check=(check<<1);
         }
         return result;
     }
};

[编程题] 反转链表
输入一个链表，反转链表后，输出链表的所有元素。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		ListNode* now=pHead;
        ListNode* preHead=new ListNode(0);
        preHead->next=now;
        
        if(now==NULL) return now;
        while(now->next)
        {
            ListNode* tmp=now->next;
            now->next=tmp->next;
            tmp->next=preHead->next;
            preHead->next=tmp;
        }
        return preHead->next;
        
    }
};