面试准备

1、正整数n的操作有两类:如果n为奇数，可以加1或者减1；如果n为偶数，可以除以2。设计一个函数，求出最少需要多少次操作使得n=1？

用二进制去处理。关键是如何判断在n为奇数时到底是加1还是减1。自己找两个例子分析一下就可以发现规律，当n的二进制码的最后3位是‘111’时，需要加1。其他奇数情况需要减1。偶数情况下，当然是除以2了。

int count_Operation(int n)
{
	//计数操作次数
	int count=0;
	//主要是在n为奇数的情况下，如何判断
	//是执行+1操作还是-1操作
	while (n!=1)
	{
		if((n&0x111)==0x111)
			n+=1;
		else if ((n&0x1)==0x1)
			n-=1;
		else
			n/=2;
		count++;
	}
	return count;
}

2、仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

class MyQueue {
    stack<int> instack,outstack;
    void in2out() {
        while(!instack.empty()) {
           outstack.push(instack.top());
            instack.pop();
        }
    }
public:
    MyQueue() {}
    
    void push(int x) {
        instack.push(x);
    }
    
    int pop() {
        if(outstack.empty()){
            in2out();
        }
        int x = outstack.top();
        outstack.pop();
        return x;
    }
    
    int peek() {
        if(outstack.empty()){
            in2out();
        }
        return outstack.top();
    }
    
    bool empty() {
        return instack.empty() && outstack.empty();
    }
};

3、请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

class MyStack {
private:
    queue<int> queue1;
    queue<int> queue2;
public:
    MyStack() {}
    
    void push(int x) {
        queue2.push(x);
        while(!queue1.empty()){
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }
    
    int pop() {
        int r = queue1.front();
        queue1.pop();
        return r;
    }
    
    int top() {
        return queue1.front();
    }
    
    bool empty() {
        return queue1.empty();
    }
};

4、工厂设计模式，如何实现，以及它的优点

1. 工厂设计模式的定义    定义一个创建对象的接口，让子类决定实例化哪个类，而对象的创建统一交由工厂去生产，有良好的封装性，既做到了解耦，也保证了最少知识原则。
2. 工厂设计模式分类    工厂模式属于创建型模式，大致可以分为三类，简单工厂模式、工厂方法模式、抽象工厂模式。

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

class Product{
public:
    virtual void Show() = 0;
};

class CreateProductA : public Product {
public:
    void Show(){
        cout << "create product A" << endl;
    }
};

class CreateProductB : public Product {
public:
    void Show(){
        cout << "create product B" << endl;
    }
};

class SimpleFactory {
public:
    static unique_ptr<Product> CreateProduct(const string& type){
        if(type == "A"){
            return make_unique<CreateProductA>();
        } else if (type == "B"){
            return make_unique<CreateProductB>();
        } else {
            return nullptr;
        }
    }
};

int main(){
    auto ProductA = SimpleFactory::CreateProduct("A");
    ProductA->Show();

    auto ProductB = SimpleFactory::CreateProduct("B");
    ProductB->Show();

    return 0;
}
//优点： 简单工厂模式可以根据需求，动态生成使用者所需类的对象，而使用者不用去知道怎么创建对象，使得各个模块各司其职，降低了系统的耦合性。    
//缺点：就是要增加新的核类型时，就需要修改工厂类。这就违反了开放封闭原则：软件实体（类、模块、函数）可以扩展，但是不可修改。

#include<iostream>
#include<memory>
using namespace std;
class Product{
public:
    virtual void Show() = 0;
};

class CreateProductA : public Product {
public:
    void Show(){
        cout << "create product A" << endl;
    }
};

class CreateProductB : public Product {
public:
    void Show(){
        cout << "create product B" << endl;
    }
};

class Factory{
public:
    virtual unique_ptr<Product> CreateProduct() = 0;
};

class FactoryA : public Factory{
public:
     unique_ptr<Product> CreateProduct(){
        return make_unique<CreateProductA>();
    }
};
class FactoryB : public Factory{
public:
     unique_ptr<Product> CreateProduct(){
        return make_unique<CreateProductB>();
    }
};

int main() {
    unique_ptr<Factory> factoryA = make_unique<FactoryA>();
    auto productA = factoryA->CreateProduct();
    productA->Show();

    unique_ptr<Factory> factoryB = make_unique<FactoryB>();
    auto productB = factoryB->CreateProduct();
    productB->Show();

    return 0;
}
//优点： 扩展性好，符合了开闭原则，新增一种产品时，只需增加改对应的产品类和对应的工厂子类即可。    
//缺点：每增加一种产品，就需要增加一个对象的工厂。如果这家公司发展迅速，推出了很多新的处理器核，那么就要开设相应的新工厂。在C++实现中，就是要定义一个个的工厂类。显然，相比简单工厂模式，工厂方法模式需要更多的类定义。