NC522 旅行Ⅰ 题解一：优先队列，拓扑排序 题解思路：  首先，如果将list中限制条件构建成一个图。如图：  在去2号城市之前必须先去1号城市， 转换成有向图1--->2; 我们使用 vector<vector<int> > in(N+1,vector<int>(N+1,0)); 表示有向图的邻接矩阵，第一行用来代表每个结点的入度数。 其次， 将所有入度为0的结点加入到优先队列，并且按照花费从小到大排序。 最后，利用拓扑排序的思想，每次从优先队列中取出一个元素，如果当前V-当前城市花费>=0,那么就将可到达...

本次不知道是一面还是一二三面，因为面了3个面试官 一面（70min） 第一位面试官： 1、cpu架构你了解吗？ 答： ①l1、l2级缓存、页面置换算法； ②目前多核cpu，每个核都有自己的高速缓存，所以需要使用volatile变量做多线程开发； ③聊了局部性原理； ④计算机怎么读取内存，为什么字节不对齐会读取两次数据； 2、怎么用代码体现局部性原理？ 答：二维数组，按行读取还是按列读取 然后我听到了面试官说像是背的，然后出现了第二、三位面试官 （ps：面试官您听我说，我真不是背的😫😫） 第二位面...

有重复项数字的所有排列题解一：搜索回溯 题解思路： 该题与“没有重复项数字的所有排列“思路一样，只是多了约束条件。 约束条件： 1.一个数字不能重复地被选择。 2.不能产生重复地排列。 所以排列中地同一个位置不能出现相同的。图示： 剪枝：使用一个vis数组标记使用过的数字，如果使用过了就回溯。如果当前的选项num[i],与同一层的前一个选项num[i-1]相同且num[i-1]已经使用了，那表示同一层是相同的数字 复杂度分析：  时间复杂度：，同无重复一样，最坏情况就是数组无重复  空间复杂度：，N为序列的长度。除返回的数组以外，递归函数在递归过程中需要为每一层递归函数分配...

一面（70min） 1、自我介绍 2、在pc上开发还是开发板上开发（这个没怎么听懂题目，出现了下面的问题） 3、有交叉编译的经历吗？ 4、平时开发用的什么ide 5、用的什么系统，centOS还unbantu 6、用的是Cmake还是makefile 7、vim使用 8、group使用 9、kill -9作用 10、C与C++内存分布 11、GDB调试 12、RDMA协议作用 13、http交互过程 14、URL解析过程 ...

题解一：回溯 题解思路： 每次尝试选一个数，不满足条件就回溯 图示：  约束条件：数组不能重复使用.  递归分析： cur==num.size 表示找到一个全排列  递归过程： 如果该数字能添加，那么将vis置位1 ，表示该数字已经用了。   回溯： 恢复状态复杂度分析:  时间复杂度： : 共有n！个叶节点，需要使用O(N)的时间复制到目标数组  空间复杂度： ：排列个数N！，每个排列占N实现如下： class Solution { public: int vis[1001]; vector<...

有多少百度三面完面试流程变成简历处理中的小伙伴。 一起抱团求温暖。

题解一:暴力主要思路：根据题意,①判断n是否大于10，小于10结束返回n，否则执行②②对n各位求乘积，执行① class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param n long长整型 老师给牛牛的数字 * @return int整型 */ int f(long long n){ long long res=1; while(n!=0){ res=res*(n%10);...

题解一:Hash+遍历(不符合题目要求)主要思路:根据题意n的范围是，建立hash表 ①对数字散列到hash表，非正整数忽略 ②对hash表进行从小到大的遍历，对应key值没有value的bucket即为第一个未出现的最小正整数 图示 复杂度分析: 时间复杂度分析:,散列的时间为O(N),而遍历时间复杂度也为O(N),综上时间复杂度为O(N) 空间复杂度分析:，开辟了一个最大的为N的hash表 实现如下： int hash_table[1000000000];//hash表，放在外面定义的原因是，可能超过了栈空间 class Solution { public: /** *...

题解：回溯 首先，每个皇后不能同行，不能同列，不能同斜线。 对于一个3皇后问题，如图： 约束条件判断： 同行和同列好判断，同斜线判断如图： 可以看出斜线约束判断([ (i-1)-(j-1),(i-j),(i+1)-(j+1) ], [ (i+1)+(j-1),(i+j),(i-1)+(j+1) ] 递归函数分析：  递归边界： cur==n 表明 每个皇后都已放好  递归过程：尝试这在第cur行的某个位置放皇后 graph[cur] =i, 并判断是否与之前放置的皇后有冲突。 如果没有，...

题解一：递归 首先遍历两个链表求出长度len1，len2, 并且head1永远指向长度较长的那个链表。 递归分析：  递归边界： head1 == NULL; 递归过程：  情况1： len1>len2 表明没有到首位相加位数只需add(head1->next,head2)  情况2： add(head1->next,head2->next); 回溯过程：  情况1：len1>...

题解一：暴力+hash表主要思路:①从1遍历到n，选取子数组的起点start②第二重循环，从start下一个数字开始，选择子数组的结束位置end；③直到end位置出现重复，记录最长的长度，跳转至步骤①，直到遍历完所有子数组的起点图示： 复杂度分析:时间复杂度：,双重循环分别找子数组的头部和尾部空间复杂度:,最差情况下，整个数组都是不重复的。 实现如下: class Solution { public: /** * * @param arr int整型vector the array * @return int整型 */ int maxL...

一面(50min)： 1、自我介绍 2、多态中虚析构函数的作用 3、内存泄露的情况，怎么防止 4、C++类型转换 5、const_cast,static_cast,dynamic_cast作用与区别 6、C++11特性 7、share_ptr指针原理，注意的点 8、编程题：输入一个n，第一行放1，第二行2，第三行3以此类推，放完n，最后一行是多少。 8.5 给我发感谢信了，我觉得问题出在编程题上面，没有给面试官讲述清楚。

题解一：暴力①遍历1~n；②判断这个数是否为水题时间复杂度:空间复杂度: class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回牛牛获得的快乐指数 * @param n int整型 题单里的题目数量 * @return int整型 */ int doQuestion(int n) { // write code here int res=0; for(int i=1;i<=...

题解一:迭代主要思路:①根据题意对n减去7②判断是否为2的幂次方 复杂度分析:时间复杂度:空间复杂度: 实现如下: class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定一个数字n，如果该数减去7后是2的幂次方，返回"YES"，否则，返回"NO"。 * @param n int整型 代表题目中的n * @return string字符串 */ string solve(int n) { ...