useful code

C++ (mainly for Online Judge)

About STL

来源于Acwing中，要求输出六位浮点数，需要使用iomanip库

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

int main() {
   double n = 10;
   cout << fixed << setprecision(6) << n << endl; // fixed setprecision(x) 固定模板
}

Type Casting

long to int

1 2	`long currentUgly = 1; return (int)currentUgly;`

int/float to string

std::to_string 是 C++11 引入的函数，可以将整数或浮点数转换为字符串。
1
string index_s = to_string(index);

string to integer

支持处理带符号的整数（如正数和负数）
如果字符串不是有效数字格式，则会抛出异常

1	`int stoi(const string& str, size_t* idx = 0, int base = 10);`

str：待转换的字符串
idx（可选）：表示转换停止的字符索引（用来标记多余字符起始位置）
base（可选）：表示字符串的进制（默认为10，支持2、8、16等）

string s1 = "123";
string s2 = "-456";
string s3 = "789abc";

// 基本使用
cout << stoi(s1) << endl;  // 输出 123
cout << stoi(s2) << endl;  // 输出 -456

// 使用 idx 参数
size_t idx;
int num = stoi(s3, &idx);
cout << num << endl;       // 输出 789
cout << "剩余字符串: " << s3.substr(idx) << endl;  // 输出 "abc"

Digit Separation

// 来自快乐数
int square_sum(int n) {
    int sum = 0;
    while (n != 0 ) {
        int digit = n % 10;
        n /= 10;
        sum += digit * digit;
    }
    return sum;
}

Create LinkedList

#include <iostream>
using namesapce std;
int main () {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    ListNode* head = nullptr;
    ListNode pnode = nullptr;
    cout << "Enter the elements: ";
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        if (i == 0) {
            head = new ListNode(val);
            pnode = head;
        } else {
            ListNode* newNode = new ListNode(val);
            pnode->next = newNode;
            pnode = newNode;
        }
    }
}

BinarySearch

需要理解题目适当变形！

Leetcode第69题:x的平方根

int binarySearch(const vector<int>& nums, int target) {
   int left = 0;
   int right = nums.size() - 1;
 
   while (left <= right) {
   int mid = left + (right - left) / 2; // 防止溢出
 
   if (nums[mid] == target) {
      return mid;
   } else if (nums[mid] < target) {
      left = mid + 1;
   } else {
      right = mid - 1;
            }
   }
 
   return -1;
}

Acwing790.数的三次方根

double cube_root(double n) {
   double left = -1000,right = 1000;
   double eps = 1e-7; // 10的-6次方精度
   
   while (right - left  > eps) {
      double mid = (left + right) / 2;
      if (mid * mid * mid < n) left = mid;
      else right = mid;
   }
   return left; // 返回一个边界
}

About vector

basic operations

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

int main() {
vector<int> v;
v.push_back(1);
v.pop_back(); // 删除最后一个元素
vector<vector<int>> dp(m,vector<int>(n,0)); // 建立一个固定大小的二维数组
v.insert(v.begin(), 3); // 在第一个元素前面插入一个元素
v.erase(v.begin() + 1); // 删除第二个元素
sort(v.begin(), v.end()); // 对数组进行原地排序
}

dynamic array vs static array

在做题的时候一不小心把vector<string> s(3)打成了vector<string> s[3]，因为本人没有细学过C++，因此在这里记录一下~

vector<string> s; // 这是一个动态大小的向量，能够在运行时添加任意数量的 string 元素
vector<string> s[3]; // 这是一个静态数组，包含 3 个 vector<string> 对象。
vector<string> s(3); // 向量 s 会有 3 个元素，且这些元素都是空字符串。
vector<int> v(3); // 向量 v 会有 3 个元素，且这些元素都是 0。

回过头来意识到我这个问题好幼稚，犯的错好傻呀...🫥🫥

reverse array

包含在algorithm头文件中，可以通过reverse(begin, end)函数实现数组的翻转。注意，begin()和end()函数返回的迭代器是左闭右开的，也就是说，begin()指向第一个元素，而end()指向最后一个元素的下一个位置。

#include <vector>
#include <algorithm>

vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end()); // 翻转数组
reverse(v.begin(), v.begin() + 4); // 翻转转从第 0 个元素开始到第 3 个元素

accumulate vector

accumulate是C++标准库中的一个函数，用于计算范围内所有元素的累计和。它通常用于容器（如vector、array等）中的元素累计。accumulate函数位于<numeric>头文件中。

1 2	`template <class InputIterator, class T> T accumulate(InputIterator first, InputIterator last, T init);`

first：输入序列的起始迭代器（指向序列的第一个元素）。
last：输入序列的结束迭代器（指向序列的最后一个元素的后一个位置）。
init：累加的初始值，这个值会作为累加计算的起点。累加后的结果将基于这个初始值。

#include <vector>
#include <numeric>  // accumulate 所在的头文件
using namespace std;
// 使用 accumulate 计算 nums 中所有元素的和，初始值为 0
int total = accumulate(nums.begin(), nums.end(), 0);

lower_bound()

在一个有序数组（或容器）中找到第一个大于等于指定值的元素的位置

1	`auto it = lower_bound(sub.begin(), sub.end(), x);`

如果it == sub.end()，表示x比sub中的所有元素都大（即x可以直接追加到数组末尾）。

max_element()/min_element()

用于找到在指定范围内最大、最小值的函数，它是<algorithm>头文件中的一个函数模板。参数：

first：容器或范围的起始迭代器
last：容器或范围的结束迭代器（不包括最后一个元素）
（可选）comp：一个二元谓词，用于指定比较规则

template< class ForwardIterator >
ForwardIterator max_element( ForwardIterator first, ForwardIterator last );

template< class ForwardIterator, class Compare >
ForwardIterator max_element( ForwardIterator first, ForwardIterator last, Compare comp );

注意，返回值是一个指向最大元素的迭代器，在取出具体值的时候，要使用*取出：

1
2
3

vector<int> vec = {3, 1, 4, 1, 5};
auto max_it = max_element(vec.begin(), vec.end());
cout << "最大值是：" << *max_it << endl;

next_permutation()

也是一个cpp的STL函数，返回该序列的下一个字典序，如果该字典序已经是最后一个了，那么返回第一个字典序。使用该函数，hot100_31.下一个排列这一题秒解

示例用法：

vector<int> nums = {1,1,5};
next_permutation(nums.begin(),nums.end());// 之后nums变为{1,5,1}
// 当然也可以自定义比较函数
next_permutation(nums.begin(),nums.end(),cmp);

About Binary Tree

中序遍历

递归实现

void inorder(TreeNode* root,vector<int>& res) {
    if (root == nullptr)  return 0;
    inorder(root->left);
    res.push_back(root->val);
    inorder(root->right);
    }

int inorderTraversal(TreeNode* root) {
    vector<int> res;
    inorder(root, res);
    return res;
}

迭代实现

 vector<int> inorderTraversal(TreeNode* root) {
 vector<int> res;
 stack<TreeNode*> stk;
 while (root != nullptr || !stk.empty()) {
     while (root != nullptr) {
     stk.push(root);
     root = root->left;
    }
     root = stk.top();
     stk.pop();
     res.push_back(root->val);
     root = root->right;
  }
return res;
}

Calculate the depth of the binary tree

int maxDepth(TreeNode* root) {
   if (root == nullptr) return 0;
   return max(maxDepth(root->left), maxDepth(root->right)) + 1; 
}

About Heap

maxHeap & minHeap

cpp中已经实现了最大堆和最小堆，没有必要自己手动实现，包含在<queue>中。

默认情况下，C++ 的 priority_queue 是一个最大堆。
想要使用最小堆，需要使用 priority_queue 并传递 std::greater 比较器。

// 默认最大堆
priority_queue<int> maxHeap;
// 最小堆
priority_queue<int,vector<int>,greater<int>> minHeap;
// 基本操作：push pop top size和栈一样

Custom heap sorting

举个例子：

// 使用最小堆 按照频率从低到高排序 这里是一个lambda表达式
// 如果定义为 frequencyMap[a] > frequencyMap[b]，堆会按照频率从小到大排序，变成了最小堆。
// 如果定义为 frequencyMap[a] < frequencyMap[b]，堆会按照频率从大到小排序，保持为最大堆。
unordered_map<int,int> frequencyMap;
auto cmp = [&frequencyMap](int a,int b) {
        return frequencyMap[a] > frequencyMap[b];
    };
// decltype(cmp)：用于指定比较器的类型，这里通过 decltype(cmp) 获取 cmp 的类型。
// cmp：将定义好的 lambda 表达式 cmp 作为堆的比较器传递。
priority_queue<int,vector<int>,decltype(cmp)> minHeap(cmp);

About Hash Table & Hash Set

Traverse the hash table

HashMap

for (auto it = mp.begin(); it != mp.end(); ++it) {
   it->first; // key
   it->second; // value
   // other code
   }
for (auto& [key, value] : mp) {
   // other code
   }

HashSet

for (auto it = st.begin(); it != st.end(); ++it) {
   *it; // value
}
for (auto& value : st) {
   value;
}

About char

isDigit()

用于检查一个字符是否是数字字符（0-9）
返回值为布尔值：true 表示该字符是数字，false 表示不是数字

char c1 = '5';
char c2 = 'a';
cout << isdigit(c1) << endl;  // 输出 1，因为 '5' 是数字
cout << isdigit(c2) << endl;  // 输出 0，因为 'a' 不是数字

About string

substring

1
2
3

string s = "Hello World";
string sub = s.substr(6, 5); // 从索引6开始，长度为5的子串
sub == "World"; // 判断字符串是否相等

Append string

1
2
3

string s1 = "Hello";
int num = 3;
s1.append(num, 'a'); // 将字母a重复3次，并追加到s1后面

Reverse string

1 2	`string s = "123456"; reverse(s.begin().s.end()); // 反转字符串顺序`

Spilt string

string s = "/home/foo/"
for (char ch : s) {
   if (ch == "/") {
      // some work
   } else {
      // some work
   }
}

clear string

1 2	`string s = "122344"; s.clear(); // 置空字符串`

About matrix

Matrix transpose

vector<vector<int>> matrix = {{1,2,3},{4,5,6},{7,8,9}};
int n = matrix.size();
for (int i = 0;i < n;i++) {
   for (int j = i + 1; j < n;j++) {
      swap(matrix[i][j],matrix[j][i]);
      }
}

matrix flipped horizontally

#include <algorithm>
   int n = matrix.size();
   for (int i = 0; i < matrix.size();i++) {
      reverse(matrix[i].begin(),matrix[i].end());
   }

DFS template

Tree's DFS

void DFSTree(TreeNode* root) {
   if (root == nullptr) return;
   // 处理当前节点
   cout << root->val << " ";
   // 递归遍历左子树
   DFSTree(root->left);
   // 递归遍历右子树
   DFSTree(root->right);
   
   // 回溯
   // pop_back();
}

Sort Methods

Custom Sorting

来源于Leetcode 179.largestNumber，这个题目中只要自定义排序几行代码就完事！

1
2
3

sort(nums.begin(),nums.end(),[](int x,int y){
         return to_string(x) + to_string(y) > to_string(y) + to_string(x);
     });

第三个参数是自定义的比较函数，用于定义排序的规则
这里使用匿名lambda表达式

MergeSort

2024/12/27，虽然需要临时数组，不过最好还是对数组进行原地修改，在这里更新一个版本

void mergeSort(vector<int>& arr,int left,int right) {
    int mid = left + (right - left) / 2;
    int i = left,j = mid + 1;
    
    vector<int> temp;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i]);
            i++;
        }
        else {
            temp.push_back(arr[j]);
            j++;
        }
    }

    for (int k = i; k <= mid;k++) temp.push_back(arr[k]);
    for (int k = j; k <= right;k++) temp.push_back(arr[k]);

    for (int k = 0; k < temp.size();k++)
        arr[left + k] = temp[k];
}

void sortArray(vector<int>& arr,int left,int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    sortArray(arr,left,mid);
    sortArray(arr,mid + 1,right);

    mergeSort(arr,left,right);
}

QuickSort

2024/12/24，原来常用的QuickSort模板在Acwing中时间超限，更新一个新的模板

void quickSort(vector<int>& nums,int left,int right) {
   if (left >= right) return;
   int i = left - 1,j = right + 1;
   int mid = nums[(left + right) / 2]; // 取最中间的数
   while(i < j) {
      do(i++); while (nums[i] < mid); // 注意do while 循环要加`;`
      do(j--); while (nums[j] > mid);
      if (i < j) swap(nums[i],nums[j]);
   }
   quickSort(nums,left,j);
   quickSort(nums,j + 1,right);
}

#cpp

useful code

https://august6676.github.io/2024/08/22/code/

作者

Xiaoxuan Zhou

发布于

2024年8月22日

许可协议

Basic Knowledge for Domain Generalization 上一篇

本地主机连接远程服务器的几种方式下一篇