首页 > 已通过公开华为终面,新鲜的笔试面经复盘整理
头像
L_瞅啥
编辑于 2021-08-18 11:48
+ 关注

已通过公开华为终面,新鲜的笔试面经复盘整理

顺利通过HW公开终面。流程很快,面试体验感很好,base西安+上海+成都+东莞。根据面试官说在这个部门可以参与打造“无线网络自动驾驶的大脑”,有一流的技术大佬,可以出差国内外和客户交流贡献才智。大家快到有需要可以联加微信号a584015461或者QQ1873935877

好的 废话不多说,先分享一下8.11号晚上的笔试题目

给出一些标记了长和宽的方形积木,长度和宽度都是整数:就是给出一个二维数组,第一维表示不同的积木,第二维只取0和1,表示长和宽。当一个积木的长宽均不大于另一个积木的时候,这个积木可以垒在另一个积木上面。计算最多能垒多少积木。
例如:
输入:[[3,4],[5,7],[6,3],[6,7],[5,8],[6,6]]
输出:4
提示:[3,4], [6,3], [6,6], [6,7]即4个积木。
相关题目:
俄罗斯套娃:https://leetcode-cn.com/problems/russian-doll-envelopes/
最长递增子串:https://leetcode-cn.com/problems/longest-increasing-subsequence
本题和俄罗斯套娃信封的区别在于两点:大于等于关系,积木可以旋转
思路:
将二维(长、宽)的比较问题,先固定一个维度(长),然后只比较另一个维度(宽)即可,在长度的从小到大顺序确定以后,已经可以保证以该顺序所提出的任意子串都满足长度的要求,只需要考虑宽度要求即可(详细解释参考俄罗斯套娃的题解)
代码:

#include <algorithm> #include <vector> using namespace std; class Solution { public: void standardizeBlocks(vector<vector<int>> &blocks) { for (auto &block : blocks) { if (block[0] < block[1]) { std::swap(block[0], block[1]);
            }
        }
    } int maxBlocks(vector<vector<int>> blocks) { if (blocks.empty()) { return 0;
        }

        standardizeBlocks(blocks); // 因为可以旋转,因此将所有的积木标准化为长度一定大于宽度,第0维度为长度 sort(blocks.begin(), blocks.end(), [](const auto& b1, const auto& b2) { if (b1[0] == b2[0]) { return b1[1] < b2[1]; // 长度相等情况下,宽度排序与俄罗斯套娃也有区别 } return b1[0] < b2[0];
        }); int dpMax = 0; // 此处的一维DP问题,可以参考最长递增子序列。 vector<int> dp(blocks.size(), 1); for (int i = 1; i < blocks.size(); ++i) { for (int j = 0; j < i; ++j) { if (blocks[j][1] <= blocks[i][1]) //这里的 <= 是和俄罗斯套娃的一个区别 {
                    dp[i] = max(dp[i], dp[j] + 1);
                    dpMax = max(dpMax, dp[i]);
                }
            }
        } return dpMax;
    }
};

第二题:字符串压缩算法

这道题目在leetcode上找不到同级别的对应题,比0106字符串压缩,要求提供两种形式的压缩:
1) 单个字符重复:aaaaaaaa -> a8
2) 子序列重复:abcabcabc -> ABC3
输入:全部小写字母的字符串(a-z)
输出:压缩后的字符串
例:
bbb应该压缩为b3, bb压缩后没有收益,因此不压缩(连续两个重复字母不压缩)
abcabcabc压缩为ABC3
重复字母和重复子串同时出现,优先进行重复子串的压缩,如aaaabcabc应该压缩成a3ABC2
有多个重复子串时,优先压缩最长的重复子串:
bbbbacbacbbbbacbac --- > BBBBACBAC2
思路:
本题优先考虑处理子串(处理子串时需要知道该位置是否有单个字符的重复,比如aaaaaa,优先写成a6,而不是AAA3),然后再处理单个字符重复的情况。
代码:

// 返回子串的重复数量 int getRepTimes(const std::string &s, int i, int l) { int rep = 1; while (i + l * rep + l <= s.size()) { if (s.substr(i, l) != s.substr(i + rep * l, l)) { break;
        }
        ++rep;
    } return rep;
} // 转为大写 std::string toUpperStr(const std::string &str) { std::string result; for (auto c : str) { if (c >= 'a' && c <= 'z') {
            c += 'A' - 'a';
        }
        result.push_back(c);
    } return result;
} // 计算连续字符的重复次数, v[i]代表从i往后包括i本身共有多少个重复字符 vector<int> calcRepTable(std::string s) { vector<int> repTable(s.size(), 0); int rep = 1; char prev = ' '; for (int i = s.size() - 1; i >= 0; --i) { if (!(s[i] >= 'a' && s[i] <= 'z')) {
            rep = 1;
        } else if (s[i] != prev) {
            rep = 1;
        } else {
            ++rep;
        }
        repTable[i] = rep;
        prev = s[i];
    } return repTable;
} std::string zipIt(const std::string &s) { auto repTbl = calcRepTable(s); std::string s1; for (int i = 0; i < s.size(); ++i) { bool anyZip = false; for (int l = (s.size() - i) / 2; l > repTbl[i]; --l) { int repTimes = getRepTimes(s, i, l); if (repTimes > 1) {
                s1 += toUpperStr(s.substr(i, l)) + std::to_string(repTimes);
                i += l*repTimes - 1;
                anyZip = true; break;
            }
        } if (!anyZip) {
            s1.push_back(s[i]);
        }
    }; auto repTblS1 = calcRepTable(s1); //std::cout << "s1 is : " << s1 << std::endl; //从后往前进行单字符的压缩 std::string result; for (int i = 0; i < s1.size(); ++i) { if (repTblS1[i] > 2) {
            result.push_back(s1[i]);
            result.append(std::to_string(repTblS1[i]));
            i += repTblS1[i] - 1;
        } else {
            result.push_back(s1[i]);
        }
    } std::cout << "result : " << result << std::endl; return result;
}

第三题:货仓问题

有一个货仓,是台阶状的结构(形状类似接雨水题目),每个台阶的宽度都是1,高度由输入决定,是一个可正可负的整数,正整数表示高于地面,0表示和地面一样高,负整数表示低于地面。
给出一批大小相同的货物(只考虑长宽两个维度,类似薄纸片),货物的高度都是1,长度都是N(由输入给出)而且货物只能平着放,不能斜着放。货物的上表面不能超出地面(即高度为0的地面表面)。计算整个货仓能放多少个货物。

  • 输入: 货物长度N和一个整数数组
  • 输出: 一个正整数表示能放几个货物(0表示一个也放不下)
  • 例:[1,1,0,-1,-2,-2,-1,0,-1,3,-3,1]这个数组所代表的货仓如下图所示(红色线代表地面):
    image
    如果要求往里放长度为N=2的货物,则可以放下3个:
    image
    注意,最左侧的1,1即使可以放下一个货物,但在地表以上,因此不允许放货物。另外,一个货物的下表面可以被不完全支撑。
  • 思路:
    这道题目比接雨水简单很多,货物平放就已经排除了很多可能性,其实是个取整问题,因为平放导致每一个平面都与其他平面相互之间不干扰(考虑一种例外情况:货物有没有可能找不到支撑,这种情况是不存在的,如果货物下方完全没有支撑,那么下方的空间完全足够放下一个相同的货物,因此排除)。每个平面考虑其自身即可。将整个货仓地形从左到右遍历一遍,用另一个数组记录下当前每个水平面的货物已经放了几个长度单位,据此可以知道什么时候放下一个完整的货物。
    代码:
#include <vector> #include <algorithm> class Solution { public: int solveIt(int N, std::vector<int> heights) { int result = 0; std::vector<int> curLen = {0}; // 占位 for (unsigned int i = 0; i < heights.size(); ++i) { int height = heights[i];
            height = std::max(-height, 0); while (curLen.size() <= height) {
                curLen.push_back(0);
            } unsigned int j = 1; for (;j <= height; ++j) {
                curLen[j]++; if (curLen[j] == N) {
                    curLen[j] = 0;
                    result++;
                }
            } for (;j <= curLen.size(); ++j) {
                curLen[j] = 0;
            }
        } return result;
    }
}
面试情况:
码字太累,后续更新,有需要私聊我或者联系上面的qq

更多模拟面试

全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐