每日算法题：Day 15（C/C++）
作者：TeddyZhang，公众号：算法工程师之路
Day 15, C/C++知识点走起~
1
编程题
【剑指Offer】最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：
很多人都觉得这个问题是一个排序问题，但我觉得不一定要排序啊，可以使用堆结构（最小堆），首先将所有的元素都压入到最小堆中，每次弹出最小值就好了，一共弹出k个数。
直接使用STL库中的堆结构，也就是优先级队列！代码就非常简洁了！
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
vector<int> res;
if(input.size() < k) return res; // 返回数值内存大于输入内存，则返回空
for(auto i: input){
pq.push(i);
}
while(k--){
res.push_back(pq.top());
pq.pop();
}
return res;
}
};
当然，只会用库在面试官面前是不行的，接下来我们手动使用vector实现一个最小堆! 文章链接: 从底层实现堆结构和堆排序
这里面我将上面文章中的最大堆改成了最小堆，右一个细节就是：heapify中有一个left+1的边界，如果不满足这个边界，那么必须返回left，而不是left+1。
class Solution {
public:
void heapInsert(vector<int>& list, int index){
while(list[index] < list[(index-1)/]){
swap(list[index], list[(index-1)/]); // 与根节点交换
index = (index-1)/; // 当前位置更新
}
}
// 改变某个值，仍然是最小堆结构
void heapify(vector<int>& list, int index, int heapSize){
int left = index*+;
while(left < heapSize){
int mini = (left + ) < heapSize && list[left] > list[left+]
? left + : left;
// 这个判断错误时只能是left，由于left+1可能出了索引范围
mini = list[mini] < list[index] ? mini : index;
if(mini == index){
break;
}
swap(list[mini], list[index]);
index = mini;
left = index*+;
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(input.size() == ) return res;
if(input.size() < k) return res;
for(int i = ;i < input.size(); i++){
heapInsert(input, i);
}
int heapSize = input.size();
while(k--){
res.push_back(input[]);
swap(input[], input[--heapSize]);
heapify(input, , heapSize);
}
return res;
}
};
【剑指Offer】连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
思路： 遍历这个数组，设置一个累加变量sum，如果sum < 0，那么sum + array[i] 必定小于sum，因此此时sum在本阶段为最大连续子序列，遍历到下一个时，sum更新为array[i]，表示重新开启一个连续子序列！将各个阶段的sum求最大值即可！
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int res = INT_MIN; // 整型的最小值
int sum = ;
for(int i = ; i < array.size(); i++) {
if(sum < ) {
sum = array[i]; // 如果sum小于0，则sum+array[i] < array[i]
} else {
sum += array[i];
}
if(sum > res) {
res = sum;
}
}
return res;
}
};2
概念题
【C/C++】malloc和new的区别？
- malloc和free是标准库函数，支持覆盖；new和delete是运算符，并且支持重载。
- malloc仅仅分配内存空间，free仅仅回收空间，不具备调用构造函数和析构函数功能，用malloc分配空间存储类的对象存在风险；new和delete除了分配回收功能外，还会调用构造函数和析构函数。
- malloc和free返回的是void类型指针（必须进行类型转换），new和delete返回的是具体类型指针。
int *a = (int *)malloc(sizeof(int)); //需要显示指定开辟内存大小，且需要强制类型转换
int *a = new int;
【C/C++】面向对象的三大特性都有哪些？
- 封装性：数据和代码捆绑在一起，避免外界干扰和不确定性访问。一般使用类进行封装！
- 继承性：让某种类型对象获得另一个类型对象的属性和方法。
- 多态性：同一事物表现出不同事物的能力，即向不同对象发送同一消息，不同的对象在接收时会产生不同的行为（重载实现编译时多态，虚函数实现运行时多态），其实质为父类指针指向子类对象，当传递不同对象时，同一个函数的运行结果也不同。
【C/C++】多态原理解析
- 当父类中有了虚函数后，内部结构就发生了变化
- 内部多了一个vfptr（虚函数表指针）,并指向vftable(虚函数表)
- 如果父类中有vfptr，那么子类继承的话会继承vfptr，vftable，在创建对象，即构造函数中会将虚函数表指针vfptr指向自己的虚函数表vftable，此时，如果函数发生了重写，那么在多态时会对原来虚函数表中的函数进行替换，然后就造成了同样一个函数当传入父类和子类时，其函数运行行为是不同的！
3
资源分享
欢迎关注我的个人公众号 （算法工程师之路），公众号内有大量视频资料和电子书资料以及算法笔记，回复关键字即可获取！
公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)
号外，算法刷题群已经建立，但由于人数超出限制，无法扫码添加，可以加号主微信（Leopard7319538）说明来意，可以加入到算法刷题群，每天2道编程题3道概念题，晚9点打卡，我们一起坚持下去！！！
完