首页 > 代码库 > 笔试算法题（12）：整数的string到int转换 & 两个栈实现队列
笔试算法题（12）：整数的string到int转换 & 两个栈实现队列
出题：将输入的表示整数的字符串转变为对应的整数值；
分析：
- 每当右边增加一位，说明之前的sum应该高一个数量级，所以*10。由于这两个实现仅仅考虑正规的、正整数输入，所以需要一个Wrapper函数，其功能 主要处理：符号判断（第一个字符是-,+或者直接是数字）；非法输入判断（是否有非"0123456789"的字符存在）；
- 另外以string存在的整数极有可能是大整数，所以需要考虑int的溢出的情况，当然这已经超出本议题的范围，不做详细论述；
解题：
1 int NonRecursiveStrInt(char *target) { 2 int sum=0; 3 char *index=target; 4 while(*index != ‘\0‘) { 5 sum*=10; 6 sum+=*index-‘0‘; 7 index++; 8 } 9 return sum; 10 } 11 int RecursiveStrInt(char *target, int sum) { 12 if(*target != ‘\0‘) { 13 sum*=10; 14 sum+=*target-‘0‘; 15 return RecursiveStrInt(target++, sum); 16 } else 17 { 18 return sum; 19 } 20 } 21 //一个更加robust的版本，可以处理负数，以及包含非数字字符的string的转换 22 int str2int(char *str) { 23 char *temp;bool isnegative=false; 24 int sum=0; 25 26 if(*str==‘-‘) { 27 isnegative=true; 28 temp=str+1; 29 } else 30 temp=str; 31 32 while(*temp!=‘\0‘) { 33 if(*temp<‘0‘ || *temp>‘9‘) { 34 printf("\nbad int"); 35 return 0; 36 } 37 38 sum*=10; 39 sum+=*temp-‘0‘; 40 temp++; 41 } 42 43 if(isnegative) 44 sum=-sum; 45 return sum; 46 } 47 48 49 int main() { 50 char *target="-324g54s"; 51 printf("\n%d", str2int(target)); 52 return 0; 53 }
出题：要求使用两个堆栈结构实现队列
分析：
- 后进先出的模式转变成先进先出，堆栈A负责加入元素，堆栈B负责弹出元素，两种情况下需要将A中的元素弹出并加入B，所有操作均按照堆栈的性质执行：当B 空栈的时候，当A满栈的时候。第一种情况较为简单，检测到B空栈，则将A中元素弹出并加入B；第二种情况需要使用第三个辅助堆栈保存B原有的元素，处理完 A中元素之后再将原有元素压入B栈，并且A中送过来的元素需要满足一定的数量限制，以保证B有足够的空间存储原有的元素；
- 反过来如果要用两个队列实现一个堆栈，能想到的办法是：迭代使用一个队列保存最近压入的元素，迭代发生在弹出元素的时候；
解题：
1 class MyStack { 2 private: 3 int *array; 4 int capability; 5 int length; 6 int head; 7 int tail; 8 public: 9 MyStack(int n=5): array((int*)malloc(sizeof(int)*n)), head(0),tail(0),capability(n), length(0) {} 10 ~MyStack() {delete [] array;} 11 12 bool isFull() { 13 if(length == capability) return true; 14 return false; 15 } 16 bool isEmpty() { 17 if(length == 0) return true; 18 return false; 19 } 20 int freeSlot() { 21 return capability-length; 22 } 23 void setBack() { 24 length=0; 25 } 26 /** 27 * head当前的指向位置是下一次将push的元素的 28 * */ 29 bool push(int n) { 30 if(isFull()) return false; 31 array[head]=n; 32 33 head=(head+1)%(capability); 34 length++; 35 return true; 36 } 37 /** 38 * tail当前指向的位置是下一次将pop的元素的 39 * */ 40 bool pop(int *n) { 41 if(isEmpty()) return false; 42 *n=array[tail]; 43 44 tail=(tail+1)%(capability); 45 length--; 46 return true; 47 } 48 49 void showStack() { 50 int i=tail; 51 int temp=length; 52 printf("\ncurrent stack elements: \n"); 53 while(temp>0) { 54 printf("%d, ",array[i++]); 55 temp--; 56 } 57 } 58 }; 59 /** 60 * first用于接收新元素，second用于输出旧元素， 61 * assist用于辅助栈 62 * */ 63 class MyQueue { 64 private: 65 MyStack *first; 66 MyStack *second; 67 MyStack *assist; 68 public: 69 MyQueue(int n=5): first(new MyStack(n)), second(new MyStack(n)), assist(new MyStack(n)) {} 70 bool push(int e) { 71 if(first->isFull()) { 72 /** 73 * freeSlot()可以知道stack中剩余的空位置 74 * */ 75 int fs=second->freeSlot(); 76 int temp=0; 77 /** 78 * 将second中的元素弹出并加入到assist中 79 * 80 * */ 81 while(second->pop(&temp) && assist->push(temp)); 82 83 /** 84 * 从first中的元素弹出并压入second中，注意 85 * 有个数限制 86 * */ 87 int i=0; 88 while(i<fs && first->pop(&temp) && second->push(temp)) { 89 i++; 90 } 91 92 /** 93 * 将second原有的元素从assist中取回，由于之前经过严格 94 * 的个数计算，所以一定可以全数压回 95 * */ 96 while(assist->pop(&temp) && second->push(temp)); 97 /** 98 * setBack()函数可以将stack重置为0个元素 99 * */ 100 assist->setBack(); 101 } 102 if(first->push(e)) return true; 103 else return false; 104 } 105 bool pop(int *e) { 106 int temp=0; 107 if(second->isEmpty()) { 108 /** 109 * 当second为空的时候，将first中的元素弹出并压入 110 * 到second中，主要当second满栈的时候需要将最后 111 * 一个元素压回first 112 * */ 113 while(first->pop(&temp) && second->push(temp)); 114 115 if(second->isFull()) first->push(temp); 116 } 117 if(second->pop(e)) return true; 118 else return false; 119 } 120 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。