[C++后台开发面经]面试总结第四波:笔试面试算法题总结

前言

        面试总结第四波,主要针对面试时要求编写的算法编程题总结。

C++面试笔试算法题合集

1、之字形打印二叉树

vectorvectorint print(TreeNode *node){
    vectorvectorint res;
    if(!node) return res;
    queueTreeNode* q;
    q.push(node);
    int flag=false;
    
    while(q.size()){
        int len=q.size();
        vectorint line;
        for(int i=0;ilen;i++){
            auto p=q.front();
            line.push_back(p-val);
            if(p-left) q.push(p-left);
            if(p-right) q.push(p-right);
            q.pop();
        }
        if(flag){
            reverse(line.begin(),line.end());
        }
        flag=!flag;
        res.push_back(line);
    }
}

2、K路归并有序链表

ListNode* mergeKList(vectorListNode* lists){
    
    priority_queuepairint,ListNode*,vectorpairint,ListNode*,greaterpairint,ListNode* pq;
    
    for(auto p:lists){
        if(p) pq.push({p-val,p});
    }
    
    auto pre=new ListNode(-1);
    auto cur=pre;
    while(pq.size()){
        auto t=pq.top();
        if(t.second-next) pq.push({t.second-next-val,t.second-next});
        cur-next=t.second;
        cur=cur-next;
        pq.pop();
    }
    return pre-next;
}

3、简单实现一个LRU

class LRUCache{
private:
    int n;
    listpairint,int l;
    unordered_mapint,listpairint,int::iterator hash;
public:
    LRUCache(int capacity){
        n=capacity;
    }
    
    int get(int key){
        int ret=-1;
        auto iter=hash.find(key);
        if(iter!=hash.end()){
            auto temp=hash[key];
            ret=temp-second;
            l.erase(temp);
            l.push_front({key,ret});
            hash[key]=l.begin();
        }
        return ret;
    }
    
    void put(int key,int value){
        auto iter=hash.find(key);
        if(iter!=hash.end()){//缓存中有此数据,先删掉
            l.erase(iter-second);
        }
        else if(l.size()n){
            
        }
        else{
            int key=l.back().first;//缓存中没有此数据,且已超过n,删除链表最后值
            l.pop_back();
            hash.erase(key);
        }
        l.push_front({key,value});//把新数据放到链表首
        hash[key]=l.begin();
    }
};

4、正则字符匹配(?和*)

bool isMatch(string s,string p){
    int n=s.size(),m=p.size();
    vectorvectorbool f(n+1,vectorbool(m+1));
    
    for(int i=0;i=n;i++){
        for(int j=0;j=m;j++){
            
            if(!i!j){//空串匹配空串
                f[i][j]=true;
                continue;
            }
            if(!j){ //正则表达式为空
                f[i][j]=false;
                continue;
            }
            if(p[j-1]!='*'){
                if(i0(p[j-1]=='?'||s[i-1]==p[j-1])) f[i][j]=f[i][j]||f[i-1][j-1];
            }
            else{
                f[i][j]=f[i][j]||f[i][j-1]; //忽略
                if(i0) f[i][j]=f[i][j]||f[i-1][j];  //不忽略
            }
        }
    }
    
    return f[n][m];
}

5、单次买卖股票最大利润

6、二叉树非递归后序遍历

7、循环队列

8、删除一个平衡二叉树的非叶子节点

9、KMP算法

10、超大数组去重,排序

11、编写一个扑克牌洗牌程序

12、快速排序非递归

void quick_sort(vectorint q){
    int n=q.size();
    stackint s;
    int top=0;
    int i,j,high,low,provit;
    s.push(n-1);  //high
    s.push(0);   //low
    while(s.size()){
        low=s.top(),s.pop();  //把右端点压入栈中
        high=s.top(),s.pop();  //把左端点压入栈中
        provit=high;   //选中右端点为中心轴
        i=low;     
        for(j=low;jhigh;j++){ //遍历,把小于的部分放在前面
            if(q[j]=q[provit]){
                swap(q[j],q[i++]);
            }
        }
        if(i!=provit){ //交换中心轴
            swap(q[i],q[provit]);
        }
        if(i-low1){ //若前半部分个数大于1个,则入栈
            s.push(i-1);
            s.push(low);
        }
        if(high-i1){ //若后半部分个数大于1个,则入栈
            s.push(high);
            s.push(i+1);
        }
    }
}

 

最新回复(0)
/jishusJb5ma0U6NanbMq_2FXGxVu4gecCODJ2r9YVqePMW_2BDHQ_3D4672150
8 简首页