C++ 算法题常用工具函数

C/C++ May 3, 2021

C++ STL 提供的工具函数非常强大,但是对于不是经常使用拿来干活的人来说(比如我),经常会忘记如果使用这些函数。所以我专门写一篇来总结一下一些做算法常用的工具函数。

虽说现在 LeetCode 支持各种个样的编程语言提交,不过由于我从小到大做算法题都是用的 C++,成为传统的。按理说现在直接用js写会更快一些的。

集合求和

const data1 = [1,2,3]
const result1 = _.sum(data1)

const data2 = [{ a: 1 }, { a: 2 }, { a: 3 }]
const result2 = _.sumBy(data2, (i) => i.a)
const result3 = data2.reduce((result, i) => {
    result += i.a
    return result;
}, 0)
#include <numeric>      // std::accumulate

std::vector<int> data1 = {1,2,3};
int result1 = std::accumulate(data1.begin(), data1.end(), 0);

struct Item {
	int a;
};
std::vector<Item> data2 = {{1}, {2}, {3}};
auto result2 = std::accumulate(data2.begin(), data2.end(), 0, [](int& result, Item& i) {
	return result + i.a;
});

C++ 的 `std::accumulate`  相当于 JavaScript 的 `Array.reduce`

集合最大最小

const data1 = [1,2,3]
const max1 = _.max(data1)
const min1 = _.min(data1)

const data2 = [{ a: 1 }, { a: 2 }, { a: 3 }]
const max2 = _.maxBy(data2, (i) => i.a)
const min2 = _.minBy(data2, (i) => i.a)
#include <algorithm>    // std::min_element, std::max_element

std::vector<int> data1 = {1,2,3};
int max1 = std::max_element(data1.begin(), data1.end());
int min1 = std::min_element(data1.begin(), data1.end());

struct Item {
	int a;
};
std::vector<Item> data2 = {{1}, {2}, {3}};
auto max1 = std::max_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a < j.a;
});
auto min1 = std::min_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a < j.a;
});

C++ 的 `max_element` 和 `min_element` 的 comp function 很奇怪,都要求前一个元素比后一个元素小为 True。不知道为何 C++ 要如此设计。理论上这两个函数可以反着用。

auto max1 = std::min_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a > j.a;
});
auto min1 = std::max_element(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a > j.a;
});

二分查找

  • `std::lower_bound` 在前闭后开区间进行二分查找,返回大于或等于目标值的第一个元素位置。如果所有元素都小于目标值,则返回区间最后元素的位置。
  • `std::upper_bound` 在前闭后开区间查找的关键字的上界,返回大于目标值的第一个元素位置。如果目标值大于所有元素,则返回区间最后元素的位置。
  • `std::binary_search` 在前闭后开区间查找的关键字,返回是否存在的布尔值。
#include <algorithm>    // std::lower_bound, std::upper_bound

std::vector<int> data1 = {1,6,3,4,2};
sort(data1.begin(), data1.end());
auto result1 = std::lower_bound(data1.begin(), data1.end(), 4);
auto result2 = std::upper_bound(data1.begin(), data1.end(), 4);
bool result3 = std::binary_search(data1.begin(), data1.end(), 4);

struct Item {
	int a;
};
std::vector<Item> data2 = {{1}, {6}, {3}, {4}, {2}};
sort(data2.begin(), data2.end(), [](Item& i, Item& j) {
	return i.a < j.a;
});
auto result1 = std::lower_bound(data2.begin(), data2.end(), 4, [](Item& i, int target) {
	return i.a < target;
});
auto result2 = std::upper_bound(data2.begin(), data2.end(), 4, [](Item& i, int target) {
	return i.a < target;
});
bool result3 = std::binary_search(data2.begin(), data2.end(), 4, [](Item& i, int target) {
	return i.a < target;
});

交换值

#include <algorithm>    // std::swap, std::iter_swap

int a = 1; int b = 2;
std::swap(a, b);

std::vector<int> data1 = {1,6,3,4,2};
std::iter_swap(data1.begin()+1, data1.begin()+3);

字符串前后缀匹配

const text = "Hello World!"
text.startsWith("He")
text.endsWith("d!")
bool startsWith(std::string s, std::string sub) {
	return s.find(sub) == 0 ? true : false;
}

bool endsWith(std::string s, std::string sub) {
	return s.rfind(sub) == (s.length() - sub.length()) ? true : false;
}

map/transform

const data = [1,2,3]
const result = data.map((i) => {
    return { a: i }
})
#include <algorithm> // std::transform

struct Item {
	int a;
};

std::vector<int> data = {1,6,3,4,2};
std::vector<Item> result(data.size());
std::transform(data.begin(), data.end(), result.begin(), [](const int& i) -> Item {
	return Item({i});
});

集合过滤

const data = [1,2,3,4,5]
const result = data.filter((i) => i % 2 == 0)

JavaScript 里的 Array.prototype.filter 返回的数据,对 Object 类型的集合元素是引用。C++ 语言对于集合过滤的处理有两个方法:copy_if 和 remove_if。copy_if 对原集合做过滤处理并返回复制的新数据,而 remove_if 则是在原集合基础上原地修改。在做算法题的时候要注意一下。

#include <algorithm>    // std::copy_if, std::remove_if

struct Item {
	int a;
};
std::vector<Item> data = {{1}, {6}, {3}, {4}, {2}};
std::vector<Item> result;

std::copy_if(data.begin(), data.end(), std::back_inserter(result), [](const Item& item) {
	return item.a % 2 == 0;
});
auto pend = std::remove_if(data.begin(), data.end(), [](const Item& item) {
	return item.a % 2 == 0;
});
data.erase(pend, data.end());

优先队列

普通队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。而在优先队列中,元素被赋予了优先级。当访问元素时,最高优先级的元素会被最先删除。

// 小顶堆
priority_queue<int, vector<int>, greater<int>> pq1;

// 大顶堆
priority_queue<int> pq2;
priority_queue<int, vector<int>, less<int>> pq3;

集合连接

const data1 = [1,2,3]
const data2 = [4,5,6]
const result = data1.concat(data2)

和集合过滤一样的,C++ 中对集合连接也要考虑到是复制还是引用操作。

std::vector<int> data1 = {1,2,3};
std::vector<int> data2 = {4,5,6};
data1.insert(data1.end(), data2.begin(), data2.end());

std::vector<int> data3 = {1,2,3};
std::vector<int> data4 = {4,5,6};
std::move(data4.begin(), data4.end(), std::back_inserter(data3));
data4.clear();

Tags

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.