[学習アルゴリズム]実戦アルゴリズム3講-配列

4317 ワード
名学習 テキストリンク
私がバーク金督がアップロードした「実戦アルゴリズム」のビデオを見て勉強した過程を記録します.
すべての写真は巴金督のブログから持ってきたものです.
https://blog.encrypted.gg/

アレイの性質

  • アレイのk番目の要素は、O(1)において
    • を決定/変更することができる.
  • 追加消費メモリ量=(ほとんどオーバーヘッドなし)
  • キャッシュヒット率が高い
  • メモリの連続セグメントが割り当てを制限しています

    機能と実装


    任意の位置をチェックして変更する要素はO(1)です.
    端点に要素を追加または削除する最後の要素はO(1)です.
    任意の場所に要素をO(n)として追加します.任意の位置の後ろの要素は1つの格子を移動するのでO(n)である.
    任意の場所の要素を削除してもO(n)

    任意の要素のinsert関数を追加し、任意の位置要素を削除するerase関数

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

void insert(int idx, int num, int arr[], int& len)
{
	for (int i = len ; i > idx; --i)
		arr[i] = arr[i - 1];
	arr[idx] = num;
	len++;
}

void erase(int idx, int arr[], int& len)
{
	for (int i = idx; i < len; ++i)
		arr[i] = arr[i + 1];
	len--;
}

void printArr(int arr[], int& len)
{
	for (int i = 0; i < len; i++) cout << arr[i] << ' ';
	cout << "\n\n";
}

void insert_test()
{
	cout << "***** insert_test *****\n";
	int arr[10] = { 10, 20, 30 };
	int len = 3;
	insert(3, 40, arr, len); // 10 20 30 40
	printArr(arr, len);
	insert(1, 50, arr, len); // 10 50 20 30 40
	printArr(arr, len);
	insert(0, 15, arr, len); // 15 10 50 20 30 40
	printArr(arr, len);
}

void erase_test()
{
	cout << "***** erase_test *****\n";
	int arr[10] = { 10, 50, 40, 30, 70, 20 };
	int len = 6;
	erase(4, arr, len); // 10 50 40 30 20
	printArr(arr, len);
	erase(1, arr, len); // 10 40 30 20
	printArr(arr, len);
	erase(3, arr, len); // 10 40 30
	printArr(arr, len);
}

int main(void)
{
	insert_test();
	erase_test();
}
    パラメータが参照として送信されると、元の値が変更されます.
    fill関数を使用してスキーマ全体を初期化することを推奨します

    STL vector


    vectorは配列と同じ機能を実行するデータ構造であり,配列と同様に要素がメモリに連続的に格納されるため,O(1)の各要素にアクセスできる.vectorは配列とは異なる利点があり,自由にサイズを変更できる.
    #include <bits/stdc++.h>
using namespace std;

int main(void) {
  vector<int> v1(3, 5); // {5,5,5};
  cout << v1.size() << '\n'; // 3
  v1.push_back(7); // {5,5,5,7};

  vector<int> v2(2); // {0,0};
  v2.insert(v2.begin()+1, 3); // {0,3,0};

  vector<int> v3 = {1,2,3,4}; // {1,2,3,4}
  v3.erase(v3.begin()+2); // {1,2,4};

  vector<int> v4; // {}
  v4 = v3; // {1,2,4}
  cout << v4[0] << v4[1] << v4[2] << '\n';
  v4.pop_back(); // {1,2}
  v4.clear(); // {}
}
    vectorのinsert,eraseはO(n),push back,pop backは末尾に元素を添加または減算するのでO(1)である.
    for( auto e : v) // range-based for loop
	cout << e << ' ';
    
for(auto &e : v) // range-based for loop
	cout << e << ' ';
    rangeベースのfor loop方式を使用する場合、参照を使用すると元のv値が変更されます.
    これ以降はvectorだけでなくlist,map,setなどにも用いられる.

    練習問題



    コード#コード#

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

int num[101];

int func2(int arr[], int N)
{
	fill(num, num + 101, 0);
	for (int i = 0; i < N; ++i)
		num[arr[i]]++;

	for (int i = 1; i <= 50; ++i)
		if (num[50 - i] == num[50 + i] && num[50 - i] == 1)
			return 1;
	return 0;
    
    // 바킹독님의 코드
    /*for (int i = 0; i < N; ++i)
	{
		if (num[100 - arr[i]] == 1)
			return 1;
		num[arr[i]]++;
	}
	return 0;*/
}

int main(void) {
	int arr1[] = { 1,52,48 };
	int arr2[] = { 50,42 };
	int arr3[] = { 4,13,63,87 };
	printf("%d", func2(arr1, 3));
	printf("\n");
	printf("%d", func2(arr2, 2));
	printf("\n");
	printf("%d", func2(arr3, 4));
}
    • 非同期
    Lv 1. 失敗率