笔试算法题（12）：整数的string到int转换 & 两个栈实现队列
2024-08-30 18:01:41
出题：将输入的表示整数的字符串转变为对应的整数值；
分析：
- 每当右边增加一位，说明之前的sum应该高一个数量级，所以*10。由于这两个实现仅仅考虑正规的、正整数输入，所以需要一个Wrapper函数，其功能 主要处理：符号判断（第一个字符是-,+或者直接是数字）；非法输入判断（是否有非"0123456789"的字符存在）；
- 另外以string存在的整数极有可能是大整数，所以需要考虑int的溢出的情况，当然这已经超出本议题的范围，不做详细论述；
解题：
int NonRecursiveStrInt(char *target) {
int sum=;
char *index=target;
while(*index != '\0') {
sum*=;
sum+=*index-'';
index++;
}
return sum;
}
int RecursiveStrInt(char *target, int sum) {
if(*target != '\0') {
sum*=;
sum+=*target-'';
return RecursiveStrInt(target++, sum);
} else
{
return sum;
}
}
//一个更加robust的版本，可以处理负数，以及包含非数字字符的string的转换
int str2int(char *str) {
char *temp;bool isnegative=false;
int sum=;
if(*str=='-') {
isnegative=true;
temp=str+;
} else
temp=str;
while(*temp!='\0') {
if(*temp<'' || *temp>'') {
printf("\nbad int");
return ;
}
sum*=;
sum+=*temp-'';
temp++;
}
if(isnegative)
sum=-sum;
return sum;
}
int main() {
char *target="-324g54s";
printf("\n%d", str2int(target));
return ;
}
出题：要求使用两个堆栈结构实现队列
分析：
- 后进先出的模式转变成先进先出，堆栈A负责加入元素，堆栈B负责弹出元素，两种情况下需要将A中的元素弹出并加入B，所有操作均按照堆栈的性质执行：当B 空栈的时候，当A满栈的时候。第一种情况较为简单，检测到B空栈，则将A中元素弹出并加入B；第二种情况需要使用第三个辅助堆栈保存B原有的元素，处理完 A中元素之后再将原有元素压入B栈，并且A中送过来的元素需要满足一定的数量限制，以保证B有足够的空间存储原有的元素；
- 反过来如果要用两个队列实现一个堆栈，能想到的办法是：迭代使用一个队列保存最近压入的元素，迭代发生在弹出元素的时候；
解题：
class MyStack {
private:
int *array;
int capability;
int length;
int head;
int tail;
public:
MyStack(int n=): array((int*)malloc(sizeof(int)*n)), head(),tail(),capability(n), length() {}
~MyStack() {delete [] array;}
bool isFull() {
if(length == capability) return true;
return false;
}
bool isEmpty() {
if(length == ) return true;
return false;
}
int freeSlot() {
return capability-length;
}
void setBack() {
length=;
}
/**
* head当前的指向位置是下一次将push的元素的
* */
bool push(int n) {
if(isFull()) return false;
array[head]=n;
head=(head+)%(capability);
length++;
return true;
}
/**
* tail当前指向的位置是下一次将pop的元素的
* */
bool pop(int *n) {
if(isEmpty()) return false;
*n=array[tail];
tail=(tail+)%(capability);
length--;
return true;
}
void showStack() {
int i=tail;
int temp=length;
printf("\ncurrent stack elements: \n");
while(temp>) {
printf("%d, ",array[i++]);
temp--;
}
}
};
/**
* first用于接收新元素，second用于输出旧元素，
* assist用于辅助栈
* */
class MyQueue {
private:
MyStack *first;
MyStack *second;
MyStack *assist;
public:
MyQueue(int n=): first(new MyStack(n)), second(new MyStack(n)), assist(new MyStack(n)) {}
bool push(int e) {
if(first->isFull()) {
/**
* freeSlot()可以知道stack中剩余的空位置
* */
int fs=second->freeSlot();
int temp=;
/**
* 将second中的元素弹出并加入到assist中
*
* */
while(second->pop(&temp) && assist->push(temp));
/**
* 从first中的元素弹出并压入second中，注意
* 有个数限制
* */
int i=;
while(i<fs && first->pop(&temp) && second->push(temp)) {
i++;
}
/**
* 将second原有的元素从assist中取回，由于之前经过严格
* 的个数计算，所以一定可以全数压回
* */
while(assist->pop(&temp) && second->push(temp));
/**
* setBack()函数可以将stack重置为0个元素
* */
assist->setBack();
}
if(first->push(e)) return true;
else return false;
}
bool pop(int *e) {
int temp=;
if(second->isEmpty()) {
/**
* 当second为空的时候，将first中的元素弹出并压入
* 到second中，主要当second满栈的时候需要将最后
* 一个元素压回first
* */
while(first->pop(&temp) && second->push(temp));
if(second->isFull()) first->push(temp);
}
if(second->pop(e)) return true;
else return false;
}
};
最新文章
- TPC-H生成.tbl文件导入postgresql数据库的坑
- ASP.NET MVC 5– 使用Wijmo MVC 5模板1分钟创建应用
- C++ 11 中的右值引用
- 深入理解PHP内核(七)变量及数据类型-常量
- Xcode编译相关
- CLR via C#(16)--泛型
- Asp.net窄屏页面 手机端新闻列表
- 读书笔记——OpenGL超级宝典
- js为元素添加onclick事件
- 诡异的XmlSerializer属性字段Specified
- Android入门教程之我见
- input输入字母自动大小写转换
- LightOJ 1205 Palindromic Numbers
- 【云图】如何制作全国KTV查询系统？
- python no module named _socket 原因
- hihocoder1323 回文字符串（区间dp）
- tomcat 拒绝服务
- jq svg 修改image的xmlns:xlink及图片的显隐
- jQuery操作(一)
- 通过request获取网页资讯 通过BeautifulSoup剖析网页元素