I. Mảng (Array)

Mảng tĩnh có kích thước cố định

Đây là cấu trúc dữ liệu được sử dụng phổ biến nhất trong các cuộc thi lập trình. Bất cứ khi nào có một tập hợp các dữ liệu tuần tự đồng nhất cần được lưu trữ và sau đó truy cập thông qua các chỉ số của chúng, thì mảng tĩnh là cấu trúc dữ liệu tự nhiên nhất để sử dụng. Vì kích thước đầu vào tối đa thường được nêu trong câu hỏi, kích thước của mảng có thể được khai báo bằng kích thước đầu vào tối đa, với một vùng đệm nhỏ (sentinel) để đảm bảo an toàn - nhằm tránh lỗi "out of bounds" không cần thiết. Thông thường, các mảng 1D và 2D được sử dụng trong các cuộc thi lập trình (mảng 3D hoặc nhiều chiều hơn thì hiếm gặp). Các thao tác điển hình trên mảng 1D sẽ được trình bày sau, bao gồm truy cập các phần tử theo chỉ số, sắp xếp các phần tử, thực hiện quét tuyến tính trên mảng, hoặc thực hiện tìm kiếm nhị phân trên một mảng đã được sắp xếp. Một số thao tác 2D mảng thú vị bao gồm xoay, chuyển vị hoặc phản chiếu mảng 2D.

Mảng động (có thể thay đổi kích thước)

Mọi người thường được biết loại kiểu dữ liệu này trong C++ là vector Cấu trúc dữ liệu này tương tự như mảng tĩnh, ngoại trừ việc nó được thiết kế để xử lý việc thay đổi kích thước trong thời gian chạy. Tốt hơn là sử dụng vector thay vì mảng nếu kích thước của chuỗi các mục không rõ ràng tại thời điểm biên dịch. Thông thường, chúng ta khởi tạo kích thước (bằng cách sử dụng hàm khởi tạo, reserve() hoặc resize()) với kích thước ước tính (hoặc tối đa) của phần tử để có hiệu suất tốt hơn. Các thao tác vector STL C++ điển hình được sử dụng trong lập trình thi đấu bao gồm push_back(), at(), toán tử [], assign(), clear(), erase() và các bộ lặp để duyệt qua nội dung của vector. Bạn cũng có thể trực tiếp so sánh từ điển các giá trị trong hai vector bằng cách sử dụng các toán tử ==, !=, <, <=, >, và >= nếu kiểu dữ liệu cơ bản có hàm so sánh tích hợp (ví dụ: int, double, string, v.v.).

Sắp xếp và tìm kiếm

Đúng vậy, sắp xếp và tìm kiếm là hai trong số những thao tác phổ biến nhất được thực hiện trên mảng trong các cuộc thi lập trình. Hãy cùng tìm hiểu chi tiết về chúng:

Sắp xếp:

• Sắp xếp là quá trình sắp xếp các phần tử của một mảng theo một thứ tự cụ thể (tăng dần, giảm dần, v.v.).
• Trong C++, hàm std::sort() được xây dựng sẵn từ thư viện <algorithm> có thể được sử dụng để sắp xếp một mảng hoặc vector.

#include <bits/stdc++.h>
using namespace std; int main()
{ int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int n = sizeof(arr) / sizeof(arr[0]); sort(arr, arr + n); for (int i = 0; i < n; ++i) cout << arr[i] << " "; return 0;
}

#include <bits/stdc++.h> using namespace std; int main() { vector<int> v{ 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; sort(v.begin(), v.end()); for (auto x : v) cout << x << " "; return 0; } 

Tìm kiếm:

• Tìm kiếm là quá trình tìm một phần tử cụ thể trong một mảng hoặc xác định xem một phần tử có tồn tại hay không.
• Đối với các mảng chưa được sắp xếp, tìm kiếm tuyến tính thường được sử dụng, có độ phức tạp thời gian là O(n).
• Đối với các mảng được sắp xếp, thuật toán tìm kiếm nhị phân có thể được sử dụng, có độ phức tạp thời gian là O(log n). Trong C++, hàm std::binary_search() từ thư viện <algorithm> có thể được sử dụng để thực hiện tìm kiếm nhị phân trên một mảng hoặc vector đã được sắp xếp hoặc bạn có thể tự viết hàm binary search của riêng mình.

// C++ code to demonstrate the working of binary_search() #include <bits/stdc++.h>
using namespace std; int main()
{ // initializing vector of integers vector<int> arr = { 10, 15, 20, 25, 30, 35 }; // using binary_search to check if 15 exists if (binary_search(arr.begin(), arr.end(), 15)) cout << "15 exists in vector"; else cout << "15 does not exist"; cout << endl; // using binary_search to check if 23 exists if (binary_search(arr.begin(), arr.end(), 23)) cout << "23 exists in vector"; else cout << "23 does not exist"; cout << endl;
} 

Nắm vững các thao tác mảng cơ bản này là rất quan trọng để giải quyết hiệu quả nhiều vấn đề trong các cuộc thi lập trình.

Mảng giá trị boolean

C++ STL bitset Nếu mảng của chúng ta chỉ cần chứa các giá trị Boolean (1/true và 0/false), chúng ta có thể sử dụng một cấu trúc dữ liệu thay thế khác thay vì một mảng thông thường - một bitset trong C++ STL. Bitset trong C++ STL này hỗ trợ các thao tác hữu ích như reset(), set(), toán tử [] và test(). Tuy nhiên, nếu mảng các giá trị Boolean của chúng ta nhỏ (không quá 62 giá trị Boolean), thì việc sử dụng cấu trúc dữ liệu bitmask được thảo luận ở post sau sẽ có lợi hơn. Dưới đây là 1 vài cách sử dụng bitset

// C++ program to demonstrate the bitset 
#include <bitset>
#include <iostream> using namespace std; int main()
{ // declaring an uninitialized bitset object bitset<8> uninitializedBitset; // initialization with decimal number bitset<8> decimalBitset(15); // initialization with binary string bitset<8> stringBitset(string("1111")); cout << "Uninitialized bitset: " << uninitializedBitset << endl; cout << "Initialized with decimal: " << decimalBitset << endl; cout << "Initialized with string: " << stringBitset << endl; return 0;
}

// C++ program to demonstrate the
// use of std::bitset member
// functions
#include <bitset>
#include <iostream> using namespace std; int main()
{ // declaring index variable int index = 0; // declaring few bitset objects bitset<4> allSet("1111"), allUnset; cout << "any() value: " << boolalpha << allSet.any() << endl; cout << "all() value: " << allSet.all() << endl; cout << "none() value: " << allSet.none() << endl; cout << "test() at index 0: " << noboolalpha << allSet.test(index) << endl; cout << "size() value: " << allSet.size() << endl; cout << "Value of allUnset on before using set(): " << allUnset << endl; allUnset.set(index); cout << "Value of allUnset on after using set(): " << allUnset << endl; cout << "Value of allSet on before using reset(): " << allSet << endl; allSet.reset(index); cout << "Value of allSet on after using reset(): " << allSet << endl; // declaring an empty string string bitString; // using to_string() method to assign value to empty // string bitString = allSet.to_string(); cout << "bitString: " << bitString << endl; cout << "Unsigned Long value: " << allSet.to_ulong(); return 0;
}

// C++ program to show the different operator functions on
// bitset
#include <bitset>
#include <iostream> using namespace std; int main()
{ bitset<4> bitset1("1001"), bitset2("1010"); bitset<4> result; cout << "Bitset1: " << bitset1 << "\nBitset2: " << bitset2 << endl; cout << "Accessing bit value at index 1 of bitset1: " << bitset1[1] << endl; // bitwise AND cout << "Bitwise AND using &: " << (result = bitset1 & bitset2) << endl; cout << "Bitwise AND using &=: " << (bitset1 &= bitset2) << endl; // bitwise OR bitset1 = 9; // 9 = 1001 cout << "Bitwise OR using |: " << (result = bitset1 | bitset2) << endl; cout << "Bitwise OR using |=: " << (bitset1 |= bitset2) << endl; // bitwise NOT cout << "Bitwise NOT: " << (result = ~bitset1) << endl; // bitwise XOR bitset1 = 9; cout << "Bitwise XOR: " << (bitset1 ^= bitset2) << endl; bitset1 = 9; cout << "Binary leftshift on bitwise1: " << (bitset1 <<= 1) << endl; bitset1 = 9; cout << "Binary rightshift on bitwise1: " << (bitset1 >>= 1) << endl; return 0;
}