2022届秋招面经--秋招笔试（2）_大疆笔试算圆周率

1.大疆编程（2022嵌入式软开）

1.求1-n中 十进制数中 1出现的次数？
int NumberOf1Between1AndN_Solution(int n) {
        
        int num=0;
        
        /*string s;//法一 转换为字符串
        for(int i=1;i<=n;i++){
            s=to_string(i);//将整数转化为字符串 
            for(int j=0;j<s.size();j++){
                if(s[j]=='1')num++;
            }
        }*/
        
    //法二 遍历
        for(int i=1;i<=n;i++){
            int t=i;
            while(t){
                if(t%10==1){
                    //cout<<i<<endl;
                    num++;
                    
                }
                t=t/10;
            }
        }
        return num;
    }
};

2.求N位精度的圆周率值？
使用级数求pi  π/4=1-（1/3）+（1/5）-（1/7）+...+（-1）^（n-1）*(1/(2n-1))

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    double precision;
    cin>>precision;
    double pi=0,now;
    int n=1,flag=1;
    now=1.0/n;
    do
    {
        pi=pi+now*(flag)*4;//相当于π/4=...
        flag=-flag;
        n+=2;
        now=1.0/n;
    }while(fabs(now)>=precision); //precision  就相当于精度0.1、0.001
    cout<<pi<<endl;
    return 0;
}

注：大疆的笔试总体难度一般吧，但是切记大疆的测评和大部分公司不一样，有些选项是必选的，这个要注意一下，有很多人测评就被out了（我这里有测评/笔试的一些总结word版本的，想交流的私信我哦）（PS：私信的有点多来不及回，去牛客评论留下邮箱2022届笔试编程题_笔经面经_牛客网1.大疆编程（2022嵌入式软开） 2.联发科（基本都是链表题--好像必须用C写） 3.深信服 4.中兴（现场面，手撕概率为10%，结果我手撕了） 5.字节跳动（phttps://www.nowcoder.com/discuss/959958）

2.联发科（基本都是链表题--好像必须用C写）

1.链表的创建删除 最基本的吧，，，后续我会接着更新

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

//单向链表结构体
typedef struct list
{
    int data;
    struct list* next;
}list;

//双向链表结构体
typedef struct list2
{
    int data;
    struct list* next;
    struct list* pre;
}list2;

//单链表的创建
list* createlist() {
    list* p;
    p = (list*)malloc(sizeof(list));
    p->next = NULL;
    list* cur = p;//建立辅助指针
    cout << "请输入链表" << endl;
    do {
        list *L= (list*)malloc(sizeof(list));
        scanf("%d",&(L->data));
        cur->next = L;//尾插法
        cur = L;
    
    } while (getchar() != '\n');
    cur->next = NULL;//插入完成后 将最后一个结点指向空
    return p->next;//因为起初p指向一个空表  注意是p->next 指向空  插数据都是在cur->next 插的 因此返回的时候 应返回 p->next
}
//单链表的插入数据(在第index后插数据)
list* insertNode(list* n, int x,int index) {
    list* p;
    p = n;
    for (int i = 1; i < index; i++) {//从第一个结点开始遍历，遍历到index前一个结点  即index-1
        p = p->next;
    }
    list* inser = (list*)malloc(sizeof(list));
    inser->data = x;
    inser->next=p->next;
    p->next = inser;
    
    return n;
}

//单链表的删除
list* deletelist(list * n,int x) {//n是待删除的链表，x是要删除的数据
    list* p, * q;
    p = n;
    q = p->next;
    //删除头结点
    if (n!=NULL && n->data == x) {
        //p = n;
        n =  p->next;
        free(p);
        p = NULL;
        //cout << "删除后："<<n->data<<endl;
        return n;
    }
    //针对不是头结点的删除
    while (q != NULL) {
        if (q->data == x) {
            p->next = q->next;
            free(q);
            q = p->next;
        }
        else {
            p = p->next;
            q = q->next;
        }
    }
    return n;

}
//链表的打印/显示
void displaylist(list *p) {
    list* d = p;
    while (d != NULL) {
        //cout << d->data << " ";
        printf("%d ",d->data);
        d = d->next;
    }
    printf("\n");

}

int main()
{
    list* p = createlist();
    displaylist(p);

    int x;
    scanf("%d",&x);
    
    list * L=deletelist(p,x);//调用函数一定要看清 返回值  需不需要接返回值
    //insertNode(p,x,2);
    displaylist(L);
    return 0;

}

2.链表转换成队列

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

//单链表结构
typedef struct list {
    int data;
    struct list* next;
}list;

//队列结构
typedef struct que{
    //注意 必须多出来一个头指针 和尾指针  且类型必须是list链表
    list* first;
    list* end;
    
}que;

//初始化队列
que* initque() {
    //que* q = new que;
    que* q = (que*)malloc(sizeof(que));
    q->first = q->end=NULL;
    return q;
}

//队列插入 /入队  （只能从一端入 从另一端出）
void insertque(que* q, int x) {
    list* p = (list*)malloc(sizeof(list));
    p->data = x;
    p->next = NULL;
    if (q->end == NULL) {
        q->first = p;
        q->end = p;
    }
    else
    {
        q->end->next = p;
        q->end = p;
    }
    //return q;
}

//队列的删除/出队  (只能从一端删除  删除的元素固定（尾部插入/头部删除）)
void deleteque(que* q) {
    list* n = q->first;
    //如果只有一个元素
    if (q->first == q->end) {
        q->first = NULL;
        q->end = NULL;
    }
    else
    {
        q->first = n->next;
        //q->first = q->end->next;
        free(n);
    }
    //return q;
}

//打印队列
void displayque(que*q) {
    //list *n= (list*)malloc(sizeof(list));
    list *n = q->first;
    if (n == NULL)return;
    while (n != NULL) {
        cout << n->data<<" ";
        n = n->next;
    }
    cout << endl;
}

int main()
{
    que *n=initque();
    do {
        int x;
        cin >> x;
        insertque(n, x);
    
    } while (getchar()!='\n');

    displayque(n);

    deleteque(n);

    displayque(n);

    return 0;
}

3.深信服
1.编程memcpy（）

void * mymemcpy(void * dst, void * src, int size){
    if(NULL == dst || NULL == src){
        printf("mystrcpy param error\n");
        return NULL;
    }
 
    char * p = dst;
    char * q = src;
 
    while(size != 0){
        *p++ = *q++;
        size--;
    }
 
    return dst;

}

4.中兴（现场面，手撕概率为10%，结果我手撕了）

1.在100个数中随机加入一个数，然后再找出来这个数（这个我记不清了，好像当时我用的遍历，面试官说，这个时间复杂度太高，还有其他办法吗，我说可以尝试用map，他说对）

5.字节跳动（ps:投的提前批，面试官是真有耐心，干了将近50分钟吧，手撕+问的头皮发麻）

1.二叉树

#include<iostream>
#include<queue>
#include<vector>
#include<malloc.h>

using namespace std;
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) :
        data(x), left(NULL), right(NULL) {
    }
};

TreeNode* CreateBiTree()//创建时要注意  每一层根节点其后的空结点都要输入 0（如果左右都为空 需要输入两个零  ）
{
    int a;
    TreeNode* T;
    cin>>a;
    if (a == 0)
    {
        T = NULL;
        

    }
    else
    {
        T = (TreeNode*)malloc(sizeof(TreeNode));//注意是按前序输入的
        T->data = a;
        T->left=CreateBiTree();
        T->right=CreateBiTree();
    }
    return T;//返回根节点
}

//二叉树的层序遍历   核心队列 
vector<int> CBfun(TreeNode* root) {
    vector<int>v;
    if (root == nullptr)return v;
    queue<TreeNode*>q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* n = q.front();//相当于把队列中首元素的地址赋给n  那么n与q所指内容应该是一样的   
        q.pop();//此处是把队列中首元素弹出
        v.push_back(n->data);//但是此时n依旧指向首元素
        if (n->left)q.push(n->left);
        if (n->right)q.push(n->right);
        //q.pop();//所以弹出操作也可以放最后
    }     
    return v;
}

//二叉树的层序遍历   核心队列 
//严格按层打印
vector<int> CBfun2(TreeNode* root) {
    vector<int>v;
    if (root == nullptr)return v;
    queue<TreeNode*>q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        
        while (size--) {
            TreeNode* n = q.front();//相当于把队列中首元素的地址赋给n  那么n与q所指内容应该是一样的   
            q.pop();//此处是把队列中首元素弹出
            cout << n->data<<" ";
            v.push_back(n->data);//但是此时n依旧指向首元素
            if (n->left)q.push(n->left);
            if (n->right)q.push(n->right);
            //q.pop();//所以弹出操作也可以放最后
        }
        cout << endl;
    }
    return v;
}

//前序遍历  核心递归
void PreOrderTraverse(TreeNode* T)
{
    if (!T)
        return;
    cout << T->data;    //显示节点数据
    PreOrderTraverse(T->left);
    PreOrderTraverse(T->right);
}

int main()
{
    vector<int>v;

    TreeNode* root= CreateBiTree();
    cout << "创建完毕！" << endl;
    
    
    
    PreOrderTraverse(root);//前序遍历

    v=CBfun2(root);
    cout << "vector: ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }

    return 0;
}

2.数组头部 插入一个元素
3.一堆数据找到K个最大的

4.合并单链表

5.给定二叉树后序 重建二叉搜索树

6.联想

1.链表逆序（翻转链表）

typedef struct list {
    int data;
    struct list* next;
 
}list;
 
//单链表创建
list* createlist() {
    list* p;
    p = (list*)malloc(sizeof(list));
    p->next = NULL;
    list* cur = p;
    cout << "请输入链表： " << endl;
    do {
        list* L = (list*)malloc(sizeof(list));
        cin >> L->data;
        cur->next = L;
        cur = L;
    } while (getchar()!='\n');
    cur->next = NULL;//插入完成后 将最后一个结点指向空
    return p->next;//因为起初p指向一个空表  注意是p->next 指向空  插数据都是在cur->next 插的 因此返回的时候 应返回 p->next
}
 
//链表的打印/显示
void displaylist(list* p) {
    list* d = p;
    while (d != NULL) {
        //cout << d->data << " ";
        printf("%d ", d->data);
        d = d->next;
    }
    printf("\n");
 
}
 
list* reverselist(list* p) {
    list* pre = NULL;
    list* cur = p;
    list* nex = NULL;
 
    while (cur) {
        nex = cur->next;
        cur->next = pre;//将第一个节点的指针指向空
        pre = cur;//将pre向后移
        cur = nex;//将cur向后移
    }
 
    return pre;//pre 是在cur前边的  当cur为空时跳出循环 此时应返回pre
}

最后还有一些其他公司的

总结了下一般都是字符串，链表考的比较多

1.字符串按出现次数降序-map

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>

using namespace std;
//一般取按字典序排好的
int main()
{
    string s;
    while (cin >> s) {
        int len = s.size();
        
        map<char, int>m;
        vector<char>v;
        //将数据插入map （根据出现的频率）
        for (int i = 0; i < len; i++) {
            m[s[i]]++;
        }
        

        //次数相同按字典序输出
        //while (m.size() != 0) {
        //    //遍历找出map中频率最高的num  然后将其对应的key 压入vector 然后删除map中该值 继续循环
        //    int num = 0;
        //    for (auto it = m.begin(); it != m.end(); it++) {
        //        num = max(num,it->second);
        //    }
        //    for (auto it = m.begin(); it != m.end(); it++) {
        //        if (it->second == num) {
        //            v.push_back(it->first);
        //            m.erase(it);//注意：此时删除的数值是map中排好序的字符
        //            break;
        //        }
        //    }
        //    
        //}
        出现次数相同的 是按字典序打印的  因为map中会自动排序
        //for (auto it = v.begin(); it != v.end(); it++) {
        //    cout << *it << " ";
        //}
        //cout << endl;

        //次数不同按原顺序输出
        while (m.size() != 0) {
                //遍历找出map中频率最高的num  然后将其对应的key 压入vector 然后删除map中该值 继续循环
                int num = 0;
                for (auto it = m.begin(); it != m.end(); it++) {
                    num = max(num,it->second);
                }
                for (auto it = m.begin(); it != m.end(); it++) {
                    if(num>1){
                        if (it->second == num) {
                        v.push_back(it->first);//将出现次数大于1的按降序存入vector中
                        m.erase(it);//注意：此时删除的数值是map中排好序的字符
                        break;
                        }
                        
                    }
                    else
                    {
                        if (it->second == num) {
                            //v.push_back(it->first);
                            m.erase(it);//注意：此时删除的数值是map中排好序的字符
                            break;
                        }
                    }
                    
                }
                
            }
        //将s中次数为1的按原顺序压入vector
            for (auto i = s.begin(); i !=s.end(); i++) {
                if (find(v.begin(), v.end(), *i) == v.end())
                    v.push_back(*i);
                
            
            }
            for (auto it = v.begin(); it != v.end(); it++) {
                cout << *it << " ";
            }    
            cout << endl;
        
    }
    
    return 0;
}

2.字符串匹配返回匹配下标

/*给定一个字符串,判断该字符串中是否包含某个子串.
如果包含,求出子串的所有出现位置. 要求：从键盘输入两个字符串，
第一个是给定的字符串，第二个是子串。*/

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int len1 = s1.size();
    vector<int>v1;
    int j = 0;
    for (int i = 0; i < len1; i++) {
        
        if (s1[i] == s2[j]) {
            j++;
            if (j == s2.size())
            {
                cout << i << endl;
                j = 0;
            }
        }
        /*if (j >= s2.size()) {
            break;
        }*/
    }

    

    return 0;
}

以上就是本人此次秋招遇到的一些编程题，希望对大家有帮助，有错误的希望指出，整理不易，还望支持，愿大家都能找到理想的工作。。。