ideallove

ideallove

ホームアーカイブ

（ノート）C++アルゴリズムトリック

#cpp128
AI 翻訳
この記事はAIを通じて中国語から日本語に翻訳されました。原文を表示
AI が生成した要約
C++算法Trick包括万能头文件、取消同步流、getline、string类的c语言风格字符串、常见的遍历string的方法、排序、二分查找、tolower/toupper函数、全排列、memset函数、reverse函数、unique函数。

C++ アルゴリズムトリック

万能ヘッダーファイル#

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    // ここにコードを入力してください
    
    return 0;
}

同期ストリームの解除#

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

getline#

getline(cin, string);

string クラスの C 言語スタイルの文字列#

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

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    char buffer[100];
    scanf("%s", buffer);
    string str(buf);
    printf("str = %s\n", str.c_str());
    
    return 0;
}

str.c_str();

// 文字列の長さを取得
str.length();
// 文字列を結合
string res1 = str1 + "," + str2;
string res2 = str1.append(",").append(str2);
// 文字列検索
str.find();
// 文字列置換
// サブ文字列の開始位置、サブ文字列の長さ、置換後の文字列
str.replace(7, 5, "xxxxx");
// 文字列を抽出する 越境しないように
str.substr(7, 5);
// 文字列比較
str1.compare(str2);

一般的な string の走査方法#

  1. インデックスをループして列挙
for(int i=0;i < s.length(); ++i) cout << s[i];
  1. auto 列挙

ソート sort#

// sort(開始アドレス、終了アドレスの次、 *比較関数)
// 比較関数はデフォルトで昇順
// カスタム比較関数
bool cmp(const int &u, const int &v){
    // int u, int vでも良い
    return u > v;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // vを初期化
    vector<int> v = {5,1,3,9,11};
    // 配列をソート、降順に並べ替え
    sort(v.begin(), v.end(), cmp);
    // 出力
    for(int i=0; i < v.size(); ++i){
        cout << v[i] << ' ';
    }
}
// ラムダ式を使用してカスタム比較関数を定義
sort(v.begin(), v.end(), [](const int &u, const int &v)
{
    return u > v;
});
// 構造体によるカスタム比較関数
struct Node
{
    int u, v;
    bool operator < (const Node &m)const{
        return u == m.u ? v < m.v : u < m.u;
    }
}
// スペースと改行のテクニック
for(int i = 1; i <=n; i++){
    // 正順出力
    cout << a[i] << " \n"[i == n];
}

最小値・最大値の検索#

min(a, b);
min({1,2,3,4})=1;
max(a, b);

min_element(st, ed); // 最小値のアドレスを返す
max_element(st, ed); //
// 例
vector<int> v = {5, 1, 3, 9, 11};
cout << *max_element(v.begin(), v.end()) << '\n';

ntn_element(st, k, ed); // 部分ソート
// kは正しい位置にあり、前はそれより小さく、後ろはそれより大きい
// https://www.lanqiao.cn/problems/497/learning/

二分探索#

単調配列に対してのみ検索できる

// binary_search関数
// ソートされた列（配列またはコンテナvector）内で特定の要素を検索するために使用されます。
vector<int> numbers = {1, 3, 5, 7, 9};
int target = 5;
// binary_searchを使用して目標を検索
bool found = binary_search(numbers.begin(), numbers.end(), target);

lower_bound & upper_bound

// 前提：配列は非降順でなければならない
// lower_bound(st, ed, x)はアドレス[st, ed)内で最初にx以上の要素のアドレスを返します。
// upper_bound(st, ed, x)はアドレス[st, ed)内で最初にxより大きい要素のアドレスを返します。
// 存在しない場合は最後の要素の次の位置を返します。vectorではend()になります。
vector<int> v = {5, 1, 7, 3, 10, 18, 9};
sort(v.begin(), v.end());
for(auto &i : v) cout << i << ' ';
cout << '\n';
// 配列内で最初に8以上の要素の位置を見つける
cout << (lower_bound(v.begin(), v.end(), 8) - v.begin()) << '\n';
// https://www.lanqiao.cn/problems/1389/learning/

大文字小文字の変換#

// islower/isupper関数はchar型が小文字または大文字かどうかをチェックします
#include <cctype>
// tolower/toupper関数
char ch1 = 'A';
char lowercaseCh1 = tolower(ch1);

全順列#

next_permutation () 関数

vector<int> nums = {1, 2, 3};

cout << "初期順列: ";

for(int num : nums){
    cout << num << " ";
}
cout << '\n';

// 次の順列を生成 next_permutationはtrue/falseを返します
while (next_permutation(nums.begin(), nums.end())){
    cout << "次の順列: ";
    for(int num : nums){
        cout << num << " ";
    }
    cout << endl;
}

prev_permutation () 関数

vector<int> nums = {3, 2, 1};

cout << "初期順列: ";

for(int num : nums){
    cout << num << " ";
}
cout << '\n';

// 前の順列を生成 prev_permutationはtrue/falseを返します
while (prev_permutation(nums.begin(), nums.end())){
    cout << "次の順列: ";
    for(int num : nums){
        cout << num << " ";
    }
    cout << endl;
}

探索 / DFS の方法を使用して全順列の方法を使用します

その他のライブラリ関数#

memset(void* ptr, int value, site_t num)#

メモリブロックの値を設定する関数 #include <cstring>

void* memset(void* ptr, int value, site_t num)

ptr は値を設定するメモリブロックのポインタを指します

value は設定する値 通常は整数です

num は設定するバイト数

memset(arr, 0, sizeof(arr)); // 配列arrを初期化

memset () 関数は非文字型配列に対して未定義の動作を引き起こす可能性があります。
非文字型配列を処理する場合は、C++ の他の方法（ループを使用して配列を初期化するなど）を使用する方が良いです。
memset は各バイトを value に設定します。

int main(){
    int a[5];
    memset(a, 0, sizeof(a));
    for(int i = 0; i < 5; i++){
        // cout << bitset<32>(a[i]) << '\n';
        cout << a[i] << '\n';
    }
    return 0;
}

swap(T &a, T &b)#

交換

std::swap(a, b);

reverse(BidirIt first, BidirIt last)#

#include <algorithm>
template(class BidirIt)
void reverse(BidirIt first, BidirIt last);

[first, last)を反転します

reverse(vec.begin(), vec.end());

unique(ForwardIt first, ForwardIt last)#

#include <algorithm>
template(class ForwardIt)
ForwardIt unique(ForwardIt first, ForwardIt last)

int main(){
    vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5};
    auto it = unique(vec.begin(), vec.end()); // 隣接する重複要素を削除
    vec.erase(it, vec.end()); // 重複した要素を削除
    
    for(int num : vec) {
        cout << num << " ";
    }
    cout << '\n';
    
    return 0;
}

STL ライブラリ#

pair 値のペア#

pair(const T1& x, const T2& y);
// 値のペアの組み合わせを表し、2つの値を組み合わせて渡したり、保存したり、操作したりします
pair<int, double> p1(1, 3.14);
pair<char, string> p2('a', "Hello")
cout << p1.first << ", " << p1.second << endl;

pair のネスト：
pair オブジェクトを別の pair オブジェクトのメンバーとして持つ

pair は自動的にソートルールを持ち、first メンバーに従って昇順にソートされます

vector<pair<int, int>> vec;
vec.push_back(make_pair(3, 2));
vec.push_back(make_pair(1, 4));
vec.push_back(make_pair(2, 1));

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

for (const auto& p : vec) {
    cout << p.first << ", " << p.second << endl;
}

vector 動的配列#

動的配列コンテナ 同じ型の要素の系列を保存します

#include <vector>
vertor<T> vec;

// 要素アクセス: 0~size()-1
// 要素の追加と削除: push_back() pop_back() insert() erase()
// コンテナサイズ管理: size() empty() resize()
// イテレータ: begin() end()

vector<int> vec = {10, 20, 30};
for(auto it = vec.begin(); it != vec.end(); ++it){
    cout << *it << " ";
}

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

// ソートして重複を削除
vector<int> vec = {10, 20, 30};
sort(vec.begin(), vec.end());
auto last = unique(vec.begin(), vec.end());
vec.erase(last, vec.end());
for(const auto& num : vec){
    cout << num << " ";
}

list リスト#

あまり使用されない

双方向リンクリスト

list<T>

stack スタック#

後入れ先出しのデータ構造

#include <stack>
stack<T>

// よく使われる関数
push(x) // スタックのトップに要素xを挿入
pop() // スタックのトップの要素を取り出す
top() // スタックのトップの要素を返す
empty() // スタックが空かどうかをチェック
size() // スタック内の要素数を返す
// stackは走査できません

queue キュー#

//queue
//priority_queue優先キュー
//deque両端キュー

//queue FIFO
push(x)
pop()
front()
back()
empty()
size()

https://www.lanqiao.cn/problems/1113/learning/

//priority_queue優先キュー デフォルトで大きい順に並べ替え
1. push()：要素を優先キューに挿入します。挿入後、自動的に優先度に従って再配置されます。
2. pop()：キューのトップの要素を取り出します。これにより、キュー内で最も優先度の高い要素が削除されます。
3. top()：キューのトップ（つまり優先度が最も高い）要素を返しますが、キューからは削除しません。
4. size()：キュー内の要素数を返します。
5. empty()：キューが空であればtrueを返し、そうでなければfalseを返します。

struct Compare{
    bool operator()(int a, int b) {
        return a > b;
    }
}
int main(){
    priority_queue<int, vector<int>, Compare> pq;
}
// または
// priority_queue<int, vector<int>, greater<int>> pq;

//deque両端キュー
push_back(x)
push_front(x)
pop_back()
pop_front()
front()
back()
empty()
size()
clear()

set 集合#

// set集合 デフォルトで昇順にソート
// setは内部で赤黒木を使用して要素を保存します
// setは重複要素を許可しません
insert()
erase()
find()
lower_bound()
upper_bound()
size()
empty()
clear()

// ソート方法を変更 1
set<int, greater<int>> mySet;
// 2
struct MyCompare(){
    bool operator()(const int& a, const int& b) const {
        // カスタム比較ロジック
        return a > b;
    }
}
int main(){
    set<int, myCompare> mySet;
}

// multiset多重集合 重複要素を保存することができます

// unordered_set無秩序集合

map キーと値のペア#

map()
// keyに基づいてソート
insert(K, V)
erase(key)
find(key)
count(key)

// 複数の同じキー
multimap()


// 無秩序
unordered_map()

小結#

https://www.lanqiao.cn/problems/3226/learning/ 宝物のソート2
https://www.lanqiao.cn/problems/1624/learning/ 小ブルーのキャンディ
https://www.lanqiao.cn/problems/2490/learning/ 小ブルーの括弧列1
https://www.lanqiao.cn/problems/1531/learning/ 荷物の仕分け

時間計算量#

列挙#

すべての可能な状況を列挙し、解空間をループします

シミュレーション#

再帰#

進数変換#

プレフィックス和#

差分#

差分の原理と特徴

配列a[]に対する差分配列diff[]の定義は：

diff[i] = a[i] - a[i-1]

差分配列に対してプレフィックス和を行うことで元の配列に戻すことができます：

diff[1] = a[1]
diff[2] = a[2] - a[1]
diff[3] = a[3] - a[2]
...
diff[n] = a[n] - a[n-1]

差分の実装

O (n) のループを一度実行するだけで済みます。a[0]=0を推奨し、インデックスは 1 から始めます。

読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。