每日一题---day8

基础题：

元素出栈、入栈顺序的合法性。如：入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1），则合法。
入栈的序列（1,2,3,4,5），出栈序列（4,5,2,3,1），则不合法。

思路：栈的性质是后进先出，但入栈的同时也可进行出栈操作

代码：

bool IsLegal(const int* in,size_t inlength,const int* out,size_t outlength)
{
 if(inlength != outlength)
 return false;
 size_t inIndex  = 0;
 size_t outIndex = 0;
 stack<int> s;
 while(inIndex < inlength)
 {
 if(in[inIndex] == out[outIndex])
 {
 ++inIndex;
 ++outIndex;
 }
 else if(!s.empty() && out[outIndex] == s.top())
 {
s.pop();
    ++outIndex;
 }
 else
 {
 s.push(in[inIndex]);
 ++inIndex;
 }
 }
 while(!s.empty() && outIndex < outlength)
 {
 if(s.top() == out[outIndex])
 {
 s.pop();
 ++outIndex;
 }
 else
 break;
 }
 if(outIndex == outlength)
 return true;
 else
 return false;
}

附加题

计算一个整数二进制位中1的个数，要求效率尽可能的高。且能正确求正数和负数中的1的个数。

代码：

int cout_one_bits(int num)
{
 int count = 0;
 while(num)
 {
 ++count;
 num = num &(num-1);//这个数中1所在的位的权值
 }
 return count;
}