华为实习生2022机考、技术面及主管面试

第一题：

在一个单元上装满4个A芯片后，有两种情况：

第一种情况，a坐标比b坐标小，a的坐标更新为b+1
第二种情况，a坐标比b坐标大，直接加1
对于B来说也是一样,按照这个原则来更新坐标，最后返回即可。

第二题：动态规划求地图障碍物的题：

没有障碍物的：已经用滚动数组优化了
class Solution {
public:
int uniquePaths(int m, int n) {
//优化滚动数组来做
vectorf(n);
f[0] = 1;
for(int i=0;i
for(int j=0;j
if(j>=1){
f[j] = f[j]+f[j-1];//f[j]在这相当于f[i-1][j],这时候值还没更新//f[j-1]相当于f[i][j-1]
}
}
}
return f.back();
}
};
有障碍物的，照猫画虎也是一样：关键思路就是当有障碍物的时候，将当前f[j]置0，且跳过循环。
class Solution {
public:
int uniquePathsWithObstacles(vector& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid.at(0).size();
//优化滚动数组来做
vectorf(n);
f[0] = (obstacleGrid[0][0] == 0);
for(int i=0;i
for(int j=0;j
if(obstacleGrid[i][j] == 1){
f[j] = 0;
continue;
}
if(j>=1){
f[j] = f[j]+f[j-1];
//f[j]在这相当于f[i-1][j]纵向前一个,这时候值还没更新
//f[j-1]相当于f[i][j-1]横向前一个
}
}
}
return f.back();
}
};

第三题：树的共同子树

首先是要建一个树：
1 2 3 # 4 # # 5 # # 6 # #
int CreateBitTree(BiTNode *T)
{
ElemType ch;
ElemType temp;
cin>>ch;
temp = getchar();//
if (ch == ‘#’)
T = nullptr;
else {
T = new BiTNode;
T->data = (int)ch;
cout<<“输入”< CreateBitTree(T->lchild);
cout<<“输入”< CreateBitTree(T->rchild);
}return 1;
}
这样可以用数组的格式输入，

1. 知道自己的子树什么样子

2. 知道别人的子树什么样子
   其中有个序列化的思想，把子树变成字符串，用哈希表来比较即可
   class Solution {
   public:
   string dfs(TreeNode* root, vector& res, unordered_map& mp){
   if(root==NULL) return “”;
   //二叉树先序序列化
   string str = to_string(root->val) + “,” + dfs(root->left, res, mp) + “,” + dfs(root->right, res, mp);

   if(mp[str]==1){
       res.push_back(root);
   } 
   mp[str]++;
   return str;
   

   }

   vector findDuplicateSubtrees(TreeNode* root) {
   vector res;
   unordered_map mp;
   dfs(root, res, mp);
   return res;
   }

};

技术面：

问项目
c++析构函数为什么是虚函数
编程题：
接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

主管面

项目、自己的优势