每日算法题：Day 22（C/C++）
作者：TeddyZhang，公众号：算法工程师之路
Day 22, C/C++知识点走起~
1
编程题
【剑指Offer】反转字符串
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
思路： 使用STL中的find函数来查找每个空格的位置，由于find函数只能查找一个位置，因此我们使用循环，每当查找结束后，将查找的出发点begin赋值为end+1，接着就可以查找到下一个空格的位置了，这样就可以得到STL版的split函数，虽然比较麻烦，但是C++标准库是没有split函数的，必须这么写！接着就是reverse函数进行反转，可以直接使用库函数！当然自己也可以使用swap函数利用首尾指针实现！
class Solution {
public:
string ReverseSentence(string str) {
reverse(str.begin(), str.end()); // 整体反转
int begin = , end;
while((end=str.find(' ', begin)) != string::npos){
reverse(str.begin()+begin, str.begin()+end);
begin = end + ;
}
reverse(str.begin()+begin, str.end()); // 最后一个空格到最后字符串结束
return str;
}
};
【剑指Offer】扑克牌顺子
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
思路： 这道题目是比较长，接近于实际笔试题目的长度，所以需要快速的获取信息，从题中得知其主要判断一个数组是不是顺子，其中大小王为0。我们首先对整个数组进行排序，并设置一个变量cntNeed用来储存如果这个数组是一个顺子，则需要多少个大小王，然后遍历整个数组，计算相邻两个数的差-1，并累加。也就是说如果是顺子，那么其相加和为0，表示需要0个大小王！
在遍历的同时使用cntZero记录大小王的个数，最后判断cntNeed和cntZero的大小，如果Need > Zero,那么就返回false.还有一点需要注意，如果存在不为零的数重复，那么此序列必不是顺子！
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
int len = numbers.size();
if(len == ) return false; // numbers为空的情况
sort(numbers.begin(), numbers.end());
int cntZero = , cntNeed = ;
for(int i = ;i < len; i++){
if(numbers[i] == ){
cntZero++; // 大小王的数量
}else if(i+ < len){
if(numbers[i+] == numbers[i]) return false;
cntNeed += numbers[i+]-numbers[i]-1; // 若形成顺子需要大小王的个数为cntNeed
}
}
if(cntNeed > cntZero) return false;
return true;
}
};2
概念题
【C/C++】范围解析运算符（::）的使用总结
全局作用域符（::name）：用于类型名称（类、类成员、成员函数、变量等）前，表示作用域为全局命名空间 类作用域符（class::name）：用于表示指定类型的作用域范围是具体某个类的 命名空间作用域符（namespace::name）:用于表示指定类型的作用域范围是具体某个命名空间的
int count = ; // 全局（::）的 count
class A {
public:
static int count; // 类 A 的 count（A::count）
};
int main() {
::count = ; // 设置全局的 count 的值为 1
A::count = ; // 设置类 A 的 count 为 2
int count = ; // 局部的 count
count = ; // 设置局部的 count 的值为 3
return ;
}
【C/C++】静态多态和动态多态的区别？
静态动态（编译期/早绑定） 使用函数重载的方式，如下代码：
class A
{
public:
void do(int a);
void do(int a, int b);
};
动态多态（运行期/晚绑定） 使用virtual修改成员函数，使其变成虚函数！
class Shape // 形状类
{
public:
virtual double calcArea()
{
...
}
virtual ~Shape();
};
class Circle : public Shape // 圆形类
{
public:
virtual double calcArea();
...
};
class Rect : public Shape // 矩形类
{
public:
virtual double calcArea();
...
};
int main()
{
Shape * shape1 = new Circle(4.0);
Shape * shape2 = new Rect(5.0, 6.0);
shape1->calcArea(); // 调用圆形类里面的方法
shape2->calcArea(); // 调用矩形类里面的方法
delete shape1;
shape1 = nullptr;
delete shape2;
shape2 = nullptr;
return ;
}
【C/C++】虚函数在使用中的限制
- 普通函数不能是虚函数，也就是说这个函数必须是某一个类的成员函数，不可以是一个全局函数，否则会导致编译错误。
- 静态成员函数不能是虚函数 , static成员函数是和类同生共处的，他不属于任何对象，使用virtual也将导致错误。
- 内联函数不能是虚函数, 如果修饰内联函数 如果内联函数被virtual修饰，计算机会忽略inline使它变成存粹的虚函数。这是由于inline函数在编译时内联，而虚函数多态发生在运行期！
- 构造函数不能是虚函数，由于虚函数中的虚指针表是在构造后创建的，因此在构造时，虚表指针并没有存在于内存对象当中！