当前位置： 首页 > news >正文

【刷题日记】笔试经典编程题目（八）

news 来源：原创 2024/5/21 5:17:51

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

在这里插入图片描述

文章目录

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

📗前言

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

img

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

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

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

🔮1. 电话号码

image-20220919223245659

🍬原题链接：电话号码

🍭算法思想：

  • 这道题就是一道实现题，利用哈希的思想将其对应翻译出来，再放入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']);
				else
					continue;

				if (snum.size() == 3)
					snum += '-';
			}
			ss.insert(snum);
		}

		for (auto& s : ss)
		{
			cout << s << endl;
		}

		cout << endl;

	}

	return 0;
}

🪄2. 求和

image-20220919223637724

🍬原题链接：求和

🍭算法思想：

  • 直接上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 皇后

image-20220919234710173

🍬原题链接：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. 骆驼命名法

image-20220920091719413

🍬原题链接：骆驼命名法

🍭算法思想：

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

🍡代码实现：

#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. 单词倒排

image-20220920091934905

🍬原题链接：单词倒排

🍭算法思想：

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

🍡代码实现：

#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. 乒乓球筐

image-20220921210441218

🍬原题链接：乒乓球筐

🍭算法思想：

  • 先利用哈希表对 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插入，并且直接对默认计数--，使其小于0
        for (char c : s2)
        {
            int cnt = --smap[c];
            if (cnt < 0)
            {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

🪆7. 查找兄弟单词

image-20220921210843421

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

🍭算法思想：

  • 先利用 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;

    // 将源字符串字符插入set
    multiset<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. 简单错误记录

image-20220923104414501

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

🍭算法思想：

  • 这道题的限制条件很恶心：
    • 首先，只有文件名（或者后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. 合唱团

image-20220923133324408

🍬原题链接：合唱团

🍭算法思想：

  • 动态规划题目，直接用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 - 1
			for (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. 马戏团

image-20220923133617053

🍬原题链接：马戏团

🍭算法思想：

  • 这道题巨坑，题目描述不清楚，相同体重身高相同的人才能站在身上，不然，即使体重相同身高高于前者，也不能让前者站在自己肩上。并且，测试用例里面有体重为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;
			else
				return 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;
			else
				return 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. 左右最值最大差

image-20220924222609910

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

🍭算法思想：

  • 分别记录左右部分的最大值，左部分从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. 顺时针打印矩阵

image-20220924222631747

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

🍭算法思想：

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

🍡代码实现：

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;
    }
};

📙后记

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

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

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

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

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

相关文章：

  • 阿里巴巴编程规范实战(一)：编程规约之常量定义代码格式
  • 人生苦短 我用Python，零基础运行你的第一行Python代码
  • zabbix案例--zabbix监控nginx状态
  • 《Rust权威指南》读书笔记 - Chapter 1, 2
  • 框架学习——ElasticSearch分布式搜索框架
  • 羊了个羊数据结构分析与代码简单实现
  • Linux驱动开发10 --- 内存和I/O
  • 【大模型迁移 2022】Exploring Visual Prompts for Adapting Large-Scale Models
  • RDKit计算摩根分子描述符
  • 从事网络安全工作一定要科班出身吗？
  • 【BERT-多标签文本分类实战】之四——数据集预处理
  • FreeSWITCH 1.10 源码阅读(2)-xml_curl 模块原理
  • springboot+旅游网站 毕业设计-附源码211713
  • Java：Java和C++哪个更好
  • WebGL编程指南-20 三维视图对象前后关系的处理/隐藏面消除与深度冲突处理
  • [译] React v16.8： 含有Hooks的版本
  • 「面试题」如何实现一个圣杯布局？
  • 【译】理解JavaScript：new 关键字
  • 2019年如何成为全栈工程师？
  • 4月23日世界读书日 网络营销论坛推荐《正在爆发的营销革命》
  • Angular Elements 及其运作原理
  • C++11: atomic 头文件
  • C++入门教程（10）：for 语句
  • ECMAScript6(0)：ES6简明参考手册
  • input实现文字超出省略号功能
  • Intervention/image 图片处理扩展包的安装和使用
  • isset在php5.6-和php7.0+的一些差异
  • JavaScript 一些 DOM 的知识点
  • Just for fun——迅速写完快速排序
  • leetcode98. Validate Binary Search Tree
  • mongodb--安装和初步使用教程
  • Otto开发初探——微服务依赖管理新利器
  • pdf文件如何在线转换为jpg图片
  • python 学习笔记 - Queue Pipes，进程间通讯
  • REST架构的思考
  • 前端技术周刊 2019-01-14：客户端存储
  • 驱动程序原理
  • 算法---两个栈实现一个队列
  • 通信类
  • 正则学习笔记
  • 正则表达式-基础知识Review
  • ​LeetCode解法汇总307. 区域和检索 - 数组可修改
  • ​如何在iOS手机上查看应用日志
  • #pragam once 和 #ifndef 预编译头
  • #周末课堂# 【Linux + JVM + Mysql高级性能优化班】（火热报名中~~~）
  • (1)Map集合 (2)异常机制 (3)File类 (4)I/O流
  • （3）llvm ir转换过程
  • (Matlab)基于蝙蝠算法实现电力系统经济调度
  • （python）数据结构---字典
  • （附源码）ssm高校升本考试管理系统 毕业设计 201631
  • （规划）24届春招和25届暑假实习路线准备规划
  • （十）DDRC架构组成、效率Efficiency及功能实现
  • （十八）三元表达式和列表解析
  • (一)为什么要选择C++
  • （转）linux 命令大全