😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！💪💪💪

文章目录

📗前言📘笔试经典编程题目（八）🔮1. 电话号码🪄2. 求和🧿3. N 皇后🧩4. 骆驼命名法🧸5. 单词倒排🪅6. 乒乓球筐🪆7. 查找兄弟单词🪀8. 简单错误记录🎴9. 合唱团🃏10. 马戏团🀄11. 左右最值最大差♟️12. 顺时针打印矩阵 📙后记

📗前言

大家好呀，我是白晨。好久没有更新这个系列了。这次依旧是熟悉的12道题，本次的题型有动态规划，条件控制，回溯算法等，难度没有太大波动，与上一次的题目难度大抵相同。

都是很有代表性的经典题目，适合大家复习和积累经验。

这里是第八周，大家可以自己先试着自己挑战一下，再来看解析哟！

📘笔试经典编程题目（八）

🔮1. 电话号码

🍬原题链接：电话号码

🍭算法思想：

这道题就是一道实现题，利用哈希的思想将其对应翻译出来，再放入set中去重即可。

🍡代码实现：

#include <iostream>#include <string>#include <vector>#include <unordered_map>#include <set>#include <cctype>using namespace std;static string num = "22233344455566677778889999";int main(){int n;while (cin >> n){vector<string> vs;string line;while (n--){cin >> line;vs.push_back(line);}set<string> ss;for (string& s : vs){string snum;for (char c : s){if (isdigit(c))snum.push_back(c);else if (isalpha(c))snum.push_back(num[c - 'A']);elsecontinue;if (snum.size() == 3)snum += '-';}ss.insert(snum);}for (auto& s : ss){cout << s << endl;}cout << endl;}return 0;}

🪄2. 求和

🍬原题链接：求和

🍭算法思想：

直接上DFS暴力搜索，第一次从1开始累加，后面从传入的参数begin开始累加（不回头），一直加到目标数，将对应的排列记录用数组记录，最后返回所有的可能组合。

🍡代码实现：

#include <iostream>#include <string>#include <vector>using namespace std;// begin 为开始进行累加的数，本次DFS从这个数开始 // cur记录目前累加的结果，vv保存全部可能的组合，curv保存当前累加的组合// limit为最大可以选择的数，target为目标数void DFS(int begin, int cur, vector<vector<int>>& vv, vector<int>& curv, int limit, int target){// 当前和等于目标和时，直接记录当前累加的组合if (cur == target){vv.push_back(curv);return;}// 从begin开始累加，循环尝试各种可能for (int i = begin; i <= limit; ++i){int val = cur + i;if (val <= target){curv.push_back(i);DFS(i + 1, val, vv, curv, limit, target);curv.pop_back();}}}int main(){int n, m;while (cin >> n >> m){vector<vector<int>> vv;vector<int> v;DFS(1, 0, vv, v, n, m);for (auto& res : vv){for (int num : res){cout << num << " ";}cout << endl;}}return 0;}

🧿3. N 皇后

🍬原题链接：N 皇后

深度优先搜索经典题目。

🍭算法思想：

根据题意，皇后的同行，同列以及所处的两个斜线不能有皇后，所以这次我们可以选择按行搜索。在每一行选择一个位置放皇后，每层放置皇后时，要根据当前皇后放置情况判断是否能放置，能放置才能进入下一层递归。具体皇后放置判断标准： 当有皇后在同一行，同一列，同一斜线上时，返回false。斜线判断：同一上斜线的皇后坐标：行数 + 列数 = 定值同一下斜线的皇后坐标：行数 - 列数 = 定值满足在同一条斜线上的直接false。

🍡代码实现：

class Solution {public:// allRet代表所有方案 curv为当前皇后放置的位置 // cur为当前查找的行数，当然也能理解为当前皇后的数量 n代表棋盘行数void DFS(vector<vector<pair<int, int>>>& allRet, vector<pair<int, int>>& curv, int curRow, int n){// 有n位皇后则返回if(curRow == n){allRet.push_back(curv);return;}// 按列查找for(int i = 0; i < n; ++i){// 判断放置位置是否合法if(isVaildPos(curv, curRow, i)){curv.emplace_back(curRow, i);DFS(allRet, curv, curRow + 1, n);curv.pop_back();}}}// 判断皇后位置是否合法bool isVaildPos(vector<pair<int, int>>& curv, int i, int j){for(auto& pos : curv){// 当有皇后在同一行，同一列，同一斜线上时，返回false// 斜线判断：同一上斜线 -- 行数 + 列数 == 定值// 同一下斜线 == 行数 - 列数 == 定值if(pos.first == i || pos.second == j || pos.first + pos.second == i + j || pos.first - pos.second == i - j)return false;}return true;}// 将全部可能的组合转换为字符串数组vector<vector<string>> transString(vector<vector<pair<int, int>>>& allRet, int n){vector<vector<string>> vv;for(auto& vpos : allRet){vector<string> vs(n, string(n, '.'));for(auto& pos : vpos){vs[pos.first][pos.second] = 'Q';}vv.push_back(vs);}return vv;}vector<vector<string>> solveNQueens(int n) {vector<vector<pair<int, int>>> allRet;vector<pair<int, int>> curv;DFS(allRet, curv, 0, n);return transString(allRet, n);}};

🧩4. 骆驼命名法

🍬原题链接：骆驼命名法

🍭算法思想：

实现题，没有难度，实现见代码：

🍡代码实现：

#include <iostream>#include <string>#include <vector>#include <cctype>using namespace std;int main(){vector<string> v;string line;while (cin >> line){v.push_back(line);}for (auto& str : v){// 遍历字符串for (auto iter = str.begin(); iter != str.end(); ){// 当前位置为'_'时，将其删除，并将后面的字母变为大写if (*iter == '_'){iter = str.erase(iter);if (isalpha(*iter)){*iter = toupper(*iter);}}// 否则就遍历下一个字符else{++iter;}}}for (auto& str : v){cout << str << endl;}return 0;}

🧸5. 单词倒排

🍬原题链接：单词倒排

🍭算法思想：

同样是实现题，将字符串切割，分割出单独的单词，最后拼合打印即可。

🍡代码实现：

#include <iostream>#include <string>#include <vector>#include <cctype>using namespace std;int main(){string str;getline(cin, str);vector<string> v;int begin = 0;int end = 0;bool flag = false; // false 为无效字符 true 为有效字符for (int i = 0; i < str.size(); ++i){bool isal = isalpha(str[i]); // 这个字符是否为有效字符// 开始记录有效字符if (isal && flag == false){flag = true;begin = i;}// 有效字符结束，将其插入数组else if (!isal && flag == true){flag = false;end = i;v.push_back(str.substr(begin, end - begin));}}// 给定字符串以字母结尾时，最后一个单词还未被记录，在这里记录if (flag == true){v.push_back(str.substr(begin));}for (auto iter = v.rbegin(); iter != v.rend(); ++iter){cout << *iter << " ";}cout << endl;return 0;}

🪅6. 乒乓球筐

🍬原题链接：乒乓球筐

🍭算法思想：

先利用哈希表对A中的乒乓球种类进行计数，再用先前的哈希表对B中乒乓球进行减数，遇到和A中相同的乒乓球种类计数减1，当计数减为负数或者没有对应种类的乒乓球时，就为No，反之为Yes。

🍡代码实现：

#include <iostream>#include <string>#include <unordered_map>using namespace std;int main(){string s1, s2;while (cin >> s1 >> s2){unordered_map<char, int> smap;bool flag = true;// 对A中乒乓球进行计数for (char c : s1){smap[c]++;}// 遍历B中乒乓球，减数// 如果没有对应的种类，根据[]的用法，会将c插入，并且直接对默认计数--，使其小于0for (char c : s2){int cnt = --smap[c];if (cnt < 0){flag = false;break;}}if (flag)cout << "Yes" << endl;elsecout << "No" << endl;}return 0;}

🪆7. 查找兄弟单词

🍬原题链接：查找兄弟单词

🍭算法思想：

先利用multiset统计源单词的字母，再用multiset分别统计其他单词。先判断源单词和其他单词是否相等，如果相等，不是兄弟单词；如果不相等，再逐个比较字母是否相等，只要不相等或者长度不等，就不为兄弟单词，全部相等才为兄弟单词。最后，按字典序打印第k个兄弟单词，如果最后兄弟单词总数都没有k个，则不打印。

🍡代码实现：

#include <iostream>#include <algorithm>#include <vector>#include <string>#include <set>using namespace std;bool isBro(string& src, string& s, multiset<char>& cst){if (src == s)return false;multiset<char> tmp;for (char c : s)tmp.insert(c);auto it1 = cst.begin(), it2 = tmp.begin();while (it1 != cst.end() && it2 != tmp.end()){if (*it1 != *it2)return false;it1++;it2++;}if (it1 != cst.end() || it2 != tmp.end())return false;return true;}int main(){int n;cin >> n;vector<string> vs;string word;while (n--){cin >> word;vs.push_back(word);}string src;cin >> src;int rank;cin >> rank;// 将源字符串字符插入setmultiset<char> cst;multiset<string> ss; // 存放兄弟单词for (char c : src){cst.insert(c);}// 判断一个字符是否是源词的兄弟单词for (string& s : vs){if (isBro(src, s, cst)){ss.insert(s);}}cout << ss.size() << endl;auto iter = ss.begin();if (rank > ss.size()){return 0;}else{while (--rank)++iter;if (iter != ss.end())cout << *iter << endl;}return 0;}

🪀8. 简单错误记录

🍬原题链接：简单错误记录

🍭算法思想：

这道题的限制条件很恶心： 首先，只有文件名（或者后16个字符）以及行号完全相等才算相同的错误，即使前面的路径不同或者后16位前的字符不同。其次，相同记录以第一次出现时间的为准，也就是说太前面出现过，即使在最后八条出现了相同记录，也不能显示。 知道了限制条件以后就可以开始做题了： 首先，先反向搜索出最后一个\，保留\后的部分，如果没有\，说明直接就是文件名，全保留。当前，以上保留的文件名最多16位，多了进行截断。其次，用一个数组记录字符串第一次出现的顺序，同时，用一个哈希表记录一个字符串出现了多少次。最后，选出最后出现的8个字符串，并打印其出现的次数。

🍡代码实现：

#include <iostream>#include <string>#include <vector>#include <unordered_map>using namespace std;int main(){vector<pair<string, string>> raw; // 原始字符串string str, num;vector<string> times; // 记录字符串第一次出现的相对顺序unordered_map<string, int> um; // 记录所有字符串出现的次数while (cin >> str >> num){raw.emplace_back(str, num);}for (auto& sp : raw){string tmp;size_t pos = sp.first.rfind('\\');// 当原字符串直接是文件名时if (pos == string::npos){tmp = sp.first + " " + sp.second;//times.push_back(sp.first + " " + sp.second);}else{size_t dist = sp.first.size() - pos - 1; // 算出文件名长度if (dist > 16){tmp = sp.first.substr(sp.first.size() - 16) + " " + sp.second;}else{tmp = sp.first.substr(pos + 1) + " " + sp.second;}}// 查看是否曾经出现过if (!um.count(tmp))// 未出现过就保存，保证相对顺序times.push_back(tmp);um[tmp]++;}int begin = times.size();begin = begin - 8 >= 0 ? begin - 8 : 0;for (; begin < times.size(); ++begin){cout << times[begin] << " " << um[times[begin]] << endl;}return 0;}

🎴9. 合唱团

🍬原题链接：合唱团

🍭算法思想：

动态规划题目，直接用DFS会超时。状态：vmax[i][j]—— 选择i个元素，最后一个成员的编号为j的最大值。vmin[i][j]—— 选择i个元素，最后一个成员的编号为j的最小值。 因为这个题目中会有负数的能力值，最大正数相乘负数一下直接就变最小了，而最小负数乘负数却可能成为最大值，所以必须有一个记录最大值，一个记录最小值。状态转移方程： v m a x [ i ] [ j ] = m a x ( v m a x [ i − 1 ] [ j − d + k ] ∗ v a l s [ j ] , v m i n [ i − 1 ] [ j − d + k ] ∗ v a l s [ j ] ) ( 0 < k < d + 1 , v a l s 为能力值数组 ) vmax[i][j] = max(vmax[i - 1][j - d + k] * vals[j], vmin[i - 1][j - d + k] * vals[j])(0<k< d + 1,vals为能力值数组) vmax[i][j]=max(vmax[i−1][j−d+k]∗vals[j],vmin[i−1][j−d+k]∗vals[j])(0<k<d+1,vals为能力值数组) 在选择了i-1个的人，最后一个尾号为(j-d)~(j-1)的最大值 * 当前人物的能力值 和 选择了i-1个的人，最后一个尾号为(j-d)~(j-1)的最小值 * 当前人物的能力值中 选最大值。为何要遍历(j-d)~(j-1)呢？因为，最后编号为j-1的不能保证就是选i - 1个人中的最大值或者最小值，所以要遍历保证选中。 初始状态： v m a x [ 1 ] [ j ] = v a l s [ j ] , v m i n [ 1 ] [ j ] = v a l s [ j ] vmax[1][j] = vals[j],vmin[1][j]=vals[j] vmax[1][j]=vals[j],vmin[1][j]=vals[j]，选一个人末尾编号为j的最大最小能力值都是他本身。结果：遍历规划数组，选出最大能力值的成绩。

🍡代码实现：

#include <iostream>#include <vector>#include <climits>using namespace std;int main(){int n;cin >> n;vector<int> vals(n + 1);for (int i = 1; i <= n; ++i)cin >> vals[i];int k, d;cin >> k >> d; // k 为选出的人数，d 为编号最大差值vector<vector<long long>> vmax(k + 1, vector<long long>(n + 1, 0)); // 选择i个元素，最后一个元素的编号为j的最大值vector<vector<long long>> vmin(k + 1, vector<long long>(n + 1, 0)); // 选择i个元素，最后一个元素的编号为j的最小值，因为有负数// 初始化选择一个，最后元素为j的值for (int j = 1; j <= n; ++j){vmax[1][j] = vmin[1][j] = vals[j];}long long res = 0;// 尾号为j的人for (int j = 1; j <= n; ++j){// 拿i个人for (int i = 2; i <= k; ++i){// j - d <= m <= j - 1for (int m = j - 1; m >= max(1, j - d); --m){vmax[i][j] = max(vmax[i][j], max(vmax[i - 1][m] * vals[j], vmin[i - 1][m] * vals[j]));vmin[i][j] = min(vmin[i][j], min(vmax[i - 1][m] * vals[j], vmin[i - 1][m] * vals[j]));}}// 选取拿了k个中尾号为j的最大值res = max(res, vmax[k][j]);}cout << res << endl;return 0;}

🃏10. 马戏团

🍬原题链接：马戏团

🍭算法思想：

这道题巨坑，题目描述不清楚，相同体重身高相同的人才能站在身上，不然，即使体重相同身高高于前者，也不能让前者站在自己肩上。并且，测试用例里面有体重为0或者负数的存在，所以如果你空间开辟了n + 1个，很容易就会将第一个不用的数据排序时放到后n个位置。思路见代码

🍡代码实现：

第一次的思路，直接DFS，不加任何优化，果然超时。

#include <iostream>#include <vector>#include <queue>#include <unordered_set>using namespace std;struct employee{int no;int weight;int height;};void DFS(vector<employee>& v, unordered_set<int>& book, vector<int>& vals, int prevNo, int high, int start){//if (vals[prevNo] > -1)//return;bool isLast = true;for (int i = 1; i < v.size(); ++i){if (prevNo == 0){book.insert(i);DFS(v, book, vals, i, 1, i);book.erase(book.find(i));}else{// 满足题意且没有使用过的员工才可继续递归if (v[i].height <= v[prevNo].height && v[i].weight <= v[prevNo].weight && !book.count(i)){isLast = false;book.insert(i);DFS(v, book, vals, i, high + 1, start);book.erase(book.find(i));}}}if (isLast){vals[start] = max(high, vals[start]);}}int main(){int n;cin >> n;vector<employee> v(n + 1);int no, weight, height;for (int i = 0; i < n; ++i){cin >> no >> weight >> height;v[no] = {no, weight, height };}unordered_set<int> book(n + 1);vector<int> vals(n + 1);DFS(v, book, vals, 0, 0, 0);int Max = 0;for (int i = 1; i < vals.size(); ++i){Max = max(Max, vals[i]);}cout << Max << endl;return 0;}

第二次，DFS+记忆化搜索+身高体重排序，成功通过，没有测试不排序会不会超时。

#include <iostream>#include <vector>#include <queue>#include <unordered_set>#include <algorithm>using namespace std;struct employee{int no;int weight;int height;};// v是员工的数据数组，book记录哪个员工已经使用过，vals是以i号员工为底座，最高能垒多少个，prevNo是下面的人的编号，high是当前高度，start为以start号员工为底座开始的递归void DFS(vector<employee>& v, unordered_set<int>& book, vector<int>& vals, int prevNo, int high, int start){// 记忆化，遇到之前搜索过的直接返回if (vals[prevNo] > 1)return;for (int i = prevNo - 1; i > 0; --i){// 满足题意且没有使用过的员工才可继续递归if (v[i].height <= v[prevNo].height&& !book.count(i)){book.insert(i);DFS(v, book, vals, i, high + 1, start);book.erase(book.find(i));vals[start] = max(vals[start], vals[i] + 1);}}}int main(){int n;while (cin >> n){vector<employee> v(n + 1);// tnnd，有一个体重为0的人！！这题的大坑v[0].weight = -10000000;v[0].height = -11111111;int no, weight, height;for (int i = 0; i < n; ++i){cin >> no >> weight >> height;v[no] = {no, weight, height };}unordered_set<int> book(n + 1);vector<int> vals(n + 1, 1);int Max = 0;// 按体重升序排列，体重相同时按身高降序排列sort(v.begin(), v.end(), [](const employee& e1, const employee& e2) {if (e1.weight != e2.weight)return e1.weight < e2.weight;elsereturn e1.height > e2.height;});for (int i = 1; i < v.size(); ++i){book.insert(i);DFS(v, book, vals, i, 1, i);book.erase(book.find(i));Max = max(Max, vals[i]);}cout << Max << endl;}return 0;}

动态规划，思路就是最大上升字符串的变式：

先按照按体重升序排列，体重相同时，按身高降序对员工进行排列，身高按降序的理由是体重相同时，身高高的人不能在低的人下面，为了防止体重相同，身高较低的人的干扰，这样排序最好。

状态：vals[i] -- 以第i个员工为底座最多能垒几个人

状态转移方程：

i f ( v [ j ] . h e i g h t < = v [ i ] . h e i g h t ) v a l s [ i ] = m a x ( v a l s [ i ] , v a l s [ j ] + 1 ) ; if (v[j].height <= v[i].height) \\ vals[i] = max(vals[i], vals[j] + 1); if(v[j].height<=v[i].height)vals[i]=max(vals[i],vals[j]+1);

遍历i号之前的vals，如果i号员工的身高大于等于前面员工的身高，就尝试更新（体重已经按升序排列，不用考虑前面会出现体重大于i号员工的情况）

初始状态：vals[0] = 1

目标状态：max(vals[i])(0 <= i <= n - 1)

#include <iostream>#include <vector>#include <queue>#include <unordered_set>#include <algorithm>using namespace std;struct employee{int no;int weight;int height;};int main(){int n;while (cin >> n){vector<employee> v(n);int no, weight, height;for (int i = 0; i < n; ++i){cin >> no >> weight >> height;v[i] = {no, weight, height };}vector<int> vals(n, 1);// 按体重升序排列，体重相同时按身高降序排列sort(v.begin(), v.end(), [](const employee& e1, const employee& e2) {if (e1.weight != e2.weight)return e1.weight < e2.weight;elsereturn e1.height > e2.height;});int Max = 0;for (int i = 1; i < n; ++i){for (int j = 0; j < i; ++j){if (v[j].height <= v[i].height)vals[i] = max(vals[i], vals[j] + 1);} Max = max(Max, vals[i]);}cout << Max << endl;}return 0;}

🀄11. 左右最值最大差

🍬原题链接：左右最值最大差

🍭算法思想：

分别记录左右部分的最大值，左部分从0开始记录一直到N-2，右部分从N-1开始记录一直到1。最后对应的两部分相减取最大的绝对值即可。

🍡代码实现：

class MaxGap {public:int findMaxGap(vector<int> A, int n) {vector<int> vleft(n, INT_MIN);int Max = INT_MIN;for (int i = 0; i <= n - 2; ++i){// 每走一步就记录最大值Max = max(Max, A[i]);vleft[i] = Max;}// 记录对应右边的最大值Max = INT_MIN;vector<int> vright(n, INT_MIN);for (int i = n - 1; i > 0; --i){Max = max(Max, A[i]);vright[i - 1] = Max;}int ret = INT_MIN;for (int i = 0; i <= n - 2; ++i)ret = max(ret, (int)fabs(vleft[i] - vright[i]));return ret;}};

♟️12. 顺时针打印矩阵

🍬原题链接：顺时针打印矩阵

🍭算法思想：

记录左上角和右下角坐标，作为边界。按照右、下、左、上的顺序遍历数组，记录遍历的数字，要控制边界条件，不要重复记录或者串行。具体实现见代码：

🍡代码实现：

class Printer {public:int NextPos[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0} };vector<int> clockwisePrint(vector<vector<int> > mat, int n, int m) {vector<int> ret;pair<int, int> leftTop = make_pair(0, 0);pair<int, int> rightBottom = make_pair(n - 1, m - 1);while (leftTop.first <= rightBottom.first && leftTop.second <= rightBottom.second){for (int i = leftTop.second; i <= rightBottom.second; ++i)ret.push_back(mat[leftTop.first][i]);for (int i = leftTop.first + 1; i <= rightBottom.first; ++i)ret.push_back(mat[i][rightBottom.second]);// 防止最后出现行重合情况if(leftTop.first < rightBottom.first)for (int i = rightBottom.second - 1; i >= leftTop.second; --i)ret.push_back(mat[rightBottom.first][i]);// 防止最后出现列重合情况if(leftTop.second < rightBottom.second)for (int i = rightBottom.first - 1; i > leftTop.first; --i)ret.push_back(mat[i][leftTop.second]);// 更新边界leftTop.first++;leftTop.second++;rightBottom.first--;rightBottom.second--;}return ret;}};

📙后记

这就是本次的题目推荐+解析了，白晨好久没有更新这个系列了，真的是想写的东西太多了，而时间又太少了。白晨准备更新完这一期后，暂时停止更新【刷题日记】系列了，准备将更多的精力投入到【网络】等后端技术系列。真的很感谢大家的支持，白晨虽然比较🕊，但是还是会保持高质量博客来回馈各位粉丝❤️。

如果解析有不对之处还请指正，我会尽快修改，多谢大家的包容。

如果大家喜欢这个系列，还请大家多多支持啦😋！

如果这篇文章有帮到你，还请给我一个大拇指👍和小星星⭐️支持一下白晨吧！喜欢白晨【刷题日记】系列的话，不如关注👀白晨，以便看到最新更新哟！！！

我是不太能熬夜的白晨，我们下篇文章见。