头像

努力刷题的小旋




离线:8小时前



一面

项目介绍,项目中遇到的困难

1.说一下STL中的vector的扩容机制

扩容方式:
1、倍数开辟二倍的内存
2、旧的数据开辟到新内存
3、释放旧的内存
4、指向新内存

2. 了解哪些STL容器?

  • vector-数组,list-链表,deque-分配中央控制器map(并非map容器),map记录着一系列的固定长度的数组的地址.
  • map-红黑树,unordered_map-哈希表。

3. 你刚才说了map和unordered_map,说一下他们查找的时间复杂度?

  • map->采用红黑树实现,红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:插入: O(logN);查找:O(logN);删除:O(logN)
  • unordered_map->采用哈希表实现,不同操作的时间复杂度为:插入:O(1)查找看:O(1);删除:O(1)。

4. 刚才有说了deque,那deque在头尾插入、删除和访问的时间复杂度呢?

deque的push_back, push_front, pop_back, pop_front操作时间复杂度为O(1);访问O(1).

5. 数组和链表区别.

  • 数组的存储区间是连续的,查询简单,增加和删除困难.
  • 链表是一种物理存储单元上非连续、非顺序的存储结构,查询相对于数组困难,增加和删除容易。

6.平时写算法题多不?

7. STL项目中用哪个比较多?

刷题的时候vector和stack用的多......

8.那就用stack实现一个队列吧

相关题目(用栈实现队列),这里只讲了思路就好。

9. 手撕代码:区间合并, [3,5],[4,6],[7,9]-> [3,6],[7,9]

广告一波->算法基础课第一讲(PS:Y总太强了) 区间合并
先说思路:
1.左端点排序。
2.然后比较是否有相交的区间,然后再进行合并。具体可以去看基础课讲的。

然后分析了一下时间复杂度,因为用到了排序,时间复杂度为O(NlogN).然后面试官说有没有时间复杂度更小的方法,说用可以用空间来换时间,这个我就不太懂了。zzz




一面

代码题:括号匹配(LeetCode原题)( LeetCode 20

//自己写的~
#include <algorithm>
#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool isvalid(string &s)
{
    stack<char> stk;
    for(int i = 0 ; i < s.size(); i++)
    {
        if(stk.empty() || s[i] =='(')
        {
            stk.push(s[i]);
        }
        else if(s[i] == ')')
        {
            if(stk.top() != '(')
            {
                return false;
            }
            else 
                stk.pop();
        }
    }
    return stk.empty();
}

int main()
{
    string s;
    cin >> s;
    bool flag = isvalid(s);
    if(flag)
        cout << "true"<<endl;
    else
    {
        cout << "false"<<endl;
    }
    return 0;

}

项目详细介绍

select和epoll的区别?

select底层是用数组实现,有最大文件描述符限制,而epoll底层使用红黑树实现,突破了最大文件描述符的限制。
select采用轮询的方式,而epoll则使用回调的方式…

二面

代码题1:生成一个m到n的随机数

int get_random(int m, int n)
{
    int t = rand();
    if(t < m)
    {
        return (t + m)%m + m;
    }
    else if(t > n)
    {
        return (t % n) + m;
    }
    else return t;
}

代码题2:斐波那契数列递归写法

int f(int n)
{
    if(n == 1)
        return 1;
    if(n == 2)
        return 1;
    return f(n-1)+f(n-2);
}

代码题3:实现一个string类,构造函数,拷贝构造函数,拷贝赋值运算符

//这个好像写的不太好,但也能跑通...
class String{
public:
    String(int n=1);
    String(const char *s);
    String(const String &s);

    ~String();

// private:
    char *m_char;

};

String::String(int n)
{
    if(n == 1)
    {
        m_char = new char[1];
        m_char[0]='\0';
    }
    else
    {
        m_char = new char[n+1];
    }
}

String::String(const char *s)
{
    int len = strlen(s);
    m_char = new char[len+1];
    for(int i = 0; i <= len; i++)
        m_char[i] = s[i];
}
String::String(const String &s)
{
    if(s.m_char == NULL)
        return ;
    int len = strlen(s.m_char);
    m_char = new char[len+1];
    strcpy(m_char, s.m_char);
}

String::~String()
{
    delete[] m_char;
}

C++重载和重写的区别

重载overload:在同一个类中,函数名相同,参数列表不同,编译器会根据这些函数的不同参数列表,将同名的函数名称做修饰,从而生成一些不同名称的预处理函数,未体现多态。

重写override:也叫覆盖,子类重新定义父类中有相同名称相同参数的虚函数,主要是在继承关系中出现的,被重写的函数必须是virtual的,重写函数的访问修饰符可以不同,尽管virtual是private的,子类中重写函数改为public,protected也可以,体现了多态。

拓展:隐藏
重定义redefining:也叫隐藏,子类重新定义父类中有相同名称的非虚函数,参数列表可以相同可以不同,会覆盖其父类的方法,未体现多态。

a如果派生类的函数和基类的函数同名,但是参数不同,此时,不管有无virtual,基类的函数被隐藏。

b如果派生类的函数与基类的函数同名,并且参数也相同,但是基类函数没有vitual关键字,此时,基类的函数被隐藏。(如果有virtual就成重写了)

C++智能指针

shared_ptr:允许多个指针指向同一个对象。每个shared_ptr都要一个关联的计数器,称为引用计数。无论何时,我们拷贝一个shared_ptr,计数器都会递增。当我们给shared_ptr赋予一个新值或是shared_ptr被销毁时,计数器就会递减。一旦计数器变成0,就会自动释放自己所管理的对象。

unique_ptr则独占所指向的对象。某个时刻只能有一个unique_ptr指向一个给定对象。当unique_ptr被销毁时,它所指向的对象也被销毁。当我们定义一个unique_ptr时,需将其绑定到一个new返回的指针上,直接初始化。

weak_ptr伴随类,是一种弱引用,指向shared_ptr所管理的对象。不会改变shared_ptr的引用计数。

是否了解数据库




一面

C++,C和python的区别?

C和C++是编译型语言,python是解释型语言。编译型和解释型,在编程时的最大区别是必不必要写一个入口函数,在C语言里是 main,而 Python 可以不写。
编译型的优点是“静态”,代码不能一行一行编译执行,必须作为整个工程来编译,这样便于类型检查,降低运行时错误率;运行时效率更高,因为编译器可以统筹各个方面,生成更优化的机器指令;一经编译便可直接以机器语言再次执行。
解释型语言的优点是“动态”,代码的每一行可独立执行(代码块除外)。这样就可以灵活地进行实时交互,调整正在运行的程序,进行实时、异步的调试。比如 Python 的 CLI(命令行交互界面)就可以直接输入 Python 代码执行。

C,C++ 是弱类型、静态类型检查的,Python 是强类型、动态类型检查的。
强类型:偏向于不容忍隐式类型转换
弱类型:偏向于容忍隐式类型转换
静态类型: 编译的时候就知道每一个变量的类型,因为类型错误而不能做的事情是语法错误。
动态类型:编译的时候不知道每一个变量的类型,因为类型错误而不能做的事情是运行时错误。

c/c++ -> bin,中间经历了哪些过程?介绍每个过程,以及优化的时候在什么过程优化?

源代码-->预处理-->编译-->优化-->汇编-->链接–>可执行文件

预处理:读取c源程序,对其中的伪指令(以#开头的指令)和特殊符号进行处理。宏定义指令;条件编译指令;头文件包含指令;特殊符号。 预编译程序所完成的基本上是对源程序的“替代”工作。经过此种替代,生成一个没有宏定义、没有条件编译指令、没有特殊符号的输出文件

编译:经过预编译得到的输出文件中,将只有常量。如数字、字符串、变量的定义,以及C语言的关键字,如main,if,else,for,while,{,},+,-,*,\,等等。预编译程序所要作得工作就是通过词法分析和语法分析,在确认所有的指令都符合语法规则之后,将其翻译成等价的中间代码表示或汇编代码。

优化阶段。优化阶段在编译阶段做。经过优化得到的汇编代码必须经过汇编程序的汇编转换成相应的机器指令,方可能被机器执行。

extern关键字的作用?

  1. extern用在变量或者函数的声明前,用来说明“此变量/函数是在别处定义的,要在此处引用”。
  2. extern C表示此段代码使用C语言的方式进行编译。由于C++支持函数重载,因此编译器编译函数的过程中会将函数的参数类型也加到编译后的代码中,而不仅仅是函数名;而C语言并不支持函数重载,因此编译C语言代码的函数时不会带上函数的参数类型,一般只包括函数名。具有函数名匹配的功能。

static关键字的作用

  1. 函数中的静态变量。当变量声明为static时,空间将在程序的生命周期内分配。
  2. 类中的静态变量。声明为static的变量只被初始化一次,因为它们在单独的静态存储中分配了空间,因此类中的静态变量由对象共享。它是属于类的。静态变量不能使用构造函数初始化。在类的内部只是声明,定义必须在类定义体的外部,通常在类的实现文件中初始化。类中的静态变量应由用户使用类外的类名和范围解析运算符显式初始化
  3. 类对象为静态。对象也在声明为static时具有范围,直到程序的生命周期。
  4. 类中的静态成员函数。允许静态成员函数仅访问静态数据成员或其他静态成员函数,它们无法访问类的非静态数据成员或成员函数。建议使用类名和范围解析运算符调用静态成员。

volatile

当对象的值可能在程序的控制或检测之外被改变时,应该将该对象声明为volatile。关键字volatile告诉编译器不应对这样的对象进行优化。编译器每次应该从内存中取对象的值,而不是从缓存中读取。

二面

代码题:单链表反转,需要自己写输入输出。

单链表和双向链表的区别?

单链表只有一个指向下一结点的指针。
双链表除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以快速找到前一结点。

代码调试工具GDB是否使用过?

Linux常用命令有哪些?

数组和链表的区别?

数组:随机访问性强、查找速度快、插入和删除效率低、可能浪费内存、内存空间要求高,必须有足够的连续内存空间。
链表:插入删除速度快、内存利用率高,不会浪费内存、大小没有固定,拓展很灵活。不能随机查找,必须从第一个开始遍历,查找效率低。
数组大小固定,不能动态拓展

结构体内存对齐,计算结构体的大小

   struct {
    int a;
    char b;
    int d;
    short c;
    //int d;
  }

内存对齐的默认规则,平台的默认对齐系数, #pragma pack(n) , n = 1,2,4,8,16。
有效对齐值:给定对齐系数和结构体中最长数据类型中较小的那个。有效对齐值也叫对齐单位。
对齐规则1(数据对齐):结构体的第一个成员的偏移量是0,以后每一个成员相对于结构体首地址的偏移量都是该成员大小与有效对齐值中较小的那个值的整数倍。如果有需要的话会在成员之间加上填充字节。
对齐规则2(结构体对齐):结构体的总大小必须为有效对齐值的整数倍,如果有需要,编译器会在最末一个成员之后加上填充字节。



活动打卡代码 LeetCode 398. 随机数索引

class Solution {
public:
    unordered_map<int, vector<int>> hash;
    Solution(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++)
            hash[nums[i]].push_back(i);
    }

    int pick(int target) {
        return hash[target][rand() % hash[target].size()];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */



//树状数组

class NumArray {
public:

    int n ;
    vector<int> tr, nums;

    int lowbit(int x)
    {
        return x & -x;
    }

    int query(int x)
    {
        int res = 0;
        for(int i = x; i ; i-=lowbit(i))
            res += tr[i];
        return res;
    }

    void add(int x, int v)
    {
        for(int i = x; i<= n; i += lowbit(i)) 
            tr[i] += v;
    }

    NumArray(vector<int>& _nums) {
        nums = _nums;
        n = nums.size();
        tr.resize(n+1);
        for(int i = 1; i <= n; i++)
        {
            tr[i] = nums[i-1];
            for(int j = i-1; j > i-lowbit(i); j-=lowbit(j))
                tr[i] += tr[j];
        }
    }

    void update(int i, int val) {
        add(i+1, val-nums[i]);
        nums[i] = val;
    }

    int sumRange(int i, int j) {
        return query(j+1) - query(i);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */


活动打卡代码 LeetCode 306. 累加数

class Solution {
public:

    string add(string a, string b)
    {
        vector<int> A,B,C;
        for(int i = a.size()-1; i >= 0 ; i--) A.push_back(a[i]-'0');
        for(int i = b.size()-1; i >= 0; i--) B.push_back(b[i]-'0');
        for(int i = 0, t = 0; i <A.size() || i < B.size() || t; i++)
        {
            if(i < A.size()) t+=A[i];
            if(i < B.size()) t+=B[i];
            C.push_back(t%10);
            t/=10;
        }
        string z;
        for(int i = C.size()-1; i >= 0; i--) z += to_string(C[i]);
        return z;
    }

    bool isAdditiveNumber(string num) {
        for(int i = 0; i < num.size(); i++)//枚举第一个数字的终点
        {
            for(int j = i + 1; j + 1 < num.size(); j++)//枚举第二个数字的终点
            {
                int a = -1, b = i, c = j;//a是第一个数字起点的前一位,b是第二个数字起点的前一位,c是第三个数字起点的前一位
                while(true)
                {
                    if(b -a >1 && num[a+1] == '0' || c-b>1 && num[b+1] =='0')break;//跳过包含前导0的部分
                    auto x = num.substr(a+1, b-a), y = num.substr(b+1, c-b);
                    auto z = add(x,y);
                    if(num.substr(c+1, z.size()) != z) break;//下一个数不匹配
                    a = b, b = c, c += z.size();
                    if(c+1 == num.size()) return true;
                }
            }
        }
        return false;
    }
};



class NumMatrix {
public:
    vector<vector<int>> sum;
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size(), m = matrix[0].size();
        sum= vector<vector<int>>(n+1, vector<int>(m+1));
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        res = sum[row2+1][col2+1] -sum[row2+1][col1]-sum[row1][col2+1] + sum[row1][col1];
        return res;
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */



class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> S;
        for(auto x : nums1) S.insert(x);
        vector<int> res;
        for(auto x : nums2)
        {
            if(S.count(x))
            {
                res.push_back(x);
                S.erase(x);
            }
        }
        return res;
    }
};



class NumArray {
public:
    vector<int> sum;
    NumArray(vector<int>& nums) {
        sum = vector<int>(nums.size()+1);
        for(int i = 1; i <= nums.size(); i++)
        {

            sum[i] = sum[i-1] + nums[i-1];//前缀和
        }
    }

    int sumRange(int i, int j) {
        i++, j++;
        return sum[j]-sum[i-1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */



class Solution {
public:

    vector<string> ans;
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for(auto x:s)
        {
            if(x == '(') l++;
            else if(x == ')')
            {
                if(l == 0) r++;
                else l--;
            }
        }
        dfs(s, 0, "",0, l, r);
        return ans;
    }

    void dfs(string& s, int u, string path, int cnt, int l, int r)
    {
        if(u == s.size())
        {
            if(!cnt)
            {
                ans.push_back(path);   
            } 
            return ;
        }

        if(s[u] != '(' && s[u] != ')') dfs(s, u+1, path+s[u], cnt, l, r);
        else if(s[u] == '(')
        {
            int k = u;
            while(k < s.size() && s[k] == '(') k++;
            l -= k-u;
            for(int i = k-u; i >= 0; i--)
            {
                if(l >= 0 ) dfs(s, k, path, cnt, l, r);
                path += '(';
                cnt++, l++;
            }
        }
        else if(s[u] == ')')
        {
            int k = u;
            while(k < s.size() && s[k] == ')') k++;
            r -= k-u;
            for(int i = k-u; i >= 0; i--)
            {
                if(cnt >= 0 && r >= 0)
                    dfs(s, k, path, cnt, l, r);
                path += ')';
                cnt--,r++;
            }
        }
    }
};