判断牌是不是顺子

描述：

JQK分别为11，12，13，大小王为0，大小王能替代任意一个数字。

思路：

排序数组。计算0的个数，计算每两个数的间隔的个数。最后比较。

代码：

bool Iscpntinuous(int* numbers, int len)
{
    if (numbers == NULL || len < 1)
        return false;
    sort(numbers, numbers + len);
    int numofzero = 0;
    int numofgap = 0;
    for (int i = 0; i < len && numbers[i] == 0; i++)
    {
        numofzero++;
    }
    int small = numofzero;
    int big = small + 1;
    while (big < len)
    {
        if (numbers[small] == numbers[big])
            return false;
        numofgap += numbers[big] - numbers[small] - 1;
        small = big;
        big++;
    }
    return numofgap <= numofzero ? true : false;
}

圈中最后的数字

思路：

1.用链表模拟圈，每次指针到末尾就自动到开头。

代码：

int LastRemaining(int n, int m)
{
    list<int> numbers;
    for (int i = 0; i < n; i++)
    {
        numbers.push_back(i);
    }
    list<int>::iterator current = numbers.begin();
    while (numbers.size()>1)
    {
        for (int i = 1; i < m; i++)
        {
            current++;
            if (current == numbers.end())
                current = numbers.begin();
        }
        list<int>::iterator next = ++current;
        if (next == numbers.end())
            next = numbers.begin();
        current--;
        numbers.erase(current);
        current = next;
    }
    return *current;
}

数字在排序数组中的个数

思路：

遍历的话时间复杂度为O(n)。既然是排序数组，考虑用二分查找，但每次找到k，要判断它是否是第一个或最后一个k。

代码：

int FindLastK(int arr[], int len, int l, int r, int k)
{
    if (l <= r)
    {
        int mid = (l + r) / 2;
        if (arr[mid] == k)
        {
            if ((mid < len - 1 && arr[mid + 1] != k) || mid == len - 1) 当前k是最后一个
                return mid;
            else
            {
                l = mid + 1;

            }
        }
        else if (arr[mid] < k)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
        return FindLastK(arr, len, l, r, k);
    }
    return -1;
}
int FindFirstK(int arr[], int len, int l, int r, int k)
{
    if (l <= r)
    {
        int mid = (l + r) / 2;
        if (arr[mid] == k)
        {
            if ((mid > 0 && arr[mid - 1] != k) || mid == 0)  //当前k是第一个
                return mid;
            else
            {
                r = mid - 1;

            }
        }
        else if (arr[mid] < k)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
        return FindFirstK(arr, len, l, r, k);
    }
    return -1;
}
int NumberOfK(int arr[], int len,int k)
{
    if (arr == NULL || len <= 0)
        return -1;
    int first = FindFirstK(arr,len,0,len-1,k);
    int last = FindLastK(arr, len,0,len - 1,k);
    if(last>-1&&first>-1)
    return last - first + 1;
    return -1;
}

剑指offer-判断牌是不是顺子，圈中最后的数字，数字在排序数组中的个数

原文：https://www.cnblogs.com/void-lambda/p/12431737.html