劍指offer例題分享--8

　　前言：繼續分享，加油！

　　面試題44：

　　

　　代碼如下：

#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; 
}      

　　面試題45：

#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;
}      

　　面試題46：

　　這道題用是三種方法給大家示範：

　　方法一：構造函數

/* 解法一：利用構造函數 */

#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;
}      

　　面試題47：

#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;
}      

　　總結：經過很長一段時間才把這本書看完并碼代碼，收獲很多，資料結構和算法之路才剛剛開始，學習之路還很長，希望對各位能有所幫助。繼續加油...,夢想還是要用有的，萬一見鬼了呢！

作者：

柳德維

出處：

https://www.cnblogs.com/liudw-0215/

-------------------------------------------

個性簽名：獨學而無友，則孤陋而寡聞。做一個靈魂有趣的人！

如果覺得這篇文章對你有小小的幫助的話，記得在右下角點個“推薦”哦，部落客在此感謝！

萬水千山總是情，打賞一分行不行，是以如果你心情還比較高興，也是可以掃碼打賞部落客，哈哈哈(っ•̀ω•́)っ⁾⁾！