Mảng (Array)
Mảng là cấu trúc dữ liệu lưu trữ các phần tử cùng kiểu liên tiếp trong bộ nhớ. Truy cập phần tử theo chỉ số (index) với độ phức tạp .
Khai báo và sử dụng trong C++
// Mảng tĩnh
int a[100005];
// Mảng động (vector)
vector<int> v = {1, 2, 3, 4, 5};
v.push_back(6); // thêm vào cuối: O(1) amortized
v.pop_back(); // xóa cuối: O(1)
v.size(); // kích thước
v[i]; // truy cập phần tử: O(1)
// Mảng 2 chiều
vector<vector<int>> mat(n, vector<int>(m, 0));
Sử dụng trong Python
a = [1, 2, 3, 4, 5]
a.append(6) # thêm cuối: O(1)
a.pop() # xóa cuối: O(1)
a[i] # truy cập: O(1)
len(a) # kích thước
# List 2 chiều
mat = [[0] * m for _ in range(n)]
Các thao tác thường dùng
| Thao tác | C++ | Python | Độ phức tạp |
|---|---|---|---|
Truy cập a[i] |
a[i] |
a[i] |
|
| Thêm cuối | push_back |
append |
|
| Xóa cuối | pop_back |
pop() |
|
| Chèn giữa | insert |
insert |
|
| Xóa giữa | erase |
del / pop(i) |
|
| Tìm kiếm | find |
in |
|
| Sắp xếp | sort |
sort |
Kỹ thuật Prefix Sum
Dùng để tính tổng đoạn trong sau tiền xử lý.
vector<long long> pre(n+1, 0);
for (int i = 0; i < n; i++)
pre[i+1] = pre[i] + a[i];
// Tổng đoạn [l, r] (0-indexed)
long long sum = pre[r+1] - pre[l];
pre = [0] * (n + 1)
for i in range(n):
pre[i+1] = pre[i] + a[i]
total = pre[r+1] - pre[l]
Xâu ký tự (String)
C++
string s = "hello";
s.length(); // độ dài
s[i]; // ký tự thứ i
s.substr(l, len); // chuỗi con từ vị trí l, độ dài len
s.find("ell"); // tìm chuỗi con
s += " world"; // nối chuỗi
for (char c : s) { ... }
Python
s = "hello"
len(s) # độ dài
s[i] # ký tự thứ i
s[l:r] # chuỗi con [l, r)
s.find("ell") # tìm chuỗi con
s + " world" # nối chuỗi
s.split() # tách theo khoảng trắng
",".join(lst) # nối list thành chuỗi
Lưu ý quan trọng
- Trong C++, nối chuỗi trong vòng lặp lần mất — hãy dùng
stringstream. - Trong Python,
strlà immutable — nối trong vòng lặp cũng — dùng"".join(list).
Bình luận