首页 > 代码库 > 笔试算法题(14):整数二进制表示中的1 & 判定栈的push和pop序列是否对应
笔试算法题(14):整数二进制表示中的1 & 判定栈的push和pop序列是否对应
出题:输入一个整数,要求计算此整数的二进制表示中1的个数
分析:
- 如果整数表示为k,当其是负数的时候,使用1<<i分别检测k的每一位;当其位整数的时候,则k/2表示将其二进制表示右移一位,k%2 ==0表示其是否是偶数,如果不是则说明当前二进制表示的最右边一位为1,当k==0成立的时候移位结束;
- 另外还可以使用‘消1’的方法,如果二进制表示A为‘****1000‘,则A-1为‘****0111‘,也就是我们仅关注二进制表示最右边的第一个 1,这样的话A&(A-1)的结果就可以将最右边的第一个1开始往右边的所有位都清除为0,‘****0000‘;所以没进行一次处理就消除一个 1,直到整个数字为0,则A&(A-1)进行的次数就是1的个数;
- 另外可以使用空间换时间的策略,将int所有取值所对应的1的个数存储为一个数组,则直接取数组值就可以得到;
解题:
1 int count1Binary(int k) { 2 int count=0; 3 if(k<0) { 4 /** 5 * 针对负数的情况,使用1<<i可以每次检测k的一个 6 * 位上是否为1,移动次数为sizeof(int),也可以 7 * 使用while(i){………, i=i<<1}这样当1溢出的时候 8 * 就是0,也就是结束的时候 9 * */ 10 int limit=sizeof(int)*8; 11 printf("the size of int is: %d",limit); 12 for(int i=0;i<limit;i++) { 13 if((k & (1 << i)) != 0) count++; 14 } 15 } 16 while(k>0) { 17 /** 18 * 此判断条件可以替换为 k&1 == 1 19 * */ 20 if(k%2 == 1) { 21 count++; 22 } 23 /** 24 * 移位操作可以替换为 k>>1 25 * 可以获得更高运算效率 26 * */ 27 k/=2; 28 } 29 30 return count; 31 } 32 33 int count1Binary2(int k) { 34 int count=0; 35 while(k) { 36 k=k&(k-1); 37 count++; 38 } 39 return count; 40 } 41 42 int main() { 43 printf("\n%d\n", count1Binary(-23)); 44 printf("\n%d\n", count1Binary2(-23)); 45 return 0; 46 }
出题:判断stack的push和pop序列是否对应,push和pop可能交替发生
分析:例如:push序列"1,2,3,4,5",pop序列"4,5,3,2,1"
解题:
1 /** 2 * 由于当前pop出去的元素肯定位于堆栈的栈顶,所以可以根据 3 * 这个性质,用push中的元素重建堆栈,创建tempStack,则 4 * 当前pop出去的元素要么已经位于tempStack的栈顶,要么还 5 * 在push序列中,如果是后者则需要将对应元素之前的元素都压入 6 * tempStack。所以如果上述两种情况都没有发生,则失败;如果 7 * 最终的pop序列和push序列都遍历完全,tempStack非空,则返 8 * 回true,否则返回失败。 9 * */ 10 bool judgePushPopSeq(int *push, int pushL, int *pop, int popL) { 11 MyStack *tempStack=new MyStack(); 12 int pushI=0, popI=0; 13 int temp;bool isFound; 14 while(true) { 15 isFound=false; 16 if(tempStack->peek(&temp) && temp==pop[popI]) { 17 isFound=true; 18 tempStack->pop(NULL); 19 popI++; 20 } else { 21 for(int i=pushI;i<pushL;i++) { 22 if(push[i] == pop[popI]) { 23 for(int j=pushI;j<i;j++) { 24 tempStack->push(push[j]); 25 } 26 pushI=i++; 27 popI++; 28 isFound=true; 29 break; 30 } 31 } 32 } 33 if(!isFound) { 34 delete tempStack; 35 return false; 36 } 37 if(popI==popL && pushI==pushL && tempStack->isEmpty()) { 38 delete tempStack; 39 return true; 40 } else { 41 delete tempStack; 42 return false; 43 } 44 } 45 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。