输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
可以采用移位的方式，也可以采用如下的方式
//该方式较好
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n)
{
count++;
n = n&(n-1);
}
return count;
}
};
//移位方式
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(n & flag)
count++;
flag = flag<<1;
}
return count;
}
};
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
分析：1.是否有意义的判断？
2.double类型的数据与0的比较
3.指数为负数时的处理
4.两种方法计算一个正数的n次幂
#include <iostream>
using namespace std;
//输入错误标志
bool g_bFlagError = false;
class Solution
{
public:
double Power(double base, int exponent) {
//输入无意义，由于浮点数有精度问题，所以判断等于0要判断值是否在一个较小的区间
if(base < 0.0000001 && base > -0.0000001)
{
if(0 == exponent)
{
cout<<"No meaning\n";
g_bFlagError = true;
return 0;
}
}
//e^0 = 1
if((base >= 0.0000001 || base <= -0.0000001) && exponent == 0)
return 1;
//有意义的情况
unsigned int nAbsExponent = (unsigned int) exponent;
if(exponent < 0)
nAbsExponent = (unsigned int)(-exponent);
double result = 1.0;
//计算,若要提高运算速度可以采用递归的方式实现
//while(nAbsExponent>0)
//{
//result = result*base;
//nAbsExponent--;
//}
result = PowerWithUsignedexponent(base,nAbsExponent);
//若指数为负数时需要处理
if(exponent < 0)
result = 1.0/result;
return result;
}
double PowerWithUsignedexponent(double base, int exponent)
{
//递归截止条件
if(exponent == 0)
return 1;
if(exponent == 1)
return base;
//计算
int result = PowerWithUsignedexponent(base, exponent>>1);
result *= result;
//如果指数是奇数
if(exponent & 0x1 == 1)
result *= base;
return result;
}
};
int main()
{
Solution s;
cout << s.Power(0,0)<<endl;
cout << s.Power(2,0)<<endl;
cout << s.Power(4,-2)<<endl;
cout << s.Power(4,2)<<endl;
return 0;
}
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
注意：相对位置不变!
class Solution
{
public:
void reOrderArray(vector<int> &array)
{
if(array.size() == 0)
return;
//定义连个临时队列
queue<int> odd;
queue<int> even;
vector<int>::iterator ite = array.begin();
for(; ite != array.end(); ite++)
{
//偶数
if((*ite & 0x1) == 0)
even.push(*ite);
else
odd.push(*ite);
}
ite = array.begin();
while(!odd.empty())
{
*ite = odd.front();
//cout<<*ite<<endl;
odd.pop();
ite++;
}
while(!even.empty())
{
*ite = even.front();
//cout<<*ite<<endl;
even.pop();
ite++;
}
}
};
int main()
{
Solution s;
//初始化容器
vector<int> array(8);
vector<int>::iterator ite = array.begin();
for(; ite != array.end(); ite++)
{
cout<<"Please input the array:";
cin>>*ite;
}
//操作
s.reOrderArray(array);
//输出
cout<<"***********************************"<<endl;
ite = array.begin();
for(; ite != array.end(); ite++)
{
cout<<*ite<<endl;
}
return 0;
}
输入一个链表，输出该链表中倒数第k个结点。
#include <iostream>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
//处理链表为NULL以及k=0的情况
if(pListHead == NULL || k == 0)
return NULL;
//定义两个指针，其中pHead指向链表前部分，pBehind指向链表后面部分
ListNode *pAhead = pListHead;
ListNode *pBehind = pListHead;
int i = 0;
for( ; i < k-1; i++)
{
if(pBehind->next != NULL)
pBehind = pBehind->next;
else
return NULL;
}
//当链表满足条件时
while(pBehind->next != NULL)
{
pBehind = pBehind->next;
pAhead = pAhead->next;
}
return pAhead;
}
};
int main()
{
int val;
ListNode *pListHead = NULL;
ListNode *ptemp = NULL;
for(int i = 0; i < 10; i++)
{
cout<<"Please input val:";
cin>>val;
ListNode *node = new ListNode(val);
if(i == 0)
{
ptemp = pListHead = node;
}
else
{
ptemp->next = node;
ptemp = node;
}
}
Solution s;
ListNode *result = s.FindKthToTail(pListHead, 12);
if(result!=NULL)
cout<<result->val<<endl;
else
cout<<"NULL"<<endl;
result = s.FindKthToTail(pListHead, 0);
if(result!=NULL)
cout<<result->val<<endl;
else
cout<<"NULL"<<endl;
result = s.FindKthToTail(pListHead, 5);
if(result!=NULL)
cout<<result->val<<endl;
else
cout<<"NULL"<<endl;
result = s.FindKthToTail(NULL, 5);
if(result!=NULL)
cout<<result->val<<endl;
else
cout<<"NULL"<<endl;
return 0;
}
输入一个链表，反转链表后，输出链表的所有元素。
考虑问题要全面: 链表为NULL的处理
链表只有1个结点时的处理
链表有2个或者2个以上节点的处理
（需要使用3个指针）
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
//如果链表为NULL，则返回NULL
if(pHead == NULL)
return NULL;
//如果链表只有1个结点
if(pHead->next == NULL)
return pHead;
//如果链表有2个或者2个以上的结点
ListNode *pPre = pHead;
ListNode *pReverseHead = pHead->next;
ListNode *pBehind = NULL;
while(pReverseHead != NULL)
{
if(pReverseHead->next != NULL)
pBehind = pReverseHead->next;
else
pBehind = NULL;
//如果是pHead中的第一个结点，那么其next指针为NULL
if(pPre == pHead)
pPre->next = NULL;
//将中间指针的next指向前一个指针，然后三个指针向前移动一个位置
pReverseHead->next = pPre;
pPre = pReverseHead;
pReverseHead = pBehind;
}
//如果中间指针为NULL，那么意味着翻转后链表的头结点为该节点的前一个结点
if(pReverseHead == NULL)
pReverseHead = pPre;
pHead = pReverseHead;
return pHead;
}
};
