现在的位置: 首页 > 综合 > 正文

面试题整理(七)

2019年01月15日 ⁄ 综合 ⁄ 共 4348字 ⁄ 字号 评论关闭

28.整数的二进制表示中1的个数
题目:输入一个整数,求该整数的二进制表达中有多少个1。
例如输入10,由于其二进制表示为1010,有两个1,因此输出2。

分析:
这是一道很基本的考查位运算的面试题。
包括微软在内的……


一个很基本的想法是,我们先判断整数的最右边一位是不是1。
接着把整数右移一位,原来处于右边第二位的数字现在被移到第一位了,
再判断是不是1。
这样每次移动一位,直到这个整数变成0为止。
现在的问题变成怎样判断一个整数的最右边一位是不是1了。

很简单,如果它和整数1作与运算。由于1除了最右边一位以外,其他所有位都为0。
因此如果与运算的结果为1,表示整数的最右边一位是1,否则是0。*/

得到的代码如下:

///////////////////////////////////////////////////////////////////////
// Get how many 1s in an integer's binary expression
///////////////////////////////////////////////////////////////////////
int NumberOf1_Solution1(int i)
{
      int count = 0;
      while(i)
      {
            if(i & 1)
                  count ++;

            i = i >> 1;
      }

      return count;
}

可能有读者会问,整数右移一位在数学上是和除以2是等价的。
那可不可以把上面的代码中的右移运算符换成除以2呢?答案是最好不要换成除法。
因为除法的效率比移位运算要低的多,
在实际编程中如果可以应尽可能地用移位运算符代替乘除法。 

编程之美:复杂度降到1的个数

int Count(Byte v)

{

int num=0;

while(v)

{

v &= (v-1);

num++;

}

return num;

}

29题目:输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。

比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列:push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

分析:这到题除了考查对栈这一基本数据结构的理解,还能考查我们的分析能力。

这道题的一个很直观的想法就是建立一个辅助栈,每次push的时候就把一个整数push进入这个辅助栈,同样需要pop的时候就把该栈的栈顶整数pop出来。

我们以前面的序列4、5、3、2、1为例。第一个希望被pop出来的数字是4,因此4需要先push到栈里面。由于push的顺序已经由push序列确定了,也就是在把4 push进栈之前,数字1,2,3都需要push到栈里面。此时栈里的包含4个数字,分别是1,2,3,4,其中4位于栈顶。把4 pop出栈后,剩下三个数字1,2,3。接下来希望被pop的是5,由于仍然不是栈顶数字,我们接着在push序列中4以后的数字中寻找。找到数字5后再一次push进栈,这个时候5就是位于栈顶,可以被pop出来。接下来希望被pop的三个数字是3,2,1。每次操作前都位于栈顶,直接pop即可。

再来看序列4、3、5、1、2。pop数字4的情况和前面一样。把4 pop出来之后,3位于栈顶,直接pop。接下来希望pop的数字是5,由于5不是栈顶数字,我们到push序列中没有被push进栈的数字中去搜索该数字,幸运的时候能够找到5,于是把5 push进入栈。此时pop 5之后,栈内包含两个数字1、2,其中2位于栈顶。这个时候希望pop的数字是1,由于不是栈顶数字,我们需要到push序列中还没有被push进栈的数字中去搜索该数字。但此时push序列中所有数字都已被push进入栈,因此该序列不可能是一个pop序列。

也就是说,如果我们希望pop的数字正好是栈顶数字,直接pop出栈即可;如果希望pop的数字目前不在栈顶,我们就到push序列中还没有被push到栈里的数字中去搜索这个数字,并把在它之前的所有数字都push进栈。如果所有的数字都被push进栈仍然没有找到这个数字,表明该序列不可能是一个pop序列。

基于前面的分析,我们可以写出如下的参考代码:

#include <stack>

/////////////////////////////////////////////////////////////////////////////
// Given a push order of a stack, determine whether an array is possible to 
// be its corresponding pop order
// Input: pPush   - an array of integers, the push order
//        pPop    - an array of integers, the pop order
//        nLength - the length of pPush and pPop
// Output: If pPop is possible to be the pop order of pPush, return true.
//         Otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool IsPossiblePopOrder(const int*
pPush, const int* pPop, int nLength)
{
      bool bPossible = false;

      if(pPush && pPop && nLength > 0)
      {
            const int *pNextPush = pPush;
            const int *pNextPop = pPop;

            // ancillary stack
            std::stack<int> stackData;

            // check every integers in pPop
            while(pNextPop - pPop < nLength)
            {
                  // while the top of the ancillary stack is not the integer 
                  // to be poped, try to push some integers into the stack
                  while(stackData.empty() || stackData.top() != *pNextPop)
                  {
                        // pNextPush == NULL means all integers have been 
                        // pushed into the stack, can't push any longer
                        if(!pNextPush)
                              break;

                        stackData.push(*pNextPush);

                        // if there are integers left in pPush, move 
                        // pNextPush forward, otherwise set it to be NULL
                        if(pNextPush - pPush < nLength - 1)
                              pNextPush ++;
                        else
                              pNextPush = NULL;
                  }

                  // After pushing, the top of stack is still not same as 
                  // pPextPop, pPextPop is not in a pop sequence
                  // corresponding to pPush
                  if(stackData.top() != *pNextPop)
                        break;

                  // Check the next integer in pPop
                  stackData.pop();
                  pNextPop ++;
            }

            // if all integers in pPop have been check successfully, 
            // pPop is a pop sequence corresponding to pPush 
            if(stackData.empty() && pNextPop - pPop == nLength)
                  bPossible = true;
      }

      return bPossible;
}

30.在从1到n的正数中1出现的次数

要计算百位上出现1的次数,它将会受到三个因素的影响:百位上的数字,百位以下的数字,百位以上的数字。

如果百位上的数字为0,可知,百位上可能出现的1的次数由更高位决定,比如12013,百位上1的个数为12*100

如果百位上的数字为1,可知,它不仅受更高位影响,还受低位影响,比如12113,1的个数为12*100+113+1

如果百位上的数字大于1,仅由更高位影响,比如12213,(12+1)*100

抱歉!评论已关闭.