[编程题] 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
[c language=”++”]
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;
}
}
};
[/c]
[编程题] 二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
[c language=”++”]
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;
}
};
[/c]
[编程题] 反转链表
输入一个链表，反转链表后，输出链表的所有元素。
[c language=”++”]
/*
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;
}
};
[/c]