每日算法题：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点打卡，我们一起坚持下去！！！

完