常用算法

// 判断素数
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

// 判断闰年
bool isLeapYear(int x) {
    if (x % 400 == 0 || (x % 4 == 0 && x % 100 != 0)) return true;
    return false;
}

// 求最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 求最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

// 求阶乘
int factorial(int x) {
    int res = 1;
    for (int i = 2; i <= x; i++) {
        res *= i;
    }
    return res;
}

// 求组合数
int combination(int n, int m) {
    return factorial(n) / factorial(m) / factorial(n - m);
}

// 分解质因数
vector<int> primeFactor(int x) {
    vector<int> res;
    for (int i = 2; i * i <= x; i++) {
        while (x % i == 0) {
            res.push_back(i);
            x /= i;
        }
    }
    if (x > 1) res.push_back(x);
    return res;
}

// 求欧拉函数
int euler(int x) {
    int res = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

// 求逆元
int inverse(int a, int p) {
    return a == 1 ? 1 : (long long)(p - p / a) * inverse(p % a, p) % p;
}

约瑟夫环

// 约瑟夫环问题
void josephus_problem() {

    int n, m;
    cin >> n >> m;
    vector<int> vec1(n);    // vector
    for (int i = 0; i < n; i++) {
        vec1[i] = i + 1;
    }
    int index = 0;  // 记录当前位置
    while (vec1.size() > 1) {
        index = (index + m - 1) % vec1.size();  // 计算下一个位置
        vec1.erase(vec1.begin() + index);   // 删除当前位置的元素
    }
    cout << vec1[0] << endl;

}

bool 转换 true 或 false

cout << boolalpha << containsDuplicate(nums) << endl;
cout << (containsDuplicate(nums) ? "true" : "false") << endl;

向量读入

while (cin >> num) {
    nums.push_back(num);
    if (cin.get() == '\n') break;
}

读取并创建二叉树

// 读取 3 9 20 null null 15 7
    int val;
    string s;
    cin >> val;
    TreeNode *root = new TreeNode(val);
    queue<TreeNode*> q;
    q.push(root);
    while (cin >> s) {
        if (s == "null") {
            q.front()->left = nullptr;
        } else {
            val = stoi(s);
            TreeNode *node = new TreeNode(val);
            q.front()->left = node;
            q.push(node);
        }
        cin >> s;
        if (s == "null") {
            q.front()->right = nullptr;
        } else {
            val = stoi(s);
            TreeNode *node = new TreeNode(val);
            q.front()->right = node;
            q.push(node);
        }
        q.pop();
        if (cin.get() == '\n') break;
    }

判断素数

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

创建和输出 二叉树

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
    TreeNode(int _val, TreeNode *_left, TreeNode *_right) : val(_val), left(_left), right(_right) {}
};

// 创建二叉树，返回根结点指针
TreeNode *createTree(vector<int>& nums) {
    TreeNode *root = new TreeNode(nums[0]);  // 创建二叉树的根节点
    
    queue<TreeNode*> q;  // 创建队列，用于按照层序顺序建立二叉树
    q.push(root);
    
    int i = 1;  // 迭代器，用于遍历 vector 中的每一个元素
    while (!q.empty() && i < nums.size()) {  // 只要队列不为空且 vector 中还有元素就继续遍历
        TreeNode* node = q.front();
        q.pop();
        if (i < nums.size()) {  // 预防越界
            if (nums[i] != -1) {  // 如果 vector 中的元素不是 -1，说明需要构建左子树
                node->left = new TreeNode(nums[i]);
                q.push(node->left);
            }
            i++;
            
            if (i < nums.size()) {  // 预防越界
                if (nums[i] != -1) {  // 如果 vector 中的元素不是 -1，说明需要构建右子树
                    node->right = new TreeNode(nums[i]);
                    q.push(node->right);
                }
                i++;
            }
        }
    }
    
    return root;
}

int main() {
    vector<int> nums = {1, 2, 3, -1, -1, 4, 5};  // 待转化为二叉树的 vector，其中 -1 表示该节点为空节点
    TreeNode* root = createTree(nums);  // 创建二叉树并获取根结点指针
    // 层序遍历并输出
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
    }
    cout << endl;
    return 0;
}

创建和输出 链表

#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 创建链表，返回链表的头结点指针
ListNode* createList(vector<int>& nums) {
    ListNode* head = nullptr;  // 头结点指针初始化为空
    ListNode* tail = nullptr;  // 尾结点指针初始化为空
    for (int i = 0; i < int(nums.size()); i++) {  // 遍历 vector，逐个创建结点插入链表中
        ListNode* node = new ListNode(nums[i]);
        if (head == nullptr) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    return head;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};  // 定义向量
    ListNode* head = createList(nums);  // 创建链表并获取头结点指针
    // 遍历链表并输出每个结点的值
    ListNode* p = head;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
    return 0;
}

stringstream 用法

#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
int n;
int a[N];

int main() {
	int cnt;
	cin >> cnt;
    
	string line;
	getline(cin, line);
    
	while (cnt -- ) {
		getline(cin, line);
		stringstream ssin(line);
		while (ssin >> a[n]) n ++ ;
	}

	sort(a, a + n);

	int res1, res2;
	for (int i = 1; i < n; i ++ )
		if (a[i] == a[i - 1]) res2 = a[i];
		else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1;

	cout << res1 << ' ' << res2 << endl;

	return 0;
}

二分查找

int binarySearch(vector<int>& nums, int target) {
	if (nums.size() == 0)
		return -1;

	int left = 0, right = nums.size() - 1;
	while (left <= right) {
		int mid = left + ((right - left) >> 1);
		if (nums[mid] == target) {
			return mid;
		}
		// 搜索区间变为 [mid+1, right]
		else if (nums[mid] < target)
			left = mid + 1;
		// 搜索区间变为 [left, mid - 1]
		else
			right = mid - 1;
	}
	return -1;
}

二维矩阵输出

int main() {
    int num;
    cin >> num;
    vector<vector<int>> res = generateMatrix(num);
    for (int i = 0, n = res.size(); i < n; i++) {
        for (int j = 0, m = res[i].size(); j < m; j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

vector 标准输入输出

// 解法一 : 暴力枚举

# include <bits/stdc++.h>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0, n = nums.size(); i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) return {i, j};
        }
    }
    return {};
}

int main() {
    vector<int> nums;
    int num, target;
    while (cin >> num) {        // 读入数据
        nums.push_back(num);
        char ch = getchar();
        if (ch == '\n') break;        
    }
    cin >> target;              // 读入目标值
    vector<int> res = twoSum(nums, target);
    for (int i = 0, n = res.size(); i < n; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}