首页 > 代码库 > 笔试算法题(21):将stack内外颠倒 & 判断扑克牌顺子

笔试算法题(21):将stack内外颠倒 & 判断扑克牌顺子

出题:要求用递归将一个栈结构的元素内外颠倒;

分析:

  • 本题再次说明系统栈是程序员最好的帮手,但递归度较高所以时间复杂度较大,可以使用空间换时间的方法(额外数组保存栈元素,然后逆向压入);
  • 第一层递归(清空栈元素,并使用系统栈保存):[1,2,3,4,5],栈顶元素为1,将1弹出之后,递归处理[2,3,4,5];
  • 第二层递归(将栈顶元素插入到栈底,同样使用系统栈保存):当[2,3,4,5]已经逆序之后,需要将1插入到栈底,所以将1作为参数传递到递归调用中,之后递归处理2和[3,4,5];

解题:

 1 class MyStack {
 2 private:
 3         int *array;
 4         int capability;
 5         int top;
 6 public:
 7         MyStack(int cap=5): array((int*)malloc(sizeof(int)*cap)), capability(cap), top(0) {}
 8         ~MyStack() {delete [] array;}
 9 
10         bool isFull() {
11                 return top == capability;
12         }
13         bool isEmpty() {
14                 return top == 0;
15         }
16         int freeSlot() {
17                 return capability - top;
18         }
19         /**
20          * top当前的位置就是下一个push元素所在的slot
21          * */
22         bool push(int n) {
23                 if(isFull()) return false;
24                 array[top++]=n;
25                 return true;
26         }
27         bool pop(int *n) {
28                 if(isEmpty()) return false;
29                 *n=array[--top];
30                 return true;
31         }
32         void ShowStack() {
33                 int temp=top-1;
34                 printf("\n");
35                 for(int i=0;i<=temp;i++)
36                         printf("%d, ",array[i]);
37                 printf("\n");
38         }
39 };
40 void AddToBottom(MyStack *stack, int top) {
41         int curTop;
42         if(stack->pop(&curTop)) {
43                 AddToBottom(stack, top);
44                 stack->push(curTop);
45         }else
46                 stack->push(curTop);
47 }
48 void ReverseStack(MyStack *stack) {
49         int top;
50         if(stack->pop(&top)) {
51                 ReverseStack(stack);
52                 AddToBottom(stack, top);
53         }
54 }

 

出题:从扑克牌中随机抽出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 /**
 2  * 解法1:
 3  * */
 4 bool BetterVersion(int *array, int length) {
 5         int hash[14];
 6         int max=array[0],min=array[1];
 7         /**
 8          * 使用一个14个元素的int数组表示13个数字和王(0)
 9          * 全部初始化为0
10          * */
11         for(int i=0;i<14;i++)
12                 hash[i]=0;
13         
14         for(int i=0;i<length;i++) {
15                 if(array[i]==0)
16                         hash[0]++;
17                 else {
18                         /**
19                          * max和min仅在1到13之间统计
20                          * 并且一旦某个数字出现两次,则失败
21                          * */
22                         if(hash[array[i] == 0)
23                                 hash[array[i]=1;
24                         else
25                                 return false;
26                         if(array[i]>max) max=array[i];
27                         if(array[i]<min) min=array[i];
28                 }
29         }
30         /**
31          * 只要max和min相差值小于5,说明肯定可以连续
32          * */
33         if(max-min<=4) return true;
34         else return false;
35 }/**
36  * 解法2:
37  * */
38 bool DetermineJunko(int *array, int length) {
39         /**
40          * 使用插入排序对数组进行排序
41          * */
42         InsertSort(array, 0, length-1);
43         /**
44          * 计算王的个数,使用king索引,缺省值为-1
45          * */
46         int king=-1;
47         for(int i=0;i<length;i++) {
48                 if(array[i]==0)
49                         king++;
50                 else
51                         break;
52         }
53         /**
54          * 从king后面一个位置开始,判断current和next索引
55          * 的元素是否连续
56          * 如果是则current和next向右移动
57          * 如果不是则向左移动king表示使用王替换
58          * 并且向右移动current和next
59          * 如果king已经到-1则失败
60          * 如果next已经到达数组末尾则成功
61          * */
62         int current=king+1, next=king+2, diff=0;
63         while(next < length) {
64                 if(array[current]+1==array[next]) {
65                         current++;next++;
66                 } if (array[current]==array[next]) {
67                         return false;
68                 } else {
69                         diff=array[next]-array[current];
70                         for(int i=1;i<diff;i++) {
71                                 if(king>-1) {
72                                         king--;
73                                         current++;next++;
74                                 } else
75                                         return false;
76                         }
77                 }
78         }
79         return true;
80 }