面试准备
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、工厂设计模式，如何实现，以及它的优点
- 工厂设计模式的定义 定义一个创建对象的接口，让子类决定实例化哪个类，而对象的创建统一交由工厂去生产，有良好的封装性，既做到了解耦，也保证了最少知识原则。
- 工厂设计模式分类 工厂模式属于创建型模式，大致可以分为三类，简单工厂模式、工厂方法模式、抽象工厂模式。
#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++实现中，就是要定义一个个的工厂类。显然，相比简单工厂模式，工厂方法模式需要更多的类定义。