算法实战练习
持续更新~~
目录
前言
1. 奇1偶0
2. 最大消费额
3. 目录树生成
4. 75. 颜色分类
5. 合并两个有序数组
6. 206. 反转链表
前言
算法的学习离不开实战。经过一段时间的练习，我深刻体会到，只有通过解决实际问题，才能真正掌握算法的精髓，并将其灵活运用。这个博客系列记录了我通过实战练习后的心得和总结，涵盖了我从基础到进阶的解题思路、优化技巧以及代码实现。
在实战中，我逐渐意识到，算法不仅仅是“写对代码”，更是理解问题本质、设计高效解决方案的过程。每一道题目都让我对算法有了更深的理解，也让我更加注重细节和逻辑的严谨性。
这个系列将分享我在实战中遇到的典型问题，以及我的解题过程和优化思路。希望这些内容能为你的算法学习提供一些启发和帮助，也欢迎一起交流，共同进步！
1. 奇1偶0
给出一个数，这个数的每位如果是奇数就变为1，如果是偶数就变为0.
输入：2222 输出：0
输入：123 输出：101
#include <iostream>
#include <cmath>
using namespace std;
int modify_number(int n) {
int result = 0;
int place = 1; // 用于记录每一位的权重，类似于十进制的位数
while (n > 0) {
int digit = n % 10; // 获取当前数字的最低位
if (digit % 2 == 0) {
result += 0 * place; // 偶数变为 0
} else {
result += 1 * place; // 奇数变为 1
}
n /= 10; // 去掉最低位
place *= 10; // 更新权重
}
return result;
}
int main() {
// 测试
cout << modify_number(222) << endl; // 输出 0
cout << modify_number(123) << endl; // 输出 101
return 0;
}
2. 最大消费额
第一行给出 m 张桌子和 n 批客人。
第二行给出 m 个数字，代表每张桌子能容纳的人数。
接下来的 n 行给出每批客人的人数和消费金额。
你需要计算在不拼桌的情况下，求出最大消费金额。
输入：
3 5
2 4 2
3 100
2 50
1 30
4 80
2 40
输出：230
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> m >> n; // m 是桌子数量，n 是客人批次数量
vector<int> table_capacity(m); // 桌子的容量
for (int i = 0; i < m; ++i) {
cin >> table_capacity[i];
}
vector<pair<int, int>> customers(n); // 每批客人的人数和消费金额
for (int i = 0; i < n; ++i) {
cin >> customers[i].first >> customers[i].second;
}
// 排序：桌子容量从小到大，客人按消费金额从大到小排序
sort(table_capacity.begin(), table_capacity.end());
sort(customers.begin(), customers.end(), [](pair<int, int> a, pair<int, int> b) {
return a.second > b.second; // 按消费金额降序排序
});
int total_consumption = 0;
vector<bool> used_table(m, false); // 标记桌子是否已经被用过
// 遍历每批客人
for (auto& customer : customers) {
int customer_people = customer.first;
int customer_money = customer.second;
// 尝试找到合适的桌子
for (int i = 0; i < m; ++i) {
if (!used_table[i] && table_capacity[i] >= customer_people) {
// 找到一个未使用且足够容纳客人的桌子
total_consumption += customer_money;
used_table[i] = true; // 标记这个桌子已使用
break; // 一旦找到合适的桌子就跳出循环
}
}
}
cout << total_consumption << endl; // 输出最大消费金额
return 0;
}
3. 目录树生成
编写一个程序，解析给定的多个文件路径，并以树形结构打印出各个目录的层级关系。路径格式为Unix风格的路径，即各个目录由 / 分隔。根目录的子目录不需要前缀 -，其他目录按层级递归打印，子目录前面需要加上 - 并根据层级缩进。
示例输入：
5 /a/b/c /a/b/d /a/e /f/g /a/b/c/d/e示例输出：
a - b - c - d - e - d - e f - g
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
class Node {
public:
string name;
map<string, Node*> children;
Node(const string& name) : name(name) {}
};
vector<string> split(const string& path) {
vector<string> parts;
string part;
for (char c : path) {
if (c == '/') {
if (!part.empty()) {
parts.push_back(part);
part.clear();
}
} else {
part += c;
}
}
if (!part.empty()) {
parts.push_back(part);
}
return parts;
}
Node* buildTree(const vector<vector<string>>& allParts) {
Node* root = new Node("");
for (const auto& parts : allParts) {
Node* parent = root;
for (const string& part : parts) {
if (parent->children.find(part) == parent->children.end()) {
parent->children[part] = new Node(part);
}
parent = parent->children[part];
}
}
return root;
}
void printTree(Node* node, int indent) {
string spaces(indent, ' ');
cout << spaces << "- " << node->name << endl;
for (const auto& childEntry : node->children) {
printTree(childEntry.second, indent + 2);
}
}
void deleteTree(Node* root) {
if (!root) return;
for (auto& entry : root->children) {
deleteTree(entry.second);
}
delete root;
}
int main() {
int n;
cin >> n;
cin.ignore();
vector<vector<string>> allParts;
for (int i = 0; i < n; ++i) {
string path;
getline(cin, path);
allParts.push_back(split(path));
}
Node* root = buildTree(allParts);
for (const auto& entry : root->children) {
Node* node = entry.second;
cout << node->name << endl;
for (const auto& childEntry : node->children) {
printTree(childEntry.second, 2);
}
}
deleteTree(root);
return 0;
}4. 75. 颜色分类
中等
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
提示：n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
class Solution {
public:
void sortColors(vector<int>& nums) {
int p0{}, p1{}; // 初始化两个指针p0和p1，分别用于追踪0和1的边界
int n = nums.size(); // 获取数组的长度
// 遍历数组
for(int i{}; i < n; ++i) {
if(nums[i] == 1) {
// 如果当前元素是1，将其与p1指针指向的元素交换，然后p1向前移动
swap(nums[i], nums[p1++]);
} else if(nums[i] == 0) {
// 如果当前元素是0，将其与p0指针指向的元素交换
swap(nums[i], nums[p0]);
// 如果p0小于p1，说明p0指针刚交换过来的1需要与p1指针处的元素交换
if(p0 < p1) {
swap(nums[i], nums[p1]);
}
// p0和p1都向前移动
++p0;
++p1;
}
}
}
};5. 合并两个有序数组
给出两个有序数组A和B，它们的元素个数分别是m和n，数组A的数组大小是m+n，将数组B合并到数组A中。
输入：[1,3,5] [2,4,6]
输出：[1,2,3,4,5,6]
#include <iostream>
void mergeSortedArraysInPlace(int a[], int m, int b[], int n) {
int i = m - 1; // 数组 a 的末尾
int j = n - 1; // 数组 b 的末尾
int k = m + n - 1; // 合并后的数组末尾
// 从后向前合并
while (i >= 0 && j >= 0) {
if (a[i] > b[j]) {
a[k--] = a[i--];
} else {
a[k--] = b[j--];
}
}
// 如果数组 b 还有剩余元素
while (j >= 0) {
a[k--] = b[j--];
}
}
int main() {
// 定义数组 a，假设有足够的空间
int a[6] = {2, 4, 6}; // 前 3 个元素有效，剩余空间足够
int b[] = {1, 3, 5};
// 数组长度
int m = 3; // 数组 a 的有效长度
int n = sizeof(b) / sizeof(b[0]); // 数组 b 的长度
// 合并数组 b 到数组 a
mergeSortedArraysInPlace(a, m, b, n);
// 输出合并后的数组 a
std::cout << "Merged Array: ";
for (int i = 0; i < m + n; i++) {
std::cout << a[i] << " "; // 输出: 1 2 3 4 5 6
}
return 0;
}6. 206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
class Solution {
public:
// 反转单链表的函数
ListNode* reverseList(ListNode* head) {
// 如果链表为空，直接返回空指针
if(!head) return {};
// 定义两个指针，pre用于指向反转后链表的前一个节点，cur用于遍历链表
ListNode* pre = nullptr; // 初始时pre指向空
ListNode* cur = head; // cur指向链表的头节点
// 遍历链表
while(cur) {
// 保存当前节点的下一个节点
ListNode* node = cur->next;
// 反转当前节点的指向
cur->next = pre;
// 更新pre和cur指针
pre = cur; // pre指向当前节点
cur = node; // cur指向下一个节点
}
// 返回新的头节点，即反转后的链表头
return pre;
}
};