首页 / 面试 / C++面试总结之算法（四）：数组
C++面试总结之算法（四）：数组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++面试总结之算法（四）：数组，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3983字，纯文字阅读大概需要6分钟。
内容图文
1. 栈用数组怎么实现
#define?MAXSIZE?10;??
template<class?T>??
class?Stack?{??
public:??//默认构造函数??
Stack();??
Stack(size_t?maxElements);??
Stack(T?data[],size_t?maxElments);??
~Stack()?{??
delete[]?arrays;
}?
//入栈??
void?Push(T?data)?{
if(isFull())??
throw?runtime_error("Full?stack");??
????else??{??
top++;//指向栈顶??
arrays[top]=data;?????
}??
}??
//出栈并返回??
T?Pop(){??
if(isEmpty())??
throw?runtime_error("No?elements?in?the?stack");?
else??{??
T?data=arrays[top];??
top--;??
return?data;??
}??
}??
//返回栈顶元素??
T?Top(){??
if(isEmpty())?
throw?runtime_error("No?elements?in?the?stack");??
else??
return?arrays[top];??
}??
//判断是否为空栈??
bool?isEmpty(){??
return?top==-1;??
}??
//栈是否已满??
bool?isFull(){??
return?top==maxSize-1;??
}??
//清空栈??
void?Clear(){??
while?(top!=-1)??
top--;??
}??
//获得栈里元素的个数??
size_t?GetSize(){??
return?top+1;??
}??
private:??
size_t?top;??
T?*arrays;??
size_t?maxSize;??
};????
template<class?T>??
Stack<T>::Stack():??maxSize(MAXSIZE),top(-1)?{??
arrays=new?T[maxSize];??
if(arrays==NULL)??
cout<<"动态分配内存失败";??
}??
template<class?T>??
Stack<T>::Stack(size_t?maxElements):?maxSize(maxElements),top(-1)??{??
arrays=new?T[maxSize];//创建存储栈的数组??
}??
template<class?T>??
Stack<T>::Stack(T?data[],size_t?maxElements):?maxSize(maxElements),top(-1)?{??
arrays=new?T[maxSize];//创建存储栈的数组??
for(size_t?i=0;i<maxSize;i++)??
arrays[i]=data[i];??
top+=maxSize;??
}??
2．两个数进行交换，不额外使用变量，怎么做
a = a+b; a ^= b
b = a – b; 或者 b ^= a
a = a-b; a ^= b
3. 找数组中最大和最小元素，能否优化这个O（n ）
（1）最简单的写法是这样：
void?naive(const?int*?x,?size_t?n,?int*?out_min,?int?*out_max)?{
????int?min?=?x[0],?max?=?x[0];
????for?(size_t?i?=?1;?i?<?n;?i++)?{
????????if?(x[i]?<?min)?
????????????min?=?x[i];
????????if?(x[i]?>?max)
????????????max?=?x[i];
????}
????*out_min?=?min;
????*out_max?=?max;
}
（2）逐对处理
void?pairwise(const?int*?x,?size_t?n,?int*?out_min,?int?*out_max){
????if?(n?==?1)?{
????????*out_min?=?*out_max?=?x[0];
????????return;
}
//初始化min和max
????int?min,?max;
????if?(x[0]?<?x[1])?{
????????min?=?x[0];?max?=?x[1];
????}
????else?{
????????min?=?x[1];?max?=?x[0];
????}
????size_t?i;
????for?(i?=?2;?i?<?n?-?1;?i?+=?2) {
????????if?(x[i]?<?x[i?+?1])?{?
????????????if?(x[i]?<?min)???
????????????????min?=?x[i];
????????????if?(x[i?+?1]?>?max)?
????????????????max?=?x[i?+?1];
????????}
????????else?{?//?x[i]?>=?x[i?+?1]
????????????if?(x[i?+?1]?<?min)
????????????????min?=?x[i?+?1];
????????????if?(x[i]?>?max)????
????????????????max?=?x[i];
????????}
????}
????if?(i?!=?n)?{????????????//?还有一个元素（因为奇数?n）
????????if?(x[i]?<?min)
????????????min?=?x[i];
????????else?if?(x[i]?>?max)?//?加入?else
????????????max?=?x[i];
????}
????*out_min?=?min;
????*out_max?=?max;
}
核心部分每次先比较两个相连的元素，然后把较小的与 min 比较，较大的与 max 比较，所以每对元素需要 3 次比较（(1)，(2A)或(2B)，(3A)或(3B)）。在偶数 n 的情况下，共需要3n/2次比较，奇数 n 则是(3n+1)*/2或(3n+2)/2次。
也可以写一个空间复杂度O(logn)的分治递归解：
void?divide(const?int*?x,?size_t?n,?int*?out_min,?int?*out_max){
????assert(size?>?0);
????if?(size?==?1)
????????*out_min?=?*out_max?=?x[0];
????else?if?(size?==?2)?{
????????if?(x[0]?<?x[1])?{
????????????*out_min?=?x[0];
????????????*out_max?=?x[1];
????????}
????????else?{
????????????*out_min?=?x[1];
????????????*out_max?=?x[0];
????????}
????}
????else?{
????????size_t?half?=?n?/?2;
????????int?min1,?max1,?min2,?max2;
????????divide(x,?half,?&min1,?&max1);
????????divide(x?+?half,?n?-?half,?&min2,?&max2);
????????*out_min?=?min1?<?min2???min1?:?min2;
????????*out_max?=?max1?>?max2???max1?:?max2;
????}
}
这种分治方式，时间复杂度仍然是不变的，即O(n)。但如果有n/2个并行单元，最理想的延迟是O(logn)。
4.找出一个字符串中第一个出现次数为一次的字符的下标,如何优化算法使得遍历次数更少？
哈希表统计出现次数
5.int 数组中保存了一个整数，如{1,2,3}，实现一个对数组加1的函数，不考虑{0,1,2,3}这种情况
6. 一个英文文章，含有各种单词和标点符号，从中找出A-Z都出现过至少一次的最小子串大小写不限
内容总结
以上是互联网集市为您收集整理的C++面试总结之算法（四）：数组全部内容，希望文章能够帮你解决C++面试总结之算法（四）：数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】