已通过公开华为终面，新鲜的笔试面经复盘整理
给出一些标记了长和宽的方形积木，长度和宽度都是整数：就是给出一个二维数组，第一维表示不同的积木，第二维只取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]这个数组所代表的货仓如下图所示（红色线代表地面）：
如果要求往里放长度为N=2的货物，则可以放下3个：
注意，最左侧的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; } }
面试情况：
