4.14华为实习机考题
1.给一个字符串如"（k（abc）（def）gh）"，从里向外将括号内的字符翻转，如"（k（abc）（def）gh）" -> "（k cba fed gh）" -> "hg def abc k" (不包括空格，输出不含括号)
思路：（）将字符分割，使用string栈记录从左向右的分段字符，出现）则反转top()，并合并。100%。
上leetcode找了下是1190题
1190. 反转每对括号间的子串 - 力扣（LeetCode） (leetcode-cn.com)
用栈解决O(n)复杂度，不是很难
用栈解决O(n)复杂度，不是很难
2.给出每0.5s的汽车速度值，如果速度比上次测量低9及以上进入AEB状态，根据一些规则进行上报，在不AEB状态则周期上报。字太多了，没记住多少。
感觉就是分好情况弄清楚上报点范围。可是写了很长的程序，才20%到最后也没上去。。。
3.通信中继
给出n个节点的通信能力，a1,a2,...an km，每个节点距离1km，问从左到右，最后一个节点通信需要的最小跳数。（节点数<=65535,通信能力<=65535）
动态规划吗？
设dp[i]表示从头传到第i个节点所需最小跳数。
方程： dp[i] = min(dp[j]）+1 对于所有满足就j<i，i-j<=aj的j
即i处dp值等于所有能传到i处（i-j<=aj）的j的最小的dp值中+1
初始dp[0] = 0
结果dp[n-1]
时间复杂度O(n^2)空间复杂度O(n) 当时就想到这个解法，没有优化，95%怎么调也上不去。
我的代码：
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n,INT_MAX);
dp[0] = 0;
for(int i=1;i<n;++i){
for(int j=0;j<i;++j){
if(j+nums[j]>=i){
dp[i] = min(dp[i],dp[j]+1);
}
}
}
return dp[n-1];
}
找到原题，leetcode第45题，我跳着刷没刷到QAQ。
用贪心时间O(n)空间O(1)
我的方法在leetcode AC了但是华为机考只有95%，难道是通信能力有＜1的传不过去了？
4.23专业面试
中午11.20开始
1.先验证身份，学生证或身份证拍一下
2.介绍面试有三个环节：复盘机考题、现场做一道题、问一些专业问题
3.复盘：
前面两个人分别复盘了1和3题，你来复盘一下第二题吧。就第二题弄不明白为啥只有20%......讲了我的做法，听了面试官的做法，说我编程细节有问题，不知道为啥不能都过......
4.手撕题：
给一个字符串如“aadddccddc11 2###”，按字符出现的频数输出字符串，如果次数相同按ASCII表顺序排序。（#是非法字符，合法字符包括空格 ）
我的思路，用map存吧，map<char,int>自动按频数排序，重写比较函数加上对key的排序。
但是本人基础知识掌握不牢固不会重写map的比较函数，考官让我查，我也没查出个所以然......
那就遍历吧，倒序把频数相同的key（char）放在vector里，再对vector排序输出。
用STL自带sort测试结果不对，sort按字典序排不是按ASCII码表排......
时间浪费太多了，考官不想等了，拍一下代码，进入下一环节
5.问答：
看你是通信专业的，问点专业知识吧？
（1）采样定理解释下
easy
（2）数字信号处理里倍频是什么东西，他也没描述清楚，我就按标准正交基{cos sin} {e^(j2piT/n)}瞎说了一通......他问啥也没说清楚
（3）其他知识数据结构也学过吧？说一下图算法吧，都了解过什么啊？最短路径怎么求。
迪杰斯特拉算法，我复习过，只知道，但是忘了具体算法了。
（4）图太复杂了，那树总会吧，讲一下二叉搜索树。
左子树<父<右子树
（5）二叉搜索树会有什么问题？
插入删除操作不当会让树退化成链表，深度增加，效率降低
（6）为解决这个，现在有平衡二叉树，讲一下有什么性质吧。
左右子树深度差绝对值不超过1
（7）平衡二叉树为了实现平衡耗费了那些代价？
具体实现我不会，听他讲大概是在插入时不断比较左右树来保证平衡
（8）碎碎念：讲了讲红黑树，又说俺们通信专业知识强的都在L1层，大概是暗示我应该报嵌入式开发不适合通用软件开发......
最后说恭喜你过了，但是我自我评价不好，一是复盘相比写的时候没有进步，二是手撕没写出来，三是c++专业知识掌握不深（我还以为会问计算机网络和操作系统，复习了半天），估计和GG差不多 了，这一轮不好意思直接挂你，主管面再挂吧。
主管面要安排到25号，我看别人都是上午面完专业下午面主管啊？？
全部评论
(4) 回帖