算法题7 判断扑克牌中的顺子

题目:

  来源 http://www.cnblogs.com/python27/archive/2011/11/27/2264405.html

  随机抽取扑克牌中的n张牌,判断是不是顺子,即这5张牌是不是连续的。其中A看成1,J看成11,Q看成12,K看成13,大小王可以看成任何需要的数字。

分析:

  对于扑克牌来说,数字范围是很明确的,1到K外加大小王(设定为M)。假如这副牌是个顺子,也就是每张牌都不相同,那么利用一个大小为14的辅助数组counts[]就可以快速的实现排序,记录每张牌出现的次数,然后遍历输出次数为1的值即可。

判断这副牌是不是一个连续数列,需要判断相邻两个数字的差是否为1,大于1的话由M来填充(可以填充两个缺位)。

因为这样一副牌最多不过54张,算法时间复杂度O(1),空间复杂度O(1)

bool IsContinuousPoker(char* pokers,unsigned int n)
{
	if (pokers==NULL||n==0)
		throw std::exception("Invalid input.");

	int *counts=new int[14]();

	char *p=pokers;
	unsigned int num=0;
	while (*p!=‘\0‘)
	{
		if (*p==‘J‘)
			num=11;
		else if (*p==‘Q‘)
			num=12;
		else if (*p==‘K‘)
			num=13;
		else if(*p==‘M‘)
			 num=0;
		else
			num=*p-‘0‘;

		counts[num]++;
		if(num!=0&&counts[num]>1)
			return false;

		p++;
	}

	int pre=0;
	for (int i=1;i<14;i++)
	{
		if (counts[i]==1)
		{
			int dif=i-pre-1;
			if (pre!=0&&dif>0)
			{
				counts[0]-=dif;
				if (counts[0]<0)
					return false;
			}
			pre=i;
		}
	}
	return true;
}

  

时间: 01-28

算法题7 判断扑克牌中的顺子的相关文章

算法题:求数组中最小的k个数

说明:本文仅供学习交流,转载请标明出处,欢迎转载! 题目:输入n个整数,找出其中最小的k个数. <剑指offer>给出了两种实现算法: 算法1:采用Partition+递归法,该算法可以说是快速排序和二分查找的有机结合.算法的时间复杂度为O(n),缺点在于在修改Partition的过程中会修改原数组的值. 算法2:采用top-k算法.如果要找最小的K个数,我们才用一个含有K个值的大顶堆:如果要找最大的K个数,我们采用小顶堆.该算法的时间复杂度为O(nlogK),是一种比较好的算法,启发于堆排序

如何在JS中计算扑克牌中的顺子、对子、半顺、豹子、杂六

1 <!DOCTYPE html> 2 <html> 3 <head> 4 <title>如何计算扑克牌中的顺子.对子.半顺.豹子.杂六</title> 5 <meta charset="utf-8"/> 6 </head> 7 <body> 8 号码1:<input type="number" value="5" id="num1&q

常见算法题:判断表达式括号是否匹配

题目:设计一个算法,判断用户输入的表达式中括号是否匹配,表达式中可能含有圆括号.中括号和大括号. 思路:建立一个顺序栈,当表达式中有左括号时将其入栈,当出现右括号时,将栈顶元素出栈,检查与当前右括号是否匹配.最后如果栈为空则表示该表达式中的括号是匹配的. 代码: #include<iostream> #include<string> using namespace std; #define MaxSize 20 //字符串栈 class Stack { char *data; in

【趣味算法题】在数组中,对于所有元素,找出比当前元素大的下一个元素

在数组中,对于所有元素,找出比当前元素大的下一个元素 意思就是,eg.  数组为 3 1 2 5 4 6 7 那么我们需要得到的结果应该是  5 2 5 6 6 7 -1 解决方法如下: 暴力匹配: O (n ^ 2 ) 的效率对所有元素匹配过去,效率非常的低 经过提示, 我想到的一种 O ( nlg n ) 效率的算法 只需要对数组扫描一次,我们用一个 Priority_queue 来得到当前最小的元素 Prority_queue 存放的数据结构为: struct sc { int key,

算法题:将一个数组中所有奇数放前面和偶数放后面(不开辟新的内存空间)

package arithmetic; import java.util.Arrays; public class OddAndEven { public static void main(String[] args) { int [] a={5,10,26,32,41,7,9,8,4,12,1};; int low = 0; int high = a.length-1; /**想法: * 1.遍历.将奇数放在左边,偶数放在右边 * 2.先遍历左边,直到出现不是奇数的时候为止 * 3.再遍历右边

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

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

每天一道算法题:数字二进制形式中1的个数

题目:请实现一个函数,属于一个整数,输出该数二进制表示中1的个数,例如把9表示成二进制是1001,有2位为1.因此如果输入9,该函数输出2. 可能的死循环陷阱 看完题目,相信大家很快就能想到一个解题思路:先判断整数二进制表示中最右边的一位是否为1,接着把输入的整数右移一位,此时原来处于从右边起的第二位被移动至最右边了,再判断是不是1,这样每次移动一位,直到这个整数变成0,即能够得到整数二进制表示形式中1的个数,而现在问题变为如何判断数字的最后一位为1,其实这个也很简单,只需要将数字与1做与运算,

算法题——翻转链表中的一段

题目:给出一个链表中的两个指针p1和p2,将其之间的结点翻转. 思路:可以通过交换结点内的值来实现结点的翻转,空间为O(N):如果要求不能交换值,那么仅凭p1和p2是无法翻转的,只能交换两个指针之间的链表. 代码: 交换值: 1 struct ListNode 2 { 3 int val; 4 ListNode *next; 5 }; 6 7 void reverseNodes(ListNode *p1, ListNode *p2) { 8 if ( p1 == NULL || p2 == NU

微软算法100题88 将字符串中的字符&#39;*&#39;移到串的前部分

函数将字符串中的字符'*'移到串的前部分,前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回串中字符'*'的数量.如原始串为:ab**cd**e*12,处理后为*****abcde12,函数并返回值为5.(要求使用尽量少的时间和辅助空间) 思路:类似于快速排序,用两个指针分别指向字符数组的左右边界,寻找左边第一个不为*的字符,寻找右边第一个*,然后交换字符,然后继续寻找和交换的过程,直到两个指针相交, 时间复杂度o(n), 空间复杂度o(1) 第一个写的程序有问题,没有考虑到保持