首页 > 代码库 > 笔试算法题(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 };