笔试算法题（21）：将stack内外颠倒 & 判断扑克牌顺子
2024-09-30 17:09:33
出题：要求用递归将一个栈结构的元素内外颠倒；
分析：
- 本题再次说明系统栈是程序员最好的帮手，但递归度较高所以时间复杂度较大，可以使用空间换时间的方法（额外数组保存栈元素，然后逆向压入）；
- 第一层递归（清空栈元素，并使用系统栈保存）：[1,2,3,4,5]，栈顶元素为1，将1弹出之后，递归处理[2,3,4,5]；
- 第二层递归（将栈顶元素插入到栈底，同样使用系统栈保存）：当[2,3,4,5]已经逆序之后，需要将1插入到栈底，所以将1作为参数传递到递归调用中，之后递归处理2和[3,4,5]；
解题：
class MyStack {
private:
int *array;
int capability;
int top;
public:
MyStack(int cap=): array((int*)malloc(sizeof(int)*cap)), capability(cap), top() {}
~MyStack() {delete [] array;}
bool isFull() {
return top == capability;
}
bool isEmpty() {
return top == ;
}
int freeSlot() {
return capability - top;
}
/**
* top当前的位置就是下一个push元素所在的slot
* */
bool push(int n) {
if(isFull()) return false;
array[top++]=n;
return true;
}
bool pop(int *n) {
if(isEmpty()) return false;
*n=array[--top];
return true;
}
void ShowStack() {
int temp=top-;
printf("\n");
for(int i=;i<=temp;i++)
printf("%d, ",array[i]);
printf("\n");
}
};
void AddToBottom(MyStack *stack, int top) {
int curTop;
if(stack->pop(&curTop)) {
AddToBottom(stack, top);
stack->push(curTop);
}else
stack->push(curTop);
}
void ReverseStack(MyStack *stack) {
int top;
if(stack->pop(&top)) {
ReverseStack(stack);
AddToBottom(stack, top);
}
}
出题：从扑克牌中随机抽出5张牌，判断是否为顺子（顺子则为连续的5张牌，A为1, 2-10为其本身，J为11，Q为12，K为13，大小王可代替任意数字，13在中间的连续不算顺子）；
分析：
- 解法1：首先确认5个数中除0之外没有其他重复的数字，如果有则失败，并且找到最大值max，最小值min和0的个数(count0)；然后如果max-min<=4则成立，否则失败，此方法不用排序；
- 解法2：首先对5个数字进行排序，然后使用king索引最右边的0，使用index遍历king之后的所有元素，一旦遇到next与current有大于 1的差值，则将king向左移动并判断是否超出数组下限，如果超出则返回false；如果next到达数组上限则返回true；
- 解法3：将大小王的大小看做0，首先对5个数字进行排序，然后统计0的个数，然后统计数组中连续数字是否有空缺，如果没有说明有重复出现的牌，则失败；如果空缺数大于统计的0的个数，则说明王不够用于替换所有的空缺，失败；
- 所以判断K个数字是否连续的最直接的方法就是判断其max和min的差值是否小于K个数字；
解题：
/**
* 解法1:
* */
bool BetterVersion(int *array, int length) {
int hash[];
int max=array[],min=array[];
/**
* 使用一个14个元素的int数组表示13个数字和王（0）
* 全部初始化为0
* */
for(int i=;i<;i++)
hash[i]=; for(int i=;i<length;i++) {
if(array[i]==)
hash[]++;
else {
/**
* max和min仅在1到13之间统计
* 并且一旦某个数字出现两次，则失败
* */
if(hash[array[i］ == )
hash[array[i］=;
else
return false;
if(array[i]>max) max=array[i];
if(array[i]<min) min=array[i];
}
}
/**
* 只要max和min相差值小于5，说明肯定可以连续
* */
if(max-min<=) return true;
else return false;
}/**
* 解法2:
* */
bool DetermineJunko(int *array, int length) {
/**
* 使用插入排序对数组进行排序
* */
InsertSort(array, , length-);
/**
* 计算王的个数，使用king索引，缺省值为-1
* */
int king=-;
for(int i=;i<length;i++) {
if(array[i]==)
king++;
else
break;
}
/**
* 从king后面一个位置开始，判断current和next索引
* 的元素是否连续
* 如果是则current和next向右移动
* 如果不是则向左移动king表示使用王替换
* 并且向右移动current和next
* 如果king已经到-1则失败
* 如果next已经到达数组末尾则成功
* */
int current=king+, next=king+, diff=;
while(next < length) {
if(array[current]+==array[next]) {
current++;next++;
} if (array[current]==array[next]) {
return false;
} else {
diff=array[next]-array[current];
for(int i=;i<diff;i++) {
if(king>-) {
king--;
current++;next++;
} else
return false;
}
}
}
return true;
}
最新文章
- 【NopCommerce源码架构学习-二】单例模式实现代码分析
- 使用burpsuite抓android包
- MVC学习之前必须掌握的c#基础知识
- linux软件包的安装和卸载
- mysql-mysql悲观锁和乐观锁
- [Leetcode] Maximum Gap
- C++学习基础六——复制构造函数和赋值操作符
- 每天一个linux命令（40）：watch命令
- 首次push本地代码到github上出现的问题及解决方案
- [改善Java代码]静态变量一定要先声明后赋值
- JavaScript高级程序设计60.pdf
- 移动端web页面使用position:fixed问题总结
- Oracle 常用语句汇总
- js中if的简写方法
- ASP.NET MVC — 第 4 天
- Application的多种值判断测试程序
- MemCache在网站中的使用
- 11 The superlative
- android 开发 View _16 自定义计步器View、自定义柱状图View
- mybatis 返回类型为 java.lang.String 接收为null的情景
热门文章
- (转)Silverlight_5_Toolkit_December_2011 安装后点击Toolkit Samples没反应的解决方法
- 【黑金教程笔记之003】【建模篇】akuei2的Verilog hdl心路
- Pycharm的安装教学
- python爬虫BeautifulSoup库class_
- Unix\Linux | 总结笔记 | 查看文件的方式
- 洛谷 P2062 分队问题
- 在Paint事件中绘制控件（边框）
- ASP.NET Core MVC使用MessagePack配合前端fetch交换数据
- [BZOJ1083][SCOI2005]繁忙的都市 最小生成树
- Vue 学习之el、template、replace和vue的生命周期 参考网址：https://segmentfault.com/a/1190000008010666