Vector
- Độ khó
- ★☆☆☆☆ Dễ
- Thời lượng
- Khoảng 90 phút
- Học trước
- Mảng 1 chiều
- Chủ đề
- STLvector
- Trạng thái
Kiến thức cơ bản
Vector tương tự như mảng nhưng nó tự thay đổi kích thước khi bạn thêm hay xóa các phần tử trong mảng và hỗ trợ nhiều hàm có sẵn.
Để sử dụng thự viện vector, ta thêm vào đầu chương trình:
#include <vector> // Khai báo thư viện chứa vector
Khai báo vector
vector<int> v; // khai báo vector v rỗng (size = 0)
vector<int> v(n); // vector có sẵn n phần tử, giá trị mặc định là 0
vector<int> v(n, 100); // vector có n phần tử, giá trị mặc định là 100
vector<int> v = {2, 4, 6}; // vector chứa sẵn 3 số 2, 4, 6
Duyệt vector
Dùng vòng lặp For truyền thống (Index-based), từ 0 đến < v.size().
for (int i = 0; i < (int)v.size(); ++i) {
// Các câu lệnh với phần tử v[i]
}
Dùng Range-based For Loop:
// in ra các phần tử của vector v
for (int i : v) {
cout <<i <<" ";
}
Một số hàm của cơ bản của vector
v.push_back(x); // Thêm một phần tử có giá trị x vào cuối vector
v.pop_back(); // Xóa bỏ phần tử ở cuối vector
v.size(); // Trả về số lượng phần tử hiện đang có trong vector
v.empty(); // Trả về true nếu vector rỗng, ngược lại trả về false
v.back(); // Trả về tham chiếu đến phần tử cuối cùng trong vector
v.front(); // Trả về tham chiếu đến phần tử đầu tiên trong vector
v.clear(); // Xóa tất cả các phần tử trong vector (kích thước trở về 0)
Luyện tập
Bài 1. Chiếc ba lô của Doraemon
Doraemon có một chiếc ba lô ma thuật. Nobita nhặt được các món bảo bối trên đường (mỗi bảo bối mang một mã số nguyên dương) và liên tục bỏ vào ba lô. Quá trình bỏ bảo bối dừng lại khi Nobita nhặt được số 0. Bạn hãy cho biết trong ba lô có bao nhiêu bảo bối và in lại danh sách các bảo bối đó nhé!
| Đầu vào | Một dãy các số nguyên dương kết thúc bằng số 0 (số 0 chỉ là tín hiệu dừng, không phải bảo bối). | |
|---|---|---|
| Đầu ra | Dòng 1: Số lượng bảo bối trong ba lô. Dòng 2: Danh sách các bảo bối theo thứ tự được bỏ vào túi, cách nhau một khoảng trắng. | |
| Test | Input | Output |
| 12 45 9 100 7 0 | 5 12 45 9 100 7 | |
Bài 2. Tuyển chọn đội tuyển tin học
Thầy giáo muốn chọn ra các bạn học sinh có điểm kiểm tra từ 8 điểm trở lên để vào đội tuyển thi Tin học. Thầy nhập danh sách điểm của cả lớp vào máy tính. Bạn hãy dùng vector để lọc ra danh sách điểm của các bạn được chọn nhé!
| Đầu vào | Dòng 1: Số nguyên n (1 ≤ n ≤ 105) – số học sinh cả lớp. Dòng 2: n số nguyên (0 ≤ a[i] ≤ 10) là điểm số của các bạn. | |
|---|---|---|
| Đầu ra | Dòng 1: Số lượng bạn được vào đội tuyển. Dòng 2: Điểm của các bạn được chọn theo đúng thứ tự ban đầu. Nếu không có ai đạt từ 8 điểm trở lên thì để trống. | |
| Test | Input | Output |
| 6 9 5 8 7 10 6 | 3 9 8 10 | |
Bài 3. Push & Pop
Giờ ra chơi, các bạn học sinh xếp hàng mua đồ ăn ở căng-tin trường. Bác quản lý phục vụ các bạn theo các quy ước: Lệnh 1 x: Bạn mang mã số x vừa đến và xếp vào cuối hàng. Lệnh 2: bạn đứng ở cuối hàng đổi ý không mua nữa, rời khỏi hàng, bỏ qua nếu hàng rỗng.
Hãy in ra danh sách các bạn còn lại trong hàng sau khi kết thúc giờ ra chơi.
| Đầu vào | Dòng 1: Số nguyên q (1 ≤ q ≤ 105) – số lượng thao tác. q dòng tiếp theo, mỗi dòng mô tả một thao tác dạng 1 x hoặc 2 | |
|---|---|---|
| Đầu ra | In ra danh sách mã số các bạn còn lại trong hàng. Nếu không còn ai thì in EMPTY. | |
| Test | Input | Output |
| 6 1 10 1 20 2 1 30 1 40 2 | 10 30 | |
Bài 4. Đảo ngược túi bi
Bạn Nam có một túi đựng n viên bi ma thuật. Nam muốn lấy từng viên bi ra và xếp lại theo thứ tự ngược lại hoàn toàn so với thứ tự ban đầu. Hãy giúp Nam in ra dãy số bi sau khi đã đảo ngược!
| Đầu vào | Dòng 1: Số nguyên n (1 ≤ n ≤ 105) – số lượng viên bi. Dòng 2: n số nguyên là giá trị ghi trên các viên bi. | |
|---|---|---|
| Đầu ra | In ra dãy số theo thứ tự từ viên bi cuối cùng về viên bi đầu tiên. | |
| Test | Input | Output |
| 5 1 3 5 7 9 | 9 7 5 3 1 | |
Bài 5. Truy vết bảo bối X
Trong túi bảo bối của Nobita gồm n món đồ, Nobita muốn kiểm tra xem món bảo bối có mã số X có nằm trong túi hay không. Nếu có, hãy chỉ ra vị trí xuất hiện đầu tiên (chỉ số tính từ 0) và số lần món bảo bối đó xuất hiện trong túi.
| Đầu vào | Dòng 1: Hai số nguyên n (1 ≤ n ≤ 105), x (|x| ≤ 109). Dòng 2: n số nguyên biểu diễn các mã số bảo bối. | |
|---|---|---|
| Đầu ra | Nếu tìm thấy, in ra 2 số: chỉ số đầu tiên tìm thấy và số lần xuất hiện của x. Nếu không tìm thấy in ra -1. | |
| Test | Input | Output |
| 7 5 2 5 1 5 8 5 9 | 1 3 | |
Bài 6. Ngôi sao may mắn (Tìm Max & đếm)
Một nhóm bạn tham gia trò chơi hái sao. Mỗi bạn hái được một số lượng ngôi sao nhất định và lưu vào danh sách vector. Hãy tìm xem số lượng ngôi sao nhiều nhất mà một bạn hái được là bao nhiêu và có bao nhiêu bạn cùng đạt được số lượng kỷ lục đó?
| Đầu vào | Dòng 1: Số nguyên n (1 ≤ n ≤ 105) – số người tham gia. Dòng 2: n số nguyên (0 ≤ a[i] ≤ 109) là số sao của từng bạn. | |
|---|---|---|
| Đầu ra | In ra hai số nguyên: Số sao kỷ lục lớn nhất và số lượng bạn cùng đạt kỷ lục đó. | |
| Test | Input | Output |
| 6 15 28 35 12 35 35 | 35 3 | |
Bài 7. Gộp hai túi kẹo
Bo và Bi mỗi bạn có một túi kẹo n, m chiếc. Hai bạn quyết định đổ chung hai túi kẹo vào một chiếc giỏ lớn, kẹo của Bo được xếp vào trước, kẹo của Bi được xếp tiếp theo vào sau. Hãy in ra toàn bộ số kẹo trong giỏ lớn!
| Đầu vào | Dòng 1: Hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n số nguyên trong túi của Bo Dòng 3: m số nguyên trong túi của Bi. | |
|---|---|---|
| Đầu ra | In ra toàn bộ n + m kẹo sau khi đã gộp vào một vector duy nhất. | |
| Test | Input | Output |
| 3 4 1 3 5 2 4 6 8 | 1 3 5 2 4 6 8 | |
Bài 8. Vệ tinh dò tìm số chẵn cuối cùng
Một trạm thu phát tín hiệu liên tục nhận các con số từ vũ trụ gửi về và lưu vào vector. Trạm trưởng muốn tìm xem tín hiệu số chẵn cuối cùng được gửi về là số nào và nằm ở vị trí chỉ số bao nhiêu trong vector.
| Đầu vào | Dòng 1: Số nguyên n(1 ≤ n ≤ 105). Dòng 2: n số nguyên là dãy tín hiệu (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | In ra giá trị của số chẵn cuối cùng và chỉ số của nó (tính từ 0). Nếu cả dãy toàn số lẻ thì in -1. | |
| Test | Input | Output |
| 6 3 8 5 12 7 9 | 12 3 | |
Bài tập tự luyện
Bài 1. Phân loại quân cờ Chẵn - Lẻ
Bạn Tí có một hộp chứa n quân cờ số. Tí muốn phân loại toàn bộ số cờ này vào hai vector riêng biệt: Túi 1 chỉ chứa các quân cờ mang số chẵn, Túi 2 chỉ chứa các quân cờ mang số lẻ. In các quân cờ trong từng túi theo thứ tự xuất hiện ban đầu.
| Đầu vào | Dòng 1: Số nguyên n(1 ≤ n ≤ 105). Dòng 2: n số nguyên biểu diễn các quân cờ (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | Dòng 1: Số lượng và các số trong túi chẵn (cách nhau khoảng trắng). Dòng 2: Số lượng và các số trong túi lẻ (cách nhau khoảng trắng). Nếu túi nào rỗng thì in EMPTY. | |
| Test | Input | Output |
| 6 1 4 7 8 2 5 | 3 4 8 2 3 1 7 5 | |
Bài 2. Cắt tỉa nhánh khô (Lọc bỏ số âm)
Một cây cảnh điện tử ghi lại sự phát triển của các nhánh bằng các chỉ số nguyên. Các nhánh có chỉ số âm là các nhánh bị sâu bệnh cần phải cắt bỏ. Hãy tạo một vector mới chỉ chứa các nhánh khỏe mạnh (chỉ số ≥ 0) và in ra kết quả.
| Đầu vào | Dòng 1: Số nguyên n(1 ≤ n ≤ 105). Dòng 2: n số nguyên (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | In ra các số khỏe mạnh được giữ lại. Nếu tất cả các nhánh đều bị cắt bỏ thì in EMPTY. | |
| Test | Input | Output |
| 6 5 -2 8 -9 0 12 | 5 8 0 12 | |
Bài 3. Sưu tầm thẻ bài độc nhất
Vy rất thích sưu tầm thẻ bài. Mỗi khi có một thẻ bài mới mang giá trị x, Vy chỉ bỏ vào cuốn album vector nếu trong album chưa từng có thẻ bài mang số x nào trước đó. Hãy in ra những thẻ bài có trong album của Vy!
| Đầu vào | Dòng 1: Số nguyên n(1 ≤ n ≤ 104). Dòng 2: n số nguyên 1 ≤ a[i] ≤ 104. | |
|---|---|---|
| Đầu ra | In ra danh sách các thẻ bài được cất vào album theo thứ tự xuất hiện lần đầu. | |
| Test | Input | Output |
| 7 3 5 3 2 5 8 2 | 3 5 2 8 | |
Bài 4. Băng chuyền siêu thị thông minh
Một băng chuyền thông minh có thể nhận hàng ở cuối và nhả hàng ra ở cuối theo các mã lệnh:
- add x: Đặt món hàng có giá trị x vào cuối băng chuyền (push_back(x)).
- remove: Nhấc món hàng cuối cùng ra khỏi băng chuyền (pop_back()), nếu băng chuyền không có hàng thì bỏ qua.
- get: In ra giá trị của món hàng đang đứng ở cuối băng chuyền hiện tại (v.back()), nếu rỗng in -1.
| Đầu vào | Dòng 1: Số nguyên t (1 ≤ t ≤ 105) là số lượng thao tác. t dòng tiếp theo chứa một trong ba loại lệnh: add x, remove, hoặc get. | |
|---|---|---|
| Đầu ra | Mỗi khi gặp lệnh get, hãy in kết quả trên một dòng. | |
| Test | Input | Output |
| 7 add 15 add 25 get remove get remove get | 25 15 -1 | |
Bài 5. Erase và insert
Cho vector và 2 thao tác:
Thao tác 1 (1 k x): Chèn giá trị x vào vị trí k (tính từ 0) trong vector. Giả sử vector đang có n phần tử, chỉ số chèn hợp lệ sẽ là từ 0 tới n, các vị trí không hợp lệ sẽ không thực hiện chèn.
Thao tác 2 (2 k): Xóa phần tử ở chỉ số k (tính từ 0) trong vector. Nếu k không nằm trong đoạn 0..n-1 (với n là số phần tử) thì sẽ không thực hiện xoá.
Hãy in ra các phần tử trong vector trên 1 dòng sau khi thực hiện xong mọi thao tác. Nếu vector rỗng in ra EMPTY.
| Đầu vào | Dòng 1 là m: số lượng phần tử trong vector. Dòng 2 là m số trong vector. Dòng 3 là q (1 ≤ q ≤200) – số thao tác được thực hiện. q dòng tiếp theo mỗi dòng mô tả thao tác. | |
|---|---|---|
| Đầu ra | In ra EMPTY nếu vector rỗng, ngược lại in ra các phần tử trong vector trên 1 dòng. | |
| Test | Input | Output |
| 5 40 87 73 47 22 5 1 3 21 2 3 2 0 2 1 1 0 70 | 70 87 47 22 | |
Bài 6. Dãy bậc thang đều đặn
Một dãy số được gọi là "Dãy bậc thang đều đặn" nếu độ chênh lệch giữa hai số đứng cạnh nhau bất kỳ luôn luôn bằng nhau (Ví dụ: dãy 2, 5, 8, 11 có độ lệch đều bằng 3). Hãy viết chương trình kiểm tra xem vector số đã cho có phải là bậc thang đều đặn hay không?
| Đầu vào | Dòng 1: Số nguyên n (3 ≤ n ≤ 105). Dòng 2: n số nguyên (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | In ra YES nếu dãy là bậc thang đều đặn, ngược lại in NO. | |
| Test | Input | Output |
| 5 3 7 11 15 19 | YES | |
| 3 1 3 1 | NO | |
Bài 7. Cặp đôi chênh lệch nhỏ nhất
Cho một vector gồm n số nguyên đã được xếp theo thứ tự tăng dần. Hãy tìm khoảng cách chênh lệch nhỏ nhất giữa hai phần tử đứng cạnh nhau trong vector!
| Đầu vào | Dòng 1: Số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên (|a[i]| ≤ 109) đã được sắp xếp tăng dần. | |
|---|---|---|
| Đầu ra | In ra một số nguyên duy nhất là hiệu nhỏ nhất giữa hai phần tử cạnh nhau: min(a[i+1] – a[i]). | |
| Test | Input | Output |
| 5 1 5 8 10 17 | 2 | |
Bài 8. Vector các vector
Cho 1 bảng số có n dòng và m cột, bạn hãy lưu bảng số này vào một vector các vector (vector<vector<int>>) trong đó mỗi hàng của bảng số bạn lưu vào 1 vector. Hãy lật ngược từng dòng của bảng số sau đó in ra màn hình.
| Đầu vào | Dòng 1 là hai số n và m (1 ≤ n, m ≤ 100); n dòng tiếp theo mỗi dòng là m số nguyên kiểu int. | |
|---|---|---|
| Đầu ra | In ra bảng số sau khi lật ngược từng dòng | |
| Test | Input | Output |
| 5 5 7 5 6 1 6 7 4 2 3 9 5 0 4 1 9 2 0 1 5 4 7 5 6 7 3 | 6 1 6 5 7 9 3 2 4 7 9 1 4 0 5 4 5 1 0 2 3 7 6 5 7 | |