####41、扑克牌的顺子
题目: 从扑克牌中随机抽取5张牌, 判断是不是一个顺子, 即这5张牌是不是连续的.2~10为数字本身, A为1, J为11, Q为12, K为13, 而大小王可以看成任意数字.
思路：把大小王视为0，首先把数组排序，再统计数组中0 的个数，最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺的总数小于或者等于0 的个数，那么这个数组就是连续的：反之则不连续。
最后，我们还需要注意一点： 如果数组中的非0 数字重复出现，则该数组不是连续的。换成扑克牌的描述方式就是如果一副牌里含有对子，则不可能是顺子。
bool IsContinuous(int *arr,int len)
{
if(arr==NULL || len<1)
return false;
quick_sort();
int NumOf0 = 0; //0的个数
int NumOfGap = 0; //空缺的个数
int i;
for(i=0;i<len-1;i++)
{
if(arr[i] == 0)
NumOf0++;
else
{
if(arr[i] == arr[i+1])
return false;
else
NumOfGap += arr[i+1]-arr[i]-1;
}
}
return (NumOfGap>NumOf0)?false:true;
}
42、最后剩下的数字
0, 1, … , n-1 这n个数字排成一个圈圈，从数字0开始每次从圆圏里删除第m个数字。求出这个圈圈里剩下的最后一个数字。
解法一
可转换为带环单链表删除结点的问题：创建一个总共有n个结点的环形链表，然后每次在这个链表中删除第m个结点。时间复杂度为O(n*m)，空间复杂度为O(n).
解法二
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2并且从k开始报0。 现在我们把他们的编号做一下转换： k –> 0 k+1 –> 1 k+2 –> 2 … k-2 –> n-2 k-1 –> n-1 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解： 例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，不难推导出：x’=(x+k)%n。 令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]。
相应的递推关系为：
f(1)=0;
f(n)=(f(n-1)+m)%n; (n>1, n∈N)
有了这个公式，我们要做的就是从1-n顺序算出f(i)的数值，最后结果是f(n)。 因为实际生活中编号总是从1开始，我们输出f(n)+1。
注意：此题中m是不变的量，从刚开始输入后就一直不变，而n逐一减小…
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(n<1 || m<1) return -1;
if(n==1) return 0;
return (LastRemaining_Solution(n-1,m)+m)%n;
}
};
class Solution {
public:
int LastRemaining_Solution(unsigned int n, unsigned int m)
{
if(n==0 || m==0) return -1;
if(n==1) return 0;
int last=0; // f(1,x)=0
for(unsigned int i=2; i<=n; i++)
{
last=(last+m)%i;
}
return last;
}
};
43、不用算数运算符实现加法
class Solution
{
public:
int Add(int left, int right)
{
int temp;
while(right != 0)
{
temp = left ^ right; // 计算不带进位的情况
right = (left & right) <<1; // 计算带进位的情况
left = temp;
// now left = 不带进位的情况, right = 带进位的情况
}
return left;
}
};
44、链表中环的结点
题目：如果一个链表中包含环，请找出该链表的环的入口结点。如：在1->2->3->4->5->6->3的链表中，包含一个环，环的入口节点是3。
思路：
- (1) 确定链表中是否包含环：双指针，一个每次移动一步，一个每次移动两步，如果两个指针最后相遇，那么就包含环。且相遇点一定在环中（注意，移动两步的指针要判断判断其第一步不为空，才能移动第二步）
- (2) 确定环中点节点数目：在上面相遇的节点的基础上，移动一个指针，并计数，当指针回到该节点时，确定环中节点数目。
- (3) 找到环的入口节点：从头开始，使用两个指针，第一个指针先移动n步（其中n为确定的环中的节点数目），第二个指针再开始同时移动，两个指针相遇的节点即为入口节点。
// 相遇点
ListNode* MeetingNode(ListNode* pHead){
if(pHead == nullptr) return nullptr;
ListNode* pSlow = pHead->next;
if(pSlow == nullptr) return nullptr;
ListNode* pFast = pSlow->next;
while(pSlow != nullptr && pFast != nullptr){
if(pSlow == pFast) return pFast;
// 慢指针一步
pSlow = pSlow->next;
// 快指针两步
pFast = pFast->next;
if(pFast != nullptr)
pFast = pFast->next;
}
return nullptr;
}
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
// 找到相遇点
ListNode* meetingNode = MeetingNode(pHead);
if(meetingNode == nullptr) return nullptr;
// 找到环的长度
int nodesNumInLoop = 1;
ListNode* pNode1 = meetingNode;
while(pNode1->next != meetingNode){
pNode1 = pNode1->next;
++nodesNumInLoop;
}
// 找到入口
pNode1 = pHead;
for(int i=0; i<nodesNumInLoop; ++i)
pNode1 = pNode1->next;
ListNode* pNode2 = pHead;
while(pNode1 != pNode2){
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}
45、删除重复结点
题目：删除链表中的重复结点
ListNode* deleteDuplication(ListNode* pHead)
{
//设置一个trick, 作为头指针, 这样我们无需单独考虑第一个元素
ListNode *first = new ListNode();
first->next = pHead;
ListNode *p = pHead;
ListNode *last = first;
while (p != NULL && p->next != NULL)
{
// 如果有元素重复
if (p->val == p->next->val)
{
// 就跳过所有重复的数字
int val = p->val;
while (p != NULL && p->val == val)
{
p = p->next;
}
// 此时p指向了非重复的第一个元素
// 我们设置last->next = p
// 但是此时p-val也可能是重复的,
// 因此我们不可以设置last = p
// 而是重新进入循环
last->next = p;
}
else
{
last = p;
p = p->next;
}
}
return first->next;
};