C++算法三及设计模式

双指针学习：双指针或者两个下标(下标也是指针),来协同完成任务；
1）双指针的第一个用法，两个指针，方向相反：
程序案例：查找一个升序数组里面的两个数之和，等于一个目标数，并返回两个数所在数组的位置；
//两个指针，方向相反代码如下：

#include
#include
#include

using namespace std;
int* towNum(int data[],int size,int target)
{
    int i = 0;
    int j = size - 1;
    while(i < j)
    {
        int sum = data[i] + data[j];
        if(sum == target) break;
        if(sum < target)
        {
            i++;
        }
        else
        {
            j--;
        }
        if(i > j)
            return nullptr;
    }
    int* ret = (int*)malloc(sizeof(int) * 2);
    ret[0] = i + 1;
    ret[1] = j + 1;
    return ret;
}
int main(void)
{
    int data[] = {2,7,11,15,18,30};
    int target = 29;
    int* ret = towNum(data,sizeof(data)/sizeof(data[0]),target);
    if(ret)
    {
        printf("%d %d\n",ret[0],ret[1]);
    }
    else
    {
        printf("no find\n");
    }
    return 0;
}

测试代码结果：

3 5

2)双指针的第二个用，两个指针，方向相同
案例分析：//实现两个数组的合并,合并后的新数组，保持有序

#include
#include
#include

using namespace std;

int* merge(int num1[], int m, int num2[], int n)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int* ret = (int*)malloc(sizeof(int)*(m + n));
    while(i < m && j < n)
    {
        if(num1[i] < num2[j])
        {
            ret[k++] = num1[i++];
        }
        else
        {
            ret[k++] = num2[j++];
        }
    }
    while(i < m)
    {
        ret[k++] = num1[i++];
    }
    while(i < n)
    {
        ret[k++] = num2[j++];
    }
    return ret;
}
int main(void)
{
    int data1[] = {2,7,11,15,20,25,56,59}; //数组1
    int data2[] = {1,2,3,12,18}; //数组2
    int* ret = merge(data1,sizeof(data1)/sizeof(data1[0]),data2,sizeof(data2)/sizeof(data2[0]));
    int num = sizeof(data1)/sizeof(data1[0]) + sizeof(data2)/sizeof(data2[0]);
    for(int i = 0; i < num; i++)
    {
        printf("%d ",ret[i]);
    }
    return 0;
}

测试输出结果如下：

1 2 2 3 7 11 12 15 18 20 25 56 59 //两个数组合并，依然保持数组有序

3）C++设计模式中，策略模式的应用案例
应用场景：strategy及其子类为组件提供了一系列可重用的算法，从而使得类型在运行时方便的根据需要在各个算法之间进行切换；
测试代码如下：

#include
#include
#include

using namespace std;
//策略模式
//武器策略
class WeaponStrategy
{
public:
    virtual void UseWeapon() = 0;
    virtual ~WeaponStrategy(){ }
};

class Knife : public WeaponStrategy
{
public:
    virtual void UseWeapon()
    {
        cout<<"using knife-------"<<endl;
    }
};

class AK47 : public WeaponStrategy
{
public:
    virtual void UseWeapon()
    {
        cout<<"using AK47*********"<<endl;
    }
};

class Person
{
public:
    void setWeapon(WeaponStrategy* weapon)
    {
        this->pWeapon = weapon;
    }
    void RunWeapon()
    {
        this->pWeapon->UseWeapon();
    }
public:
    WeaponStrategy* pWeapon;
};

int main(void)
{
    //创建一个人
    Person* person = new Person;
    //武器策略
    WeaponStrategy* knife = new Knife;
    WeaponStrategy* ak47 = new AK47;

    person->setWeapon(knife);
    person->RunWeapon();

    person->setWeapon(ak47);
    person->RunWeapon();

    delete ak47;
    delete knife;
    delete person;
    return 0;
}

测试输出结果：

using knife-------
using AK47*********

4）C++设计模式中，模板方法模式的应用案例
定义一个 *** 作中的算法的骨架（稳定），而将一些步骤的实现延迟（变化）到子类中。Template Method使得子类可以不改变（复用）一个算法的结构即可重定义（override重写）该算法的某些特定步骤：
案例代码如下：

#include
#include
#include

using namespace std;
//模板方法模式

class DrinkTemplate
{
public:
    virtual void BoilWater() = 0; //煮水
    virtual void Brew() = 0; //冲泡
    virtual void PourInCup() = 0; //导入杯中
    virtual void AddSomething() = 0; //加入辅料

    //模板方法
    void Make()
    {
        BoilWater();
        Brew();
        PourInCup();
        AddSomething();
    }
};

class Coffee : public DrinkTemplate
{
    virtual void BoilWater()
    {
        cout<<" good water--"<<endl;
    }
    virtual void Brew()
    {
        cout<<" brew caffee--"<<endl;
    }
    virtual void PourInCup()
    {
        cout<<" coffee input cup--"<<endl;
    }
    virtual void AddSomething()
    {
        cout<<" add lomen-----orange--"<<endl;
    }
};

class Tea : public DrinkTemplate
{
    virtual void BoilWater()
    {
        cout<<" bad water--"<<endl;
    }
    virtual void Brew()
    {
        cout<<" brew Tea--"<<endl;
    }
    virtual void PourInCup()
    {
        cout<<" Tea input cup--"<<endl;
    }
    virtual void AddSomething()
    {
        cout<<" add lomen- jiang ----orange--"<<endl;
    }
};

int main(void)
{
    Tea tea;
    DrinkTemplate* drink = &tea;
    drink->Make();

    cout<<"-----------------------------"<<endl;

    Coffee coffee;
    drink = &coffee;
    drink->Make();
    return 0;
}

案例测试结果：

 bad water--
 brew Tea--
 Tea input cup--
 add lomen- jiang ----orange--
-----------------------------
 good water--
 brew caffee--
 coffee input cup--
 add lomen-----orange--