剑指offer例题分享--8

#include<iostream>
#include<stdlib.h>
using namespace std;

int compare(const void *arg1,const void *arg2)
{
    return *(int *)arg1 - *(int *)arg2;
}

bool IsContinuous(int *numbers,int len)
{
    if(numbers==NULL || len<1)
        return false;

    qsort(numbers,len,sizeof(int),compare);

    int    numberOfZero = 0;
    int numberOfGap = 0;

    //统计数组中的间隔数目
    int small = numberOfZero;
    int big = small+1;
    while(big < len)
    {
        //两个数相等，有对子，不可能是顺子
        if(numbers[small] == numbers[big])
            return false;

        numberOfGap += numbers[big]-numbers[small]-1;
        small = big;
        ++big;
    }

    return (numberOfGap>numberOfZero)?false:true;
}

int main()
{
    int data[]={1,2,3,4,9};
    cout << boolalpha << IsContinuous(data,5) << endl;
    
    return 0; 
}

#include<iostream>
#include<list>
using namespace std;

int LastRemaining(unsigned int n,unsigned int m)
{
    if(n<1 || m<1)
        return -1;

    unsigned int i=0;

    //创建双向链表
    list<int> numbers;
    for(i=0;i<n;++i)
        numbers.push_back(i);
    //使用迭代器
    list<int>::iterator current = numbers.begin();
    while(numbers.size() > 1)
    {
        //找到m位置
        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);
}

int main()
{
    cout << "data: " << LastRemaining(5,3) << endl;
    
    return 0;
}

/* 解法一：利用构造函数 */

#include<iostream>
using namespace std;

class Temp{
    private:
        static unsigned int N;
        static unsigned int Sum;
    public:
        //构造函数
        Temp(){++N;Sum+=N;};
        static void Reset(){N=0;Sum=0;}
        static unsigned int GetSum(){return Sum;}
};

unsigned int Temp::N = 0;
unsigned int Temp::Sum = 0;

unsigned int Sum_Solution(unsigned int n)
{
    Temp::Reset();

    //会调用n次
    Temp *a = new Temp[n];
    delete []a;
    a=NULL;

    return Temp::GetSum();
}

int main()
{    
    cout << "sum: " << Sum_Solution(100) << endl;;

    return 0;
}

/* 解法二 用虚函数  */

#include<iostream>
using namespace std;

class A;
A*Array[2];

class A{
    public:
        virtual unsigned int Sum(unsigned int n)
        {
            return 0;
        }
};

class B:public A
{
    public:
        virtual unsigned int Sum(unsigned int n)
        {
            //两次取反，非0的n转换为true
            return Array[!!n]->Sum(n-1) + n;
        }
};

int Sum_Solution(int n){
    A a;
    B b;
    Array[0] = &a;
    Array[1] = &b;

    int value = Array[1]->Sum(n);

    return value;
}

int main()
{
    cout << "sum: " << Sum_Solution(3) << endl;

    return 0;
}

/* 利用函数指针 */

#include<iostream>
using namespace std;

typedef unsigned int (*fun)(unsigned int);

unsigned int Solution_T(unsigned int n)
{
    return 0;
}

unsigned int Sum_Solution(unsigned int n)
{
    static fun f[2] = {Solution_T,Sum_Solution};
    return n + f[!!n](n-1);
}

int main()
{
    cout << "sum: " << Sum_Solution(100) << endl;

    return 0;
}

#include<iostream>
using namespace std;

int Add(int num1,int num2)
{
    int sum,carry;
    do{
        //两个数先求异或，相同为0，相反为1
        sum = num1 ^ num2;
        //相与然后左移一位
        carry = (num1&num2)<<1;

        num1 = sum;
        num2 = carry;
    }while(num2 != 0);

    return num1;
}

int main()
{
    cout << "num: " << Add(1,2) << endl;

    return 0;
}