【华为OD：C++机试】Day-4

news/2024/7/20 19:18:45 标签: 华为od, c++, 算法

目录

🌷1. 排队游戏：

🌷2. 购物：

🌷3. 划分字符串：

🌷4. MELON 的难题：

🌷5. 荒岛求生：

🌷6. 通过软盘拷贝文件：

🌷7. 数字序列比大小：

🌷8. 树状结构查询：

🌷9. 评论转换输出：

🌷10. 找出两个整数数组中同时出现的整数：


🌷1. 排队游戏：

题目描述：

code： 

// 排队游戏
#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int sum(const vector<int>& capacity, int n)
{
	int count = 0;
	for (int i = 0; i < n; i++)
		if (capacity[i] > capacity[n])
			count++;
	return count;
}

int main()
{
	int n, m, k;
	cin >> n >> m >> k;

	// 用于存储刺头学生位置
	unordered_set<int> set;
	for (int i = 0; i < m; i++)
	{
		int num;
		cin >> num;
		set.insert(num);
	}

	// 用于存储学生的能力值
	vector<int> capacity(n);
	for (int i = 0; i < n; i++)
	{
		cin >> capacity[i];
	}

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (!set.count(i))
			ans += sum(capacity, i);
	}

	if (ans > k)
		cout << 1 << endl;
	else
		cout << 0 << endl;
	return 0;
}
🌷2. 购物：

题目描述：

code： 

// 购物
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int>& price, int startindex, vector<bool>& used)
{
	result.push_back(path);
	for (int i = startindex; i < price.size(); i++)
	{
		// 如果要去重的话，则要加上下面的语句 和 used语句
		//if (i > 0 && price[i] == price[i - 1] && used[i-1] == false) continue;
		path.push_back(price[i]);
		//used[i] = true;
		backTracking(price, i + 1, used);
		path.pop_back();
		//used[i] = false;
	}
}

int main()
{
	// 分别读入：物品的个数 和 总价钱
	int n, k;
	cin >> n >> k;

	vector<bool> used(n, false);

	// 读入各个物品的价格
	vector<int> price(n);
	for (auto& e : price)
		cin >> e;

	// 将上面数组中所有的子集存放到result数组中
	backTracking(price, 0, used);

	// ans数组存放各子集的和
	vector<int> ans;
	for (const auto& s : result)
	{
		int sum = 0;
		for (const auto& e : s)
			sum += e;
		ans.push_back(sum);
	}

	sort(ans.begin(), ans.end());

	for (int i = 1; i <= k; i++)
		cout << ans[i] << endl;

	return 0;
}
🌷3. 划分字符串：

题目描述：

code： 

// 划分字符串
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int left_sum(const vector<int>& save, int k)
{
	int sum = 0;
	for (int i = 0; i < k; i++)
		sum += save[i];
	return sum;
}

int right_sum(const vector<int>& save, int j)
{
	int sum = 0;
	for (int i = j + 1; i < save.size(); i++)
		sum += save[i];
	return sum;
}

vector<int> find_value(const string& str)
{
	// 判断字符串的不合法性
	if (str.size() < 5 || str.size() > 30)
		return { 0, 0 };

	// 将字符串转换为数字存储在数组中
	vector<int> save;
	for (auto& e : str)
		save.push_back(static_cast<int>(e));

	// 求出数组中的所有元素的和
	int sum = 0;
	for (const auto& e : save)
		sum += e;

	for (int i = 1; i < save.size() - 1; i++)
	{
		int target = save.size() - 2;
		while (i < target)
		{
			int left = left_sum(save, i);
			int right = right_sum(save, target);
			int mid_sum = sum - left - right - save[i] - save[target];
			if (left == right && left == mid_sum)
				return { i, target };
			target--;
		}
	}
	return { 0,0 };
}

int main()
{
	// 用于存储输入的字符串
	string str;
	cin >> str;

	vector<int> index = find_value(str);
	cout << index[0] << ',' << index[1] << endl;

	return 0;
}
🌷4. MELON 的难题：

题目描述：

code： 

// MELON的难题
#include <iostream>
#include <vector>

using namespace std;

int half = 0;
int min_count = INT_MAX;

void solve_method(const vector<int>& save, int count, vector<int>& lst, int index)
{
	if (count == half)
	{
		if (index < min_count)
			min_count = index;
		if (save.size() - index < min_count)
			min_count = save.size() - index;
	}
	else
	{
		for (int i = index; i < save.size(); i++)
		{
			lst[index] = save[i];
			count += lst[index];
			if(count <= half && ( index < min_count || save.size() - index < min_count))
				solve_method(save, count, lst, index + 1);
			count -= lst[index];
		}
	}
}

int main()
{
	int n;
	cin >> n;

	// 将雨花石的重量存在数组中
	vector<int> save(n);
	for (auto& e : save)
		cin >> e;

	// 求出雨花石的重量总和
	int sum = 0;
	for (const auto& e : save)
		sum += e;

	// 判断雨花石的重量是否可以整除2
	if (sum % 2 != 0)
		cout << -1 << endl;
	else
	{
		half = sum / 2;
		vector<int> lst(n);
		solve_method(save, 0, lst, 0);
		cout << min_count << endl;
	}
	return 0;
}
🌷5. 荒岛求生：

题目描述：

code： 

// 荒岛求生
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <sstream>

using namespace std;

vector<int> exchange(const string& str)
{
	stringstream ss(str);
	string s;
	vector<int> save;
	while (getline(ss, s, ' '))
		save.push_back(stoi(s));
	return save;
}

int main()
{
	string str;
	getline(cin, str);

	vector<int> save = exchange(str);

	stack<int> st;
	int i = 1;
	int count = 0;
	st.push(save[0]);
	while (i < save.size())
	{
		if ((save[i - 1] < 0 && save[i] < 0) || (save[i - 1] > 0 && save[i] > 0))
				st.push(save[i++]);
		else
		{
			int top = st.top();
			st.pop();
			int c = top + save[i];
			if (c != 0)
			{
				if (c > 0 && top > 0)
				{
					count++;
					st.push(c);
				}
				else
				{
					count--;
					save[i] = c;
				}
			}
			else
			{
				save.erase(save.begin() + i);
			}
		}

	}
	cout << count + st.size() << endl;
	return 0;
}
🌷6. 通过软盘拷贝文件：

题目描述：

code： 

// 通过软件拷贝文件
#include <iostream>
#include <vector>

using namespace std;

int bag = 1474560 / 512;

int main()
{
	int n;
	cin >> n;

	// 存储文件的容量
	vector<int> cap(n);
	for (auto& e : cap)
		cin >> e;

	// 存储文件所占的块数
	vector<int> wei(n);
	for (int i = 0; i < n; i++)
	{
		if (cap[i] % 512 == 0)
			wei[i] = cap[i] / 512;
		else
			wei[i] = cap[i] / 512 + 1;
	}

	// 动态规划数组记录背包容量下的最大价值
	vector<int> dp(bag + 1, 0);
	for (int i = 0; i < n; i++)
	{
		for (int j = bag; j >= wei[i]; j--)
			dp[j] = max(dp[j], dp[j - wei[i]] + cap[i]);
	}

	// 输出最大值
	cout << dp[bag] << endl;
	return 0;
}
🌷7. 数字序列比大小：

题目描述：

code： 

// 数字序列比大小
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> a(n);
	vector<int> b(n);
	for (auto& e : a)
		cin >> e;

	cin.ignore();

	for (auto& e : b)
		cin >> e;

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		int num = a[i];
		if (num < b[0])
		{
			ans--;
			b.pop_back();
		}
		else
		{
			if (num > b[0])
				ans++;
			b.erase(b.begin());
		}
	}
	cout << ans << endl;
	return 0;
}
🌷8. 树状结构查询：

题目描述：

code： 

// 树状结构查询
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
	// 总共有多少行数据
	int n;
	cin >> n;

	// 以树状形式存储数据
	map<char, vector<char>> tree;
	for (int i = 0; i < n; i++)
	{
		char a, b;
		cin >> a >> b;
		tree[b].push_back(a);
	}

	// 要求的父节点
	char parent;
	cin >> parent;

	vector<char> child = tree[parent];
	vector<char> ans;
	while (!child.empty())
	{
		char c = child[0];
		child.erase(child.begin());
		ans.push_back(c);
		if (tree.count(c))
		{
			for (const auto& e : tree[c])
				child.push_back(e);
		}
	}

	sort(ans.begin(), ans.end());

	for (const auto& e : ans)
		cout << e << endl;

	return 0;
}
🌷9. 评论转换输出：

题目描述：

code： 

// 评论转换输出
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <list>

using namespace std;

list<string> exchange(const string& str)
{
	stringstream ss(str);
	string s;
	list<string> lst;
	while (getline(ss, s, ','))
		lst.push_back(s);
	return lst;
}

void ensure_level_exists(vector<vector<string>>& tree, int level)
{
	if (tree.size() < level)
		tree.push_back(vector<string>());
}

void recursive(list <string>& lst, int childCount, vector<vector<string>>& tree, int level)
{
	for (int i = 0; i < childCount; i++)
	{
		string comment = lst.front();
		lst.pop_front();
		ensure_level_exists(tree, level);
		tree[level - 1].push_back(comment);
		int child = stoi(lst.front());
		lst.pop_front();
		if (child > 0)
			recursive(lst, child, tree, level + 1);
	}
}

void printTree(vector<vector<string>>& tree)
{
	cout << tree.size() << endl;
	for (const auto& e : tree)
	{
		for (const auto& c : e)
		{
			cout << c << " ";
		}
		cout << endl;
	}
}

int main()
{
	// 用于存储输入的字符串
	string str;
	cin >> str;

	// 将字符串转换为数组进行存储
	list<string> lst = exchange(str);

	// 将数据以数的形式进行存储
	vector<vector<string>> tree;
	
	int level = 1;
	while (!lst.empty())
	{
		string comment = lst.front();
		lst.pop_front();
		ensure_level_exists(tree, level);
		tree[level - 1].push_back(comment);
		int child = stoi(lst.front());
		lst.pop_front();
		recursive(lst, child, tree, level + 1);
	}

	printTree(tree);

	return 0;
}
🌷10. 找出两个整数数组中同时出现的整数：

题目描述：

code： 

// 找出两个整数数组中同时出现的整数
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <map>
#include <algorithm>

using namespace std;

vector<int> exchange(const string& str)
{
	stringstream ss(str);
	string s;
	vector<int> save;
	while (getline(ss, s, ','))
		save.push_back(stoi(s));
	return save;
}

int main()
{
	string str1, str2;
	cin >> str1 >> str2;

	vector<int> a = exchange(str1);
	vector<int> b = exchange(str2);

	unordered_map<int, int> map1;
	unordered_map<int, int> map2;
	for (const auto& e : a)
		map1[e]++;

	for (const auto& e : b)
		map2[e]++;

	map<int, vector<int>> map;
	for (const auto& e : map1)
	{
		int num = e.first;
		int count = e.second;
		if (map2.count(num))
		{
			int n = min(count, map2[num]);
			map[n].push_back(num);
		}
	}

	if (map.empty())
		cout << "NULL" << endl;
	else
	{
		for (const auto& e : map)
		{
			int num = e.first;
			vector<int> cap = e.second;
			sort(cap.begin(), cap.end());
			cout << num << ":";
			for (int i = 0; i < cap.size(); i++)
			{
				if (i != cap.size() - 1)
					cout << cap[i] << ',';
				else
					cout << cap[i] << endl;
			}
		}
	}

	return 0;
}

坚持打卡！😃


http://www.niftyadmin.cn/n/5170402.html

相关文章

python3GUI--PyQt5打包心得（二）nuitka、inno Setup（详细图文演示、附所有软件）

python3GUI--PyQt5打包心得（二）nuitka、inno Setup（详细图文演示、附所有软件）

文章目录 一&#xff0e;前言二&#xff0e;准备1.nuitka1.1介绍1.3项目地址1.3安装 2.mingw641.1介绍1.2下载安装 3.Inno Setup1.1介绍1.2安装 三&#xff0e;nuitka打包1.打包2.装mingw643.装ccahe4.打包完成 四&#xff0e;测试效果五&#xff0e;inno Setup制作安装软件1.配…
阅读更多...
在Java继承关系中变量访问规则

在Java继承关系中变量访问规则

首先示例代码如下&#xff1a; class A{public int x 0;public int get() {return x;}}class AA extends A{public int x 1; }class AAA extends AA {public int x 2;public int get() {return x;}public static void main(String[] args) {A a new AA();System.out.pri…
阅读更多...
【论文阅读】FreeMatch: Self-adaptive Thresholding for Semi-supervised Learning

【论文阅读】FreeMatch: Self-adaptive Thresholding for Semi-supervised Learning

论文下载 GitHub bib: INPROCEEDINGS{wang2023freematch,title {FreeMatch: Self-adaptive Thresholding for Semi-supervised Learning},author {Wang, Yidong and Chen, Hao and Heng, Qiang and Hou, Wenxin and Fan, Yue and and Wu, Zhen and Wang, Jindong and Savv…
阅读更多...
自媒体项目详述

自媒体项目详述

总体框架 本项目主要着手于获取最新最热新闻资讯&#xff0c;以微服务构架为技术基础搭建校内仅供学生教师使用的校园新媒体app。以文章为主线的核心业务主要分为如下子模块。自媒体模块实现用户创建功能、文章发布功能、素材管理功能。app端用户模块实现文章搜索、文章点赞、…
阅读更多...
js 变量、对象的类型判断

js 变量、对象的类型判断

// 如果比较简单的判断 typeof a // "string" typeof true // "boolean" typeof undefined // "undefined" typeof [] // object typeof {} // object typef null // object // 如果要区分object类型&#xff0c;为null, 还是null, 还是{}&…
阅读更多...
【论文阅读笔记】Detecting AI Trojans Using Meta Neural Analysis

【论文阅读笔记】Detecting AI Trojans Using Meta Neural Analysis

个人阅读笔记&#xff0c;如有错误欢迎指出&#xff01; 会议&#xff1a;2021 S&P Detecting AI Trojans Using Meta Neural Analysis | IEEE Conference Publication | IEEE Xplore 问题&#xff1a; 当前防御方法存在一些难以实现的假设&#xff0c;或者要求直…
阅读更多...
windows下QZipReader和QZipWriter解压缩zip格式文件(只针对纯文件，递归目前暂不处理)

windows下QZipReader和QZipWriter解压缩zip格式文件(只针对纯文件，递归目前暂不处理)

# 运行效果 ui设计文件 采用了网格布局，组件跟随窗口最大化最小化 # .pro项目文件 这段代码是一个项目文件（.pro文件）中的内容，用于配置一个Qt项目的构建和部署规则。它包含了一些指令和设置，用于指定项目中需要编译的源代码文件、头文件、UI表单文件以及项目所依赖的Qt…
阅读更多...
呼叫中心系统如果对接大模型

呼叫中心系统如果对接大模型

电话机器人对接大模型的例子 介绍 自chatgpt3.5发布以来&#xff0c;各种大模型飞速发展&#xff0c;各行各业都有接入大模型的需求&#xff0c;呼叫中心行业非常适合通过接入大模型用AI来回答用户的各种咨询&#xff0c;降低人力资源&#xff0c;使用顶顶通呼叫中心中间件&a…
阅读更多...
最新文章

Copyright @ 2022~2023